Recentemente, investigamos novas estratégias para combinação de técnicas de diversidade em ensemble. Essa pesquisa tem produzido estruturas heterogêneas para Bagging e Boosting (CO- ELHO; NASCIMENTO, 2010; NASCIMENTO; COELHO, 2009b). Em ambos os casos, a ideia era combinar duas diferentes técnicas de diversidade, permitindo o recrutamento de algoritmos de aprendizagem distintos para indução de ensembles em base de dados reamostrados via Bag- ging(BREIMAN, 1996a) e Boosting (SCHAPIRE; FREUND, 2012), respectivamente.
Nesta abordagem, o objetivo é incrementar os níveis de diversidade em ensemble em três estágios (NASCIMENTO et al., 2011), conforme exibido na Figura 6. Cada estágio capitaliza da técnica produzida no estágio anterior.
No primeiro estágio, a diversidade é promovida através da seleção de características e a redistribuição através dos componentes de ensemble. Seleção de características reduz a dimen- sionalidade das características de uma base original, mantendo os atributos mais discriminativos e excluindo aqueles que são redundantes (GUYON et al., 2006). Comumente, essa tarefa é re- alizada por alguma função de otimização (EIBEN; SMITH, 2007), e, para nossa proposta, um algoritmo genético (AG) foi adotado para seleção de um (quase) ótimo subconjunto de caracte- rísticas a ser associado a diferentes componentes.
Nesse AG, um cromossomo binário representa um possível subconjunto de características. A representação binária é apropriada em problemas de otimização combinatória (EIBEN; SMITH, 2007), tal como o típico caso de seleção de características investigada nesta tese. De fato, outros trabalhos relacionados tem feito o uso dessa solução em seleção de características no contexto de ensembles heterogêneos (SANTANA et al., 2010). Para nossa proposta, o tamanho do cro- mossomo é K × F, onde K representa o número de componentes e F denota a cardinalidade de características originais da base. Nesse cromossomo, a primeira parte de F bits representa o subconjunto de características para ser associado ao classificador k1, enquanto que o segundo
F bitscorresponde ao subconjunto de características associadas ao classificador k2, e assim por
diante. A Figura 7 ilustra como um cromossomo individual é particularmente codificado para a base “credit-a”, com 15 características, conforme apresentados no Apêndice A, logo, neste caso, |F| = 15 e |k| = 12. Nesse exemplo, as características #2, 3, 6, 9, 12, 14 e 15 são associadas para
Figura 6: Estágios adotados para incremento dos níveis de diversidade em ensemble. o primeiro classificador k1, enquanto que apenas as características #4, 6 e 15 são associadas ao
classificador k12.
Durante a primeira fase, uma vez que os componentes que irão compor o conjunto final não tenham sido selecionados, no entanto, um método baseado em filtro de seleção de característica é empregado (GUYON et al., 2006), configurado com um Coeficiente de correlação de Pearson (CCP) (CHEN; POPOVICH, 2002) como critério de otimização (ou seja, função de aptidão do GA). A fim de definir formalmente o CCP, considere duas variáveis aleatórias X e Y , cada
Figura 7: Codificação do cromossomo para seleção de características aplicado à base “credit-a”. amostra de tamanho n. Então o CCP, pode ser definido pela Equação ( 3.1).
CCP= ∑
n
i=1(Xi− X)(Yi−Y )
q
∑ni=1(Xi− X)2
q
∑ni=1(Yi−Y )2
. (3.1)
Em outras palavras, CCP é uma medida não-paramétrica de correlação, que avalia o quão boa uma função monotônica arbitrária poderia descrever a relação entre duas variáveis aleatórias, sem fazer quaisquer suposições sobre a distribuição dos seus valores. Assim, esta medida parece ser muito apropriada para capturar a correlação das características de qualquer padrão de entrada. No nosso caso, CCP é utilizado para medir os níveis de intra-correlação, isto é, a correlação entre as características atribuídas a um único componente. A ideia é escolher as características para um classificador que não possuem correlação. A CCP é calculada separadamente para cada componente e em seguida a média é calculada para produzir um único resultado. Quanto maior a média, maior tende a ser a diversidade entre os componentes induzidos.
Na segunda fase da nossa abordagem, reamostragem de dados é empregada como o meca- nismo para elevar os níveis de diversidade entre os classificadores. Isto é feito usando réplicas de bootstrapdo conjunto de dados de treinamento como em Bagging (BREIMAN, 1996b), cada ré- plica que está sendo gerada aleatoriamente. Cada novo conjunto de dados tem o mesmo número de instâncias de formação do conjunto de dados original (Ntr); no entanto, algumas instâncias
aparecerão várias vezes, enquanto outras não vão aparecer. O tamanho efetivo é menor, e os conjuntos de dados tendem a sobrepor-se significativamente. Cada conjunto de dados derivado é usado para treinar um classificador, e os recursos associados a cada conjunto de dados são aqueles selecionados pelo AG da etapa anterior da metodologia.
Finalmente, o terceiro estágio emprega um segundo AG (EIBEN; SMITH, 2007) como se- letor de componente. Cada componente pode ser induzido por diferentes algoritmos de aprendi- zado para uma base derivada pela estratégia anterior, produzindo arquiteturas heterogêneas (CA-
NUTO et al., 2007). Neste estudo, assim como em Coelho e Nascimento (2010), nós conside- ramos M = 10 diferentes algoritmos de aprendizado (WITTEN; FRANK, 2005): Naïve Bayes (NB), baseado em estatística bayesiana; redes neurais RBF e máquinas de vetores-suporte via SMO algoritmo, baseada em função não-linear; J48 e REP Tree (RT), baseado em árvores de decisão; IBk, baseado em aprendizado por vizinhança; e Decision Stump (DS), OneR, PART e Decision Table(DT), baseados em regras.
Nesse segundo AG, os indivíduos são codificados como vetor de valores inteiros (referente ao terceiro estágio da Figura 6). Esses valores são representados entre 1 e 10, indicando, respec- tivamente, os métodos de classificação listado anteriormente SMO, NB, IBk, RT, RBF, J48, DS, OneR and PART. Através da validação cruzada estratificada de 10-fold, os modelos de ensembles heterogêneos são induzidos. Os valores de erro médio são utilizados como valor de aptidão.
Do ponto de vista teórico, a eficácia da proposta de três estágios de diversidade também pode ser analisada, considerando o trabalho de Geman, Bienenstock e Doursat (1992), de acordo com o erro esperado de um algoritmo de aprendizagem de uma função alvo e um conjunto de treinamento de tamanho particular, podem ser decomposto em termos de bias, variância e ruído.
3.2.2 Segunda Abordagem: Algoritmo Genético com Função de Avaliação
Adaptativa
A ideia do novo algoritmo genético é semelhante a discutida para incremento de diversidade; por outro lado, a contribuição está relacionada na utilização de uma função de aptidão adaptativa que explora duas técnicas de avaliação de fitness, uma baseada em filtro e uma outra baseada em wrapper. A motivação nessa solução deve-se a observação em muitos experimentos computacio- nais, nos quais, percebeu-se que melhores resultados são alcançados quando aplicados à técnica wrapper; por outro lado, o tempo de execução para experimentos mais complexos era melhor (menor tempo) quando aplicado à técnica de filtro. Isso é facilmente justificado, porque geral- mente no wrapper é utilizado, como resultado de avaliação, o erro médio obtido da validação cruzada de uma algoritmo de aprendizado. Já no filtro, são utilizados como resultado de avali- ação, por exemplo, cálculos estatísticos aplicados diretamente sobre o conjunto de treinamento. Logo o objetivo é conseguir, de forma concomitante, alcançar os benefícios de ganhos de desem- penho e custo computacional proporcionado por cada técnica quando aplicadas em separado.
A Equação (3.2) apresenta a adaptação de uma função de avaliação que usa as técnicas de filtro e wrapper.
f it(i)= W F(i)∗ Filter(i)+WW(i)∗W rapper(i) (3.2)
Onde W F(i) é um peso associado à função de filtro Filter(i). No mesmo contexto, WW(i) corresponde a um peso associado a função wrapper W rapper(i). A função de filtro é a mesma utilizada na versão do algoritmo genético mencionado anteriormente. Já para a função wrap- perfoi utilizado o nível de acuidade em ensemble. Portanto, como já mencionado, o cálculo de acuidade de um ensemble é complexo em termos computacionais. Ao fazer isso, precisamos de- cidir aspectos importantes, principalmente relacionados com a utilização da função de avaliação para aqueles indivíduos que não passaram por avaliação de wrapper e a proporção da popula- ção que passa pela avaliação wrapper. Em relação à primeira questão, a função de aptidão dos indivíduos que não passaram pela avaliação wrapper foi baseada apenas na avaliação do filtro, tendo W F(i)= 1 e WW(i)= 0. Em relação à segunda questão, essa proporção é definida de forma
dinâmica e utilizando o seguinte procedimento:
1. Defina a proporção inicial de população que passa por avaliação wrapper, prop, a 50%; 2. Escolha os indivíduos para avaliação wrapper. Essa escolha pode ser feita aleatoriamente
ou tendo em consideração um critério. No nosso caso, foi utilizada a última vez que o ascendente do indivíduo foi avaliado via wrapper. A ideia é dar altas probabilidades para indivíduos cujo ascendente não passaram por avaliação de wrapper;
3. Criar duas listas de classificação (rankging), baseado no critério de filtro e uma com base no critério wrapper;
4. Compare os dois ranking e então faça:
(a) Incremente prop se a o valor de similaridade entre os dois ranking é maior que o máximo, max;
(b) Decremente prop se o valor de similaridade dos dois ranking é menor que o mínimo, min; ou
(c) Mantenha o valor de prop se o valor de similaridade estiver entre o mínimo e má- ximo.
A ideia da configuração dinâmica de prop é que se o ranking usando filtro semelhante ao ranking produzido vai wrapper, mantêm-se a utilização de avaliação via filtro (por ser mais rápido), caso contrário, mantêm-se utilizando a avaliação o wrapper (por ser mais eficiente). Em nosso estudo experimental, usamos max = 70% e min = 40%. Além disso, a escolha dos pesos associados aos filtros e avaliações wrapper pode ser um processo complexo. Portanto, neste trabalho, assumimos W F(i) = WW(i)= 0, 5. Neste caso, ambas as abordagens têm igual importância na função de fitness.
Para ambas as versões dos algoritmos genéticos, os principais parâmetros foram definidos da seguinte forma (após o ajuste manual): 20 como o tamanho da população; 80 % e 5 % em taxas de cruzamento e mutação, respectivamente; e 200 o número de máximo de gerações. O algoritmo genético também mantém o melhor indivíduo para a próxima geração (elitismo).