Categoria: Seleção dinâmica de classificadores

Seleção dinâmica de one-class classifiers

Mesmo sendo desenvolvidos para problemas que tenham apenas dados de uma classe, one-class classifiers (OCCs) também podem ser usados para tarefas que possuem várias classes. Nesse caso, um OCC é treinado para cada classe. Logo, para uma tarefa com n classes, n OCCs serão treinados. A classificação de uma nova instância é realizada da seguinte forma: essa instância é fornecida como entrada para cada um dos OCCs e sua classe é definida como a classe do OCC que responder com maior certeza.

Entretanto, quando uma nuvem de instâncias é multimodal, ou seja, quando essa nuvem possui mais de um grupo, boa parte dos OCCs não consegue lidar com essa dificuldade. Suponha que os pontos vermelhos na figura (a) acima pertençam à classe target e os pontos verdes à classe outlier. Vale destacar que durante o processo de treinamento do OCC, apenas os pontos vermelhos estão disponíveis. Assim, os pontos em verde são mostrados na figura apenas para fins de ilustração. A elipse em preto representa o classificador OCC e engloba todos os pontos vermelhos, dividindo a área do espaço de características em duas: target (dentre da elipse) e outlier (fora da elipse). Nessa figura, é possível notar que vários exemplos da classe outlier estão localizados dentro da região delimitada pelo OCC e, por consequência, esses pontos são incorretamente classificados como pertencentes à classe target. Nota-se também que as instâncias em vermelho compõem uma classe multimodal, ou seja, formada por várias modas/grupos.

Uma alternativa para lidar com essa multi-modalidade é criar várias meta-classes, uma para cada grupo, e treinar um OCC por grupo. Logo, uma nuvem de pontos (uma classe) será representada por vários OCC, um para cada meta-classe ou grupo. O desafio é definir o número de grupos em uma nuvem de pontos e, para esse fim, pode-se usar cluster validity indices para estimar este número.

Entretanto, não existe um índice (cluster validity index) que consiga definir de maneira precisa todos os grupos de qualquer nuvem de pontos, pois tal tarefa depende da medida de distância usada, da estrutura dos dados e de outras características. Em outras palavras, um dado índice pode ser a melhor escolha para uma classe e não ser para outra. Logo, esse mapeamento, do melhor índice por classe, é um problema em aberto.  Além disso, quando os cluster validity indeces são aplicados a uma dada nuvem de pontos, eles podem separar essa nuvem de maneiras diferentes.  Por exemplo, o índice Silhouette pode indicar que a nuvem possui 3 grupos, enquanto o índice NbClust pode indicar 5 grupos.

Diante deste contexto, foi proposto o método One-class Classifier Dynamic Ensemble Selection for Multi-class problems (MODES) que é um sistema de seleção dinâmica de classificadores para tarefas multi-classe. O MODES usa vários índices e treina um OCC para cada grupo definido por cada um dos índices. Essa estratégia permite que a diversidade das informações extraídas pelos índices seja incorporada ao sistema através do treinamento de vários OCCs. Por exemplo: a figura (b) ilustra que um dado cluster validity index encontra dois grupos; assim, dois OCC são treinados, um para cada grupo. Já outros cluster validity indexes encontram 4 e 5 grupos, como mostrado nas figuras (c) e (d), respectivamente; e, mais nove OCCs são treinados. Assim, cada OCC torna-se um especialista em uma determinada área do espaço de caraterística e minimiza o erro de classificar um outiler como target, como ocorre na figura (a).

Vale destacar que no MODES cada classe é tratada individualmente, logo, desbalanceamento entre as classes não é uma preocupação. Além disso, estratégias que decompõem as classes, como é o caso do MODES, podem se apresentar como alternativas interessantes para incremental learning e para open-set recognition. 

O MODES propõe uma abordagem capaz de lidar com dados que possuem distribuições complexas usando uma estratégia que seleciona dinamicamente os OCCs mais competentes para cada uma das instâncias de teste.

Rogério CP Fragoso, George DC Cavalcanti, Roberto HW Pinheiro, Luiz S Oliveira. Dynamic selection and combination of one-class classifiers for multi-class classification. Knowledge-based Systems, 2021.

Etapas de um sistema de múltiplos classificadores

Um sistema de múltiplos classificadores (multiple classifier system — MCS) é composto por um pipeline de três etapas: geração, seleção e integração — conforme mostrado na figura a seguir.

mcs
Etapas de um sistema de múltiplos classificadores. [adaptada de Cruz et al. 2018]
Pode-se observar essas três etapas de um MCS como uma caixa-preta que recebe como entrada um conjunto de treinamento (Γ), um conjunto validação e uma instância de teste (xq), e que fornece como saída, a classe (no caso de classificação) ou o valor predito (no caso de regressão ou previsão de séries temporais) da instância de teste. Da mesma forma que máquinas de aprendizagem monolíticas (árvore e decisão, redes neurais, entre outras), um MCS busca uma função capaz de predizer com eficácia o rótulo das instâncias que lhe são apresentadas durante a generalização. A seguir, são descritas as três etapas de um MCS.

