Km++knn: Um Algoritmo Rápido Para A Busca Exata de K Vizinhos

O algoritmo k-NN – k-nearest neighbor – é amplamente utilizado em Aprendizado de Máquina e Estatística para tarefas que envolvem classificação e regressão. Tendo como entradas uma instância x, um conjunto de instâncias T e um inteiro k ≥ 1, o k-NN realiza uma busca exaustiva em T das k instâncias mais similares à instância x (k vizinhos). Em aplicações envolvendo grande número de instâncias e/ou instâncias com alta dimensionalidade, o processo de busca consome muito tempo devido à necessidade de se realizar muitos cálculos de funções de similaridade entre instâncias. Diversas propostas para reduzir o tempo de busca do k-NN têm sido feitas, algumas delas objetivando a busca exata das k instâncias mais similares a x em T e, outras, reduzindo o tempo de busca via métodos que calculam de forma aproximada as instâncias mais similares a x. Este trabalho propõe um algoritmo denominado kM++kNN para a busca exata das k instâncias mais similares a x em T, utilizando o conceito de desigualdade triangular para reduzir o tempo de busca do k-NN. O algoritmo kM++kNN é comparado, em experimentos de medida da economia do número de cálculos funções de similaridade entre instâncias e de tempo de busca, com um algoritmo atualmente considerado rápido, o kMkNN.