Skip to content
Torna ai risultati

Online Random Forest

Introdotto da
Saffari, A. et al.
Anno
2009
Tipo
Incremental ensemble (streaming decision trees)
Famiglia
Machine learning

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

Online Random Forest (ORF) estende il classico Random Forest (Foresta Casuale) a contesti di streaming, aggiornando ogni albero incrementalmente man mano che arrivano nuove osservazioni, senza memorizzare o riprodurre l'intero set di addestramento.

Algoritmi come Adaptive Random Forests (ARF) aggiungono il rilevamento del drift (cambiamento concettuale) in modo che l'ensemble si adatti quando la distribuzione dei dati cambia nel tempo.

L’intuizione alla base del metodo

Il classico Random Forest richiede l'intero dataset in anticipo per far crescere i suoi alberi. Online Random Forest sostituisce il campionamento bootstrap batch con un trucco di 'online bagging' pesato con Poisson: ogni osservazione in arrivo viene passata a ogni albero, che decide – estraendo un conteggio di Poisson – quante volte trattare quell'esempio come un nuovo punto di addestramento. Gli alberi crescono incrementalmente usando criteri di ricerca dello split online (ad es., limiti di Hoeffding), e un modulo di rilevamento del drift monitora il concept drift, sostituendo gli alberi obsoleti con nuovi. Il risultato è una foresta che apprende continuamente da uno stream, pur combinando alberi multipli e diversi per la riduzione della varianza.

Storia

Il Poisson-weighted bagging è stato formalizzato da Oza & Russell (2001) come un'approssimazione pesata con Poisson all'aggregazione bootstrap. Saffari et al. (2009) hanno introdotto gli On-line Random Forests combinando online bagging con selezione casuale delle feature e criteri di split basati su Hoeffding per stream di computer vision. Gomes et al. (2017) hanno introdotto gli Adaptive Random Forests (ARF), aggiungendo il rilevamento del drift per albero tramite ADWIN, e hanno dimostrato accuratezza allo stato dell'arte su task di classificazione di data stream benchmark. ARF è diventato un baseline standard nel framework MOA (Massive Online Analysis).

Quando usarlo

Utilizzare Online Random Forest quando i dati arrivano continuamente o in grandi batch che non possono essere memorizzati nella memoria principale, quando il concept drift è plausibile (ad es., flussi finanziari, reti di sensori, log di comportamento utente), o quando sono richieste predizioni a bassa latenza prima che l'intero dataset sia disponibile. È anche una scelta naturale per applicazioni in cui i dati etichettati arrivano gradualmente nel tempo. Evitarlo quando l'intero dataset entra comodamente nella memoria e il riaddestramento è conveniente – in tal caso un Random Forest standard addestrato offline sarà tipicamente più accurato e più semplice da validare. Evitarlo anche quando sono necessarie classificazioni di importanza delle feature stabili e riproducibili, poiché le foreste online producono stime di importanza meno stabili rispetto alle loro controparti batch.

Limiti e considerazioni

  • Le decisioni di split prese precocemente con dati sparsi possono essere sub-ottimali e difficili da rivedere.
  • Le stime di importanza delle feature sono meno stabili rispetto al Random Forest batch.
  • La sintonizzazione degli iperparametri (numero di alberi, soglie di rilevamento del drift) è più complessa in un contesto di streaming.
  • La valutazione richiede protocolli dedicati basati su stream (prequenziale/test-then-train) che differiscono dalla cross-validation standard.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Apprende dai dati in streaming con memoria costante per albero, indipendente dalla lunghezza dello stream.
  • Si adatta al concept drift quando accoppiato con meccanismi di rilevamento del drift come ADWIN.
  • Eredita i benefici di riduzione della varianza dell'aggregazione dell'ensemble anche in un contesto online.
  • Fornisce predizioni utilizzabili dalle prime osservazioni, migliorando nel tempo.
  • Nessuna necessità di memorizzare o riprodurre l'intero dataset storico.

Applicazioni

  • Rilevamento di frodi e intrusioni in tempo reale su stream di rete o transazioni.
  • Manutenzione predittiva da stream di sensori dove le distribuzioni cambiano con l'invecchiamento delle apparecchiature.
  • Predizione del click-through rate nella pubblicità dove il comportamento degli utenti si evolve quotidianamente.
  • Monitoraggio medico dove lo stato del paziente cambia continuamente nel tempo.
  • Rilevamento ambientale e climatico con pattern stagionali non stazionari.

Come funziona

Come funziona

