Introdução ao KNN

O objetivo aqui é mostrar noções básicas de machine learning, mais especificamente mostrar como utilizar o algoritmo KNN no software R. Não será abordado aqui os detalhes matemáticos, mas se quiser saber mais sobre isso será muito legal trocar ideias sobreo o assunto. Se quiser mais detalhes sobre machine learning há o excelente livro “Statistical Learning” do Trevor Hastie.

O algoritmo KNN ou k-vizinhos mais próximos é um algoritmo bem simples de machine learning. Ele usa algum tipo de medida de similaridade para dizer em qual classe o novo dado se classifica. Essa medida de similaridade é normalmente uma medida de distância como a distância Euclidiana (obrigado Pitágoras!) ou a distância de Manhattan(métrica do táxi) por exemplo. Existe todo uma área da matemática que estuda o conceito de distância de forma mais geral, caso tenha interesse e realmente gostar de matemática pode consultar/estudar o excelente livro do saudoso prof. Elon Lages Lima chamado “Espaços Métricos” da editora IMPA. Agora se tiver interessado na matemática e nos algoritmos de machine learning e além disso as aplicações no R você poderá consultar, como eu disse antes , o também excelente livro “Statistical Learning” do Trevor Hastie.

Livro:

Abordagem:

Para ver como o KNN funciona e como usar no R será utilizada a seguinte sequência:

Problemas que pode-se usar o KNN

O KNN é usado numa extensa variedade de aplicações como finanças, saúde, ciência política, detecção de manuscritos, reconhecimento de imagem e reconhecimento de vídeo.

Por exemplo,no desembolso de empréstimos, os institutos bancários irão prever se o empréstimo é seguro ou arriscado. Na ciência política, classificar eleitores em potencial em duas classes votará ou não votará. Na saúde dado os sintomas do paciente na base de dados o algoritmo pode classificá-lo em doente ou não doente.

Quando usar o algoritmo KNN?

O KNN pode ser usado para problemas preditivos de classificação(saída discreta) e regressão(saída contínua). No entanto, parece ser mais utilizado em problemas de classificação.

Como funciona o algoritmo KNN?

No KNN, K é o número de vizinhos mais próximos. O número de vizinhos é o principal fator decisivo. Quando K = 1, o algoritmo é conhecido como o algoritmo do vizinho mais próximo. Este é o caso mais simples. Suponha a situação abaixo e P( que aparece como interrogação), seja a classe(ou rótulo) que se quer prever. Primeiro, você encontra o ponto mais próximo de P e depois o rótulo desse ponto mais próximo. P terá a mesma classificação do seuvizinho mais próximo. No exemplo abaixo será classificado como estrela vermelha.

Se k > 1 a classe a ser escolhida é pela maioria dos vizinhos mais próximos. Se caso houver impate pode ser feito um sorteio aleatório para escolher qual classe o novo rótulo será classificado.

Adquirindo dados

Vamos aplicar a abordagem KNN ao conjunto de dados Caravan, que faz parte da biblioteca ISLR. Esse conjunto de dados inclui 86 variáveis onde há dados sociodemográficos (variáveis nas colunas de 1-43) e propriedade do produto (variáveis nas colunas de 44-86)

A variável de resposta é Compra( variável 86), que indica se um determinado indivíduo compra ou não uma apólice de seguro de Caravan. Neste conjunto de dados, apenas 6% das pessoas adquiriram seguro da caravana.

Vamos verificar a estrutura desses dados

