Machine Learning, R

Uma visão sobre o algoritmo kNN, com aplicação em R

O kNN é um dos algoritmos mais simples de Machine Learning e é uma abreviação para k-nearest neighbors (k-vizinhos mais próximos). Este algoritmo implementa o aprendizado baseado em instâncias (instance-based learning). Isso significa que a classificação de um exemplar cuja classe é desconhecida é realizada a partir da comparação desse exemplar com aqueles que possuem uma classe já conhecida.

Em outras palavras, se temos um dataset com as variáveis A, B e C e outro dataset apenas com as variáveis A e B, o algoritmo kNN pode fazer uma predição sobre as classes/valores da variável C para o segundo dataset.

O kNN pode ser utilizado para predição de classes ou valores (regressão).

Na classificação, o resultado é uma associação de classe. Um objeto é classificado pela classe mais comum entre seus vizinhos mais próximos.
Na regressão, a saída é um valor numérico. Este valor será uma medida de posição dos valores dos seus vizinhos mais próximos, por exemplo a média ou mediana.

 

Como o kNN funciona

 

Um exemplar é classificado de acordo com a maioria dos k exemplares mais próximos.

Em geral, a métrica de distância utilizada no kNN é a distância euclidiana, mas também pode-se utilizar outras métricas como a Manhattan e a Hamming.

 

Utilizando a imagem abaixo como exemplo, o ponto verde é desconhecido e queremos saber se ele pertence à classe quadrado azul ou triângulo vermelho.

Se utilizamos o algoritmo kNN com um k = 3 (círculo em linha), temos que a maioria dos exemplares dentro desta área são vermelhos (2 vermelhos contra 1 azul) e assim classificaríamos o ponto desconhecido como triângulo vermelho.

Entretanto, se utilizamos um k = 5 (círculo tracejado), a maioria dos exemplares dentro desta área são azuis (3 azuis contra 2 vermelhos) e assim classificaríamos o ponto desconhecido como quadrado azul.

 

 

 

Escolher o número de vizinhos mais próximos, ou seja, determinar o valor do parâmetro k, é o que determina a eficácia do modelo. Assim, o valor selecionado para k determinará a forma como os dados serão utilizados para generalizar os resultados do algoritmo.

De modo a evitar “empates”, o parâmetro k é, em geral, um valor ímpar.

Um grande valor de k pode reduzir a variância devido aos dados ruidosos. Porém, um k grande pode gerar um viés em sua classificação, pois padrões menores que podem vir a conter insights úteis, serão ignorados.

A animação a seguir, feita pela DataCamp, mostra os efeitos da escolha do k:

 

Mais à frente apresentarei um método para validação da performance do modelo.

 

Normalização

 

Muitas vezes temos que normalizar os nossos dados para que eles apresentem maior consistência e assim facilitem a implementação/aprendizado do kNN.

Se os valores de uma variável apresentarem uma amplitude (valor máximo – valor mínimo) muito alta, é boa prática normalizar os dados. Ou ainda, se as métricas das variáveis diferirem muito entre si. Por exemplo, se X varia de 0 a 100 e Y varia de 0 a 1.000, a influência de Y na função de distância será muito alta.

Quando você normalizar, você ajusta o intervalo de todos os recursos, de modo que as distâncias entre variáveis ​​com intervalos maiores não serão enfatizadas demais.

Existem diferentes formas para normalização, cada uma se adequa melhor à cada caso.

Um bom formato de normalização, é aplicar para cada valor x a função:

(x – min(x)) / (max(x) – min(x))

Assim, os valores das observações se convertem para um intervalo entre 0 e 1 e a sua variável estará normalizada.

 

Dados para treinamento x Dados para teste

 

Para avaliar o desempenho do seu modelo, você precisará dividir o conjunto de dados em duas partes: um conjunto de treinamento e um conjunto de testes.

O conjunto de treinamento é usado para construir o modelo e implementar o algoritmo, enquanto o conjunto de teste é usado para avaliar a eficácia do seu modelo. Utilize o conjunto de teste para tornar o seu modelo o mais eficiente possível.

A divisão de seu conjunto de dados entre conjunto teste e conjunto treinamento é disjunta: a escolha de divisão mais comum é tomar 2/3 do seu conjunto para  treinamento e o 1/3 restante para teste.

Mas atenção! Não é recomendável simplesmente fatiar o seu conjunto de dados em 2/3 para realizar a divisão treinamento/teste. Se as linhas do seu conjunto de dados estiverem organizadas por determinadas categorias de uma variável, por exemplo, se você fatiar o conjunto de dados, você irá perder muita informação útil e o poder preditivo do algoritmo será ineficiente.

