ID3 (algoritmus)

Az ID3 algoritmus a döntési fa felépítésének egyik algoritmusa . John R. Quinlan tervezte John R. Quinlan . Ezt követően Quinlan készített egy továbbfejlesztett verziót - a C4.5 algoritmust .

Algoritmus

Vegye ki az összes nem használt jellemzőt, és számítsa ki az entrópiájukat a tesztmintákhoz viszonyítva
Válasszon olyan jellemzőt, amelynél az entrópia minimális (és az információnyereség maximális)
Készítsen egy fa csomópontot, amely tartalmazza ezt a tulajdonságot

Az algoritmus a következő:

ID3 (példatáblázat, célfunkció, szolgáltatások)

Ha minden példa pozitív, akkor adja vissza a "+" feliratú csomópontot.
Ha minden példa negatív, akkor adja vissza a "-" feliratú csomópontot.
Ha a jellemzőkészlet üres, akkor adja vissza a csomópontot azzal a címkével, amelyik a legtöbbször előfordul a példákban a cél jellemzőértékekben.
Másképp:
1. Az A az a jellemző, amely a legjobban osztályozza a példákat (maximális információs előnyökkel).
2. Hozzon létre egy döntési fa gyökerét; a gyökér jele ez lesz . $A$
3. Minden lehetséges értékhez ( ): $A$ $v_{i}$
  1. Adjon hozzá egy új faágat a gyökér alá egy értékkel rendelkező csomóponttal $A=v_{i}$
  2. Válassza ki a példák azon részhalmazát , amelyekben . $Példák (v_{i})$ $A=v_{i}$
  3. Ha a példák részhalmaza üres, akkor az új ág alá adjon hozzá egy csomópontot azzal a címkével, amelyik a legtöbbször előfordul a példákban a célelem értékeiben.
  4. Ellenkező esetben az új elágazás alá adjon hozzá egy részfát az ID3( , Target Feature, Features) rekurzív meghívásával. $Példák (v_{i})$
Gyökér visszaadása.

Irodalom

Paklin N.B., Oreshkov V.I. 9. fejezet // Üzleti elemzés: Az adatoktól a tudásig (+CD): oktatóanyag. 2. kiadás – Szentpétervár. : Péter, 2013. - S. 444-459. - ISBN 978-5-459-00717-6 .