Wie können kontinuierliche Daten in Entscheidungsbäumen (besser) diskretisiert werden?

Standardentscheidungsbaumalgorithmen wie ID3 und C4.5 haben einen Brute-Force-Ansatz zur Auswahl des Schnittpunkts in einem kontinuierlichen Feature. Jeder einzelne Wert wird als möglicher Schnittpunkt geprüft. (Mit getestet meine ich, dass zB der Informationsgewinn bei jedem möglichen Wert berechnet wird.)

Mit vielen fortlaufenden Funktionen und vielen Daten (daher viele Werte für jede Funktion) scheint dieser Ansatz sehr ineffizient zu sein!

Ich gehe davon aus, dass es ein heißes Thema im maschinellen Lernen ist, einen besseren Weg zu finden, dies zu tun. Tatsächlich ergab meine Google Scholar-Suche einige alternative Ansätze. Zum Beispiel mit k-Mitteln diskretisieren. Dann scheint es viele Artikel zu geben, die sich mit bestimmten Problemen in bestimmten Bereichen befassen.

Aber gibt es ein aktuelles Übersichtsartikel, einen Blogbeitrag oder ein Buch, das einen Überblick über gängige Ansätze zur Diskretisierung gibt? Ich konnte keinen finden ...

Oder vielleicht ist einer von Ihnen ein Experte auf diesem Gebiet und bereit, einen kleinen Überblick zu schreiben. Das wäre enorm hilfreich!

Nein, Sie möchten wahrscheinlich nicht alle möglichen Schnittpunkte in einer seriösen Implementierung ausprobieren. So beschreiben wir es in einfachen Einführungen in ID3, weil es leichter zu verstehen ist, aber normalerweise nicht so, wie es tatsächlich implementiert wird, weil es langsam ist. Insbesondere wenn es welche gibt$n$ Datenpunkte, dann müssen Sie testen $n-1$Kandidatenschwellen; Verwenden des naiven Algorithmus zum Berechnen des Informationsgewinns für jeden dieser Kandidatenschwellenwerte$O(n)$ Zeit pro Kandidat für insgesamt $O(n^2)$ Zeit.

In der Praxis gibt es Optimierungen, die dies erheblich beschleunigen:

1. Versuchen Sie nicht alle möglichen Schwellenwerte. Wählen Sie stattdessen eine Zufallsstichprobe von 1000 Kandidatenschwellenwerten (gleichmäßig zufällig ausgewählt aus dem Satz von$n-1$ Kandidatenschwellenwerte), berechnen Sie den Informationsgewinn für jeden und wählen Sie den besten aus.

2. Verwenden Sie dynamische Programmierung, um den Informationsgewinn aller effizient zu berechnen $n-1$ Splits, insgesamt $O(n)$Zeit durch Wiederverwendung der Berechnung. Der Algorithmus ist ziemlich einfach abzuleiten.