Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/14284
Document type: Tese
Access type: Acesso Aberto
Title: Algoritmo de aprendizado supervisionado - baseado em máquinas de vetores de suporte - uma contribuição para o reconhecimento de dados desbalanceados
Alternate title (s): Supervised learning Algorithm - Based on Support Vector Machines - A Contribution to the Recognition of Unbalanced Data
Author: Rufino, Hugo Leonardo Pereira
First Advisor: Veiga, Antônio Cláudio Paschoarelli
First member of the Committee: Camilo Júnior, Celso Gonçalves
Second member of the Committee: Carrijo, Gilberto Arantes
Third member of the Committee: Yamanaka, Keiji
Fourth member of the Committee: Vellasco, Marley Maria Bernardes Rebuzzi
Summary: O aprendizado de máquina em conjuntos de dados que possuam classes desbalanceadas tem recebido considerável atenção na comunidade científica, pois os algoritmos de classificação tradicionais não fornecem um desempenho satisfatório. Este baixo desempenho pode ser justificado pelo fato das técnicas tradicionais de aprendizado de máquina considerarem que cada classe presente em um conjunto de dados possui um número aproximadamente igual de instâncias. Entretanto, a maioria dos conjuntos de dados reais possuem classes com uma distribuição desbalanceada, onde uma classe de dados está super representada em comparação com outras classes. Isto faz com que surjam classificadores com uma alta precisão para a predição da classe majoritária e com baixa precisão para prever a classe minoritária. Logo, a classe minoritária é ignorada pelo classificador. Esta predisposição do classificador em relação à classe majoritária ocorre em função dos classificadores serem projetados para maximizar a precisão em relação ao conjunto de dados que está sendo utilizado para o treinamento. No treinamento do classificador é assumido que quando for fazer a predição de dados ainda não vistos, estes terão a mesma distribuição dos dados que foram utilizados no treinamento. Isto limita sua habilidade em reconhecer exemplos da classe minoritária. Várias melhorias nos algoritmos tradicionais de classificação têm sido propostas na literatura, onde foram feitas considerações a nível de dados e a nível de algoritmos. O primeiro utiliza diversas formas de reamostragem, tal como super-amostragem de exemplos da classe minoritária, sub-amostragem de exemplos da classe majoritária ou a combinação de ambos. Os últimos tentam adaptar (inserindo custos diferenciados em exemplos da classe minoritária e majoritária, alterando kernels, e outras técnicas) os algoritmos de classificação já existentes para melhorar o desempenho da classe minoritária. Vários algoritmos na forma de um comitê de máquinas também são reportados como meta-técnicas para trabalhar com classes desbalanceadas. Esta tese estuda os principais algoritmos que lidam com classes desbalanceadas, destacando suas principais características como: a geração de novos exemplos sintéticos ao invés da replicação de dados de forma aleatória, no processo de super-amostragem; o uso de penalidades diferentes para erros de classificação da classe minoritária e majoritária; e a utilização de comitês de máquinas para que os classificadores gerados possuam uma capacidade de generalização maior. Após o levantamento das contribuições que cada algoritmo fornece, foi feito um estudo se poderia obter algo mais das características de cada um. Foi feita uma modificação no algoritmo que gera novos exemplos sintéticos de forma que reduzisse a possibilidade de geração de novos elementos na região incorreta. Como em conjuntos de dados altamente desbalanceados, a geração de elementos sintéticos não é suficiente para equilibrar o conjunto, houve a necessidade da criação de um novo algoritmo para efetuar uma sub-amostragem de exemplos da classe majoritária. E, para melhorar a capacidade de generalização do classificador gerado, também foi feita uma modificação em um algoritmo de comitês de máquinas. Utilizando estas três etapas, obteve-se um algoritmo composto que possui uma taxa de acerto na classificação de dados melhor que os algoritmos nos quais se baseou.
Abstract: The machine learning in datasets that have unbalanced classes, has received considerable attention in the scientific community, because the traditional classification algorithms don t provide a satisfactory performance. This low performance can be explained by the fact that the traditional techniques of machine learning consider that each class present in the database has an approximately equal number of instances. However, most real datasets, have classes with an unbalanced distribution, where one class is over represented in comparison with the others. This gives rise to classifiers with high accuracy to predict the majority class and low accuracy for predicting the minority class. Therefore, the minority class is ignored by the classifier. This predisposition of the classifier for the majority class occurs, because the classifiers are designed to maximize accuracy in relation to the database being used for training. In training the classifier, it is assumed that when making the prediction of data not yet seen, they have the same distribution of the data that were used in training. This limits its ability to recognize examples of the minority class. Several improvements in the traditional classification algorithms have been proposed in the literature, where considerations were made at the level of data and algorithms. The former uses various ways of resampling, such as oversampling of examples from the minority class, undersampling the majority class or a combination of both. The latter attempt to adapt (by inserting dierent costs in the minority class examples and majority, changing kernels and other techniques) the existing classification algorithms to improve the performance of minority class. Several algorithms in the form of a ensemble machine, are also reported as meta-techniques for working with unbalanced classes. This thesis studies the main algorithms that deal with unbalanced class, highlighting its main features as: the generation of new synthetic examples instead of replicating data at random, in the process of oversampling; the use of dierent penalties to misclassification of the minority and majority class; and the use of ensembles for that the generated classifiers have a greater ability to generalize. After assessing the contributions that each algorithm provides, a study was done if one could get something more of the characteristics of each one. It was made a modification in the algorithm that generates new synthetic examples of way that reduces the possibility of generating new elements in the incorrect region. As with highly unbalanced datasets, the generation of synthetic elements is not enough to balance the whole, there was a need to develop a new algorithm to perform an undersampling the majority class examples. And to enhance the generalization ability of the generated classifier, was also made a change to an ensemble algorithm. Using these three steps, we obtained an compound algorithm that has a hit rate of data classification better than the algorithms on which it was relied.
Keywords: Aprendizado do computador
Inteligência artificial
Algoritmos de computador
Aprendizado supervisionado
Máquinas de vetores de suporte
Conjuntos de dados desbalanceados
Supervised learning
Support vector machines
Unbalanced datasets
Area (s) of CNPq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
Language: por
Country: BR
Publisher: Universidade Federal de Uberlândia
Institution Acronym: UFU
Department: Engenharias
Program: Programa de Pós-graduação em Engenharia Elétrica
Quote: RUFINO, Hugo Leonardo Pereira. Supervised learning Algorithm - Based on Support Vector Machines - A Contribution to the Recognition of Unbalanced Data. 2011. 107 f. Tese (Doutorado em Engenharias) - Universidade Federal de Uberlândia, Uberlândia, 2011.
URI: https://repositorio.ufu.br/handle/123456789/14284
Date of defense: 26-Sep-2011
Appears in Collections:TESE - Engenharia Elétrica

Files in This Item:
File Description SizeFormat 
t.pdf2.93 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.