Técnicas geométricas de condensação para o classificador k-NN

Abstract

Na aproximação ao reconhecimento de padrões por aprendizagem baseadaem instâncias, um conjunto de treino formado por padrões (objectos,exemplos, instâncias) são recolhidos e usados para a implementação do classificador (regra de decisão). Entre estes, o mais conhecido,é o classificador k-vizinhos mais próximos (k-NN). Esta regra de decisão,classifica um novo objecto na classe mais votada entre os seus k-vizinhos mais próximos, no conjunto de treino. Quando este (o conjunto de treino) é grande, a taxa de erro obtida para o classificador k-NN é pequena e aproxima-se do erro óptimo de Bayes. Contudo, ao considerarmos um conjunto de treinogrande o custo computacional eleva-se, limitando a eficiência do classificador. De facto, para determinar os k-vizinhos mais próximos de um novo objecto (não classificado) é necessário calcular todas as distâncias entre este e oconjunto de elementos do conjunto de treino. As técnicas de condensação, identificam e eliminam os objectos do conjunto de treino que não contribuem para a melhoria do desempenho do classificador, por isso, constituem uma parte fundamental na implementação do classificador k-NN. A presente dissertação, analisa como as estruturas geométricas de proximidade e vizinhança, tais como o diagrama de Voronoi, grafo de Gabriel egrafo de Vizinhança Relativa, mostram ser boas estratégias para acondensação do conjunto de treino, sem que se degrade significativamente odesempenho do classificador k-NN. O trabalho inicia-se com uma breve introdução ao reconhecimento de padrões,seguido de um estudo sobre as principais características do classificador k-NN. Depois, é produzida uma análise detalhadadas propriedades e dos métodos de construção associados a cada estrutura geométrica. Em seguida, são descritas as técnicas geométricas de condensação para o classificador k-NN, por aplicação de estruturas geométricas de proximidade e vizinhança. Finalmente, são referidos os resultados de estudos experimentais mais recentes, relativos à comparação de diferentes técnicas geométricas decondensação para a implementação da regra k-NN.

In instance based learning approach to pattern recognition, a training set of patterns (examples, instances, objects) are collected and used to implement a classifier (decision rule). One of the most well known of such rules is the k-nearest neighbour (k-NN) classifier. This decision rule classifies an unknownobject in the majority class among the k-nearest neighbours in the training set. When this one is large the k-NN decision rule gives low error rates approaching the Bayes optimal error. However, for large training datasets its efficiency is limited by a high computationally cost;indeed, to compute the nearest neighbours for each new unclassified objectwe need to compute all the distances between itand the whole training set. Condensing techniques,identifying and removing objectsfrom the training set that do not improve classification performance, play an important part in the implementation of a k-NN classifier. The main goal of this thesis is to study how geometric proximityand neighbourhood structures such as Voronoi diagram, Gabriel graph and RelativeNeighbourhood graph provide good condensed training sets for the k-NN classifier while maintaining similar accuracy levels. At first, a brief introduction to pattern recognition is given followed by a studyabout the principal characteristics of the k-NN classifier. Next, a detailed study of the main characteristics and construction methods of each geometric structure is carried out. Afterwards, the geometric condensing techniques to k-NN classifier based on the application of the geometric proximity and neighbourhood structures are described. Finally, results of recent experimentalstudies aimed at comparing different geometric condensing techniques for thek-NN decision rule are provided.