Classificador de distância mínima

O algoritmo de aprendizagem de máquina mais simples que você pode imaginar e que funciona se chama classificador de distância mínima. É um tipo de classificador supervisionado baseado em instâncias (amostras). Ele não é nenhum classificador “matador” e, no geral, fica muito longe da performance de uma deep learning. Entretanto, considerando a sua simplicidade, funciona muito bem. E em casos específicos de classes sem sobreposição o desempenho de classificação é ótimo ou próximo do ótimo.

Funcionamento Básico

A ideia básica é:

Considerando:

1) Um conjunto de amostras classificadas $p_i$;

2) Uma amostra de teste não classificada $x$;

3) Uma métrica de distância $D()$;

Classificar $x$ como pertencente a mesma classe da amostra $p_i$ mais próxima a $x$ segundo a métrica $D()$.

É só isso!

Vantagens

Uma das vantagens do classificador de distância mínima é a facilidade de implementação. O que o torna a opção numero UM quando é necessário fazer uma implementação do Zero em uma linguagem de programação específica. Fazer uma implementação do Zero pode parecer uma coisa meio de iniciante em um mundo de bibliotecas como scikit-learn, Keras, etc. Entretanto, em um mundo mais “baixo” de programação de sistemas embarcados não há muitas opções. Em ambientes de programação de dispositivos e microcontroladores com linguagens assembly,C, verilog ou VHDL falta opções! E, em muitos casos, você mesmo tem que implementar o algoritmo.

Para conjuntos de dados sem sobreposição, ver o exemplo na Figura 1, o classificador de distância mínima é ótimo em relação a performance de classificação. Ou seja, nestes casos, você poderia utilizar a deep learning do tamanho que quisesse, a performance de classificação seria no máximo igual a do algoritmo de distância mínima!

Figura 1: Dois conjuntos de amostras sem sobreposição.

Desvantagens

O algoritmo de distância mínima tem, basicamente, dois pontos fracos: tempo de classificação dependente do número de protótipos e grande sensibilidade a ruido, outlier e sobreposição dos dados. O fato do tempo de classificação depender do número de protótipos é ruim porque quanto mais protótipos forem utilizados para o treinamento do sistema mais lento ele vai ficar. Entretanto, esse é um problema que pode ser contornado através de uma escolha cuidadosa do conjunto de treinamento e utilização de métodos de categorização/clustering para reduzir a dimensionalidade do conjunto de treinamento quando necessário. Árvores de busca também podem ser utilizadas para reduzir significativamente o tempo necessário para encontrar o protótipo mais próximo da amostra testada. O segundo problema do método, a sensibilidade a ruído,outliers e sobreposições, é mais complicado de ser resolvido. Na Figura 2, há um gráfico ilustrativo desse caso. Claro que os dados de treinamento podem ser “filtrados” para remover os outlier e diminuir o ruído. Entretanto, esses procedimento por si já podem ser mais custosos e difíceis de implementar que a utilização de outros classificadores naturalmente mais robustos a esse tipo de problema, como o KNN ou redes neurais. Ou seja, se houver problemas de outlier, ruídos ou sobreposição nos dados é melhor escolher outro tipo de classificador.

Figura 2: Dois conjuntos de amostras com sobreposição e ruído. Este é um caso típico onde a performance de um classificador de distância mínima é muito baixa.

Codificando o “só isso” …

Aqui, vamos fazer um código ilustrativo em Scilab script. Um código básico e simples que o próprio leitor pode depois baixar e melhorar se desejar.

Para as amostras classificadas ou protótipos ($p_i$) vamos utilizar uma representação matricial onde as $n-1$ colunas representam as características das amostras e a última coluna ($n$) representa a classe da amostra. As linhas da matriz representam as amostras. Ou seja, vamos utilizar notação vetor linha.

\[ [P]_{m \times n} = \left[ \begin{array}{cc|c} && \\ \vdots && \vdots \\ p_i && C_i \\ \vdots && \vdots \\ && \end{array} \right]_{m \times n} \]

\[ p_i = [p_{i1} \ldots p_{i(n-1)} ]_{1 \times (n-1)} \]