1

Viene inizializzato un insieme di T alberi (o alberi di Hoeffding). Ogni albero mantiene statistiche sufficienti per foglia – conteggi di classe o somma dei quadrati per la regressione – invece di memorizzare osservazioni grezze, rendendo il modello a memoria costante per albero.

2

Per ogni osservazione in arrivo, ogni albero estrae indipendentemente k da una distribuzione di Poisson(1) e tratta l'osservazione come k repliche virtuali di sé stessa. Quando k = 0 l'albero salta il punto (agendo come suo campione out-of-bag). Questo approssima il campionamento bootstrap senza richiedere l'intero dataset.

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

Ogni albero aggiorna le statistiche sufficienti nella sua foglia attiva. Uno split viene attivato quando un criterio statisticamente valido (come il limite di Hoeffding) indica che lo split migliore è improbabile che cambi con più dati, dopodiché la foglia viene espansa in un nodo interno e nuove foglie vengono inizializzate.

4

Un modulo opzionale di rilevamento del drift (ad es., ADWIN) monitora l'errore di predizione di ogni albero sullo stream out-of-bag. Quando viene rilevato un degrado statisticamente significativo, l'albero interessato viene resettato o sostituito con un albero appena inizializzato, mantenendo l'ensemble aggiornato con le distribuzioni in evoluzione.

5

In qualsiasi momento, tutti gli alberi attivi votano: voto di maggioranza per la classificazione o media delle predizioni per la regressione. Gli alberi che hanno elaborato pochissimi esempi possono essere sottopesati o esclusi finché non accumulano dati sufficienti per fornire voti affidabili.

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

Errori comuni

  • Valutare con la cross-validation k-fold standard, che assume dati i.i.d. (indipendenti e identicamente distribuiti) e ignora l'ordine temporale.
  • Ignorare il concept drift: non includere un componente di rilevamento del drift quando la distribuzione dei dati cambia nel tempo.
  • Confrontare l'accuratezza di una foresta online direttamente con un Random Forest batch addestrato sull'intero dataset storico – quest'ultimo ha un vantaggio informativo intrinseco.
  • Usare troppo pochi alberi all'inizio dello stream prima che ogni albero abbia visto abbastanza dati per fare split affidabili.
  • Dimenticare che il Poisson-weighted bagging approssima il bootstrap – non riproduce esattamente le proprietà statistiche del bootstrap batch.

Domande frequenti

In che modo Online Random Forest differisce da Random Forest standard?

Standard Random Forest addestra tutti gli alberi contemporaneamente sull'intero dataset usando il campionamento bootstrap. Online Random Forest sostituisce il bootstrap batch con Poisson-weighted online bagging, aggiorna gli split degli alberi incrementalmente man mano che ogni osservazione arriva, e opzionalmente rileva e si adatta al concept drift – tutto senza memorizzare dati passati.

Cos'è il trucco del Poisson weighting?

Ogni esempio in arrivo viene mostrato a ogni albero k volte, dove k è estratto da Poisson(1). Poiché il valore atteso di k è 1, e k = 0 con probabilità ~37%, questo approssima statisticamente il processo bootstrap (campionamento con rimpiazzo) senza necessitare dell'intero dataset in memoria.

Come dovrei valutare un online random forest?

Utilizzare il protocollo prequenziale (test-then-train): per ogni osservazione in arrivo, prima predire con il modello corrente, registrare l'errore, poi aggiornare il modello. Questo fornisce una stima imparziale e temporalmente ordinata delle prestazioni predittive senza data leakage.

Quando dovrei aggiungere il rilevamento del drift?

Ogni volta che è probabile che il processo generatore di dati cambi nel tempo – ad esempio, preferenze degli utenti, mercati finanziari, o sistemi meccanici che si usurano. Senza il rilevamento del drift, alberi obsoleti si accumulano e peggiorano l'accuratezza dell'ensemble. ADWIN è una scelta comune e ben testata.

Adaptive Random Forest è la stessa cosa?

ARF è la variante più ampiamente adottata di Online Random Forest. Combina online bagging, selezione casuale delle feature e rilevamento del drift ADWIN per albero, ed è disponibile nelle librerie MOA e scikit-multiflow/River. Il termine 'Online Random Forest' si riferisce spesso genericamente alla famiglia; ARF è un'implementazione specifica e altamente raccomandata.

Metodi correlati

Fonti

  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.

    Apri il riferimento della pubblicazione
    Copiato.
  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.

    Apri il riferimento DOI
    Copiato.