kNN - uma introdução aos algoritmos de aprendizado de máquina
Neste artigo darei continuidade a série de artigos do time de Pesquisa & Desenvolvimento, sobre algoritmos clássicos de aprendizado de máquina.
Hoje irei falar sobre (e implementar) o algoritmo k Vizinhos Mais Próximos, conhecido como kNN (do inglês, k Nearest Neighbors). Na primeira parte do artigo, irei introduzir a teoria do algoritmo, e na segunda parte, farei uma implementação simples em Python.
Parte 1 - Introdução
O kNN é um simples e popular algoritmo de aprendizado de máquina que pode ser utilizado para problemas de classificação e regressão. Em resumo, dado um elemento sem rótulo conhecido, seu rótulo será definido por uma análise de seus k vizinhos mais próximos.
Mas o que define “vizinhos”?
Vizinhos são basicamente os elementos mais próximos (ou semelhantes) a um dado elemento. Para encontrá-los, existem diversas métricas de cálculo de distância (ou similaridade) entre dois pontos. Uma delas, muito popular, é a Distância Euclidiana, definida abaixo.
Assim, a distância é calculada entre dois exemplos (pontos) a e b do nosso conjunto de dados, onde aᵢ e bᵢ representam seus respectivos atributos. Um exemplo pode possuir entre 1 a n atributos (desconsiderando sua classe) mas por fins didáticos, iremos utilizar exemplos com 2 atributos, que podem ser facilmente visualizados em um espaço 2D.
No entanto, essa métrica não é indicada no caso de existência de valores extremos (conhecidos como outliers) no nosso conjunto de dados. Felizmente, pode-se tentar normalizar os dados ou utilizar outras medidas de similaridade resistentes à escala dos dados, como por exemplo, a Medida de Mahalanobis.
E o que fazer com os vizinhos?
Depois de escolher uma métrica e calcular as distâncias para achar os k vizinhos mais próximos, isto é, os k elementos que possuem menor distância ao novo elemento, é feito a seguinte análise:
- para problemas de classificação, o rótulo do novo elemento é dado pela maioria dentre os rótulos desses k elementos selecionados.
- já para regressão, o rótulo é dado pela média dos valores de todos esses k elementos.
Exemplo
Para exemplificar, vamos considerar um problema de classificação ilustrado na seguinte figura. Nela temos exemplos da classe “Class A” e “Class B”. Além disso, existe um exemplo não classificado ainda, representado por um quadrado amarelo.
Analisando os 3 vizinhos mais próximos ao novo elemento, temos dois exemplos da “Class B” e um exemplo da “Class A”. Dessa forma, podemos concluir que esse elemento pertence a “Class B”. Porém, note que se considerarmos k = 7, teríamos agora 4 exemplos “Class A” e 3 exemplos “Class B” e com isso, o novo elemento pertenceria agora a “Class A”.
Então como escolher o valor de k?
O k é o principal parâmetro do algoritmo e deve ser escolhido com cuidado. Uma dica, mas não regra, é escolher um valor pequeno e ímpar (para minimizar o risco de empate em classificação binária). Escolhas comuns são algo como 3, 5, 7 e etc. Porém, pode-se fazer testes de classificação variando valores de k, para definir o melhor valor.
Vantagens e desvantagens
Para finalizar a primeira parte desse artigo vamos discutir as vantagens e desvantagens do algoritmo. Entre as vantagens estão sua simplicidade em teoria e implementação, e por trazer bons resultados em diversas aplicações. Como desvantagem, temos seu custo computacional, pois para cada novo exemplo, devemos calcular sua distância até todos os outros exemplos, além de ser sensível a ruídos nos dados. Vale também lembrar que o algoritmo espera variáveis numéricas que devem ser, de preferência, normalizadas.
Parte 2 - Implementação
Agora que você já entendeu a teoria do algoritmo, ou pelo menos chegou até aqui, vamos implementá-lo?! Ps: Nessa implementação, prezei pela didática e não na otimização e tratamento de exceções do código.
Módulo para cálculo de distâncias
A primeira função a ser implementada é a função para cálculo da Distância Euclidiana, demonstrada abaixo. A função recebe dois pontos (exemplos) a e b como parâmetro e retorna a distância euclidiana entre eles.
Módulo para a função principal
Depois da função de similaridade, vamos, em partes, criar nossa função principal. A primeira etapa é calcular a distância do novo exemplo a todos os exemplos de treino, denotados por novo_exemplo e dados_treino, respectivamente. Esse passo é exemplificado no código a seguir, onde guardamos essas distâncias em um dicionário, em que distancias[i] representa a distância do novo_exemplo ao exemploᵢ.
Com as distâncias do novo_exemplo até todos os exemplos de treino, vamos selecionar quem são seus k vizinhos mais próximos. Para isso, vamos ordenar o dicionário de distâncias e em seguida, selecionar o índice dos k elementos com menor distância, ou seja, as k primeiras posições.
Já que agora sabemos quem são os k vizinhos dos novo_exemplo, vamos contabilizar as classes desses vizinhos. Assim, vamos iniciar um dicionário com as classes “1” e “2” e analisar a classe dos vizinhos: sempre que um exemplo tiver uma certa classe, atualizamos o contador dessa classe. Por fim, a classe com mais votos (maior valor), é a classe mais provável para o novo_exemplo, e será retornada ao final da execução.
Dado as etapas anteriores, finalizamos todas as tarefas da nossa função principal. Juntando todos os trechos acima, devemos ter algo parecido como o próximo trecho de código, que define uma função chamada knn. Essa função deve receber como parâmetro um conjunto de treinamento, um exemplo a ser classificado e k, um valor inteiro positivo, que define o número de vizinhos a ser analisado.
Vamos testar?
Para testar nosso código, vamos supor que temos o seguinte conjunto de dados de treino, plotados em um espaço 2D. Nesse caso, os triângulos azuis representam a classe “1” e os círculos laranjas representam a classe “2”.
Porém, suponha que apareceu um novo exemplo ainda sem classe, que pode ser visualizado na seguinte figura, representado por um quadrado verde com coordenadas (30, 20).
Você, provavelmente, já deve imaginar a qual classe o exemplo deve pertencer. Mas vamos testar com nosso o algoritmo utilizando k = 3.
Ao analisar a saída do nosso algoritmo, observamos o seguinte resultado.
Dessa forma, analisando os 3 vizinhos mais próximos do exemplo, podemos concluir que a classe mais provável ao novo_exemplo, é a classe “2”. E aí, acertou?
Isso é tudo, pessoal!
Espero que tenha sido uma leitura tranquila e útil. Voltaremos em breve com mais artigos sobre algoritmos de aprendizado de máquina. Mas enquanto isso, que tal fazer novos testes variando o valor de k ou então criar um novo exemplo não classificado?
Qualquer dúvida, não hesite em perguntar! Também, caso queira sugerir algum algoritmo/técnica/tutorial que gostaria de ver por aqui, deixe nos comentários!
