K vizinhos mais próximos - KNN

3 minuto(s) de leitura

Introdução

Após um pequeno hiato no blog, hoje vamos falar um pouco sobre um dos classificadores clássicos mais conhecidos, o K vizinhos mais próximos (do inglês:K nearest neighboors – KNN). O KNN foi proposto por Fukunaga e Narendra em 1975 [1]. É um dos classificadores mais simples de ser implementado, de fácil compreensão e ainda hoje pode obter bons resultados dependendo de sua aplicação. Antes de iniciar, caso você não tenha afinidade com o problema de classificação, sugiro que leia nosso post sobre classificação de dados. Agora, sem mais delongas, vamos ao que interessa.

Funcionamento do KNN

A ideia principal do KNN é determinar o rótulo de classificação de uma amostra baseado nas amostras vizinhas advindas de um conjunto de treinamento. Nada melhor do que um exemplo para explicar o fucionamento do algoritmo como o da Figura 1, na qual temos um problema de classificação com dois rótulos de classe e com . No exemplo, são aferidas as distâncias de uma nova amostra, representada por uma estrela, às demais amostras de treinamento, representadas pelas bolinhas azuis e amarelas. A variável representa a quatidade de vizinhos mais próximos que serão utilizados para averiguar de qual classe a nova amostra pertence. Com isso, das sete amostras de treinamento mais próximas da nova amostra, 4 são do rótulo e 3 do rótulo . Portanto, como existem mais vizinhos do rótulo , a nova amostra receberá o mesmo rótulo deles, ou seja, .

Figura 1: exemplo de classificação do KNN com dois rótulos de classe e k = 7

Dois pontos chaves que devem ser determinados para aplicação do KNN são: a métrica de distância e o valor de . Portanto, vamos discutir cada uma delas.

Cálculo da distância

Calcular a distância é fundamental para o KNN. Existem diversas métricas de distância, e a escolha de qual usar varia de acordo com o problema. A mais utilizada é a distância Euclidiana, descrita pela equação 1.

Outros exemplos de distância, é a de Minkowsky:

E também, a distância de Chebyshev:

Em todos os casos, e são dois pontos -dimensionais e na equação 2, é uma constante que deve ser escolhida. No exemplo da Figura 1, essas distâncias seriam calculadas entre as bolinhas (azuis e laranjas) e a estrela (a nova entrada). Como o exemplo é 2D, cada uma cada ponto teria seu valor em e em . Para problemas com dimensões maiores a abordagem é a exatamente a mesma, porém, a visualização das amostras no espaço é mais complicada.

A escolha de K

Em relação a escolha do valor , não existe um valor único para a constante, a mesma varia de acordo com a base de dados. É recomendável sempre utilizar valores ímpares/primos, mas o valor ótimo varia de acordo com a base de dados. Dependendo do seu problema, você pode utilizar um algoritmo de otimização (PSO, GA, DE etc) para encontrar o melhor valor para o seu problema. Todavia, você pode deixar o desempenho geral do modelo bem lento na etapa de seleção de . Outra maneira e simplesmente testar um conjunto de valores e encontrar o valor de empiricamente.

Pseudocódigo

Para melhor compreensão do algoritmo, apresento também o pseudocódigo do mesmo.

Código do KNN em Python

Resumidamente, a grande vantagem do KNN é sua abordagem simples de ser compreendida e implementada. Todavia, calcular distância é tarefa custosa e caso o problema possua grande número de amostras o algoritmo pode consumir muito tempo computacional. Além disso, o método é sensível à escolha do . Por fim, deixo linkado uma implementação do KNN em Python. No repositório existe bases de dados comuns da literatura, como Iris e Australian Credit. Todavia, você pode utilizar o código para qualquer que seja a base. Bom proveito!

Implementação do KNN em Python

Referências

[1] Fukunaga, K.; Narendra, P. M. A branch and bound algorithm for computing k-nearest neighbors. IEEE Transactions on Computers, v. 100, n. 7, p. 750–753, 1975.

Deixe um comentário