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.