Uma metodologia para classificação de dados nominais baseada no processo KDD : ênfase aos algoritmos culturais, estimação de distribuição e análise de correspondência múltipla

Abstract

Resumo: A classificação de padrões é um problema de aprendizado supervisionado do campo da ciência conhecido como Reconhecimento de Padrões (RP), através do qual se deseja discriminar instâncias de dados em diferentes classes. A solução para este problema é obtida por meio de algoritmos (classificadores) que buscam por padrões de relacionamento entre classes em casos conhecidos (treinamento), usando tais relações para classificar casos desconhecidos (teste). O desempenho em termos de acurácia preditiva dos algoritmos que se propõem a realizar tal tarefa depende muito da qualidade e dos tipos de dados contidos nas bases. Visando melhorar a qualidade dos dados e dar tratamento adequado aos tipos de dados utilizados, o presente trabalho faz uso do processo de Descoberta de Conhecimento em Bases de Dados (Knowledge Discovery in Databases; KDD), no qual a classificação é uma das tarefas da etapa conhecida como Mineração de Dados (Data Mining; DM). As etapas aqui aplicadas antes da classificação são a seleção de atributos wrapper e um processo de transformação de atributos baseado em Análise Geométrica de Dados (Geometric Data Analysis; GDA). Para a seleção de atributos é proposta uma nova técnica baseada em Algoritmo de Estimação de Distribuição (Estimation of Distribution Algorithm; EDA) e em Algoritmos Culturais (AC) batizada de Belief-Based Incremental Learning (BBIL). Para a transformação de atributos é aqui proposta a utilização de uma alternativa à clássica Análise de Componentes Principais (Principal Component Analysis; PCA) para lidar especificamente com dados nominais: a Análise de Correspondência Múltipla (Multiple Correspondence Analysis; MCA). Na etapa de DM, de fato, faz-se a aplicação de dois tradicionais classificadores da área de RP, Naïve Bayes e Função Discriminante Linear de Fisher (Linear Discriminant Analysis; LDA). Apoiado em argumentos teóricos e em testes empíricos realizados com nove diferentes conjuntos de dados nominais, o presente trabalho objetiva avaliar a capacidade do MCA e do BBIL em melhorar o desempenho de classificadores em termos de acurácia preditiva média. Com o objetivo de se beneficiar simultaneamente das vantagens de ambos os tratamentos de dados são avaliadas duas combinações entre estas técnicas. A primeira trata-se da transformação GDA sobre os atributos previamente selecionados e, a segunda, a seleção de factor scores do MCA utilizando o BBIL (metodologia proposta). Os resultados dos experimentos confirmam a melhoria no desempenho de classificação proporcionada pelos tratamentos realizados e atestam a superioridade da metodologia proposta na maioria das situações analisadas.

Abstract: Pattern classification is a supervised learning problem in the field of science known as Pattern Recognition, through which to discriminate data instances in different classes. The solution to this problem is obtained through algorithms (classifiers) that search for patterns of relationships between classes in known cases (training), using such relationships to classify unknown cases (test). The performance in terms of predictive accuracy of the algorithms they propose to undertake such a task depends on the quality and types of data from databases. To improve the quality of data and provide proper treatment to the types of data used, the present work makes use of the process of Knowledge Discovery in Databases (KDD), in which classification is one of the tasks of step known as Data Mining (DM). The steps here applied before classification are feature selection wrapper and a process of transformation of attributes based on Geometric Data Analysis (GDA). For feature selection is proposed a new technique based on Estimation of Distribution Algorithm (EDA) and Cultural Algorithms named Belief-Based Incremental Learning (BBIL). For the transformation of attributes is proposed here the use of an alternative to the classical Principal Component Analysis (PCA) to deal specifically with nominal data: the Multiple Correspondence Analysis (MCA). In the stage of DM, in fact, it is the application of two traditional classifiers area Pattern Recognition, Naïve Bayes (NB) and Fisher Linear Discriminant Function (Linear Discriminant Analysis, LDA). Supported by theoretical arguments and empirical tests conducted with nine different nominal datasets, this study aims to evaluate the ability of the MCA and BBIL in improving the performance of classifiers in terms of predictive accuracy. In order to benefit simultaneously from the advantages of both data treatments are evaluated two combinations of these techniques. The first one refers to the transformation GDA on the attributes previously selected, and the second one, the selection of the MCA factor scores using the BBIL (proposed methodology). The experimental results confirm the improvement in classification performance provided by the treatments performed and attest to the superiority of the proposed methodology in most analysed situations.