Algoritmo dos k-vizinhos mais próximos

Em estatística, o algoritmo dos k vizinhos mais próximos (k-NN) ou do inglês k-nearest neighbors algorithm é um método de aprendizado supervisionado não paramétrico. Foi desenvolvido por Evelyn Fix e Joseph Hodges em 1951, e posteriormente expandido por Thomas Cover. Mais frequentemente, é usado para classificação, como um classificador k-NN, cuja saída é uma associação de classe. Um objeto é classificado por uma votação da pluralidade de seus vizinhos, sendo o objeto atribuído à classe mais comum entre seus k vizinhos mais próximos (k é um inteiro positivo, normalmente pequeno). Se k = 1, então o objeto é simplesmente atribuído à classe daquele vizinho mais próximo.

O algoritmo k-NN também pode ser generalizado para regressão. Na regressão k-NN, também conhecida como suavização do vizinho mais próximo, a saída é o valor da propriedade do objeto. Esse valor é a média dos valores dos k vizinhos mais próximos. Se k = 1, então a saída é simplesmente atribuída ao valor daquele vizinho mais próximo, também conhecida como interpolação do vizinho mais próximo.

Tanto para classificação quanto para regressão, uma técnica útil pode ser atribuir pesos às contribuições dos vizinhos, de modo que os vizinhos mais próximos contribuam mais para a média do que os distantes. Por exemplo, um esquema de ponderação comum consiste em atribuir a cada vizinho um peso de 1/d, onde d é a distância até o vizinho.

A entrada consiste nos k exemplos de treinamento mais próximos em um conjunto de dados. Os vizinhos são obtidos de um conjunto de objetos para os quais a classe (para classificação k-NN) ou o valor da propriedade do objeto (para regressão k-NN) é conhecido. Isso pode ser considerado o conjunto de treinamento para o algoritmo, embora nenhuma etapa de treinamento explícita seja necessária.

Uma peculiaridade (às vezes até uma desvantagem) do algoritmo k-NN é sua sensibilidade à estrutura local dos dados. Na classificação k-NN, a função é aproximada apenas localmente e todo o cálculo é adiado até a avaliação da função. Como esse algoritmo depende da distância, se as características representam unidades físicas diferentes ou estão em escalas muito diferentes, a normalização dos dados de treinamento por características pode melhorar significativamente sua precisão.