Classificação usando kNN

O nome k-NN vem de “k-Nearest Neighbor” (k-ésimo vizinho mais próximo), ou seja, esse método de machine learning tem como objetivo classificar x_t atribuindo a ele o rótulo representado mais frequentemente dentre as k amostras mais próximas e utilizando um esquema de votação. O que determina essa “proximidade entre vizinhos” é uma distância calculada entre pontos em um espaço euclidiano (instâncias), cujas fórmulas mais comuns são a distância Euclidiana e a distância Manhattan.

O “Center for Machine Learning and Intelligent Systems” da Universidade da Califórnia (CML-UCI) possui centenas de conjuntos de dados, disponíveis gratuitamente nesse link: UCI Machine Learning Repository. Um dos conjuntos de dados mais utilizados é o iris data set, que contém as dimensões de pétalas (protegem partes reprodutoras da planta e atraem polinizadores) e sépalas (partes semelhantes a folhas que envolvem o botão da flor) de exemplares de três espécies de flores iris. Ele contém 3 classes (Iris Setosa, Iris Versicolour e Iris Virginica) de 50 instâncias cada. Uma classe é linearmente separável das outras duas; estas últimas NÃO são separáveis linearmente entre si. Aqui, o objetivo é classificar a planta conforme quatro características físicas (em cm): comprimento da sépala, largura da sépala, comprimento da pétala e largura da pétala.

Gráfico (feito com matplotlib) ilustrando modelo classificador e instâncias com rótulos já definidos. Fonte: Brain Scribble

A figura acima ilustra a classificação usando k-NN (mapa de cores) para as instâncias com classes já informadas (pontos coloridos) considerando apenas o comprimento e largura da sépala (vermelho é virginica, verde é versicolor e azul é setosa).

Implementação em Python

Além de definir o conjunto de dados de treinamento e a métrica para calcular a distância entre os exemplos de treinamento, também deve-se definir o número de vizinhos mais próximos que serão considerados pelo algoritmo (o valor de K).

Não existe um valor único para o K (varia de acordo com a base de dados). Se K for muito pequeno, a classificação fica sensível a pontos de ruído; Se K for muito grande, a vizinhança pode incluir elementos de outras classes. Pode-se definir um valor inicial como a raiz quadrada do número de amostras e então ir chutando valores para ver qual K acerta mais, desde que K seja um número ímpar/primo.

O algoritmo k-NN consiste em, para cada nova amostra:

  1. Calcular a distância entre o exemplo desconhecido e o outros exemplos do conjunto de treinamento
  2. Identificar os K vizinhos mais próximos
  3. O rótulo da classe com mais representantes no conjunto definido no passo anterior será o escolhido (voto majoritário)

Esse algoritmo foi aplicado no script a seguir. São utilizados o “iris data set” (com 150 amostras), a distância Euclidiana como métrica e K = 13. O objetivo é classificar a classe da planta íris conforme as quatro dimensões fornecidas de suas flores. Uma parte das amostras (60%) é utilizada para fazer o treinamento e o restante serve para fazer o teste, que funciona da seguinte forma: o algoritmo faz a classificação e o resultado é comparado com seu valor de classe conhecido; se a classe prevista for a mesma que a observada, é registrado um acerto.

Como é retirada uma porcentagem dos dados para treinamento conforme a ordem das linhas, deve-se reordenar randomicamente as linhas, já que o arquivo original possui as linhas ordenadas por classe. Para isso, use o comando “cat iris.data | sort -R > iris.data2” no terminal Linux ou “random.shuffle(amostras)” logo após fechar o “for” de leitura do arquivo (nesse caso, cada vez que rodar o script os dados são rearranjado, atrapalhando outras comparações).

A saída revela o número de amostras utilizadas no treinamento, o total de testes realizados e o número de classificações acertadas (com exibição em porcentagem também):

Nota-se que o modelo do tipo k-NN, implementado para classificar o tipo de flor conforme as dimensões da sépala e da pétala, consegue estimar bem a classe de novos dados (não utilizados no treinamento).

Implementação em Python scikit-learn

A scikit-learn (de SciPy Toolkit) é uma biblioteca de aprendizado de máquina de código aberto para a linguagem de programação Python, uma extensão do SciPy desenvolvida por terceiros e distribuída separadamente. É projetada para interagir com as bibliotecas Python numéricas e científicas, como a NumPy, que suporta arrays e matrizes multidimensionais e também possui maior desempenho para realizar operações matemáticas que demandam mais processamento. Para sua instalação no Python 3 (foi utilizado Python 3.5.2), execute os seguintes comandos no terminal Linux:

Para versões mais antigas de Linux, usar “sudo apt-get install python3-setuptools && sudo easy_install3 pip” no lugar da primeira linha.

O código apresentado anteriormente pode ficar mais sucinto e eficiente usando a biblioteca sklearn.neighbors.KNeighborsClassifier da scikit-learn e seus métodos. Veja como fica o código para as mesmas condições utilizadas no script anterior:

A saída deve ser a mesma do caso anterior.

Para estudo e previsão de séries temporais, existe o kNN-TSP (k-Nearest Neighbor – Time Series Prediction). Sua ideia consiste em, considerando os últimos n registros ocorridos, encontrar as subsequências de tamanho n que apresentaram comportamentos similares no passado. Com base nas informações dessas subsequências, é realizado o cálculo do valor futuro.

Fonte: curso Machine Learning e Data Science com Python da udemy.