Dissertação de Mestrado - repositorio.ufpe.br · adquiridas onde a vida já me levou e que eu...

Uma abordagem para a escolha do melhorMétodo de Seleção de Instâncias usando

meta-aprendizagem

Por

Shayane de Oliveira Moura

Dissertação de Mestrado

Universidade Federal de Pernambuco

posgraduacao@cin.ufpe.br

www.cin.ufpe.br/~posgraduacao

Recife, 2015

Universidade Federal de PernambucoCentro de InformáticaPós-graduação em Ciência da Computação

Shayane de Oliveira Moura

Uma abordagem para a escolha do melhor Método deSeleção de Instâncias usando meta-aprendizagem

Este trabalho foi apresentado à Pós-graduação em Ci-

ência da Computação do Centro de Informática da

Universidade Federal de Pernambuco como requisito

parcial para obtenção do grau de Mestre em Ciência

da Computação.

Orientador: George Darmiton da Cunha Cavalcanti

Recife, 2015

Catalogação na fonte

Bibliotecária Jane Souto Maior, CRB4-571

M929a Moura, Shayane de Oliveira Uma abordagem para a escolha do melhor método de seleção

de instâncias usando meta-aprendizagem / Shayane de Oliveira Moura. – Recife: O Autor, 2015.

107 f.: il., fig., tab. Orientador: George Darmiton da Cunha Cavalcanti. Dissertação (Mestrado) – Universidade Federal de

Pernambuco. CIn, Ciência da computação, 2015. Inclui referências.

1. Inteligência artificial. 2. Aprendizagem de máquinas. I. Cavalcanti, George Darmiton da Cunha (orientador). II. Título. 006.3 CDD (23. ed.) UFPE- MEI 2015-162

Dissertação de Mestrado apresentada por Shayane de Oliveira Moura à Pós-Graduação

em Ciência da Computação do Centro de Informática da Universidade Federal de Per-

nambuco, sob o título Uma abordagem para a escolha do melhor Método de Seleção

de Instâncias usando meta-aprendizagem, orientada pelo Prof. George Darmiton

da Cunha Cavalcanti e aprovada pela Banca Examinadora formada pelos professores:

———————————————————————–

Prof. Cleber Zanchettin

Centro de Informática/UFPE

———————————————————————–

Profa. Rita Maria da Silva Julia

Faculdade de Computação / UFU

———————————————————————–

Prof. George Darmiton da Cunha Cavalcanti

Centro de Informática/UFPE

Visto e permitida a impressão.

Recife, 21 de agosto de 2014

—————————————————————————————

Profa. Edna Natividade da Silva Barros

Vice-Coordenador da Pós-Graduação em Ciência da Computação do

Centro de Informática da Universidade Federal de Pernambuco.

Dedico:

À minha mãe, Maria Eunice de Oliveira Moura;

Às minhas irmãs: Charmenha (In memoriam),

Charmile, Charlene e Charline;

Ao meu pai, João Antonio de Moura.

Aos meus sobrinhos: Shayná, Sabrina, Cauã, Lucas e

Laura.

Às minhas tias, às minhas primas, às minhas

Oliveiras!

Agradecimentos

À Deus, pelo desafio da vida, pelo dom de aprender, pelas vitórias já alcançadas e

por me permitir crescer todos os dias.

À UFPE e aos seus professores, pela oportunidade e por todo o aprendizado profis-

sional e pessoal adquirido ao longo desses anos.

Em especial ao professor George Darmiton. Conhecer e trabalhar com você é um

prazer. Com muita competência, sabe ser exigente na medida certa, instigar a busca

por conhecimentos e direcionar bem os seus alunos. É paciente, bem humorado,

cordial, ético, você é exemplar, professor!

Aos professores Cleber Zanchettin e Rita Silva Julia, pela participação na banca de

avaliação deste trabalho e pelas ótimas contribuições fornecidas.

Ao IF Sertão - PE, Campus Ouricuri e a todos os profissionais dessa instituição da

qual tenho orgulho em fazer parte. Obrigada pelo apoio à minha qualificação e ao

apoio financeiro. Espero saber compensar o incentivo!

Ao professor Ágio Felipe, pelo incentivo para eu fazer esse mestrado. Tenho grande

admiração por você como pessoa e como professor.

À Marcelo Bassani e a Halisson Alberdan, pela parceria na realização de todos os

experimentos, pelos ensinamentos que tanto me ajudaram e pela amizade construída.

A participação de vocês foi essencial neste trabalho.

Aos colegas de disciplina, de noites em claro para fazer listas e projetos, aos amigos

que sem os quais esse mestrado não teria sido tão divertido: Leandro Henrique

Espíndola, Davi Hirafuji, Halisson Alberdan e Marcelo Bassani.

À Lorena Brizza e a Crislene Paixão, por todas as broncas, as brincadeiras, a amizade

sincera e por me permitir ter mais um lar, ganhei mais uma família, como as outras

adquiridas onde a vida já me levou e que eu guardo com tanto amor!

Aos meus amigos de sempre, àqueles que fazem eu me sentir segura, que estão

sempre comigo para o que der e vier e que me fazem acreditar que conseguirei tudo:

Iulanda Nascimento, Sherly Gabriela, Tamiris Santos, família Gama, Enilce Lima,

Marla Maria Ms, Elizângela Sousa, Karine Vasconcelos, Nadjane Lopes, Joselha Mateus,

Raquel Brígido, Lyrane Brito, Sâmmia Alcântara, Débora Farias, Ana Marina Lemos, ...

enfim, que esses representem todos os amigos que sabem que meu amor é recíproco.

Ao mestrado, não apenas pelo crescimento, como também, pelos amigos que me

trouxe: além de todos os já agradecidos acima, Luma Seixa, Alysson Bispo, Francisco

Kbça, Peter Keays, Elizane Moraes, Renata da Hora, Leonardo Dorneles, Alysson José,

Jesús Pavón, Ammis Sánchez, Jean Teixeira, Maria Clara Bezerra, Anderson Elias,

George Gomes, porteiros do INOCOOP...

Ao mestrado. Obrigada mestrado, por me fazer conhecer Antonio Jorge Fontenele

Neto, que durante esse percurso foi Jorge, Antonio, Tonho, Neto e agora é meu Tonho!

Ao meu Tonho pelo mestrado! Em qual segundo desse período não estivemos

juntos? O nosso Recife! Quantas ideias, angústias, alegrias, tarefas, desafios, experi-

ências novas, momentos incríveis nós compartilhamos! Meu Tonho, muito obrigada

principalmente nesta etapa final, por ter acompanhado a minha rotina, pela força,

pelo amor, por trabalharmos juntos e conseguirmos tantas coisas. Você é sensacional!

Obrigada mestrado e Recife por fazer essa amizade se tornar um amor tão especial!

Amo você, Tonho!

Por fim, à família Oliveira! Como é maravilhoso fazer parte de vocês! Como é

bom saber que vocês são o meu maior exemplo de amor, honestidade, amizade,

compreensão, união, luta e vitória. Mãe, Charmenha (In memoriam), Charmile,

Charlene, Charline e pai, obrigada por ajudarem a me construir, vocês me ensinam

todo dia a ter coragem, fé e amor.

Repito por pura alegria de viver:

a salvação é pelo risco, sem o qual a vida não vale a pena!

—CLARICE LISPECTOR

Resumo

Os sistemas de Descoberta de Conhecimentos em Bases de Dados (mais conheci-

dos como sistemas KDD) e métodos de Aprendizagem de Máquinas preveem situações,

agrupam e reconhecem padrões, entre outras tarefas que são demandas de um mundo

no qual a maioria dos serviços está sendo oferecido por meio virtual. Apesar dessas

aplicações se preocuparem em gerar informações de fácil interpretação, rápidas e

confiáveis, as extensas bases de dados utilizadas dificultam o alcance de precisão

unida a um baixo custo computacional. Para resolver esse problema, as bases de

dados podem ser reduzidas com o objetivo de diminuir o tempo de processamento e

facilitar o seu armazenamento, bem como, guardar apenas informações suficientes e

relevantes para a extração do conhecimento. Nesse contexto, Métodos de Seleção de

Instâncias (MSIs) têm sido propostos para reduzir e filtrar as bases de dados, selecio-

nando ou criando novas instâncias que melhor as descrevam. Todavia, aqui se aplica

o Teorema do No Free Lunch, ou seja, a performance dos MSIs varia conforme a base e

nenhum dos métodos sempre sobrepõe seu desempenho aos demais. Por isso, esta

dissertação propõe uma arquitetura para selecionar o “melhor” MSI para uma dada

base de dados (mais adequado em relação à precisão), chamada Meta-CISM (Meta-

learning for Choosing Instance Selection Method). Estratégias de meta-aprendizagem

são utilizadas para treinar um meta-classificador que aprende sobre o relacionamento

entre a taxa de acerto de MSIs e a estrutura das bases. O Meta-CISM utiliza ainda

reamostragem e métodos de seleção de atributos para melhorar o desempenho do

meta-classificador. A proposta foi avaliada com os MSIs: C-pruner, DROP3, IB3, ICF e

ENN-CNN. Os métodos de reamostragem utilizados foram: Bagging e Combination

(método proposto neste trabalho). Foram utilizados como métodos de seleção de

atributos: Relief-F, CFS, Chi Square Feature Evaluation e Consistency-Based Subset

Evaluation. Cinco classificadores contribuíram para rotular as meta-instâncias: C4.5,

PART, MLP-BP, SMO e KNN. Uma MLP-BP treinou o meta-classificador. Os experi-

mentos foram realizados com dezesseis bases de dados públicas. O método proposto

(Meta-CISM) foi melhor que todos os MSIs estudados, na maioria dos experimentos

realizados. Visto que eficientemente seleciona um dos três melhores MSIs em mais de

85% dos casos, a abordagem é adequada para ser automaticamente utilizada na fase

de pré-processamento das base de dados.

Palavras-chave: Aprendizagem de Máquinas. Mineração de Dados. Meta-aprendizagem.

Métodos de Seleção de Instâncias (MSI). Meta-CISM.

Abstract

The systems for Knowledge Discovery in Databases (better known as KDD systems)

and Machine Learning methods predict situations, recognize and group (cluster) pat-

terns, among other tasks that are demands of a world in which the most of the services

is being offered by virtual ways. Although these applications are concerned in gene-

rate fast, reliable and easy to interpret information, extensive databases used for such

applications make difficult achieving accuracy with a low computational cost. To solve

this problem, the databases can be reduced aiming to decrease the processing time

and facilitating its storage, as well as, to save only sufficient and relevant information

for the knowledge extraction. In this context, Instances Selection Methods (ISMs) have

been proposed to reduce and filter databases, selecting or creating new instances that

best describe them. Nevertheless, No Free Lunch Theorem is applied, that is, the ISMs

performance varies according to the base and none of the methods always overco-

mes their performance over others. Therefore, this work proposes an architecture to

select the "best"ISM for a given database (best suited in relation to accuracy), called

Meta-CISM (Meta-learning for Choosing Instance Selection Method). Meta-learning

strategies are used to train a meta-classifier that learns about the relationship between

the accuracy rate of ISMs and the bases structures. The Meta-CISM still uses resam-

pling and feature selection methods to improve the meta-classifier performance. The

proposal was evaluated with the ISMs: C-pruner, DROP3, IB3, ICF and ENN-CNN.

Resampling methods used were: Bagging and Combination (method proposed in this

work). The Feature Selection Methods used were: Relief-F, CFS, Chi Square Feature

Evaluation e Consistency-Based Subset Evaluation. Five classifiers contributed to label

the meta-instances: C4.5, PART, MLP-BP, SMO e KNN. The meta-classifier was trained

by a MLP-BP. Experiments were carried with sixteen public databases. The proposed

method (Meta-CISM) was better than all ISMs studied in the most of the experiments

performed. Since that efficiently selects one of the three best ISMs in more than 85%

of cases, the approach is suitable to be automatically used in the pre-processing of the

databases.

Keywords: Machine Learning. Data Mining. Meta-learning. Instance Selection

Method (ISM). Meta-CISM

Lista de Figuras

2.1 Estrutura de uma árvore de decisões. A partir do melhor atributo, os

dados são divididos, um novo atributo é escolhido, até que um critério de

parada seja satisfeito e as classes estejam representadas nas folhas. . . . . . 30

2.2 Classificação de uma instância desconhecida com KNN. O conjunto T é

usado para classificar uma instância desconhecida x, com a classe c1 ou c2,

por voto majoritário. Para k = 3, a instância é classificada como pertencente

à classe c2. Para k = 5, a instância é classificada com a classe c1. E para k = 7,

a instância é novamente classificada como pertencente à classe c2. Isso

mostra a influência da escolha do valor de k no algoritmo KNN. . . . . . . . 32

2.3 Neurônio Artificial. O Combinador linear (∑

) faz a soma ponderada dos

sinais de entrada do neurônio ( f1, f2, . . . , fn), multiplicados pelos seus

respectivos pesos (w1, w2, . . . , wn), com o Limiar de ativação (θ). Caso

o potencial de ativação (u), resultado do somatório, seja positivo, produz

um potencial excitatório, caso negativo, produz um potencial inibitório. O

potencial de ativação é limitado pela função de ativação (g ) para gerar a

saída do neurônio (y). Fonte: Adaptado de SILVA; SPATTI; FLAUZINO (2010) 33

2.4 Multilayer Perceptron - MLP. Possui uma camada de entrada LE com

N1, . . . , Np neurônios correspondentes às variáveis de entrada de cada

exemplo a ser mostrado para a rede. Em seguida, as camadas escondi-

das L1, . . . ,L j podem ter quantidades de neurônios diferentes(Nq , Nr

), a

depender da topologia escolhida para a rede. E a última camada é a ca-

mada de saída LS que tem um neurônio para cada saída possível da MLP

(N1, . . . , Ns). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.5 Exemplo de como PART constrói uma árvore de decisões parcial. Está-

gio 1 - um teste divide as instâncias em nós (em cinza porque não foram

expandidos ainda). Estágio 2 - O nó 3 com menor entropia é expandido.

Estágio 3 - o nó com menor entropia é uma folha (preto), então começa

o retrocesso a partir da expansão do nó 5. Estágio 4 - a expansão do nó

5 gera apenas folhas, desse modo, inicia-se a poda da árvore. O nó 5 e o

nó 3 viram folhas. Estágio 5 - continua o retrocesso e o próximo nó com

menor entropia é o 4, que é expandido em folhas, mas não obedece à regra

de substituição da subárvore. A construção da árvore de decisões parcial

encerra com 3 folhas em 5 estágios. Fonte: FRANK; WITTEN (1998) . . . . 38

2.6 Separação de duas classes com hiperplanos. Uma base de dados com

classes linearmente separáveis tem suas classes facilmente distintas com

várias possibilidades de hiperplanos. . . . . . . . . . . . . . . . . . . . . . . . . 40

2.7 Hiperplano aleatório separativo de duas classes. Um hiperplano esco-

lhido aleatoriamente pode errar ao classificar novos exemplos. . . . . . . . 40

2.8 Hiperplano a partir de uma SVM. Um hiperplano escolhido por uma SVM

procura estar equidistante das classes e possuir a maior margem possível

(mg ), diminuindo a possibilidade de erro de classificação. . . . . . . . . . . 41

2.9 Mudança de dimensão e separação linear de conjuntos não linearmente

separáveis. As figuras a) e c) representam os conjuntos em suas dimensões

originais de classes não-linearmente separáveis, unidimensional e bidi-

mensional, respectivamente. Em em b) e d) a mudança de dimensão de

a) e c) para 2 dimensões e 3 dimensões, respectivamente, torna possível a

separação linear de suas classes. . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.10 Restrições dos multiplicadores de Lagrange. As restrições de desigual-

dade fazem os multiplicadores pertencerem a uma caixa. Enquanto a res-

trição de igualdade linear faz pertencerem a uma linha diagonal. Portanto,

um passo do SMO deve encontrar um ponto ótimo da função objetivo

sobre um segmento de linha diagonal. Fonte: PLATT (1999) . . . . . . . . . 47

2.11 Base de dados antes e depois da aplicação de um MSI. Antes de aplicar

um método de seleção de instâncias (MSI), a base pode ter ruídos, instân-

cias irrelevantes e não distinguir bem as classes, após a aplicação de um

MSI a base tende a se tornar mais sucinta e ao mesmo tempo mais eficiente. 57

2.12 Modelo do processo de seleção de características com validação. Inici-

almente, os subconjuntos são gerados e em seguida avaliados, até que

obedeçam o critério de parada e sigam para validação. Fonte: DASH; LIU

(1997) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.1 Processo de construção da Meta-base e treinamento do meta-classificador.

Cada base de dados é submetida à fase de reamostragem para aumentar

o número de bases de dados disponíveis. Cada nova base de dados passa

pelos processos de Extração de características e Anotação para tornar-se

uma meta-instância. A meta-base resultante pode ser reduzida pelo pro-

cesso de Seleção de Características. Em seguida, é usada para treinar o

meta-classificador F. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

3.2 Módulo de Anotação. Cada base de dados Γi j é reduzida por N diferentes

MSIs e as precisões das bases de dados resultantes Ωl são calculadas como

a média dos M classificadores cm. O rótulo é o MSI com a maior média de

precisão. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.3 Avaliação do Meta-classificador. Cada base de dados de teste tem suas

meta-características extraídas. A quantidade de meta-características pode

ser reduzida se o módulo de seleção de atributos for utilizado. Finalmente,

são submetidas ao meta-classificador treinado F para obter o MSI mais

adequado para a base de dados de entrada ∆. . . . . . . . . . . . . . . . . . . 88

4.1 Parâmetro K para KNN. Taxas de acerto com barras de erro para cada

meta-base em relação a cada valor de K. . . . . . . . . . . . . . . . . . . . . . . 92

4.2 Camadas escondidas para MLP-BP (meta-base mbBagging ). Com a meta-

base mbBagging, é exibida a influência da quantidade neurônios em uma

camada escondida sobre a taxa de acerto, a partir das possíveis variações

de taxa de aprendizado e momento. . . . . . . . . . . . . . . . . . . . . . . . . 93

4.3 Camadas escondidas para MLP-BP (meta-base mbCombination). Com

a meta-base mbCombination, é exibida a influência da quantidade neurô-

nios em uma camada escondida sobre a taxa de acerto, a partir das possí-

veis variações de taxa de aprendizado e momento. . . . . . . . . . . . . . . . 94

4.4 Camadas escondidas para MLP-BP (meta-base mbBaggingCombination).

Com a meta-base mbBaggingCombination, é exibida a influência da quan-

tidade de neurônios em uma camada escondida sobre a taxa de acerto, a

partir das possíveis variações de taxa de aprendizado e momento. . . . . . 95

4.5 Taxa de aprendizado e momento para MLP-BP. Taxas de acerto individu-

ais e média das taxas de acerto de todas as meta-bases, por combinação de

taxa de aprendizado com momento, para indicação da combinação mais

adequada a ser utilizada na MLP-BP. . . . . . . . . . . . . . . . . . . . . . . . . 96

4.6 Avaliação de meta-classificadores. Taxas de acerto dos meta-classificadores:

KNN, MLP-PB, PART e C4.5 sobre as meta-bases: mbBagging, mbCombina-

tion e mbBaggingCombination . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.7 Algoritmos de busca para Consistency-based Subset Evaluation. Taxas

de acerto do meta-classificador MLP-BP para as meta-bases: mbBagging,

mbCombination e mbBaggingCombination, aplicadas ao método de sele-

ção de atributos Consistency-based Subset Evaluation com os algoritmos

de busca: Best First Search e Genetic Search. . . . . . . . . . . . . . . . . . . . 98

4.8 Algoritmos de busca para Correlation-based Feature Selection - CFS. Ta-

xas de acerto do meta-classificador MLP-BP para as meta-bases: mbBag-

ging, mbCombination e mbBaggingCombination, aplicadas ao método

de seleção de atributos Correlation-based Feature Selection - CFS com os

algoritmos de busca: Best First Search e Genetic Search. . . . . . . . . . . . . 99

4.9 Taxas de acerto relativas às variações do número de atributos no ran-

king para Chi Square Feature Evaluation. Taxas de acerto do meta-classificador

MLP-BP para as meta-bases: mbBagging, mbCombination e mbBagging-

Combination, aplicadas ao método de seleção de atributos Chi Square

Feature Evaluation com variação do número de atributos no ranking de 1

a 30. Os pontos em destaque correspondem às quantidades de atributos

escolhidas para cada meta-base. . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.10 Taxas de acerto relativas às variações do número de atributos no ran-

king para Relief - F . Taxas de acerto do meta-classificador MLP-BP para as

meta-bases: mbBagging, mbCombination e mbBaggingCombination, apli-

cadas ao método de seleção de atributos Relief - F com variação do número

de atributos no ranking de 1 a 30. Os pontos em destaque correspondem

às quantidades de atributos escolhidas para cada meta-base. . . . . . . . . 100

4.11 Histograma das meta-caracteríticas selecionadas pelos Métodos de Se-

leção de Atributos. Frequência de escolha de cada meta-característica

(no range de 0 a 12), considerando a soma dos resultados de cada meta-

base (mbBagging, mbCombination e mbBaggingCombination) submetida

a todos os Métodos de Seleção de Atributos (Consistency-based Subset Eva-

luation com Best First Search, Correlation-based Feature Selection - CFS

com Genetic Search, Chi Square Feature Evaluation e Relief - F ) . . . . . . . 101

4.12 Taxas de acerto alcançadas com o uso de métodos de seleção de atribu-

tos sobre a meta-base mbBagging . Resultado dos classificadores sobre

a meta-base mbBagging quando submetida aos quatro métodos de sele-

ção de atributos (Consistency-based Subset Evaluation, Correlation-based

Feature Selection - CFS, Chi Square Feature Evaluation e Relief - F ). . . . . . 103

4.13 Taxas de acerto alcançadas com o uso de métodos de seleção de atribu-

tos sobre a meta-base mbCombination. Resultado dos classificadores so-

bre a meta-base mbCombination quando submetida aos quatro métodos

de seleção de atributos (Consistency-based Subset Evaluation, Correlation-

based Feature Selection - CFS, Chi Square Feature Evaluation e Relief - F ). . 104

4.14 Taxas de acerto alcançadas com o uso de métodos de seleção de atribu-

tos sobre a meta-base mbBaggingCombination. Resultado dos classifi-

cadores sobre a meta-base mbBaggingCombination) quando submetida

