Algoritmo genético restrito por listas tabu no contexto de mineração de dados

Abstract

Resumo: O presente trabalho teve como objetivo a obtenção e implementação de um algoritmo de geração de um classificador, no contexto da Mineração de Dados. Este classificador utilizou Algoritmos Genéticos (AGs). Alguns dos fundamentos que justificaram a escolha deste paradigma, foram baseados em sua grande capacidade em lidar com ruídos, dados inválidos ou imprecisos e, sua facilidade de adaptação frente à diferentes domínios de dados. A principal contribução do algoritmo projetado é a utilização de listas tabu restringindo o processo de seleção do AG. Esta restrição permite gerar um conjunto de regras potenciais para o classificador. Este tipo de estrategia foi proposta recentemente para trabalhar com funções multimodais e ainda não tinha sido avaliado seu comportamento no contexto de mineração de dados. Para análise da eficiência do algoritmo implementado foram realizados testes em cinco bases de dados, e os resultados comparados a 34 algoritmos classificadores. Posteriormente, foram realizados testes com adição de ruídos nas bases de dados. O algoritmo implementado demonstrou ser efeciente e robusto. A estratégia utilizada para manter a diversidade do AGs se mostrou válida, pois mesmo na utilização de populações menores, o algoritmo conseguiu manter sua precisão de classificação. A maior dificuldade encontrada no algoritmo foi o ajuste da medida de distância, parâmetro utilizado para as listas Tabu, o que afetou diretamente os resultados da precisão de classificação do algoritmo.

Abstract: The present work aims to obtain and to implement a algorithm of generation of a classifier, in the context of Data Mining. This classifier used Genetic Algorithms (AGs). The choice of this paradigm is partially justified on its great capacity in dealing with noise, invalid or inexact data, and its easy adaptation to different domains of data. The GA algorithm uses Tabu List to restrict the selection process. This restriction allows the creation a set of potential rules for the classifier tool. This strategy was proposed recently, for multimodal and multiobjective function optimization and this behavior had not still been evaluated in the context of Data Mining. For analysis of the efficiency of the algorithm, tests were performed on five databases and compared with 34 classifying algorithms. Later, tests with addition of noises to the databases were performed. The implemented algorithm was shown to be efficient and robust. The strategy used to keep the diversity in the searching process was considered valid, since even for smaller populations, the algorithm kept its accuracy of sorting. The biggest difficulty found in the algorithm was the adjustment of the measure of distance, parameter used for the Tabu lists, which directly affected the results of the accuracy of sorting of the algorithm.