4.4.1.1.3: Das CART Verfahren

Als eine andere Methode die berechneten Koeffizienten zu verwenden, beschreiben Brodley und Utgoff das von Breiman, Friedman, Olshen und Stone (1984 [->]) eingeführte CART Verfahren. Dabei wird als Gütefunktion - ähnlich wie das Entropiemaß beim ID3 Algorithmus - ein Maß für die Vermischung ( impurity) der Zielmengen verwendet. Zur Bestimmung der zu verwendenden Attribute wird eine Rückwärtselimination durchgeführt, bei der die Koeffizienten aber nicht neu berechnet werden. Es wird lediglich jeweils ein Attribut versuchsweise weggelassen und dann die Vermischung berechnet. Für das Attribut, bei dem die Vermischung am meisten steigt, wird die Schwelle, also der Wert x₀ optimiert, die anderen Koeffizienten werden aber nicht verändert. Ist der Quotient aus dem damit erziehlten Vermischungsgrad und der größten Vermischungszunahme kleiner als eine vorgegebene Schranke, wird das Attribut tatsächlich weggelassen. Erst wenn dieses Verfahren beendet ist, werden für die übriggebliebenen Attribute neue Koeffizienten berechnet. Falls das so gewonnene zusammengesetzte Attribut besser als alle Einzelattribute ist, wird es als Attribut des Knotens verwendet, sonst wird das beste Einzelattribut benutzt.