NXT Mindstrom device

Na literatura encontramos diferentes definições de medidas de diversidade para comitês de classificadores, porém ainda não existe uma medida padrão (BROWN et al, 2005; BROWN; KUNCHEVA, 2010; KUNCHEVA; WHITAKER, 2003; TANG; SUGANTHAN; YAO, 2006).

O trabalho de (TANG; SUGANTHAN; YAO, 2006) realiza um estudo teórico e experimental de seis medidas de diversidade: namely disagreement measure, double fault measure, KW variance, inter-rate agreement, generalized diversity e measure of difficulty. Nos estudos experimentais, os comitês são construídos gerando um conjunto de classificadores e selecionando um subconjunto de membros que maximize a diversidade e minimize o erro de classificação do comitê através de um processo de busca guloso. Conclui que as medidas estudadas são ineficientes para geração de comitês acurados quando o erro de classificação é minimizado e a medida de diversidade maximizada. Os resultados são confirmados teoricamente mostrando que maximizar tais medidas não implica em minimizar o erro de classificação de comitês de classificação.

O trabalho de (KUNCHEVA; WHITAKER, 2003) apresenta e categoriza diferentes medidas de diversidade. Estuda a relação das mesmas com a acurácia de classificação em comitês que fazem uso do voto

majoritário como técnica de combinação. Realiza um estudo de dez medidas de diversidade concluindo que otimizar uma dessas medidas em vez de minimizar o erro de classificação não gera comitês mais acurados. Cita ainda, que não existe uma medida que faça isso de forma eficiente, aumentando a desempenho dos comitês, e que ainda é necessária definir como uma medida de diversidade possa ser usada para construir comitês de classificadores mais eficientes.

Em (BROWN et al, 2005) são apresentadas e categorizadas diferentes técnicas de construção de comitês de classificadores que apresentem diversidade. Tais técnicas são categorizadas em: ponto inicial no espaço das hipóteses (“starting point in hypothesis space”); conjunto limitado no espaço hipóteses (“set of accessible hypothesis”); e percurso no espaço de hipóteses (“traversal of hypothesis space”). Estas categorias são definidas levando em consideração como as hipóteses de classificação são geradas, isto é, como cada classificador base é gerado.

Esse trabalho ainda define quando os métodos são construídos usando a diversidade de modo implícito ou explícito. É definida quanto à consideração da diversidade na construção, isto é, um método de construção usa a diversidade explicitamente se durante a construção do comitê for otimizada alguma métrica de diversidade (BROWN et al, 2005). Porém, como citamos anteriormente, usar explicitamente a diversidade na construção de comitês não compartilha o mesmo sucesso do uso de metodologias implícitas (KUNCHEVA, 2004).

A categoria de ponto inicial engloba os métodos de construção que consistem em variar os parâmetros das técnicas de geração dos comitês de classificação. Exemplos dessa categoria são comitês de classificadores onde cada classificador base é gerado por uma mesma técnica, utilizando um mesmo conjunto de dados para cada um, porém variando os parâmetros da técnica. Por exemplo, podemos formar um comitê de classificadores utilizando a técnica de k-NN para gerar cada classificador base usando um valor de diferente para cada um. Esta categoria é a menos efetiva das três (BROWN et al, 2005).

Já a categoria de conjunto limitado engloba os métodos que constroem os classificadores limitando as hipóteses de classificação que podem ser geradas pelas técnicas de classificação. Representantes desta categoria são as técnicas que constroem os classificadores utilizando um conjunto de bases de dados diferente para cada ou utilizando diferentes técnicas de geração dos classificadores. Assim, quando fornecemos diferentes bases de dados limitamos as informações utilizadas para gerar os classificadores e consequentemente as técnicas não são capazes de gerar classificadores que capturem as características representadas pelas informações ausentes. De modo análogo, cada técnica de classificação captura diferentes informações das bases de dados e assim os classificadores gerados por diferentes técnicas são diferentes entre si, isto é, apresentarão erros em instâncias de diferentes tipos.

O trabalho de (LEE et al, 2008) é um exemplo da categoria de conjunto que gera diversidade implicitamente. O comitê é gerado em duas etapas. Na primeira etapa é empregada a técnica de Algoritmos Genéticos para maximizar a acurácia de um classificador modificando os atributos a serem utilizados no treinamento. O classificador é gerado pela técnica de Análise de Discriminante Linear e a acurácia é definida como uma combinação linear do acerto de classificação, da sensitividade e da especificidade do classificador. Para cada execução da técnica de Algoritmos Genéticos é gerado um membro do comitê e o conjunto de atributos que se repetem mais vezes nesses classificadores é selecionado como o melhor conjunto de atributos. Na segunda etapa é aplicado o método de Seleção Aleatória de Subespaço sobre o conjunto dos melhores atributos. Para cada base de dados dos classificadores é gerada uma base de dados que possui um subconjunto

das instâncias e dos melhores atributos como resultados da técnica de Seleção Aleatória de Subespaço. O comitê é retornado utilizando classificadores gerados pelas bases de dados criadas utilizando um método de combinação de voto majoritário.