Geração

Na primeira etapa, geração, as máquinas de aprendizagem são treinadas e armazenadas em um pool C que pode ser homogêneo ou heterogêneo. Por homogêneo, entende-se que todos os modelos do pool são treinados usando o mesmo algoritmo de aprendizagem, e.g., árvore de decisão. Por outro lado, em um pool heterogêneo, os modelos são treinados com diferentes algoritmos, tais como: árvore de decisão, perceptron e redes neurais.

Usar algoritmos diferentes é uma forma de aumentar a diversidade do pool; sendo essa uma vantagem de um pool heterogêneo. Porém, escolher quais algoritmos de aprendizagem devem ser usados, e quantos, é um problema desafiador. Daí, gerar um pool homogêneo é uma alternativa interessante por sua simplicidade.

Mesmo trabalhando com um pool homogêneo, é necessário que os modelos desse pool sejam diversos. Bagging (bootstrap aggregating) é um algoritmo comumente usado para esse fim e funciona da seguinte forma: dado um banco de dados de treinamento (Γ) com n instâncias, bagging gera m bancos de dados usando reamostragem com reposição. Cada banco de dados gerado tem o mesmo número de instâncias (n) do banco de dados original. Mas, como bagging é um procedimento com reposição, cada banco de dados terá instâncias repetidas. É esperado que 63,2% sejam instâncias únicas de Γ, e que, o restante, 36,8%, seja composto de instâncias repetidas. Cada um dos bancos de dados gerado por bagging é usado para treinar um modelo. Assim, ao fim do processo, m modelos são treinados, C = {c1, c2, …, cm}.

Dado que bagging usa um processo aleatório para adicionar instâncias a cada um dos bancos, pode-se afirmar, com alta probabilidade, que os bancos gerados são diferentes entre si. Diferença essa que auxilia na geração de modelos diversos. Além do bagging, outros algoritmos são usados para gerar o pool, entre eles: boosting, random subspace e rotation forest.

Seleção

Após a geração, a próxima etapa tem o objetivo de selecionar um subconjunto de modelos do pool que será usado para predizer a classe/valor da instância de teste. A seleção pode se dar de duas formas: estática ou dinâmica.

ss
Seleçao estática [adaptada de Cruz et al. 2018]
A seleção estática (static selection – SS) escolhe os melhores modelos do pool C que comporão o ensemble de modelos C’, sendo C’ ⊂ C. A figura acima mostra que esse processo é realizado offline, ou seja, durante o treinamento, e usa o conjunto de validação como guia para a escolha dos modelos. Na seleção estática, o mesmo subconjunto de modelos C’ é usado para classificar/predizer todas as instâncias de teste (xq).

Já na seleção dinâmica, os modelos selecionados podem diferir de uma instância de teste para outra; por esse motivo é chamada de dinâmica. Essa operação de seleção é realizada online, quando o sistema completo já está em operação, e depende da instância de teste que se deseja avaliar.

dcs
Seleção dinâmica de um modelo (ci) por instância de teste (xq) [adaptada de Cruz et al. 2018]
des
Seleção dinâmica de um ensemble (C’) por instância de teste (xq) [adaptada de Cruz et al. 2018]
As duas figuras acima mostram formas de selecionar dinamicamente modelos: a primeira seleciona apenas um modelo por instância de teste, enquanto a segunda seleciona um ensemble, um subconjunto do pool inicial.

A seleção dinâmica é motivada pelo fato de que nem todos os modelos no pool são competentes para predizer o rótulo de todas as instâncias de teste. Assim, deseja-se encontrar, por instância, os melhores especialistas (modelos) para realizar essa predição.

Integração

A etapa de seleção pode escolher um ou mais modelos. Se apenas um modelo for selecionado, não há integração. Nesse caso, a resposta do sistema é dada pela aplicação do modelo selecionado à instância de teste, i.e., ci(xq).

Sob outra perspectiva, se mais de um modelo for selecionado, é necessário o emprego de alguma regra para combinar as respostas dos modelos. Essas regras podem ser divididas em duas categorias: treináveis e não-treináveis. As não-treináveis levam esse nome pois são regras fixas que não necessitam de um processo de treinamento. Nessa categoria, o voto majoritário é a regra mais empregada. Nesta regra, cada modelo vota em uma classe e a classe com mais votos é atribuída como sendo o rótulo da instância de teste. Outros exemplos de regras não-treináveis são: média, produto, soma, mínimo e máximo.

Como o próprio nome indica, as regras treináveis são definidas por um processo de treinamento. Assim, usam-se máquinas de aprendizagem com o propósito de aprender a melhor função que integrará as respostas dos modelos selecionados. Qualquer máquina de aprendizagem pode ser usada para esse fim, e.g., árvore de decisão e multi-layer perceptrons.

Quando não se sabe a priori quantos modelos serão escolhidos pela etapa de seleção, as regras não-treináveis são mais usadas do que as treináveis, pois a maioria das máquinas de aprendizagem requerem um vetor de características de tamanho fixo. Além disso, as regras não-treináveis são mais simples e, por conseguinte, mais fáceis de interpretar.