$C_i$ é o respectivo rótulo da classe ao qual o vetor $p_i$ pertence. A entrada do classificador é a amostra de teste $x$. E será representada na forma de vetor linha com tamanho $n-1$.

\[ x = [ x_1 \ldots x_{n-1} ]_{1 \times (n-1)} \]

A métrica de distância utilizada pode ser de uma infinidade de tipos diferentes. Neste exemplo simples vamos nos limitar ao caso mais comum. Ou seja, a distância euclidiana ao quadrado, como descrita na equação abaixo:

\[ D(x,p_i) = (x-p_i)(x-p_i)^T \]

Definido o formato dos protótipos, da entrada e da distância, podemos começar o código propriamente dito:

//Distância euclidiana ao quadrado
//x e p -> vetores linha
function d=dist2(x,p)
    d=x-p
    d=d*d'
endfunction

//x -> vetor linha
//P -> Uma matriz de protótipos (formato vetores linha)
function rotulo=cDistMin(x,P)
    [M,N] = size(P)
    dmin=dist2(x,P(1,1:(N-1)))
    rotulo=P(1,N)

    for i=2:M,
        d=dist2(x,P(i,1:(N-1)))
        if d<dmin then
            dmin=d
            rotulo=P(i,N)
        end
    end
endfunction

O código do classificador de distância mínima ( função cDistMin ) fica com menos de 12 linhas no Scilab! O fato de utilizarmos uma linguagem com suporte a matrizes ajuda um pouco a reduzir o tamanho, mas se tivéssemos feito em C puro, por exemplo, o código não ficaria muito maior.

Notem que o código do classificador de distância mínima, basicamente, se resume a um busca em loop para encontrar o vetor $p_i$ mais próximo a $x$. E também é interessante notar que esse algoritmo funciona independentemente da dimensão dos vetores $p_i$ e $x$. Podendo ir do caso escalar (dimensão 1) até o onde o seu computador permitir chegar!

Exemplo de uso

O código implementado acima não tem uma limitação explicita para a quantidade de amostras, a quantidade de características ou número de classes. Na realidade, o maior limitador será a capacidade de memória e processamento do computador no qual esse código for executado. Entretanto, para facilitar o entendimento, neste exemplo vamos utilizar um conjunto de amostras bem simples. Vamos aplicar o código em um conjunto com 4 amostras e 2 características apenas de uma função lógica XOR. Os dados estão sumarizados abaixo:

O código anterior atualizado com os protótipos $p_i$ da função XOR fica da seguinte forma:

//Protótipos 
P=[
0 0 0;
0 1 1;
1 0 1;
1 1 0;
]

//Distância euclidiana ao quadrado
//x e p -> vetores linha
function d=dist2(x,p)
    d=x-p
    d=d*d'
endfunction



//x -> vetor linha
//P -> Uma matriz de protótipos (formato vetores linha)
function rotulo=cDistMin(x,P)
    [M,N] = size(P)
    dmin=dist2(x,P(1,1:(N-1)))
    rotulo=P(1,N)

    for i=2:M,
        d=dist2(x,P(i,1:(N-1)))
        if d<dmin then
            dmin=d
            rotulo=P(i,N)
        end
    end
endfunction

A única novidade mesmo deste código é a definição do conjunto de protótipos $[P]$ que está entre as linhas 2 e 7. Para utilizar esse código e ver o funcionamento do classificador basta executar esse código no Scilab e depois, na linha de comando, fazer as chamadas da função $cDistMin$ com os pontos de teste $x$ desejados. O classificador $cDistMin$ deve retornar o valor do rótulo do protótipo mais próximo à amostra de teste. Assim, se chamarmos $cDistMin([0,1],P)$ ou $cDistMin([1,0],P)$, o valor retornado deve ser $1$. Funcionando exatamente da mesma forma que um XOR. Entretanto, se entrarmos $cDistMin([0.1,0.9],P)$ o sistema também vai retornar $1$, mesmo que os valores da entrada não correspondam exatamente aos valores dos protótipos. Isso porque a entrada não precisa ser exatamente o valor do protótipo, basta ser algum valor próximo.

Abaixo segue uma pequena animação ilustrativa do uso desse classificado no prompt de comando do Scilab para alguns pontos de teste.

That’s all folks!