Mesterséges Intelligencia I. ID3 futás Futtassuk az ID3 algoritmust az S adatbázison az E(S) = 4p+ p− entrópia használatával. Kezdeti hívás: ID3 (S, {Outlook, T emperature, Humidity, W ind})
1. ábra. S adatbázis (eredeti) A következő Gain értékek maximumaként tudja az algoritmus kiválasztani az aktuális hívásban létrejövő csomópont címkéjét. 90 9 5 = E(S) = 4 14 14 98 90 5 23 4 40 5 32 90 24 Gain(S, Outlook) = − 4 + 4 + 4 − = 0.23 = 98 14 5 5 14 4 4 14 5 5 98 35 90 90 37 6 42 4 31 4 22 Gain(S, T emp) = = − 4 + 4 + 4 − = 0.03 98 14 4 4 14 6 6 14 4 4 98 42 90 36 7 61 7 34 90 = − 4 + 4 − = 0.18 Gain(S, Hum) = 98 14 7 7 14 7 7 98 49 90 90 6 6 33 8 62 Gain(S, W ind) = = − 4 + 4 − = 0.06 98 14 8 8 14 6 6 98 7 Maximális a Sunny attributum → ő lesz a gyökér, 3 leszármazottal.
2. ábra. Első hívás által létrehozott csomópont Minden egyes leszármazott egy-egy rekurzív hívással lesz létrehozva. A Sunny él mentén történő hívás: ID3 (SOutlook=Sunny , {T emperature, Humidity, W ind})
3. ábra. SOutlook=Sunny adatbázis A következő Gain értékek maximumaként tudja az algoritmus kiválasztani az aktuális hívásban létrejövő csomópont címkéjét. 24 23 = E(S) = 4 55 25 24 24 4 2 02 2 11 1 10 Gain(SOutlook=Sunny , T emp) = = − 4 + 4 + 4 − 25 5 22 5 22 5 11 25 10 24 24 3 03 2 20 Gain(SOutlook=Sunny , Hum) = = − 4 + 4 25 5 33 5 22 25 3 12 2 11 24 24 − 4 + 4 −X >0 = Gain(SOutlook=Sunny , W ind) = 25 5 33 5 22 25 Maximális a Humidity attributum → ő lesz az Outlook csúcs Sunny él menti leszármazottja.
4. ábra. Második hívás által létrehozott csomópont Minden egyes leszármazott egy-egy rekurzív hívással lesz létrehozva. A High él mentén történő hívás: ID3 (SOutlook=Sunny∧Humidity=High , {T emperature, W ind})
5. ábra. SOutlook=Sunny∧Humidity=High adatbázis Ahogy látható az adatbázis homogén (csak N o címkével rendelkező példákat tartalmaz), ami az ID3 algoritmus megállási feltétele. Tehát megállunk és egy N o címkével rendelkező levelet hozunk létre.
6. ábra. Második hívás által létrehozott csomópont
A N ormal él mentén történő hívás: ID3 (SOutlook=Sunny∧Humidity=N ormal , {T emperature, W ind})
7. ábra. SOutlook=Sunny∧Humidity=N ormal adatbázis Ahogy látható az adatbázis homogén (csak Y es címkével rendelkező példákat tartalmaz), ami az ID3 algoritmus megállási feltétele. Tehát megállunk és egy Y es címkével rendelkező levelet hozunk létre.
8. ábra. Harmadik hívás által létrehozott csomópont Mivel a Humidity csomópont teljes részfáját létrehoztuk visszatér a rekurzió.
9. ábra. Visszatérünk a gyökér szintjére A Overcast él mentén történő hívás: ID3 (SOutlook=Overcast , {T emperature, Humidity, W ind})
10. ábra. SOutlook=Overcast adatbázis Ahogy látható az adatbázis homogén (csak Y es címkével rendelkező példákat tartalmaz), ami az ID3 algoritmus megállási feltétele. Tehát megállunk és egy Y es címkével rendelkező levelet hozunk létre.
11. ábra. A következő hívás által létrehozott csomópont
A Rain él mentén történő hívás: ID3 (SOutlook=Rain , {T emperature, Humidity, W ind})
12. ábra. SOutlook=Rain adatbázis A következő Gain értékek maximumaként tudja az algoritmus kiválasztani az aktuális hívásban létrejövő csomópont címkéjét. 32 24 = 55 25 24 14 3 21 2 11 24 = − 4 + 4 − Gain(SOutlook=Rain , T emp) = 25 5 33 5 22 25 15 24 24 14 2 11 3 21 Gain(SOutlook=Rain , Hum) = = − 4 + 4 − 25 5 22 5 33 25 15 24 3 30 2 02 24 = − 4 + 4 Gain(SOutlook=Rain , W ind) = 25 5 33 5 22 25 E(S) = 4
Maximális a W ind attributum → ő lesz az Outlook csúcs Rain él menti leszármazottja.
13. ábra. A következő hívás által létrehozott csomópont
Minden egyes leszármazott egy-egy rekurzív hívással lesz létrehozva. A W eak él mentén történő hívás: ID3 (SOutlook=Rain∧W ind=W eak , {T emperature, Humidity})
14. ábra. SOutlook=Rain∧W ind=W eak adatbázis Ahogy látható az adatbázis homogén (csak Y es címkével rendelkező példákat tartalmaz), ami az ID3 algoritmus megállási feltétele. Tehát megállunk és egy Y es címkével rendelkező levelet hozunk létre.
15. ábra. Következő hívás által létrehozott csomópont
A Strong él mentén történő hívás: ID3 (SOutlook=Rain∧W ind=Strong , {T emperature, Humidity})
16. ábra. SOutlook=Rain∧W ind=Strong adatbázis Ahogy látható az adatbázis homogén (csak N o címkével rendelkező példákat tartalmaz), ami az ID3 algoritmus megállási feltétele. Tehát megállunk és egy N o címkével rendelkező levelet hozunk létre.
17. ábra. Következő hívás által létrehozott csomópont Mivel a W ind csomópont teljes részfáját létrehoztuk visszatér a rekurzió. Mivel a Outlook csomópont teljes részfáját létrehoztuk visszatér a rekurzió. A futás véget ér.
Ugyan ez a feladat Shanon entropiával számolva: X E:− pi log2 pi
9 5 5 9 − log2 = 0.94 E(S) = − log2 14 14 14 14 4 0 0 2 3 3 3 2 3 4 5 2 5 3 4 (− log2 − log2 ) + (− log2 − log2 ) + (− log2 − log2 ) = 0.25 Gain(S, Outlook) = 0.94− 14 4 4 4 4 14 5 5 5 5 14 5 5 5 5 4 3 1 1 2 2 2 4 2 2 3 4 2 6 4 Gain(S, T emp) = 0.94− (− log2 − log2 ) + (− log2 − log2 ) + (− log2 − log2 ) = 0.029 14 4 4 4 4 14 4 4 4 4 14 6 6 6 6 7 3 4 4 6 1 1 3 7 6 Gain(S, Hum) = 0.94 − (− log2 − log2 ) + (− log2 − log2 ) = 0.15 14 7 7 7 7 14 7 7 7 7 3 3 3 6 2 2 3 8 6 6 (− log2 − log2 ) + (− log2 − log2 ) = 0.048 Gain(S, W ind) = 0.94− 14 6 6 6 6 14 8 8 8 8
2 3 3 2 E(SOutlook=Sunny ) = − log2 − log2 = 0.97 5 5 5 5 2 0 0 2 2 1 1 1 1 0 0 2 1 1 1 Gain(SOutlook=Sunny , T emp) = 0.97− (− log2 − log2 ) + (− log2 − log2 ) + (− log2 − log2 ) 5 2 2 2 2 5 2 2 2 2 5 1 1 1 1 3 0 0 3 3 2 0 0 2 2 Gain(SOutlook=Sunny , Hum) = 0.97− (− log2 − log2 ) + (− log2 − log2 ) = 0.97 5 3 3 3 3 5 2 2 2 2 2 1 1 1 1 1 2 2 3 1 Gain(SOutlook=Sunny , W ind) = 0.97− (− log2 − log2 ) + (− log2 − log2 ) = 0.02 5 2 2 2 2 5 3 3 3 3 3 2 2 3 E(SOutlook=Rain ) = − log2 − log2 = 0.97 5 5 5 5 2 1 1 1 1 1 2 1 3 2 Gain(SOutlook=Rain , T emp) = 0.97− 0 + (− log2 − log2 ) + (− log2 − log2 ) = 0.02 5 3 3 3 3 5 2 2 2 2 2 1 1 1 1 2 1 1 3 2 Gain(SOutlook=Rain , Hum) = 0.97− (− log2 − log2 ) + (− log2 − log2 ) = 0.02 5 2 2 2 2 5 3 3 3 3 0 2 2 3 0 0 3 3 2 0 Gain(SOutlook=Rain , W ind) = 0.97− (− log2 − log2 ) + (− log2 − log2 ) = 0.97 5 2 2 2 2 5 3 3 3 3
