Resumo: A tarefa de classificação em Mineração de Dados utiliza algoritmos chamados de classificadores para extrair padrões sobre bases de dados. Bases de dados reais podem apresentar um desbalanceamento em suas classes, contendo mais casos de uma classe do que de outras. Algoritmos classificadores têm dificuldade em encontrar padrões de qualidade para as classes minoritárias, pelo fato dos casos pertencentes à classe minoritária possuírem pouca representatividade no conjunto de treinamento. Isto se torna um problema quando a classe minoritária é a de maior interesse para o usuário. O objetivo deste trabalho é o desenvolvimento de extensões para o algoritmo Ant-Miner (Ant Colony-based Data Miner) para ajudar a encontrar melhores regras para as classes minoritárias. Essas extensões modificam, principalmente, a forma como as regras são construídas e avaliadas. O algoritmo Ant-Miner é baseado na meta heurística ACO (Ant Colony Optimization) e tanto a versão original quanto outros trabalhos relacionados mostram que a técnica é competitiva com outros algoritmos de classificação. Além disso, são analisadas técnicas de balanceamento (undersampling e oversampling) e também um estudo da análise ROC (Receiver Operating Characteristics). As técnicas de balanceamento visam fazer uma nova amostragem dos dados mudando a distribuição do conjunto de treinamento. A análise ROC realiza avaliações mais apuradas que outras métricas (e.g.: taxa de acerto), principalmente quando se trata de bases com classes desbalanceadas. Resultados experimentais mostraram que os algoritmos desenvolvidos contribuíram para a descoberta de melhores regras para as classes minoritárias e também com a simplicidade do modelo de regras.
Abstract: The classification task in Data Mining uses algorithms called classifiers to find patterns on data bases. Real data bases can have an imbalance in its classes, when there are more cases of one class then the others. Classification algorithms are sensitive of this imbalance and tend to valorize the majority class and ignore de minority class, because the cases of minority class have low representation on the training set. It is a problem when the minority class is the class of interest. In this work we propose two extensions to the Ant-Miner algorithm to find better rules to the minority classes. These extensions modify, mainly, how rules are constructed and evaluated. The Ant-Miner algorithm is based on ACO (Ant Colony Optimization). The original version and others related works showed that the Ant-Miner is competitive with other standard classifiers. Moreover, we analyzed sampling techniques (undersampling and oversampling) and also a study of ROC (Receiver Operating Characteristics) analysis. The sampling techniques aim to make a new sampling of the data sets changing the classes? proportion of the training set. The ROC analysis can evaluate the results with more accurate than other metrics, mainly when the classifiers are applied in data sets with classes imbalance. Experimental results showed that the developed algorithms contribute to the rule discovery of the minority classes and also contribute with the simplicity of the rules. |