aos quatro métodos de seleção de atributos (Consistency-based Subset

Evaluation, Correlation-based Feature Selection - CFS, Chi Square Feature

Evaluation e Relief - F ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4.15 Desempenho de Meta-CISM sem seleção de atributos para a meta-base

mbBagging. O gráfico apresenta as médias dos resultados de precisão

dos MSIs estudados e de Meta-CISM para as bases de dados geradas por

Bagging, separadas por classificador. . . . . . . . . . . . . . . . . . . . . . . . . 106

4.16 Desempenho de Meta-CISM sem seleção de atributos para a meta-base

mbCombination. O gráfico apresenta as médias dos resultados de precisão

dos MSIs estudados e de Meta-CISM para as bases de dados geradas por

Combination, separadas por classificador. . . . . . . . . . . . . . . . . . . . . 107

4.17 Desempenho de Meta-CISM sem seleção de atributos para a meta-base

mbBaggingCombination. O gráfico apresenta as médias dos resultados de

precisão dos MSIs estudados e de Meta-CISM para para as bases de dados

geradas por Bagging e Combination juntas, separadas por classificador. . . 107

4.18 Taxas de ranking de Meta-CISM sem seleção de atributos para a meta-

base mbBagging. Os MSIs foram ordenados em ranking pela média das

precisões dos classificadores para cada base, a fim de mostrar com que

frequência o Meta-CISM escolhe os melhores MSIs. O gráfico apresenta o

ranking das bases correspondentes à meta-base mbBagging. . . . . . . . . 110

4.19 Taxas de ranking de Meta-CISM sem seleção de atributos para a meta-

base mbCombination. Os MSIs foram ordenados em ranking pela média

das precisões dos classificadores para cada base, a fim de mostrar com que

frequência o Meta-CISM escolhe os melhores MSIs. O gráfico apresenta o

ranking das bases correspondentes à meta-base mbCombination. . . . . . 111

4.20 Taxas de ranking do Meta-CISM sem seleção de atributos para a meta-

base mbBaggingCombination. Os MSIs foram ordenados em ranking pela

média das precisões dos classificadores para cada base, a fim de mostrar

com que frequência o Meta-CISM escolhe os melhores MSIs. O gráfico

apresenta o ranking das bases correspondentes à meta-base mbBagging-

Combination. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

4.21 Desempenho do Meta-CISM com seleção de atributos para a meta-base

mbBagging. O gráfico apresenta a média dos resultados de precisão do

Meta-CISM com e sem o módulo de seleção de atributos, separadas por

classificador, para as bases de dados geradas por Bagging. . . . . . . . . . . 113

4.22 Desempenho do Meta-CISM com seleção de atributos para a meta-base

mbCombination. O gráfico apresenta a média dos resultados de precisão

do Meta-CISM com e sem o módulo de seleção de atributos, separadas por

classificador, para as bases de dados geradas por Combination. . . . . . . . 114

4.23 Desempenho do Meta-CISM com seleção de atributos para a meta-base

mbBaggingCombination. O gráfico apresenta a média dos resultados de

precisão do Meta-CISM com e sem o módulo de seleção de atributos,

separadas por classificador, para as bases de dados geradas por mbBag-

gingCombination. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Lista de Tabelas

2.1 Características dos métodos de seleção de atributos utilizados . . . . . . . . 72

3.1 Medidas de caracterização dos dados . . . . . . . . . . . . . . . . . . . . . . . 86

4.1 Informações das bases de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.2 Quantidade de neurônios para primeira camada escondida de uma MLP-BP 93

4.3 Atributos selecionados por cada Método de Seleção de Atributos . . . . . . 102

4.4 Médias de precisão para cada MSI avaliados por cinco classificadores

(meta-base mbBagging ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.5 Médias de precisão para cada MSI avaliados por cinco classificadores

(meta-base mbCombination). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.6 Médias de precisão para cada MSI avaliados por cinco classificadores

(meta-base mbBaggingCombination). . . . . . . . . . . . . . . . . . . . . . . 106

4.7 Teste de Friedman para os resultados do Meta-CISM e demais MSIs estuda-

dos, aplicados às meta-bases mbBagging, mbCombination e mbBagging-

Combination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4.8 Teste de Wilcoxon comparando Meta-CISM × MSIs . . . . . . . . . . . . . . . 109

4.9 Teste de Holm-Bonferroni comparando Meta-CISM × MSIs . . . . . . . . . 110

4.10 Comparação das médias de precisão do Meta-CISM com e sem o módulo

de seleção de atributos (meta-base mbBagging ). . . . . . . . . . . . . . . . . 112

4.11 Comparação das médias de precisão do Meta-CISM com e sem o módulo

de seleção de atributos (meta-base mbCombination). . . . . . . . . . . . . . 112

4.12 Comparação das médias de precisão do Meta-CISM com e sem o módulo

de seleção de atributos (meta-base mbBaggingCombination). . . . . . . . 113

4.13 Teste de Friedman para os resultados do Meta-CISM com a aplicação de

Métodos de Seleção de Atributos nas meta-bases mbBagging, mbCombina-

tion e mbBaggingCombination. . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

4.14 Redução do tempo para o cálculo das meta-características com o uso do

Módulo de Seleção de Atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Lista de Acrônimos

AM Aprendizagem de Máquina

CFS Consistency-based Subset Evaluation

CNN Condensed Nearest Neighbor

DM Data Mining

DROP3 Decremental Reduction Optimization Procedure 3

ENN Edited Nearest Neighbor

HVDM Heterogeneous Value Difference Metric

IB3 Instance Based 3

ICF Iterative Caise Filtering

KBIS Knowledge-base IS

KDD Knowledge Discovery in Databases

KKT Condições Karush-Kuhn-Tucker

KNN K Nearest Neighbors

META-CISM Meta-learning for Choosing Instance Selection Method

MLP-BP Multilayer Perceptron com Backpropagation

MSA Método de Seleção de Atributos

MSI Método de Seleção de Instâncias

RNA Rede Neural Artificial

SA Sistemas de Aprendizagem

SMO Sequential Minimal Optimization

SVM Support Vector Machine

Sumário

1 Introdução 20

1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.3 Estrutura do documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2 Conceitos básicos 25

2.1 Aprendizagem de máquinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 Classificação de Padrões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.1 C4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.2 K - Nearest Neighbor (KNN) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.2.3 Multilayer Perceptron - MLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2.4 PART . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.2.5 Sequential Minimal Optimization (SMO) . . . . . . . . . . . . . . . . . . . . 39

2.3 Meta-aprendizagem e caracterização de dados . . . . . . . . . . . . . . . . 50

2.4 Métodos de seleção de instâncias . . . . . . . . . . . . . . . . . . . . . . . . 56

2.4.1 ENN-CNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.4.2 Instance Based 3 - IB3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

2.4.3 Decremental Reduction Optimization Procedure 3 - DROP3 . . . . . . . . 63

2.4.4 Iterative Caise Filtering - ICF . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

2.4.5 C-pruner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.5 Métodos de seleção de atributos . . . . . . . . . . . . . . . . . . . . . . . . . 69

2.5.1 Consistency-based Subset Evaluation . . . . . . . . . . . . . . . . . . . . . . 72

2.5.2 Correlation-based Feature Selection - CFS . . . . . . . . . . . . . . . . . . . 73

2.5.3 Chi Square Feature Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 74

2.5.4 Relief - F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

2.6 Métodos de reamostragem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

2.6.1 Bagging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

2.7 Trabalhos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3 Meta-CISM

Meta-learning for Choosing Instance Selection Method 79

3.1 Geração do meta-classificador F . . . . . . . . . . . . . . . . . . . . . . . . 80

3.1.1 Reamostragem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.1.1.1 Proposta de reamostragem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.1.2 Geração de meta-instância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

3.1.3 Seleção de atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.1.4 Treinamento do meta-classificador . . . . . . . . . . . . . . . . . . . . . . . . 88

3.2 Avaliação do meta-classificador F . . . . . . . . . . . . . . . . . . . . . . . . 88

4 Estudo Experimental 89

4.1 Bases de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.2 Configurações para o Módulo de Anotação . . . . . . . . . . . . . . . . . . 91

4.3 Meta-classificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.3.1 Configuração de parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.3.1.1 Parâmetros para KNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

4.3.1.2 Parâmetros para MLP-BP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

4.3.2 Avaliação dos meta-classificadores . . . . . . . . . . . . . . . . . . . . . . . . 96

4.4 Métodos de seleção de atributos . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.4.1 Configuração de parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4.4.2 Avaliação dos métodos de seleção de atributos . . . . . . . . . . . . . . . . . 103

4.5 Avaliação do Meta-CISM sem seleção de atributos . . . . . . . . . . . . . . 105

4.6 Avaliação do Meta-CISM com seleção de atributos . . . . . . . . . . . . . . 112

4.7 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

5 Conclusões 119

5.1 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Referências 122

202020

1Introdução

1.1 Motivação

Ao abrirmos e-mails, redes sociais ou quando apenas nos conectamos à internet,

recebemos, adicionalmente, recomendações de leituras, compras, pessoas a curtir,

jogos e muitas outras propostas que nos impressionam porque, na maioria das vezes,

tais recomendações são exatamente o que nos interessa. O sistema parece nos conhe-

cer. E de fato, ele nos conhece. A cada clique, geramos informações que são guardadas

e analisadas para gerar o nosso perfil. Entregamos informações suficientes para traçar

um perfil do que nós somos de acordo com o foco do sistema, seja comportamento,

gostos, consumo, etc.

Outra situação curiosa envolve organizações que precisam analisar as tendências

políticas, sociais e econômicas. Por exemplo, empresas que precisam tomar decisões

de negócios, avaliar clientes ou procurar possíveis clientes. Essas empresas usam a tec-

nologia para identificar os padrões de consumo, analisam os perfis, procuram padrões

e tendências a partir de dados de outras empresas, dados históricos, econômicos e

resultados anteriores de suas próprias ações. Sistemas de segurança também estão

aliados à tecnologia para guardar informações, dar permissões, auxiliar investigações,

como no caso do uso de câmeras para reconhecer pessoas e observar situações sus-

peitas. Na medicina, investigações sobre doenças, com o uso da teconologia para

analisar sintomas, também têm trazido grandes avanços ao setor.

Essas situações são algumas de muitas que têm em comum a formação de grandes

bases de dados e o uso dessas em Processos de Descoberta de Conhecimento em

Bases de Dados, em inglês, Knowledge Discovery in Databases - KDD. Um campo

multidisciplinar que envolve: aprendizado de máquinas, reconhecimento de padrões,

banco de dados, estatística, sistemas especialistas, entre outros. Os processos KDD

estão em evidência pela vasta aplicação em um mundo no qual a maioria dos serviços

está sendo oferecido com facilidade, conforto e segurança, por meio virtual. Assim, a

1.1. MOTIVAÇÃO 21

abundância de dados disponíveis e as informações que estes dados podem fornecer

não podem deixar de ser aproveitadas. Bases de dados são formadas e submetidas aos

processos KDD para extração do conhecimento implícito nos dados, úteis à descoberta

de padrões e tomadas de decisões. Um processo KDD possui etapas interligadas

que podem ocorrer em um ciclo iterativo: consolidação dos dados, seleção e pré-

processamento, mineração de dados (Data Mining ) e interpretação.

Mineração de dados é uma etapa normalmente confundida com o processo com-

pleto de KDD. No entanto, essa etapa corresponde à aplicação de uma técnica (geral-

mente de aprendizagem de máquinas) que descobrirá padrões nos dados. O tempo

de processamento e a precisão dos resultados da Mineração de dados são os fatores

mais importantes para a obtenção de bons resultados do processo KDD. Tempo e

precisão estão diretamente ligados à qualidade dos dados trazidos pela etapa anterior:

seleção e pré-processamento. Na etapa de seleção e pré-processamento, os dados são

submetidos a técnicas capazes de melhorar o subconjunto de exemplos e transformar

os dados para adequá-los ao processo de mineração a ser utilizado. Apesar de outros

contextos de aprendizagem de máquinas também disporem de grandes bases de da-

dos para tratamento, processos KDD têm sido os maiores impulsores dessas extensas

bases e da necessidade de pré-processamento delas.

Diante dessa necessidade de pré-processamento de bases de dados, surgem os

Métodos de Seleção de Instâncias (MSIs). Um Método de Seleção de Instância (MSI)

é um algoritmo de pré-processamento que busca eliminar nos dados disponíveis,

instâncias redundantes, irrelevantes e ruidosas que não ajudam ou até prejudicam o

resultado final do processo no qual serviu como pré-processamento. A redução de

uma base com um MSI pode melhorar os resultados do processo completo, reduzir o

custo computacional e reduzir a necessidade de armazenamento da base de dados.

O uso de Métodos de Seleção de Instâncias pode focar em um de dois objetivos

principais:

• manter ou melhorar a precisão final, reduzindo a base de dados o máximo

possível;

• ou, reduzir a base de dados o máximo possível, mesmo que haja uma perda

tolerável de precisão;

Mais de cem MSIs têm sido propostos nas últimas décadas GARCÍA; LUENGO;

HERRERA (2015). O problema é que cada um trata os dados de maneira diferente, e

desse modo, têm resultados finais com desempenhos diferentes. Alguns conseguem

lidar melhor com bases que possuem valores faltantes, outros com bases ruidosas,

outros apenas com duas classes, outros não são bons com atributos categóricos, ou a

distribuição espacial e estatística dos dados influencia no desempenho. E assim, a

composição da base que o algoritmo precisa reduzir influencia, tanto no resultado

1.1. MOTIVAÇÃO 22

de precisão, quanto de redução. Portanto, a performance dos MSIs varia de acordo

com as bases de dados nas quais eles são aplicados. Peculiaridades destas bases criam

ambientes que são mais adequados a alguns métodos que outros. Os trabalhos de

REINARTZ (2002), KIM; OOMMEN (2003a) e CZARNOWSKI; JEDRZEJOWICZ (2006)

corroboram que a falta de um MSI que constantemente se sobreponha aos demais,

direciona pesquisas recentes à busca de formas para definir o MSI mais adequado

para cada base de dados.

Neste trabalho, levamos em conta a precisão após a aplicação do MSI e deixamos a

análise de redução das bases de dados fora do escopo. Considerando que um algo-

ritmo de seleção de instâncias será aplicado, utilizamos MSIs de abordagens distintas,

como ENN-CNN que é uma junção do algoritmo de condensação e incremental Con-

densed Nearest Neighbor - CNN (HART, 1968) com o algoritmo de edição e decremental

Edited Nearest Neighbor - ENN (WILSON, 1972), proposto por CAISES et al. (2011). E

além desse, utilizamos métodos híbridos (em relação à condensação e edição) que se

diferenciam na direção de pesquisa: Instance Based 3 - IB3 (AHA; KIBLER; ALBERT,

1991), com direção de pesquisa incremental; C-pruner (ZHAO et al., 2003) e Decremen-

tal Reduction Optimization Procedure 3 - DROP3 (WILSON; MARTINEZ, 2000), os dois

com direção de pesquisa decremental; e Iterative Caise Filtering - ICF (BRIGHTON;

MELLISH, 2002), com direção de pesquisa em lote.

Investigamos qual dos MSIs utilizados fornece a melhor precisão. Por conseguinte,

propomos uma arquitetura para escolher o “melhor” método de seleção de instâncias

para uma nova base de dados, o Meta-CISM (Meta-learning for Choosing Instance

Selection Method).

A arquitetura proposta é baseada em meta-aprendizagem. Modelos comuns de

aprendizagem estruturam características de um problema real em forma de bases

de dados e a partir dessas aprendem o comportamento do sistema que as gerou.

Com o aprendizado, são capazes de prever os resultados do sistema em novas bases

representantes de outros problemas semelhantes. Esse é um sitema de aprendizagem

(SA). Meta-aprendizagem é o aprendizado sobre os sistemas de aprendizagem, na

qual várias bases dos SAs são estudadas.

Ao invés de modelar os problemas reais para uma base de dados, cada base que

serviu de entrada para um SA, é modelada para ser uma meta-instância de uma meta-

base a ser utilizada em outro sistema de aprendizagem. Características da estrutura

da base são extraídas para a geração de meta-características ou meta-atributos. A

denominação meta-aprendizagem se dá à aprendizagem sobre a meta-base formada.

Usando meta-aprendizagem, a arquitetura proposta aprende como os MSIs se

comportam dependendo da estrutura da base que lhe é aplicada. Para cada base de

treinamento, é obtida a indicação do MSI com “melhor” desempenho em precisão.

O sistema de meta-aprendizagem avalia a relação entre as características da base

1.2. OBJETIVO 23

(meta-características) e o MSI que tem melhor desempenho para ela (meta-classe),

identificando relações de dependência. Com o aprendizado dessa dependência entre a

estrutura da base e o MSI que “melhor” lida com ela, o sistema de meta-aprendizagem

pode prever para novas bases aquele MSI que terá a melhor precisão.

Propomos uma arquitetura que usa reamostragem na fase inicial para aumen-

tar a quantidade de bases a serem estudados e assim obter melhor generalização.

Estruturamos o sistema de meta-aprendizagem com uma fase de extração das meta-

características e outra para a obtenção das meta-classes. Verificamos as melho-

res meta-características a serem usadas no treinamento com um módulo de sele-

ção de atributos. Treinamos o meta-classificador e obtemos uma função de um

meta-classificador treinado. Indicamos ainda as etapas para o uso e teste do meta-

classificador treinado. Finalmente, analisamos os resultados dos experimentos reali-

zados e verificamos se Meta-CISM é uma boa opção para a fase de pré-processamento

de dados.

1.2 Objetivo

Esta dissertação busca contribuir com as pesquisas relacionadas ao uso de meta-

aprendizagem para a escolha de Métodos de Seleção de Instâncias (MSIs). Para este

fim, sugere uma arquitetura para a escolha automática de um MSI adequado para

uma dada base de dados, de forma a obter a melhor precisão possível. Junto a essa

arquitetura, propõe-se a apresentar os conceitos envolvidos em processos de meta-

aprendizagem e em seleção de instâncias, assim como, investigar a inclusão de outros

métodos de aprendizagem de máquinas no processo.

Mais especificamente, objetiva:

• Sugerir a arquitetura: Meta-CISM (Meta-learning for Choosing Instance Selection

Method).

• Utilizar meta-aprendizagem como meio para indicação do MSI mais apropriado

dada uma nova base de dados.

• Incluir métodos de Reamostragem para diminuir a dependência do método

proposto às grandes quantidades de bases disponíveis para treino.

• Avaliar meta-características e a utilização de Métodos de Seleção de Atributos

(MSAs) na arquitetura proposta.

1.3. ESTRUTURA DO DOCUMENTO 24

1.3 Estrutura do documento

Este documento tem a seguinte estrutura:

Capítulo 1 - Contextualiza os Métodos de Seleção de Instâncias e explica a neces-

sidade de uma abordagem para a escolha do “melhor” método a ser

aplicado. Além disso, define os objetivos do estudo e descreve a estrutura

deste documento.

Capítulo 2 - As técnicas utilizadas nos experimentos são explanadas e são apresenta-

das as premissas para entendimento da arquitetura proposta.

Capítulo 3 - A arquitetura Meta-CISM (Meta-learning for Choosing Instance Selection

Method) é apresentada.

Capítulo 4 - Os experimentos realizados são relatados e seus resultados são avaliados.

Capítulo 5 - Mostra as contribuições que este trabalho fornece às pesquisas envolvi-

das em Métodos de Seleção de Instâncias e em meta-aprendizagem. São

apresentadas as conclusões extraídas dos estudos realizados associados

aos resultados obtidos com os experimentos da arquiterura proposta. In-

dicações para pesquisas complementares também estão presentes neste

capítulo.

252525

2Conceitos básicos

Este capítulo traz uma revisão dos conceitos básicos e das principais contribuições

da literatura necessárias ao estudo proposto. Inicialmente, a Aprendizagem de Má-

quinas é apresentada na Seção 2.1. Em seguida, a Seção 2.2 especifica o estudo para

a aprendizagem supervisionada e mostra os algoritmos de classificação escolhidos.

A Seção 2.3 fornece os conceitos de meta-aprendizagem e detalha as medidas de

caracterização de dados utilizadas. A Seção 2.4 discorre sobre os métodos de seleção

de instâncias existentes e o porquê dos escolhidos para experimentação. Na Seção 2.5,

os métodos de seleção de atributos utilizados são apresentados. A Seção 2.6 define

reamostragem e explica o método Bagging executado. Enfim, a Seção 2.7 mostra

como pesquisadores vêm trabalhando na área e qual a inovação deste trabalho.

2.1 Aprendizagem de máquinas

Entre seres vivos, relacionamos a inteligência com a capacidade dos indivíduos

de aprender. Não obstante, em Inteligência Artificial, essa capacidade também tem

grande relevância e é estudada pela subárea chamada de Aprendizagem de Máquinas

(AM) (MICHALSKI, 1986).

Programadores não são capazes de prever todas as situações possíveis ou as mu-

danças ocorridas com o passar do tempo, e muitas vezes não sabem encontrar a

solução de um problema diretamente. Nesse sentido, a Aprendizagem de Máquinas é

o caminho para que os algoritmos criados sejam os próprios responsáveis por encon-

trar soluções, adaptar-se e melhorar seus desempenhos com experiências anteriores.

O objetivo da AM é criar algoritmos capazes de generalizar comportamentos para

que os sistemas saibam agir em novas situações, de acordo com um conhecimento

adquirido de forma automática.

Os conceitos abaixo são premissas para entender o funcionamento de algoritmos

de aprendizagem de máquinas:

2.1. APRENDIZAGEM DE MÁQUINAS 26

Preditor, indutor ou hipótese - é o nome dado ao algoritmo de aprendizagem de

máquinas tanto no momento da aprendizagem quanto após, na fase de utilização do

conhecimento aprendido (essa última fase é mais característica para a denominação

hipótese).

Atributos, características ou descritores - são informações extraídas de ocorrências

conhecidas do evento a ser aprendido. Cada atributo é uma característica particular

do problema. Podem ser quantitativos (grandezas numéricas, normalmente, resultan-

tes de medições) ou qualitativos (apresentam maior nível de abstração e podem ser

categóricos ou simbólicos).

Instância - é o conjunto dos atributos extraídos de cada ocorrência conhecida do

problema. Uma instância é a representação completa de um evento ocorrido.

Base de dados ou conjunto de dados - é a coleção de instâncias que servirá de base

para o algoritmo de aprendizagem entender o comportamento anterior dos eventos e

generalizar para eventos futuros.

Treinamento - o algoritmo de aprendizagem, em muitos casos, processa a base de

dados (ou parte dela) para aprender e gerar um indutor pronto para reconhecer dados

desconhecidos.

Teste - após o treinamento, instâncias de teste (podendo ser parte da base original)

são submetidas ao indutor e é verificado se esse consegue identificar a classe correta

de cada uma. Esse procedimento ajuda a analisar se o indutor conseguiu generalizar

bem.

Valores faltantes - são valores ausentes em atributos de algumas instâncias da base

de dados, normalmente ocasionados por problemas na fase de extração de caracterís-

ticas.

Ruídos - instâncias com erros e não representativas do problema, existentes por

causa de erros na fase de extração dos atributos ou rotulação da instância.

Valores atípicos (outliers) - valores que não são ruídos, ou seja, realmente represen-

tam o problema, mas, têm valores fora do padrão da classe.

Bias ou viés - como várias hipóteses podem ser capazes de modelar o conceito,

2.1. APRENDIZAGEM DE MÁQUINAS 27

é necessário que o processo tenha um critério de preferência de uma em relação a

outra, o que denominamos de bias.

Variância - mede o quanto o indutor se modifica ao ser treinado com diferentes

conjuntos de treinamento.

Estabilidade - o indutor é estável se sua variância é baixa, ou seja, não sofre muita

mudança na hipótese gerada se o conjunto de treinamento for alterado.

Sobreajustamento (overfitting) - após o treinamento o indutor não consegue ge-

neralizar bem e tem aprendizado muito específico para o conjunto de treinamento.

Engana com um bom desempenho no treino, mas depois demonstra maus resultados

no teste. Pode ser devido à base de dados ou às configurações de treinamento do

indutor.

Subajustamento (underfitting) - o desempenho é ruim tanto no treinamento

quanto no teste. Esse problema é ocasionado por causa de um conjunto de trei-

namento pequeno, pouco descritivo ou pela configuração do indutor a ser treinado.

A partir dessas premissas, são apresentadas as quatro formas para realizar a apren-

dizagem de máquinas (NORVIG; RUSSELL, 2014). Cada uma se modela para resolver

problemas diferentes.

1 - Apredizagem supervisionada: a base de dados submetida ao algoritmo possui

instâncias com um atributo especial, chamado de classe ou rótulo. Após aprender

as relações atributos-classes, o preditor se torna capaz de reconhecer a classe

de novas instâncias. Com a aprendizagem supervisionada é possível resolver

problemas de Classificação (quando o número de classes é limitado) e Regressão

(quando as classes são valores contínuos e, portanto, não têm quantidade defi-

nida).

2 - Apredizagem não-supervisionada: essa forma de aprendizagem não tem classes

predefinidas para os problemas de entrada. Assim, o algoritmo de aprendizagem

analisa como as instâncias descritoras dos problemas podem se agrupar a partir

das relações entre seus atributos. Resolvem problemas de agrupamentos, também

chamados de clusterização.

3 - Apredizagem semi-supervisionada: também utilizada em problemas de Classi-

ficação e Regressão, essa forma de aprendizagem conta com alguns exemplos

2.1. APRENDIZAGEM DE MÁQUINAS 28

rotulados e outros não, e faz inferências sobre as classes de algumas instâncias não

rotuladas para utilizá-las no treinamento do preditor e melhorar seu desempenho.

4 - Apredizagem por esforço: utilizada para tomada de decisões instantâneas. En-

quanto é operado, o algoritmo de aprendizagem realiza ações e tem a resposta se

agiu corretamente ou não. A cada resposta correta o preditor recebe um bônus

para seguir na mesma direção, enquanto decisões erradas trazem penalidades

para ajustar as decisões tomadas.

As características dos diversos tipos de algoritmos de aprendizagem de máquinas

permitem também classificá-los segundo paradigmas e modos de aprendizagem.

Quanto aos paradigmas, temos:

• Simbólico: representado principalmente por árvores e regras de decisões, esse

paradigma analisa exemplos e contra-exemplos de um conceito e constrói uma

estrutura simbólica de representação para esse conceito.

• Estatístico: um modelo estatístico é utilizado para encontrar a hipótese que

melhor representa os parâmetros do conceito induzido. Tal modelo pode ser

paramétrico (quando fazem suposição sobre a distribuição dos dados) ou não-

paramétricos (quando não fazem suposição sobre a distribuição dos dados). Os

algoritmos Baysianos fazem parte desse paradigma.

• Baseado em exemplos: supõe que instâncias da mesma classe sejam parecidas,

assim, novas instâncias são classificadas ou agrupadas de acordo com a sua

similaridade com instâncias conhecidas. O K Nearest Neighbors - KNN (COVER;

HART, 1967) é um dos principais representantes desse paradigma.

• Conexionistas: utiliza redes neurais artificiais (RNAs). Uma RNA é um modelo

computacional inspirado no sistema nervoso humano que com unidades sim-

ples de processamento interconectadas, realizam processamentos complexos

com boa performance. Exemplos de algoritmos de classificação conexionis-

tas são: Multilayer Perceptron com Backpropagation - MLP-BP (RUMELHART;

HINTON; WILLIAMS, 1986) e Self-Organizing Map - SOM (KOHONEN, 1998).

• Evolutivo: inspirado na teoria da evolução das espécies de Charles Darwing

em que apenas os mais adaptados sobrevivem, o paradigma evolucionista usa

populações de soluções que competem até que seja encontrada uma solução

ótima. OlexGA (PIETRAMALA et al., 2008) é um algoritmo evolutivo popular para

classificação de documentos.

2.2. CLASSIFICAÇÃO DE PADRÕES 29

Quanto ao modo, podemos classificar algoritmos de aprendizagem de máquinas

como incrementais ou não-incrementais. Os algoritmos incrementais atualizam a

resposta do indutor a cada novo exemplo submetido, enquanto, os não-incrementais

necessitam que toda a base de dados seja novamente submetida a cada novo exemplo.

A próxima seção discorre sobre classificação de padrões, o ramo da aprendiza-

gem supervisionada estudado nesta dissertação. Do mesmo modo, apresenta os

classificadores utilizados, de diversos paradigmas e modos de aprendizagem.

2.2 Classificação de Padrões

Em Aprendizagem de Máquinas, Reconhecimento de Padrões é o ramo que procura

replicar a capacidade humana de agrupar objetos e situações em categorias, de acordo

com as características comuns que apresentam (padrão).

Reconhecer padrões consiste em utilizar um algoritmo que extrapole o conheci-

mento fornecido por dados extraídos dos problemas, e desse modo, tenha a capaci-

dade de atribuí-los corretamente aos grupos aos quais pertencem. Sendo, principal-

mente, capaz de modelar um conceito geral desses padrões para agrupar corretamente

exemplos nunca vistos pelo processo de reconhecimento. Quando esse processo é

realizado com aprendizagem supervisionada, é chamado de Classificação.

A classificação de um padrão ocorre após o treinamento de um algoritmo classi-

ficador que é responsável por descobrir os padrões dos grupos e criar uma função

preditora ou hipótese capaz de reconhecer novas entradas.

Este trabalho utiliza algoritmos de classificação para rotular meta-instâncias e para

treinar o meta-classificador. Os classificadores utilizados pertencem a paradigmas de

aprendizado diferentes e são descritos nas seções a seguir.

2.2.1 C4.5

C4.5 (QUINLAN, 1993) é uma árvore de decisão proposta para melhorar o algoritmo

ID3 (QUINLAN, 1986). Uma Árvore de Decisão é uma técnica de aprendizagem

supervisionada, não incremental e de paradigma simbólico. Usa a estratégia “dividir

para conquistar”, ou seja, o problema é dividido em subproblemas mais simples

até que a complexidade de interpretação seja mínima. Inicialmente, um atributo é

escolhido para ser a raiz. Dessa raiz, os dados são divididos a partir de seus valores

em nós. A cada nó, um novo atributo é escolhido para dividir os dados, até que todos

os exemplos divididos pertençam a uma mesma classe, gerando folhas. Uma grande

vantagem de árvores de decisões é a geração de regras de decisões que facilitam a

classificação de instâncias desconhecidas. A Figura 2.1 mostra a estrutura de uma

2.2. CLASSIFICAÇÃO DE PADRÕES 30

árvore de decisão.

Figura 2.1: Estrutura de uma árvore de decisões. A partir do melhor atributo,os dados são divididos, um novo atributo é escolhido, até que um critério de

parada seja satisfeito e as classes estejam representadas nas folhas.

O C4.5 escolhe os melhores atributos com a medida de Razão de Ganho, segundo

(QUINLAN, 1986), melhor que a medida Ganho de Informação, usada por ID3, em

termos de precisão e complexidade. A Razão de Ganho é calculada para a escolha do

melhor atributo pela divisão entre o Ganho de Informação e a Entropia do atributo.

Outras melhoras do C4.5 em relação ao ID3, foram:

• tratar atributos tanto contínuos quanto discretos - para atributos contínuos, cria

um limite e divide os exemplos entre os que estão acima do limite e aqueles que

são inferiores ou iguais a esse limite.

• ignorar os valores faltantes dos atributos - nesse caso, não calula entropia nem

ganho de informação para os valores faltantes.

• tratar o sobreajustamento com um método de pós poda - elimina folhas que

possuem maior erro que o nó de origem, fazendo o nó virar a folha.

2.2.2 K - Nearest Neighbor (KNN)

O algoritmo de classificação de padrões K - Nearest Neighbor (KNN) é um dos mais

simples da literatura. Ele faz parte do grupo de técnicas de aprendizado baseado em

instâncias e usa da proximidade espacial dos exemplos para inferir suas classes.

O uso de KNN não exige um treinamento prévio do algoritmo. Dado um conjunto

de treinamento T = x1, x2, . . . , xN com classes conhecidas C = c1,c2, . . . ,cM e uma

2.2. CLASSIFICAÇÃO DE PADRÕES 31

instância nova a ser classificada x, o algoritmo calcula a distância entre a instância

desconhecida x e as demais instâncias do conjunto de treinamento T . Em seguida,

ordena as distâncias encontradas em ordem crescente. Os k vizinhos mais próximos

são aqueles que estão menos distantes de x. O elemento k representa a quantidade de

vizinhos considerados para a verificação da classe pertencente à maioria dos vizinhos

de x. Este processo de identificar a classe predominante entre os vizinhos de uma

instância é denominado voto majoritário. Através do voto majoritário, o exemplo x é

classificado com a classe da maioria dos seus vizinhos.

A Figura 2.2 mostra um modelo de classificação com KNN e a influência do valor

de k na classificação de novas instâncias. O conjunto T é usado para classificar a

instância desconhecida x. Dada a configuração espacial dos exemplos de treinamento,

valores diferentes de k classificam o novo exemplo com classes diferentes. Para os

valores k = 3 e k = 7, a instância é classificada como pertencente à classe c2. Já para

k = 5, a classe c1 é atribuída à nova instância. Esse fato mostra que apesar do usuário

ser o responsável por definir a métrica para o cálculo de distâncias e o número k para

a quantidade de vizinhos mais próximos a serem analisados, alguns cuidados devem

ser adotados na implementação do KNN, a fim de alcançar uma boa classificação:

• A métrica de distância escolhida deve ser capaz de lidar com o tipo de informação

presente na base de dados e nos exemplos que podem surgir para classificação

(ex.: atributos categóricos).

• A normalização dos dados permite cálculos de distâncias mais justos para os

valores dos atributos, não permitindo que um atributo domine o resultado.

• O valor de k deve ser sempre ímpar para não gerar empate no voto dos vizinhos

para a classe.

• Um valor de k muito pequeno torna a classificação sensível a ruídos, porém, um

k muito grande pode incluir vizinhos de outra classe.

A presença de ruídos ou atributos irrelevantes pode afetar bastante o resultado

do KNN. Além disso, esse algoritmo se torna computacionalmente custoso quando o

tamanho da base de dados é muito grande, devido ao cálculo de distância efetuado

para cada exemplo de treinamento. Entretanto, a facilidade de implementação, a

flexibilidade e os ótimos resultados apresentados, fazem o KNN ser um dos mais

utilizados em experimentos de classificação (WU et al., 2008).

2.2. CLASSIFICAÇÃO DE PADRÕES 32

Figura 2.2: Classificação de uma instância desconhecida com KNN. Oconjunto T é usado para classificar uma instância desconhecida x, com a classe

c1 ou c2, por voto majoritário. Para k = 3, a instância é classificada comopertencente à classe c2. Para k = 5, a instância é classificada com a classe c1. Epara k = 7, a instância é novamente classificada como pertencente à classe c2.

Isso mostra a influência da escolha do valor de k no algoritmo KNN.

.

2.2.3 Multilayer Perceptron - MLP

O cérebro humano processa informações a partir da ativação de uma série de

neurônios biológicos, interagindo em uma rede neural com uma intercomunicação

(sinapses) entre seus níveis de ativação. As Redes Neurais Artificiais (RNAs) se inspi-

ram no sistema neurológico humano para resolver problemas conforme o cérebro.

Assim, neurônios artificiais são modelos computacionais dos neurônios biológicos

e suas interconexões em rede (sinapses artificiais) permitem o processamento de

informações para resolução de tarefas complexas (ALMEIDA, 1995).

O primeiro neurônio artificial foi modelado matematicamente por MCCULLOCH;

PITTS (1943). A Figura 2.3 apresenta o neurônio artificial composto pelos seguintes

elementos (SILVA; SPATTI; FLAUZINO, 2010):

a) Sinais de entrada f1, f2, . . . , fn: sinais dos quais o conhecimento deve ser extraído,

normalmente normalizados para melhorar o desempenho da rede. Neste trabalho,

são os atributos das instâncias.

2.2. CLASSIFICAÇÃO DE PADRÕES 33

b) Pesos sinápticos w1, w2, . . . , wn: valores que indicam a relevância de cada atributo

para o neurônio.

c) Limiar de ativação θ: é uma variável que indica como a soma das variáveis de

entrada afetará a saída do neurônio. É considerado negativo para fazer subtração

no somatório do Combinador linear.

d) Combinador linear ∑

: produz o potencial de ação que pode gerar disparos positi-

vos ou negativos para outros neurônios. Soma as entradas multiplicadas por seus

pesos e subtrai o limiar de ativação.

e) Potencial de ativação u: é o resultado do Combinador linear. Quando positivo,

gera um potencial excitatório, quando negativo, produz um potencial inibitório.

f) Função de ativação g : limita o valor de saída do neurônio para valores aceitáveis.

g) Sinal de saída y: valor de resposta do neurônio, o qual pode ser utilizado pelos

neurônios a ele interconectados na rede.

Figura 2.3: Neurônio Artificial. O Combinador linear (∑

) faz a somaponderada dos sinais de entrada do neurônio ( f1, f2, . . . , fn), multiplicadospelos seus respectivos pesos (w1, w2, . . . , wn), com o Limiar de ativação (θ).Caso o potencial de ativação (u), resultado do somatório, seja positivo, produz

