R. Ferber: Data Mining & Information Retrieval 1.5.2.4.13

4.2.4.2: Formale Beschreibung des ID3 Algorithmus

Nach dieser eher informalen Beschreibung soll nun eine formalere und ausführlichere Beschreibung gegeben werden, zunächst für die Konstruktion des Entscheidungsbaumes:

4.2.4.2.1: Algorithmus

Sei

A_i:D->R_i, 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.

Ordne alle Beispiele einem (Wurzel-) Knoten zu:
N=(A,K,z)=N_0,0=(A,K_0,0,z), K_0,0=D

Falls alle Tupel aus K der selben Kategorie angehören, falls also gilt A₀(d_i)=z_k d_iK 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 2 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 Attributes einen Kindknoten N_{i,r_j}=(A,K_{i,r_j}) mit unbestimmtem aktuellem Attribut A und
K_{i,r_j}=A^-1_i({r_j})K

(also mit den Beispielen aus K , bei denen das Attribut A_i den Wert r_j annimmt) an.
Falls ein unbearbeiteter Kindknoten N_{i,r_j} exisitiert, setze N:=N_{i,r_j} . Andernfalls prüfe, ob es einen unbearbeiteten Geschwisterknoten N_{i,r_k} gibt und setze in diesem Fall N:=N_{i,r_k} . Ist das auch nicht der Fall, setzte N auf den Elternknoten.
Falls NN_0,0 gehe nach Schritt 2, andernfalls beende den Alogrithmus.

4.2.4.2.2: Auswahlkriterium

In Schritt 2 muß ein Attribut A_i:D->R_i ausgewählt werden, das zur Selektion verwendet werden soll. Für jedes Attribut, das in Frage kommt, wird der Wert

berechnet. Dabei gilt

mit

q_k,r gibt also den Anteil der Tupel aus der Kategorie r unter den Tupeln des Knotens an, bei denen das Attribut A_i den Wert k annimmt. Der Entropiewert I(k,K) gibt damit an, wie durchmischt die Tupel des Knotens in Bezug auf das Attribut A₀ , also in Bezug auf die gesuchte Kategorisierung, sind.

Es wird das Attribut zur Selektion gewählt, bei dem der Wert E(A_i,K_{j,r_m}) minimal ist, bei der die Kindknoten also bezüglich der gesuchten Kategorie möglichst wenig durchmischt sind.

Die Auswahl der Optimierungsheuristik ist folgendermaßen motiviert: Betrachtet man die Beispiele eines Knotens als Informationsquelle über die Zugehörigkeit zu den Zielkategorien, dann gibt Formel ( 4.2.4.2.2 ) eine Abschätzung des Informationsgehalts bzw. der Entropie eines Kindknotens an, d. h. des mittleren Informationsgewinns, den das Inspizieren eines Beispiels aus der Menge bringt. Sind fast alle Beispiele der Knotenmenge aus einer Kategorie, ist der zu erwartende Informationsgewinn gering. Sind sie sogar alle aus einer Kategorie, ist entweder q_k,r=0 oder q_k,r=1 und damit ln(q_k,r)=ln(1)=0 . In beiden Fällen ist das Produkt -q_k,rln(q_k,r) und damit I(k,K) gleich Null. In den anderen Fällen ist der Wert positiv, weil das Argument des Logarithmus zwischen 0 und 1 liegt und der Logarithmus daher negativ ist. Formel ( _4.2.4.2.2_ ) gibt also den mittleren erwarteten Informationsgehalt der Kindknoten bei einer Aufteilung nach Attribut A_i an. Je kleiner der ist, desto größer ist der Informationsgewinn durch die Wahl von A_i .