Análise do impacto de feature selection e detecção de concept drift na classificação de fluxos de dados em evolução

Abstract

O aprendizado a partir de fluxos de dados sofre de diversos problemas que não existem em outros cenários de aprendizado de máquina convencional. Os principais problemas tratados nesse trabalho são a sua natureza online e não estacionária, além de suas consequências: as possíveis mudanças na função geradora dos dados, que caracterizam um concept drift. Esse cenário cria a necessidade de novos algoritmos desevolvidos para se adaptar à essas possíveis mudanças, que podem ocorrer de maneira gradual ou abrupta. Mas não limitado a essas anomalias, também existe a necessidade de lidar com uma possível alta dimensionalidade dos dados somado à necessidade de realizar o aprendizado incrementalmente, e em tempo real. Como resposta a esses desafios, existem diferentes soluções no estado da arte, envolvendo variados mecanismos como feature selection e métodos de detecção de concept drift. Portanto, nesse trabalho é analisado o impacto e viabilidade da adição desses mecanismos à algoritmos de classificação, em relação ao custo computacional e poder preditivo. Para isso, é proposto um algoritmo de controle definido como um comitê de árvores de decisão equipado com adaptação passiva externa aos classificadores base, e três modificações distintas originadas dele, onde uma utiliza um seletor de features relevantes, outra um detector de concept drift e adaptação ativa, e a última modificação utiliza os dois simultaneamente. Para comparar estas variações, são apresentados os resultados dos testes em múltiplos cenários representados por datasets sintéticos e reais. Deste modo, o algoritmo utilizando apenas feature selection e adaptação passiva apresentou ganho de acurácia e diminuição do custo computacional, enquanto os algoritmos utilizando métodos de detecção de concept drift apresentaram um desempenho inferior ao demais algoritmos, na maioria dos casos. Esses resultados foram verificados utilizando o teste de Friedman com procedimento post-hoc, onde a modificação com apenas feature selection foi a única que mostrou diferença estatisticamente significativa sobre os outros algoritmo com grau de confiança de 0.10, enquanto os testes foram inconclusivos para os algoritmos que utilizaram adaptação ativa.

Learning from data streams poses many challenges that are not present in conventional machine learning. The main problems addressed in this work are the datastream’s online nature and non stationarity, and its consequences: the possible changes in the generating function, that is also called a concept drift. This scenario creates the need for new algorithms that are able to adapt to these changes, which can happen in a gradual, or abrupt manner. But not limited to these anomalies, there is also the need to deal with the possibility of high dimensional data, added to the need for real time incremental learning. As an answer for these challenges, many solutions have been suggested in the state of the art, involving many mechanisms like feature selection and concept drift detection methods. Therefore, in this work we analyze the impact and viability of the adition of these mechanisms to classification algorithms, in relation to prediction power and computing cost. For this purpose, an ensemble classifier made of decision trees, equiped with a passive adapting method extern to the base learners, is proposed as a control algorithm, while three modifications originated by it are used as comparison, one using a relevant features selector, a second one using concept drift detector and active adapting, and the last one using both simultaneously. In order to compare these variations, the results of testing on multiple scenarios are presented, represented by testing on real and synthetic datasets. This way, the algorithm using only feature selection and passive adapting showed increases in accuracy and lower computing cost, while those equiped with active adaptation performed worse in most cases. These results were verified using a Friedman test with a post-hoc procedure, where the modification using only feature selection was the only one that showed statistically significant difference to the other algorithms with confidence level of 0.10, while the tests were inconclusive for those using active adapting.