Online Decision Tree
- Eingeführt von
- Domingos, P. & Hulten, G.
- Jahr
- 2000
- Typ
- Incremental supervised classifier
- Familie
- Machine learning
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Ein Online Decision Tree ist ein Entscheidungsbaum, der sich inkrementell aus einem kontinuierlichen Datenstrom entwickelt, ohne vergangene Beispiele erneut zu betrachten.
Der dominierende Algorithmus, der Hoeffding Tree (VFDT), verwendet die Hoeffding-Schranke, um zu entscheiden, wann genügend Beispiele an einem Knoten gesehen wurden, um ihn mit Sicherheit zu teilen. Dies ermöglicht skalierbare Echtzeitklassifizierung auf potenziell unendlichen Datenströmen.
Die Intuition hinter der Methode
Ein Standard-Entscheidungsbaum wird aufgebaut, indem der vollständige Datensatz wiederholt gescannt wird, um die besten Teilungen zu finden. In Streaming-Umgebungen ist dies unmöglich, da Daten einzeln eintreffen und nicht gespeichert werden können. Der Online-Ansatz speichert nur laufende Statistiken an jedem Blatt. Sobald genügend Beispiele gesammelt sind, bestätigt die Hoeffding-Schranke – eine statistische Garantie –, dass die offensichtlich beste Teilung auch dann die beste bliebe, wenn wir alle möglichen Beispiele gesehen hätten. Erst dann teilt sich der Baum tatsächlich, wächst von einem einzelnen Blatt zu einer sich ständig vertiefenden Struktur, ohne jemals auf vergangene Daten zurückzublicken.
Geschichte
Der grundlegende Algorithmus, der Very Fast Decision Tree (VFDT) oder Hoeffding Tree, wurde von Domingos und Hulten auf der KDD 2000 vorgestellt. Er wandte die Hoeffding-Ungleichung an, um den Fehler bei der Auswahl von Split-Attributen aus einem Datenstrom zu begrenzen, was eine asymptotisch korrekte Bauminduktion ohne Speicherung von Beispielen ermöglichte. Hulten, Spencer und Domingos erweiterten dies 2001 auf Streams mit Konzeptdrift. Der Ansatz wurde zum Eckpfeiler des MOA (Massive Online Analysis) Frameworks und beeinflusste eine Generation von Streaming-Ensemble-Methoden.
Wann wird sie eingesetzt?
Verwenden Sie einen Online Decision Tree, wenn Daten als kontinuierlicher Strom eintreffen, wenn die Speicherung des vollständigen Datensatzes aufgrund von Volumen- oder Datenschutzbeschränkungen nicht machbar ist oder wenn das Modell in Echtzeit mit jeder neuen Beobachtung aktualisiert werden muss. Er eignet sich gut für IoT-Sensorströme, Clickstream-Klassifizierung, Betrugserkennung mit sich entwickelnden Mustern und jede Umgebung, in der Konzeptdrift erwartet wird und sich das Modell ohne Neuschulung von Grund auf anpassen muss. Verwenden Sie ihn nicht, wenn der Datensatz klein und statisch ist – ein Standard-Entscheidungsbaum oder Random Forest ist schneller zu implementieren und genauer. Vermeiden Sie ihn auch, wenn die Interpretierbarkeit der exakten Split-Schwellenwerte entscheidend ist, ohne zu akzeptieren, dass sich Schwellenwerte im Laufe der Zeit verschieben können.
Grenzen und Hinweise
- Die Genauigkeit bei kleinen Datensätzen ist typischerweise geringer als bei einem Batch-Entscheidungsbaum, da die Hoeffding-Schranke viele Beispiele erfordert, bevor frühe Splits gemacht werden.
- Split-Entscheidungen sind im Basisalgorithmus unumkehrbar; ein schlechter früher Split kann bestehen bleiben, es sei denn, es wird ein expliziter Ersatz von Teilbäumen hinzugefügt.
- Das Einstellen des Konfidenzparameters delta und der Wartezeit zwischen Split-Evaluierungen erfordert Domänenwissen.
- Die Interpretierbarkeit des Baumes ändert sich im Laufe der Zeit, da neue Splits hinzugefügt werden, was eine statische Berichterstattung erschwert.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Verarbeitet Daten in einem einzigen Durchlauf mit konstantem Speicher pro Knoten und skaliert auf theoretisch unendliche Streams.
- Bietet theoretische Garantien über die Hoeffding-Schranke, dass die Splits bei genügend Daten asymptotisch identisch mit denen eines Batch-Baums sind.
- Kann Drift-Detektoren integrieren, um sich an nicht-stationäre Verteilungen anzupassen, ohne vollständiges Neuschulung.
- Liefert ab dem ersten Beispiel ein nutzbares Modell, im Gegensatz zu Batch-Methoden, die einen vollständigen Datensatz benötigen, bevor sie eine Vorhersage liefern.
- Handhabt naturgemäß Hochdurchsatz-Szenarien, in denen die Datenspeicherung unpraktisch oder gesetzlich eingeschränkt ist.
Anwendungen
- Echtzeit-Betrugserkennung bei Finanztransaktionsströmen.
- Netzwerk-Intrusion-Detection, bei der Verkehrsstatistiken kontinuierlich eintreffen.
- Klassifizierung von IoT- und Sensordaten mit speicherbeschränkten Edge-Geräten.
- Modellierung von Clickstreams oder Nutzerverhalten, bei denen das Datenvolumen eine vollständige Speicherung ausschließt.
- Adaptive Spam-Filterung, da sich linguistische Muster in E-Mails im Laufe der Zeit entwickeln.
- Baseline-Streaming-Klassifikator, gegen den komplexere Streaming-Ensembles verglichen werden.
So funktioniert es
So funktioniert es
Jedes gelabelte Beispiel trifft einzeln aus dem Datenstrom ein. Der Baum leitet es vom Wurzelknoten durch bestehende Teilungen zum entsprechenden Blatt und erstellt eine Vorhersage für die Instanz, bevor diese gelabelt wird.
Ausreichende Statistiken für alle Kandidaten-Split-Attribute – wie klassenbedingte Zählungen oder Gaußsche Mittelwerte und Varianzen – werden im Blatt aktualisiert, das die Instanz empfangen hat. Es werden keine Rohdaten gespeichert; nur diese kompakten Zusammenfassungen wachsen.
Die Hoeffding- (oder Chernoff-) Schranke epsilon = sqrt(R^2 * ln(1/delta) / (2n)) quantifiziert den maximalen Fehler zwischen dem beobachteten besten Split-Attribut und dem wahren besten Split mit einer Wahrscheinlichkeit von mindestens 1 - delta. Wenn n wächst, schrumpft epsilon gegen Null.
Formel
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}Wenn die Differenz der Informationsgewinne zwischen dem besten und dem zweitbesten Split-Kandidaten die aktuelle Hoeffding-Schranke überschreitet, wird das Blatt durch einen internen Split-Knoten auf dem gewinnenden Attribut ersetzt und zwei neue Blattzähler werden initialisiert. Andernfalls wartet der Knoten auf weitere Daten.
Jede ankommende Instanz erhält eine Klassen-Vorhersage vom aktuellen Baum, bevor ihr Label zur Aktualisierung verwendet wird. Optional überwachen Drift-Detektoren (z. B. ADWIN) die Fehlerraten der Blätter; wenn ein Konzeptdrift erkannt wird, können Teilbäume ersetzt werden, um das Modell aktuell zu halten.
Häufige Fallstricke
- Das Einstellen der Hoeffding-Konfidenz delta zu locker, was zu vorzeitigen Splits auf nicht repräsentativen frühen Daten führt.
- Ignorieren von Konzeptdrift – das Ausführen eines stationären Online-Baums auf Daten mit sich verschiebenden Verteilungen führt zu einer stillen Verschlechterung der Genauigkeit.
- Vergleich der Genauigkeit mit einem Batch-Modell, das auf den gesamten Daten desselben Streams trainiert wurde, was dem Batch-Modell einen unfairen Vorteil verschafft.
- Vergessen, dass Blätter vor ihrem ersten Split immer die bisher gesehene Mehrheitsklasse vorhersagen, was in frühen Phasen mit unausgeglichenen Streams irreführend sein kann.
Häufig gestellte Fragen
Wie unterscheidet sich der Hoeffding Tree von einem Standard-CART-Entscheidungsbaum?
Ein CART-Baum scannt den gesamten Datensatz an jedem Knoten, um die global beste Teilung zu finden. Der Hoeffding Tree beobachtet stattdessen, wie Beispiele einzeln eintreffen, und legt sich erst dann auf eine Teilung fest, wenn die statistische Theorie garantiert, dass der offensichtliche Gewinner auch mit mehr Daten gewinnen würde – ohne gespeicherte Rohdaten.
Verarbeitet der Online Decision Tree Konzeptdrift?
Der grundlegende Hoeffding Tree erkennt Drift nicht automatisch. Erweiterungen wie der Concept-adapting Very Fast Decision Tree (CVFDT) und Versionen, die mit ADWIN- oder Page-Hinkley-Drift-Detektoren kombiniert werden, können veraltete Teilbäume ersetzen, wenn Drift erkannt wird.
Was ist die Wartezeit (grace period) und wie sollte ich sie einstellen?
Die Wartezeit ist die Anzahl der Beispiele, die an einem Blatt zwischen aufeinanderfolgenden Split-Evaluierungen eintreffen. Ein größerer Wert reduziert die Rechenlast, verzögert aber Splits; ein kleinerer Wert evaluiert Splits häufiger bei höherer CPU-Last. Typische Standardwerte liegen zwischen 200 und 1000 Beispielen.
Ist der Online Decision Tree für kleine, statische Datensätze geeignet?
Nein. Für kleine, vollständig verfügbare Datensätze erzielt ein Standard-Batch-Entscheidungsbaum oder Random Forest fast immer eine bessere Genauigkeit bei weitaus geringerer Komplexität. Online-Bäume sind speziell für das Streaming-, Big-Data- oder ressourcenbeschränkte Regime konzipiert.
Wie verhält sich die Genauigkeit im Vergleich zu Batch-Methoden auf einem festen Datensatz?
Bei genügend Daten konvergiert der Hoeffding Tree zu demselben Baum, den ein Batch-Lerner produzieren würde, sodass die Genauigkeit schließlich übereinstimmt. Früher im Stream, bevor Blätter viele Beispiele gesehen haben, ist die Genauigkeit geringer als bei einem Batch-Baum, der auf den bisher gesehenen Daten trainiert wurde.
Verwandte Methoden
Quellen
Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.
Publikationsreferenz öffnenKopiert.Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.
DOI-Referenz öffnenKopiert.