um potencial excitatório, caso negativo, produz um potencial inibitório. Opotencial de ativação é limitado pela função de ativação (g ) para gerar a saída

do neurônio (y). Fonte: Adaptado de SILVA; SPATTI; FLAUZINO (2010)

As funções de ativação dos neurônios podem ser:

Função Degrau: g (u) assume 1, se u ≥ 0 ou 0, se u < 0.

Função Degrau Bipolar ou Função Sinal: g (u) assume 1, se u > 0; 0, se u = 0; ou −1,

se u < 0.

2.2. CLASSIFICAÇÃO DE PADRÕES 34

Função Rampa Simétrica: considerando um intervalo limite [−a, a], g (u) assume a,

se u > a; u, se −a ≤ u ≤ a; ou −a, se u < a.

Função Logística: valores reais entre zeros e uns, pela equação 2.1, na qual β é uma

constante real associada ao nível de inclinação da função logística frente ao seu ponto

de inflexão:

g (u) = 1

1+e−βu

2.1

Função Tangente Hiperbólica: assume valores entre −1e1, a partir da equação 2.2,

e neste caso, β está associada ao nível de inclinação da função tangente hiperbólica

frente ao seu ponto de inflexão.

g (u) = 1−e−βu

1+e−βu

2.2

Função Gaussiana: a saída do neurônio tem valores de potenciais de ativação u

posicionados a uma mesma distância da sua média. Obedece a equação 2.3, na qual c

define a média e σ é o desvio padrão da função gaussiana.

g (u) = e− (u−c)2

2σ2 2.3

Função Linear ou identidade: valores idênticos ao potencial de ativação, ou seja,

g (u) = u.

Algumas estruturas precisam ser definidas para a construção e utilização de uma

rede neural. As RNAs possuem basicamente três partes: camada de entrada (neurônios

que recebem os dados de entrada); camadas intermediárias, escondidas ou ocultas

(neurônios responsáveis por extrair o conhecimento); e camada de saída (responsá-

veis por organizar e entregar a saída da rede neural). A arquitetura de uma rede se

caracteriza pelo arranjo entre neurônios e como interagem durante o processamento.

São exemplos de arquiteturas: redes diretas (feedforward) de camadas simples, re-

des diretas de camadas múltiplas, redes recorrentes e redes reticuladas. Definindo a

arquitetura, a quantidade de camadas, número de neurônios nas camadas e outras

composições estruturais, tem-se a topologia da rede.

Um algoritmo de treinamento é utilizado para ajustar os pesos e os limiares de

ativação dos neurônios, a fim de adquirir conhecimento sobre o problema e produzir

saídas próximas aos valores desejados. No processo de treinamento, todos os exem-

plos devem ser apresentados à rede mais de uma vez, denominando-se época cada

apresentação completa da base de dados. Os ajustes nos pesos e limiares ocorrem em

lote de padrões (após cada época) ou padrão-por-padrão (ajustando a cada padrão

2.2. CLASSIFICAÇÃO DE PADRÕES 35

apresentado). O processo de treinamento pode ocorrer de forma supervisionada,

não-supervisionada ou com reforço.

O Perceptron é a rede neural artificial de configuração mais simples. Ele consiste

de uma camada neural com apenas um neurônio nessa camada. Foi proposto por

ROSENBLATT (1958) para identificar padrões geométricos, como letras e números.

Uma vez que trabalha com um neurônio, o funcionamento da rede Perceptron é

idêntico ao funcionamento de um neurônio artificial, mostrado acima, e a formulação

matemática para seu processamento interno é dada pelas equações 2.4 (na qual

i = 1, . . . ,n é o conjunto dos dados de entradas de um exemplo) e 2.5.

u =n∑

i=1wi . fi −θ

2.4

y = g (u) 2.5

A função de ativação para o Perceptron pode ser a Função Degrau ou Degrau Bi-

polar. O processo de treinamento é supervisionado e o algoritmo de aprendizagem é

a Regra de Hebb (DONALD, 1949), que incrementa pesos e limiares quando a saída

é condizente com a desejada (potencial de ativação excitatório) e decrementa (po-

tencial de ativação inibitório) quando a saída da rede é diferente da saída desejada.

As equações 2.6 e 2.7 mostram como os pesos e limiares são ajustados. Para essas

equações, têm-se:

• wi , o peso para a i-ésima entrada da rede neural;

• η, a taxa de aprendizagem, que define a velocidade de aprendizagem até a

estabilidade das respostas da rede;

• x(k), a k-ésima amostra de treinamento;

• sd (k), a saída desejada para a k-ésima amostra de treinamento;

• θ, o limiar de ativação;

• y , o valor da saída produzida pelo Perceptron.

w atuali = w anter i or

i +η.(d (k) − y

).x(k)

2.6

θatual = θanter i or +η.(d (k) − y

).x(k)

2.7

Todavia, o Perceptron é restrito por resolver apenas problemas linearmente se-

paráveis. Nesse contexto, essa rede neural artificial perdeu o foco de estudos, e a

2.2. CLASSIFICAÇÃO DE PADRÕES 36

sua popularização só voltou com o surgimento do algoritmo Backpropagation de

RUMELHART; HINTON; WILLIAMS (1986). O Backpropagation permitiu o uso de

redes com mais de uma camada, as redes neurais Perceptron Multicamadas (PMC)

ou Multilayer Perceptron (MLP). As MLPs suprem a necessidade de classificação de

dados não linearmente separáveis.

A Figura 2.4 mostra a estrutura das MLPs. Na primeira camada, a camada de

entrada (LE ), o número de neurônios N1, . . . , Np corresponde às variáveis de entrada

de cada exemplo a ser mostrado para a rede. A quantidade de camadas escondidas

L1, . . . ,L j é definida a partir do projeto da rede, bem como a quantidade de neurônios

em cada camada escondida(Nq , Nr

). A última camada de uma rede neural artificial

é a camada de saída (LS), que tem um neurônio para cada saída possível da MLP

(N1, . . . , Ns).

Figura 2.4: Multilayer Perceptron - MLP. Possui uma camada de entrada LE

com N1, . . . , Np neurônios correspondentes às variáveis de entrada de cadaexemplo a ser mostrado para a rede. Em seguida, as camadas escondidas

L1, . . . ,L j podem ter quantidades de neurônios diferentes(Nq , Nr

), a depender

da topologia escolhida para a rede. E a última camada é a camada de saída LS

que tem um neurônio para cada saída possível da MLP (N1, . . . , Ns).

A rede neural MLP tem arquitetura feedforward de camadas múltiplas, as fun-

ções de ativação podem ser Função Logística ou Função Tangente Hiperbólica e tem

aprendizado supervisionado. O algoritmo utilizado para seu treinamento é o Back-

propagation, que faz parte dos algoritmos supervisionados (possuem a orientação da

saída desejada) e estáticos (não alteram a estrutura da rede) das redes multicamadas.

Com o Backpropagation, o treinamento ocorre em duas fases:

1ª Fase - Forward (para frente) - o padrão é apresentado e as saídas dos neurônios

são transmitidas até a última camada para gerar a saída final.

2ª Fase - Backward (para trás) - o erro é calculado na última camada a partir da

comparação da saída da rede com a saída desejada e os pesos e limiares são

2.2. CLASSIFICAÇÃO DE PADRÕES 37

corrigidos da saída até a entrada até que seja atingido o erro mínimo aceitável

ou a a quantidade de épocas especificadas como limite da rede).

2.2.4 PART

O algoritmo de regras de aprendizado PART, proposto por FRANK; WITTEN (1998),

combina estratégias da árvore de decisões C4.5 de QUINLAN (1993) (descrita na Seção

Seção 2.2.1) e estratégias das regras de aprendizado RIPPER de COHEN (1995). O

objetivo dessa combinação é diminuir a complexidade presente nos dois métodos,

por não usar, como esses, a fase de otimização global. Além disso, se propõe a eliminar

o problema de sobrepoda1 de RIPPER, diminiur o tempo de execução, o tamanho e

a redundância do conjunto de regras e a restrição aos testes atributo-valor de uma

árvore de decisões, como ocorre em C4.5. A ideia principal de PART é inferir regras

utilizando a técnica dividir-para-conquistar junto a geração repetida de árvores de

decisões parciais.

Com o uso da técnica dividir-para-conquistar, PART constrói uma regra por vez e

remove as instâncias cobertas por ela. Assim, segue criando recursivamente regras

para as instâncias restantes até que não sobrem instâncias no conjunto de treinamento.

A diferença para RIPPER consiste em como essas regras são criadas. Nesse ponto,

entram as árvores de decisões parciais similares a C4.5. Para cada regra, uma árvore é

construída e podada para o conjunto de instâncias correntes. Dessa árvore de decisões,

a folha que cobrir o maior número de exemplos vira uma regra e a árvore é descartada.

O fato de recriar árvores de decisões a cada nova regra é o responsável por evitar a

sobrepoda.

PART não gera árvores completas a cada regra, gera árvores parciais. O algoritmo

faz um teste para dividir os exemplos em subconjuntos e toma decisões da mesma

maneira que C4.5. Com o propósito de criar as menores árvores possíveis, e em con-

sequência, gerar regras mais gerais, a decisão de expansão dos subconjuntos se dá a

partir daquele que apresentar a menor entropia média. A Figura 2.5 de FRANK; WIT-

TEN (1998) mostra um exemplo de como uma árvore de decisões parcial é construída,

passo a passo:

1Também chamado de generalização apressada e ocorre quando o algoritmo não atinge o conheci-mento necessário, ou seja, não faz boa generalização do problema.

2.2. CLASSIFICAÇÃO DE PADRÕES 38

Figura 2.5: Exemplo de como PART constrói uma árvore de decisões parcial.Estágio 1 - um teste divide as instâncias em nós (em cinza porque não foram

expandidos ainda). Estágio 2 - O nó 3 com menor entropia é expandido.Estágio 3 - o nó com menor entropia é uma folha (preto), então começa o

retrocesso a partir da expansão do nó 5. Estágio 4 - a expansão do nó 5 geraapenas folhas, desse modo, inicia-se a poda da árvore. O nó 5 e o nó 3 viram

folhas. Estágio 5 - continua o retrocesso e o próximo nó com menor entropia é o4, que é expandido em folhas, mas não obedece à regra de substituição da

subárvore. A construção da árvore de decisões parcial encerra com 3 folhas em5 estágios. Fonte: FRANK; WITTEN (1998)

Estágio 1 - Um teste para os exemplos correntes os divide em subconjuntos ainda

não expandidos. Nós não expandidos são representados pela cor cinza.

Estágio 2 - Verifica-se que o nó 3 apresenta a menor entropia. Este nó é expandido e

gera uma folha, ou seja, todos os exemplos pertencentes à mesma classe

(representada pela cor preta) e outro nó.

Estágio 3 - Após a expansão do nó 3, o nó com menor entropia é aquele que já re-

presenta uma folha. Assim, começa um processo de retrocesso e o nó 5 é

expandido, gerando duas folhas.

Estágio 4 - Não há mais como expandir após o nó 5, visto que este possui como filhos,

duas folhas. Dessa forma, o processo de poda é iniciado, conforme a

poda de C4.5, por substituição de subárvore. O erro das folhas do nó 5 é

analisado e aceito para ser substituído por uma folha. A mesma análise é

2.2. CLASSIFICAÇÃO DE PADRÕES 39

feita para o nó 3 quando o nó 5 vira uma folha e a substituição da subárvore

também é aceita, vista no estágio 4.

Estágio 5 - O retrocesso continua e o próximo nó com menor entropia ainda não

expandido é o 4. O nó quatro é expandido para duas folhas, mas no

processo de poda, não tem a sua subárvore aceita para ser substituída

por uma folha. Por isso, a construção da árvore de decisões termina, não

necessitando expandir o nó 1. A árvore termina com três folhas em 5

estágios.

Uma vez criada uma árvore de decisões parcial, uma única regra é estraída da folha

que cobrir o maior número de instâncias. Como dito anteriormente, essas instâncias

são removidas do conjunto de treino e uma nova árvore é construída para extrair

uma nova regra com as instâncias restantes. O conjunto de regras está completo

quando não restar mais instâncias a serem cobertas por regras advindas das árvores

de decisões parciais.

FRANK; WITTEN (1998) afirma que PART opera eficientemente sem a necessidade

de otimização global e sabe lidar com conjuntos de dados patológicos (com ruídos ou

valores faltantes). Além disso, tem precisão similar a C4.5 e melhor que RIPPER.

2.2.5 Sequential Minimal Optimization (SMO)

Sequential Minimal Optimization - SMO é um algoritmo de treinamento para Má-

quinas de Vetores Suporte (Support Vector Machines - SVM ). Contudo, para entender

SMO é necessário entender, primeiramente, o que é uma SVM.

Support Vector Machine - SVM

SVM é uma técnica de aprendizagem de máquinas fundamentada em Teoria da

Aprendizagem Estatística e em Otimização Matemática. Proposta inicialmente por

BOSER; GUYON; VAPNIK (1992) e melhorada por CORTES; VAPNIK (1995), a técnica

busca encontrar um hiperplano de separação dos dados de forma que possuam a

maior margem de segurança possível, ou seja, a máxima distância entre os vetores

suportes.

Em conjuntos de dados com classes linearmente separáveis, a distinção das classes

pode acontecer com diferentes hiperplanos de separação. A Figura 2.6 mostra um

exemplo de duas classes e como vários hiperplanos podem ser eficientes na separação

de seus elementos.

2.2. CLASSIFICAÇÃO DE PADRÕES 40

Figura 2.6: Separação de duas classes com hiperplanos. Uma base de dadoscom classes linearmente separáveis tem suas classes facilmente distintas com

várias possibilidades de hiperplanos.

Entretanto, mesmo escolhendo um hiperplano que atenda ao objetivo de distinção

dos exemplos disponíveis, não é possível garantir que um exemplo novo se encaixe do

lado do hiperplano que represente a sua classe (Figura 2.7).

Figura 2.7: Hiperplano aleatório separativo de duas classes. Um hiperplanoescolhido aleatoriamente pode errar ao classificar novos exemplos.

O risco de erro é diminuído com a escolha de um hiperplano que tenha como

critério a maior margem de separação das classes e, consequentemente, o menor erro

de classificação. Esse é o trabalho de uma SVM. Ela cria vetores suporte a partir dos

elementos mais próximos de classes diferentes, para fazer um hiperplano equidistante

entre essas classes e que maximize a margem de separação, conforme a Figura 2.8.

Funções de Langrange são utilizadas para garantir essa maximização, enquanto algo-

ritmos de otimização quadrática, caso do SMO, encontram o hiperplano ótimo.

2.2. CLASSIFICAÇÃO DE PADRÕES 41

Figura 2.8: Hiperplano a partir de uma SVM. Um hiperplano escolhido poruma SVM procura estar equidistante das classes e possuir a maior margem

possível (mg ), diminuindo a possibilidade de erro de classificação.

A separação de problemas lineares por uma SVM pode ser definida pelo hiperplano

de separação representado pela Equação 2.8, em que w é o vetor normal para o

hiperplano e x é o vetor do exemplo de entrada. É necessário encontrar o hiperplano

de separação em f (x) = 0 e encontrar os vetores suportes, sobre os planos f (x) =+1

para a classe y =+1 e f (x) =−1 para a classe y =−1, conforme as Equações 2.9 e 2.10.

f (x) = w.x +b 2.8

f1(x) = w.x +b =+1 2.9

f2(x) = w.x +b =−1 2.10

Considerando que a distância entre um ponto em duas dimensões (x0, y0) e uma

linha (Ax +B y +C = 0) é dada pela Equação 2.11, é possível formular a margem de

separação das classes, usando a distância entre o ponto extremo de uma classe e o

vetor da reta de separação do hiperplano w , conforme a Equação 2.12.

di st = Ax0 +B y0 +CpA2 +B 2

2.11

mg = |w.x +b|‖w‖ = 1

‖w‖ 2.12

Assim, a margem de separação de uma classe a outra ( f1(x) para f2(x)), mostrada

na Figura 2.7, é dada pela Equação 2.13.

2mg = 2

‖w‖ 2.13

2.2. CLASSIFICAÇÃO DE PADRÕES 42

Sabendo que um hiperplano ótimo é aquele que tem a maior margem entre seus

vetores suportes, a determinação desse hiperplano deve maximizar 2mg . Equivalente

a minimizar ‖w‖ = w T w , não deixando pontos entre f1(x) e f2(x), ou seja, sujeito a :

w xi +b ≥+1, se a classe yi =+1 e w xi +b ≤−1, se a classe yi =−1. Essas duas condições

juntas podem ser expressas por:

yi (w.xi +b) ≥ 1 2.14

O problema de otimização pode ser expresso pela Equação 2.15. Essa equação re-

presenta um problema de Programação Quadrática (problema PQ), dado que a função

objetivo quadrática está sujeita a um conjunto de restrições lineares. Considera-se xi

o i-ésimo exemplo de treino e yi a classe correta da SVM para o i-ésimo exemplo de

treino xi . Os valores de yi podem ser +1 para exemplos do hiperplano superior ou −1

para aqueles pertencentes ao hiperplano inferior.

mi nw,b

1

2w T w sujeito a yi (w.xi +b) ≥ 1, ∀xi

2.15

Problemas de extremos (mínimos e máximos), sujeitos a restrições de igualdade,

podem ser resolvidos com Multiplicadores de Lagrange. Multiplicadores de Lagrange

combinam a função objetivo e as restrições em uma função, resolvendo a função

objetivo com um conjunto de multiplicadores αi .

Para um problema definido por F (x) como função objetivo e gi (x) = 0 (com i =1, . . . , N) como restrições, chama-se Lagrangiano à Função ou Função de Lagrange, a

Equação 2.16.

L(x, ?) = F (x)+N∑

i=1αi gi (x)

2.16

Desse modo, introduzindo um multiplicador de Lagrange αi para cada exemplo de

treino (α1, . . . ,αn ≥ 0), tem-se:

L(w,b,α) ≡ 1

2w T w −

N∑i=1

αi yi (w.xi +b)+N∑

i=1αi

2.17

Dentro de uma forma dual, ao invés de minimizar L(w,b,α) com respeito a w ,

podemos resolver a maximização de L(w,b,α) com respeito a α, sujeito às restrições

de que o gradiente de L(w,b,α) para as variáveis primárias w e b sejam nulos e α≥ 0

(Equações 2.18 e 2.19).

∂L

∂w= 0 ∴ w =

N∑i=1

αi yi xi

2.18

2.2. CLASSIFICAÇÃO DE PADRÕES 43

∂L

∂b= 0 ∴

N∑i=1

αi yi = 0 2.19

Resolvendo as Equações 2.18 e 2.19, as variáveis primal w e b são eliminadas com

a substituição desses resultados em L(w,b,α) (Equação 2.20).

LD ≡N∑

i=1αi − 1

2

∑i , jαiα j yi y j xi x j

2.20

Na Equação 2.20, o vetor xi é o vetor de entrada e x j é o padrão de entrada perten-

cente ao j-ésimo exemplo. Maximizando LD com respeito a α, o hiperplano ótimo é

obtido com w da Equação 2.18 e com b, calculado pela Equação 2.21.

b = 1−w.x(s), sendo x(s) um vetor suporte no hiperplano superior. 2.21

Todavia, uma SVM que resolve apenas problemas linearmente separáveis se torna

muito restrita. A maioria dos problemas reais se caracteriza por pertencer a classes não

linearmente separáveis. Para problemas não lineares, as máquinas de vetores suporte

mapeam o espaço original dos dados para um espaço não-linear de maior dimensão e

criam o hiperplano no qual os exemplos sejam linearmente separáveis. A Figura 2.9

mostra como é possível fazer essa separação num espaço de maior dimensão. Em

a) um conjunto unidimensional possui exemplos de duas classes que não podem

ser separados por uma reta. Ao aplicar uma determinada função Φ(x) sobre esses

exemplos, o resultado bidimensional possibilita a criação de uma reta de separação

entre suas classes. Do mesmo modo, em b) um conjunto bidimensional não tem

suas classes linearmente separáveis e com a aplicação de uma função Φ(x), é possível

identificar um hiperplano que as separem linearmente em terceira dimensão.

2.2. CLASSIFICAÇÃO DE PADRÕES 44

Figura 2.9: Mudança de dimensão e separação linear de conjuntos nãolinearmente separáveis. As figuras a) e c) representam os conjuntos em suasdimensões originais de classes não-linearmente separáveis, unidimensional ebidimensional, respectivamente. Em em b) e d) a mudança de dimensão de a) ec) para 2 dimensões e 3 dimensões, respectivamente, torna possível a separação

linear de suas classes.

A Função de Lagrange utilizando o mapeamento da função Φ(x) para um espaço

de alta dimensão, seria:

LD ≡N∑

i=1αi − 1

2

∑i , jαiα j yi y jΦ(xi )Φ(x j )

2.22

Entretanto, encontrar e executar a função Φ(x) que mapeie o espaço de caracterís-

ticas de um conjunto de dados para outro que o torne linearmente separável, pode

ser computacionalmente custoso e inviável. As funções de mapeamento utilizadas

por SVMs são funções especiais, chamadas de Funções de Kernel (Equação 2.23).

Com uma Função de Kernel é possível mapear os pontos de um conjunto implicita-

mente, sem definir o mapeamento de Φ(x), ao calcular o produto escalar dos vetores

de características em outro espaço.

k(xi , x j ) =Φ(xi ).Φ(x j ) 2.23

Exemplos de Funções de Kernel utilizadas em SVMs são:

• Kernel Polinomial, com p sendo o grau do polinômio:

K (xi , x j ) = (xi x j +1)p 2.24

2.2. CLASSIFICAÇÃO DE PADRÕES 45

• Kernel RBF (Radius Basis Function), sendo γ a largura da função de base radial

gaussiana:

K (xi , x j ) = e−γ‖xi x j‖2 2.25

• Kernel Sigmoidal, no qual o parâmetro k pode ser visto como um parâmetro de

escala dos dados de entrada e θ como um parâmetro que controla o desloca-

mento limite de mapeamento:

K (xi , x j ) = t anh (kxT xi +θ) 2.26

Usando uma Função de Kernel K (xi , x j ), o Lagrangiano à Função fica:

LD ≡N∑

i=1αi − 1

2

∑i , jαiα j yi y j K (xi , x j )

2.27

Outro parâmetro importante das SVMs é o parâmetro C , pois, ele flexibiliza as mar-

gens para erros pequenos, diminuindo a sensibilidade de SVMs a ruídos ou separação

imperfeita. Com C , entre f1(x) e f2(x) (hiperplanos de margens superior e inferior,

respectivamente) podem existir alguns exemplos que não fazem parte dos vetores

suporte. A penalidade aplicada por causa dos exemplos que atravessam as margens é

dada pela introdução de ξi ≥ 0, ∀i (Equações 2.29 e 2.29).

w.xi +b ≥+1−ξi para yi =+1 2.28

w.xi +b ≤−1+ξi para yi =−1 2.29

À função objetivo do problema de otimização também é adicionado um termo de

penalidade, conforme a Equação 2.30.

mi ni mi zarw,b,ξ

1

2w T w +C

N∑i=1

ξi

2.30

sujeito a yi (w.xi +b)+ξi −1 ≥ 0, 1 ≤ i ≤ N

ξi ≥ 0, 1 ≤ i ≤ N

Com esse problema em sua forma dual, a Função de Lagrange permanece inal-

tareda, exceto às restrições, visto que os multiplicadores αi , agora são limitados por

C (Equação 2.31).

maxi mi zeα

LD ≡N∑

i=1αi − 1

2

∑i , jαiα j yi y j K (xi , x j )

2.31

2.2. CLASSIFICAÇÃO DE PADRÕES 46

sujeito a:

0 ≤αi ≤C , ∀i ;∑i αi yi = 0

A fim de fazer o problema de Programação Quadrática ser positivamente definido,

o Kernel deve obedecer condições de Karush-Kuhn-Tucker(KKT) (KUHN, 2014). Es-

sas condições são suficientes e necessárias para encontrar um ponto ótimo de um

problema de Programação Quadrática definido positivo. Para o problema de PQ em

questão ser resolvido para todo i , as condições KKT são:

αi = 0 ⇔ yi f (xi ) ≥ 1,

0 <αi <C ⇔ yi f (xi ) = 1, 2.32

αi =C ⇔ yi f (xi ) ≤ 1.

Sendo f (xi ) a saída da SVM para o i-ésimo exemplo de treino e as condições KKT

avaliadas exemplo por exemplo.

Sequential Minimal Optimization - SMO

A partir da definição de Support Vector Machines (SVMs), entende-se por Sequential

Minimal Optimization - SMO, um algoritmo que implementa a SVM e encontra seus

vetores suportes resolvendo dois multiplicadores de Lagrange a cada passo.

O diferencial de SMO para outros algoritmos de SVMs está em resolver o problema

de Programação Quadrátiva sem usar métodos numéricos e sem usar grande espaço

para armazenamento de uma matriz. O método decompõe o problema em subproble-

mas e busca resolver o menor problema de otimização possível. Visto que uma das

restrições de uma SVM está em obedecer a uma igualdade linear∑

i αi yi = 0, o menor

problema de otimização possível é a otimização conjunta de dois multiplicadores de

Lagrange αi e esses podem ser resolvidos analiticamente (PLATT, 1999). Para manter

a condição de igualdade linear verdadeira, quando um multiplicador é atualizado, o

outro deve ser ajustado, conforme a Equação 2.34.

∑i∈A

αi yi =∑j∈B

α j y j

2.33

SMO consiste em três passos a cada iteração: a escolha de dois multiplicadores de

Lagrange para resolver, através de buscas heurísticas; a busca pelos valores ótimos

dos multiplicadores escolhidos, com um método analítico; e a atualização dos valores

ótimos da SVM.

Os multiplicadores de Lagrange de cada iteração devem obedecer a Equação 2.34,

a fim de não violar a condição∑

i αi yi = 0.

2.2. CLASSIFICAÇÃO DE PADRÕES 47

αnovo1 y1 +αnovo

2 y2 = const ante =αanter i or1 y1 +αanter i or

2 y2

2.34

Conforme mostra a Figura 2.10 de PLATT (1999), valores novos são viáveis para a

resolução do problema se respeitarem as retrições: 0 ≤α1 , α2 ≥C .

Figura 2.10: Restrições dos multiplicadores de Lagrange. As restrições dedesigualdade fazem os multiplicadores pertencerem a uma caixa. Enquanto arestrição de igualdade linear faz pertencerem a uma linha diagonal. Portanto,

um passo do SMO deve encontrar um ponto ótimo da função objetivo sobre umsegmento de linha diagonal. Fonte: PLATT (1999)

.

No primeiro passo do algoritmo SMO, o valor de αnovo2 é encontrado e atualizado

para a obtenção de αnovo1 . Para α2, tem-se a restrição:

L ≤αnovo2 ≤ H

2.35

Considerando que αnovoi é o novo multiplicador de Lagrange do exemplo xi e

αanter i ori é o valor anterior do multiplicador, tem-se:

se y1 6= y2

L = max(0,αanter i or

2 −αanter i or1

)H = mi n

(C ,C +αanter i or

2 −αanter i or1

)se y1 = y2

L = max(0,αanter i or

2 +αanter i or1 −C

)H = mi n

(C ,αanter i or

2 +αanter i or1

)A função atual é a função em xi determinada pelos valores dos multiplicadores de

Lagrange e por b no estágio atual da aprendizagem, dada por:

f (xi ) =l∑

j=1α j y j K (x j , xi )+b

2.36

A distância do ponto xi ao hiperplano atual, dado pela atualização dos multiplica-

2.2. CLASSIFICAÇÃO DE PADRÕES 48

dores de Lagrange, equivale a Ei . Ei é o erro do i-ésimo exemplo de treino, ou seja, à

diferença entre f (xi ) e a classe yi pertencente ao ponto xi (Equação 2.37).

Ei = f (xi )− yi =[

l∑j=1

α j y j K (x j , xi )+b

]− yi

2.37

A Equação 2.38 expressa a quantidade adicional exigida, dada pela segunda de-

rivada da função objetivo ao longo da linha diagonal. Nessa equação, x1 e x2 são os

pontos associados a α1 e α2, respectivamente.

η= K (x1, x1)+K (x2, x2)−2K (x1, x2) = ‖Φ(x1)−Φ(x2)‖2 2.38

Existindo um αaux , limitado por L ≤ αaux ≤ H , dado pela Equação 2.39, o valor

máximo da função objetivo é dado pela Equação 2.40.

αaux2 =αanter i or

2 + y2(E1 −E2)

η

2.39

αnovo2 =

H se αaux

2 ≥ H ;

αaux2 se L <αaux

2 < H ;

L se αaux2 ≤ L

2.40

Após encontrar o valor de αnovo2 , é possível encontrar o valor de αnovo

1 , com a

Equação 2.41.

αnovo1 =αanter i or

1 + y1 y2

(αanter i or

2 −αnovo2

) 2.41

Uma heurística diferente é utilizada para cada um dos dois multiplicadores de

Lagrange a serem escolhidos nas iterações. Na escolha de α2, o ponto x2 é escolhido

entre os exemplos que violam as condições KKT (Equação 2.32). O algoritmo primeiro

encontra no conjunto de treinamento, todos os pontos que violam as condições KKT

e faz um subconjunto desses, como pontos elegíveis para otimização. Em seguida,

percorre todo o subconjunto criado e faz os seguintes testes (considerando um nível

de tolerância tol): E2.y2 < −tol e α2 < C ou E2.y2 > tol e α2 > 0. Quando o algoritmo

encontra um exemplo que satisfaz esses testes, seleciona-o para otimizar.

Na segunda heurística, o ponto x1 deve ser escolhido com o intuito de ser atu-

alizado junto a x2, e assim, causar um grande acréscimo da função objetivo. Para

