Algoritmo de Classificação: KNN (K Nearest Neighbors)

O algoritmo KNN, abreviação de K Nearest Neighbors, é um algoritmo bastante utilizado por cientistas de dados, principalmente pela sua facilidade de implementação (além de ser um lazy learner*). É um algoritmo supervisionado de machine learning, utilizado para problemas de classificação e regressão. Hoje, o foco é na parte de classificação. A ideia é simples, separar os indivíduos em grupos (ou classes) de acordo com a semelhança existente. Vamos entender o que isso quer dizer…

Imagine que você tenha que dividir as pessoas em grupos semelhantes. Querendo buscar alguma semelhança, talvez para entender as características que distinguem um bom aluno do mau, ou um bom pagador do mau pagador ou qualquer outro tipo de classificação, podendo envolver obviamente mais de duas classes. A questão aqui é que você tem um problema que exige classificação dos indivíduos de acordo com suas características, buscando encontrar os semelhantes. Esse é o tipo de problema em que normalmente se utiliza a técnica KNN.

Vamos supor que você tenha 15 indivíduos. Você possui as informações de peso e altura deles, e também a definição de quem é um bom jogador de basquete. Os dados estão apresentados no gráfico abaixo:

Você sabe desses atletas quem é ruim e quem é bom no basquete. Os pontos em vermelho são os atletas ruins e os verdes são os bons:

Agora, imagine que chega um novo jogador para você analisar a contratação. Você acredita, e sabe por vários outros estudos, que peso e altura têm impacto considerável na qualidade do atleta. Por isso, você quer classificar o novo atleta de acordo com a proximidade dele aos demais jogadores de sua base de dados. Imagine que o ponto preto é o novo jogador. Você diria que ele é um mau ou bom jogador?

Um (não tão) breve parênteses aqui: essa base que temos acima é o nosso histórico, é o que a gente observou no passado e vai usar para fazer classificações no futuro. Afinal, o modelo não sai do nada. Você primeiro tem um histórico de informações com as características dos indivíduos e a partir disso você vai fazer predições para novos entrantes da base. Quando se está num banco, por exemplo, você tem a informação da dívida de determinado cliente, suas características e o histórico de pagamento (i.e. se o indivíduo pagou a dívida ou não). A partir disso, quando entra um novo cliente, você consegue definir se ele será um bom ou mau pagador, verificando com quem ele se parece mais no nosso histórico. Dito isto, a questão levantada no parágrafo anterior é semelhante, porém para definir se o jogador é bom ou ruim.

Voltando ao problema depois desse longo parênteses, uma das respostas possíveis e que você verá com frequência envolve o uso do KNN. O que o KNN faz é encontrar os k indivíduos mais próximos deste ponto, daí o nome k nearest neighbors: os k vizinhos mais próximos. Caso você defina que k = 1, então você analisará o vizinho mais próximo ao seu novo ponto, ou seja, encontrará o ponto mais próximo ao novo indivíduo e, se este ponto for da classe A, o ponto indefinido pertencerá à classe A. Se você escolher k = 5, então o algoritmo irá analisar os 5 pontos mais próximos do ponto sem classe definida e a definição será pelo número de votos.

COMO DECIDIR QUAL K USAR?

Da forma mais simples possível: medindo a distância entre os pontos. Aqui, pensaremos na distância Euclidiana. No entanto, tenha em mente que outras distâncias também podem ser utilizadas, como a Hamming e a Manhattan. Veja que se você desenhar um círculo em volta do ponto preto, você terá situações em que mais você terá mais pontos vermelhos e outras em que você terá mais pontos verdes. Ou seja, a depender do k escolhido, você o ponto será classificado como verde ou vermelho.

A definição do k é talvez a parte mais complexa. Inclusive, você vai encontrar diversos posts que ignoram essa parte da aula (confesso que fiquei tentado à isso). De uma forma geral, a escolha é subjetiva, depende muito do método sendo utilizado e dos parâmetros. Outra forma, é escolher o método que foi mais acurado na sua base teste. Outros métodos mais elegantes, como a inspeção de um dendograma e o elbow method podem ser encontrados neste post. Prometo que futuramente vou explorar essas análises aqui no EstatSite.

MAS E SE TIVERMOS MAIS DE 2 VARIÁVEIS?

Na prática, é raro que somente duas variáveis sejam determinantes para fazer boas predições. Pense no nosso exemplo do banco. Você provavelmente utilizaria as características pessoais do cliente, como endereço e profissão, mas também as informações da dívida, como o montante e o número de parcelas. O KNN continuaria sendo executado da mesma forma, calculando a diferença entre os pontos. O melhor de tudo é que o software que você estiver utilizando (R, Python ou SAS) faz as contas para você. O importante é saber que a ideia é a mesma. Ah, e é claro, se você está na faculdade, isso não é motivo para relaxar em Álgebra Linear.

MOMENTO DE ATENÇÃO!

Um pequeno, mas importante, aviso para encerrar o post. Veja que se você comparar um jogador de 1,80m com outro de 1,60m, a distância entre os dois será de 0,2 unidades da medida em questão. Entretanto, se você comparar um jogador de 80kg com um de 82kg, você terá uma diferença de duas unidades da métrica em questão. Ou seja, a diferença de peso, apesar de ser pequena, tem peso 10 vezes maior que a diferença nas alturas. Por esse motivo, por tratarmos de unidades diferentes, toda vez que rodamos um knn precisamos nos certificar de que os dados foram normalizados, caso contrário, a escala pode interferir na análise.

Creio que com isso você já possa iniciar a prática. No próximo post, compartilharei um exemplo em R fácil de ser replicado!

E se você gostou do post, não vá embora sem deixar uma curtida ou um comentário. Eu sei que não parece relevante, mas faz diferença para mim e custa pouco para você, vai… Se encontrou algum erro ou tem alguma sugestão, dúvida, elogio ou crítica, pode escrever nos comentários ou me enviar uma mensagem diretamente em Sobre o Estatsite. E visite também a conta do Twitter @EstatSite, costumo postar algumas coisas bem rapidinho por lá, geralmente são posts e códigos mais curtos ou compartilhamento de algo legal ou alguma reflexão.

Forte abraço e bons estudos!

Leitura adicional:

https://towardsdatascience.com/machine-learning-basics-with-the-k-nearest-neighbors-algorithm-6a6e71d01761

https://stats.stackexchange.com/questions/287425/why-do-you-need-to-scale-data-in-knn

https://medium.com/brasil-ai/knn-k-nearest-neighbors-1-e140c82e9c4e