Categoria: Espaço de características

k-vizinhos mais próximos: uma análise

O algoritmo k-vizinhos mais próximos (do inglês, k-Nearest Neighbors – kNN) funciona da seguinte forma: dada uma instância de teste xq, o algoritmo encontra os k vizinhos mais próximos de xq no conjunto de treinamento. Em seguida, a classe de xq é dada pela classe que ocorrer com maior frequência entre os k vizinhos.

Na figura acima, são mostrados os cinco vizinhos mais próximos da instância de teste xq. Dessas cinco instâncias, 4 são da classe “+” (vermelha) e 1 da classe “0” (azul). Ao aplicar o kNN, com k=5, a instância xq é classificada como sendo da classe vermelha, pois essa classe possui mais representantes na vizinhança de xq.

Esse algoritmo possui dois parâmetros: o número de vizinhos (k) e a medida de dissimilaridade (ou de similaridade) usada para encontrar os vizinhos mais próximos. A distância Euclidiana é a medida mais amplamente usada para determinar os vizinhos, embora existam diversas opções. Em relação ao parâmetro k (número de vizinhos), várias alternativas para determinar o valor mais adequado por tarefa podem ser empregadas. Uma delas é avaliar o algoritmo kNN no conjunto de validação, adotando diferentes valores para k. O valor de k que alcançar a melhor precisão será escolhido para classificar todas as instâncias de teste.

Uma primeira diferença em relação a outras máquinas de aprendizagem, tais como árvore de decisão e multi-layer perceptron, é que, no kNN, a etapa de treinamento é caracterizada apenas pelo armazenamento das instâncias. A rigor, não há treinamento. Logo, a função que será usada para a tomada de decisão é definida em operação, analisando um subconjunto dos dados de treinamento, i.e., os k vizinhos mais próximos. Por esse motivo, pode-se dizer que o kNN é uma máquina de aprendizagem local.

Embora seja simples, vale destacar que o kNN constrói regiões de decisão não-lineares no espaço de características. Para ilustrar, a figura a seguir mostra como o espaço de características bidimensional é dividido quando emprega-se o kNN, com k=1. As linhas verdes delimitam a área de cobertura de cada uma das instâncias de treinamento (pontos pretos: x1, x2 e x3). Assim, qualquer instância de teste que se posicionar na região amarela será classificada como sendo da mesma classe da instância x1, pois essa será a instância mais próxima. Da mesma forma, instâncias localizadas na região laranja serão classificada pela classe de x2 e, na região azul, pela classe de x3.

Importante destacar que as regiões de cobertura mostradas na figura foram obtidas usando apenas um vizinho mais próximo (1NN). Ou seja, essas regiões podem ficam mais complexas ao adotar valores maiores de k. Além disso, uma caraterísticas interessante do kNN é que as regiões de coberturas podem ser facilmente modificadas ao inserir, remover ou reposicionar as instâncias.

Mas, o kNN possui algumas desvantagens:

Armazenamento: todas as instâncias de treinamento são armazenadas para posterior consulta, quando da chegada de uma instância de teste. Se o conjunto de treinamento possuir muitas instâncias, a quantidade de memória requerida para armazená-lo pode ser um problema. Uma alternativa, para aliviar essa questão, é usar algoritmos de redução de instâncias que têm o intuito de reduzir o número de instâncias no conjunto de treinamento.

Esforço computacional: a função que classificará uma instância de teste, só é definida em operação, usando os vizinhos mais próximos. Logo, o kNN requer um esforço de processamento, em tempo de execução, para vasculhar todo o conjunto de treinamento em busca dos vizinhos para cada instância de teste. Algoritmos de redução de instâncias também podem auxiliar para mitigar essa desvantagem do kNN.

Alta dimensionalidade: ao calcular a dissimilaridade (por exemplo: usando a distância Euclidiana) entre vetores que são representados por muitas variáveis, esse cálculo pode ser impreciso devido à alta dimensionalidade dos vetores. Uma maneira de atenuar essa questão é remover variáveis redundantes ou pouco relevantes, para fins de classificação, usando algoritmos de seleção ou de extração de características.

A figura a seguir mostra dois exemplos que ilustram uma instância de teste e seus cinco vizinhos mais próximos. Nesses dois exemplos, percebe-se que a instância de teste xq está bastante próxima das instâncias da classe “0” (azul). Mas, o kNN (k=5) classificará as duas instâncias de teste como pertencentes à classe “+” (vermelha), pois essa classe possui mais instâncias do que a classe azul na vizinhança de xq.

Nesses exemplos, a proximidade de xq em relação aos seus vizinhos não é levada em consideração. Apenas a quantidade de instâncias na vizinhança é usada para decidir a classe de xq. Mas, é possível encontrar variações do kNN que visam abrandar essa e outras propriedades previamente discutidas.

Redução de instâncias: seleção & geração