Em (OLIVEIRA; CANUTO; SOUTO, 2009) é feita uma análise experimental de construção de comitês de classificadores heterogêneos através da técnica de Algoritmos Genéticos usando explicitamente a medida de diversidade de Yule s Q-Statistic. A técnica de Algoritmos Genéticos é empregada para selecionar os membros do comitê, otimizando a acurácia, ou a diversidade ou a acurácia e a diversidade. Quando os dois objetivos são utilizados é empregado o algoritmo Multi-Objective Genetic Algorithm (MOGA) que é um algoritmo multiobjetivo baseado na técnica de Algoritmos Genéticos. Os algoritmos gerados são comparados para execuções em três bases de dados concluindo que utilizar a acurácia mais a diversidade geram resultados melhores que utilizar somente a acurácia ou somente a diversidade como objetivo de otimização. Porém os resultados se limitam a medida de diversidade empregada, ao método de construção do comitê e as bases de dados utilizadas para avaliação. O trabalho proposto fará uma análise similar essa, porém são utilizadas as medidas de boa e má diversidade e os resultados são verificados com mais bases de dados.

O trabalho de (SANTANA et al, 2010) é um exemplo da categoria de conjunto que usa uma medida de diversidade explicitamente na construção do comitê sem a otimização de uma medida de acurácia, isto é, a acurácia é gerada implicitamente. São empregadas as técnicas de Algoritmos Genéticos e de Colônia de formigas para selecionar os atributos utilizados por cada membro do comitê. A técnica de Colônia de Formigas é uma técnica de otimização metaheurística. Como medida de diversidade é definida a medida de Intra Correlação que consiste da média da correlação de cada atributo presente em relação ao atributo que representa as classes do problema. A correlação é avaliada pela medida de Pearson s Product Moment Correlation Coefficient (GIBBONS; CHAKRABORTI, 2003). Em alguns resultados é verificado que otimizar a medida de diversidade gera comitês mais acurados que otimizar a acurácia de classificação. Assim como esse trabalho, desejamos verificar se o mesmo ocorre para as medidas de boa e má diversidade, ou seja, verificar se é possível otimizar a diversidade em vez da acurácia de classificação e ainda assim obter comitês mais acurados.

Citamos ainda o trabalho de (TAHIR; SMITH, 2010) em que é apresentado um comitê de classificadores baseado no k-NN e na Busca Tabu. Os classificadores base são gerados pela técnica de k-NN utilizando 1 como o valor de , porém cada classificador utiliza uma métrica de distância diferente. O operador de vizinhança consiste em gerar um conjunto de classificadores para cada métrica de distância selecionando os atributos baseado na distância de Hamming. O melhor classificador de cada conjunto é selecionado. A avaliação é efetuada por validação cruzada utilizando dez partições. Cada combinação dos classificadores selecionados corresponde a um vizinho do comitê e aquele que apresenta a maior diversidade é selecionado como melhor vizinho. Então o conjunto de atributos de cada classificador base é utilizado para gerar os novos conjuntos de classificadores de cada métrica. Assim, esse trabalho é categorizado como técnica baseada em ponto inicial e de conjunto utilizando explicitamente a uma medida de diversidade.

A categoria de percurso engloba os métodos que constroem os classificadores de modo a ocuparem diferentes posições no espaço de hipóteses. Isto é, são as técnicas que tentam construir classificadores especialistas em cada característica do problema. Exemplos dessa categoria são as técnicas de construção destinadas à geração de comitês que usem técnicas de combinação dos valores baseada em seleção.

Como exemplo desta categoria, apresentamos o trabalho de (CHEN et al, 2008) que apresenta um método de construção de comitês heterogêneos. A diversidade neste trabalho é gerada implicitamente através da escolha dos membros do comitê. Inicialmente é gerado um conjunto de classificadores base e atribuído a eles um peso de importância na classificação. A metaheurística de Nuvens de Partículas é empregada para maximizar a acurácia do comitê modificando o peso de cada classificador durante a otimização. Ao final do processo é selecionado o conjunto de classificadores que apresentem os maiores valores dos pesos.

Outro exemplo desta categoria é o trabalho de (SOUTO et al, 2008), porém diferente do anterior ele gera diversidade explicitamente. O método consiste em gerar um comitê de classificadores aplicando técnicas de agrupamento sobre a base de dados gerando diferentes conjuntos de instâncias, ou grupos de instâncias, com características em comum. Necessita de um conjunto inicial de classificadores que são selecionados para formar o comitê. Para cada grupo de dados é selecionado o conjunto de classificadores que apresente as maiores acurácias e em seguida selecionado nesse conjunto, o subconjunto que apresente as maiores diversidades. Então é retornado um comitê formado pelos conjuntos de classificadores selecionados para cada grupo utilizando uma técnica de fusão para combinação dos resultados.

Neste trabalho empregamos um método de construção que usa explicitamente uma medida de diversidade e que é classificado como categoria de ponto inicial e de conjunto limitado. Durante a construção dos comitês as técnicas de geração dos classificadores são modificadas, os atributos das bases de dados utilizadas por cada técnica também são modificados assim como as técnicas usadas para gerar os classificadores. Caso os resultados obtidos sejam favoráveis à utilização das medidas de boa e má diversidade em vez da acurácia como objetivo de otimização, os resultados podem ser comparados com os resultados dos trabalhos aqui apresentados.