Classificador K-Nearest Neighbors (ou KNN)

É um dos classificadores mais simples e intuitivos em machine learning. Foi proposto originalmente por Evelyn Fix e Joseph Hodges em 1951. Entretanto, há muitas dezenas de variações em relação a proposta original de Hodges e Fix. Pode ser considerado uma “evolução” do classificador de distância mínima. O algoritmo do KNN é menos sensível a outlier, um dos maiores problemas do classificador de distância mínima. Ele funciona baseado no princípio que amostras de uma mesma classe tendem a estar próximos umas das outras em um espaço de características. Assim, se você desejar realizar a classificação de uma determinada amostra de teste, basta associar a esta a classe mais comum entre as $K$ amostras conhecidas mais próximas da amostra de teste.

Funcionamento Básico

O KNN é um algoritmo não paramétrico de classificação supervisionada. Isso significa que ele aprende com um conjunto de dados rotulados (conjunto de treinamento) e depois classifica novos dados não rotulados (conjunto de teste) sem fazer suposições da distribuição de probabilidade dos dados (não paramétrico). No KNN não há propriamente um “treinamento” como, por exemplo, em uma rede neural. Um treinamento “verdadeiro”, normalmente é um procedimento interativo de refinamento e ajuste dos parâmetros do algoritmo de classificação. Por outro lado, no KNN, os dados de treinamento são simplesmente armazenados e utilizados diretamente durante a classificação das amostras de teste. Assim, dizemos que o KNN é um algoritmo baseado em instâncias e sem um treinamento “verdadeiro”. Em alguns casos, isso pode ser uma vantagem. Por exemplo, quando as instâncias de treinamento mudam muito ao longo do tempo. Entretanto, na maiorias dos casos, o fato do KNN não ter um treinamento “verdadeiro” é ruim. Isso porque o procedimento de treinamento, como realizado em uma rede neural, já é um tipo de “pré-computação” ou “pré-processamento” realizado pelo sistema para diminuir o esforço computacional no momento da operação real de classificação das amostras de teste. Ou seja, em sistemas “treináveis”, após o treinamento o sistema tende a apresentar respostas de uma forma mais rápida e de uma forma independente da quantidade de instâncias utilizadas no treinamento.

Ideia básica do KNN:

Se compararemos os algoritmos do KNN e do classificador de distância mínima vamos perceber que eles são bem semelhantes. O algoritmo do KNN pode até ser entendido como uma generalização do algoritmo de distância mínima, pois se implementarmos um KNN com $K=1$ teremos um sistema que será funcionalmente idêntico ao algoritmo de distância mínima.

Parâmetros Importantes

• K (Número de vizinhos): Esse parâmetro define quantos vizinhos considerar. Se $K=1$, o algoritmo simplesmente atribui a classe do vizinho mais próximo e, basicamente, se torna um classificador de distância mínima. Valores muito baixos de $K$ podem fazer o modelo ser muito sensível ao ruído, enquanto valores muito altos podem diminuir a influência de vizinhos relevantes. Normalmente, o valor de $K$ ideal é determinado através de testes exaustivos em um conjunto de amostras de validação.
• Métrica de Distância: A distância Euclidiana ao quadrado $(L_2)^2$ é a mais comum, mas a distância Manhattan $L_1$ e outras distâncias também são usadas. A definição da métrica de distância depende muito do problema e das características dos dados.

Vantagens

1. Simplicidade: KNN é fácil de entender e implementar.
2. Um único parâmetro de ajuste: O único parâmetro de ajuste de um KNN é o $K$, que em muitas situações pode ser encontrado de forma relativamente simples realizando alguns testes com um conjunto de validação. A métrica de distância quase sempre é a distância euclidiana ao quadrado. Assim, a métrica de distância não chega a ser algo que precise de ajuste. A grande maioria dos livros e pesquisadores da área não consideram a métrica de distância do KNN como um parâmetro de ajuste do KNN.
3. Flexibilidade: Pode ser usado tanto para classificação quanto para regressão.

Desvantagens

O KNN precisa calcular uma distância entre a amostra de teste e cada instância do conjunto de treinamento. Depois disso, para determinar os $K$ vizinhos mais próximos é necessário fazer um ordenamento de todas as distâncias medidas (ver o código abaixo). Esses procedimentos se tornam mais custosos a medida que o conjunto de treinamento cresce e, também, são difíceis de serem paralelizados. Assim, o desempenho/velocidade computacional do KNN pode se degradar muito quando utilizado em grandes massas de dados. É possível mitigar esse problema de escalabilidade do KNN com a utilização de algoritmos não supervisionados aplicados sobre os dados de treinamento para redução de instâncias e de características. Para redução do conjunto de instâncias, por exemplo, pode-se utilizar um algoritmo de clustering, como o k-means. E para redução do número de características, por exemplo, pode-se utilizar PCA. Entretanto, essas técnicas apenas reduzem os problemas de desempenho computacional do KNN.

Codificação

Abaixo segue uma codificação do algoritmo de KNN implementado em Scilab script.

//Exemplo site www.drgomes.pro

//p1 e p2 vetores linha
function y=dist2(p1,p2)
    vd=p1-p2
    y=vd*vd'
endfunction


