ID3 - LinkFang.de





ID3


Dieser Artikel beschäftigt sich mit dem ID3-Algorithmus. Für das Format der Metainformationen bei MP3-Dateien, siehe ID3-Tag.

ID3 (Iterative Dichotomiser 3) ist ein Algorithmus, der zur Entscheidungsfindung dient. Er wird bei Entscheidungsbäumen eingesetzt. Der australische Forscher J. Ross Quinlan publizierte diesen Algorithmus erstmals im Jahre 1986.[1] ID3 war in seinen ersten Jahren sehr einflussreich. Er findet auch heute noch in einigen Produkten Verwendung. ID3 gilt als Vorgänger des C4.5-Algorithmus.

ID3 wird verwendet, wenn bei großer Datenmenge viele verschiedene Attribute von Bedeutung sind und deshalb ein Entscheidungsbaum ohne große Berechnungen generiert werden soll. Somit entstehen meist einfache Entscheidungsbäume. Es kann aber nicht garantiert werden, dass keine besseren Bäume möglich wären.

Die Basisstruktur von ID3 ist iterativ. Es werden zu jedem noch nicht benutzten Attribut Entropien bezüglich der Trainingsmenge berechnet. Das Attribut mit dem höchsten Informationsgewinn (engl.: information gain) bzw. der kleinsten Entropie, wird gewählt und daraus ein neuer Baum-Knoten generiert. Das Verfahren terminiert, wenn alle Trainingsinstanzen klassifiziert wurden, d.h. wenn jedem Blattknoten eine Klassifikation zugeordnet ist.

Algorithmus

Wenn alle Elemente aus T (Daten) zu einer Klasse gehören

Dann
// Erzeuge ein Blatt //
Konstruiere ein Blatt mit der Klasse als Bezeichner
Sonst
// Erzeuge rekursiv einen Teilbaum //
Wähle das „informativste“ Merkmal xi
Beginn: Für_alle vorkommenden Werte von Merkmal xi
Konstruiere alle Teilbäume rekursiv mit den entsprechenden Teilmengen als Daten
Ende: Für_alle
Konstruiere einen Baumknoten mit Bezeichner xi und hänge alle erzeugten Teilbäume an
Ende Sonst

Auswahl der Merkmale

Für die Bildung der Teilbäume wird jeweils entsprechend der Informationstheorie das informativste Merkmal ausgewählt.

Sei [math]S[/math] die Menge der Merkmale mit ihrer jeweiligen Klassifizierung, [math]a \in A[/math] das zu prüfende Attribut aus der Menge der verfügbaren Attribute, [math]V(a)[/math] die Menge der möglichen Attributwerte von [math]a[/math] und [math]S_v[/math] die Untermenge von [math]S[/math], für die das Attribut [math]a[/math] den Wert [math]v[/math] annimmt. Der Gewinn, der durch Auswahl des Merkmals [math]a[/math] erzielt wird errechnet sich dann folgendermaßen:

[math]G(S, a) = Entropie(S) - \sum_{v \in V(a)} \dfrac{|S_v|}{|S|} Entropie(S_v) [/math].

Schließlich wählt man ein Attribut mit dem größtmöglichen Gewinn aus der Menge [math]\lbrace a_{next} \in A | G(S, a_{next}) = max_{a \in A}(G(S, a)) \rbrace [/math] als das nächste Attribut.

Diese Wahl führt zur Bevorzugung von Merkmalen mit vielen Wahlmöglichkeiten und damit zu einem breiten Baum. Um dem entgegenzuwirken kann eine Normalisierung über die Anzahl der Wahlmöglichkeiten durchgeführt werden.

Siehe auch

Weblinks

Einzelnachweise

  1. J. Ross Quinlan: Induction of Decision Trees. In: Machine learning 1.1. Band 1, Nr. 1, August 1985, S. 81–106.

Kategorien: Klassifikationsverfahren

Quelle: Wikipedia - http://de.wikipedia.org/wiki/ID3 (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.