Iterative Dichotomiser 3
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. 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 bessere Bäume möglich wären.
Die Basisstruktur von ID3 ist iterativ. Zuerst wird ein Baum generiert, indem im Zufallsprinzip ein Teil des Trainingssets gewählt wird. Dieser Baum klassifiziert alle Objekte der Auswahl. Danach werden sämtliche Objekte des Trainingssets klassifiziert. Sofern der Baum eine korrekte Antwort für alle Objekte gibt, ist der Prozess abgeschlossen. Falls dies nicht der Fall ist, wird die Auswahl ergänzt durch einen Teil der nicht korrekt klassifizierten Objekte und der Prozess geht so weiter. Somit wird bereits nach einigen Iterativschritten ein Entscheidungsbaum generiert, der bis zu 30.000 Objekte und bis zu 50 Attribute korrekt klassifiziert.