Árvore de Decisão Online
- Proposto por
- Domingos, P. & Hulten, G.
- Ano
- 2000
- Tipo
- Incremental supervised classifier
- 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?
Uma Árvore de Decisão Online é uma árvore de decisão que cresce incrementalmente a partir de um fluxo contínuo de dados, sem revisitar exemplos passados.
O algoritmo dominante, a Árvore de Hoeffding (VFDT), utiliza o limite de Hoeffding para decidir quando exemplos suficientes foram vistos em um nó para dividi-lo com confiança, permitindo classificação escalável em tempo real em fluxos de dados potencialmente infinitos.
A intuição por trás do método
Uma árvore de decisão padrão é construída escaneando o conjunto de dados completo repetidamente para encontrar as melhores divisões. Em cenários de fluxo, isso é impossível porque os dados chegam um de cada vez e não podem ser armazenados. A abordagem online mantém apenas estatísticas correntes em cada folha. Quando exemplos suficientes se acumulam, o limite de Hoeffding — uma garantia estatística — confirma que a melhor divisão aparente permaneceria a melhor divisão mesmo se tivéssemos visto todos os exemplos possíveis. Somente então a árvore realmente se divide, crescendo de uma única folha para uma estrutura cada vez mais profunda, sem nunca olhar para trás nos dados passados.
História
O algoritmo fundamental, a Very Fast Decision Tree (VFDT) ou Árvore de Hoeffding, foi introduzido por Domingos e Hulten na KDD 2000. Ele aplicou a desigualdade de Hoeffding para limitar o erro na seleção de atributos de divisão de um fluxo de dados, permitindo a indução de árvores assintoticamente corretas sem armazenar exemplos. Hulten, Spencer e Domingos estenderam isso para fluxos com desvio de conceito em 2001. A abordagem tornou-se a pedra angular do framework MOA (Massive Online Analysis) e influenciou uma geração de métodos de ensemble de streaming.
Quando usar
Use uma árvore de decisão online quando os dados chegam como um fluxo contínuo, quando o armazenamento do conjunto de dados completo é inviável devido a restrições de volume ou privacidade, ou quando o modelo deve ser atualizado em tempo real com cada nova observação. É bem adequado para fluxos de sensores IoT, classificação de clickstream, detecção de fraudes com padrões em evolução e qualquer cenário onde o desvio de conceito é esperado e o modelo deve se adaptar sem retreinamento do zero. Não o use quando o conjunto de dados for pequeno e estático — uma árvore de decisão padrão ou floresta aleatória será mais rápida de implementar e mais precisa. Evite-o também se a interpretabilidade dos limiares exatos de divisão for crítica, sem aceitar que os limiares podem mudar ao longo do tempo.
Limitações e considerações
- A precisão em conjuntos de dados pequenos é tipicamente menor do que uma árvore de decisão em lote porque o limite de Hoeffding requer muitos exemplos antes que as primeiras divisões sejam feitas.
- As decisões de divisão são irreversíveis no algoritmo básico; uma divisão precoce ruim pode persistir a menos que substituição explícita de subárvore seja adicionada.
- Ajustar o parâmetro de confiança delta e o período de carência (grace period) entre as avaliações de divisão requer conhecimento do domínio.
- A interpretabilidade da árvore muda ao longo do tempo à medida que novas divisões são adicionadas, tornando relatórios estáticos difíceis.
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
- Processa dados em uma única passagem com memória constante por nó, escalando para fluxos teoricamente infinitos.
- Fornece garantias teóricas via limite de Hoeffding de que as divisões são assintoticamente idênticas às de uma árvore em lote (batch tree) com dados suficientes.
- Pode incorporar detectores de desvio para se adaptar a distribuições não estacionárias sem retreinamento completo.
- Entrega um modelo utilizável desde o primeiro exemplo, ao contrário de métodos em lote que exigem um conjunto de dados completo antes de produzir qualquer previsão.
- Lida naturalmente com cenários de alta vazão onde o armazenamento de dados é impraticável ou legalmente restrito.
Aplicações
- Detecção de fraudes em tempo real em fluxos de transações financeiras.
- Detecção de intrusão em rede onde estatísticas de tráfego chegam continuamente.
- Classificação de dados de IoT e sensores com dispositivos de borda com restrição de memória.
- Modelagem de clickstream ou comportamento do usuário onde o volume de dados impede o armazenamento completo.
- Filtragem adaptativa de spam à medida que os padrões linguísticos em e-mails evoluem ao longo do tempo.
- Classificador de streaming de linha de base contra o qual ensembles de streaming mais complexos são comparados.
Como funciona
Como funciona
Cada exemplo rotulado chega um de cada vez do fluxo de dados. A árvore o roteia da raiz para baixo através das divisões existentes até a folha apropriada, fazendo uma previsão para a instância antes que ela seja rotulada.
Estatísticas suficientes para todos os atributos de divisão candidatos — como contagens condicionais de classe ou média e variância Gaussianas — são atualizadas na folha que recebeu a instância. Nenhum dado bruto é retido; apenas esses resumos compactos crescem.
O limite de Hoeffding (ou Chernoff) epsilon = sqrt(R^2 * ln(1/delta) / (2n)) quantifica o erro máximo entre o atributo de divisão aparente e o verdadeiro melhor atributo de divisão com probabilidade de pelo menos 1 - delta. À medida que n cresce, epsilon encolhe para zero.
Fórmula
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}Se a diferença de ganho de informação entre os melhores e os segundos melhores candidatos à divisão exceder o limite de Hoeffding atual, a folha é substituída por um nó de divisão interno no atributo vencedor, e dois novos contadores de folha são inicializados. Caso contrário, o nó espera por mais dados.
Cada instância que chega recebe uma previsão de classe da árvore atual antes que seu rótulo seja usado para atualização. Opcionalmente, detectores de desvio (drift detectors) (por exemplo, ADWIN) monitoram as taxas de erro das folhas; quando o desvio de conceito (concept drift) é detectado, subárvores podem ser substituídas para manter o modelo atualizado.
Erros comuns
- Definir o delta de confiança de Hoeffding muito frouxamente, causando divisões prematuras em dados iniciais não representativos.
- Ignorar o desvio de conceito — executar uma árvore online estacionária em dados com distribuições em mudança leva à degradação silenciosa da precisão.
- Comparar a precisão contra um modelo em lote treinado com todos os dados do mesmo fluxo, o que dá ao modelo em lote uma vantagem injusta.
- Esquecer que as folhas antes de sua primeira divisão sempre preveem a classe majoritária vista até agora, o que pode ser enganoso nas fases iniciais com fluxos desbalanceados.
Perguntas frequentes
Como a Árvore de Hoeffding difere de uma árvore de decisão CART padrão?
Uma árvore CART escaneia o conjunto de dados completo em cada nó para encontrar a melhor divisão global. A Árvore de Hoeffding, em vez disso, observa os exemplos chegarem um de cada vez, e só se compromete com uma divisão quando a teoria estatística garante que o vencedor aparente ainda venceria mesmo com mais dados — usando nenhum exemplo bruto armazenado.
A árvore de decisão online lida com desvio de conceito?
A Árvore de Hoeffding básica não detecta desvio automaticamente. Extensões como a Concept-adapting Very Fast Decision Tree (CVFDT) e versões combinadas com detectores de desvio ADWIN ou Page-Hinkley podem substituir subárvores desatualizadas quando o desvio é detectado.
Qual é o período de carência e como devo configurá-lo?
O período de carência é o número de exemplos que chegam a uma folha entre avaliações consecutivas de divisão. Um valor maior reduz a computação, mas atrasa as divisões; um valor menor avalia as divisões com mais frequência a um custo de CPU mais alto. Padrões típicos variam de 200 a 1000 exemplos.
A árvore de decisão online é apropriada para conjuntos de dados pequenos e estáticos?
Não. Para conjuntos de dados pequenos e totalmente disponíveis, uma árvore de decisão em lote padrão ou floresta aleatória quase sempre alcançará melhor precisão com muito menos complexidade. Árvores online são projetadas especificamente para o regime de streaming, larga escala ou com recursos restritos.
Como a precisão se compara a métodos em lote em um conjunto de dados fixo?
Com dados suficientes, a Árvore de Hoeffding converge para a mesma árvore que um aprendiz em lote produziria, então a precisão eventualmente se iguala. No início do fluxo, antes que as folhas tenham visto muitos exemplos, a precisão é menor do que a de uma árvore em lote treinada com todos os dados vistos até agora.
Métodos relacionados
Fontes
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.
Abrir referência da publicaçãoCopiado.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.
Abrir referência DOICopiado.