encontrar x1, o algoritmo SMO maximiza o valor dado por |E1 −E2|. Se E1 é positivo, o

x1 com menor erro E2 é o escolhido. Se E1 é negativo, o x1 com maior erro E2 é selecio-

nado para otimização. Caso o x1 escolhido não forneça um acréscimo significante na

função objetivo, o SMO analisa todos os pontos x1 fora das bordas, ou seja, 0 <α<C . E

se mesmo nos pontos fora da borda, o ponto adequado não for encontrado, a procura

2.2. CLASSIFICAÇÃO DE PADRÕES 49

por esse é feita em todo o conjunto de treinamento.

Após conseguir um acréscimo de valores na função objetivo com o uso dos pontos

x1 e x2, a heurística escolhe novos pontos e termina o processo quando todos os pontos

do conjunto de treinamento atendem às condições de KKT. A fim de reduzir contas

adicionais, uma lista com os erros de todos os pontos de treinamento é mantida na

memória.

A solução proposta pelo algoritmo SMO obedece a restrição αi[

yi (w.xi +b)−1]= 0

para i = 1,2, . . . , l , ou seja, αi[

yi f (xi )−1] = 0. Correspondente à Equação 2.32, vista

anteriormente:

αi = 0 ⇔ yi f (xi ) ≥ 1,

0 <αi <C ⇔ yi f (xi ) = 1,

αi =C ⇔ yi f (xi ) ≤ 1.

Logo, SMO satisfaz as condições de complementariedade de Karush-Kuhn-Tucker

e classifica com a máxima margem entre os conjuntos.

O valor de b, do vetor w e dos erros Ei são calculados separadamente, ao fim

de cada iteração, quando as condições KKT são atendidas pelos pontos x1 e x2. A

atualização dos valores se dá sempre utilizando o valor atual e o valor anterior, com a

função f (xi ) (Equação 2.36).

Para o exemplo x1, o valor de b1 deve forçar a saída da SVM para y1 quando a

entrada for o exemplo x1, dado por:

b1 =−[

E1 + y1

(αnovo

1 −αanter i or1

)K (x1, x1)+ y2

(αnovo

2 −αanter i or2

)K (x1, x2)+banter i or

] 2.42

Para o exemplo x2, o valor de b2 deve forçar a saída da SVM para y2 quando a

entrada for o exemplo x2, dado por:

b1 =−[

E2 + y1

(αnovo

1 −αanter i or1

)K (x1, x2)+ y2

(αnovo

2 −αanter i or2

)K (x2, x2)+banter i or

] 2.43

Para valores de b1 = b2, o novo valor de b é bnovo = b1 = b2. Caso contrário, o

intervalo entre b1 e b2 possui todos os limiares que são consistentes com as condições

de KKT. Portanto, o SMO escolhe o limiar que está no meio do intervalo, ou seja:

bnovo = b1 +b2

2

2.44

Em conjuntos de dados linearmente separáveis, o valor do vetor w pode ser atuali-

2.3. META-APRENDIZAGEM E CARACTERIZAÇÃO DE DADOS 50

zado por:

bnovo = w anter i or + y1

(αnovo

1 −αanter i or1

)x1 + y2

(αnovo

2 −αanter i or2

)x2

2.45

A cada iteração, os erros Ei são atualizados por:

E novoi = E anter i or

i + y1

(αnovo

1 −αanter i or1

)K (x1, xi )+

2.46

+y2

(αnovo

2 −αanter i or2

)K (x2, xi )+bnovobanter i or

Denomina-se g ap a diferença entre a função objetivo atual e a função objetivo

anterior. A atualização da função objetivo também pode ser feita usando o g ap da

seguinte forma:

g ap =(αnovo

1 −αanter i or1

)+

(αnovo

2 −αanter i or2

)+

2.47

−[

2∑j=1

l∑i=1

yi y j

(αnovo

j −αanter i orj

)K (x j , xi )

]i 6=1i 6=2

+

− 1

2y2

1

(αnovo

1 −αanter i or1

)K (x1, x1)− 1

2y2

2

(αnovo

2 −αanter i or2

)K (x2, x2)+

− y1 y2

[αnovo

1 αnovo2 −αanter i or

1 αanter i or2

]K (x1, x2)

Mesmo contendo mais subproblemas a serem resolvidos no processo, cada sub-

problema do SMO é resolvido rapidamente. Além disso, esse algoritmo foi escolhido

por representar a ideia original de SVM, atuando com um processo relativamente

simples.

2.3 Meta-aprendizagem e caracterização de dados

Bastante difundido entre pesquisadores, o teorema do "No Free Lunch" (WOLPERT;

MACREADY, 1997) se aplica a algoritmos de aprendizagem de máquinas, visto que

nenhum algoritmo consegue obter sempre as melhores performances em todas as

situações. Algumas saídas têm sido propostas para lidar com esse problema, como

combinação de classificadores, aprendizagem ativa e meta-aprendizagem.

Dando foco em meta-aprendizagem, BRAZDIL et al. (2008) afirma que deve ser

possível aprender sobre o próprio processo de aprendizagem, e ainda, que um sistema

poderia aprender a lucrar com a experiência anterior para gerar conhecimento adicio-

nal e simplificar a seleção automática de modelos eficientes que resumem os dados.

Meta-aprendizagem também foi definida por SMITH-MILES (2008) como exploração

2.3. META-APRENDIZAGEM E CARACTERIZAÇÃO DE DADOS 51

do conhecimento sobre a performance de algoritmos para melhorar essa performance

ou selecionar algoritmos de aprendizagem.

As principais diferenças entre o aprendizado básico e o aprendizado em nível meta

estão no escopo e em como acumula experiência. O escopo do aprendizado básico é

uma tarefa específica, a experiência é acumulada a partir de situações do problema

sobre suas saídas. Já no meta-aprendizado, o escopo está definido por várias tarefas e

guarda experiências sobre como as saídas estudadas se comportaram em cada tarefa.

Para recomendação de algoritmos, a comunidade acadêmica considera que é

possível modelar as características dos problemas para relacionar ao desempenho

desses algoritmos, analisando como uma situação clara de aprendizagem. Assim,

meta-aprendizagem, ou um aprendizado sobre a aprendizagem, tem sido campo de

grandes pesquisas e ótimos resultados, como em NAKHAEIZADEH (1993), GIRAUD-

CARRIER et al. (2002), LEYVA et al. (2014) e OLIVEIRA MOURA et al. (2014a).

Os conceitos de meta-aprendizagem apresentados a seguir, são importantes para

a compreensão da proposta do nosso trabalho.

• Meta-características: são medidas extraídas das bases de dados com a expecta-

tiva de que forneçam informações relevantes para determinar o comportamento

dessas bases em relação aos métodos estudados.

• Meta-instâncias: são formadas pelas meta-características extraídas das bases

de dados de amostra, utilizadas como atributos e rotuladas pela informação da

saída desejada para cada base, a partir de conhecimentos a priori do problema

ou resultados experimentais.

• Meta-base: é construída com as meta-instâncias criadas contendo informações

de todas as amostras de bases.

Um dos principais requisitos para aplicação de meta-aprendizagem é caracterizar

bases de dados através de medidas. Caracterizar dados em tarefas de classificação de

padrões é extrair medidas e informações dos dados que possam revelar padrões de

comportamento entre eles, associados às saídas desejadas. As meta-características,

seguem a mesma ideia da caracterização de dados comuns, sendo nesse caso, inferidas

de bases de dados ao invés de dados brutos e associadas ao desempenho de algoritmos

como saídas.

Muitas medidas de caracterização de dados têm sido propostas para diversas

tarefas de meta-aprendizagem (LEYVA et al., 2014). Para algoritmos de seleção de

instâncias, entre os autores que definiram medidas de caracterização de dados para

gerar atributos de meta-bases, destacamos e apresentamos a diante, as medidas

sugeridas por SOTOCA; MOLLINEDA; SANCHEZ (2006), por CAISES et al. (2011) e

2.3. META-APRENDIZAGEM E CARACTERIZAÇÃO DE DADOS 52

por LEYVA et al. (2014), por terem sido utilizadas pela maioria dos estudos propostos

recentemente.

As medidas de CAISES et al. (2011), estão relacionadas ao conceito de conjunto

local. O conjunto local de uma instância é formado pela maior hiperesfera possível de

instâncias da mesma classe, de acordo com suas distâncias ao vizinho mais próximo.

Algumas das medidas de CAISES et al. (2011) foram desmembradas e suas partes foram

utilizadas em nosso trabalho como medidas individuas, porque várias distâncias intra-

locais foram nulas e impediam o cálculo de algumas divisões. Uma breve descrição

das medidas de CAISES et al. (2011) é apresentada a seguir:

• Pontos isolados são o número de pontos que são mais próximos a instâncias de

outras classes (inimigas) que a instâncias pertencentes a sua própria classe.

• Cardinalidade média de conjuntos locais mostra instâncias de bordas e se as

bordas das classes são regulares ou irregulares.

• Dispersão intergrupos (DP1 e DP2) determina o grau de proximidade entre gru-

pos. Ao invés de usarmos DP1 e DP2, usamos as suas partes, que são: distância

intergrupos, distância intragrupos, gruposNE e diâmetro do grupo.

• Nível de ruído informa o nível de ruído a partir das instânicas excluídas pela

execução do ENN.

• Desbalanceamento é o grau de disparidade do número de instâncias por classes.

• Número de atributos nominais é usado para escolher MSIs que trabalham com

atributos nominais e eliminar aqueles que possuem performance baixa na pre-

sença desses atributos.

• Número de classes influencia na performance de classificadores e na complexi-

dade dos algoritmos de treino.

• Regiões fornece informações sobre a distribuição dos dados.

Já SOTOCA; MOLLINEDA; SANCHEZ (2006) faz uma revisão das medidas de com-

plexidade existentes na literatura e discute como aplicá-las em meta-aprendizagem

no domínio de classificação de padrões. Essas medidas também são eficientes quando

aplicadas em métodos de seleção de instâncias, conforme mostrado por LEYVA; GON-

ZALEZ; PEREZ (2015) e MOLLINEDA; SÁNCHEZ; SOTOCA (2005). Geralmente, são

agrupadas nas categorias: estatísticas, separabilidade de classes, geometria e densi-

dade e, sobreposição.

Dentre as medidas estatísticas, usamos:

2.3. META-APRENDIZAGEM E CARACTERIZAÇÃO DE DADOS 53

• medidas de informações simples, pela contagem no conjunto completo de

instâncias de cada base: número de instâncias, número de atributos, número de

classes, atributos numéricos, atributos binários, atributos nominais. Também

utilizadas em CAISES et al. (2011)

• medidas de informações proporcionais, pela proporção de valores de cada tipo

em relação ao número completo de instâncias da base de dados: proporção de

atributos numéricos, proporção de atributos binários, proporção de atributos

nominais.

• Entropia mede a quantidade de informação presente na base de dados para

identificar uma instância pertencente a uma classe ci do conjunto de C classes.

O valor de entropia da base H (Γ) em relação às classes, pode ser calculado com

a Equação 2.48, na qual p (ci ) é a probabilidade a priori da classe ci , ou seja, é a

frequência da classe na base de dados.

H (Γ) =−C∑

i=1p (ci ) log2

(p (ci )

) 2.48

Como medidas de sobreposição, usamos Raio discrimintante de Fisher (F1) e

Volume da região de sobreposição (F2), estas medidas inicialmente foram propostas

para problemas de duas classes, mas ganharam generalização para mais classes em

MOLLINEDA; SÁNCHEZ; SOTOCA (2005).

• F1 generalizada para várias classes consistem em:

F 1g en =

C∑i=1

ni .δ(m,mi )

C∑i=1

ni∑j=1

δ(xij ,mi )

2.49

Para F1, é necessário calcular previamente, o número de exemplos por cada

classe, aqui representado por ni , a média da base de dados completa m, a média

por classe mi , δ equivale a uma medida de distância e xij é o exemplo j da classe

i.

• Em F2, a generalização segue:

F 2g en = ∑ci ,c j

∏k

mi nmaxk −maxmi nk

maxmaxk −mi nmi nk

2.50

2.3. META-APRENDIZAGEM E CARACTERIZAÇÃO DE DADOS 54

Nesta medida, considera-se: k = 1, . . . ,d para um problema com d atributos, ou

d dimensional. Então, deve-se calcular um vetor com os atributos máximos

ou mínimos de cada classe e em seguida fazer as comparações entre classes,

conforme abaixo:

mi nmaxk = mi nmax( fk ,ci ),max( fk ,c j )

maxmi nk = maxmi n( fk ,ci ),mi n( fk ,c j )

maxmaxk = mi nmax( fk ,ci ),max( fk ,c j )

mi nmi nk = maxmi n( fk ,ci ),mi n( fk ,c j )

O resultado do produto dos atributos do vetor resultante é somado a cada itera-

ção de comparação entre classes.

As medidas de separabilidade de classes utilizadas foram:

• Frações de pontos sobre as bordas (N1)

É construída uma árvore geradora mínima, em inglês Minimum Spanning Tree

(MST), em que todos as instâncias da base de dados são consideradas pontos e

conectadas ao seu vizinho mais próximo. A quantidade de pontos conectados

ao seu inimigo mais próximo, ou seja, conectado a uma classe diferente, é

considerada a quantidade de pontos de borda. A medida N1 equivale à fração

dos pontos de borda sobre o número total de pontos (instâncias) da base de

dados.

• Raio de distância média entre classes dos vizinhos (N2)

Verifica o quanto os dados são discrinantes, com a comparação da dispersão

inter-classes com a separabilidade intra-classes. Quanto menor o valor da me-

dida, mais discriminantes são os dados.

N 2 =

n∑i=1

δ(N1 = (xi ), xi )

n∑i=1

δ(N1 6= (xi ), xi )

2.51

δ indica o cálculo da distância entre a instância em questão e N1 = (xi ) que é o

vizinho mais próximo dentro da mesma classe ou N1 6= (xi ) que é o vizinho mais

próximo de outra classe (inimigo mais próximo).

2.3. META-APRENDIZAGEM E CARACTERIZAÇÃO DE DADOS 55

• Estimação da taxa de erro (N3)

N3 corresponde à taxa de erro obtida pela aplicação do método Leaving-one-out.

Leaving-one-out pertence ao grupo de algoritmos de avaliação de classificadores

por validação cruzada. Considere o método de validação cruzada k-fold, em

que o conjunto de treinamento original é dividido em k subconjuntos e em k

execuções cada subconjunto é usado como teste, enquanto os demais fazem

o treino do classificador. O resultado da avaliação é a média dos k resultados

de testes. Leaving-one-out é equivalente a aplicação de k-fold com k igual ao

número total de exemplos de treino, ou seja, um exemplo vai para teste e os

demais para treino a cada execução.

Medidas de geometria e densidade:

• ε-Vizinhança (T1)

Enquanto N1 indica as formas geométricas das classes a partir do lado externo,

através das bordas, T1 começa de dentro das classes para indicar tais formas.

Cada instância de treino é tida como centro de uma bola que vai crescendo o

máximo possível com a inclusão de instâncias de mesma classe, até encontrar

uma instância inimiga (de outra classe). Após a criação de todas as bolas, aquelas

completamente dentro de outras são consideradas redundantes e são removidas.

Finalmente, o número de bolas equivale à quantidade necessária para cobrir

todas as classes. T1 é o número de bolas normalizado pelo número de instâncias

da base de dados.

• Média do número de pontos por dimensão (T2)

Descreve a densidade da distribuição espacial dos exemplos, apenas dividindo o

número de instâncias da base de dados n pelo número de atributos d .

T 2 = n

d

2.52

• Densidade D1

A densidade é definida como a média do número de instância pelo volume da

base de dados. O volume corresponde ao produto dos tamanhos dos ranges dos

atributos dessa base de dados. Assim, D1 é definida por:

D1 = n

vol

2.53

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 56

Em que n é o número de instâncias e vol o volume da base.

• Volume da vizinhança local (D2)

Nessa medida, o volume é dado pela equação:

Vi =d∏

h=1(max( fh , Nk (xi ))−mi n( fh , Nk (xi )))

2.54

Nk (xi ) são os k vizinhos mais próximos da instância xi . Assim, calcula-se o valor

máximo e mínimo de cada atributo fh entre esses vizinhos e o volume de cada

instância se dá pela equação 2.54. A medida D2 é o valor médio de Vi por n

instâncias de treino, conforme a equação 2.55

D2 = 1

n

n∑i=1

Vi

2.55

• Densidade da classe em região de sobreposição (D3)

Para computar D3, encontramos os k vizinhos mais próximos de cada instância

i e verificamos se a maioria desses vizinhos pertence a classes diferentes da ins-

tância em questão. Quando sim, consideramos que essa instância está em região

de sobreposição e acrescentamos em D3. MOLLINEDA; SÁNCHEZ; SOTOCA

(2005) propôs D3 porque as regiões de sobreposição têm grande influência nos

erros dos classificadores. Levando em conta tal importância, calculamos D3

com 3 e 5 vizinhos e normalizamos o valor pelo número de instâncias da base

de dados para minimizar a dispersão dos valores na meta-base. Quando D3 é

calculada com apenas um vizinho, produz os mesmos valores que N3, ou seja,

indica a taxa de erro pelo método leaving-one-out.

2.4 Métodos de seleção de instâncias

Em tarefas de classificação, os principais problemas em relação às bases de dados

são: ruídos (instâncias com informações erradas), informações irrelevantes, necessi-

dade de grande espaço para armazenamento, e execução do algoritmo intratável ou

muito lento devido ao tamanho da base de dados. Métodos de seleção de instâncias

(MSIs) são algoritmos que se propõem a mitigar esses problemas. MSIs reduzem as ba-

ses de dados, criando um subconjunto de instâncias que melhor descrevem as classes,

com dois objetivos: reduzir o custo computacional e melhorar as taxas de acerto dos

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 57

processos de classificação. O dois objetivos podem ser atingidos simultaneamente,

no entanto, quando o custo computacional é a meta principal, são aceitas pequenas

perdas nas taxas de acerto de classificação para aumento na redução da base de dados.

A Figura 2.11 mostra como a utilização de um MSI pode beneficar uma base de dados

e discriminar melhor suas classes.

Figura 2.11: Base de dados antes e depois da aplicação de um MSI. Antes deaplicar um método de seleção de instâncias (MSI), a base pode ter ruídos,

instâncias irrelevantes e não distinguir bem as classes, após a aplicação de umMSI a base tende a se tornar mais sucinta e ao mesmo tempo mais eficiente.

Neste trabalho, assumimos que seleção de instâncias corresponde à busca, em

todo o vetor de espaço, daquelas instâncias que melhor descrevem as classes das bases

de dados. Logo, são entendidos como MSIs, tanto métodos que criam instâncias novas

para representar a base de dados (também chamados de geração de protótipos), como

métodos que selecionam a partir das instâncias já disponíveis (seleção de protótipos).

Desde 1968, quando o primeiro MSI foi criado, Condensed Nearest Neighbor -

CNN (HART, 1968), quase cem outros métodos foram sugeridos por muitos autores.

GARCÍA; LUENGO; HERRERA (2015) apresentam uma taxonomia com esses MSIs,

mostrando a distinção entre eles de acordo com suas abordagens em relação à:

• tipo de seleção: métodos de condensação, edição e híbridos;

• direção de pesquisa: incremental, decremental, em lote, misto e fixo;

• avaliação da pesquisa: filtro e wrapper ;

• outras propriedades: representação, função de distância e votação.

Dentro da família de condensação, CNN ainda é o mais usado em trabalhos re-

centes. Ele tem direção de pesquisa incremental, normalmente, alcança boas taxas

de redução e é muito sensível a ruídos por causa da inclusão das instâncias clas-

sificadas erroneamente. Muitos métodos foram criados baseados no CNN com a

pretenção de melhorar esse algoritmo. No entanto, as mudanças propostas são mais

complexas, necessitam de elevado tempo para processamento e continuam sensíveis

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 58

a ruídos. Outros métodos desta família são: Reduced Nearest Neighbor - RNN (decre-

mental) (GATES, 1972), Selective Nearest Neighbor - SNN (decremental) (RITTER et al.,

1975), Minimal Consistent Set - MCS (decremental) (DASARATHY, 1994) and Patterns

by Ordered Projection - POP (batch) (RIQUELME; AGUILAR-RUIZ; TORO, 2003).

O método decremental Edited Nearest Neighbor - ENN (WILSON, 1972) pertence à

família dos métodos de edição. Ele remove as instâncias que têm classes diferentes

de seus vizinhos. ENN é normalmente usado apenas como filtro de ruídos, devido a

sua baixa taxa de redução. Métodos que tentaram melhorar o ENN como Repeated

ENN - RENN (decremental) e All-KNN (em lote) (TOMEK, 1976) aumentaram a com-

plexidade, o custo computacional e não obtiveram boas taxas de redução. Então, foi

adotada a combinação proposta por CAISES et al. (2011) combinando ENN com CNN,

visto que possuem resultados complementares. A (Seção 2.4.1) detalha os métodos e a

combinação utilizada.

A maioria dos métodos propostos atualmente é da família de métodos híbridos.

Esses métodos tentam combinar as vantagens das abordagens de condensação e

edição para construir métodos que alcancem boas taxas de redução, sem perdas

relevantes em suas precisões e com baixo custo computacional. Por esses motivos,

essa família possui uma maior importância e, portanto, foram utilizados quatro mé-

todos híbridos. Eles diferem na direção de pesquisa: o método incremental Instance

Based 3 - IB3 (AHA; KIBLER; ALBERT, 1991) (Seção 2.4.2); os métodos decremen-

tais e filtros de avaliação de pesquisa: Decremental Reduction Optimization Proce-

dure 3 - DROP3 (WILSON; MARTINEZ, 2000) (Seção 2.4.3) e C-pruner (ZHAO et al.,

2003) (Seção 2.4.5); e o método de processamento em lote Iterative Caise Filtering -

ICF (BRIGHTON; MELLISH, 2002) (Seção 2.4.4).

Estratégias de geração de protótipos e meta-heurísticas têm a grande vantagem

de explorar um largo espaço de soluções, no entanto, o alto custo computacional

dessas técnicas as colocam em desvantagem no uso prático comparadas às demais

abordagens. Exemplos de métodos baseados em geração de protótipos são: Prototype

nearest neighbor (PNN) (CHANG, 1974), Hybrid LVQ3 algorithm (HYB) (KIM; OOM-

MEN, 2003b) e Differential evolution (DE) (TRIGUERO; GARCÍA; HERRERA, 2011).

Já Explore (CAMERON-JONES, 1995), Cooperative coevolutionary instance selection

(CoCoIS) (GARCÍA-PEDRAJAS; DEL CASTILLO; ORTIZ-BOYER, 2010) e Tabu search

(ZhangTS) (ZHANG; SUN, 2002) são MSIs que abordam meta-heurística.

Além da popularidade dos métodos mencionados, em JANKOWSKI; GROCHOWSKI

(2004) uma comparação entre algoritmos de seleção de instâncias mostra a perfor-

mance relevante dos métodos escolhidos. Entre os métodos IB’s, IB3 tem o melhor

resultado. E em relação a métodos DROP’s, DROP3 tem boas saídas com baixo custo.

Os outros métodos têm performance semelhante àqueles do grupo a que pertencem,

mas diferem conforme explicado anteriormente. Baseados nessa análise, foram es-

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 59

colhidos MSIs que possuem abordagens distintas, a saber: ENN-CNN, IB3, DROP3,

C-pruner e ICF. As seções seguintes detalham os métodos utilizados.

2.4.1 ENN-CNN

A combinação do uso de Condensed Nearest Neighbor - CNN (HART, 1968) com

Edited Nearest Neighbor - ENN (WILSON, 1972) proposta por CAISES et al. (2011),

consiste simplesmente em executar ENN como um filtro e em seguida CNN.

O método CNN possui dois passos. No primeiro passo, uma instância de cada

classe é selecionada aleatoriamente para formar uma nova base de dados. No segundo,

esta nova base de dados é usada para treinar um classificador que classifica todas

as instâncias da base de dados original. As instâncias classificadas erroneamente

são incluídas na nova base de dados a fim de garantir que instâncias desconhecidas

e similares àquelas classificadas erroneamente serão corretamente classificadas. O

Algoritmo 2.1 apresenta um pseudo-código para CNN.

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 60

Algoritmo 2.1 Condensed Nearest Neighbor - CNNEntrada: T = t1, . . . , tu . conjunto de instâncias originais da base de dados

Entrada: C = c1, . . . ,cn . classes da base de dados

Entrada: K . número de vizinhos considerados na classificação com KNN

Entrada: di st . distância considerada na classificação com KNN

Saída: S = s1, ..., sr . conjunto de instâncias selecionadas

Etapa 1 - Seleção aleatória de instâncias de cada classe

1: S =;2: para i ← 1 até n faça

3: Escolha aleatória de tu ∈C (i ),

4: S ← S ∪ tu . tu , a instância da classe, é adicionada ao subconjunto S

5: fim para

Etapa 2 - Inclusão de instâncias erroneamente classificadas

6: para j ← 1 até u faça

7: se K N N (T ( j ),S) 6=C (T ( j )) então . Classifica a instância T ( j ) com o

classificador K N N em relação ao subconjunto S e verifica se a predição da classe

foi errada

8: S ← S ∪T ( j ) . T ( j ), a instância erroneamente classificada, é adicionada ao

subconjunto S

9: fim se

10: fim para

ENN é bastante simples. Ele tenta preservar as instâncias não pertencentes às

bordas das classes e assim, aumentar a margem de separação entre elas. Para tanto,

elimina as instâncias erroneamente classificadas, decrementando a base de dados

original. Seu pseudo-código é apresentado no Algoritmo 2.2.

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 61

Algoritmo 2.2 Edited Nearest Neighbor - ENNEntrada: T = t1, . . . , tu . conjunto de instâncias originais da base de dados

Entrada: C = c1, . . . ,cn . classes da base de dados

Entrada: K . número de vizinhos considerados na classificação com KNN

Entrada: di st . distância considerada na classificação com KNN

Saída: S = s1, ..., sr . conjunto de instâncias selecionadas

1: S ← T

2: para j ← 1 até u faça

3: se K N N (T ( j ),T ) 6=C (T ( j )) então . Classifica a instância T ( j ) com o

classificador K N N e verifica se a predição da classe foi errada

4: S ← S −S( j ) . S( j ), a instância erroneamente classificada, é retirada do

subconjunto S

5: fim se

6: fim para

2.4.2 Instance Based 3 - IB3

No método Instance Based 3 - IB3 (AHA; KIBLER; ALBERT, 1991), o mais recente

dos métodos IB’s, uma nova base de dados é criada com as instâncias da base de dados

original cujas instâncias aceitáveis mais próximas têm classes diferentes das instâncias

que estão sendo adicionadas. A aceitabilidade de instâncias é baseada em intervalo

de confiança e precisão de classificação. O pseudo-código de IB3 é apresentado no

Algoritmo 2.3.

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 62

Algoritmo 2.3 Instance Based 3 - IB3Entrada: T = t1, . . . , tu . conjunto de instâncias originais da base de dados

Entrada: C = c1, . . . ,cn . classes da base de dados

Entrada: di st . distância considerada na classificação com KNN

Saída: S = s1, ..., sr . conjunto de instâncias selecionadas

1: S =;2: para j ← 1 até u faça

3: y ← Acei t abi l i d ade(T ( j ),S) . Instância aceitável mais próxima de T ( j ) em S.

Caso não exista, uma instância aleatória de S é atribuída

4: se C (T ( j )) 6=C (y) então . Caso T ( j ) não classifique y corretamente, y é

inserida em S

5: S ← S ∪T ( j ) . A instância erroneamente classificada por T ( j ), é inserida no

subconjunto S

6: fim se

7: Atualize o registro de classificação de y

8: para l ← 1 até r faça

9: se d(T ( j ),S(l )) ≤ d(T ( j ), y) então . Caso a distância entre T ( j ) e S(l ) seja

menor ou igual à distância entre T ( j ) e y , atualizar o registro de classificação de

S(l )

10: Atualize o registro de classificação de S(l )

11: se registro de l é significativamente pobre então

12: S ← S −S(l )

13: fim se

14: fim se

15: fim para

16: fim para

17: para j ← 1 até r faça

18: se S( j ) não é aceitável então

19: S ← S −S( j )

20: fim se

21: fim para

Aceitabilidade é uma função na qual se a precisão em classificação de uma instân-

cia for significativamente superior à frequência da sua classe, ela será mantida, senão

será eliminada. Para diminuir a sensibilidade com bases desbalanceadas, IB3 nor-

maliza a aceitação de cada instância em relação à frequência das classes. A Equação

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 63

2.56 apresenta o cálculo dos limites de intervalo de confiança utilizados em IB3.Para

a precisão de um exemplo em S, tem-se: n o número de tentativas de classificação

da instância, p a precisão nas tentativas de classificação e z o nível de confiança. Já

para a frequência da classe, considera-se: n o número de instâncias já processadas,

p a proporção de instâncias processadas que pertencem a essa classe e z o nível de

confiança.

p + z2/2n ± z√

p(1−p)n + z2

4n2

1+ z2/n

2.56

2.4.3 Decremental Reduction Optimization Procedure 3 - DROP3

Decremental Reduction Optimization Procedure 3 - DROP3 é um de cinco métodos

propostos por WILSON; MARTINEZ (2000). O algoritmo executa primeiramente o

algoritmo ENN. Depois, ordena as instâncias de acordo com suas distâncias para

a instância mais próxima que possui classe diferente. Em seguida, DROP3 remove

toda instância do conjunto que não altera a classificação do conjunto das instâncias

associadas. Instâncias associadas são aquelas que possuem ti como vizinho mais

próximo, formando o conjunto A(ti ). As instâncias de A(ti ) possuem com relação a ti .

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 64

