Performance evaluation of feature selection algorithms applied to data streams classification with concept drift

Orientador: André Leon Sampaio GradvohlDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de TecnologiaResumo: Fluxos de Dados são dados gerados de modo contínuo, potencialmente infinito, em grande volume, alta velocidade e alta quantidade de atributos, tornando impraticável seu armazenamento em sistemas tradicionais. Nesse caso, os fluxos de dados precisam ser analisados e processados de modo on-line, na medida em que são recebidos, no menor tempo possível. Entretanto, por serem potencialmente infinitos, espera-se que a distribuição probabilística dos dados mude ao longo do tempo, fenômeno conhecido como Mudança de Conceito. Esse fenômeno torna o processo de análise de dados on-line completamente dinâmico. Uma forma de analisar esses fluxos é por meio da aplicação de algoritmos de classificação on-line, que categorizam os dados em diferentes classes para tomadas de decisão futuras. A alta quantidade de atributos dos fluxos, no entanto, dificulta o processo de classificação por aumentar o custo computacional e o tempo necessário para o aprendizado, além de agravar os impactos da mudança de conceito. Por isso, algoritmos de seleção de atributos on-line vêm sendo propostos na literatura, com o objetivo de reduzir a quantidade de atributos a partir da remoção de atributos irrelevantes ou redundantes para o processo de classificação. No entanto, esses algoritmos não foram avaliados em cenários de mudança de conceito, o que dificulta sua real utilização nesses cenários. Neste sentido, o objetivo inicial deste trabalho foi avaliar cinco algoritmos de seleção de atributos on-line propostos na literatura em cenários de mudança de conceito. A partir dos resultados obtidos, que demonstraram um baixo desempenho dos algoritmos comparados à utilização de um classificador base considerando o domínio completo de atributos, esta pesquisa identificou uma oportunidade de melhoria e propôs o algoritmo Modified Online Feature Selection. Trata-se de uma versão modificada do algoritmo Online Feature Selection, que utiliza regularização dinâmica para minimizar os impactos das mudanças de conceito no processo de seleção de atributos on-line. Os experimentos -- utilizando conjuntos de dados reais e artificiais com três tipos de mudanças de conceito -- apontam que o algoritmo proposto obteve acurácias até 13,73% superiores aos demais algoritmos, incluindo o classificador base que considerou o domínio completo de atributos, em cinco de sete cenáriosAbstract: Data streams are continuous, potentially unbounded and high-dimensional data, transmitted at high-volume and high-velocity, which turns impracticable its storage in traditional database mechanisms. In such cases, data streams have to be processed and analyzed online. However, as it is potentially unbounded, it is expected a change in data probabilistic distribution over time, a phenomenon is known as Concept Drift. The concept drift phenomenon turns the online data process and analysis completely dynamic. Using classification algorithms is one approach to learn from data streams, as it will categorize the data into different classes for future decisions. However, data streams high dimensionality imposes a challenge on the classification process, since it increases both computational cost and time, as well as aggravate the concept drift impacts. To solve this problem, online feature selection algorithms have been proposed to reduce data dimensionality by removing irrelevant and redundant attributes from the data streams. However, none of these algorithms were evaluated in concept drift environments. Therefore, this work firstly intended to verify which algorithm performed better in concept drift environments. From the obtained results, which showed low performance in comparison with a base classifier using all attributes, we identified an improvement opportunity. Therefore, in this work, we propose the Modified Online Feature Selection algorithm, a modified version of the Online Feature Selection algorithm, which uses dynamic regularization to minimize the concept drift impacts on the online feature selection process. The experiments using both real and artificial datasets showed the proposed algorithm obtained accuracies up to 13,73% better than the other algorithms, including the base classifier, in five out of seven scenariosMestradoSistemas de Informação e ComunicaçãoMestre em TecnologiaCAPE