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.