library(ISLR)
library(dplyr)
glimpse(Caravan)
## Observations: 5,822
## Variables: 86
## $ MOSTYPE  <dbl> 33, 37, 37, 9, 40, 23, 39, 33, 33, 11, 10, 9, 33, 41,...
## $ MAANTHUI <dbl> 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2,...
## $ MGEMOMV  <dbl> 3, 2, 2, 3, 4, 2, 3, 2, 2, 3, 4, 3, 2, 3, 1, 2, 2, 3,...
## $ MGEMLEEF <dbl> 2, 2, 2, 3, 2, 1, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 3, 3,...
## $ MOSHOOFD <dbl> 8, 8, 8, 3, 10, 5, 9, 8, 8, 3, 3, 3, 8, 10, 5, 8, 9, ...
## $ MGODRK   <dbl> 0, 1, 0, 2, 1, 0, 2, 0, 0, 3, 1, 1, 1, 0, 0, 0, 0, 0,...
## $ MGODPR   <dbl> 5, 4, 4, 3, 4, 5, 2, 7, 1, 5, 4, 3, 4, 5, 6, 7, 6, 5,...
## $ MGODOV   <dbl> 1, 1, 2, 2, 1, 0, 0, 0, 3, 0, 1, 2, 1, 0, 1, 0, 0, 0,...
## $ MGODGE   <dbl> 3, 4, 4, 4, 4, 5, 5, 2, 6, 2, 4, 4, 4, 4, 2, 2, 3, 4,...
## $ MRELGE   <dbl> 7, 6, 3, 5, 7, 0, 7, 7, 6, 7, 7, 7, 6, 7, 1, 7, 7, 7,...
## $ MRELSA   <dbl> 0, 2, 2, 2, 1, 6, 2, 2, 0, 0, 1, 1, 2, 1, 2, 2, 0, 0,...
## $ MRELOV   <dbl> 2, 2, 4, 2, 2, 3, 0, 0, 3, 2, 2, 2, 3, 1, 6, 0, 2, 2,...
## $ MFALLEEN <dbl> 1, 0, 4, 2, 2, 3, 0, 0, 3, 2, 0, 2, 3, 1, 5, 0, 0, 0,...
## $ MFGEKIND <dbl> 2, 4, 4, 3, 4, 5, 3, 5, 3, 2, 3, 3, 4, 4, 3, 5, 6, 2,...
## $ MFWEKIND <dbl> 6, 5, 2, 4, 4, 2, 6, 4, 3, 6, 6, 5, 3, 5, 1, 4, 3, 7,...
## $ MOPLHOOG <dbl> 1, 0, 0, 3, 5, 0, 0, 0, 0, 0, 4, 1, 1, 2, 2, 0, 2, 2,...
## $ MOPLMIDD <dbl> 2, 5, 5, 4, 4, 5, 4, 3, 1, 4, 3, 7, 4, 4, 6, 3, 6, 1,...
## $ MOPLLAAG <dbl> 7, 4, 4, 2, 0, 4, 5, 6, 8, 5, 3, 1, 5, 4, 2, 6, 2, 7,...
## $ MBERHOOG <dbl> 1, 0, 0, 4, 0, 2, 0, 2, 1, 2, 0, 4, 1, 3, 1, 2, 2, 0,...
## $ MBERZELF <dbl> 0, 0, 0, 0, 5, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 2,...
## $ MBERBOER <dbl> 1, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,...
## $ MBERMIDD <dbl> 2, 5, 7, 3, 0, 4, 4, 2, 1, 3, 9, 5, 3, 2, 4, 2, 4, 1,...
## $ MBERARBG <dbl> 5, 0, 0, 1, 0, 2, 1, 5, 8, 3, 0, 1, 2, 2, 3, 5, 0, 1,...
## $ MBERARBO <dbl> 2, 4, 2, 2, 0, 2, 5, 2, 1, 3, 0, 1, 4, 2, 2, 2, 4, 5,...
## $ MSKA     <dbl> 1, 0, 0, 3, 9, 2, 0, 2, 1, 1, 3, 2, 1, 4, 1, 2, 2, 2,...
## $ MSKB1    <dbl> 1, 2, 5, 2, 0, 2, 1, 1, 1, 2, 0, 3, 2, 2, 3, 1, 2, 0,...
## $ MSKB2    <dbl> 2, 3, 0, 1, 0, 2, 4, 2, 0, 1, 6, 4, 2, 1, 2, 2, 4, 0,...
## $ MSKC     <dbl> 6, 5, 4, 4, 0, 4, 5, 5, 8, 4, 0, 1, 5, 4, 4, 5, 2, 7,...
## $ MSKD     <dbl> 1, 0, 0, 0, 0, 2, 0, 2, 1, 2, 0, 0, 1, 0, 0, 2, 0, 0,...
## $ MHHUUR   <dbl> 1, 2, 7, 5, 4, 9, 6, 0, 9, 0, 0, 6, 5, 5, 9, 0, 6, 4,...
## $ MHKOOP   <dbl> 8, 7, 2, 4, 5, 0, 3, 9, 0, 9, 9, 3, 4, 4, 0, 9, 3, 5,...
## $ MAUT1    <dbl> 8, 7, 7, 9, 6, 5, 8, 4, 5, 6, 6, 7, 6, 7, 5, 4, 7, 6,...
## $ MAUT2    <dbl> 0, 1, 0, 0, 2, 3, 0, 4, 2, 1, 2, 1, 1, 2, 1, 4, 2, 1,...
## $ MAUT0    <dbl> 1, 2, 2, 0, 1, 3, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 0, 2,...
## $ MZFONDS  <dbl> 8, 6, 9, 7, 5, 9, 9, 6, 7, 6, 5, 4, 7, 8, 5, 6, 4, 7,...
## $ MZPART   <dbl> 1, 3, 0, 2, 4, 0, 0, 3, 2, 3, 4, 5, 2, 1, 4, 3, 5, 2,...
## $ MINKM30  <dbl> 0, 2, 4, 1, 0, 5, 4, 2, 7, 2, 0, 3, 3, 3, 4, 2, 0, 0,...
## $ MINK3045 <dbl> 4, 0, 5, 5, 0, 2, 3, 5, 2, 3, 3, 4, 4, 2, 3, 5, 1, 6,...
## $ MINK4575 <dbl> 5, 5, 0, 3, 9, 3, 3, 3, 1, 3, 2, 3, 3, 4, 3, 3, 6, 3,...
## $ MINK7512 <dbl> 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 1, 0, 0, 2, 0,...
## $ MINK123M <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0,...
## $ MINKGEM  <dbl> 4, 5, 3, 4, 6, 3, 3, 3, 2, 4, 8, 3, 3, 4, 3, 3, 5, 4,...
## $ MKOOPKLA <dbl> 3, 4, 4, 4, 3, 3, 5, 3, 3, 7, 7, 4, 3, 4, 3, 3, 4, 2,...
## $ PWAPART  <dbl> 0, 2, 2, 0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 2, 2, 0, 2,...
## $ PWABEDR  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PWALAND  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PPERSAUT <dbl> 6, 0, 6, 6, 0, 6, 6, 0, 5, 0, 6, 5, 6, 0, 5, 0, 0, 6,...
## $ PBESAUT  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PMOTSCO  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PVRAAUT  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PAANHANG <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PTRACTOR <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PWERKT   <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PBROM    <dbl> 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PLEVEN   <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PPERSONG <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PGEZONG  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PWAOREG  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PBRAND   <dbl> 5, 2, 2, 2, 6, 0, 0, 0, 0, 3, 0, 2, 0, 0, 2, 4, 0, 3,...
## $ PZEILPL  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PPLEZIER <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PFIETS   <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PINBOED  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ PBYSTAND <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AWAPART  <dbl> 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1,...
## $ AWABEDR  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AWALAND  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ APERSAUT <dbl> 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1,...
## $ ABESAUT  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AMOTSCO  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AVRAAUT  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AAANHANG <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ ATRACTOR <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AWERKT   <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ ABROM    <dbl> 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ ALEVEN   <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ APERSONG <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AGEZONG  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AWAOREG  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ ABRAND   <dbl> 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1,...
## $ AZEILPL  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ APLEZIER <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AFIETS   <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ AINBOED  <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ ABYSTAND <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...
## $ Purchase <fct> No, No, No, No, No, No, No, No, No, No, No, No, No, N...

