Zum Inhalt springen
Zurück zu den Suchergebnissen

Online Random Forest

Eingeführt von
Saffari, A. et al.
Jahr
2009
Typ
Incremental ensemble (streaming decision trees)
Familie
Machine learning

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Online Random Forest (ORF) erweitert den klassischen Random Forest auf Streaming-Szenarien, indem jeder Baum inkrementell aktualisiert wird, sobald neue Beobachtungen eintreffen, ohne den vollständigen Trainingsdatensatz zu speichern oder erneut abzuspielen.

Algorithmen wie Adaptive Random Forests (ARF) fügen eine Drift-Erkennung hinzu, sodass sich das Ensemble anpasst, wenn sich die Datenverteilung im Laufe der Zeit ändert.

Die Intuition hinter der Methode

Der klassische Random Forest benötigt den gesamten Datensatz im Voraus, um seine Bäume zu wachsen. Online Random Forest ersetzt das Batch-Bootstrap-Sampling durch einen Poisson-gewichteten Online-Bagging-Trick: Jede eingehende Beobachtung wird an jeden Baum weitergeleitet, der – durch Ziehen einer Poisson-Zählung – entscheidet, wie oft dieses Beispiel als neuer Trainingspunkt behandelt wird. Die Bäume wachsen inkrementell unter Verwendung von Online-Split-Kriterien (z. B. Hoeffding-Grenzen), und ein Drift-Erkennungsmodul überwacht auf Konzeptdrift und ersetzt veraltete Bäume durch neue. Das Ergebnis ist ein Forest, der kontinuierlich aus einem Stream lernt und dennoch mehrere diverse Bäume zur Varianzreduktion kombiniert.

Geschichte

Online-Bagging wurde von Oza & Russell (2001) als Poisson-gewichtete Approximation der Bootstrap-Aggregation formalisiert. Saffari et al. (2009) führten On-line Random Forests ein, die Online-Bagging mit zufälliger Merkmalsauswahl und Hoeffding-basierten Split-Kriterien für Computer-Vision-Streams kombinierten. Gomes et al. (2017) führten Adaptive Random Forests (ARF) ein, die eine pro-Baum-Drift-Erkennung mittels ADWIN hinzufügten und auf Benchmark-Datenstrom-Klassifikationsaufgaben eine Spitzenleistung demonstrierten. ARF wurde zu einem Standard-Baseline im MOA (Massive Online Analysis)-Framework.

Wann wird sie eingesetzt?

Verwenden Sie Online Random Forest, wenn Daten kontinuierlich oder in großen Batches eintreffen, die nicht im Speicher gehalten werden können, wenn Konzeptdrift plausibel ist (z. B. Finanzströme, Sensornetzwerke, Benutzerverhaltensprotokolle) oder wenn Vorhersagen mit geringer Latenz erforderlich sind, bevor der vollständige Datensatz verfügbar ist. Es passt auch natürlich zu Anwendungen, bei denen gelabelte Daten im Laufe der Zeit eintrudeln. Vermeiden Sie es, wenn der vollständige Datensatz bequem in den Speicher passt und ein erneutes Training erschwinglich ist – in diesem Fall ist ein Standard Random Forest, der offline trainiert wurde, in der Regel genauer und einfacher zu validieren. Vermeiden Sie es auch, wenn Sie stabile, reproduzierbare Ranglisten der Merkmalswichtigkeit benötigen, da Online-Forests weniger stabile Wichtigkeitsschätzungen als ihre Batch-Gegenstücke liefern.

Grenzen und Hinweise

  • Frühe Split-Entscheidungen mit spärlichen Daten können suboptimal sein und sind schwer zu revidieren.
  • Schätzungen der Merkmalswichtigkeit sind weniger stabil als bei Batch Random Forest.
  • Hyperparameter-Tuning (Anzahl der Bäume, Drift-Erkennungs-Schwellenwerte) ist im Streaming-Kontext komplexer.
  • Die Evaluierung erfordert spezielle Stream-basierte Protokolle (Prequential/Test-then-Train), die sich von der Standard-Kreuzvalidierung unterscheiden.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Lernt aus Streaming-Daten mit konstantem Speicher pro Baum, unabhängig von der Stream-Länge.
  • Passt sich an Konzeptdrift an, wenn er mit Drift-Erkennungsmechanismen wie ADWIN kombiniert wird.
  • Erbt die Vorteile der Varianzreduktion durch Ensemble-Aggregation auch im Online-Setting.
  • Liefert nutzbare Vorhersagen ab den ersten wenigen Beobachtungen, die sich im Laufe der Zeit verbessern.
  • Keine Notwendigkeit, den gesamten historischen Datensatz zu speichern oder erneut abzuspielen.

Anwendungen

  • Echtzeit-Betrugs- und Intrusion-Erkennung auf Netzwerk- oder Transaktionsströmen.
  • Vorhersagende Wartung aus Sensorströmen, bei denen sich die Verteilungen mit der Alterung der Ausrüstung verschieben.
  • Klickraten-Vorhersage in der Werbung, bei der sich das Benutzerverhalten täglich weiterentwickelt.
  • Medizinische Überwachung, bei der sich der Patientenzustand kontinuierlich im Laufe der Zeit ändert.
  • Umwelt- und Klimasensorik mit nicht-stationären saisonalen Mustern.

So funktioniert es

So funktioniert es

1

