Aprendizagem Baseada em Instâncias — KNN
O K Nearest Neighbors (KNN) ou os K vizinhos mais próximos, traduzindo para o português, é um algoritmo de aprendizagem de máquina supervisionado. Embora seja majoritariamente utilizado em problemas de classificação, este algoritmo também pode ser aplicado em problemas de regressão.
A aprendizagem baseada em instâncias provém da não existência de um modelo (regra ou função) construído a partir de uma base de dados de treinamento (até porque o KNN não possui uma etapa de treinamento, propriamente dito). O que se faz é armazenar todos os dados (instâncias) de treinamento (demandando um alto poder de armazenamento), e a cada nova instância que se deseja classificar, cálculos comparativos são realizados entre esta e os demais dados já existentes. Por esse motivo, o KNN é conhecido como sendo um algoritmo preguiçoso.
O KNN faz a comparação entre instâncias por meio do cálculo da distância entre vetores/dados dispostos no espaço euclidiano. Existem várias métricas para calcular a distância entre pontos no espaço (Euclidiana, Hamming, Manhattan, Minkowski, Chebyshev e outras), aqui vamos analisar o algoritmo utilizando a distância Euclidiana, por ser a mais comumente utilizada.
Na imagem acima temos inicialmente todos os dados dispostos no espaço euclidiano (incluindo o dado que se deseja classificar). Em seguida o algoritmo realiza o cálculo da distância euclidiana entre a nova instância e todas as outras instâncias já classificadas (uma a uma), em que a classe é conhecida através dos dados de treinamento. Com todas as distâncias calculadas, os K elementos mais próximos (com menor distância) são selecionados e suas respectivas classes são analisadas (representado no terceiro gráfico da figura). Por fim, a classe que obteve maior representatividade através dos K vizinhos mais próximos será usada para definir o rótulo da nova instância. No exemplo da figura, o novo elemento seria classificado como sendo da Classe B.
Quando o KNN é utilizado em problemas de classificação, a predição é feita por meio da classe com maior representatividade (moda). Por outro lado, em problemas de regressão, o resultado da predição é definido como sendo a média dos K valores mais próximos.
A análise matemática do algoritmo é essencialmente concentrada na equação da distância euclidiana:
- Em que n representa o número de variáveis (colunas) que são usadas para caracterizar os dados e m é a variável que é iterada por esses possíveis valores — m=1, 2, …, n. A variável alvo não entra nos equacionamentos.
- pim e pjm são, respectivamente, o vetor com as características do dado a ser classificado e o vetor que contém as informações referentes aos dados existentes (dados de treino).
- Esse cálculo é realizado x vezes, onde x é a quantidade de instâncias existentes no conjunto de treino.
Para visualizar como a equação da distância euclidiana é aplicada em uma base de dados de interesse, vamos usar o exemplo das imagens abaixo:
A figura acima é uma base de dados didática que retrata o Risco (variável alvo) de conceder crédito bancário a um cliente dados os atributos História do crédito, Dívida, Garantias e Renda anual.
Visto que todos os atributos são categóricos é necessário fazer a transformação para variáveis numéricas, afinal operações aritméticas serão realizadas sobre esses valores. Com as devidas transformações feitas em cada variável, a imagem seguinte clarifica como é realizado o cálculo da distância entre um novo registro que se deseja classificar e os dados de “treino” já existentes. Na imagem são calculadas a distância entre o novo registro e o terceiro e nono registro da base de dados, no entanto, para finalizar a classificação é necessário calcular a distância em relação a todas as instâncias para saber quais são os K vizinhos mais próximos.
Vantagens
- É um algoritmo simples, fácil de entender e de fácil implementação, porém poderoso.
- Possui um bom desempenho quando os dados apresentam relacionamentos entre características complexos.
- Não possui uma etapa de treinamento, logo não requer a construção de um modelo.
- Não requer o ajuste de muitos parâmetros para otimizar o desempenho do algoritmo.
Desvantagens
- O custo computacional do algoritmo cresce drasticamente com o aumento do número de dados de treino e em data sets com muitos atributos (valor de n elevado). Logo em casos em que a predição precisa ser feita de forma rápida, o KNN é uma opção lenta.
- Definir um valor para K é normalmente uma tarefa manual, experimental e não trivial.
- Requer uma atenção maior no pré-processamento dos dados que serão armazenados pelo algoritmo, uma vez que variáveis categóricas precisam ser transformadas e a métrica utilizada pelo algoritmo é o cálculo da distância entre pontos.
Aplicações práticas
- Mineração de texto
- Previsões climáticas
- Sistemas de recomendação
Escolhendo o valor certo para K
Como mencionado, a escolha do valor ótimo para K é um processo experimental onde se executa várias vezes o algoritmo para diferentes valores de K até que se encontre o K que minimize os erros de classificação mantendo a capacidade de prever novas instâncias de forma precisa (sem viés).
É importante considerar que:
- Para valores de K muito pequenos (K = 1, por exemplo), o algoritmo tende a se tornar instável, adquirindo sensibilidade a ruídos e variações presentes nos dados (outliers) e por consequência aumentando as chances de realizar predições incorretas.
- Por outro lado, quando se aumenta o valor de K as predições são realizadas pelo voto da maioria, dando estabilidade ao algoritmo e melhorando a precisão das predições. No entanto, ao aumentar o valor de K além de certo ponto, o número de erros volta a subir (pois irá considerar pontos muito distantes e possivelmente fora da região desejada).
- Em problemas de classificação, deseja-se que o valor de K seja um número ímpar, de forma a evitar cenários de empate de votos entre classes durante a classificação.
Exemplo Prático
Recomendo o artigo abaixo caso você esteja interessado em ter outra perspectiva sobre o KNN, inclusive aprender uma forma de como esse algoritmo pode ser implementado utilizando Python.