Para evitar esse erro, faça a divisão do seu conjunto de dados a partir de uma amostra aleatória. Mais à frente mostro como fazer essa divisão aleatória utilizando o R.

 

Avaliando a performance do modelo

 

Um passo essencial em Machine Learning é a avaliação do desempenho do seu modelo. Em outras palavras, você deseja analisar o grau de correção das previsões do modelo.

Se o seu conjunto de dados não for muito grande, você pode fazer essa avaliação comparando se cada resultado da predição feita pelo algoritmo está de acordo com o valor real, disponível no conjunto teste.

Para uma avaliação mais analítica, você pode utilizar tabelas de contingência (ou tabelas cruzadas). Estas tabelas são muito utilizadas para entender a relação entre 2 variáveis, que no caso serão as variáveis do resultado do algoritmo e do conjunto teste.

 

Implementação do algoritmo em R

 

Para exemplificar a implementação do kNN, utilizarei um dataset clássico do RStudio e que é muito utilizado para fins didáticos em análise de dados e Machine Learning.

O dataset se chama iris, se trata de um estudo sobre flores e é composto por 150 observações (linhas) e 5 variáveis (colunas), que são:

  • Sepal.Length: comprimento da sépala
  • Sepal.Width: largura da sépala
  • Petal.Length: comprimento da pétala
  • Petal.Width: largura da pétala
  • Species: espécie da flor (Versicolor, Setosa ou Virginica)

Existem 50 observações para cada uma das três espécies.

 

Nosso caso aqui será o de construir um modelo kNN que prevê a espécie (Species) da flor, tomando como parâmetros apenas as variáveis numéricas do conjunto.

O dataset já vem dentro do RStudio, você pode ver o conjunto de dados executando-o pelo seu nome ou importando do repositório UCI.

# Abrindo pelo RStudio:

iris  

# Importando da UCI:

iris <- read.csv(url(“http://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data”), header = FALSE)

names(iris) <- c(“Sepal.Length”, “Sepal.Width”, “Petal.Length”, “Petal.Width”, “Species”)

 

Apenas para ter uma visão do comportamento das variáveis, segue o código para o gráfico de dispersão categorizado pelas espécies:

library(tidyverse)

iris %>%
    ggplot(aes(x = Sepal.Length, y = Sepal.Width, colour = Species))+
    geom_point()

iris %>%
   ggplot(aes(x = Petal.Length, y = Petal.Width, colour = Species))+
   geom_point()

 

 

 

Em um caso real, seria importante realizar uma análise exploratório do conjunto de dados a fim de observar melhor o comportamento das variáveis e a relação entre elas. Uma análise de correlação seria muito interessante aqui, mas vou manter o foco apenas para a implementação do kNN.

Abaixo segue o código para a criação da função para normalização e a sua aplicação em todas as linhas do conjunto de dados:

# Construindo função normalizar:
normalizar <- function(x) {
     num <- x – min(x)
     denom <- max(x) – min(x)
     return (num/denom)
}

# aplicando a função normalizar para as variáveis numéricas
iris_norm <- as.data.frame(lapply(iris[1:4], normalizar))

# Obtendo um resumo do novo dataset
summary(iris_norm)

 

Para aplicar o kNN, neste caso específico, não utilizarei os dados normalizados.

Abaixo segue o código para dividir o conjunto de dados em conjunto treinamento e conjunto teste, via amostra aleatória, na proporção 2/3 e 1/3 respectivamente:

# Construindo um indicador para amostra aleatória:
set.seed(1234)

ind <- sample(2, nrow(iris), replace=TRUE, prob=c(0.67, 0.33))

# Construindo o conjunto de treinamento:
iris.treinamento <- iris[ind==1, 1:4]

# Construindo o conjunto de treinamento:
iris.test <- iris[ind==2, 1:4]

# Inspecionando os conjuntos:
head(iris.treinamento)
head(iris.test)

 

Perceba que os conjuntos treinamento e teste possuem apenas os valores numéricos e não mais a variável Species, que é justamento o que queremos prever.

Logo, vamos criar um vetor que contenha as observações da variável Species para os conjuntos treinamento e teste:

# Criando o vetor com os nomes(labels) para o conjunto treinamento
iris.trainLabels <- iris[ind==1,5]

# Criando o vetor com os nomes(labels) para o conjunto teste
iris.testLabels <- iris[ind==2, 5]

# Inspecionando o resultado
print(iris.trainLabels)
print(iris.testLabels)

 

Temos agora tudo o que é necessário para construir o modelo, executando a função knn(), disponível no pacote class.

Vamos utilizar aqui um k = 3.

# Instale e carregue o pacote class:
# install.packages(“class”)
library(class)

# Veja mais detalhes sobre a função knn:
?knn

# Construindo o modelo
iris_pred <- knn(train = iris.treinamento, test = iris.test, cl = iris.trainLabels, k=3)

# Inspecionando `iris_pred`
iris_pred

Veja acima que o retorno da função knn() são as espécies predizidas para o conjunto teste.

Nosso último passo é validar a performance do nosso modelo.

De maneira rudimentar, você pode fazer esta validação verificando se cada observação do resultado do modelo (variável iris_pred) fez a predição correta, ou seja, se é igual à classe do conjunto teste (variável iris.testLabels).

Mas vamos fazer esta validação de uma forma mais eficiente, utilizando a função de tabela cruzada, CrossTable(), disponível no pacote gmodels:

# Instale e carregue o pacote gmodels:
# install.packages(“gmodels”)
library(gmodels)

# Construindo a tabela:
CrossTable(x = iris.testLabels, y = iris_pred, prop.chisq=FALSE)

Da tabela acima, lemos que nosso modelo fez apenas uma previsão errada: para uma observação de espécie virginica, o modelo prediziu que era de espécie versicolor.

Para todas as outras 39 observações do conjunto teste, o nosso modelo fez a previsão correta. Poderíamos concluir que a performance do modelo é bastante satisfatória.

Este foi um exemplo simples, então não tivemos que trabalhar muito no modelo. Mas na prática, aumentar a performance do modelo implica em normalizar os dados, verificar o resultado para diferentes valores para k e testar diferentes formas de manipulação estatística, de modo a construir o modelo mais eficaz possível.

Abaixo segue todo o código utilizado neste artigo:

# Abrindo pelo RStudio:

iris  

# Importando da UCI:

iris <- read.csv(url("http://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data"), header = FALSE)

names(iris) <- c("Sepal.Length", "Sepal.Width", "Petal.Length", "Petal.Width", "Species")

# Visualizando os dados:

library(tidyverse)

iris %>% 
  ggplot(aes(x = Sepal.Length, y = Sepal.Width, colour = Species))+
  geom_point()

iris %>% 
  ggplot(aes(x = Petal.Length, y = Petal.Width, colour = Species))+
  geom_point()

# Construindo função normalizar:
normalizar <- function(x) {
  num <- x - min(x)
  denom <- max(x) - min(x)
  return (num/denom)
}

# aplicando a função normalizar para as variáveis numéricas
iris_norm <- as.data.frame(lapply(iris[1:4], normalizar))

# Obtendo um resumo do novo dataset
summary(iris_norm)

# Construindo um indicador para amostra aleatória:
set.seed(1234)

ind <- sample(2, nrow(iris), replace=TRUE, prob=c(0.67, 0.33))

# Construindo o conjunto de treinamento:
iris.treinamento <- iris[ind==1, 1:4]

# Construindo o conjunto de treinamento:
iris.test <- iris[ind==2, 1:4]

# Inspecionando os conjuntos:
head(iris.treinamento)
head(iris.test)

# Criando o vetor com os nomes(labels) para o conjunto treinamento
iris.trainLabels <- iris[ind==1,5]

# Criando o vetor com os nomes(labels) para o conjunto teste
iris.testLabels <- iris[ind==2, 5]

# Inspecionando o resultado
print(iris.trainLabels)
print(iris.testLabels)

# Instale e carregue o pacote class:
# install.packages("class")
library(class)

# Veja mais detalhes sobre a função knn:
?knn

# Construindo o modelo
iris_pred <- knn(train = iris.treinamento, test = iris.test, cl = iris.trainLabels, k=3)

# Inspecionando `iris_pred`
iris_pred

# Instale e carregue o pacote gmodels:
# install.packages("gmodels")
library(gmodels)

# Construindo a tabela:
CrossTable(x = iris.testLabels, y = iris_pred, prop.chisq=FALSE)

 


Espero que este artigo tenha sido útil para você e que possa usufruir do conhecimento aqui compartilhado.

Caso tenha qualquer comentário, sugestão, crítica ou dúvida, utilize o espaço para comentários abaixo.

Até a próxima!