GeeksforGeeks (Português)

K-Nearest Neighbours é um dos algoritmos de classificação mais básicos, porém essenciais, no aprendizado de máquina. Pertence ao domínio da aprendizagem supervisionada e encontra aplicação intensa em reconhecimento de padrões, mineração de dados e detecção de intrusão.

É amplamente descartável em cenários da vida real, uma vez que é não paramétrico, ou seja, não faz quaisquer suposições subjacentes sobre a distribuição de dados (ao contrário de outros algoritmos, como GMM, que assumem uma distribuição Gaussiana dos dados fornecidos).

Recebemos alguns dados anteriores (também chamados de dados de treinamento), que classifica as coordenadas em grupos identificados por um atributo.

Como exemplo, considere a seguinte tabela de pontos de dados contendo dois recursos:

Agora, dado outro conjunto de pontos de dados ( também chamados de dados de teste), aloque esses pontos em um grupo analisando o conjunto de treinamento. Observe que os pontos não classificados são marcados como ‘Brancos’.

Intuição
Se plotarmos esses pontos em um gráfico, podemos localizar alguns clusters ou grupos. Agora, dado um ponto não classificado, podemos atribuí-lo a um grupo observando a qual grupo pertencem seus vizinhos mais próximos. Isso significa que um ponto próximo a um grupo de pontos classificados como Vermelho tem maior probabilidade de ser classificado como Vermelho.

Intuitivamente, podemos ver que o primeiro ponto (2,5, 7) deve ser classificado como Verde e o segundo ponto (5.5, 4.5) deve ser classificado como Vermelho.

Algoritmo
Seja m o número de amostras de dados de treinamento. Seja p um ponto desconhecido.

1. Armazene as amostras de treinamento em uma matriz de pontos de dados arr. Isso significa que cada elemento desta matriz representa uma tupla (x, y).

2. for i=0 to m: Calculate Euclidean distance d(arr, p).

3. Faça o conjunto S das K menores distâncias obtidas . Cada uma dessas distâncias corresponde a um ponto de dados já classificado.
4. Retorne o rótulo da maioria entre S.

K pode ser mantido como um número ímpar para que possamos calcular uma clara maioria no caso em que apenas dois grupos são possíveis (por exemplo, vermelho / azul). Com o aumento de K, obtemos limites mais suaves e definidos em diferentes classificações. Além disso, a precisão do classificador acima aumenta à medida que aumentamos o número de pontos de dados no conjunto de treinamento.

Exemplo de programa
Assuma 0 e 1 como os dois classificadores (grupos).

Resultado:

The value classified to unknown point is 0.

Este artigo foi contribuído por Anannya Uberoi. Se você gosta de GeeksforGeeks e gostaria de contribuir, também pode escrever um artigo usando contrib.geeksforgeeks.org ou enviar seu artigo para [email protected]. Veja o seu artigo na página principal do GeeksforGeeks e ajude outros Geeks.