O Algorítmo k-Nearest Neighbors (kNN) em Machine Learning

Neste post você descobrirá sobre o algoritmo k-Nearest Neighbors (KNN), ou método dos vizinhos mais próximos, para classificação e regressão. Depois de ler este post você saberá:

• A representação do modelo usada pelo KNN.
• Como um modelo é aprendido usando KNN (dica, não é).
• Como fazer previsões usando o KNN
• Os muitos nomes para o KNN, incluindo como diferentes campos se referem a ele.
• Como preparar seus dados para aproveitar ao máximo o KNN.
• Onde procurar para aprender mais sobre o algoritmo KNN.

Este post foi escrito para desenvolvedores e não assume nenhum histórico em estatística ou matemática. O foco está em como o algoritmo funciona e como usá-lo para problemas de modelagem preditiva. Se você tiver alguma dúvida, deixe um comentário e eu farei o meu melhor para responder.

Vamos começar.

Representação do Modelo KNN

A representação do modelo para o KNN é o conjunto de dados completo do treinamento.

É tão simples quanto isso.

O KNN não possui outro modelo além de armazenar o conjunto de dados inteiro, portanto, não é necessário aprender.

Implementações eficientes podem armazenar os dados usando estruturas de dados complexas, como árvores kd, para fazer a pesquisa e a correspondência de novos padrões durante a previsão eficiente.

Como todo o conjunto de dados de treinamento é armazenado, convém pensar cuidadosamente sobre a consistência de seus dados de treinamento. Pode ser uma boa ideia organizá-lo, atualizá-lo com frequência à medida que novos dados forem disponibilizados e remover dados errôneos e discrepantes.

Fazendo previsões com o KNN

A KNN faz previsões usando o conjunto de dados de treinamento diretamente.

As previsões são feitas para uma nova instância (x) pesquisando todo o conjunto de treinamento para as K instâncias mais semelhantes (os vizinhos) e resumindo a variável de saída para essas instâncias de K. Para a regressão, essa pode ser a variável de saída média; na classificação, esse pode ser o valor de classe do modo (ou mais comum).

Para determinar quais das instâncias do K no conjunto de dados de treinamento são mais semelhantes a uma nova entrada, uma medida de distância é usada. Para variáveis ​​de entrada de valor real, a medida de distância mais popular é a distância euclidiana .

A distância euclidiana é calculada como a raiz quadrada da soma das diferenças quadráticas entre um novo ponto (x) e um ponto existente (xi) em todos os atributos de entrada j.

Distância Euclidiana (x, xi) = sqrt (soma ((xj – xij) ^ 2))

Outras medidas populares de distância incluem:

• Distância de Hamming: Calcula a distância entre os vetores binários ( mais ).
• Manhattan Distance: Calcula a distância entre vetores reais usando a soma de sua diferença absoluta. Também chamado de City Block Distance ( mais ).
• Distância Minkowski: Generalização da distância Euclidiana e Manhattan ( mais ).

Existem muitas outras medidas de distância que podem ser usadas, como a distância de Tanimoto, Jaccard , Mahalanobis e cosseno. Você pode escolher a melhor métrica de distância com base nas propriedades de seus dados. Se não tiver certeza, você pode experimentar diferentes métricas de distância e valores diferentes de K juntos e ver qual mistura resulta nos modelos mais precisos.

Euclidean é uma boa medida de distância para usar se as variáveis ​​de entrada forem semelhantes em tipo (por exemplo, todas as larguras e alturas medidas). A distância de Manhattan é uma boa medida para usar se as variáveis ​​de entrada não forem semelhantes em tipo (como idade, sexo, altura, etc.).

O valor para K pode ser encontrado por ajuste de algoritmo. É uma boa ideia tentar vários valores diferentes para K (por exemplo, valores de 1 a 21) e ver o que funciona melhor para o seu problema.

A complexidade computacional do KNN aumenta com o tamanho do conjunto de dados de treinamento. Para conjuntos de treinamento muito grandes, o KNN pode ser estocástico tomando uma amostra do conjunto de dados de treinamento a partir do qual calcular as instâncias mais semelhantes.

Diferentes nomes para kNN

KNN existe há muito tempo e tem sido muito bem estudado. Como tal, disciplinas diferentes têm nomes diferentes para isso, por exemplo:

• Aprendizado Baseado em Instância: As instâncias de treinamento brutas são usadas para fazer previsões. Como tal, o KNN é geralmente chamado de aprendizado baseado em instância ou de aprendizado baseado em casos (onde cada instância de treinamento é um caso do domínio do problema).
• Aprendizado Preguiçoso: Nenhum aprendizado do modelo é necessário e todo o trabalho acontece no momento em que uma previsão é solicitada. Como tal, o KNN é frequentemente referido como um algoritmo de aprendizado lento .
• Não paramétrica: a KNN não faz suposições sobre a forma funcional do problema a ser resolvido. Como tal, o KNN é referido como um algoritmo de aprendizagem de máquina não paramétrico .

O KNN pode ser usado para problemas de regressão e classificação.

KNN para regressão

Quando o KNN é usado para problemas de regressão, a previsão é baseada na média ou na mediana das instâncias mais semelhantes.

KNN para classificação

Quando o KNN é usado para classificação, a saída pode ser calculada como a classe com a maior frequência das instâncias mais semelhantes do K. Cada instância, em essência, vota em sua classe e a classe com o maior número de votos é considerada a predição.

As probabilidades de classe podem ser calculadas como a frequência normalizada de amostras que pertencem a cada classe no conjunto de K instâncias mais semelhantes para uma nova instância de dados. Por exemplo, em um problema de classificação binária (a classe é 0 ou 1):

p (classe = 0) = contagem (classe = 0) / (contagem (classe = 0) + contagem (classe = 1))

Se você está usando K e você tem um número par de classes (por exemplo, 2), é uma boa idéia escolher um valor K com um número ímpar para evitar empate. E o inverso, use um número par para K quando você tiver um número ímpar de classes.

Os empates podem ser quebrados consistentemente expandindo K por 1 e observando a classe da próxima instância mais semelhante no conjunto de dados de treinamento.

Maldição da Dimensionalidade

O KNN funciona bem com um pequeno número de variáveis ​​de entrada (p), mas luta quando o número de entradas é muito grande.

Cada variável de entrada pode ser considerada uma dimensão de um espaço de entrada p-dimensional. Por exemplo, se você tivesse duas variáveis ​​de entrada x1 e x2, o espaço de entrada seria bidimensional.

À medida que o número de dimensões aumenta, o volume do espaço de entrada aumenta a uma taxa exponencial.

Em altas dimensões, pontos que podem ser semelhantes podem ter distâncias muito grandes. Todos os pontos estarão distantes um do outro e nossa intuição para distâncias em espaços simples de 2 e 3 dimensões se rompe. Isso pode parecer não intuitivo no começo, mas esse problema geral é chamado de “ Maldição da Dimensionalidade ”.

Melhor preparação dos dados para KNN

• Rescale Data: O KNN funciona muito melhor se todos os dados tiverem a mesma escala. Normalizar seus dados para o intervalo [0, 1] é uma boa ideia. Também pode ser uma boa ideia padronizar seus dados se tiver uma distribuição gaussiana.
• Endereço de dados ausentes: Dados ausentes significam que a distância entre as amostras não pode ser calculada. Essas amostras podem ser excluídas ou os valores ausentes podem ser imputados.
• Dimensionalidade inferior: o KNN é adequado para dados dimensionais inferiores. Você pode experimentá-lo em dados de alta dimensão (centenas ou milhares de variáveis ​​de entrada), mas esteja ciente de que ele pode não funcionar tão bem quanto outras técnicas. O KNN pode se beneficiar da seleção de recursos que reduz a dimensionalidade do espaço do recurso de entrada.

Cursos:

Quer aprender mais sobre? Conheça nossos cursos!

Resumo

Neste post você descobriu o algoritmo de aprendizado de máquina KNN. Você aprendeu isso:

• O KNN armazena todo o conjunto de dados de treinamento que ele usa como sua representação.
• KNN não aprende nenhum modelo.
• A KNN faz predições just-in-time calculando a similaridade entre uma amostra de entrada e cada instância de treinamento.
• Existem muitas medidas de distância para escolher para corresponder à estrutura dos dados de entrada.
• É uma boa ideia redimensionar seus dados, como usar a normalização, ao usar o KNN.

Se você tiver alguma dúvida sobre este post ou o algoritmo KNN, pergunte nos comentários e eu farei o meu melhor para responder.