Data Science, Machine Learning, Recuperação da Informação

Introdução ao Algoritmo K-Nearest Neighbour (código Python)

Dentre todos os algoritmos de aprendizado de máquina, KNN é o mais simples de aprender. Apesar da simplicidade, provou ser incrivelmente eficaz em certas tarefas (como veremos a seguir).

E mais, pode ser utilizado para problemas de classificação e regressão! É muito mais popularmente usado para problemas de classificação, no entanto, raramente vemos o KNN sendo implementado em qualquer tarefa de regressão.

O objetivo aqui é ilustrar e enfatizar como o algoritmo KNN pode ser igualmente eficaz quando a variável alvo é de natureza contínua.

Neste Post, primeiro entenderemos a intuição por trás dos algoritmos KNN, examinaremos as diferentes maneiras de calcular as distâncias entre os pontos e, finalmente, implementaremos o algoritmo em Python no conjunto de dados: Big Mart Sales. Vamos começar!

Índice

  1. Um exemplo simples para entender a intuição por trás do KNN
  2. Como funciona o algoritmo KNN?
  3. Métodos de cálculo de distância entre pontos
  4. Como escolher o fator k?
  5. Trabalhando em um conjunto de dados
  6. Recursos adicionais

 

1. Um exemplo simples para entender a intuição por trás do KNN

Vamos começar com um exemplo simples, considere a tabela a seguir – ela consiste no valor de altura, idade e peso (meta) para 10 pessoas. Como você pode ver, o valor de peso do ID11 está faltando. Precisamos prever o peso dessa pessoa com base em sua altura e idade.

Nota: Os dados nesta tabela não representam valores reais. É meramente usado como um exemplo para explicar este conceito.

Para uma compreensão mais clara disso, abaixo está o gráfico de altura versus idade da tabela acima:

No gráfico acima, o eixo y representa a altura de uma pessoa (em pés) e o eixo x representa a idade (em anos). Os pontos são numerados de acordo com os valores de ID. O ponto amarelo (ID 11) é o nosso ponto de teste.

Se eu pedir para você identificar o peso do ID11 baseado no enredo, qual seria sua resposta? Você provavelmente diria que, como o ID11 está mais próximo dos pontos 5 e 1, ele deve ter um peso semelhante a esses IDs, provavelmente entre 72 e 77 kgs (pesos de ID1 e ID5 da tabela). Isso realmente faz sentido, mas como você acha que o algoritmo prevê os valores? Nós vamos descobrir isso neste artigo.

 

2. Como funciona o algoritmo KNN?

Como vimos acima, o KNN pode ser usado para problemas de classificação e regressão. O algoritmo usa ‘ similaridade de recurso ‘ para prever valores de quaisquer novos pontos de dados. Isso significa que o novo ponto recebe um valor baseado em quão próximo ele se parece dos pontos no conjunto de treinamento. Do nosso exemplo, sabemos que o ID11 tem altura e idade semelhantes a ID1 e ID5, portanto, o peso também seria aproximadamente o mesmo.

Se tivesse sido um problema de classificação, teríamos tomado o modo como a previsão final. Neste caso, temos dois valores de peso – 72 e 77. Algum palpite de como o valor final será calculado? A média dos valores é considerada a previsão final.

Abaixo está uma explicação passo a passo do algoritmo:

  1. Primeiro, a distância entre o novo ponto e cada ponto de treinamento é calculada.

2. Os pontos de dados k mais próximos são selecionados (com base na distância). Neste exemplo, os pontos 1, 5, 6 serão selecionados se o valor de k for 3. Continuaremos a explorar o método para selecionar o valor correto de k mais adiante neste artigo.

 

3. A média desses pontos de dados é a previsão final para o novo ponto. Aqui, temos peso de ID11 = (77 + 72 + 60) / 3 = 69.66 kg.

Nas próximas seções, discutiremos cada uma dessas três etapas em detalhes.

 

3. Métodos de cálculo da distância entre os pontos

primeiro passo é calcular a distância entre o novo ponto e cada ponto de treinamento. Existem vários métodos para calcular essa distância, dos quais os métodos mais conhecidos são – Euclidiano, Manhattan (para contínuo) e distância Hamming (para categórico).

  1. 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 (y).
  2. Manhattan Distance : Esta é a distância entre vetores reais usando a soma de sua diferença absoluta.
  3. Distância de Hamming : É usada para variáveis ​​categóricas. Se o valor (x) e o valor (y) forem iguais, a distância D será igual a 0. Caso contrário, D = 1.

