CART (Algorithmus)
Dieser Artikel befasst sich mit dem Algorithmus, andere Bedeutungen unter CART (Begriffsklärung).
CART (Classification and Regression Trees) ist ein Algorithmus, der zur Entscheidungsfindung dient. Er wird bei Entscheidungsbäumen eingesetzt.
Der CART-Algorithmus wurde erstmals 1984 von L. Briemen publiziert.
Ein bedeutendes Merkmal des CART-Algorithmus ist, dass nur Binärbäume erzeugt werden können, das heisst, dass an jeder Verzweigung immer genau zwei Äste vorhanden sind. Das zentrale Element dieses Algorithmus ist also das Finden einer optimalen binären Trennung.
Beim CART-Algorithmus wird die Attributsauswahl durch die Maximierung des Informationsgehalts gesteuert. CARTs zeichnen sich dadurch aus, dass sie die Daten in Bezug auf die Klassifikation optimal trennen. Dies wird mit einem Schwellwert erreicht, der zu jedem Attribut gesucht wird. Der Informationsgehalt eines Attributes wird als hoch erachtet, wenn durch die Auswertung der sich aus der Teilung über die Schwellwerte ergebenden Attributausprägungen mit einer hohen Trefferquote eine Klassifikation vorgenommen werden kann. Bei den Entscheidungsbäumen, welche durch den CART-Algorithmus berechnet werden, gilt: Je höher der Informationsgehalt eines Attributs in Bezug auf die Zielgrösse, desto weiter oben im Baum findet sich dieses Attribut.
Die Entscheidungsschwellwerte ergeben sich jeweils durch die Optimierung der Spaltenentropien. Die Gesamtentropien der Attribute ergeben sich durch ein gewichtetes Mittel aus den Spaltenentropien.