ID3 (algoritm)

ID3-algoritmen är en av algoritmerna för att bygga ett beslutsträd . Designad av John R. Quinlan . John R. Quinlan . Därefter skapade Quinlan en förbättrad version - C4.5-algoritmen .

Algoritm

Ta alla oanvända funktioner och beräkna deras entropi i förhållande till testprover
Välj en funktion för vilken entropin är minimal (och informationsvinsten är maximal)
Gör en trädnod som innehåller denna egenskap

Algoritmen är följande:

ID3(Tabell med exempel, målfunktion, funktioner)

Om alla exempel är positiva, returnera noden märkt "+".
Om alla exempel är negativa, returnera noden märkt "-".
Om funktionsuppsättningen är tom, returnera noden med den etikett som förekommer mest i målfunktionsvärdena i exemplen.
Annat:
1. A är den funktion som bäst klassificerar exempel (med maximal informationsnytta).
2. Skapa en beslutsträdrot; tecknet i roten kommer att vara . $A$
3. För varje möjligt värde ( ): $A$ $v_{i}$
  1. Lägg till en ny trädgren under roten med en nod med värde $A=v_{i}$
  2. Välj en delmängd av exempel som har . $Exempel(v_{i})$ $A=v_{i}$
  3. Om delmängden av exempel är tom, lägg till en nod under denna nya gren med den etikett som förekommer mest i målfunktionens värden i exemplen.
  4. Annars, under denna nya gren, lägg till ett underträd genom att anropa rekursivt ID3( , Target Feature, Features) $Exempel(v_{i})$
Returnera rot.

Litteratur

Paklin N.B., Oreshkov V.I. Kapitel 9. // Business Analytics: From Data to Knowledge (+CD): Handledning. 2:a uppl. - St Petersburg. : Peter, 2013. - S. 444-459. - ISBN 978-5-459-00717-6 .