Ein Satz von T Bäumen (oder Hoeffding-Bäumen) wird initialisiert. Jeder Baum speichert pro Blatt ausreichende Statistiken – Klassenzählungen oder Summen von Quadraten für Regression – anstatt rohe Beobachtungen zu speichern, wodurch das Modell pro Baum speicherkonstant bleibt.

2

Für jede ankommende Beobachtung zieht jeder Baum unabhängig k aus einer Poisson(1)-Verteilung und behandelt die Beobachtung als k virtuelle Replikationen von sich selbst. Wenn k = 0 überspringt der Baum den Punkt (agiert als sein Out-of-Bag-Sample). Dies approximiert das Bootstrap-Sampling, ohne den gesamten Datensatz zu benötigen.

Formel
k \sim \text{Poisson}(\lambda),\; \lambda=1
3

Jeder Baum aktualisiert die ausreichenden Statistiken in seinem aktiven Blatt. Ein Split wird ausgelöst, wenn ein statistisch fundiertes Kriterium (wie die Hoeffding-Grenze) anzeigt, dass sich der beste Split mit mehr Daten wahrscheinlich nicht mehr ändern wird, woraufhin das Blatt in einen internen Knoten erweitert und neue Blätter initialisiert werden.

4

Ein optionales Drift-Erkennungsmodul (z. B. ADWIN) überwacht den Vorhersagefehler jedes Baumes im Out-of-Bag-Stream. Wenn eine statistisch signifikante Verschlechterung erkannt wird, wird der betroffene Baum zurückgesetzt oder durch einen neu initialisierten Baum ersetzt, um das Ensemble mit sich entwickelnden Verteilungen aktuell zu halten.

5

Zu jedem Zeitpunkt stimmen alle aktiven Bäume ab: Mehrheitsentscheid für Klassifikation oder mittlere Vorhersage für Regression. Bäume, die nur sehr wenige Beispiele verarbeitet haben, können untergewichtet oder ausgeschlossen werden, bis sie genügend Daten gesammelt haben, um zuverlässige Stimmen abzugeben.

Formel
\hat{y} = \text{mode/mean of active trees}

Häufige Fallstricke

  • Evaluierung mit Standard-k-facher Kreuzvalidierung, die i.i.d.-Daten annimmt und die zeitliche Reihenfolge ignoriert.
  • Ignorieren von Konzeptdrift: Versäumnis, eine Drift-Erkennungskomponente einzubeziehen, wenn sich die Datenverteilung im Laufe der Zeit ändert.
  • Vergleich der Genauigkeit von Online-Forests direkt mit einem Batch-Random-Forest, der auf dem vollständigen historischen Datensatz trainiert wurde – letzterer hat einen inhärenten Informationsvorteil.
  • Verwendung von zu wenigen Bäumen früh im Stream, bevor jeder Baum genügend Daten gesehen hat, um zuverlässige Splits zu machen.
  • Vergessen, dass Poisson-gewichtetes Bagging Bootstrap approximiert – es reproduziert nicht exakt die statistischen Eigenschaften von Batch Bootstrap.

Häufig gestellte Fragen

Wie unterscheidet sich Online Random Forest von Standard Random Forest?

Standard Random Forest trainiert alle Bäume gleichzeitig auf dem vollständigen Datensatz mittels Bootstrap-Sampling. Online Random Forest ersetzt Batch-Bootstrap durch Poisson-gewichtetes Online-Bagging, aktualisiert Baum-Splits inkrementell, sobald jede Beobachtung eintrifft, und erkennt und passt sich optional an Konzeptdrift an – alles ohne Speicherung vergangener Daten.

Was ist der Poisson-Gewichtungs-Trick?

Jedes eingehende Beispiel wird jedem Baum k-mal gezeigt, wobei k aus Poisson(1) gezogen wird. Da der Erwartungswert von k 1 ist und k mit einer Wahrscheinlichkeit von ~37% gleich 0 ist, approximiert dies statistisch den Bootstrap-Prozess (Sampling mit Zurücklegen), ohne den gesamten Datensatz im Speicher zu benötigen.

Wie sollte ich einen Online Random Forest evaluieren?

Verwenden Sie das prequential (Test-then-Train)-Protokoll: Für jede eingehende Beobachtung wird zuerst mit dem aktuellen Modell vorhergesagt, der Fehler aufgezeichnet und dann das Modell aktualisiert. Dies liefert eine unverzerrte, zeitlich geordnete Schätzung der Vorhersageleistung ohne Datenlecks.

Wann sollte ich Drift-Erkennung hinzufügen?

Immer dann, wenn sich der datengenerierende Prozess wahrscheinlich im Laufe der Zeit ändert – zum Beispiel Benutzerpräferenzen, Finanzmärkte oder mechanische Systeme, die verschleißen. Ohne Drift-Erkennung sammeln sich veraltete Bäume an und ziehen die Ensemble-Genauigkeit nach unten. ADWIN ist eine gängige, gut getestete Wahl.

Ist Adaptive Random Forest dasselbe?

ARF ist die am weitesten verbreitete Variante von Online Random Forest. Es kombiniert Online-Bagging, zufällige Merkmalsauswahl und pro-Baum-ADWIN-Drift-Erkennung und ist in den Bibliotheken MOA und scikit-multiflow/River verfügbar. Der Begriff 'Online Random Forest' bezieht sich oft allgemein auf die Familie; ARF ist eine spezifische, sehr empfehlenswerte Implementierung.

Verwandte Methoden

Quellen

  1. Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.

    Publikationsreferenz öffnen
    Kopiert.
  2. Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.

    DOI-Referenz öffnen
    Kopiert.