Algoritmos de redução de instâncias têm o objetivo de representar um conjunto de dados usando poucas instâncias. Dado um conjunto de dados (T), deseja-se obter um conjunto reduzido (S), de forma que o número de instâncias em S seja menor do que o número de instâncias em T, i.e., |S|<|T|. O novo conjunto S substituirá o conjunto T; logo, S não é qualquer subconjunto de T, mas, um conjunto que mantenha as informações do conjunto original e que o represente.

Esses algoritmos de redução são comumente aplicados na etapa de pré-processamento, antes do treinamento de uma máquina de aprendizagem. Ao diminuir o número de instâncias de um conjunto de dados, a quantidade de memória requerida para armazenar esses dados é reduzida. Além disso, máquinas de aprendizagem podem ser treinadas com maior agilidade, pois precisam extrair informações de uma quantidade menor de instâncias. Em especial, os algoritmos de aprendizagem baseados em instância (instance-based learning), tal como o k-Nearest Neighbors (kNN), podem se beneficiar bastante, visto que esses algoritmos são reconhecidamente lentos em operação.

Algoritmos de redução de instância são categorizados em: seleção de instâncias e geração de protótipos. Na seleção, o conjunto reduzido S é um subconjunto de T. Já na geração, o conjunto S é formado por instâncias que não necessariamente existem em T, ou seja, o algoritmo pode criar novas instâncias.

Seleção de instâncias

Essa abordagem busca pelo melhor subconjunto de instâncias (S) em um conjunto de dados (T), de forma que S ⊂ T. Para realizar tal tarefa, uma função de custo que define o que significa “melhor” subconjunto precisa ser definida. Por exemplo, no algoritmo de seleção de instâncias Edited Nearest Neighbors (ENN), a função de custo tem a tarefa de remover todas as instâncias que não são corretamente classificadas por seus vizinhos mais próximos. Outro exemplo é o Condensed Nearest Neighbors (CNN) que foca em remover instâncias que estão mais próximas dos centros das classes.

As figuras acima mostram os subconjuntos gerados pelos algoritmos ENN e CNN, a partir do conjunto de dados mostrado na primeira figura à esquerda. Pode-se notar que o ENN remove poucas instâncias e que a maioria das instâncias removidas pertence a regiões de borda. Logo, o ENN expõe mais claramente as fronteiras entre as classes.

A função de custo do CNN foca na remoção de áreas seguras, ou seja, agrupamentos de instâncias que têm a mesma classe. Por isso, na figura que mostra o resultado da aplicação do CNN, é possível perceber áreas vazias longe das fronteiras entre as classes. Esse algoritmo representa o conjunto de dados original usando bem menos instâncias do que o ENN.

Geração de protótipos

Os algoritmos de geração de protótipos criam instâncias artificiais que são usadas para representar o conjunto de dados original. Assim, ao invés de selecionar instâncias que existem no conjunto original, como os algoritmos de seleção de instâncias, os algoritmos de geração produzem novas instâncias (protótipos) que não existem no conjunto de dados inicial.

Para ilustrar como um protótipo pode ser criado para representar algumas instâncias, é possível se valer da noção de algoritmos de agrupamento (clustering), mesmo sabendo que esses pertencem a um espectro maior de aplicações. Os algoritmos de agrupamento fornecem um conjunto de grupos, e cada grupo pode ser representado por seu centro. Logo, pensando em reduzir as instâncias, pode-se representar todo o conjunto de dados original usando apenas os centros dos grupos. Assim, o número de protótipos no conjunto reduzido S é definido pela quantidade de grupos gerada pelo algoritmo de agrupamento.

A ideia é criar esses novos protótipos de forma que sejam necessários poucos deles para cobrir o espaço de características. Desta forma, o posicionamento desses protótipos nesse espaço é de suma importância. Muitas vezes, esse posicionamento é definido por um processo de otimização, tal como no algoritmo de classificação supervisionada learning vector quantization que é a pedra angular de diversas técnicas de geração de protótipos.

Discussão: Seleção versus Geração

A maioria das técnicas de seleção de instâncias e de geração de protótipos foi desenvolvida tendo como alvo o algoritmo kNN. Mas, vale destacar que essas técnicas podem ser usadas, eficientemente, como pré-processamento em outras abordagens de aprendizagem.

Para algumas aplicações, não é plausível gerar dados artificiais a partir dos dados originais. Logo, as técnicas de seleção seriam mais indicadas para esses casos. De maneira geral, as técnicas de seleção requerem menos poder computacional do que as de geração. Por outro lado, as técnicas de geração conseguem representar os dados originais de maneira mais concisa e, em geral, obtêm melhor precisão do que as de seleção.

Embora os algoritmos de redução de instâncias sejam rotineiramente usados na etapa de pré-processamento, antes do treinamento de uma máquina de aprendizagem, eles podem ser aplicados em outros cenários. Em [Cruz et al. 2018, Cruz et al. 2017], algoritmos de redução foram aplicados no contexto de combinação de classificadores.