Affiliations: [a] Faculdade de Computação e Informática, Brasil | [b] Programa de Pós-Graduação em Engenharia Elétrica e Computação, Brasil | [c] Universidade Presbiteriana Mackenzie, Brasil | [d] Escola Politécncia da Universidade de São Paulo, Brasil
Correspondence:
[*]
Corresponding author: Leandro A. Silva, Programa de Pós-Graduação em Engenharia e Computação Faculdade de Computação e Informática, Rua da Consolação, 930, São Paulo, Brasil. E-mail: leandroaugusto.silva@mackenzie.br.
Abstract: Due to the high accuracy of the K nearest neighbor algorithm in different problems, KNN is one of the most important classifiers used in data mining applications and is recognized in the literature as a benchmark algorithm. Despite its high accuracy, KNN has some weaknesses, such as the time taken by the classification process, which is a disadvantage in many problems, particularly in those that involve a large dataset. The literature presents some approaches to reduce the classification time of KNN by selecting only the most important dataset examples. One of these methods is called Prototype Generation (PG) and the idea is to represent the dataset examples in prototypes. Thus, the classification process occurs in two steps; the first is based on prototypes and the second on the examples represented by the nearest prototypes. The main problem of this approach is a lack of definition about the ideal number of prototypes. This study proposes a model that allows the best grid dimension of Self-Organizing Maps and the ideal number of prototypes to be estimated using the number of dataset examples as a parameter. The approach is contrasted with other PG methods from the literature based on artificial intelligence that propose to automatically define the number of prototypes. The main advantage of the proposed method tested here using eighteen public datasets is that it allows a better relationship between a reduced number of prototypes and accuracy, providing a sufficient number that does not degrade KNN classification performance.
