Neuer Ansatz liefert optimale Entscheidungsbäume mit kontinuierlichen Merkmalen

In den letzten Jahren wurden bedeutende Fortschritte bei Algorithmen zur Erzeugung optimaler Entscheidungsbäume erzielt – vor allem für binäre Merkmale. Die Übertragung dieser Methoden auf kontinuierliche Attribute bleibt jedoch schwierig, weil für jedes Merkmal unzählige mögliche Trennpunkte existieren.

Ein kürzlich vorgestellter exakter Algorithmus kann optimale Bäume für kontinuierliche Merkmale berechnen, doch die Rechenzeit wächst exponentiell mit der Tiefe des Baumes. In der Praxis ist er daher meist auf sehr flache Strukturen (typischerweise Tiefe 3 oder 4) beschränkt. Der Ansatz nutzt eine Tiefensuche, die zunächst das linke Teilbaumsegment vollständig optimiert, bevor das rechte Segment angegangen wird. Diese Strategie führt zwar zu optimalen Lösungen, wenn genügend Zeit zur Verfügung steht, aber bei vorzeitiger Unterbrechung entstehen oft stark unausgeglichene, suboptimale Bäume. In solchen Fällen liefern sogar einfache, gierige Verfahren wie C4.5 manchmal bessere Ergebnisse.

Um dieses Problem zu lösen, präsentiert die neue Arbeit einen „Anytime“-Ansatz, der dennoch vollständig ist. Durch den Einsatz von Limited Discrepancy Search wird die Rechenleistung gleichmäßiger über die gesamte Baumstruktur verteilt. Dadurch steht jederzeit ein qualitativ hochwertiger Entscheidungsbaum zur Verfügung, selbst wenn der Algorithmus unterbrochen wird.

Experimentelle Tests zeigen, dass der neue Ansatz die bisherige Methode in Bezug auf die Anytime-Performance deutlich übertrifft. Damit eröffnet sich ein vielversprechender Weg, optimale Entscheidungsbäume mit kontinuierlichen Merkmalen in realen Anwendungen effizienter zu nutzen.