Algoritmo 2.4 Decremental Reduction Optimization Procedure 3 - DROP3Entrada: T = t1, . . . , tu . conjunto de instâncias originais da base de dados

Entrada: C = c1, . . . ,cn . classes da base de dados

Entrada: K . número de vizinhos considerados na classificação com KNN

Entrada: di st . distância considerada na classificação com KNN

Saída: S = s1, ..., sr . conjunto de instâncias selecionadas

1: S ← T

2: para i ← 1 até r faça

3: N (Si ) ← [K +1] N N (S(i ),S) . Inicializa o conjunto N (Si ) de K +1 vizinhos mais

próximos de S(i )

4: para j ← 1 até nx faça

5: A(Si ( j )) ← A(Si ( j ))∪ S(i ) . Adiciona N (Si ) ao conjunto de associados de

seus vizinhos

6: fim para

7: fim para

8: para l ← 1 até r faça

9: se C (S(l )) 6=C (K N N (S(l ),T ) então

10: S ← S −S(l )

11: fim se

12: fim para

13: S ← or denaçãoi ni m(S) . Ordena S em ordem decrescente de distância ao inimigo

mais próximo

14: para q ← 1 até r faça

15: com ← número de associados de S(q) corretamente classificados com S(q)

como vizinho.

16: sem ← número de associados de S(q) corretamente classificados sem S(q)

como vizinho.

17: se com − sem ≤ 0 então

18: S ← S −S(q)

19: para a ← 1 até nx faça

20: N (A(Si (a))) ← N (A(Si (a)))− A(Si (a))

21: Adicione em N (A(Si (a))) no novo vizinho mais próximo de A(Si (a)) em

S.

22: fim para

23: fim se

24: fim para

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 65

2.4.4 Iterative Caise Filtering - ICF

O objetivo de Iterative Caise Filtering - ICF (BRIGHTON; MELLISH, 2002) é remover

instâncias dos centros das classes e reter as instâncias das bordas das classes. O ICF

usa o método ENN como um filtro de ruído no seu pré-processamento. Logo após,

as instâncias são removidas usando os conceitos de: conjunto local, acessibilidade e

cobertura. A saber:

• Conjunto local: o conjunto local de uma instância x, L(x) é aquele que contém,

dentro da maior esfera possível centrada em x, todas as instâncias da mesma

classe de x.

• Acessibilidade (x) = x ′ ∈ T : x ′ ∈ L(x) : é quantidade de exemplos no conjunto

local de x.

• Cobertura (x) = x ′ ∈ T : x ∈ L(x ′) : é quantidade de conjuntos locais diferentes nos

quais x está presente.

A instância x é removida se a sua Acessibilidade é maior que sua Cobertura. O

Algoritmo 2.5 mostra o pseudo-código de ICF.

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 66

Algoritmo 2.5 Iterative Caise Filtering - ICFEntrada: T = t1, . . . , tu . conjunto de instâncias originais da base de dados

Entrada: C = c1, . . . ,cn . classes da base de dados

Entrada: K . número de vizinhos considerados na classificação com KNN

Entrada: di st . distância considerada na classificação com KNN

Saída: S = s1, ..., sr . conjunto de instâncias selecionadas

1: S ← T

2: para l ← 1 até r faça

3: se C (S(l )) 6=C (K N N (S(l ),T ) então

4: S ← S −S(l )

5: fim se

6: fim para

7: enquanto S é atual i zado faça

8: para i ← 1 até r faça

9: Calcule Acessi bi l i d ade(S(i ))

10: Calcule Cober tur a(S(i ))

11: fim para

12: para q ← 1 até r faça

13: se Acessi bi l i d ade(S(q)) >Cober tur a(S(q)) então

14: S ← S −S(q)

15: fim se

16: fim para

17: fim enquanto

2.4.5 C-pruner

O método C-pruner (ZHAO et al., 2003) também usa os conceitos de acessibilidade

e cobertura, descritos na Seção 2.4.4. Porém, sua cobertura considera apenas as

instâncias da mesma classe. Estes dois conceitos são usados para determinar se uma

instância é ruidosa, supérflua ou crítica, conforme segue:

• Instância Supérflua: é a instância x que pode ser classificada corretamente pelas

instâncias da Acessi bi l i d ade(x). Diz-se que x é implicada pela Acessi bi l i d ade(x).

• Instância Crítica: duas condições podem tornar uma instância crítica. Na pri-

meira, se pelo menos uma instância xi pertencente à Cober tur a(x), não é im-

plicada pela Acessi bi l i d ade(xi ), a instância x é crítica. A outra é que após a

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 67

deleção de x, se pelo menos uma instância xi pertencente á Cober tur a(x), não é

implicada pela Acessi bi l i d ade(xi ), essa instância x também é crítica.

• Instância Ruidosa: Se uma instância x não é supérflua e a Acessi bi l i d ade(x) >Cober tur a(x), então x é uma instância ruidosa.

As instâncias críticas afetam a classificação de outras instâncias, por isso, são

as únicas retidas na base de dados final. As instâncias ruidosas e supérfluas são

removidas, segundo as regras:

Regra 1 - Para ser podada, ou seja, eliminada, uma instância x deve ser uma instância

ruidosa ou uma instância supéflua, mas não crítica.

Regra 2 - A ordem de remoção de duas instâncias xi e x j deve ser guiadas pelas

condições:

* Obs.:

* H −K N N (x) é o número de instâncias pertencentes à mesma classe de

x em K N N (x)

* D −N E(x) é a distância da instância x ao seu inimigo mais próximo, ou

sej, à instância de classe distinta da classe de x.

• Se H −K N N (xi ) > H −K N N (x j ), então, xi é removido primeiro.

• Se H −K N N (xi ) = H −K N N (x j ) e D −N E(xi ) > D −N E(x j ), então, x j é

removido primeiro.

• Se H −K N N (xi ) = H −K N N (x j ) e D − N E(xi ) = D − N E(x j ), então, a

ordem de remoção é escolhida aleatoriamente.

O Algoritmo 2.6 contém o pseudo-código de C-pruner.

2.4. MÉTODOS DE SELEÇÃO DE INSTÂNCIAS 68

Algoritmo 2.6 C-prunerEntrada: T = t1, . . . , tu . conjunto de instâncias originais da base de dados

Entrada: C = c1, . . . ,cn . classes da base de dados

Entrada: K . número de vizinhos considerados na classificação com KNN

Entrada: di st . distância considerada na classificação com KNN

Saída: S = s1, ..., sr . conjunto de instâncias selecionadas

1: S ← T

2: para l ← 1 até r faça

3: Calcule Acessi bi l i d ade(S(l ))

4: Calcule Cober tur a(S(l ))

5: fim para

6: para i ← 1 até r faça

7: se S(i ) é uma Instância Ruído então

8: S ← S −S(i )

9: para todo S(i )i ∈Cober tur a(S(i )) faça

10: Acessi bi l i d ade(S(i )i ) ← Acessi bi l i d ade(S(i )i )−S(i )

11: Atualiza Acessi bi l i d ade(S(i )i )

12: fim para

13: para todo S(i ) j ∈ Acessi bi l i d ade(S(i )) faça

14: Cober tur a(S(i ) j ) ←Cober tur a(S(i ) j )−S(i )

15: fim para

16: fim se

17: fim para

18: Ordena S conforme a Regra 2.

19: para q ← 1 até r faça

20: se S(q) satisfaz a Regra 1 então

21: S ← S −S(q)

22: para todo S(q)p ∈Cober tur a(S(q)) faça

23: Acessi bi l i d ade(S(q)p ) ← Acessi bi l i d ade(S(q)p )−S(q)

24: Atualiza Acessi bi l i d ade(S(q)p )

25: fim para

26: fim se

27: fim para

2.5. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 69

2.5 Métodos de seleção de atributos

O desempenho de um classificador depende da interação entre o número de

instâncias, número de atributos da base de dados e a complexidade desses dados.

Espera-se que um elevado número de instâncias ou atributos ajude o algoritmo de

classificação a entender a relação entre os dados de entrada e a saída. No entanto,

essa não é uma realidade sempre válida.

Como visto na Seção 2.4, uma base de dados deve ter instâncias batantes para que

as classes tenham representatividade e possam ser reconhecidas. Por outro lado, deve

ser considerado que se estiverem apenas representando ruídos ou redundâncias, as

instâncias afetarão negativamente na precisão e no custo computacional.

Da mesma forma, os atributos trazem a preocupação de como sua quantidade

afeta o desempenho da classificação e o custo computacional. A quantidade de atri-

butos é a dimensão da base de dados. O aumento dessa dimensionalidade traz um

aumento exponencial da complexidade do problema. Essa é uma situação conhecida

como Maldição da Dimensionalidade. Como consequência da Maldição da Dimen-

sionalidade, quando o número de instâncias para treino é relativamente pequeno em

relação aos atributos, a precisão do classificador é afetada. Isso se dá pelo fato de que

tantos atributos podem não ter informações relevantes e não ter representação sufici-

ente para que o classificador descubra os seus padrões. VALIANT (1984) afirma que

o número de instâncias necessárias para um bom resultado de classificação, cresce

exponencialmente com o número de atributos.

Um caminho para fugir da Maldição de Dimensionalidade é reduzir a dimensiona-

lidade das bases de dados. Podemos citar como vantagens desse processo:

• a melhora da eficácia, quando os atributos, ainda que condizentes com o nú-

mero de instâncias, não contribuem para o processo de classificação. Visto que

suas informações são irrelevantes, ou seja, não são descritivos do problema,

ou, porque são altamente correlacionados a outros atributos e assim possuem

informações redundantes.

• melhora na eficiência computacional, reduzindo a complexidade e tempo de

execução dos algoritmos.

• redução do tamanho necessário para a base de dados, relativo à quantidade de

instâncias.

• redução do espaço para armazenamento da base de dados.

• simplificação do modelo e interpretação dos dados.

• facilitação da visualização dos dados.

2.5. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 70

A redução de dimensionalidade pode ser feita de duas maneiras: criação de novos

atributos com a transformação dos originais ou seleção de atributos. Posto que

podemos avaliar as meta-características geradas na arquitetura proposta a fim de

melhorar os resultados e tornar o processo mais rápido, sugerimos o uso de seleção

de atributos como um módulo do Meta-CISM.

Selecionar atributos significa reduzir o número de características extraídas do

problema para uma quantidade capaz de melhorar o desempenho da classificação,

seja em tempo computacional, em precisão ou ambos simultaneamente. Para sugerir

um subconjundo de características, esses métodos utilizam estratégias para decidir

como os atributos serão combinados e qual o critério para a avaliação da qualidade

das possíveis combinações.

Geralmente, os métodos de seleção de atributos são categorizados como: Filtro,

Wrapper ou Embarcado. Na categoria Filtro, estão os algoritmos que trabalham no pré-

processamento e, independente de algoritmos de aprendizagem, avaliam a relevância

dos subconjuntos de atributos. Os algoritmos do tipo Wrapper, por sua vez, utilizam

o algoritmo de aprendizagem para avaliar o processo de seleção. E na categoria

Embarcados, estão os algoritmos de aprendizagem que possuem o seletor de atributos

intrínseco e realiza a seleção de subconjuntos como parte de seu processo.

Os métodos do tipo filtro têm destaque porque são menos custosos computacio-

nalmente e podem ser associados a diferentes algoritmos de aprendizagem. O ponto

fundamental desses métodos é a maneira como avaliam a relevância dos atributos.

A relevância de um atributo pode ser definida por um critério de qualidade, depen-

dente da natureza do problema e dos atributos envolvidos. Medidas de avaliação

encontradas na literatura são:

• Consistência: redução do conjunto de atributos mantendo a consistência original

• Dependência: correlação entre atributos e classe.

• Distância: discriminação entre atributos.

• Divergência: distância probabilística ou divergência entre as densidades de

probabilidade condicional das classes.

• Informação / Incerteza: ganho de informação com adição ou remoção de um

atributo;

Em relação às saídas, exitem duas abordagens de seleção de atributos: ranking

e seleção de subconjunto. Outras nomeações encontradas são, respecitivamente:

Contínua e Binária; non-ranker e ranker ; e univariado e multivariado. Os métodos de

seleção do tipo ranking ordenam os atributos de acordo com sua importância indivi-

dual, dando pesos de relevância para cada atributo. Já os métodos do tipo seleção de

2.5. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 71

subconjunto definem para cada atributo d se esse estará no subconjunto ou não, a

partir da avaliação dos subconjuntos possíveis, que corresponde a 2d possibilidades.

(MOLINA; BELANCHE; NEBOT, 2002)

O uso das médidas de avaliação é suficiente para os métodos de ranking e os

tornam muito mais simples que a seleção de subconjunto, porém, despreza a corre-

lação e redundância entre atributos. Portanto, os dn primeiro atributos relevantes

individualmente podem não fazer parte do melhor subconjunto e não ser relevantes

numa combinação. Já para os métodos de seleção de subconjuntos, avaliar todos os

subconjuntos possíveis de atributos pode ser uma tarefa inviável. Logo, esses métodos

necessitam fazer uma busca heurística, na qual alguns subconjuntos são analisados

até que um critério de parada seja satisfeito. Para tanto, além da medida de avaliação,

essa busca precisa definir:

1 - A direção da pesquisa (ponto inicial da busca):

• Para trás - inicia com todos os atributos e remove um atributo por vez;

• Para frente - inicia sem atributos e inclui um atributo por vez;

• Bidirecional - a busca começa em qualquer ponto e atributos podem ser

adicionados e removidos;

• Ponderada - todos os atributos estão presentes nas iterações, porém, rece-

bem pesos diferentes em cada uma;

• Aleatória - ponto de partida da busca e atributos a serem removidos ou

adicionados são decididos de forma aleatória;

2 - Procedimento para efetuar a busca, ex.:

• Backward Elimination

• Forward Selection

• Random Search

• Best First

• Genetic Search

3 - Estratégia de busca:

• Exaustiva - busca exaustiva para encontrar o subconjunto de características

que atenda o critério de avaliação.

• Sequencial - o atributos são adicionados ou removidos um a um até que não

haja melhora na qualidade da solução.

• Aleatória - os conjuntos escolhidos são completamente aleatórios.

2.5. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 72

4 - Critério de parada, ex.:

• Número máximo de iterações

• Valor da medida de avaliação obtida

DASH; LIU (1997) apresentam uma visão geral do processo de seleção de subcon-

juntos na Figura 2.12

Figura 2.12: Modelo do processo de seleção de características com validação.Inicialmente, os subconjuntos são gerados e em seguida avaliados, até que

obedeçam o critério de parada e sigam para validação. Fonte: DASH; LIU (1997)

Escolhemos avaliar os métodos da categoria filtro e dentre eles, variar os tipos de

abordagens e medidas de avaliação, conforme a Tabela 2.1. Os algoritmos de seleção

de subconjuntos escolhidos têm direção de pesquisa para frente e utilizam a estratégia

de busca exaustiva. A escolha do procedimento de busca será avaliada na Seção 4.4.

Tabela 2.1: Características dos métodos de seleção de atributos utilizados

Abordagem Método de Seleção de AtributosMedida deAvaliação

Seleção desubconjunto

Consistency-Based Subset Evaluation Consistência

Correlation-based Feature Selection - CFS Dependência

RankingChi Square Feature Evaluation Distância

Relief - F Dependência

Apresentamos a seguir, a descrições individuais de cada método de seleção de

atributos estudado com seus respectivos algoritmos.

2.5.1 Consistency-based Subset Evaluation

O método de seleção de atributos Consistency-Based Subset Evaluation, proposto

por (LIU; SETIONO, 1996), inicia seu processo com um conjunto vazio de atributos

2.5. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 73

e faz uma busca exaustiva com um procedimento de busca pré-definido. A cada

subconjunto de atributos criado, as instâncias de treinamento são projetadas sobre

esse subconjunto e a consitência dos seus valores é avaliada em relação às classes.

O critério de parada é encontrar o menor subconjunto com consistência igual à do

conjunto completo de atributos.

A formula de consistencia utilizada é:

Consi stenc y(S) = 1−∑J

i=0 |Di |− |Mi |n

2.57

Considere S um subconjunto de atributos, J é o número de combinações distintas

de valores de atributos para S, |Di | é o número de ocorrências da i-ésima combinação

dos atributos, |Mi | é a cardinalidade da classe majoritária para a i-ésima combinação

dos atributos e n é o número total de instâncias na base de dados.

A busca desse método tem direção de pesquisa para frente, produzindo uma lista

de atributos, classificadas de acordo com sua contribuição global para a consistência

do conjunto de atributos.

2.5.2 Correlation-based Feature Selection - CFS

Correlation-based Feature Selection - CFS (HALL, 1998) procura subconjuntos

que contêm atributos que são altamente correlacionadas com a classe e têm baixa

correlação uns com os outros. Inicia sem atributos e com o procedimento de busca

escolhido, faz uma busca exautiva pelo subconjunto que na adição de outros atributos,

não aumenta o mérito já encontrado.

CFS calcula uma matriz de correlação entre: atributo-classe e entre atributo-

atributo. O grau de correlação entre atributos ( fi e f j ) é calculado usando entropia H

na seguinte fórmula:

U(

fi , f j)= 2×

[H

(fi

)+H(

f j)−H

(fi , f j

)H

(fi

)+H(

f j) ] 2.58

Logo após calcular a matrix de correlação, CFS segue com a medida de avaliação:

Mér i to (S) = d × rac√d +d (d −1)raa

2.59

Na Equação 2.59, temos:

Mér i to (S) - mérito de um subconjunto de atributos S ⊂ D contendo d atributos;

rac - é a média da correlação entre atributos e a classe;

raa - é a média da correlação entre atributos com outros atributos;

2.5. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 74

O poder preditivo do conjunto de atributos avaliado é indicado pelo numerador,

enquanto o denominador indica o quão redundantes são os atributos.

2.5.3 Chi Square Feature Evaluation

O teste estatístico Chi Square é utilizado para seleção de atributos com a medição

do grau de independência entre cada atributo e a classe (FRANK et al., 2005). As

hipóteses desse teste são:

• H0: não há correlação entre os atributos (são independentes);

• H1: há correlação entre os atributos (um influencia no outro).

O teste é calculado pela Equação 2.61, que deve ser precedida pelo cálculo da

frequência esperada Ei j (Equação 2.60) para todas as combinações possíveis dos

valores do atributo F com cada classe C .

Ei j =q fi ×qc j

n

2.60

No cálculo de Ei j , temos:

• q fi é a quantidade de instâncias que possui o valor fi , sendo i petencente ao

conjunto T do número de possíveis valores para o atributo F (i ∈ T |T = 1 É i É t )

• qc j é a quantidade de instâncias da classe c j , sendo j pertencente às classes

possíveis da base de dados ( j ∈C |C = 1 É i ÉC ).

• e n é o número de instâncias da base de dados.

Além de Ei j , o cálculo do teste Chi Square Feature Evaluation (Equação 2.61) possui

Oi j como a razão entre a quantidade de instâncias que possuem o valor fi e a classe

c j , simultaneamente, sobre o número total de instâncias da base de dados n.

X 2 =t∑

i=1

C∑j=1

Oi j −Ei j

Ei j

2.61

A hipótese nula (H0) é rejeitada ao ultrapassar um limiar tabelado pelo teste esta-

tístico Chi Square, a partir dos graus de liberdade calculados pela Equação 2.62.

g l = (T −1)∗ (C −1) 2.62

Como faz o cálculo dos atributos individualmente, Chi Square Feature Evaluation

gera um ranking dos atributos, no qual quanto maior for o X 2 calculado, maior

correlação o atributo tem com o atributo classe, e assim, melhor é a sua classificação

no ranking.

2.5. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 75

2.5.4 Relief - F

Espera-se que instâncias da mesma classe tenham atributos com valores próximos,

enquanto instâncias de classes diferentes tenham maior distinção entre seus valores.

Baseados nessa ideia, KIRA; RENDELL (1992) construiram o algoritmo Relief que

atribui pesos para indicar a relevância de cada atributo e os ordena em ranking de

acordo com o atendimento a esses critérios. Inicialmente, o algoritmo seleciona,

aleatoriamente, uma instância da base de dados. Para essa instância, são procurados

o vizinho mais próximo da mesma classe (nearest hit) e o vizinho mais próximo de

outra classe (nearest miss). A instância selecionada é então comparada com seus

vizinhos e tem o peso dos seus atributos iniciados em zero e atualizados pela equação:

Wx =Wx − di f f (X ,R,nH)2

a+ di f f (X ,R,nM)2

a

2.63

Para a Equação 2.63, considere:

• Wx é o peso do atributo x;

• R é uma instância escolhida aleatoriamente;

• nH é o vizinho mais próximo da mesma classe (nearest hit);

• nM é o vizinho mais próximo de uma classe diferente (nearest miss).

• a é o número de instâncias amostradas aleatoriamente;

• A função di f f calcula a diferença entre duas instâncias para um dado atributo.

O processo é realizado com uma quantidade escolhida pelo usuário de a instâncias

amostradas aleatoriamente.

Relief - F é uma melhoria proposta por KONONENKO (1994) para o algoritmo

Relief de KIRA; RENDELL (1992). O problema encontrado por KONONENKO (1994)

em Relief foi não atender a mais de duas classes. Assim, propuseram Relief - F que

com os mesmos princípios de Relief atribui pesos de relevância aos atributos, porém,

trata de múltiplas classes com a ponderação das diferenças entre a instância analisada

e k vizinhos de cada classe distinta e da mesma classe, utilizando a probabilidade a

priori P de cada classe. Essa mudança ainda ajuda a suavizar a influência dos ruídos

no processo de Relief.

A equação para Relief - F é:

Wx =Wx −

k∑j=1

di f f(X ,R,nH j

)2

a ×k+

∑C 6=cl ass(R)

[P (C )

P (cl ass(R))

k∑j=1

di f f(X ,R,nM j

)2

]a ×k

2.64

2.6. MÉTODOS DE REAMOSTRAGEM 76

Ao final, cada peso dos atributos reflete a sua capacidade de distinguir valores

entre as classes.

2.6 Métodos de reamostragem

Métodos de reamostragem são técnicas que manipulam um conjunto de dados

para a obtenção de uma quantidade maior de novos conjuntos. Em Reconhecimento

de Padrões, esses métodos estão vinculados a comitês de classificadores. São utili-

zados para gerar diversidade e diminuir a correlação entre classificadores treinados

com as diferentes amostras geradas no processo de reamostragem. A resposta de um

comitê é uma combinação dos resultados obtidos pelos classificadores treinados.

Neste trabalho, não estamos interessados em comitês de classificadores, mas,

no processo de geração de novas bases de dados a partir de uma única, da qual

amostras são selecionadas obedecendo os critérios do método de reamostragem.

O objetivo é gerar mais representatividade dos dados. As manipulações da base

de dados podem ser realizadas com mudanças nos atributos ou instâncias e com

subamostragem (quando a base reamostrada é produto da redução da base original)

ou sobreamostragem (quando dados artificiais são gerados para fazer a reamostragem).

Além disso, os métodos podem usar reposição ou não reposição de dados que já foram

utilizados em uma nova base, para a criação de outra. O método de reamostragem

utilizado nos experimentos da arquitetura proposta foi o Bagging de BREIMAN (1996),

descrito a seguir.

2.6.1 Bagging

Também conhecido como Bootstrap Aggregating, Bagging é um método de reamos-

tragem bastante simples e intuitivo. Dado um conjunto de treinamento T = x1, . . . , xn

com N instâncias, o algoritmo cria subconjuntos de N ′ < N instâncias selecionadas

aleatoriamente do conjunto original, com reposição da instância selecionada a cada

inclusão em uma nova base.

O Algoritmo 2.7 apresenta o pseudo-código de Bagging apenas na fase de reamos-

tragem, excluindo a classificação como comitê.

2.7. TRABALHOS RELACIONADOS 77

Algoritmo 2.7 Pseudo-código: BaggingEntrada: T = x1, . . . , xn . conjunto de N instâncias originais da base de dados

Entrada: P . Porcentagem de seleção de instâncias da base de dados T

Entrada: Q . Quantidade de novas bases a serem criadas

Saída: S = s1, ..., si . conjunto de instâncias selecionadas

1: I = P ×N . Cálculo da quantidade de instâncias a serem selecionadas

2: para q ← 1 até Q faça

3: para i ← 1 até I faça

4: Escolha aleatória de x j ∈ T

5: S ← S ∪x j

6: fim para

7: fim para

2.7 Trabalhos relacionados

Pesquisas sobre meta-aprendizagem para a escolha de Métodos de Seleção de

Instâncias (MSIs) são recentes. Estudos iniciais focaram na criação de medidas de

caracterização de dados e na investigação da relação entre essas medidas e a per-

formance de MSIs. MOLLINEDA; SÁNCHEZ; SOTOCA (2005) usaram medidas de

caracterização de dados para predizer se a aplicação de um MSI é adequada ou não,

dado um problema. Iniciando a utilização de meta-aprendizagem, SOTOCA; MOL-

LINEDA; SANCHEZ (2006) revisaram algumas medidas de caracterização de dados

e indicaram possíveis aplicações da abordagem, sugerindo o uso para Métodos de

Seleção de Instâncias. SMITH-MILES; ISLAM (2010) adotaram meta-aprendizagem

para verificar a relação entre o sucesso de um MSI, características dos dados e métodos

de aprendizagem de máquinas.

A seleção do melhor MSI para uma base de dados foi estudada por CAISES et al.

(2011). Eles propuseram o método Selective Combination for Instance Selection (SCIS)

para determinar o mais adequado MSI a ser aplicado às bases de dados de entrada.

O SCIS usa regras empíricas construídas com base em medidas de caracterização

de bases de dados. Embora esse estudo tenha obtido bons resultados, o processo é

limitado. Considerando que são feitas por humanos, regras empíricas são limitadas

ao tamanho da amostra, esforço do especialista e duração da análise, que afetam

diretamente a eficácia e eficiência do processo.

Mais recentemente, LEYVA; GONZáLEZ; PéREZ (2013) afirmaram que faltam, no

2.7. TRABALHOS RELACIONADOS 78

campo relacionado a escolha de MSIs por meio de meta-aprendizagem, propostas

direcionadas a uma abordagem integral, além da necessidade de estabelecer diretrizes

para o desenvolvimento de sistemas capazes de explorar seus benefícios. Com este

propósito, no mesmo artigo, lançaram um framework e o sistema Knowledge-base IS

(KBIS) que foi mais profundamente estudado em LEYVA et al. (2014). O sistema KBIS

faz um balanceamento entre precisão e redução, possilibitando flexibilização para

um ou para o outro através do parâmetro b, escolhido pelo usuário. Utiliza regressão

linear para predizer a performance de redução à parte de precisão, ao invés de indicar

o melhor desempenho entre candidatos. Após o cálculo do balanceamento, verifica

o MSI que o maximiza e aplica esse à base de dados. A modularidade de preditores

permite que algoritmos de seleção de instâncias sejam adicionados sem a necessidade

de retreino para todo o processo. O trabalho, no entanto, utilizou poucas medidas

de caracterização de dados e o sistema KBIS apresentou algumas desvantagens por

ser dependente do classificador utilizado para a criação das meta-instâncias e ser

dependente da quantidade de meta-instâncias para treino.

Nossa proposta com Meta-CISM é estudar classificação ao invés de regressão,

com o intuito de indicar o melhor MSI entre os candidatos para uma base de dados.

Buscamos generalização na criação de meta-instâncias com o uso da média de preci-

são de classificadores pertencentes a abordagens diferentes. Além disso, utilizamos

reamostragem para ter uma boa representatividade no treino do meta-classificador.

797979

3Meta-CISM

Meta-learning for Choosing Instance

Selection Method

Este capítulo descreve o método proposto: Meta-CISM (Meta-learning for Choo-

sing Instance Selection Method), que tem o objetivo de escolher o “melhor” Método de

Seleção de Instâncias (MSI) para um dado problema (tarefa). O método foi desenvol-

vido para lidar com problemas de classificação supervisionada, ou seja, as instâncias

dessas tarefas são definidas por um vetor de características e por uma classe. O con-

junto de todas as instâncias de cada tarefa é denominado base de dados. Sendo um

problema representado por uma base de dados, cada instância do método proposto

(Meta-CISM), denominada meta-instância, é representada por um vetor de caracte-

rísticas e uma classe extraídos dessa base de dados. O conjunto de meta-instâncias

forma a meta-base.

O método é composto por duas partes: Geração do meta-classificador e Avaliação

do meta-classificador. Para a geração do meta-classificador (Seção 3.1), cada base

de dados passa por um processo de reamostragem, a fim de aumentar a quantidade

de bases, e assim, o tamanho da meta-base de treinamento, visto que cada base de

dados gera apenas uma meta-instância. Em seguida, as bases de dados resultantes são

usadas para produzir meta-instâncias. Essa atividade é realizada pelos módulos de

Extração de Características e de Anotação. Todas as meta-instâncias geradas formam

a meta-base que pode ser submetida ao Módulo de Seleção de Atributos, definido

na Seção 3.1.3. Finalmente, o meta-classificador é treinado para gerar a função

capaz de indicar o “melhor” MSI para novas bases de dados, na Seção 3.1.4. O meta-

classificador é avaliado usando uma base de dados de teste, conforme descrito na

Seção 3.2.

3.1. GERAÇÃO DO META-CLASSIFICADOR F 80

3.1 Geração do meta-classificador F

O objetivo da Geração do meta-classificador F é obter uma função destinada a

escolher entre vários MSIs, aquele mais adequado para uma base de dados (Figura 3.1).

Para um bom desempenho no treinamento desse meta-classificador, é necessário

compor uma meta-base com informações relevantes sobre como a estrutura da base

dados pode influenciar na performance dos MSIs.

A construção da meta-base é composta por duas fases: Reamostragem (Seção 3.1.1)

e Geração de meta-instância (Seção 3.1.2). Uma vez que a meta-base foi construída, é

possível treinar o meta-classificador F. No entanto, visando melhorar a taxa de acerto

desse meta-classificador F e reduzir o custo computacional, os melhores atributos da

meta-base são selecionados pelo módulo de Seleção de atributos.

3.1.1 Reamostragem

Dado que meta-aprendizagem pode ser definida como aprender sobre o próprio

processo de aprendizagem, o processo de classificação na meta-aprendizagem tam-

bém necessita de uma base de dados, denominada meta-base. Cada meta-instância

dessa meta-base tem seu vetor de características e classe extraídos de uma base de

dados que representa uma tarefa específica. Assim, cada base de dados Γi gera apenas

uma meta-instância.

O tamanho da meta-base deve ser diretamente relacionado à quantidade de MSIs a

serem usados, visto que ela deve ter meta-instâncias suficientes para representar cada

MSI. Esse tamanho também deve ter uma boa proporção em relação à quantidade

de meta-atributos para fugir da maldição da dimensionalidade, além de estar direta-

mente relacionado ao classificador a ser usado no treino do meta-classificador. Alguns

classificadores como MLP têm melhor desempenho com a utilização de grandes

quantidades de instâncias durante a aprendizagem.

Para aumentar o número de bases de dados disponíveis e, portanto, aumentar a

quantidade de meta-instâncias para o treinamento do meta-classificador, a primeira

fase para a construção da meta-base é a reamostragem. Nessa fase, um método de

reamostragem cria novas bases de dados Γi j a partir das originais Γi , usando variações,

com reposição ou sem reposição, das instâncias ou atributos da base de dados Γi .

O método de reamostragem a ser utilizado deve garantir a diversidade entre as

bases de dados a serem geradas. É importante analisar como o método faz a reamos-

tragem (por características ou por instâncias) e se a quantidade necessária de novas

bases relacionada à quantidade de instâncias ou de características da base de dados

original não gerará bases redundantes. Entre os métodos da literatura, podemos citar

o Bagging (BREIMAN, 1996) e Random Subspace (HO, 1998).

3.1. GERAÇÃO DO META-CLASSIFICADOR F 81

Figura 3.1: Processo de construção da Meta-base e treinamento dometa-classificador. Cada base de dados é submetida à fase de reamostragempara aumentar o número de bases de dados disponíveis. Cada nova base dedados passa pelos processos de Extração de características e Anotação para

tornar-se uma meta-instância. A meta-base resultante pode ser reduzida peloprocesso de Seleção de Características. Em seguida, é usada para treinar o

meta-classificador F.

3.1. GERAÇÃO DO META-CLASSIFICADOR F 82

O Bagging, por exemplo, gera bases Γi j com a criação de subconjuntos aleatórios

das instâncias da base de dados Γi , com reposição das instâncias a cada nova base

criada. Esse método foi escolhido como base para os experimentos devido à sua

popularidade e simplicidade de implementação.

Outros testes foram realizados com Random Subspace. Porém, como esse método

faz a reamostragem aleatória das características de uma base de dados, a necessidade

de criação de novas bases a partir de outras que continham poucos atributos resultou

na criação de muitas bases iguais e por isso seus experimentos não foram levados

adiante.

Com o intuito de criar a maior quantidade de bases, com a maior diversidade

possível, através da manipulação dos seus atributos, criamos um novo método de rea-

mostragem, chamado Combination. Na próxima seção (Seção 3.1.1.1), apresentamos

e exemplificamos o uso do método.

3.1.1.1 Proposta de reamostragem

Neste trabalho, propomos uma reamostragem que combina os atributos de uma

base de dados, denominada Combination. A técnica utiliza análise combinatória,

fazendo combinação simples dos atributos de uma base de dados para formar sub-

bases com atributos diferentes ou em quantidades diferentes, mantendo o mesmo

número de instâncias da base a partir da qual foi derivada. A quantidade de bases que

podem ser geradas depende da quantidade de atributos da base de dados original,

obedecendo a Equação 3.1.

k =d∑

p=1

d !

p !(d −p)!

3.1

Considere d o número de características da base de dados original e p, variando

p = 1, . . . ,d , a quantidade de características das novas bases na realização da combina-

ção. Para cada quantidade de características p, uma certa quantidade de combinações

k ′ podem ser feitas, gerando novas bases. Logo, cada base de dados Γi pode gerar um

número k de novas bases Γi j , com j = 1,2, . . . ,k. Isso corresponde à soma das quanti-

dades de combinações k ′ possíveis com cada variação do número de características

p.

Para facilitar a compreensão do que foi explanado sobre Combination, considere

uma base de dados Γi com um conjunto de atributos A = a1, a2, a3. Conforme descrito

no método, d é a quantidade de atributos da base de dados, neste caso, do conjunto

A, d = 3. O valor de p faz todas as variações possíveis da quantidade de atributos

existentes em A, para gerar os atributos das novas bases Γi j . Ou seja, p terá os valores

p = 1,2 e 3 e as k novas bases Γi j (com j = 1,2, . . . ,k) terão 1,2 ou 3 atributos. Pela

3.1. GERAÇÃO DO META-CLASSIFICADOR F 83

Equação 3.1, temos:

• Quando p = 1, serão geradas 3 novas bases de dados.

k1 = 3!

1!(3−1)!= 6

2= 3

3.2

• Para p = 2, mais 3 novas bases de dados serão geradas.

k2 = 3!

2!(3−2)!= 6

2= 3

3.3

• E finalmente, quando p = 3, mais 1 nova base de dados será gerada.

k3 = 3!

3!(3−3)!= 6

6= 1

3.4

Ao total, o número de novas bases Γi j geradas será k = k1 +k2 +k3 = 7. Equivalente

ao somatório das quantidades de bases geradas com ps diferentes.

k =3∑

p=1

3!

p !(3−p)!= 7

3.5

Dependendo da quantidade de bases de dados novas Γi j desejadas para cada base

Γi , o valor de d pode ser considerado pequeno e a quantidade de novas bases Γi j

também será pequena. Por outro lado, se d for considerado grande, não será possível

utilizar todas as bases Γi j geradas. Nesse caso, sugerimos fazer uma compensação,

utilizando todas as bases Γi j geradas por aquelas Γi que contêm poucas características

(d pequeno) e escolhendo aleatoriamente bases Γi j geradas por bases de dados Γi

que contêm muitas características (d grande), até completar a quantidade de bases

desejadas no fim da fase de reamostragem.

O pseudo-código para o método de reamostragem Combination é apresentado a

seguir, no Algoritmo 3.1.

3.1. GERAÇÃO DO META-CLASSIFICADOR F 84

Algoritmo 3.1 Método de Reamostragem CombinationEntrada: Γi . Base de dados a ser reamostrada

Entrada: A = a1, . . . , ad . Conjunto de atributos da base de dados Γi

Saída: Bases de dados Γi j , com j = 1,2, . . . ,k . Bases geradas após a reamostragem

1: para p ← 1 até d faça

2: kp ← d !p !(d−p)! . Verifica quantas combinações de atributos são possíveis para

cada variação de p

3: para j ← 1 até kp faça

4: A1 ← combinação j com kp atributos de A. . Seleção de atributos de A, de

acordo com a combinação j

5: Γi j ← Γi (A1) . Criação da nova base Γi j a partir da base original Γi e a

seleção de atributos A1

6: fim para

7: fim para

3.1.2 Geração de meta-instância

Na fase de Geração de meta-instância, após a reamostragem, cada base de dados

Γi j passa pelo processo de Extração de características, com o propósito de gerar

descritores da meta-instância; e pelo processo de Anotação, para gerar o rótulo dessa

meta-instância.

O módulo de Extração de características extrai medidas de caracterização de

dados de cada base de dados Γi j , gerando descritores da meta-instância. Esses descri-

tores têm como objetivos extrair informações sobre a estrutura das bases de dados e

extrair informações que influenciem na performance dos MSIs para o treinamento do

meta-classificador.

Diversos trabalhos, como os de SOTOCA; MOLLINEDA; SANCHEZ (2006), CAI-

SES et al. (2011) e LEYVA et al. (2014), sugerem meta-características que podem ser

utilizadas nesse módulo. A Tabela 3.1 mostra as meta-características extraídas nos

experimentos deste trabalho, descritas na Seção 2.3. A coluna Tipo classifica as medi-

das de acordo com a informação geral que extrai dos dados; a coluna Medida indica

o nome da medida de caracterização de dados; e as colunas Numéricos e Categóri-

cos informam se a medida consegue ser extraída a partir de valores numéricos ou

categóricos, respectivamente.

A classe da meta-instância é dada pelo Módulo de Anotação. Esse módulo é

responsável por rotular a meta-instância com a referência do “melhor” MSI, podendo

levar em consideração a precisão de classificação, a redução, o custo computacional ou

3.1. GERAÇÃO DO META-CLASSIFICADOR F 85

uma combinação desses. Neste trabalho, o “melhor” MSI é aquele que alcançar a maior

média de precisão de classificação para cada base de dados Γi j . A precisão média para

cada MSI é calculada da seguinte forma: (1) a base de dados Γi j é reduzida usando N

diferentes MSIs e (2) os novos conjuntos de instâncias gerados Ωi (i = 1,2, . . . , N) são

submetidos a M classificadores (c1,c2, . . . ,cM ) para obter suas precisões de classificação.

Depois de obtidas as médias dessas precisões, o MSI com maior média é representado

por uma classe (MSI1, MSI2, . . . , MSIn) para rótular a meta-instância. Esse processo é

ilustrado na Figura 3.2. Para minimizar a influência dos classificadores sobre a decisão

do “melhor” MSI, os classificadores envolvidos devem ser diversos e usar diferentes

abordagens de aprendizado.

3.1. GERAÇÃO DO META-CLASSIFICADOR F 86

Tabela 3.1: Medidas de caracterização dos dados

Tipo Medida Numéricos Categóricos

Estatística

Número de instâncias Sim Sim

Número de atributos Sim Sim

Número de classes Sim Sim

Atributos numéricos Sim Sim

Atributos binários Sim Sim

Atributos nominais Sim Sim

Proporção de atributos numéricos Sim Sim

Proporção de atributos binários Sim Sim

Proporção de atributos nominais Sim Sim

Nível de ruído Sim Sim

Desbalanceamento Sim Sim

Entropia Sim Sim

Baseada em

conjunto local

Pontos isolados Sim Sim

Número de regiões Sim Sim

Distância intergrupos Sim Sim

Distância intragrupos Sim Sim

Distância gruposNE Sim Sim

Diâmetro do grupo Sim Sim

LscAvgNorm Sim Sim

Separabilidade

de classes

N1 Sim Sim

N2 Sim Sim

N3 Sim Sim

Geometria e

densidade

T1 Sim Sim

T2 Sim Sim

D1 Sim Sim

D2 Sim Não

D3_K3 Sim Sim

D3_K5 Sim Sim

SobreposiçãoF1 Sim Não

F2 Sim Não

3.1. GERAÇÃO DO META-CLASSIFICADOR F 87

Figura 3.2: Módulo de Anotação. Cada base de dados Γi j é reduzida por Ndiferentes MSIs e as precisões das bases de dados resultantes Ωl são calculadascomo a média dos M classificadores cm . O rótulo é o MSI com a maior média de

precisão.

3.1.3 Seleção de atributos

Posto que dentre as meta-características geradas pelo processo de Extração de

características, algumas podem ser irrelevantes ou podem prejudicar a performance

do meta-classificador, o desempenho de treinamento do meta-classificador pode ser

favorecido com o uso de um método de seleção de atributos.

Portanto, o Módulo de Seleção de Atributos tem o objetivo de formar uma nova

meta-base com meta-características selecionadas de tal maneira que a performance

de classificação dessa nova meta-base seja melhor ou igual à performance de classifi-

cação da meta-base com todas as meta-características originais.

No Meta-CISM, esse módulo é opcional, dado que as meta-características do

processo de Extração de características podem ser poucas, suficientes ou consideradas

importantes para o treinamento do meta-classificador.

3.2. AVALIAÇÃO DO META-CLASSIFICADOR F 88

3.1.4 Treinamento do meta-classificador

Com a meta-base construída, o treinamento do meta-classificador é realizado com

um algoritmo de classificação que aprenderá a relação entre os atributos (descritores

representantes das bases de dados) e as classes (rótulos representantes dos “melhores”

MSI para a cada base), gerando uma função do meta-classificador treinado F, capaz

de definir o “melhor” MSI para novas bases.

3.2 Avaliação do meta-classificador F

Com o meta-classificador treinado, a operação e teste desse é feita através da

Avaliação do meta-classificador F. Bases de dados de teste ∆ têm suas medidas de

caracterização extraídas. Em seguida, essas meta-características podem ser reduzidas

por um método de seleção de atributos. Finalmente, são submetidas à função F do

meta-classificador treinado. E essa função F é a responsável por indicar o “melhor”

MSI para a base de dados de entrada.

Figura 3.3: Avaliação do Meta-classificador. Cada base de dados de teste temsuas meta-características extraídas. A quantidade de meta-características podeser reduzida se o módulo de seleção de atributos for utilizado. Finalmente, sãosubmetidas ao meta-classificador treinado F para obter o MSI mais adequado

para a base de dados de entrada ∆.

898989

4Estudo Experimental

Neste capítulo são apresentados os detalhes de como os experimentos foram reali-

zados e os resultados obtidos para validação do método proposto: Meta-CISM (Meta-

learing for Choosing Instance Selection Method). O método Meta-CISM é avaliado com

e sem o módulo de seleção de atributos para três meta-bases: mbBagging, para essa

meta-base, o método Bagging foi utilizado na fase de reamostragem; mbCombination,

gerada com o método de reamostragem Combination; e mbBaggingCombination, que

é uma meta-base construída com a união das outras duas meta-bases mencionadas.

A Seção 4.1 mostra a estrutura das bases de dados, a metodologia para os métodos

de reamostragem e sumariza as medidas de caracterização das bases. A Seção 4.2

apresenta os métodos de seleção de instâncias e classificadores utilizados para a cons-

trução das meta-bases. Na Seção 4.3 são descritos os experimentos para a escolha do

classificador aplicado como meta-classificador. Estão presentes nessa seção, inicial-

mente, a descrição dos estudos realizados para escolher valores para os parâmetros

necessários ao KNN e à MLP-BP. Em seguida, a seção apresenta uma análise de todos

os classificadores selecionados, com o propósito de escolher o mais adequado para

uso como meta-classificador. A Seção 4.4 discorre sobre os métodos de seleção de

atributos e as configurações utilizadas para esses. Além disso, essa seção relata uma

análise sobre os métodos de seleção de atributos a serem utilizados na avaliação do

método Meta-CISM. Os resultados da versão de Meta-CISM sem seleção de atribu-

tos são mostrados na Seção 4.5 e a validação da inclusão do Módulo de Seleção de

Atributos é avaliada na Seção 4.6. A Seção 4.7 sumariza os resultados obtidos.

As medidas de caracterização dos dados foram implementadas usando o software

Matlab 2012b. Os experimentos para redução da base de dados e classificação no Mó-

dulo de Anotação foram executados no Keel Tool 2.0. E os procedimentos de seleção

de atributos e classificação no treinamento do meta-classificador foram realizados no

software Weka 3.6.10.

4.1. BASES DE DADOS 90

4.1 Bases de dados

Nos experimentos, são utilizadas 16 bases de dados, apresentadas na Tabela 4.1.

Dessas, as doze primeiras são do repositório UCI Machine Learning (LICHMAN, 2013),

as duas subsequentes são do LIBSVM (RONG-EN, 2011), a seguinte é da mldata.org

(SONNENBURG et al., 2009-2015) e a última é do artigo de BERNADÓ; LLORA; GAR-

RELL (2002).

Tabela 4.1: Informações das bases de dados

Base de dados # Instâncias # Atributos # Classes # CategóricosBalance Scale 625 4 3 0

Banknotes 1372 4 2 0

Ecoli 336 7 8 0

Parkinsons 197 23 2 0

Sonar 208 60 2 0

Tic tac toe 958 9 2 9

Transfusion 748 4 2 0

Vehicle 946 18 4 0

VertebralColumn 2C

310 6 2 0

Vowel 528 10 11 0

Wall-followingSensor 2

5456 2 4 0

Wall-followingSensor 4

5456 4 4 0

Fourclass Scale 862 2 2 0

German 1000 24 2 0

Banana 138 2 2 0

Tao 1888 2 2 0

Com o intuito de aumentar a quantidade de amostras para o treinamento do meta-

classificador, para cada procedimento de reamostragem (Bagging (BREIMAN, 1996)

e Combination - descritos no Capítulo 3), são criadas 800 bases de dados Γi , j , com

i = 1,2, . . . ,16 e j = 1,2, . . . ,50, a partir da formação de 50 novas bases de dados para cada

base de entrada Γi , como ilustrado na Figura 3.1.

São realizados experimentos com as meta-bases dos procedimentos de Bagging

(mbBagging ) e Combination (mbCombination) separadas, e posteriormente, com a

união dessas, formando uma meta-base de 1600 meta-instâncias (mbBaggingCombi-

nation).

4.2. CONFIGURAÇÕES PARA O MÓDULO DE ANOTAÇÃO 91

O Módulo de Extração de Características extrai trinta medidas de caracterização

de dados sobre as bases, descritas no Capítulo 2. A Tabela 3.1 mostra tais medidas

organizadas por tipo e a indicação dos tipos de dados com os quais trabalham.

4.2 Configurações para o Módulo de Anotação

Para o Módulo de Anotação, foram usados cinco MSIs (MSI1, MSI2, . . . , MSI5) de

abordagens distintas e com performance relevante em trabalhos publicados, conforme

abordado no Capítulo 2. São eles: C-pruner (ZHAO et al., 2003), DROP3 (WILSON;

MARTINEZ, 2000), IB3 (AHA; KIBLER; ALBERT, 1991), ICF (BRIGHTON; MELLISH,

2002) e ENN-CNN (CAISES et al., 2011).

Quanto aos classificadores, também foram escolhidos cinco representantes de

diferentes abordagens: C4.5 (árvore de decisão) (QUINLAN, 1993), K Nearest Neigh-

bors - KNN (lazy learning ) (COVER; HART, 1967), Sequential Minimal Optimization

- SMO (máquina de vetores de suporte) (PLATT, 1999), Multilayer Perceptron com

Backpropagation - MLP-BP (rede neural) (RUMELHART; HINTON; WILLIAMS, 1986)

e PART (Crisp rule) (FRANK; WITTEN, 1998). Os parâmetros desses classificadores

seguiram os valores padrões do software. E todos utilizaram o método de validação

cruzada k-fold, com k = 10.

Para os cálculos de distâncias, usamos Heterogeneous Value Difference Metric -

HVDM (WILSON; MARTINEZ, 1997) porque é uma medida de distância heterogênea,

ou seja, consegue trabalhar tanto com atributos numéricos como categóricos.

4.3 Meta-classificadores

Qualquer algoritmo de classificação supervisionada poderia ser utilizado para o

treinamento do meta-classificador. Neste trabalho, analisamos as saídas de 4 classifi-

cadores, também utilizados para geração das precisões médias dos MSIs: C4.5 (QUIN-

LAN, 1993), K Nearest Neighbors - KNN (COVER; HART, 1967), Multilayer Percep-

tron com Backpropagation - MLP-BP (RUMELHART; HINTON; WILLIAMS, 1986) e

PART (FRANK; WITTEN, 1998).

4.3.1 Configuração de parâmetros

Os parâmetros dos classificadores KNN e MLP-BP podem variar em diversos valo-

res. As Subseções 4.3.1.1 e 4.3.1.2, mostram estudos para indicar a melhor configura-

ção desses classificadores para serem utilizados como meta-classificadores. Nesses

4.3. META-CLASSIFICADORES 92

experimentos, foram utilizados o método de validação cruzada k-fold (com k=10) e a

medida de distância Euclidiana.

4.3.1.1 Parâmetros para KNN

Para o KNN (K Nearest Neighbour), é necessário a escolha do parâmetro K, ou seja,

a quantidade de vizinhos utilizados pelo algoritmo. A Figura 4.1 mostra as taxas de

acerto desse classificador aplicado às três meta-bases, com as variações de k = 1, 3, 5 e

7.

45

47

49

51

53

55

57

59

61

k = 1 k = 3 k = 5 k = 7

Taxa

de

ace

rto

(%

)

Variações do parâmetro K

mbBagging mbCombination mbBaggingCombination

Figura 4.1: Parâmetro K para KNN. Taxas de acerto com barras de erro paracada meta-base em relação a cada valor de K.

As maiores taxas de acerto para as três meta-bases são obtidas quando k é igual a

5, portanto, esse valor é utilizado como parâmetro para o meta-classificador KNN.

4.3.1.2 Parâmetros para MLP-BP

A rede neural Multilayer Perceptron com Backpropagation (MLP-BP) teve 32 varia-

ções ao modificar seus parâmetros, conforme as combinações possíveis para:

• momento (M): 0,1 e 0,2;

• taxa de aprendizado (L): 0,2 e 0,3, com decaimento e sem decaimento.

Observando o comportamento das taxas de acerto em relação a variações de

camadas escondidas e aos demais parâmetros da MLP-BP, percebemos que as maiores

taxas correspondem à utilização de apenas uma camada. Por isso, focamos sobre uma

4.3. META-CLASSIFICADORES 93

camada escondida para a investigação da quantidade de neurônios a ser utilizado, de

acordo com a Tabela 4.2.

Tabela 4.2: Quantidade de neurônios para primeira camada escondida de umaMLP-BP

Símbolo Representação #Neurônios

cl #classes 5

at #atributos 30

ac #atributos + #classes 35

ac_avg (#atributos + #classes)/2 17

As Figuras 4.2, 4.3 e 4.4 mostram que dentre as três meta-bases, duas (mbBagging

e mbCombination) alcançam as maiores taxas de acerto com "cl", equivalente a 5

neurônios correspondentes ao número de classes do problema. Verifica-se ainda que

mbCombination e mbBaggingCombination não tiveram suas classificações benefiadas

com a utilização de decaimento da taxa de aprendizado.

55

56

57

58

59

60

L = 0,2 Com decaimento

L = 0,2 L = 0,3 Com decaimento

L = 0,3 L = 0,2 Com decaimento

L = 0,2 L = 0,3 Com decaimento

L = 0,3

M = 0,1 M = 0,1 M = 0,1 M = 0,1 M = 0,2 M = 0,2 M = 0,2 M = 0,2

Taxa

de

ace

rto

(%

)

Parâmetros: momento (M) e taxa de aprendizado (L)

cl at ac ac_avg

Figura 4.2: Camadas escondidas para MLP-BP (meta-base mbBagging ).Com a meta-base mbBagging, é exibida a influência da quantidade neurônios

em uma camada escondida sobre a taxa de acerto, a partir das possíveisvariações de taxa de aprendizado e momento.

4.3. META-CLASSIFICADORES 94

49

50

51

52

53

54

55

56

L = 0,2 Com decaimento

L = 0,2 L = 0,3 Com decaimento

L = 0,3 L = 0,2 Com decaimento

L = 0,2 L = 0,3 Com decaimento

L = 0,3

M = 0,1 M = 0,1 M = 0,1 M = 0,1 M = 0,2 M = 0,2 M = 0,2 M = 0,2

Taxa

de

ace

rto

(%

)

Parâmetros: momento (M) e taxa de aprendizado (L)

cl at ac ac_avg

Figura 4.3: Camadas escondidas para MLP-BP (meta-base mbCombination).Com a meta-base mbCombination, é exibida a influência da quantidadeneurônios em uma camada escondida sobre a taxa de acerto, a partir das

possíveis variações de taxa de aprendizado e momento.

4.3. META-CLASSIFICADORES 95

49

50

51

52

53

54

55

56

57

L = 0,2 Com decaimento

L = 0,2 L = 0,3 Com decaimento

L = 0,3 L = 0,2 Com decaimento

L = 0,2 L = 0,3 Com decaimento

L = 0,3

M = 0,1 M = 0,1 M = 0,1 M = 0,1 M = 0,2 M = 0,2 M = 0,2 M = 0,2

Taxa

de

ace

rto

(%

)

Parâmetros: momento (M) e taxa de aprendizado (L)

cl at ac ac_avg

Figura 4.4: Camadas escondidas para MLP-BP (meta-basembBaggingCombination). Com a meta-base mbBaggingCombination, é

exibida a influência da quantidade de neurônios em uma camada escondidasobre a taxa de acerto, a partir das possíveis variações de taxa de aprendizado e

momento.

4.3. META-CLASSIFICADORES 96

Por fim, a Figura 4.5 apresenta, para as três meta-bases, a relação entre a taxa

de acerto e as combinações de momento e taxa de aprendizado sem decaimento,

utilizando uma camada escondida com 5 neurônios. Apesar da melhor taxa de acerto

para a meta-base mbBagging ser equivalente a M = 0,2 e L = 0,3, as demais bases não

acompanham esse desempenho. Observa-se, no entanto, boas taxas de acerto para as

três meta-bases quando M = 0,2 e L = 0,2, correlato à melhor média de taxa de acerto

entre essas meta-bases, para cada par de parâmetros.

46

48

50

52

54

56

58

60

62

mbBagging mbCombination mbBaggingCombination Médias

Taxa

de

ace

rto

(%

)

Meta-bases

(M = 0,1 L = 0,2) (M = 0,1 L = 0,3) (M = 0,2 L = 0,2) (M = 0,2 L = 0,3)

Figura 4.5: Taxa de aprendizado e momento para MLP-BP. Taxas de acertoindividuais e média das taxas de acerto de todas as meta-bases, por

combinação de taxa de aprendizado com momento, para indicação dacombinação mais adequada a ser utilizada na MLP-BP.

Logo, são escolhidos como parâmetros para o meta-classificador baseado na rede

neural MLP com Backpropagation: uma camada escondida com 5 neurônios, taxa

de aprendizado L = 0,2 sem decaimento e momento M = 0,2. A função de transfe-

rência utilizada foi a tangente hiperbólica e o treinamento ocorreu com validação

cruzada k-fold, com k = 10.

4.3.2 Avaliação dos meta-classificadores

O algoritmo de classificação utilizado como meta-classificador afeta diretamente

o desempenho do método Meta-CISM. Por isso, a escolha desse é feita a partir da

avaliação de quatro classificadores bem conhecidos na literatura: K Nearest Neigh-

bors - KNN (COVER; HART, 1967), Multilayer Perceptron com Backpropagation - MLP-

4.4. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 97

BP (RUMELHART; HINTON; WILLIAMS, 1986), C4.5 (QUINLAN, 1993) e PART (FRANK;

WITTEN, 1998). Os dois primeiros adotam os parâmetros estabelecidos na Seção 4.3.

A Figura 4.6 mostra as taxas de acerto desses classificadores aplicados às meta-

bases mbBagging, mbCombination e mbBaggingCombination. Notamos nesses re-

sultados que a rede neural MLP-BP obteve as maiores taxas de acerto para as três

meta-bases e, portanto, é escolhida como meta-classificador para os experimentos de

validação do método Meta-CISM.

50

51

52

53

54

55

56

57

58

59

mbBagging mbCombination mbBaggingCombination

Taxa

de

ace

rto

(%

)

Meta-bases

C4.5 KNN MLP PART

Figura 4.6: Avaliação de meta-classificadores. Taxas de acerto dosmeta-classificadores: KNN, MLP-PB, PART e C4.5 sobre as meta-bases:

mbBagging, mbCombination e mbBaggingCombination.

4.4 Métodos de seleção de atributos

Antes de submetidas ao meta-classificador, as meta-bases podem passar por um

método de seleção de atributos, a fim de diminuir o custo computacional e melhorar

a precisão na classificação.

Neste trabalho, os métodos para seleção de atributos se diferenciam, inicialmente,

pelo uso de algoritmos de busca para a escolha do melhor subconjunto de atributos

ou pelo uso de ranking de uma quantidade determinada de atributos para a base de

dados final.

4.4. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 98

4.4.1 Configuração de parâmetros

Dos métodos estudados, dois utilizam algoritmos de busca: Consistency-Based

Subset Evaluation (LIU; SETIONO, 1996) e Correlation-based Feature Selection - CFS

(HALL, 1998), ambos variando os algoritmos de busca entre Genetic Search e Best First

Search. Os outros dois ordenam os atributos, criando rankings com a variação de 1 a

30 atributos selecionados para a base final: Chi Square Feature Evaluation (FRANK

et al., 2005) e Relief - F (KONONENKO, 1994).

Avaliando os algoritmos de busca Genetic Search e Best First Search para o método

de seleção de atributos Consistency-based Subset Evaluation aplicado às meta-bases

estudadas, notamos, na Figura 4.7, que quando Best First Search é utilizado, o meta-

classificador alcança melhor desempenho.

45

47

49

51

53

55

57

59

mbBagging mbCombination mbBaggingCombination

Taxa

de

ace

rto

(%

)

Meta-bases

Best First Search Genetic Search

Figura 4.7: Algoritmos de busca para Consistency-based Subset Evaluation.Taxas de acerto do meta-classificador MLP-BP para as meta-bases: mbBagging,mbCombination e mbBaggingCombination, aplicadas ao método de seleção deatributos Consistency-based Subset Evaluation com os algoritmos de busca: Best

First Search e Genetic Search.

No caso de Correlation-based Feature Selection - CFS, a Figura 4.8 mostra que

Genetic Search obtém melhores taxas de acerto para as meta-bases.

Para os métodos que fazem ranking dos atributos de uma base de dados, podendo

avaliar desde um até todos os atributos disponíveis, as meta-bases mostram melhor

desempenho com quantidades diferentes de atributos. A análise e escolha para cada

uma é feita considerando que, quando as taxas de acerto são muito próximas, quanto

menor for a quantidade de atributos, menor será o custo computacional.

4.4. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 99

52

53

54

55

56

57

58

mbBagging mbCombination mbBaggingCombination

Taxa

de

ace

rto

(%

)

Meta-bases

Best First Search Genetic Search

Figura 4.8: Algoritmos de busca para Correlation-based Feature Selection -CFS. Taxas de acerto do meta-classificador MLP-BP para as meta-bases:

mbBagging, mbCombination e mbBaggingCombination, aplicadas ao métodode seleção de atributos Correlation-based Feature Selection - CFS com os

algoritmos de busca: Best First Search e Genetic Search.

Assim, usando Chi Square Feature Evaluation (FRANK et al., 2005), a Figura 4.9

mostra que a meta-base mbBagging tem as melhores taxas de acerto com diferença

irrelevante para 10 e 14 atributos no ranking. Logo, mbBagging é analisada com o

ranking de 10 atributos. A meta-base mbCombination também é avaliada com 10

atributos no ranking , tendo em vista que além de apresentar pouca diferença para

o melhor resultado equivalente a 26 atributos, traz uma redução do custo compu-

tacional. A meta-base mbBaggingCombination demonstra maior establidade para

a relação de quantidade de atributos e taxa de acerto. No entanto, ainda tomando

por base a menor quantidade de atributos para redução do custo computacional, a

meta-base mbBaggingCombination é avaliada com 6 atributos no ranking .

A mesma lógica é aplicada para o Relief - F (KONONENKO, 1994), mostrado na

Figura 4.10. A meta-base mbBagging utiliza nos experimentos 6 atributos no ran-

king , por ser correspondente à segunda melhor taxa de acerto com menor quantidade

de atributos. A meta-base mbCombination segue e usa o segundo melhor resultado

com o ranking de 16 atributos. Já mbBaggingCombination, apesar de ter as me-

lhores taxas com 23 e 27 atributos, usa 10 atributos no ranking para melhor custo

computacional sem muita perda em precisão.

Os atributos selecionados por Consistency-based Subset Evaluation com Best First

Search, Correlation-based Feature Selection - CFS com Genetic Search, Chi Square

Feature Evaluation e Relief - F podem ser visto na Tabela 4.3. Um histograma da

frequência de escolha desses atributos pelos métodos de seleção de atributos é apre-

sentado na Figura 4.11.

4.4. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 100

47

49

51

53

55

57

59

61

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Taxa

de

ace

rto

(%

)

Número de atributos no ranking

mbBagging mbCombinaton mbBaggingCombination

Figura 4.9: Taxas de acerto relativas às variações do número de atributos noranking para Chi Square Feature Evaluation. Taxas de acerto do

meta-classificador MLP-BP para as meta-bases: mbBagging, mbCombination embBaggingCombination, aplicadas ao método de seleção de atributos Chi

Square Feature Evaluation com variação do número de atributos no ranking de1 a 30. Os pontos em destaque correspondem às quantidades de atributos

escolhidas para cada meta-base.

35

40

45

50

55

60

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Taxa

de

ace

rto

(%

)

Número de atributos no ranking

mbBagging mbCombination mbBaggingCombination

Figura 4.10: Taxas de acerto relativas às variações do número de atributosno ranking para Relief - F . Taxas de acerto do meta-classificador MLP-BP para

as meta-bases: mbBagging, mbCombination e mbBaggingCombination,aplicadas ao método de seleção de atributos Relief - F com variação do número

de atributos no ranking de 1 a 30. Os pontos em destaque correspondem àsquantidades de atributos escolhidas para cada meta-base.

4.4. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 101

0

1

2

3

4

5

6

7

8

9

10

11

12

Frequência

Me

did

as

Figu

ra4.

11:H

isto

gram

ad

asm

eta-

cara

cter

ític

asse

leci

on

adas

pel

os

Mét

od

os

de

Sele

ção

de

Atr

ibu

tos.

Freq

uên

cia

de

esco

lha

de

cad

am

eta-

cara

cter

ísti

ca(n

ora

nge

de

0a

12),

con

sid

eran

do

aso

ma

dos

resu

ltad

osd

eca

da

met

a-b

ase

(mbB

aggi

ng,

mbC

ombi

nat

ion

em

bBag

gin

gCom

bin

atio

n)

sub

met

ida

ato

do

so

sM

éto

do

sd

eSe

leçã

od

eA

trib

uto

s(C

onsi

sten

cy-b

ased

Subs

etE

valu

atio

nco

mB

estF

irst

Sear

ch,C

orre

lati

on-b

ased

Feat

ure

Sele

ctio

n-

CF

Sco

mG

enet

icSe

arch

,Ch

iSqu

are

Feat

ure

Eva

luat

ion

eR

elie

f-F

).

4.4. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 102

Tabela 4.3: Atributos selecionados por cada Método de Seleção de Atributos

Consistency - Consistency-based Subset Evaluation com Best First Search

CFS - Correlation-based Feature Selection com Genetic Search

Chi Square - Chi Square Feature Evaluation

B - mbBagging C - mbCombination BC - mbBaggingCombination

Consistency CFS Chi Square Relief - F

MEDIDA B C BC B C BC B C BC B C BCAtributos binários X XAtributos categóricos XAtributos numéricos X X X X XD1 X X X X X X XD2 X X X XD3_K3 X X X X X X XD3_K5 X X X X X X X XDesbalanceamento X X X X X XDiâmetro do grupo X X X X X X XDistância gruposNE X X X X X X X X XDistância intergrupos X X X X X X X X X X XDistância intragrupos X X X X X X X X X XEntropia X X X X X X X X X X XF1 X X XF2 X X X XLscAvgNorm X X X X X X XN1N2 X X X X X X XN3 X X X X X XNível de ruído X X X X XNúmero de atributos X X XNúmero de classes X X XNúmero de instâncias X X X X X XNúmero de regiões X X X X X X XPontos isolados X X X X XProporção de atribu-tos binários

X

Proporção de atribu-tos categóricos

X X

Proporção de atribu-tos numéricos

X X

T1 X X X X X XT2 X X X X

4.4. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 103

4.4.2 Avaliação dos métodos de seleção de atributos

Foram analisados quatro métodos de seleção de atributos, conforme estudo da

seção anterior: Consistency-based Subset Evaluation (LIU; SETIONO, 1996) com Best

First ; Correlation-based Feature Selection - CFS (HALL, 1998) com Genetic Search; Chi

Square Feature Evaluation (FRANK et al., 2005) com 10 atributos para mbBagging e

mbCombination e 6 atributos para mbBaggingCombination; e Relief - F (KIRA; REN-

DELL, 1992) com 6, 16 e 10 atributos para as meta-bases mbBagging, mbCombination

e mbBaggingCombination, respectivamente. As Figuras 4.12, 4.13 e 4.14 mostram as

taxas de acerto de diferentes classificadores para as meta-bases mbBagging, mbCombi-

nation e mbBaggingCombination, respectivamente, quando submetidas aos métodos

de seleção de atributos estudados. Nessas figuras, verifica-se que todos os métodos de

seleção de atributos levam os classificadores a desempenhos muito próximos, mesmo

alterando as meta-bases. A realização do teste estatístico de Friedman comprova

que não há diferenças estatísticas entre eles (p-value = 0,9893). Assim, realizamos a

análise dos resultados do Meta-CISM, com todos os MSAs aplicados separadamente

nas meta-bases para comparar com os resultados do método proposto utilizando as

meta-bases sem a aplicação de métodos de seleção de atributos.

Figura 4.12: Taxas de acerto alcançadas com o uso de métodos de seleção deatributos sobre a meta-base mbBagging . Resultado dos classificadores sobrea meta-base mbBagging quando submetida aos quatro métodos de seleção de

atributos (Consistency-based Subset Evaluation, Correlation-based FeatureSelection - CFS, Chi Square Feature Evaluation e Relief - F ).

4.4. MÉTODOS DE SELEÇÃO DE ATRIBUTOS 104

Figura 4.13: Taxas de acerto alcançadas com o uso de métodos de seleção deatributos sobre a meta-base mbCombination. Resultado dos classificadores

sobre a meta-base mbCombination quando submetida aos quatro métodos deseleção de atributos (Consistency-based Subset Evaluation, Correlation-based

Feature Selection - CFS, Chi Square Feature Evaluation e Relief - F ).

Figura 4.14: Taxas de acerto alcançadas com o uso de métodos de seleção deatributos sobre a meta-base mbBaggingCombination. Resultado dos

classificadores sobre a meta-base mbBaggingCombination) quando submetidaaos quatro métodos de seleção de atributos (Consistency-based Subset

Evaluation, Correlation-based Feature Selection - CFS, Chi Square FeatureEvaluation e Relief - F ).

4.5. AVALIAÇÃO DO META-CISM SEM SELEÇÃO DE ATRIBUTOS 105

4.5 Avaliação do Meta-CISM sem seleção de atributos

O meta-classificador sugere o “melhor” MSI em termos de classificação para cada

meta-instância correspondente a uma base de dados. Assim, para avaliar os resultados

desse meta-classificador, cada base Γi , j foi reduzida pelo MSI indicado e se tornou

uma base Γ(i , j )R . Em seguida, cada Γ(i , j )R foi submetida aos mesmos classificadores do

Módulo de Anotação (C4.5, KNN, MLP-BP, Part e SMO, utilizando validação cruzada

k-fold, com k = 10), obtendo a taxa de acerto para cada classificador. O desempenho

do método Meta-CISM foi calculado pela média das taxas de acerto de cada clas-

sificador aplicado a todas as bases Γ(i , j )R , separadas de acordo com sua meta-base

correspondente.

Com o intuito de comparar os resultados de Meta-CISM com os resultados indi-

viduais dos MSIs, as bases de dados Γi , j foram reduzidas com cada MSI e seguiram

os demais procedimentos de classificação e médias de taxa de acerto descritos no

parágrafo anterior. Nesse caso, os resultados são as médias das taxas de acerto de cada

classificador para cada MSI aplicado às bases, separadas por meta-base correspon-

dente.

As Tabelas 4.4, 4.5 e 4.6 e as Figuras 4.15, 4.16 e 4.17 mostram, para cada meta-base,

o desempenho de Meta-CISM comparado com o desempenho alcançado pelos demais

MSIs, separados por classificador. Os valores em destaque nas tabelas, correspondem

às maiores taxas de acerto para cada classificador. Percebemos que em todas as

situações o método proposto está no topo, sozinho ou com outros métodos.

Tabela 4.4: Médias de precisão para cada MSI avaliados por cincoclassificadores (meta-base mbBagging ).

KNN C4.5 SMO PART MLP

C-pruner 73,73% (0,16) 71,31% (0,17) 66,46% (0,18) 58,02% (0,17) 58,12% (0,17)

DROP3 77,64% (0,12) 71,52% (0,11) 62,45% (0,20) 57,51% (0,17) 55,39% (0,18)

ENN-CNN 79,91% (0,11) 73,18% (0,12) 63,62% (0,20) 60,25% (0,18) 57,53% (0,18)

IB3 78,55% (0,14) 69,29% (0,18) 64,46% (0,21) 59,99% (0,19) 54,13% (0,19

ICF 71,58% (0,17) 71,72% (0,11) 69,06% (0,18) 60,24% (0,17) 57,49% (0,18)

Meta-CISM 79,92% (0,11) 76,82% (0,11) 69,62% (0,18) 62,52% (0,18) 60,05% (0,19)

Tabela 4.5: Médias de precisão para cada MSI avaliados por cincoclassificadores (meta-base mbCombination).

KNN C4.5 SMO PART MLP

C-pruner 59,44% (0,16) 59,12% (0,17) 51,36% (0,21) 52,82% (0,20) 49,11% (0,18)

DROP3 64,80% (0,1)4 64,36% (0,09) 50,03% (0,21) 50,86% (0,19) 47,91% (0,18)

ENN-CNN 64,18% (0,12) 65,01% (0,11) 51,70% (0,20) 52,69% (0,20) 49,51% (0,19)

IB3 65,92% (0,09) 62,78% (0,14) 51,86% (0,21) 52,00% (0,21) 47,58% (0,18)

ICF 65,10% (0,14) 68,17% (0,09) 53,23% (0,20) 53,61% (0,20) 49,88% (0,18)

Meta-CISM 67,57% (0,13) 67,98% (0,10) 53,60% (0,20) 54,03% (0,20) 50,60% (0,18)

4.5. AVALIAÇÃO DO META-CISM SEM SELEÇÃO DE ATRIBUTOS 106

Tabela 4.6: Médias de precisão para cada MSI avaliados por cincoclassificadores (meta-base mbBaggingCombination).

KNN C4.5 SMO PART MLP

C-pruner 66,58% (0,18) 65,22% (0,62) 58,91% (0,46) 55,42% (0,54) 53,62% (0,64)DROP3 71,22% (0,52) 67,94% (0,55) 56,24% (0,46) 54,19% (0,44) 51,65% (0,58)

ENN-CNN 72,05% (0,50) 69,09% (0,57) 57,66% (0,46) 56,47% (0,50) 53,52% (0,59)IB3 72,23% (0,59) 66,03% (0,48) 58,16% (0,46) 56,00% (0,47) 50,85% (0,56)ICF 68,34% (0,56) 69,94% (0,56) 61,15% (0,46) 56,92% (0,50) 53,68% (0,64)

Meta-CISM 73,99% (0,63) 72,40% (0,62) 61,08% (0,46) 56,42% (0,54) 55,17% (0,64)

Figura 4.15: Desempenho de Meta-CISM sem seleção de atributos para ameta-base mbBagging. O gráfico apresenta as médias dos resultados de

precisão dos MSIs estudados e de Meta-CISM para as bases de dados geradaspor Bagging, separadas por classificador.

4.5. AVALIAÇÃO DO META-CISM SEM SELEÇÃO DE ATRIBUTOS 107

Figura 4.16: Desempenho de Meta-CISM sem seleção de atributos para ameta-base mbCombination. O gráfico apresenta as médias dos resultados deprecisão dos MSIs estudados e de Meta-CISM para as bases de dados geradas

por Combination, separadas por classificador.

Figura 4.17: Desempenho de Meta-CISM sem seleção de atributos para ameta-base mbBaggingCombination. O gráfico apresenta as médias dos

resultados de precisão dos MSIs estudados e de Meta-CISM para para as basesde dados geradas por Bagging e Combination juntas, separadas por

classificador.

4.5. AVALIAÇÃO DO META-CISM SEM SELEÇÃO DE ATRIBUTOS 108

Escolhemos o teste estatístico não-paramétrico de Friedman para analisar se exis-

tem diferenças estatísticas entre o Meta-CISM e os demais MSIs. Com o uso dos valores

das Tabelas 4.4, 4.5 e 4.6, obtivemos os resultados do teste para as meta-bases mb-

Bagging, mbCombination e bmBaggingCombination, respecitvamente. A Tabela 4.7

exibe a média de ranks de cada método, o p-value e a estatística de teste para cada

meta-base.

Em H0 (hipótese nula) verificamos se as médias de classificação de Meta-CISM e

dos MSIs são iguais para os resultados dos classificadores. Em H1 (hipótese alternativa)

verificamos se essas médias são estatisticamente diferentes. Friedman é calculado

de acordo com a distribuição Qui-quadrado. Temos para os seis métodos, 5 graus de

liberdade. De acordo com a tabela Qui-quadrado de valores críticos, para um nível de

significância α= 5%, a estatística de teste não deve ultrapassar 9,236. Já para α= 10% o

valor crítico é 11,071. O p-value indica o quanto os dados estão compatíveis com o

que diz a hipótese nula e deve ser maior que o nível de significância esperado para

não rejeitar H0. Em nossos experimentos, constatamos a um nível de significância

α= 5% que H0 deve ser rejeitada, visto que na Tabela 4.7 as estatísticas de teste e os

p-values obtidos para os MSIs nas aplicações das bases mbBagging, mbCombination

e mbBaggingCombination foram maiores que os limites citados acima. Diante desses

resultados, temos fortes evidências para afirmar que Meta-CISM e os MSIs possuem

diferenças estatísticas.

Tabela 4.7: Teste de Friedman para os resultados do Meta-CISM e demais MSIsestudados, aplicados às meta-bases mbBagging, mbCombination e

mbBaggingCombination

Friedman de acordo com a distribuição Chi-Quadrado, com 5 graus de liberdade

e valores críticos: 9,236 para α= 5% e 11,070 para α= 10% .

H0 As médias de classificação dos métodos são iguais.

H1 As médias de classificação dos métodos são diferentes.

Rejeitar a hipótese nula quando P-VALUE<α (nível de significância).

mbBagging mbCombination mbBaggingCombination

CPRUNER

RA

NK

S

4 4,8 4,6

DROP3 5 5 5

ENNCNN 2,8 3,8 3,4

IB3 4,6 4,2 4,2

ICF 3,6 2 2,2

META-CISM 1 1,2 1,6

Estatística de Teste 14,942857 17,228571 13,228571

P-VALUE 0,010609 0,004086 0,021328

A fim de verificar se o método proposto é responsável por diferenças significantes

em relação a cada um dos MSIs estudados, foram executados os testes: Wilcoxon

signed-ranks test com 90% e 95% de nível de confiança e o teste de múltiplas compa-

4.5. AVALIAÇÃO DO META-CISM SEM SELEÇÃO DE ATRIBUTOS 109

rações Holm–Bonferroni com 95% de confiança. Os resultados do teste de Wilcoxon

são apresentados na Tabela 4.8. Essa tabela possui os valores da soma dos rankings

positivos, equivalentes ao método proposto, uma vez que é uma comparação do

Meta - CISM com cada um dos MSIs; a soma dos rankings negativos, correspondentes

à soma dos rankings do método em comparação; e os p-values para cada meta-base.

O teste de Wilcoxon indica que o método proposto é superior à maioria dos méto-

dos estudados com 90% de confiança. O Meta-CISM se mostra melhor que todos os

MSIs para a meta-base mbBagging. Para a meta-base mbBaggingCombination, apenas

sobre ICF não alcança o melhor resultado. Já com a meta-base mbCombination, não

alcança diferenças estatísticas sobre ENNCNN e ICF. Com 95% de confiança, não

mostrou diferenças significativas sobre quaisquer MSIs.

Fazendo comparações com os p-values gerados com o teste de Holm-Bonferroni,

presentes na 4.9, vimos que: para as meta-bases mbBagging e mbCombination, o

Meta-CISM consegue, com nível de significância de 5%, melhores resultados que

C-pruner, DROP3, IB3 e ICF, enquanto é estatisticamente igual a ENN-CNN; para a

meta-base mbBaggingCombination, com a mesma significância, Meta-CISM é su-

perior a C-pruner, DROP3 e IB3 e possui igualdade estatística em relação a ICF e

ENN-CNN.

Tabela 4.8: Teste de Wilcoxon comparando Meta-CISM × MSIs

R+ soma dos rankings de Meta-CISM.

R- soma dos rankings do método em comparação.

H0 As médias de classificação dos métodos são iguais.

H1 A média de classificação do Meta-CISM é maior que a média do método em comparação.

Rejeitar a hipótese nula quando P-VALUE<α (nível de significância).

α= 5% e α= 10%

META-CISM × mbBagging mbCombination mbBaggingCombination

CPRUNER

R+ 15 15 15

R- 0 0 0

P-VALUE 0,0625 0,0625 0,0625

DROP3

R+ 15 15 15

R- 0 0 0

P-VALUE 0,0625 0,0625 0,0625

ENNCNN

R+ 15 15 14

R- 0 0 1

P-VALUE 0,0625 0,0625 0,125

IB3

R+ 15 15 15

R- 0 0 0

P-VALUE 0,0625 0,0625 0,0625

ICF

R+ 15 14 12

R- 0 1 3

P-VALUE 0,0625 0,125 ≥ 2

4.5. AVALIAÇÃO DO META-CISM SEM SELEÇÃO DE ATRIBUTOS 110

Tabela 4.9: Teste de Holm-Bonferroni comparando Meta-CISM × MSIs

H0 As médias de classificação dos métodos são iguais.H1 A média de classificação do Meta-CISM é maior que a média do método em comparação.

Rejeitar a hipótese nula quando P-VALUE<α (nível de significância).α= 5% e α= 10%

META-CISM P-VALUES

× mbBagging mbCombination mbBaggingCombination

CPRUNER 0,01123 0,002346 0,01123DROP3 0,000723 0,00132 0,004059

ENNCNN 0,12819 0,027992 0,12819IB3 0,002346 0,01123 0,027992

ICF 0,027992 0,498962 0,61209

Outra análise possível é a verificação das escolhas de Meta-CISM, atestando com

que frequência o meta-classificador escolhe o 1º, 2º, 3º, 4º ou o 5º melhor MSI para

cada base de dados (Figuras 4.18, 4.19 e 4.20). Esse diagnóstico é possível a partir do

cálculo da média das precisões dos classificadores para cada base aplicada aos MSIs,

atribuindo uma posição (1º, 2º, 3º, 4º ou 5º) para cada MSI.

O metódo escolhe um dos três melhores MSIs para mais de 85% das bases de

todos os casos. Com a meta-base mbBagging, o Meta-CISM mostrou alta precisão nos

resultados, uma vez que 98,13% das bases tiveram indicação do MSI mais adequado a

ser aplicado. Em mbCombination, 86,5% dos casos têm um dos três melhores MSIs

indicados. E em mbBaggingCombination um dos três melhores MSIs é sugerido para

88,44% das bases.

0

10

20

30

40

50

60

70

80

90

100

1º 2º 3º 4º 5º 6º

Fre

qu

ên

cia

(%)

Ranking de escolhas

Figura 4.18: Taxas de ranking de Meta-CISM sem seleção de atributos para ameta-base mbBagging. Os MSIs foram ordenados em ranking pela média das

precisões dos classificadores para cada base, a fim de mostrar com quefrequência o Meta-CISM escolhe os melhores MSIs. O gráfico apresenta o

ranking das bases correspondentes à meta-base mbBagging.

4.5. AVALIAÇÃO DO META-CISM SEM SELEÇÃO DE ATRIBUTOS 111

0

10

20

30

40

50

60

1º 2º 3º 4º 5º 6º

Fre

qu

ên

cia

(%)

Ranking de escolhas

Figura 4.19: Taxas de ranking de Meta-CISM sem seleção de atributos para ameta-base mbCombination. Os MSIs foram ordenados em ranking pela média

das precisões dos classificadores para cada base, a fim de mostrar com quefrequência o Meta-CISM escolhe os melhores MSIs. O gráfico apresenta o

ranking das bases correspondentes à meta-base mbCombination.

0

10

20

30

40

50

60

1º 2º 3º 4º 5º 6º

Fre

qu

ên

cia

(%)

Ranking de escolhas

Figura 4.20: Taxas de ranking do Meta-CISM sem seleção de atributos para ameta-base mbBaggingCombination. Os MSIs foram ordenados em rankingpela média das precisões dos classificadores para cada base, a fim de mostrar

com que frequência o Meta-CISM escolhe os melhores MSIs. O gráficoapresenta o ranking das bases correspondentes à meta-base

mbBaggingCombination.

O método Meta-CISM é validado pelo desempenho satisfatório nos resultados

apresentados, considerando as boas escolhas e o alcance de taxas de acerto iguais ou

superiores aos demais métodos estudados.

4.6. AVALIAÇÃO DO META-CISM COM SELEÇÃO DE ATRIBUTOS 112

4.6 Avaliação do Meta-CISM com seleção de atributos

Um avanço do Meta-CISM pode ser atingido com a inclusão do Módulo de Seleção

de Atributos. Se um subconjunto das meta-características atuar com desempenho

semelhante ou até melhor que o conjunto completo dessas meta-características, a

redução do custo computacional e a melhora no processo de meta-aprendizagem

compensará a inclusão desse módulo.

Tendo em vista os resultados já apresentados para o método proposto sem o Mó-

dulo de Seleção de Atributos, as Tabelas 4.10, 4.11 e 4.12 e as Figuras 4.21, 4.22 e

4.23 apontam como esse módulo influencia nos resultados. Tanto as figuras como

as tabelas, mostram uma comparação das taxas de acerto do método Meta-CISM

sem a seleção de atributos e com quatro algoritmos diferentes de seleção de atribu-

tos, a saber: Consistency-based Subset Evaluation (LIU; SETIONO, 1996) com Best

First ; Correlation-based Feature Selection - CFS (HALL, 1998) com Genetic Search; Chi

Square Feature Evaluation (FRANK et al., 2005) com 10 atributos para mbBagging e

mbCombination e 6 atributos para mbBaggingCombination; e Relief - F (KIRA; REN-

DELL, 1992) com 6, 16 e 10 atributos para as bases mbBagging, mbCombination e

mbBaggingCombination, respectivamente.

Tabela 4.10: Comparação das médias de precisão do Meta-CISM com e sem omódulo de seleção de atributos (meta-base mbBagging ).

KNN C4.5 SMO PART MLP

Sem seleção de atributos 79,92% (0,11) 76,82% (0,11) 69,62% (0,18) 62,52% (0,18) 60,05% (0,19)

CFS 79,17% (0,11) 76,92% (0,11) 69,41% (0,18) 59,69% (0,18) 59,50% (0,19)

Chi Squared 79,55% (0,11) 76,82% (0,11) 68,90% (0,19) 60,55% (0,18) 58,91% (0,19)

Consistency 79,41% (0,11) 76,65% (0,11) 68,94% (0,19) 60,89% (0,18) 59,11% (0,19)

Relief - F 79,43% (0,12) 77,15% (0,11) 68,60% (0,19) 60,76% (0,18) 58,89% (0,19)

Tabela 4.11: Comparação das médias de precisão do Meta-CISM com e sem omódulo de seleção de atributos (meta-base mbCombination).

KNN C4.5 SMO PART MLP

Sem seleção de atributos 67,57% (0,13) 67,98% (0,10) 53,60% (0,20) 54,03% (0,20) 50,60% (0,18)

CFS 67,91% (0,13) 68,74% (0,09) 53,86% (0,20) 54,26% (0,20) 49,84% (0,18)

Chi Squared 67,72% (0,13) 68,59% (0,11) 53,51% (0,21) 53,73% (0,20) 49,93% (0,19)

Consistency 68,60% (0,12) 68,32% (0,10) 53,30% (0,21) 53,77% (0,20) 50,15% (0,18)

Relief - F 68,28% (0,18) 68,67% (0,18) 53,61% (0,18) 53,95% (0,18) 50,11% (0,18)

4.6. AVALIAÇÃO DO META-CISM COM SELEÇÃO DE ATRIBUTOS 113

Tabela 4.12: Comparação das médias de precisão do Meta-CISM com e sem omódulo de seleção de atributos (meta-base mbBaggingCombination).

KNN C4.5 SMO PART MLP

Sem seleção de atributos 73,99% (0,13) 72,40% (0,11) 61,08% (0,21) 56,42% (0,19) 55,17% (0,19)CFS 73,87% (0,13) 72,72% (0,11) 60,77% (0,21) 56,86% (0,19) 54,13% (0,19)

Chi Squared 73,37% (0,14) 72,81% (0,11) 60,73% (0,21) 57,24% (0,19) 54,77% (0,19)Consistency 74,01% (0,13) 72,66% (0,11) 60,88% (0,21) 56,78% (0,19) 54,61% (0,20)

Relief - F 74,20% (0,13) 73,08% (0,11) 60,48% (0,21) 56,60% (0,19) 54,36% (0,19)

Figura 4.21: Desempenho do Meta-CISM com seleção de atributos para ameta-base mbBagging. O gráfico apresenta a média dos resultados de precisão

do Meta-CISM com e sem o módulo de seleção de atributos, separadas porclassificador, para as bases de dados geradas por Bagging.

4.6. AVALIAÇÃO DO META-CISM COM SELEÇÃO DE ATRIBUTOS 114

Figura 4.22: Desempenho do Meta-CISM com seleção de atributos para ameta-base mbCombination. O gráfico apresenta a média dos resultados de

precisão do Meta-CISM com e sem o módulo de seleção de atributos, separadaspor classificador, para as bases de dados geradas por Combination.

Figura 4.23: Desempenho do Meta-CISM com seleção de atributos para ameta-base mbBaggingCombination. O gráfico apresenta a média dos

resultados de precisão do Meta-CISM com e sem o módulo de seleção deatributos, separadas por classificador, para as bases de dados geradas por

mbBaggingCombination.

Visualmente e estatisticamente, não são encontradas diferenças significativas nas

taxas de acerto para as meta-bases estudadas. Com os valores das Tabelas 4.10, 4.11

e 4.12, realizamos o teste estatístico não-paramétrico de Friedman para analisar se

existem diferenças estatísticas nos resultados antes e após a aplicação de diferentes

4.6. AVALIAÇÃO DO META-CISM COM SELEÇÃO DE ATRIBUTOS 115

MSAs. Para a hipótese nula (H0) definimos que há igualdade nas médias de classifi-

cação do Meta-CISM com e sem a aplicação dos métodos de seleção de atributos. E

para a hipótese alternativa (H1) investigamos se essas médias são estatisticamente

diferentes.

A Tabela 4.13 contém os resultados do Teste de Friedam realizado e, nesse caso,

para a análise de 5 configurações, temos 4 graus de liberdade com os seguintes valores

críticos: 7,779 para α= 5% e 9,488 para α= 10%. Com níveis de significância α= 5% e

α= 10%, aceitamos H0, em razão dos p-values obtidos para as avaliações do uso de

MSAs aplicados às meta-bases de mbBagging, mbCombination e mbBaggingCombina-

tion, serem maiores que α. Os valores das estatísticas de teste menores que os valores

críticos, mostrados nessa tabela, ratificam que os dados condizem com a afirmação da

hipótese nula, ou seja, os resultados do teste de Friedman informam que os métodos

possuem resultados estatisticamente iguais.

Tabela 4.13: Teste de Friedman para os resultados do Meta-CISM com aaplicação de Métodos de Seleção de Atributos nas meta-bases mbBagging,

mbCombination e mbBaggingCombination.

Friedman de acordo com a distribuição Chi-Quadrado, com 4 graus de liberdade

e valores críticos: 7,779 para α= 5% e 9,488 para α= 10% .

H0 As médias de classificação dos métodos são iguais.

H1 As médias de classificação dos métodos são diferentes.

Rejeitar a hipótese nula quando P-VALUE<α (nível de significância).

mbBagging mbCombination mbBaggingCombination

Sem SA

RA

NK

S

1,6 3 3,2

CFS 3,2 3,4 2,2

Chi Squared 3,4 2,8 4

Consistency 3,4 2,8 3,2

Relief 3,4 3 2,4

Estatística de Teste 4,96 0,48 4,16

P-VALUE 0,291426 0,975419. 0,384785

Embora as taxas de acerto não tenham melhorado com o uso do Módulo de Seleção

de Atributos, o Meta-CISM manteve sua precisão. A Tabela 4.14 mostra a soma dos

tempos para calcular cada medida de caracterização de dados e a redução provocada

pelo uso de métodos de seleção de atributos em quatro das dezesseis bases de dados

estudadas. A redução do número de meta-características, por exemplo, de trinta para

seis em mbBagging aplicado a Correlation-based Feature Selection com Genetic Search

- CFS e a Relief - F, provoca uma queda considerável no custo computacional. E dado o

alcance de até 80% de redução no tempo para o cálculo, podemos validar o uso desse

módulo como contribuição ao Meta-CISM.

4.6.AV

ALIA

ÇÃ

OD

OM

ETA

-CISM

CO

MSE

LEÇ

ÃO

DE

ATR

IBU

TO

S116

Tabela 4.14: Redução do tempo para o cálculo das meta-características com ouso do Módulo de Seleção de Atributos

B - mbBagging C - mbCombination BC - mbBaggingCombination

BANANA VERTEBRAL COLUMN 2C PARKINSONS SONAR

TEMPO TOTAL (s) 91,8984 (6,1780) 2035,1122 (40,4292) 2154,8370 (45,3762) 6919,0297 (98,8893)

TEMPO REDUZIDO (s) % TEMPO REDUZIDO (s) % TEMPO REDUZIDO (s) % TEMPO REDUZIDO (s) %

Consistency-basedSubset Evaluation com

Best First Search

B 85,7180 (5,7665) 7% 1898,8272 (37,7354) 7% 2010,0810 (42,3315) 7% 6454,3057 (92,2977) 7%C 85,8114 (5,7668) 7% 1899,7507 (37,7361) 7% 2011,6261 (42,3546) 7% 6458,8425 (92,3021) 7%

BC 85,8113 (5,7668) 7% 1899,7504 (37,7362) 7% 2011,6251 (42,3546) 7% 6458,8404 (92,30221) 7%

Correlation-basedFeature Selection comGenetic Search - CFS

B 30,6116 (2,0610) 67% 677,9219 (13,4774) 67% 716,9750 (15,1165) 67% 2302,2557 (32,9493) 67%C 49,2094 (3,2982) 46% 1087,2170 (21,5722) 47% 1151,5968 (24,2137) 47% 3697,1323 (52,7750) 47%

BC 61,3181 (4,1200) 33% 1356,9938 (26,9572) 33% 1436,8534 (30,2396) 33% 4613,0981 (65,9432) 33%

Chi Square FeatureEvaluation

B 30,8416 (2,0631) 60% 680,0594 (13,4892) 60% 720,1017 (15,1232) 60% 2311,4542 (33,0057) 60%C 36,8169 (2,4752) 66% 814,0149 (16,1790) 67% 860,7637 (18,1403) 67% 2763,4056 (39,5447) 67%

BC 24,5986 (1,6515) 73% 543,0176 (10,7895) 73% 573,9693 (12,0948) 73% 1842,3299 (26,3657) 73%

Relief - FB 18,5162 (1,2357) 80% 408,1523 (8,0914) 80% 433,1214 (9,0817) 80% 1389,7978 (19,8214) 80%C 55,0111 (3,7080) 40% 1219,7754 (24,2571) 40% 1290,3608 (27,2075) 40% 4143,9302 (59,3062) 40%

BC 42,8026 (2,8829) 53% 948,5754 (18,8636) 53% 1003,5829 (21,1669) 53% 3222,2262 (46,1219) 53%

4.7. CONSIDERAÇÕES FINAIS 117

4.7 Considerações Finais

Os extensos experimentos apresentados nas seções anteriores, propiciam obser-

vações adicionais dos resultados, além das análises realizadas para a verificação dos

objetivos pretendidos neste trabalho.

Iniciando com os processos de reamostragem, a meta-base mbBagging demonstra

ter a melhor estrutura. Pois nos experimentos, desde aqueles executados para a confi-

guração de parâmetros do KNN, MLP-BP e Métodos de Seleção de Atributos (MSAs)

até os resultados do método proposto, as maiores taxas de acerto são obtidas por

essa meta-base. Além disso, todos os MSAs escolheram as menores quantidades de

meta-características para ela. A meta-base mbCombination ficou com a pior posição,

dado que os MSAs lhe atribuem as maiores quantidades de meta-características e

essa meta-base está, na maioria das vezes, relacionada às menores precisões. Já a

meta-base mbBaggingCombination apresentou as menores variações de respostas

para os diferentes experimentos realizados.

Os resultados que se referem às meta-bases, indicam que o processo de reamostra-

gem Combination, neste estudo, não apresentou os melhores resultados possíveis. É

provável que um dos motivos dessas respostas esteja no processo de atribuição dos

atributos às novas bases de dados, visto que o método Combination inicia criando

bases de apenas um atributo. Assim, pode não gerar bases com boa representatividade

do problema, principalmente, quando a base de origem possue uma grande dimensão

de atributos. A ordem de geração das bases do método deve ser reavaliada.

Nos estudos sobre parâmetros para o KNN, podemos destacar o comportamento

das precisões das meta-bases com a variação dos k-vizinhos mais próximos. Notamos

que um número k muito pequeno, não gera as melhores respostas, a classificação é

afetada pela proximidade entre as classes. No entanto, o acréscimo de k só melhora as

taxas de acerto até um certo nível (k = 5, o valor escolhido). A frente desse, as taxas

começam a cair, o raio de vizinhos acaba atingindo as fronteiras das classes.

Já nos parâmetros da MLP-BP, vimos que poucos neurônios são suficientes para

uma boa generalização da rede. As melhores respostas foram obtidas com as menores

quantidades de neurônios (nesse caso, cl = 5 neurônios e ac_av g = 17 neurônios).

Observamos ainda, que o decaimento da taxa de aprendizagem não contribuiu para

os melhores resultados.

A rede neural MLP-BP foi a melhor opção como meta-classificador. Todavia, forne-

ceu as piores precisões entre os classificadores utilizados nas bases de dados submeti-

das às aplicações dos MSIs para a avaliação do Meta-CISM. Nessas avaliações o KNN

foi o melhor classificador.

Os métodos de seleção de atributos não ofereceram aumento das precisões quando

aplicados nas meta-bases: mbBagging, mbCombination e mbBaggingCombination.

4.7. CONSIDERAÇÕES FINAIS 118

Entretanto, conseguiram reduzi-las consideravelmente. Todas essas meta-bases foram

construídas com trinta meta-características. As maiores reduções foram produzidas

pelos métodos Relief-F e CFS com Genetic Search. Pois, diminuiram a meta-base

mbBagging para seis meta-características e o tempo de processamento em 80% e

67% do tempo total, respectivamente. O MSA que fez as maiores reduções globais

foi o Chi Square Feature Evaluation, considerando reduções das três meta-bases. Já

Consistency-based Subset Evaluation foi o MSA que reteve mais meta-características

nas meta-bases.

Uma investigação geral sobre as meta-características escolhidas pelos MSAs estu-

dados, revela, conforme a Figura 4.11, que com um range de 0 a 12 chances, Entropia e

Distância Intergrupos foram as meta-características mais selecionadas para continuar

na meta-base. Em seguida, estão entre as mais escolhidas, as meta-características: Dis-

tância Intragrupos e Distância GruposNE. Isso sugere que essas meta-características

são relevantes para o uso na escolha de MSIs com meta-aprendizagem. Quinze meta-

características foram escolhidas com uma frequência maior que 50% das chances,

ou seja, seis vezes ou mais. E outras quinze meta-características foram selecionadas

menos de seis vezes. A meta-característica que demonstrou ter menor influência

nas meta-bases foi N 1, já que não foi escolhida por nenhum MSA e possuia a menor

divergência entre seus valores nas meta-bases. Também foram pouco influentes,

meta-características que informam estruturas simples das bases, como: Atributos

binários, Proporção de atributos binários, Atributos nominais, Proporção de atributos

nominais e Proporção de atributos numéricos.

Quanto aos objetivos principais desta dissertação, constatamos que foram atendi-

dos, uma vez que o método proposto (Meta-CISM) obteve respostas bastante satis-

fatórias em relação aos demais MSIs. A precisão atingida pela arquitetura proposta

esteve entre as melhores taxas de acerto em todos os resultados mostrados. O uso

de meta-aprendizagem permitiu ao Meta-CISM escolher os “melhores” MSIs em

85% dos casos (referente à precisão) para serem aplicados nas bases de dados (Figu-

ras 4.18, 4.18 e 4.20). Os processos de reamostragem possibilitaram o treinamento

de uma MLP com apenas dezesseis bases adquiridas de repositórios (Tabela 4.1). O

Módulo de Seleção de Atributos contribuiu para a redução do custo computacional

(Seção 4.6). Em suma, os estudos realizados contribuem para pesquisas sobre o uso

de meta-aprendizagem para a escolha de métodos de seleção de instâncias.

119119119

5Conclusões

Esta dissertação propôs a arquitetura Meta-CISM (Meta-learing for Choosing Ins-

tance Selection Method) para selecionar o “melhor” Método de Seleção de Instâncias

(MSI) dada uma base de dados, baseada em meta-aprendizagem.

Dezesseis bases de dados foram reamostradas e utilizadas na construção da meta-

base. Trinta medidas de caracterização de dados foram extraídas dessas bases rea-

mostradas e usadas como descritores. Após a aplicação dos MSIs em cada base de

dados, a maior precisão da média de cinco classificadores foi usada para determi-

nar o “melhor” MSI para ser rótulo de uma meta-instância. Os descritores e rótulos

compõem as meta-instâncias integrantes da meta-base que foi usada para treinar um

meta-classificador responsável por selecionar o “melhor” MSI para novas bases. A

inclusão do Módulo de Seleção de Atributos também foi estudada para verificar os

benefícios trazidos ao Meta-CISM.

Este capítulo apresenta as principais contribuições desta dissertação na Seção 5.1.

A Seção 5.2 indica como aprofundar a pesquisa e aperfeiçoar o método proposto.

5.1 Contribuições

A principal contribuição deste trabalho é a proposta do Meta-CISM (Meta-learing

for Choosing Instance Selection Method). Um método que seleciona automaticamente

o “melhor” MSI para uma base de dados, e além disso, preocupa-se em:

• se adequar à realidade da baixa disponibilidade de bases de dados para a geração

das meta-instâncias da meta-base de treino, ao incluir o Módulo de Reamostra-

gem;

• ser imparcial ao tipo de classificador utilizado para rotulação das meta-instâncias,

utilizando a média de vários tipos de algoritmos de classificação;

• propiciar o uso de vários classificadores e métodos de seleção de atributos;

5.1. CONTRIBUIÇÕES 120

• e melhorar o custo computacional do processo, através do Módulo de Seleção

de Atributos.

Outra importante contribuição é a formulação do método de reamostragem Combi-

nation. Esse método permite criar novas bases de dados com a garantia da diversidade

entre elas, porque sempre varia ou na quantidade de atributos ou em quais atributos

serão escolhidos para as novas bases. Apesar dessa importante aptidão, Combination

precisa de ajustes, visto que a meta-base mbCombination, gerada por esse processo

de reamostragem, obteve os resultados menos satisfatórios.

Os experimentos realizados contribuem para ratificar a eficiência do uso de meta-

aprendizagem com Métodos de Seleção de Instâncias. Os resultados obtidos mostram

que, na maioria das vezes, o Meta-CISM estatisticamente se sobrepõe a todos os MSIs

estudados (C-pruner, DROP3, IB3, ICF e ENN-CNN). Logo, a abordagem é adequada

para ser usada automaticamente na fase de pré-processamento das bases de dados,

visto que eficientemente seleciona um dos três melhores MSIs em mais de 85% dos

casos.

O uso do Módulo de Seleção de Atributos se mostra relevante, devido à redução

do custo computacional e à permanência dos valores de taxas de acerto. Qualquer

um dos métodos de seleção de atributos estudados poderia ser escolhido para a

aplicação nesse módulo, pois, atingiram resultados estatisticamente iguais e não

resultaram na melhora das taxas de acerto. Todavia, os métodos Correlation-based

Feature Selection com Genetic Search - CFS e Relief - F foram os que mais reduziram

as meta-características e assim, os que mais diminuiram a complexidade das meta-

bases (reduzindo a dimensão) e o tempo de processamento. A pesquisa indica que a

melhor configuração para o uso de cada um deles é: Best First Search para Consistency-

based Subset Evaluation; no caso de Correlation-based Feature Selection - CFS, Genetic

Search; em Chi Square Feature Evaluation, o ranking de 10 atributos para a meta-base

mbBagging ; também 10 atributos para a meta-base mbCombination e para a meta-

base mbBaggingCombination, 6 atributos no ranking ; para o Relief - F, 6 atributos

no ranking para a meta-base mbBagging, a meta-base mbCombination ficou com o

ranking de 16 atributos; e mbBaggingCombination com 10 atributos no ranking.

Quanto ao meta-classificador, a pesquisa aponta que dentre os quatro classificado-

res analisados (C4.5, KNN, MLP-BP e PART), a rede neural MLP-BP é a melhor opção

para classificação das meta-bases.

A meta-base mbBagging gerada pelo procedimento de reamostragem Bagging,

atingiu os melhores resultados com e sem o Módulo de Seleção de Atributos. Em

seguida, a meta-base mbBaggingCombination foi quem alcançou as melhores taxas,

com 1600 meta-instâncias, das quais 800 derivam do procedimento de Bagging e 800

derivam do procedimento de Combination. Por último, ficou a meta-base mbCombi-

nation gerada apenas pelo processo de Combination. Este resultado pode indicar que

5.2. TRABALHOS FUTUROS 121

os atributos selecionados na reamostragem Combination não foram suficientes ou os

mais representativos do problema.

Parte dos resultados desta pesquisa foi divulgada nos artigos: Chossing Instance

Selection Method using meta-learning (OLIVEIRA MOURA et al., 2014a) e Uma abor-

dagem para a escolha do melhor método de seleção de instâncias usando meta-

aprendizagem (OLIVEIRA MOURA et al., 2014b), publicados nos anais dos eventos

SMC 2014 e ENIAC 2014, respectivamente.

5.2 Trabalhos Futuros

Trabalhos futuros incluem:

• verificar o comportamento do Meta-CISM com outra configuração, alterando

os procedimentos de reamostragem, os métodos de seleção de instâncias, os

classificadores e aumentando o número de meta-características;

• considerar a porcentagem de redução para cada MSI no módulo de Anotação,

seus relacionamentos com a precisão e verificar detalhadamente o custo com-

putacional do método;

• analisar mais profundamente o método Combination e verificar possíveis me-

lhorias.

122122122Referências

AHA, D. W.; KIBLER, D.; ALBERT, M. K. Instance-based learning algorithms. Machinelearning, [S.l.], v.6, n.1, p.37–66, 1991.

ALMEIDA, M. A. F. Introdução ao Estudo das Redes Neurais Artificiais. [S.l.]: UFSC,1995.

BERNADÓ, E.; LLORA, X.; GARRELL, J. M. XCS and GALE: a comparative study of twolearning classifier systems on data mining. In: Advances in learning classifiersystems. [S.l.]: Springer, 2002. p.115–132.

BOSER, B. E.; GUYON, I. M.; VAPNIK, V. N. A training algorithm for optimal marginclassifiers. In: COMPUTATIONAL LEARNING THEORY, 1992. Anais. . . [S.l.: s.n.], 1992.p.144–152.

BRAZDIL, P.; CARRIER, C. G.; SOARES, C.; VILALTA, R. Metalearning: applications todata mining. 1.ed. [S.l.]: Springer Science & Business Media, 2008.

BREIMAN, L. Bagging predictors. Machine learning, [S.l.], v.24, n.2, p.123–140, 1996.

BRIGHTON, H.; MELLISH, C. Advances in instance selection for instance-basedlearning algorithms. Data mining and knowledge discovery, [S.l.], v.6, n.2, p.153–172,2002.

CAISES, Y.; GONZáLEZ, A.; LEYVA, E.; PéREZ, R. Combining instance selectionmethods based on data characterization: an approach to increase their effectiveness.Information Sciences, [S.l.], v.181, n.20, p.4780–4798, 2011.

CAMERON-JONES, R. Instance selection by encoding length heuristic with randommutation hill climbing. In: AUSTRALIAN JOINT CONFERENCE ON ARTIFICIALINTELLIGENCE, 1995. Anais. . . [S.l.: s.n.], 1995. p.99–106.

CHANG, C.-L. Finding prototypes for nearest neighbor classifiers. IEEE Transactionson Computers, [S.l.], v.100, n.11, p.1179–1184, 1974.

COHEN, W. W. Fast effective rule induction. In: INTERNATIONAL CONFERENCE ONMACHINE LEARNING, 1995. Anais. . . [S.l.: s.n.], 1995. p.115–123.

CORTES, C.; VAPNIK, V. Support-vector networks. Machine learning, [S.l.], v.20, n.3,p.273–297, 1995.

COVER, T.; HART, P. Nearest neighbor pattern classification. IEEE Transactions onInformation Theory, [S.l.], v.13, n.1, p.21–27, 1967.

CZARNOWSKI, I.; JEDRZEJOWICZ, P. Instance reduction approach to machinelearning and multi-database mining. Annales UMCS Sectio AI Informatica, [S.l.], v.4,n.1, p.60–71, 2006.

DASARATHY, B. Minimal consistent set (MCS) identification for optimal nearestneighbor decision systems design. IEEE Transactions on Systems, Man andCybernetics, [S.l.], v.24, n.3, p.511–517, 1994.

REFERÊNCIAS 123

DASH, M.; LIU, H. Feature Selection for Classification. Intelligent Data Analysis,[S.l.], v.1, p.131–156, 1997.

DONALD, H. The organization of behavior: a neuropsychological theory. [S.l.]: NewYork: Wiley, 1949.

FRANK, E.; HALL, M.; HOLMES, G.; KIRKBY, R.; PFAHRINGER, B.; WITTEN, I. H.;TRIGG, L. Weka. In: Data Mining and Knowledge Discovery Handbook. [S.l.]:Springer, 2005. p.1305–1314.

FRANK, E.; WITTEN, I. H. Generating Accurate Rule Sets Without GlobalOptimization. [S.l.]: University of Waikato: Department of Computer Science, 1998.144–151p.

GARCÍA-PEDRAJAS, N.; DEL CASTILLO, J. A. R.; ORTIZ-BOYER, D. A cooperativecoevolutionary algorithm for instance selection for instance-based learning. MachineLearning, [S.l.], v.78, n.3, p.381–420, 2010.

GARCÍA, S.; LUENGO, J.; HERRERA, F. Data Preprocessing in Data Mining. [S.l.]:New York: Springer, 2015.

GATES, G. The reduced nearest neighbor rule. IEEE Transactions on InformationTheory, [S.l.], v.18, n.3, p.431–433, 1972.

GIRAUD-CARRIER, C.; FLACH, P.; PENG, Y.; FARRAND, J.; BENSUSAN, H. METAL: ameta-learning assistant for providing user support in machine learning and datamining. 2002.

HALL, M. A. Correlation-based Feature Subset Selection for Machine Learning.1998. Tese (Doutorado em Ciência da Computação) — University of Waikato,Hamilton, New Zealand.

HART, P. The condensed nearest neighbor rule. IEEE Transactions on InformationTheory, [S.l.], v.14, n.3, p.515–516, 1968.

HO, T. K. The random subspace method for constructing decision forests. IEEETransactions on Pattern Analysis and Machine Intelligence, [S.l.], v.20, n.8,p.832–844, 1998.

JANKOWSKI, N.; GROCHOWSKI, M. Comparison of Instances Seletion Algorithms I.Algorithms Survey. In: RUTKOWSKI, L.; SIEKMANN, J.; TADEUSIEWICZ, R.; ZADEH,L. (Ed.). Artificial Intelligence and Soft Computing - ICAISC 2004. [S.l.]: SpringerBerlin Heidelberg, 2004. p.598–603. (Lecture Notes in Computer Science, v.3070).

KIM, S.-W.; OOMMEN, B. J. A brief taxonomy and ranking of creative prototypereduction schemes. Pattern Analysis & Applications, [S.l.], v.6, n.3, p.232–244, 2003.

KIM, S.-W.; OOMMEN, B. J. Enhancing prototype reduction schemes with LVQ3-typealgorithms. Pattern Recognition, [S.l.], v.36, n.5, p.1083–1093, 2003.

KIRA, K.; RENDELL, L. A. A practical approach to feature selection. In:INTERNATIONAL WORKSHOP ON MACHINE LEARNING, 1992. Anais. . . [S.l.: s.n.],1992. p.249–256.

REFERÊNCIAS 124

KOHONEN, T. The self-organizing map. Neurocomputing, [S.l.], v.21, n.1, p.1–6, 1998.

KONONENKO, I. Estimating attributes: analysis and extensions of relief. In:MACHINE LEARNING, 1994. Anais. . . [S.l.: s.n.], 1994. p.171–182.

KUHN, H. W. Nonlinear programming: a historical view. In: Traces and Emergenceof Nonlinear Programming. [S.l.]: Springer, 2014. p.393–414.

LEYVA, E.; CAISES, Y.; GONZÁLEZ, A.; PÉREZ, R. On the use of meta-learning forinstance selection: an architecture and an experimental study. Information Sciences,[S.l.], v.266, p.16–30, 2014.

LEYVA, E.; GONZáLEZ, A.; PéREZ, R. Knowledge-based instance selection: acompromise between efficiency and versatility. Knowledge-Based Systems, [S.l.],v.47, p.65–76, 2013.

LEYVA, E.; GONZALEZ, A.; PEREZ, R. A Set of Complexity Measures Designed forApplying Meta-Learning to Instance Selection. IEEE Transactions on Knowledge andData Engineering, [S.l.], v.27, n.2, p.354–367, Feb 2015.

LICHMAN, M. UCI Machine Learning Repository. 2013.

LIU, H.; SETIONO, R. A probabilistic approach to feature selection - A filter solution.In: INTERNATIONAL CONFERENCE ON MACHINE LEARNING, 13., 1996. Anais. . .[S.l.: s.n.], 1996. p.319–327.

MCCULLOCH, W. S.; PITTS, W. A logical calculus of the ideas immanent in nervousactivity. The bulletin of mathematical biophysics, [S.l.], v.5, n.4, p.115–133, 1943.

MICHALSKI, R. S. Understanding the nature of learning: issues and researchdirections. Machine learning: An artificial intelligence approach, [S.l.], v.2, p.3–25,1986.

MOLINA, L.; BELANCHE, L.; NEBOT, A. Feature selection algorithms: a survey andexperimental evaluation. In: IEEE INTERNATIONAL CONFERENCE ON DATAMINING, 2002. Anais. . . [S.l.: s.n.], 2002. p.306–313.

MOLLINEDA, R. A.; SÁNCHEZ, J. S.; SOTOCA, J. M. Data characterization for effectiveprototype selection. In: Pattern Recognition and Image Analysis. [S.l.]: Springer,2005. p.27–34.

NAKHAEIZADEH, G. Project statlog: comparative testing and evaluation of statisticaland logical learning algorithms for large-scale applications in classification,prediction and control. 1993.

NORVIG, P.; RUSSELL, S. Inteligência Artificial, 3ª Edição. [S.l.]: Elsevier Brasil, 2014.v.1.

OLIVEIRA MOURA, S. de; FREITAS, M. Bassani de; CARDOSO, H.; CAVALCANTI, G.Choosing instance selection method using meta-learning. In: IEEE INTERNATIONALCONFERENCE ON SYSTEMS, MAN AND CYBERNETICS, 2014. Anais. . . [S.l.: s.n.],2014. p.2003–2007.

REFERÊNCIAS 125

OLIVEIRA MOURA, S. de; FREITAS, M. Bassani de; CARDOSO, H.; CAVALCANTI, G.Uma abordagem para a escolha do melhor método de seleção de instâncias usandometa-aprendizagem. In: ENCONTRO NACIONAL DE INTELIGêNCIA ARTIFICIAL ECOMPUTACIONAL, 2014. Anais. . . [S.l.: s.n.], 2014.

PIETRAMALA, A.; POLICICCHIO, V. L.; RULLO, P.; SIDHU, I. A genetic algorithm fortext classification rule induction. In: Machine Learning and Knowledge Discovery inDatabases. [S.l.]: Springer, 2008. p.188–203.

PLATT, J. C. Fast training of support vector machines using sequential minimaloptimization. Advances in kernel methods—support vector learning, [S.l.], v.3,1999.

QUINLAN, J. R. Induction of decision trees. Machine learning, [S.l.], v.1, n.1, p.81–106,1986.

QUINLAN, J. R. C4.5: programs for machine learning. [S.l.]: Morgan kaufmann, 1993.v.1.

REINARTZ, T. A unifying view on instance selection. Data Mining and KnowledgeDiscovery, [S.l.], v.6, n.2, p.191–210, 2002.

RIQUELME, J. C.; AGUILAR-RUIZ, J. S.; TORO, M. Finding representative patternswith ordered projections. Pattern Recognition, [S.l.], v.36, n.4, p.1009–1018, 2003.

RITTER, G.; WOODRUFF, H.; LOWRY, S.; ISENHOUR, T. An algorithm for a selectivenearest neighbor decision rule. IEEE Transactions on Information Theory, [S.l.],v.21, n.6, p.665–669, 1975.

RONG-EN, F. LIBSVM Data: classification, regression, and multi-label. Acessado em:02 de agosto de 2015, http://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets.

ROSENBLATT, F. The perceptron: a probabilistic model for information storage andorganization in the brain. Psychological review, [S.l.], v.65, n.6, p.386, 1958.

RUMELHART, D.; HINTON, G.; WILLIAMS, R. Learning internal representation byback propagation. Parallel distributed processing: exploration in themicrostructure of cognition, [S.l.], v.1, 1986.

SILVA, I. N. da; SPATTI, D. H.; FLAUZINO, R. A. Redes Neurais Artificiais paraengenharia e ciências aplicadas curso prático. Artliber, [S.l.], 2010.

SMITH-MILES, K. A. Cross-disciplinary perspectives on meta-learning for algorithmselection. ACM Computing Surveys (CSUR), [S.l.], v.41, n.1, p.6, 2008.

SMITH-MILES, K.; ISLAM, R. Meta-learning for data summarization based oninstance selection method. In: IEEE CONGRESS ON EVOLUTIONARYCOMPUTATION, 2010. Anais. . . [S.l.: s.n.], 2010. p.1–8.

SONNENBURG, S.; ONG, C. S.; HENSCHEL, S.; BRAUN, M. L.; HOYER, P. O. MachineLearning Data Set Repository (2011). Acessado em: 02 de agosto de 2013.

REFERÊNCIAS 126

SOTOCA, J.; MOLLINEDA, R.; SANCHEZ, J. A meta-learning framework for patternclassification by means of data complexity measures. Inteligencia Artificial, [S.l.],v.10, n.29, p.31–38, 2006.

TOMEK, I. An Experiment with the Edited Nearest-Neighbor Rule. IEEE Transactionson Systems, Man and Cybernetics, [S.l.], n.6, p.448–452, 1976.

TRIGUERO, I.; GARCÍA, S.; HERRERA, F. Differential evolution for optimizing thepositioning of prototypes in nearest neighbor classification. Pattern Recognition,[S.l.], v.44, n.4, p.901–916, 2011.

VALIANT, L. G. A theory of the learnable. Communications of the ACM, [S.l.], v.27,n.11, p.1134–1142, 1984.

WILSON, D. L. Asymptotic Properties of Nearest Neighbor Rules Using Edited Data.IEEE Transactions on Systems, Man and Cybernetics, [S.l.], v.SMC-2, n.3, p.408–421,1972.

WILSON, D. R.; MARTINEZ, T. R. Improved heterogeneous distance functions.Journal of Artificial Intelligence Research, [S.l.], p.1–34, 1997.

WILSON, D. R.; MARTINEZ, T. R. Reduction techniques for instance-based learningalgorithms. Machine learning, [S.l.], v.38, n.3, p.257–286, 2000.

WOLPERT, D. H.; MACREADY, W. G. No free lunch theorems for optimization. IEEETransactions on Evolutionary Computation, [S.l.], v.1, n.1, p.67–82, 1997.

WU, X.; KUMAR, V.; QUINLAN, J. R.; GHOSH, J.; YANG, Q.; MOTODA, H.;MCLACHLAN, G. J.; NG, A.; LIU, B.; PHILIP, S. Y. et al. Top 10 algorithms in datamining. Knowledge and Information Systems, [S.l.], v.14, n.1, p.1–37, 2008.

ZHANG, H.; SUN, G. Optimal reference subset selection for nearest neighborclassification by tabu search. Pattern Recognition, [S.l.], v.35, n.7, p.1481–1490, 2002.

ZHAO, K.-P.; ZHOU, S.-G.; GUAN, J.-H.; ZHOU, A.-Y. C-pruner: an improved instancepruning algorithm. In: INTERNATIONAL CONFERENCE ON MACHINE LEARNINGAND CYBERNETICS, 2003. Anais. . . [S.l.: s.n.], 2003. v.1, p.94–99.