Albero Decisionale Online
- Introdotto da
- Domingos, P. & Hulten, G.
- Anno
- 2000
- Tipo
- Incremental supervised classifier
- Famiglia
- Machine learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Un Albero Decisionale Online è un albero decisionale che cresce incrementalmente da un flusso continuo di dati senza rivisitare esempi passati.
L'algoritmo dominante, l'Albero di Hoeffding (VFDT), utilizza il limite di Hoeffding per decidere quando sono stati visti abbastanza esempi in un nodo per dividerlo con sicurezza, consentendo la classificazione scalabile in tempo reale su flussi di dati potenzialmente infiniti.
L’intuizione alla base del metodo
Un albero decisionale standard viene costruito scansionando ripetutamente l'intero dataset per trovare le migliori divisioni. Nelle impostazioni di streaming questo è impossibile perché i dati arrivano uno alla volta e non possono essere memorizzati. L'approccio online mantiene solo statistiche correnti in ogni foglia. Quando si accumulano abbastanza esempi, il limite di Hoeffding — una garanzia statistica — conferma che la migliore divisione apparente rimarrebbe la migliore divisione anche se avessimo visto ogni possibile esempio. Solo allora l'albero si divide effettivamente, crescendo da una singola foglia in una struttura sempre più profonda senza mai guardare indietro ai dati passati.
Storia
L'algoritmo fondamentale, il Very Fast Decision Tree (VFDT) o Albero di Hoeffding, è stato introdotto da Domingos e Hulten a KDD 2000. Ha applicato la disuguaglianza di Hoeffding per limitare l'errore nella selezione degli attributi di divisione da un flusso di dati, consentendo un'induzione dell'albero asintoticamente corretta senza memorizzare esempi. Hulten, Spencer e Domingos hanno esteso questo ai flussi con concept drift nel 2001. L'approccio è diventato la pietra angolare del framework MOA (Massive Online Analysis) e ha influenzato una generazione di metodi ensemble di streaming.
Quando usarlo
Utilizzare un albero decisionale online quando i dati arrivano come flusso continuo, quando l'archiviazione dell'intero dataset è infattibile a causa di vincoli di volume o privacy, o quando il modello deve essere aggiornato in tempo reale con ogni nuova osservazione. È ben adatto per flussi di sensori IoT, classificazione di clickstream, rilevamento di frodi con pattern in evoluzione e qualsiasi scenario in cui ci si aspetta concept drift e il modello deve adattarsi senza riaddestramento da zero. Non utilizzarlo quando il dataset è piccolo e statico — un albero decisionale standard o una foresta casuale saranno più veloci da implementare e più accurati. Evitarlo anche se l'interpretabilità delle soglie di divisione esatte è critica senza accettare che le soglie possano cambiare nel tempo.
Limiti e considerazioni
- L'accuratezza su dataset piccoli è tipicamente inferiore a quella di un albero decisionale batch perché il limite di Hoeffding richiede molti esempi prima che vengano effettuate le prime divisioni.
- Le decisioni di divisione sono irreversibili nell'algoritmo di base; una divisione precoce e errata può persistere a meno che non venga aggiunta una sostituzione esplicita del sottoalbero.
- La messa a punto del parametro di confidenza delta e del periodo di grazia tra le valutazioni delle divisioni richiede conoscenza del dominio.
- L'interpretabilità dell'albero cambia nel tempo man mano che vengono aggiunte nuove divisioni, rendendo difficile la reportistica statica.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Elabora i dati in un singolo passaggio con memoria costante per nodo, scalando a flussi teoricamente infiniti.
- Fornisce garanzie teoriche tramite il limite di Hoeffding che le divisioni sono asintoticamente identiche a quelle di un albero batch dati abbastanza dati.
- Può incorporare rilevatori di drift per adattarsi a distribuzioni non stazionarie senza riaddestramento completo.
- Consegna un modello utilizzabile fin dal primo esempio, a differenza dei metodi batch che richiedono un dataset completo prima di produrre qualsiasi previsione.
- Gestisce naturalmente scenari ad alto throughput in cui l'archiviazione dei dati è impraticabile o legalmente limitata.
Applicazioni
- Rilevamento frodi in tempo reale su flussi di transazioni finanziarie.
- Rilevamento intrusioni di rete dove le statistiche del traffico arrivano continuamente.
- Classificazione di dati IoT e sensori con dispositivi edge con memoria limitata.
- Modellazione di clickstream o comportamento utente dove il volume dei dati preclude l'archiviazione completa.
- Filtro antispam adattivo poiché i pattern linguistici nelle email evolvono nel tempo.
- Classificatore di streaming di base rispetto al quale vengono confrontati ensemble di streaming più complessi.
Come funziona
Come funziona
Ogni esempio etichettato arriva uno alla volta dal flusso di dati. L'albero lo instrada dalla radice verso il basso attraverso le divisioni esistenti fino alla foglia appropriata, effettuando una previsione per l'istanza prima che venga etichettata.
Le statistiche sufficienti per tutti gli attributi candidati alla divisione — come i conteggi condizionati per classe o la media e la varianza Gaussiane — vengono aggiornate nella foglia che ha ricevuto l'istanza. Nessun dato grezzo viene conservato; solo questi riassunti compatti crescono.
Il limite di Hoeffding (o Chernoff) epsilon = sqrt(R^2 * ln(1/delta) / (2n)) quantifica l'errore massimo tra l'attributo di divisione migliore osservato e la migliore divisione vera con probabilità almeno 1 - delta. Man mano che n cresce, epsilon si riduce a zero.
Formula
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}Se la differenza di guadagno informativo tra i candidati alla divisione migliore e seconda migliore supera il limite di Hoeffding corrente, la foglia viene sostituita da un nodo di divisione interno sull'attributo vincente, e vengono inizializzati due nuovi contatori di foglie. Altrimenti, il nodo attende più dati.
Ogni istanza in arrivo riceve una previsione di classe dall'albero corrente prima che la sua etichetta venga utilizzata per l'aggiornamento. Opzionalmente, i rilevatori di drift (ad es. ADWIN) monitorano i tassi di errore delle foglie; quando viene rilevato un concept drift, i sottoalberi possono essere sostituiti per mantenere aggiornato il modello.
Errori comuni
- Impostare il delta di confidenza di Hoeffding troppo lasco, causando divisioni premature su dati precoci non rappresentativi.
- Ignorare il concept drift — eseguire un albero online stazionario su dati con distribuzioni mutevoli porta a un degrado silenzioso dell'accuratezza.
- Confrontare l'accuratezza con un modello batch addestrato sull'intero dataset dello stesso flusso, il che conferisce al modello batch un vantaggio sleale.
- Dimenticare che le foglie prima della loro prima divisione predicono sempre la classe maggioritaria vista finora, il che può essere fuorviante nelle prime fasi con flussi sbilanciati.
Domande frequenti
In che modo l'Albero di Hoeffding differisce da un albero decisionale CART standard?
Un albero CART scansiona l'intero dataset in ogni nodo per trovare la divisione globalmente migliore. L'Albero di Hoeffding invece osserva gli esempi arrivare uno alla volta, e si impegna in una divisione solo quando la teoria statistica garantisce che il vincitore apparente vincerebbe ancora con più dati — senza utilizzare esempi grezzi memorizzati.
L'albero decisionale online gestisce il concept drift?
L'Albero di Hoeffding di base non rileva il drift automaticamente. Estensioni come il Concept-adapting Very Fast Decision Tree (CVFDT) e versioni combinate con rilevatori di drift ADWIN o Page-Hinkley possono sostituire sottoalberi obsoleti quando viene rilevato il drift.
Cos'è il periodo di grazia e come dovrei impostarlo?
Il periodo di grazia è il numero di esempi che arrivano a una foglia tra valutazioni consecutive delle divisioni. Un valore maggiore riduce il calcolo ma ritarda le divisioni; un valore minore valuta le divisioni più spesso a un costo CPU più elevato. I valori predefiniti tipici vanno da 200 a 1000 esempi.
L'albero decisionale online è appropriato per dataset piccoli e statici?
No. Per dataset piccoli e completamente disponibili, un albero decisionale batch standard o una foresta casuale otterranno quasi sempre una migliore accuratezza con molta meno complessità. Gli alberi online sono progettati specificamente per il regime di streaming, su larga scala o con risorse limitate.
Come si confronta l'accuratezza con i metodi batch su un dataset fisso?
Con abbastanza dati, l'Albero di Hoeffding converge allo stesso albero che produrrebbe un learner batch, quindi l'accuratezza alla fine corrisponde. All'inizio del flusso, prima che le foglie abbiano visto molti esempi, l'accuratezza è inferiore a quella di un albero batch addestrato sugli stessi dati visti finora.
Metodi correlati
Fonti
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.
Apri il riferimento della pubblicazioneCopiato.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.
Apri il riferimento DOICopiato.