Deborah Ribeiro Carvalho

Título



Árvore de Decisão / Algoritmo Genético Para Tratar o Problema de Pequenos Disjuntos em Classificação de Dados

Orientador(es)



Nelson Francisco Favilla Ebecken e Alex Alves Freitas

Resumo



Este trabalho aborda a tarefa de classificação em Data Mining, na qual o conhecimento pode ser representado por regras da forma “se-então”. Em situações como esta se pode identificar a presença de pequenos disjuntos, o que em síntese são regras que cobrem um pequeno número de exemplos. Este trabalho propõe um método híbrido árvore de decisão / algoritmo genético para tratar do problema dos pequenos disjuntos. A idéia básica é que os exemplos pertencentes a grandes disjuntos sejam classificados pelas regras produzidas pelo algoritmo de árvore de decisão, enquanto exemplos pertencentes a pequenos disjuntos (aqueles considerados de mais difícil classificação) sejam classificados pelas regras descobertas por um algoritmo genético. O método híbrido proposto é avaliado quanto a três características desejáveis das regras descobertas: precisão preditiva, compreensibilidade e grau de interesse. Como medida do grau de interesse, este trabalho investiga 11 medidas objetivas de grau de interesse, as quais tentam estimar o verdadeiro e subjetivo grau de interesse do usuário nas regras descobertas. O método proposto obteve bons resultados, considerando tanto a precisão preditiva quanto a simplicidade das regras descobertas. Os testes para avaliar o grau de interesse das regras descobertas mostraram que em geral a eficácia de medidas de interesse de regras depende bastante da base de dados, como era esperado, mas foram identificadas algumas medidas de interesse que tiveram um desempenho mais consistente para várias bases de dados. Palavras-chave: Data Mining, Classificação, Algoritmo Genético, Árvore de Decisão, Pequenos Disjuntos, Medidas de Interesse de Regras.

Abstract



This work addresses the classification task in Data Mining, where the discovered knowledge can be represented by "if-then" rules. In this scenario it is possible to identify the presence of small disjuncts which, in essence, are rules covering a small number of examples. This work proposes a hybrid decision tree / genetic algorithm method for coping with the small-disjunct problem. The basic idea is that examples belonging to large disjuncts are classified by a decision tree algorithm, whereas examples belonging to small disjuncts (whose classification is considerably more difficult) are classified by rules discovered by a genetic algorithm. The proposed hybrid method is evaluated with respect to three desirable characteristics of the discovered knowledge: predictive accuracy, comprehensibility and degree of interestingness. Concerning the degree of interestingness, this work investigates 11 objective, data-driven rule interestingness measures, which try to estimate the true, subjective degree of interestingness of the user in the discovered rules. The proposed method obtained good results, with respect to both the predictive accuracy and the simplicity of the discovered rules. The experiments evaluating the degree of interestingness of the discovered rules showed that in general the effectiveness of objective rule interestingness measures significantly depends on the data set, as expected, but one has identified some rule interestingness measures that had a more consistent performance for several data sets. Keywords: Data Mining, Classification, Genetic Algorithm, Decision Tree, SmallDisjuncts, Rule Interestingness Measures.

Print