Algoritmo K-Nearest Neighbors (KNN) — Uma abordagem matemática
K-Nearest Neighbors também conhecido como K Vizinhos mais próximos é um algoritmo de aprendizado supervisionado baseado em instância, no qual pode ser aplicado para resolve tanto problemas de classificação quanto de regressão.
O aprendizado baseado em instância é frequentemente chamado de lazy learning, pois ele não cria modelos antecipadamente. Em vez disso, os dados de treinamento são armazenados e no momento de realizar uma classificação os dados de treinamento são recuperados para serem utilizados.
Com isso, após essa breve introdução vamos ver uma breve explicação logica sobre o funcionamento do KNN. Let’s go!!
Agora vamos imaginar um plano cartesiano de Peso x Tamanho, com os registros divididos entre duas classes: crianças e adultos.
Lembrando do significado de um modelo baseado em instância, desejamos classificar se uma novo registro é adulto ou criança.
Sendo que esse novo registro encontrasse em Tamanho = 1,73 e Peso = 65.
Para que não seja possível chegar a um impasse o numero de vizinhos deve ser sempre impar, pois se ocorrer de existir 4 vizinhos sendo dois adultos e duas crianças o algoritmo não vai saber qual escolher aquele com maior recorrência. Com isso consideraremos o numero de vizinhos mais próximos igual a 3.
A imagem abaixo ilustrara melhor esse exemplo.
Considerando a área no qual os três vizinhos mais próximos estão do registro verde é possível identificar que em sua maioria a classe adulta se mantem predominante.
Dessa forma considerando o numero de vizinhos igual a três o algoritmo KNN classifica esse registro de teste como sendo um Adulto.
Agora, após contextualizamos a logica de funcionamento do algoritmo KNN vamos partir para o tópico principal desse artigo, como é realizado a abordagem matemática por trás desse algoritmo.
Para realização do cálculo da distancia entre registro que será classificado com os registos da base de treinamento a técnica empregada mais popular é a do cálculo da distância euclidiana.
A distância euclidiana é calculada como a raiz quadrada da soma das diferenças quadráticas entre um novo ponto P(X1, Y1) e um ponto existente Pe(X2, Y2).
Com isso, vamos realizar os cálculos do ponto destaca em verde na figura 2, para comprovamos o resultado da classificação feita.
Dessa forma é possível comprovar que entre as 3 menores distâncias calculadas prevalece a classe adulta como sendo a mais presente.
Além da distância euclidiana existem também outas técnicas populares para cálculo de distancia:
Distância de Hamming: Calcula a distância entre os vetores binários.
Distância Manhattan: Calcula a distância entre vetores reais usando a soma de sua diferença absoluta. Também chamado de City Block Distance.
Distância Minkowski: Generalização da distância Euclidiana e Manhattan.
Considerações finais
Com isso, concluímos aqui esse artigo. Nele nós podemos aprender um pouco da abordagem matemática por traz desse simples e eficiente algoritmo, no qual com baixa capacidade de processamento possui capacidade de fornecer bons resultados.
Referências
K. Fukunaga and P. M. Narendra, “A Branch and Bound Algorithm for Computing k-Nearest Neighbors,” in IEEE Transactions on Computers, vol. C-24, no. 7, pp. 750–753, July 1975, DOI: 10.1109/T-C.1975.224297.
S. A. Dudani, “The Distance-Weighted k-Nearest-Neighbor Rule,” in IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-6, no. 4, pp. 325–327, April 1976, DOI: 10.1109/TSMC.1976.5408784.
