KNN —K-Nearest Neighbor, o que é?
Para quem estuda ciência dos dados, provavelmente se deparou com um KNN em sua vida né? Nos mais clássicos dataset, utilizando como baseline para comparar com um modelo mais complexo…quem nunca? Mas você conhece o verdadeiro potencial desse algoritmo?
Esse artigo tem como objetivo demonstrar mais um vez e com o meu olhar o que é um KNN e como usá-lo, além das suas vantagens e desvantagens. Demonstrarei o algoritmo em python e R, deixando no meu repositório do github para consultas.
O algoritmo KNN assume que coisas semelhantes existem nas proximidades. Em outras palavras, coisas semelhantes estão próximas umas das outras.
Mas como calcula a proximidade de uma N dimensão? Existem várias técnicas para o cálculo da distância, irei descrever algumas:
- Euclidean
- Hamming
- Manhattan
- Mahalanobis
- Minkowski
A mais utilizada é a distância Euclidiana, e uma ótima maneira de explicar ela é utilizar a distância Manhattan para exemplificar a diferença entre elas.
A distância euclidiana representa a distância mais curta entre dois pontos. A distância de Manhattan é a soma das diferenças absolutas entre os pontos em todas as dimensões.
A distância de Hamming calcula a distância entre dois vetores binários. Essa técnica acaba sendo uma boa opção para casos de variáveis categóricas (one-hot).
A distância de Mahalanobis é a distância entre dois pontos no espaço multivariado. Em caso de variáveis não correlacionadas a distância Euclidiana acaba resultando a mesma coisa que a distância Mahalanobis. Porém quando temos mais de duas variáveis correlacionadas, pode se tornar impossível traçar a distância entre eles com um única reta.
x — vetor da variável observação
m — vetor da média das variáveis independentes
C — covariância das variáveis independetes
E quais são seus pontos fortes e pontos fracos?
Pontos fortes
- É extremamente fácil de implementar
- Um algoritmo de aprendizado lento (lazy learning), portanto, não requer nenhum treinamento antes de fazer previsões. Isso torna o algoritmo KNN muito mais rápido do que outros algoritmos que requerem treinamento, por exemplo, SVM, regressão linear…
- Inserção de novos dados na série de maneira instantânea, já que não é necessário treinar
- Existem apenas dois parâmetros necessários para implementar KNN, ou seja, o valor de K e a função de distância (por exemplo, Euclidiano ou Manhattan etc.)
Pontos fracos
- O algoritmo KNN não funciona bem com dados dimensionais elevados porque, com grande números de variáveis, torna-se difícel aprender com ca distância de cada dimensão
- Alto custo de previsão para grandes conjuntos de dados
- Baixa performance com variáveis categóricas explicativas
Como funciona o KNN para variáveis contínuas e categoricas?
Os dois métodos são relacionais, utilizam o mesmo princípio do K vizinhos. Para melhorar o entendimento, vamos supor que no problema em questão tenhamos 6 vizinhos mais próximos, nos valores [1, 3, 0, 0, 2, 0]. Onde o 0 = muita fome, 1 = fome, 2 = pouca fome, 3 = sem fome.
O que aconcete quando aplicamos KNN categórico é o arrendondamento pela maioria dos output, já para o KNN de variáveis contínuas são todos os valores reais possíveis do intervalo [0:5]. Então no KNN categórico é para se esperar valores como 0 e no KNN regressor poderia ser 0,7.
Além dos modelos supervisionados, o KNN nos permite usufruir de modelos não superfisionados, utilizando a mesma técnica de pontos mais próximos na formação de clusters. Além de técnicas de redução de dimensionalidade, conhecida como NCA (Neighborhood Component Analysis).
Hiperparâmetros do KNN
Geralmente nas bibliotecas do python e R, existe um conjunto de hiperparâmetros que podem ser ajustados, contudo o único que não tem valor default é o N-neighbourd. Porém, acho importante ter conhecimento de outros afim de potencializar a performance do KNN.
- N-neighbourd > número de vizinhos a serem considerados
- Algoritmo > A opções ‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’ são algoritmos disponíveis para calcular o vizinho mais próximo. A opção ’auto’ deixa a cargo do algoritmo escolher qual tecnica é a mais adequada para aquele determinado problema, olhando para o resultado obtido nas observações anteriores. Já o algoritmo ’ball_tree’, é aconselhável utilizar para problemas com grande número de dimensões, diferente do ‘kd_tree’. Em contrapartida, o custo computacional é maior. A vantage do ‘kd_tree’ é em cima do ‘brute’ em problemas BigData com muitas observações, já que ele utiliza o conhecimento prévio adquirido das distâncias anteriores para inferir. A ideia básica é que se o ponto A está muito distante do ponto B e o ponto B está muito próximo do ponto C, então sabemos que os pontos A — C estão muito distantes, sem ter que calcular explicitamente sua distância. E por fim, ’brute’ calcula a distância de todos os pontos possíveis.
- Leaf size > Quanto maior, mais rápido será o processamento pois os grupos de amostras serão grande o suficiente para formação de poucos nós. O momento que você precisa se preocupar com esse parâmetro é quando o conjunto de dados é muito grande e o algoritmo escolhido for ’brute’. Seu valor de amostra default é 30.
- p > 1 ativa a utilização da distância de Manhattan e 2 da distância Euclidiana. Caso não seja inserido nenhum input, distância de minkowski será ativada que é a generalização das distâncias de Manhattan e Euclidiana.
- Metric > Esse parâmetro escolhemos o tipo de distância que mais se adequa para o problema em questão. O site do scikit-learn tem ótimas tabelas para ilustrar as medidas de distância e o tipo de problema que são utilizadas.
- Weight > é o inverso da distância que pode ser configurado de três maneiras: ‘uniform’, ‘distance’ e callable. Uniform usa o mesmo pedo para todas os vizinhos. Distance já atribui pesos maiores para os vizinhos mais próximos. Por fim, callable você incorpora uma função em específico.
A teoria é essa, vamos para prática! KNN suporta problemas de classificação e regressão, portanto iremos passar em cada separadamente.
Detetecção de anomalia com KNN
Released soon
Análise Churn de cliente com KNN
Released soon
