Abordagens Adaptativas de Ramificação em Árvores de Decisão Incrementais para Mineração de Fluxo de Dados

INTRODUÇÃO: A área de mineração de fluxo de dados estuda o desenvolvimento de algoritmos capazes de extrair padrões em dados produzidos constantemente em alta velocidade em forma de fluxo. Na tarefa de classificação de fluxo de dados, um dos principais e mais utilizados algoritmos para esse problema são Hoeffding Trees, árvores de decisão projetadas para o cenário de aprendizagem online. Para evitar a indução de uma árvore de decisão para cada exemplo que se deseja classificar, Hoeffding Trees mantém estatísticas de instâncias em nós folhas e periodicamente realiza tentativas de ramificação baseadas no teorema de Hoeffding. Contudo, essa abordagem não considera a evolução dos dados ao longo do tempo. OBJETIVOS: Esse trabalho foca no desenvolvimento de árvores de decisão com nós-folha adaptativos que visam contornar as limitações descritas em Hoeffding Trees. MATERIAIS E MÉTODO: A adaptabilidade em nós folhas é alcançada por algoritmos de detecção de mudança, que constantemente são atualizados com instâncias que chegam e determinam os momentos em que ramificações irão ocorrer. As árvores de decisão propostas nesse trabalho são avaliadas a nível monolítico e de ensemble. Esse trabalho contemplou a proposta de duas árvores de decisão, sendo elas materializadas com os algoritmos Local Adaptive Streaming Tree (LAST) e Global Adaptive Streaming Tree (GAST). O algoritmo LAST mantêm algoritmos de detecção de mudança em nós folhas, que monitoram constantemente a qualidade preditiva ou distribuição dos dados. O algoritmo GAST possui somente um detector de mudança de conceito que monitora estatísticas de diversos nós folhas simultaneamente. RESULTADOS: Os métodos com a combinação dos mecanismos estáticos e adaptativos reportaram os melhores resultados em 6 de 7 ensembles estado-da-arte. Em um comparativo entre ensembles, a ensemble Streaming Random Subspace igualou os melhores resultados reportados (ensemble Streaming Random Patches) com custo computacional inferior. CONSIDERAÇÕES FINAIS: As árvores propostas também apresentam limitações referentes a sua aplicação como base learners de ensembles. A limitação de árvores com mecanismos adaptativos foram contornadas com a proposta de combinação do mecanismo estático presente em Hoeffding Trees e adaptativo. A continuação da pesquisa envolve o estudo de viabilidade de técnicas de regularização de árvores e reavaliação de ramificações a partir das abordagens desenvolvidas.

PALAVRAS-CHAVE: Minieração de Fluxos de Dados; Ramificação em Árvores de Decisão Incrementais; Detectores de Mudança