Uma vez que a distância de uma nova observação dos pontos do nosso conjunto de treinamento tenha sido medida, o próximo passo é escolher os pontos mais próximos. O número de pontos a serem considerados é definido pelo valor de k.

 

4. Como escolher o fator k?

segundo passo é selecionar o valor k. Isso determina o número de vizinhos que observamos quando atribuímos um valor a qualquer nova observação.

Em nosso exemplo, para um valor k = 3, os pontos mais próximos são ID1, ID5 e ID6.

A previsão de peso para ID11 será:

ID11 = (77 + 72 + 60) / 3 

ID11 = 69,66 kg

Para o valor de k = 5, o ponto mais próximo será ID1, ID4, ID5, ID6, ID10.

A previsão para ID11 será:

ID 11 = (77 + 59 + 72 + 60 + 58) / 5 

ID 11 = 65,2 kg

Notamos que, com base no valor k, o resultado final tende a mudar. Então, como podemos descobrir o valor ótimo de k? Vamos decidi-lo com base no cálculo do erro para o nosso conjunto de treinamento e validação (afinal, minimizar o erro é o nosso objetivo final!).

Dê uma olhada nos gráficos abaixo para erro de treinamento e erro de validação para valores diferentes de k.

 

Para um valor muito baixo de k (suponha k = 1), o modelo ajusta os dados de treinamento, o que leva a uma alta taxa de erro no conjunto de validação. Por outro lado, para um valor alto de k, o modelo tem um desempenho ruim no conjunto de treinamento e validação. Se observar atentamente, a curva de erro de validação atinge um mínimo com um valor de k = 9. Esse valor de k é o valor ideal do modelo (ele variará para diferentes conjuntos de dados). Essa curva é conhecida como “curva do cotovelo” ou em inglês: elbow curve (porque tem uma forma semelhante a um cotovelo) e é geralmente usada para determinar o valor de k.

Você também pode usar a técnica de pesquisa de grade para encontrar o melhor valor k. Vamos implementar isso na seção a seguir.

 

5. Trabalhar em um conjunto de dados (códigos Python)

Até agora você deve ter uma compreensão clara do algoritmo. Vamos agora avançar e implementar o algoritmo em um conjunto de dados. Eu usei o conjunto de dados de vendas do Big Mart para mostrar a implementação e você pode baixá-lo neste link .

1. Leia o arquivo

import pandas as pd
df = pd.read_csv('train.csv')
df.head()

 

2. Impute valores ausentes

df.isnull().sum()
#missing values in Item_weight and Outlet_size needs to be imputed
mean = df['Item_Weight'].mean() #imputing item_weight with mean
df['Item_Weight'].fillna(mean, inplace =True)

mode = df['Outlet_Size'].mode() #imputing outlet size with mode
df['Outlet_Size'].fillna(mode[0], inplace =True)

 

3. Lidar com variáveis ​​categóricas e descartar as colunas de id

df.drop(['Item_Identifier', 'Outlet_Identifier'], axis=1, inplace=True)
df = pd.get_dummies(df)

 

4. Criar conjunto de trem e teste

from sklearn.model_selection import train_test_split
train , test = train_test_split(df, test_size = 0.3)

x_train = train.drop('Item_Outlet_Sales', axis=1)
y_train = train['Item_Outlet_Sales']

x_test = test.drop('Item_Outlet_Sales', axis = 1)
y_test = test['Item_Outlet_Sales']

5. Pré-processamento – Redimensionando os recursos

from sklearn.preprocessing import MinMaxScaler
scaler = MinMaxScaler(feature_range=(0, 1))

x_train_scaled = scaler.fit_transform(x_train)
x_train = pd.DataFrame(x_train_scaled)

x_test_scaled = scaler.fit_transform(x_test)
x_test = pd.DataFrame(x_test_scaled)

 

6. Vamos dar uma olhada na taxa de erro para diferentes valores de k

#import required packages
from sklearn import neighbors
from sklearn.metrics import mean_squared_error 
from math import sqrt
import matplotlib.pyplot as plt
%matplotlib inline
rmse_val = [] #to store rmse values for different k
for K in range(20):
    K = K+1
    model = neighbors.KNeighborsRegressor(n_neighbors = K)

    model.fit(x_train, y_train)  #fit the model
    pred=model.predict(x_test) #make prediction on test set
    error = sqrt(mean_squared_error(y_test,pred)) #calculate rmse
    rmse_val.append(error) #store rmse values
    print('RMSE value for k= ' , K , 'is:', error)

