Design of a graphical display system for Real-Time Monitor (GUI main)

Os comitês de classificadores são construídos através de técnicas de otimização metaheurísticas mono e multiobjetivo. As soluções das técnicas de otimização correspondem a comitês de classificação. O objetivo das técnicas é selecionar a quantidade de classificadores do comitê e os atributos das bases de dados de cada um, de modo a maximizar um subconjunto dos objetivos de otimização. Dependendo do experimento sendo realizado, são otimizados a acurácia de classificação, a boa diversidade, a má diversidade (ver 2.2.2) ou uma combinação deles.

As seções a seguir apresentam como os comitês são representados, como os objetivos de otimização são avaliados e quais algoritmos de otimização são aplicados.

4.1.1 Representação das Soluções

A representação das soluções nos algoritmos de otimização corresponde à configuração de um comitê e sua avaliação, isto é, quais os classificadores ativos, quais os atributos da base de dados utilizados por cada classificador base e quais os valores dos objetivos de otimização.

As soluções apresentam um conjunto de variáveis dependentes, respectivas aos objetivos de otimização, isto é, acurácia, boa diversidade e má diversidade do comitê, e um conjunto de variáveis independentes, correspondentes à configuração do comitê.

Os comitês podem apresentar uma quantidade de classificadores entre 1 e , onde é um dos parâmetros do comitê especificado antes da execução dos processos de otimização. As variáveis independentes são representadas por um vetor de valores booleanos onde cada posição representa se um atributo é ou não utilizado pelo correspondente classificador base. Assim, para uma base de dados de atributos, o vetor booleano possui posições onde as posições correspondem ao primeiro classificador, ao segundo classificador e assim por diante até representar os dados dos classificadores base do comitê. A figura 1 apresenta como essas informações são dispostas no vetor.

Figura 1: representação das variáveis independentes num comitê de classificadores base e uma base de dados de atributos.

Um classificador não é utilizado pelo comitê caso todos os seus atributos estejam desativados (iguais a falso). Todos os classificadores do comitê são gerados pela técnica k-NN com . Essa técnica é escolhida devido à sua simplicidade aumentando a eficiência em tempo de execução dos algoritmos de otimização.

Uma vez determinada as variáveis independentes, é fornecido para cada classificador uma cópia da base de dados de entrada do comitê apresentando somente os atributos que eles devem utilizar. Os classificadores são treinados e as variáveis dependentes são avaliadas pela técnica de validação cruzada e pelas medidas de boa e má diversidade. A acurácia de classificação é representada nas soluções como a quantidade de erros do comitê, assim os objetivos de acurácia (neste caso erro de classificação) e má diversidade são objetivos de minimização e a boa diversidade um objetivo de maximização.

4.1.2 Avaliação das Soluções

Avaliar uma solução consiste em avaliar o comitê de classificação representado por ela quanto a sua acurácia de classificação, a boa e má diversidade em relação à base de dados que o algoritmo de otimização está executando. Para isso, é necessário treinar o comitê para a correspondente base de dados, isto é, treinar cada classificador base que está ativo utilizando somente os atributos especificados pela solução.

O treinamento de um comitê consiste no treinamento dos classificadores base. É fornecida a cada classificador base uma cópia da base de dados do comitê. Em cada cópia são removidos os atributos que não são usados pelo classificador base correspondente e então este classificador é treinado com esta base. A figura 2 ilustra como esse processo ocorre.

Figura 2: Treinamento do comitê. A base de dados corrente é fornecida aos classificadores base removendo os atributos que não são utilizados. Cada classificador é treinado com a base correspondente.

Os objetivos de otimização são avaliados pelos resultados de classificação do comitê. As instâncias usadas para classificação são as instâncias presentes nas partições de teste determinadas pela técnica de validação cruzada (ver 2.2.1) com 10 partições da base de dados. É fornecida uma cópia da instância para cada classificador base. Essa instância é processada removendo os atributos que não são usados pelo classificador. Após classificar a instância o classificador informa o resultado ao método de combinação do comitê que neste trabalho emprega a técnica de voto majoritário (ver 2.1.3). O método efetua o seu processo e retorna a classificação do comitê. A figura 3 ilustra como esse processo ocorre.

Remoção dos Atributos

Treinamento Base de Dados 1 Comitê Base Base Classificador Classificador

Figura 3: Classificação de uma instância. Cada classificador recebe uma cópia da instância contendo somente os atributos utilizados por ele. As cópias são classificadas e o resultado informado ao método de combinação. Os resultados são combinados resultando numa das classes do problema.

Os resultados de cada classificador base e do comitê são utilizados para avaliação das medidas de boa e má diversidade. O resultado de classificação do comitê, isto é, o erro ou acerto, é utilizado pela validação cruzada para determinar seu desempenho.

