O K-NN é um dos algoritmos mais simples e intuitivos de classificação. Ele não assume nenhuma forma paramétrica para os dados. Primeiramente, o algoritmo armazena todos os exemplos de treinamento. Durante a classificação, ele calcula a distância do novo ponto para todos os exemplos armazenados. Em seguida, seleciona os K exemplos mais próximos (vizinhos). A classe mais frequente entre estes K vizinhos define a classificação. Por exemplo, com K=3, dois vizinhos da classe A e um da classe B resulta em A. Portanto, o K-NN é um método baseado em instâncias (lazy learning).
escolha do parâmetro k e métricas de distância
A escolha do parâmetro K é crucial para o desempenho do algoritmo. Valores pequenos de K (ex: 1) tornam o modelo sensível a ruídos. Valores grandes de K, por outro lado, suavizam demais as fronteiras de decisão. A validação cruzada ajuda a encontrar o K ótimo para cada problema. Além disso, a métrica de distância também impacta o resultado. A distância euclidiana é a mais comum e intuitiva. Para dados categóricos, a distância de Hamming pode ser mais adequada. Em espaços de alta dimensão, a distância de Manhattan às vezes supera a euclidiana. Portanto, normalize os atributos para que todos tenham a mesma escala. Atributos com escalas maiores dominariam a distância indevidamente.
vantagens e limitações do k-nn
O K-NN oferece várias vantagens importantes para classificação. Primeiramente, ele é extremamente simples de entender e implementar. Não requer treinamento explícito, apenas armazenamento dos dados. Além disso, o algoritmo é naturalmente multiclasse e não-linear. Ele pode modelar fronteiras de decisão complexas e arbitrárias. Contudo, o K-NN tem limitações significativas. O custo computacional na classificação é alto (O(N)). Para cada novo ponto, calcula-se distância para todos os exemplos de treinamento. Outra desvantagem é a necessidade de armazenar todo o conjunto de treinamento. Em grandes bases de dados, isto consome muita memória. Além disso, o K-NN sofre com a maldição da dimensionalidade. Em altas dimensões, a distância entre os pontos torna-se menos discriminativa.
quando utilizar o classificador k-nn
Utilize o K-NN quando o conjunto de treinamento for moderadamente pequeno. Por exemplo, até alguns milhares de exemplos. Outra aplicação adequada é quando as fronteiras de decisão são complexas. O K-NN também funciona bem como baseline para problemas mais elaborados. Por exemplo, sistemas de recomendação usam K-NN para encontrar itens similares. Reconhecimento de dígitos manuscritos é outro caso clássico de sucesso. Contudo, evite o K-NN em bases de dados muito grandes (milhões de exemplos). O custo computacional na predição torna-se proibitivo. Nestes casos, use redes neurais ou árvores de decisão. Além disso, evite o K-NN em espaços de altíssima dimensão (centenas de atributos). A redução de dimensionalidade (PCA) pode ser aplicada como pré-processamento. Em resumo, escolha o K-NN pela sua simplicidade e eficácia em problemas de pequena e média escala.