Saída:

RMSE value for k = 1 is: 1579.8352322344945
RMSE value for k = 2 is: 1362.7748806138618
RMSE value for k = 3 is: 1278.868577489459
RMSE value for k = 4 is: 1249.338516122638
RMSE value for k = 5 is: 1235.4514224035129
RMSE value for k = 6 is: 1233.2711649472913
RMSE value for k = 7 is: 1219.0633086651026
RMSE value for k = 8 is: 1222.244674933665
RMSE value for k = 9 is: 1219.5895059285074
RMSE value for k = 10 is: 1225.106137547365
RMSE value for k = 11 is: 1229.540283771085
RMSE value for k = 12 is: 1239.1504407152086
RMSE value for k = 13 is: 1242.3726040709887
RMSE value for k = 14 is: 1251.505810196545
RMSE value for k = 15 is: 1253.190119191363
RMSE value for k = 16 is: 1258.802262564038
RMSE value for k = 17 is: 1260.884931441893
RMSE value for k = 18 is: 1265.5133661294733
RMSE value for k = 19 is: 1269.619416217394
RMSE value for k = 20 is: 1272.10881411344
#plotting the rmse values against k values
curve = pd.DataFrame(rmse_val) #elbow curve 
curve.plot()

Como discutimos, quando tomamos k = 1, obtemos um valor RMSE muito alto. O valor RMSE diminui à medida que aumentamos o valor k. Em k = 7, o RMSE é aproximadamente 1219,06 e dispara aumentando ainda mais o valor k. Podemos dizer com segurança que k = 7 nos dará o melhor resultado neste caso.

Estas são as previsões usando nosso conjunto de dados de treinamento. Vamos agora prever os valores para o conjunto de dados de teste e fazer um envio.

7. Previsões sobre o conjunto de dados de teste

#reading test and submission files
test = pd.read_csv('test.csv')
submission = pd.read_csv('SampleSubmission.csv')
submission['Item_Identifier'] = test['Item_Identifier']
submission['Outlet_Identifier'] = test['Outlet_Identifier']

#preprocessing test dataset
test.drop(['Item_Identifier', 'Outlet_Identifier'], axis=1, inplace=True)
test['Item_Weight'].fillna(mean, inplace =True)
test = pd.get_dummies(test)
test_scaled = scaler.fit_transform(test)
test = pd.DataFrame(test_scaled)

#predicting on the test set and creating submission file
predict = model.predict(test)
submission['Item_Outlet_Sales'] = predict
submission.to_csv('submit_file.csv',index=False)

Ao enviar este arquivo, recebo um RMSE de 1279.5159651297.

8. Implementando o GridsearchCV 

Para decidir o valor de k, plotar a curva do cotovelo toda vez é um processo complicado e tedioso. Você pode simplesmente usar gridsearch para encontrar o melhor valor.

from sklearn.model_selection import GridSearchCV
params = {'n_neighbors':[2,3,4,5,6,7,8,9]}

knn = neighbors.KNeighborsRegressor()

model = GridSearchCV(knn, params, cv=5)
model.fit(x_train,y_train)
model.best_params_

Saída:

{'n_neighbors': 7}

 

6. Notas finais e recursos adicionais

Neste artigo originalmente escrito por AISHWARYA SINGH, foi abordado o funcionamento do algoritmo KNN e sua implementação em Python. É uma das técnicas de aprendizado de máquina mais básicas, porém eficazes. Para a implementação KNN em R, você pode passar por este artigo: kNN Algoritmo usando R .

Foi utilizado o modelo KNN diretamente da biblioteca sklearn . Você também pode implementar o KNN do zero (eu recomendo isso!), que é abordado detalhadamente neste artigo: KNN simplificado .

Se você acha que conhece bem a KNN e tem uma sólida compreensão sobre a técnica, teste suas habilidades neste teste de MCQ:  30 perguntas sobre o algoritmo kNN . Boa sorte!

Todos os direitos reservados ao Autor: AISHWARYA SINGH (link)
Traduzido e adaptado por Alex Souza

Um comentário sobre “Introdução ao Algoritmo K-Nearest Neighbour (código Python)

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s