Foi afirmado que no conjunto de dados, apenas 6% das pessoas compraram apólice de seguro Caravan.

Veja:

table(Caravan$Purchase)/nrow(Caravan)
## 
##         No        Yes 
## 0.94022673 0.05977327

Verificado!

Limpeza de dados

Para verificar se há algum dado faltante basta aplicar o código abaixo:

any(is.na(Caravan))
## [1] FALSE

Perceba que resultou em “False”, logo não há dado faltante.

Preparação dos dados

Cada algoritmo de Machine Learning usado recebe os dados de uma forma, portanto os dados devem ser preparados para serem imputados no algoritmo. Além disso pode-se fazer transformações nos dados para que o algoritmo atue de forma mais performática. No caso do Knn, que é baseado em distância faz-se necessário colocar os dados numa mesma escala. Isso se deve ao fato de que quaisquer variáveis que estiverem em escala muito alta terão um efeito muito maior na distância entre as observações e, portanto, no classificador KNN, do que as variáveis que estão em pequena escala, enviesando assim nossos resultados.

Para dar um exemplo vamos verificar a variância de duas variáveis preditoras

var(Caravan[,1])
## [1] 165.0378
var(Caravan[,2])
## [1] 0.1647078

Claramente as escalas são diferentes! Vamos agora usar a função scale em todas as variáveis preditoras exceto a variavel Purchase(Compra) para colocá-las numa mesma escala:

Caravan[,1:85]<- scale(Caravan[,1:85])

Vamos checar a variancia novamente:

var(Caravan[,1])
## [1] 1
# Standarize the dataset using "scale()" R function
var(Caravan[,2])
## [1] 1

Agora que os dados estão numa mesma escala, o conjunto de dados será dividido em teste e treinamento.

# dados de treinamento e teste
library(caTools)
set.seed(1)
divisao <- sample.split(Caravan$MOSTYPE, SplitRatio = 0.75)
#test.index <- 1:1000
Caravan_treinamento <- subset(Caravan, divisao==TRUE) #treinamento
Caravan_teste <- subset(Caravan, divisao==FALSE) # teste

Usando knn

Lembre-se de que o objetivo é elaborar um modelo para prever se alguém comprará ou não. Será usado a função knn () para isso faz-se necessário especificar 4 de seus argumentos. No primeiro argumento é colocado os dados de treinamento(sem a variábel resposta) , o segundo argumento o conjunto de dados de teste (novamente sem variável resposta), o terceiro argumento a coluna com os dados da variável resposta no conjunto de treinamento e o quarto argumento é o k (quantos vizinhos). A função knn () retorna um vetor de Ys previstos.

Começando com k = 1:

library(class)

set.seed(1)
previsoes <- knn(train = Caravan_treinamento[,-86], test= Caravan_teste[,-86],cl= Caravan_treinamento[,86],k=1)
head(previsoes)
## [1] No  No  Yes No  No  No 
## Levels: No Yes

Avaliando o modelo e taxa de erro( % de classificação errada):

mean(Caravan_teste[,86] != previsoes)
## [1] 0.1175258

Observe que com k=1 obteve-se 12% de erro.

Escolhendo valor de k

Mudando o k, para k=5:

previsoes <- knn(train = Caravan_treinamento[,-86], test= Caravan_teste[,-86],cl= Caravan_treinamento[,86],k=7)
mean(Caravan_teste[,86] != previsoes)
## [1] 0.06185567

Obteve-se 6% de erro.

No lugar de ficar “chutando” valores,pode-se automatizar o processo com um loop. Uma forma de fazer isso é a seguinte:

library(class)
previsoes = NULL
perc.erro = NULL

for(i in 1:20){
    set.seed(1)
    previsoes = knn(train = Caravan_treinamento[,-86], test= Caravan_teste[,-86],cl= Caravan_treinamento[,86],k=i)
    perc.erro[i] =mean(Caravan_teste[,86] != previsoes)
}

Perceba que o loop acima cria a variável perc.erro que armazena os erros de previsão para valores de k de 1 até 20.

Veja:

print(perc.erro)
##  [1] 0.11752577 0.11752577 0.07353952 0.07560137 0.06735395 0.06391753
##  [7] 0.06185567 0.06048110 0.06116838 0.05979381 0.06048110 0.06048110
## [13] 0.06116838 0.06116838 0.06116838 0.06116838 0.06116838 0.06116838
## [19] 0.06116838 0.06116838

Quando colocado num gráfico k x perc.erro fica melhor a visualização:

library(ggplot2)

k.values <- 1:20
error.df <- data.frame(perc.erro,k.values)


ggplot(error.df,aes(x=k.values,y=perc.erro)) + geom_point()+ geom_line(lty="dotted",color='red')

Observe que para k=10 teve-se o menor erro global

Depois de olhar o erro global ainda seria interessante analisar a matriz de confusão já que na base atual 6% das pessoas apenas compraram apólice de seguro Caravan, dificultando a acurácia na previsão de compradores. Mas isso fica para uma outra oportunidade quando for tratado sobre esse assunto específico.

Era isso que eu queria mostrar. Espero que eu tenha conseguido passar um pouco da ideia de Machine Learning, do Knn e de sua aplicação via R!

Keep calm and analysing data!