Algorithmus 3: ID3 im Detail

Sei

Ai:D->Ri, i=1,.. .,n

eine Menge vorhersagender Attribute mit endlichen Wertebereichen R_i auf einer endlichen Menge D von Beispielen und A₀:D->R₀={z₁,...,z_m} ein vorherzusagendes Attribut. Im folgenden rekursiven Algorithmus bezeichne N=(A,K,z) den aktuellen Knoten, wobei A{A₀,...,A_n} das aktuelle Attribut, KD die Menge der Beispiele, die dem Knoten zugeordnet sind, und zR₀ eine Kategorie bezeichnen.

1. Ordne alle Beispiele einem (Wurzel-) Knoten zu:

   N=(A,K,z)=N0,0 =(A,K0,0,z),  K0,0=D

2. Falls alle Tupel aus K derselben Kategorie angehören, falls also gilt A₀(d_i) =z_k  d_i K und ein z_kR₀ , setze A:=A₀ und z=z_k . Andernfalls wähle ein Attribut A_i:D->R_i ,  i{1,...,n} , das in K mindestens zwei verschiedene Werte annimmt (  d₁,d₂K mit A_i(d₁) A_i(d₂) ) als aktuelles Attribut für den Knoten N und füge für jeden Wert r_jR_i mit A^-1_i({r_j })KØ des Attributs einen Kindknoten N_i,rj=(A,K_i,rj ) mit unbestimmtem aktuellem Attribut A und

   Ki,rj=A-1i( {rj}) K

   an (also mit den Beispielen aus K , bei denen das Attribut A_i den Wert r_j annimmt).
3. Falls ein unbearbeiteter Kindknoten N_i,rj von N existiert, setze N:=N_i,rj . Andernfalls prüfe, ob es einen unbearbeiteten Geschwisterknoten N_i,rk von N gibt und setze in diesem Fall N:=N_i,rk . Ist das auch nicht der Fall, setzte N auf den Elternknoten von N .
4. Falls NN_0,0 gilt, gehe zu Schritt 2, andernfalls beende den Algorithmus.