4.1.3 Algoritmos de Construção

O método de construção dos comitês de classificação consiste na aplicação de técnicas de otimização metaheurísticas mono e multiobjetivo de Busca Tabu (ver 2.3.1 e 2.3.3.1) e Algoritmos Genéticos (ver 2.3.2 e 2.3.3.2). Como citado anteriormente, queremos avaliar o desempenho da aplicação das medidas de diversidade quando aplicadas explicitamente no processo de construção de comitês de classificação. Assim, as técnicas de otimização são aplicadas utilizando diferentes conjuntos de objetivos de otimização. Os comitês gerados são analisados para avaliar o comportamento dos mesmos em relação ao uso das medidas de diversidade.

Optamos pelo uso das técnicas de otimização metaheurísticas para construção dos comitês por permitir a utilização de várias medidas para avaliar e aprimorar os comitês. Assim, é possível utilizar explicitamente as medidas de boa e má diversidade para guiar a construção de um comitê. Porém, um problema associado a essa escolha é o tempo computacional exigido para execução dos algoritmos de otimização, este é devido ao tempo de processamento consumido para avaliação dos comitês de classificação, que depende da base de dados sendo processada, isto é, da quantidade de atributos, da quantidade de instâncias e das técnicas utilizada para gerar os classificadores base.

Cada algoritmo consiste na associação de uma técnica de otimização aos objetivos de otimização. Quando otimizamos um único objetivo aplicamos as técnicas clássicas de Busca Tabu (ver 2.3.1) e Algoritmos Genéticos (ver 2.3.2). De modo análogo, quando for empregado mais de um objetivo são utilizados os algoritmos MTS (ver 2.3.3.1) e NSGA II (ver 2.3.3.2).

A tabela 2 determina como as técnicas de otimização são associadas aos objetivos de otimização. Conforme descrito na tabela 2, são gerados os algoritmos e correspondentes às técnicas de Busca

Combinação

Remoção dos Atributos

Classificação Instância 1 Comitê Instância Instância Classificador Classificador Voto Majoritário Resultado: Classe

Tabu (BT) e Algoritmos Genéticos (AG) para o objetivo de acurácia do comitê. De modo análogo são gerados os algoritmos e para o objetivo de boa diversidade e os algoritmos e para o objetivo de má diversidade.

Algoritmos Utilizados nos Experimentos

Algoritmo Técnica de Otimização Acurácia Boa Diversidade Má Diversidade

Alg.T1 BT x Alg.T2 BT x Alg.T3 BT x Alg.G1 AG x Alg.G2 AG x Alg.G3 AG x Alg.M1 MTS x x Alg.M2 MTS x x Alg.M3 MTS x x Alg.M4 MTS x x x Alg.N1 NSGA2 x x Alg.N2 NSGA2 x x Alg.N3 NSGA2 x x Alg.N4 NSGA2 x x x

Tabela 2: Algoritmos utilizados nos experimentos onde a primeira coluna atribui um identificador ao algoritmo, a segunda identifica a técnica de otimização utilizada, a terceira, quarta e quinta coluna indicam se os respectivos objetivos de acurácia, boa diversidade e má diversidade são utilizados pelo correspondente algoritmo.

As técnicas multiobjetivo são associadas aos subconjuntos dos objetivos com mais de dois elementos resultando em oito algoritmos. Assim, para o conjunto de objetivos composto pela acurácia do comitê, pela boa diversidade e pela má diversidade são gerados os algoritmos e aplicando os algoritmos MTS e NSGA II respectivamente. De modo análogo são gerados os algoritmos e para os objetivos de acurácia e boa diversidade, os algoritmos e para os objetivos de acurácia e má diversidade e os algoritmos e para os objetivos de boa e má diversidade.

Durante a execução dos processos de otimização as variáveis independentes são modificadas dependendo da técnica de otimização sendo empregada, isto é, Busca Tabu ou Algoritmos Genéticos. As técnicas modificam as variáveis da mesma forma, seja a versão mono-objetivo ou a multiobjetivo.

No caso de algoritmos desenvolvidos segundo a técnica de Algoritmos Genéticos, as variáveis independentes são modificadas pelo operador de cruzamento de dois pontos e pelo operador de mutação uniforme (4º parágrafo de 2.3.2).

No caso de algoritmos desenvolvidos segundo a técnica de Busca Tabu as variáveis independentes são modificadas pelo operador (ver 2.3.1). O operador sorteia posições no vetor que representa as variáveis independentes. Para cada posição sorteada é gerada uma solução idêntica à solução de entrada do operador, porém modificando o valor da posição. Assim, é adicionado um parâmetro aos algoritmos baseados na técnica de Busca Tabu correspondente a quantidade de posições a serem sorteadas, isto é, a quantidade de vizinhos a serem gerados em cada iteração.