Random Forest Online
- Proposto por
- Saffari, A. et al.
- Ano
- 2009
- Tipo
- Incremental ensemble (streaming decision trees)
- Família
- Machine learning
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Random Forest Online (ORF) estende o Random Forest clássico para ambientes de streaming, atualizando cada árvore incrementalmente à medida que novas observações chegam, sem armazenar ou reexecutar o conjunto de treinamento completo.
Algoritmos como Adaptive Random Forests (ARF) adicionam detecção de drift para que o ensemble se adapte quando a distribuição dos dados muda ao longo do tempo.
A intuição por trás do método
O Random Forest clássico requer todo o conjunto de dados antecipadamente para construir suas árvores. O Random Forest Online substitui o bootstrap em batch por um truque de bagging online com ponderação de Poisson: cada observação recebida é passada para cada árvore, que decide — sorteando uma contagem de Poisson — quantas vezes tratar aquele exemplo como um novo ponto de treinamento. As árvores crescem incrementalmente usando critérios de busca de divisão online (por exemplo, limites de Hoeffding), e um módulo de detecção de drift monitora o concept drift, substituindo árvores desatualizadas por novas. O resultado é uma floresta que aprende continuamente a partir de um fluxo, ao mesmo tempo que combina múltiplas árvores diversas para redução de variância.
História
O bagging online foi formalizado por Oza & Russell (2001) como uma aproximação ponderada por Poisson à agregação bootstrap. Saffari et al. (2009) introduziram On-line Random Forests combinando bagging online com seleção de características aleatória e critérios de divisão baseados em Hoeffding para fluxos de visão computacional. Gomes et al. (2017) introduziram Adaptive Random Forests (ARF), adicionando detecção de drift por árvore via ADWIN, e demonstraram precisão de ponta em tarefas de classificação de data-stream em benchmarks. ARF tornou-se uma linha de base padrão no framework MOA (Massive Online Analysis).
Quando usar
Use Random Forest Online quando os dados chegam continuamente ou em grandes lotes que não podem ser mantidos na memória, quando o concept drift é plausível (por exemplo, fluxos financeiros, redes de sensores, logs de comportamento do usuário), ou quando predições de baixa latência são necessárias antes que o conjunto de dados completo esteja disponível. É também uma adaptação natural para aplicações onde dados rotulados chegam ao longo do tempo. Evite-o quando o conjunto de dados completo cabe confortavelmente na memória e o retreinamento é viável — nesse caso, um Random Forest padrão treinado offline geralmente será mais preciso e mais simples de validar. Evite-o também quando você precisa de rankings de importância de características estáveis e reprodutíveis, pois florestas online produzem estimativas de importância menos estáveis do que suas contrapartes em batch.
Limitações e considerações
- Decisões de divisão feitas cedo com dados esparsos podem ser sub-ótimas e difíceis de revisar.
- Estimativas de importância de características são menos estáveis do que no Random Forest em batch.
- Ajuste de hiperparâmetros (número de árvores, limiares de detecção de drift) é mais complexo em um contexto de streaming.
- A avaliação requer protocolos dedicados baseados em fluxo (prequencial/test-then-train) que diferem da validação cruzada padrão.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Aprende a partir de dados de streaming com memória constante por árvore, independente do comprimento do fluxo.
- Adapta-se ao concept drift quando pareado com mecanismos de detecção de drift como ADWIN.
- Herda os benefícios de redução de variância da agregação de ensemble mesmo em um ambiente online.
- Fornece predições utilizáveis a partir das primeiras observações, melhorando ao longo do tempo.
- Não há necessidade de armazenar ou reexecutar todo o conjunto de dados histórico.
Aplicações
- Detecção de fraude e intrusão em tempo real em fluxos de rede ou transações.
- Manutenção preditiva a partir de fluxos de sensores onde as distribuições mudam com o envelhecimento do equipamento.
- Previsão de taxa de cliques em publicidade onde o comportamento do usuário evolui diariamente.
- Monitoramento médico onde o estado do paciente muda continuamente ao longo do tempo.
- Sensoriamento ambiental e climático com padrões sazonais não estacionários.
Como funciona
Como funciona
Um conjunto de T árvores (ou árvores de Hoeffding) é inicializado. Cada árvore mantém estatísticas suficientes por folha — contagens de classes ou soma de quadrados para regressão — em vez de armazenar observações brutas, tornando o modelo de memória constante por árvore.
Para cada observação que chega, cada árvore sorteia independentemente k de uma distribuição de Poisson(1) e trata a observação como k réplicas virtuais de si mesma. Quando k = 0, a árvore ignora o ponto (agindo como sua amostra out-of-bag). Isso aproxima o bootstrap sem exigir o conjunto de dados completo.
Fórmula
k \sim \text{Poisson}(\lambda),\; \lambda=1Cada árvore atualiza as estatísticas suficientes em sua folha ativa. Uma divisão é acionada quando um critério estatisticamente sólido (como o limite de Hoeffding) indica que a melhor divisão provavelmente não mudará com mais dados, após o que a folha é expandida em um nó interno e novas folhas são inicializadas.
Um módulo opcional de detecção de drift (por exemplo, ADWIN) monitora o erro de predição de cada árvore no fluxo out-of-bag. Quando uma degradação estatisticamente significativa é detectada, a árvore afetada é reiniciada ou substituída por uma árvore recém-semeada, mantendo o ensemble atualizado com as distribuições em evolução.
A qualquer momento, todas as árvores ativas votam: voto majoritário para classificação ou predição média para regressão. Árvores que processaram muito poucos exemplos podem ser sub-ponderadas ou excluídas até que acumulem dados suficientes para dar votos confiáveis.
Fórmula
\hat{y} = \text{mode/mean of active trees}Erros comuns
- Avaliação com validação cruzada k-fold padrão, que assume dados i.i.d. e ignora a ordem temporal.
- Ignorar concept drift: falha em incluir um componente de detecção de drift quando a distribuição dos dados muda ao longo do tempo.
- Comparar a precisão da floresta online diretamente a um Random Forest em batch treinado no conjunto de dados histórico completo — este último tem uma vantagem de informação inerente.
- Usar poucas árvores no início do fluxo antes que cada árvore tenha visto dados suficientes para fazer divisões confiáveis.
- Esquecer que o bagging ponderado por Poisson aproxima o bootstrap — ele não reproduz exatamente as propriedades estatísticas do bootstrap em batch.
Perguntas frequentes
Como o Random Forest Online difere do Random Forest padrão?
O Random Forest padrão treina todas as árvores de uma vez no conjunto de dados completo usando bootstrap. O Random Forest Online substitui o bootstrap em batch por bagging online ponderado por Poisson, atualiza as divisões das árvores incrementalmente à medida que cada observação chega, e opcionalmente detecta e se adapta ao concept drift — tudo sem armazenar dados passados.
O que é o truque de ponderação de Poisson?
Cada exemplo recebido é mostrado a cada árvore k vezes, onde k é sorteado de Poisson(1). Como o valor esperado de k é 1, e k = 0 com probabilidade ~37%, isso aproxima estatisticamente o processo bootstrap (amostragem com reposição) sem precisar do conjunto de dados completo na memória.
Como devo avaliar um random forest online?
Use o protocolo prequencial (test-then-train): para cada observação recebida, primeiro preveja com o modelo atual, registre o erro, então atualize o modelo. Isso fornece uma estimativa imparcial e temporalmente ordenada do desempenho preditivo sem vazamento de dados.
Quando devo adicionar detecção de drift?
Sempre que o processo gerador de dados provavelmente mudará ao longo do tempo — por exemplo, preferências do usuário, mercados financeiros ou sistemas mecânicos que se desgastam. Sem detecção de drift, árvores desatualizadas se acumulam e prejudicam a precisão do ensemble. ADWIN é uma escolha comum e bem testada.
O Adaptive Random Forest é a mesma coisa?
ARF é a variante mais amplamente adotada do Random Forest Online. Ele combina bagging online, seleção aleatória de características e detecção de drift ADWIN por árvore, e está disponível nas bibliotecas MOA e scikit-multiflow/River. O termo 'Random Forest Online' geralmente se refere genericamente à família; ARF é uma implementação específica e altamente recomendada.
Métodos relacionados
Fontes
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.
Abrir referência da publicaçãoCopiado.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.
Abrir referência DOICopiado.