Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2007. / Submitted by Luis Felipe Souza (luis_felas@globo.com) on 2008-12-10T18:56:04Z No. of bitstreams: 1 Dissertacao_2007_EmersonMachado.pdf: 480909 bytes, checksum: 33454d8cde13ccd0274df91f48a4125d (MD5) / Approved for entry into archive by Georgia Fernandes(georgia@bce.unb.br) on 2009-03-04T12:18:48Z (GMT) No. of bitstreams: 1 Dissertacao_2007_EmersonMachado.pdf: 480909 bytes, checksum: 33454d8cde13ccd0274df91f48a4125d (MD5) / Made available in DSpace on 2009-03-04T12:18:48Z (GMT). No. of bitstreams: 1 Dissertacao_2007_EmersonMachado.pdf: 480909 bytes, checksum: 33454d8cde13ccd0274df91f48a4125d (MD5) / O objetivo geral desta pesquisa é analisar técnicas para aumentar a acurácia de classificadores construídos a partir de bases de dados desbalanceadas. Uma base de dados é desbalanceada quando possui muito mais casos de uma classe do que das outras, portanto possui classes raras. O desbalanceamento também pode ser em uma mesma classe se a distribuição dos valores dos atributos for muito assimétrica, levando à ocorrência de casos raros. Algoritmos classificadores são muito sensíveis a estes tipos de desbalanceamentos e tendem a valorizar as classes (ou casos) predominantes e a ignorar as classes (ou casos) de menor freqüência. Modelos gerados para bases de dados com classes raras apresentam baixa acurácia para estas classes, o que é problemático quando elas são classes de interesse (ou quando uma delas é a classe de interesse). Já os casos raros podem ser ignorados pelos algoritmos classificadores, o que é problemático quando tais casos pertencem à classe (ou às classes) de interesse. Uma nova proposição de algoritmo é o Cluster-based Smote, que se baseia na combinação dos métodos de Cluster-based Oversampling (oversampling por replicação de casos guiada por clusters) e no SMOTE (oversampling por geração de casos sintéticos). O método Cluster-based Oversampling visa melhorar a aprendizagem de pequenos disjuntos, geralmente relacionados a casos raros, mas causa overfitting do modelo ao conjunto de treinamento. O método SMOTE gera novos casos sintéticos ao invés de replicar casos existentes, mas não enfatiza casos raros. A combinação desses algoritmos, chamada de Clusterbased Smote, apresentou resultados melhores do que a aplicação deles em separado em oito das nove bases de dados utilizadas proposta nesta pesquisa. A outra abordagem proposta nesta pesquisa visa a diminuir a sobreposição de classes possivelmente provocada pela aplicação do método SMOTE. Intuitivamente, esta abordagem consiste em guiar a aplicação do SMOTE com a aprendizagem não supervisionada proporcionada pela clusterização. O método implementado sob esta abordagem, denominado de C-clear, resultou em melhora significativa em relação ao SMOTE em três das nove bases testadas e empatou nas demais. Foi também proposta uma nova abordagem para limpeza de dados baseada na aprendizagem não supervisionada, a qual foi incorporada ao C-clear. Esta limpeza somente surtiu melhora em uma base de dados, sendo este baixo desempenho oriundo possivelmente da escolha não adequada de seus parâmetros de limpeza. A aprendizagem destes parâmetros a partir dos dados ficou como trabalho futuro. ___________________________________________________________________________________________ ABSTRACT / It is intended in this work to research methods that improve the accuracy of classifiers applied to data set with class imbalance (high skew in class distribution causing rare classes) and within-class imbalance (high skew in data within-class distribution causing care cases). Standard classifier algorithms are strongly affected by these characteristics and their generated model are biased to the majority classes (or cases), in detriment of classes (or cases) underrepresented. Generally, models generated with imbalanced data set suffer from low accuracy for the minority classes, which is a problem when the target class is one of them. Eventually, rare cases are likely of being ignored by inductors, which is a problem when they belong to the interesting class (or classes). A new method is proposed in this work, Cluster-based Smote, which combines the methods Cluster-based Oversampling (oversampling by replication of positive cases guided by clusters) and SMOTE (Synthetic Minority Oversampling Technique). Cluster-based Oversampling addresses small disjuncts, but overfits the model to the training set. The method SMOTE addresses the overfit problem of random oversampling, but does not treat rare cases. The combination of them proposed in this research, named Cluster-based Smote, presented better results in eight out of nine datasets, compared to the applying of them all alone. Another approach proposed in this research aims at reducing the class overlap problem possibly caused by applying SMOTE. The main idea is to guide the SMOTE process by non-supervised learning (with clustering techniques). The method implemented under this approach, named Cclear, resulted in significant improvement over SMOTE in three out of nine datasets. A cleaning method based in the non-supervised learning was also proposed and has been incorporated in the C-clear method. The cleaning method improved the results in only one dataset, probably because of the not so well values chosen as cleaning parameters. The learning of these parameters from the data is left as a future work.