//t    -> Vetor linha a ser testado 
//K    -> Numero de vizinhos
//P -> Matriz linha de prototipos 
function [nc,fc]=knn(t,K,P)
    [M,N]=size(P)
    N1=N-1
    kn=zeros(M,2)

    for i=1:M,
        kn(i,1)=dist2(t,P(i,1:N1))
        kn(i,2)=P(i,N)
    end
    [B,key]=gsort(kn(:,1),'r','i')
    kno=kn(key,2)
    kno=kno(1:K)//Os três mais próximos de vetor de teste

    fc=zeros(max(kno),1);
    for i=1:K,
        fc(kno(i))=fc(kno(i))+1
    end

    [B,key]=max(fc)
    nc=key
endfunction

Analisando o código acima dá para ver como é simples a codificação do KNN. Basicamente todo o algoritmo do KNN cabe em menos de 20 linhas (se contar apenas as linhas de código). O código entre as linhas 4 e 7 é a definição da métrica de distância, que no caso é distância euclidiana ao quadrado. O código principal do KNN está entre as linhas 13 e 33. E consiste, essencialmente, em mediar a distância entre a amostra de teste ($t$) e todas as instâncias do conjunto de treinamento ($P_{M \times N}$). No código, $P$ é uma matriz de vetores linha. Ou seja, cada linha $i$ das $M$ linhas de $P$ representa uma instância de treinamento. As colunas de $P$ de 1 até $N-1$ representam as características das instâncias e a última coluna de $P$, $N$, armazena um número associado a classe da instância. Essa não é a forma mais eficiente de se armazenar os pares de entrada-saída das instâncias, mas também não chega a ser uma desgraça computacional e simplifica muito a implementação do código.

Todas as distâncias entre a amostra de teste e as instâncias de treinamento são armazenadas em uma matriz $kn_{M \times 2}$ . Neste vetor, a coluna 1 armazena a distância e a coluna 2 armazena a informação da classe ou rótulo. O número da instância não é realmente necessário. Após isso, um ordenamento é realizado na matriz $kn$ de tal forma que as menores distâncias fiquem localizadas nas primeiras linhas da matriz. Assim, para determinar as $K$ distâncias mais próximas da amostra de teste $t$ basta selecionar as $K$ primeiras linhas da matriz $kn$ e contar a frequência de ocorrência das classes.

O ordenamento da matriz $kn$ é realizado na linha 22, com o comando “gsort” do scilab. A contagem de frequência das classes entre os $K$ vizinhos mais próximos a amostra de teste $t$ é realizada entre as linhas 26 e 29. E nas linhas 31 e 32 a classe mais frequente é identificada e retornada pelo KNN como o resultado da classificação.

Exemplo

Podemos fazer um comprativo entre as abordagens de um classificador de distância mínima e um KNN com K>1. Na Tabela 1, temos 12 instâncias de vetores bidimensionais rotulados e um total de 4 classes.

Na Figura 1, é possível ver uma representação gráfica das instâncias da Tabela 1. Nesta figura, as instâncias pertencentes a classe 1 são representadas com bolinhas vermelhas. As instâncias da classe 2 são bolinhas verdes. As instâncias da classe 3, são bolinhas azuis. E, finalmente, o único elemento da classe 4 é uma bolinha ciano.

A forma como um determinado classificado “divide” o espaço em classes a partir dos dados do conjunto de treinamento pode ser visualizada através de regiões de classificação. Para isso, essencialmente, o classificador deve testar cada ponto(ou pixel) do espaço em um determinado intervalo e “colorir” os pontos testados com as cores correspondentes a classe resultante do teste.

Na Figura 1, ao redor de cada bolinha é possível perceber uma figura geométrica pintada com a mesma cor da bolinha. Este espaço colorido e circundante de cada uma das instâncias da tabela 1 é a região de classificação de um classificador de distância mínima.

Figura 1: Fronteira de decisão para um classificador de distância mínima (KNN, com $K=1$). As instâncias utilizadas para gerar essas fronteiras estão marcadas com “bolinhas”, sendo um total de 4 classes (verde, azul, vermelho e ciano).

No caso da Figura 1 e devido a distribuição irregular das instâncias de treinamento as fronteiras de classificação(limites entre as regiões de classificação) são mais irregulares que, por exemplo, as observadas na Figura 2.

Na Figura 2, temos uma região de decisão gerada por um KNN com K=3. Comparando com as regiões de decisão da Figura 1 é possível perceber fronteiras mais simples. Na realidade, o ponto $(1.5 ,1.5)$ da classe 2 (bolinha verde) e o ponto $(0.5, 1)$ da classe 4 (bolinha ciano) são ignorados pelo KNN. No KNN com K=3, esses pontos se comportam como oulier e simplesmente são ignorados pelo modelo. Assim, apesar de nos dados da Tabela 1 haver 4 classes, no resultado de classificação do KNN só aparecem 3. E isso não é pelo fato de termos escolhido K=3, mas por a classe da bolinha ciano ser improvável em relação as outras classes. O KNN também considera improvável a existência de algo que possa ser classificado como da classe 2(verde) nas vizinhanças do ponto $(1.5 , 1.5)$. Assim, de certo modo o “K” do KNN pode ser visto como um parâmetro de um filtro que tende a “simplificar” as regiões de decisão de um classificador. E isso é normalmente útil em casos de dados ruidosos e imprecisos.

Em resumo, com um ajuste cuidadoso do K no KNN é possível eliminar problemas nos dados devido a ruídos e inconsistências das medidas ou do problema.

Figura 2: Fronteira de decisão de um KNN com $K=3$ para as mesmas instâncias utilizadas anteriormente para o classificador de distância mínima.

That’s all folks!