( PDF ) Extração de conhecimentos simbólicos em técnicas de aprendizado de máquina caixa-preta por similaridade de rankings

Download PDF

ads:

Extrac¸

ao de conhecimento simb

olico

em t

ecnicas de aprendizado de

aquina caixa-preta por similaridade

de rankings

Rodrigo Elias Bianchi

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

ads:

SERVIC¸ O DE P

OS-GRADUAC¸

AO DO ICMC-

USP

Data de Dep

osito: 07.07.2008

Assinatura:

Extrac¸

ao de conhecimento

simb

olico em t

ecnicas de

aprendizado de m

aquina

caixa-preta por similaridade de

rankings

Rodrigo Elias Bianchi

Orientador: Prof. Dr. Andr

e Carlos Ponce de Leon Ferreira de Carvalho

Tese apresentada ao Instituto de Ci

encias Matem

aticas e

de Computac¸

ao - ICMC-USP, como parte dos requisitos

para obtenc¸

ao do t

ıtulo de Doutor em Ci

encias - Ci

encias

de Computac¸

ao e Matem

atica Computacional.

USP - S

ao Carlos

Julho de 2008

Este documento foi preparado utilizando-se o formatador de textos L

Sua bibliograﬁa

e gerada automaticamente pelo BIBT

X, utilizando o estilo

Apalike. O estilo dos t

ıtulos dos cap

ıtulos foi gentilmente cedido pelo amigo

Ronaldo C. Prati.

Este trabalho conta com apoio ﬁnanceiro da FAPESP processo n

03/00099-5

Agradecimentos

Gostaria de agradecer ao Andr

e, meu orientador, pela oportunidade, orien-

tac¸

ao e toda a paci

encia que ele teve comigo durante esses anos. Gostaria de

agradecer tamb

em aos amigos Gustavo e Cl

audia, pois sem eles a parte experi-

mental desse trabalho n

ao teria sido poss

ıvel. Agradec¸o aos meus pais, Neida

e Roberto por tudo o que ﬁzeram por mim desde o dia em que nasci e todo

o carinho que sempre me deram. Isso foi essencial ao meu desenvolvimento.

Tudo o que sou se deve ao esforc¸o deles. Muito obrigado! Agradec¸o

a minha

namorada Miyuki, por todos os momentos que tivemos juntos, que me deram

forc¸a para ir em frente, e por me ag

uentar e entender a minha aus

encia nos

momentos dif

ıceis que tive no doutorado. Tamb

em quero agradecer a todos

os meus amigos, os que est

ao perto e os que est

ao longe, do LABIC/BIOCOM,

dos outros laborat

orios e departamentos da USP, professores e funcion

arios do

ICMC e da Unioeste, do Kendo, de Foz do Iguac¸u, de S

ao Paulo, enﬁm, todos

os meus amigos e familiares que sempre me apoiaram incondicionalmente.

Doumo arigatou gozaimashita!

Resumo

ecnicas de Aprendizado de M

aquina n

ao-simb

olicas, como Redes Neu-

rais Artiﬁciais, M

aquinas de Vetores de Suporte e combinac¸

ao de classiﬁca-

dores t

em mostrado um bom desempenho quando utilizadas para an

alise de

dados. A grande limitac¸

ao dessas t

ecnicas

e a falta de compreensibilidade

do conhecimento armazenado em suas estruturas internas. Esta Tese apre-

senta uma pesquisa realizada sobre m

etodos de extrac¸

ao de representac¸

oes

compreens

ıveis do conhecimento armazenado nas estruturas internas des-

sas t

ecnicas n

ao-simb

olicas, aqui chamadas de caixa preta, durante seu pro-

cesso de aprendizado. A principal contribuic¸

ao desse trabalho

e a proposta

de um novo m

etodo pedag

ogico para extrac¸

ao de regras que expliquem o pro-

cesso de classiﬁcac¸

ao seguido por t

ecnicas n

ao-simb

olicas. Esse novo m

etodo

e baseado na otimizac¸

ao (maximizac¸

ao) da similaridade entre rankings de

classiﬁcac¸

ao produzidos por t

ecnicas de Aprendizado de M

aquina simb

olicas

e n

ao simb

olicas (de onde o conhecimento interno esta sendo extra

ıdo). Ex-

perimentos foram realizados com v

arios conjuntos de dados e os resultados

obtidos sugerem um bom potencial para o m

etodo proposto.

Abstract

Non-symbolic Machine Learning techniques, like Artiﬁcial Neural Networks,

Support Vector Machines and Ensembles of classiﬁers have shown a good

performance when they are used in data analysis. The strong limitation re-

garding the use of these techniques is the lack of comprehensibility of the

knowledge stored in their internal structure. This Thesis presents an inves-

tigation of methods capable of extracting comprehensible representations of

the knowledge acquired by these non-symbolic techniques, here named black

box, during their learning process. The main contribution of this work is the

proposal of a new pedagogical method for rule extraction that explains the

classiﬁcation process followed by non-symbolic techniques. This new method

is based on the optimization (maximization) of the similarity between clas-

siﬁcation rankings produced by symbolic and non-symbolic (from where the

internal knowledge is being extracted) Machine Learning techniques. Experi-

ments were performed for several datasets and the results obtained suggest a

good potential of the proposed method.

Sum

ario

Sum

ario 11

Lista de Algoritmos 13

Lista de Figuras 15

Lista de Tabelas 17

1 Introduc¸

ao 23

1.1 Justiﬁcativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.2 Organizac¸

ao da Tese . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Aprendizado de M

aquina 27

2.1 Paradigmas de Aprendizado . . . . . . . . . . . . . . . . . . . . . . 28

2.1.1 Aprendizado Supervisionado . . . . . . . . . . . . . . . . . . 28

2.1.2 Aprendizado N

ao-Supervisionado . . . . . . . . . . . . . . . 30

2.1.3 Aprendizado por Reforc¸o . . . . . . . . . . . . . . . . . . . . 31

2.2 Aprendizado de M

aquina Simb

olico . . . . . . . . . . . . . . . . . . 31

2.2.1

Arvores de Decis

ao . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2.2 Regras de Decis

ao . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3 Aprendizado de M

aquina N

ao-Simb

olico . . . . . . . . . . . . . . . 36

2.3.1 Redes Neurais Artiﬁciais . . . . . . . . . . . . . . . . . . . . 36

2.3.2 Classiﬁcadores de Margens Largas . . . . . . . . . . . . . . 40

2.4 Algoritmos Gen

eticos . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.4.1 Caracter

ısticas Gerais . . . . . . . . . . . . . . . . . . . . . . 45

2.4.2 Representac¸

ao . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.4.3 Selec¸

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.4.4 Operadores Gen

eticos . . . . . . . . . . . . . . . . . . . . . . 49

2.4.5 Par

ametros Gen

eticos . . . . . . . . . . . . . . . . . . . . . . 51

2.5 Considerac¸

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3 Extrac¸

ao de Conhecimento em T

ecnicas de AM Caixa-Preta 53

3.1 M

etodos Pedag

ogicos . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.2 M

etodos Decomposicionais . . . . . . . . . . . . . . . . . . . . . . . 55

3.3 M

etodos Ecl

eticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4 M

etricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.5 Extrac¸

ao de Conhecimento de SVMs . . . . . . . . . . . . . . . . . . 56

3.6 Sistema NNRules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.6.1 M

etodo baseado em Aprendizado de M

aquina Simb

olico . . 58

3.6.2 M

etodo Baseado em Algoritmos Gen

eticos . . . . . . . . . . 59

3.7 Considerac¸

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4 M

etodo Proposto 61

4.1 Descric¸

ao do M

etodo RankSim . . . . . . . . . . . . . . . . . . . . . 62

4.2 Func¸

ao de Avaliac¸

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.3 Caracter

ısticas do Algoritmo Gen

etico . . . . . . . . . . . . . . . . 64

4.4 Considerac¸

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5 Experimentos Realizados 67

5.1 Fase I - Estudo preliminar de extrac¸

ao de regras de RNAs e SVMs

por m

etodos de AM e AGs . . . . . . . . . . . . . . . . . . . . . . . . 67

5.1.1 Identiﬁcac¸

ao de Promotores e S

ıtios de Splice . . . . . . . . 67

5.1.2 Conjuntos de Dados . . . . . . . . . . . . . . . . . . . . . . . 68

5.1.3 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.1.4 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.2 Fase II - Experimentos com o m

etodo RankSim . . . . . . . . . . . 75

5.2.1 Conjunto breast . . . . . . . . . . . . . . . . . . . . . . . . . 76

5.2.2 Conjunto bupa . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.2.3 Conjunto ecoli . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.2.4 Conjunto ﬂag . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.2.5 Conjunto ﬂare . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.2.6 Conjunto glass . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.2.7 Conjunto haberman . . . . . . . . . . . . . . . . . . . . . . . 81

5.2.8 Conjunto heart . . . . . . . . . . . . . . . . . . . . . . . . . . 82

5.2.9 Conjunto pima . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.2.10Conjunto ionosphere . . . . . . . . . . . . . . . . . . . . . . 84

5.2.11new-thyroid . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

5.2.12Conjunto post-operative . . . . . . . . . . . . . . . . . . . . . 86

5.2.13Conjunto satimage . . . . . . . . . . . . . . . . . . . . . . . . 86

5.2.14Conjunto spliceN . . . . . . . . . . . . . . . . . . . . . . . . . 87

5.2.15Conjunto spliceEI . . . . . . . . . . . . . . . . . . . . . . . . 88

5.2.16Conjunto promoters . . . . . . . . . . . . . . . . . . . . . . . 88

5.2.17Conjunto german . . . . . . . . . . . . . . . . . . . . . . . . . 89

5.3 Considerac¸

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6 Conclus

ao 95

6.1 Resumo dos objetivos e resultados . . . . . . . . . . . . . . . . . . 95

6.2 Limitac¸

oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

6.3 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Refer

encias 97

Lista de Algoritmos

1 Algoritmo backpropagation . . . . . . . . . . . . . . . . . . . . . . . 40

2 Algoritmo de treinamento da rede SOM . . . . . . . . . . . . . . . . 40

3 Algoritmo Gen

etico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4 Algoritmo SVM+Prototypes . . . . . . . . . . . . . . . . . . . . . . . . 57

Lista de Figuras

2.1

Arvore de Decis

ao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2 Rede Perceptron. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.3 Rede Neural MLP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.4 Rede Neural SOM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.5 Um conjunto de dados linearmente separ

avel. . . . . . . . . . . . 41

2.6 Duas formas de separar o mesmo conjunto de dados. O hiper-

plano de a) n

ao maximiza as margens de separac¸

ao enquanto do

de b) determina uma grande margem de separac¸

ao entre a fron-

teira de decis

ao e os exemplos. . . . . . . . . . . . . . . . . . . . . . 42

2.7 M

etodo de selec¸

ao por torneio. . . . . . . . . . . . . . . . . . . . . . 49

2.8 Exemplo de mutac¸

ao. . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.9 Exemplo de cruzamento de um ponto. . . . . . . . . . . . . . . . . 50

2.10Exemplo de cruzamento de dois pontos. . . . . . . . . . . . . . . . 51

2.11Um exemplo de Cruzamentouniforme. . . . . . . . . . . . . . . . . 51

3.1 Esquema geral do m

etodo baseado em sistemas de AM simb

olicos. 58

3.2 Esquema geral do m

etodo baseado em AGs. . . . . . . . . . . . . . 59

4.1 M

etodo RankSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

Lista de Tabelas

2.1 Tabela atributo valor com exemplos para classiﬁcac¸

ao. . . . . . . 29

2.2 Tabela atributo valor com exemplos para regress

ao. . . . . . . . . 30

2.3 Tabela atributo valor com exemplos para agrupamento. . . . . . . 31

2.4 Conjunto de dados Viagem. . . . . . . . . . . . . . . . . . . . . . . 34

2.5 Conjunto de regras ordenadas para o conjunto de dados Viagem. 35

2.6 Conjunto de regras n

ao ordenadas para o conjunto de dados Vi-

agem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.7 Regras n

ao ordenadas com o

ındice do poder de predic¸

ao das

regras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.1 Operac¸

ao de Cruzamento . . . . . . . . . . . . . . . . . . . . . . . . 65

5.1 Taxa de Erro (m

edia e desvio padr

ao)(%). . . . . . . . . . . . . . . . 70

5.2 Taxa de inﬁdelidade (RNAs - m

edia e desvio padr

ao)(%). . . . . . . 71

5.3 Taxa de inﬁdelidade (SVMs - m

edia e desvio padr

ao)(%). . . . . . . 71

5.4 N

umero de regras induzidas (RNAs - m

edia e desvio padr

ao). . . . 71

5.5 N

umero de regras induzidas (SVMs - m

edia e desvio padr

ao). . . . 71

5.6 N

umero m

edio de condic¸

oes por regra induzida (RNAs - m

edia e

desvio padr

ao). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.7 N

umero m

edio de condic¸

oes por regra induzida (SVMs - m

edia e

desvio padr

ao). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.8 Resultados do 10-Fold Cross-Validated Paired t Test (RNAs). . . . . 73

5.9 Resultados do 10-Fold Cross-Validated Paired t Test (SVMs). . . . . 74

5.10Comparac¸

ao da aplicac¸

ao de m

etodos de extrac¸

ao de regras em

RNAs e em SVMs). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.11Descric¸

ao dos Conjuntos de Dados . . . . . . . . . . . . . . . . . . 76

5.12Conjunto breast - Acur

acia e Fidelidade (%). . . . . . . . . . . . . . 77

5.13Conjunto breast - N

umero de Regras. . . . . . . . . . . . . . . . . . 77

5.14Conjunto breast - N

umero de Condic¸

oes por Regra. . . . . . . . . 77

5.15Conjunto bupa - Acur

acia e Fidelidade (%). . . . . . . . . . . . . . 77

5.16Conjunto bupa - N

umero de Regras. . . . . . . . . . . . . . . . . . 78

5.17Conjunto bupa - N

umero de Condic¸

oes por Regra. . . . . . . . . . 78

5.18Conjunto ecoli - Acur

acia e Fidelidade (%). . . . . . . . . . . . . . . 78

5.19Conjunto ecoli - N

umero de Regras. . . . . . . . . . . . . . . . . . . 79

5.20Conjunto ecoli - N

umero de Condic¸

oes por Regra. . . . . . . . . . 79

5.21Conjunto ﬂag - Acur

acia e Fidelidade (%). . . . . . . . . . . . . . . 79

5.22Conjunto ﬂag - N

umero de Regras. . . . . . . . . . . . . . . . . . . 79

5.23Conjunto ﬂag - N

umero de Condic¸

oes por Regra. . . . . . . . . . . 80

5.24Conjunto ﬂare - Acur

acia e Fidelidade (%). . . . . . . . . . . . . . . 80

5.25Conjunto ﬂare - N

umero de Regras. . . . . . . . . . . . . . . . . . . 80

5.26Conjunto ﬂare - N

umero de Condic¸

oes por Regra. . . . . . . . . . 81

5.27Conjunto glass - Acur

acia e Fidelidade (%). . . . . . . . . . . . . . 81

5.28Conjunto glass - N

umero de Regras. . . . . . . . . . . . . . . . . . 81

5.29Conjunto glass - N

umero de Condic¸

oes por Regra. . . . . . . . . . 81

5.30Conjunto haberman - Acur

acia e Fidelidade (%). . . . . . . . . . . 82

5.31Conjunto haberman - N

umero de Regras. . . . . . . . . . . . . . . 82

5.32Conjunto haberman - N

umero de Condic¸

oes por Regra. . . . . . . 82

5.33Conjunto heart - Acur

acia e Fidelidade (%). . . . . . . . . . . . . . 83

5.34Conjunto heart - N

umero de Regras. . . . . . . . . . . . . . . . . . 83

5.35Conjunto heart - N

umero de Condic¸

oes por Regra. . . . . . . . . . 83

5.36Conjunto pima - Acur

acia e Fidelidade (%). . . . . . . . . . . . . . 83

5.37Conjunto Pima - N

umero de Regras. . . . . . . . . . . . . . . . . . 84

5.38Conjunto Pima - N

umero de Condic¸

oes por Regra. . . . . . . . . . 84

5.39Conjunto ionosphere - Acur

acia e Fidelidade (%). . . . . . . . . . . 84

5.40Conjunto ionosphere - N

umero de Regras. . . . . . . . . . . . . . . 84

5.41Conjunto ionosphere - N

umero de Condic¸

oes por Regra. . . . . . . 85

5.42Conjunto new-thyroid - Acur

acia e Fidelidade (%). . . . . . . . . . 85

5.43Conjunto new-thyroid - N

umero de Regras. . . . . . . . . . . . . . 85

5.44Conjunto new-thyroid - N

umero de Condic¸

oes por Regra. . . . . . 85

5.45Conjunto post-operative - Acur

acia e Fidelidade (%). . . . . . . . . 86

5.46Conjunto post-operative - N

umero de Regras. . . . . . . . . . . . . 86

5.47Conjunto post-operative - N

umero de Condic¸

oes por Regra. . . . . 86

5.48Conjunto satimage - Acur

acia e Fidelidade (%). . . . . . . . . . . . 87

5.49Conjunto satimage - N

umero de Regras. . . . . . . . . . . . . . . . 87

5.50Conjunto satimage - N

umero de Condic¸

oes por Regra. . . . . . . . 87

5.51Conjunto spliceN - Acur

acia e Fidelidade (%). . . . . . . . . . . . . 87

5.52Conjunto spliceN - N

umero de Regras. . . . . . . . . . . . . . . . . 88

5.53Conjunto spliceN - N

umero de Condic¸

oes por Regra. . . . . . . . . 88

5.54Conjunto spliceEI - Acur

acia e Fidelidade (%). . . . . . . . . . . . . 88

5.55Conjunto spliceEI - N

umero de Regras. . . . . . . . . . . . . . . . . 88

5.56Conjunto spliceEI - N

umero de Condic¸

oes por Regra. . . . . . . . 89

5.57Conjunto promoters - Acur

acia e Fidelidade (%). . . . . . . . . . . 89

5.58Conjunto promoters - N

umero de Regras. . . . . . . . . . . . . . . 89

5.59Conjunto promoters - N

umero de Condic¸

oes por Regra. . . . . . . 89

5.60Conjunto german - Acur

acia e Fidelidade (%). . . . . . . . . . . . . 90

5.61Conjunto german - N

umero de Regras. . . . . . . . . . . . . . . . . 90

5.62Conjunto german - N

umero de Condic¸

oes por Regra. . . . . . . . . 90

5.63Acur

acia e Fidelidade(%) . . . . . . . . . . . . . . . . . . . . . . . . 91

5.64N

umero de Regras . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5.65N

umero de Condic¸

oes por Regra . . . . . . . . . . . . . . . . . . . . 92

5.66Fidelidade: RankSim Original, RankSim Rotulado e NNRules . . . 93

CAP

ITULO

Introduc¸

ecnicas de Intelig

encia Artiﬁcial t

em sido amplamente utilizadas para

a resoluc¸

ao de problemas em diversos dom

ınios. Como exemplo, po-

demos citar a an

alise de dados biol

ogicos. Dentre elas, destacam-

se as t

ecnicas de Aprendizado de M

aquina, que s

ao capazes de formular

descric¸

oes de conceitos a partir de exemplos (Mitchel, 1997).

Redes Neurais Artiﬁciais (RNAs) (Braga et al., 2000; Haykin, 1998) e Clas-

siﬁcadores de Margens Largas (Lorena and de Carvalho, 2003), como as M

quinas de Vetores de Suporte (Support Vector Machines - SVM) (Cristianini and

Shawe-Taylor, 2000), s

ao t

ecnicas n

ao-simb

olicas de aprendizado de m

aquina

que t

em sido utilizadas com sucesso para a soluc¸

ao de diversos problemas re-

ais. Essas t

ecnicas s

ao consideradas como “caixas-pretas”, pela diﬁculdade

em explicar como elas chegam aos seus resultados.

Muitos problemas de an

alise de dados podem ser modelados como proble-

mas de classiﬁcac¸

. Em certos casos, explicitar o conhecimento utilizado

para a classiﬁcac¸

e mais importante do que a pr

opria classiﬁcac¸

ao. Por

isso, em t

ecnicas n

ao-simb

olicas de aprendizado de m

aquina,

e poss

ıvel re-

alizar uma explicac¸

ao do conhecimento armazenado internamente por essas

ecnicas com base na extrac¸

ao de representac¸

oes simb

olicas desse conheci-

mento.

Existem diversos trabalhos que abordam esse tema (Fu, 1991; Hayashi,

1991; Towell and Shavlik, 1993; Craven and Shavlik, 1994b; Fu, 1994; Sethi

and Yoo, 1994; Tan, 1994; Thrun, 1994; Tickle et al., 1994; Alexander and

Dietterich, 1995; Setiono and Liu, 1995; Thrun, 1995; Craven, 1996; Milar

et al., 1997; Schellharmmer et al., 1997; Tickle et al., 1998; Martineli, 1999;

Schmitz et al., 1999; Duch et al., 2000; Behloul et al., 2002; Zhou and Jiang,

2002; Milar

e et al., 2002; N

nez et al., 2002; Fung et al., 2008).

Dados exemplos de um conceito, um algoritmo de Aprendizado de M

aquina induz um

classiﬁcador que

e ent

ao utilizado para predizer a classe de novos exemplos.

24 Cap

ıtulo 1

Por

em, os m

etodos propostos possuem um grande n

umero de deﬁci

encias.

Craven and Shavlik (1999) identiﬁcaram que a escalabilidade

e a gene-

ralidade

ao m

etricas que n

ao foram contempladas na grande maioria dos

etodos desenvolvidos. Milar

e et al. (2002) tamb

em relatou que essas ainda

ao quest

oes em aberto. Al

em disso, existem outras deﬁci

encias relacionadas

a qualidade das representac¸

oes extra

ıdas por esses m

etodos, que s

ao descritas

na Sec¸

ao 1.1.

Portanto,

e necess

ario investigar alternativas para melhorar a qualidade

das representac¸

oes obtidas e reduzir o tempo de execuc¸

ao dos algoritmos atu-

almente utilizados para este ﬁm. Essa qualidade pode ser medida por meio

de m

etricas como compreensibilidade, ﬁdelidade, precis

ao, escalabilidade e

generalidade, al

em de outras que ser

ao descritas na Sec¸

ao 3.4 dessa Tese.

Essa Tese investiga m

etodos para explicar como os classiﬁcadores indu-

zidos por t

ecnicas n

ao-simb

olicas de aprendizado de m

aquina realizam as

classiﬁcac¸

oes e prop

oe um novo m

etodo pedag

ogico que utiliza um algoritmo

gen

etico para extrair regras de modelos de aprendizado de m

aquina caixa-

preta. A novidade do m

etodo est

a na avaliac¸

ao da similaridade entre rankings

de conﬁabilidade gerados para o modelo caixa-preta e os rankings gerados

para os indiv

ıduos do algoritmo gen

etico, que representam os poss

ıveis con-

juntos de regras extra

ıdos.

Dentre as t

ecnicas n

ao-simb

olicas de aprendizado de m

aquina, a enfase

foi conferida aos Classiﬁcadores de Margens Largas, em especial

as Support

Vector Machines - SVMs, pois sua aplicac¸

ao em diversos dom

ınios como Bioin-

form

atica e Minerac¸

ao de Textos

e promissora, possuindo diversos resultados

relevantes publicados (Jackson, 1995; Furey et al., 2000; Zien et al., 2000;

Ben-Hur et al., 2000; Ding and Dubchak, 2001; Huss et al., 2001; Mukher-

jee and Mukherjee, 2002; Lorena et al., 2002) e a extrac¸

ao de representac¸

oes

simb

olicas de conhecimento para essas t

ecnicas ainda est

a em sua inf

ancia.

1.1 Justiﬁcativa

E de grande import

ancia para v

arias aplicac¸

oes reais investigar alternativas

eﬁcientes para a extrac¸

ao de conhecimento para t

ecnicas n

ao-simb

olicas de

Aprendizado de M

aquina, pois podem elevar a compreensibilidade do conhe-

cimento adquirido por essas t

ecnicas.

Em v

arios dom

ınios, as SVMs, que induzem classiﬁcadores n

ao-simb

olicos,

A escalabilidade se refere a como o tempo de execuc¸

ao e a compreensibilidade dos mode-

los extra

ıdos variam em func¸

ao de fatores como dimensionalidade, tamanho do conjunto de

treinamento e complexidade do m

etodo de aprendizado de m

aquina.

Generalidade

e a proporc¸

ao em que o algoritmo de extrac¸

ao de conhecimento n

ao requer

treinamentos especiais ou restric¸

oes no m

etodo de aprendizado de m

aquina.

Introduc¸

ao 25

em obtido taxas de acerto superiores

as obtidas por outras t

ecnicas (Zien

et al., 2000; Ding and Dubchak, 2001).

Por

em, seres humanos t

em diﬁculdade em entender as representac¸

oes in-

ternas utilizadas por t

ecnicas n

ao-simb

olicas de Aprendizado de M

aquina.

Portanto, para fazer proveito das vantagens dessas t

ecnicas no entendimento

dos mecanismos utilizados por v

arios modelos de classiﬁcac¸

e necess

ario

algum processo de extrac¸

ao de conhecimento que gere representac¸

oes mais

compreens

ıveis, mas que mantenham ﬁdelidade com o m

etodo n

ao-simb

olico

originalmente utilizado. Entretanto, no in

ıcio de nossa pesquisa, n

ao foram

encontrados na literatura m

etodos de extrac¸

ao de conhecimento espec

ıﬁcos

para Classiﬁcadores de Margens Largas. Somente durante o desenvolvimen-

tos dessa pesquisa

e que foram surgindo m

etodos espec

ıﬁcos.

em disso, os m

etodos existentes at

e ent

ao para a extrac¸

ao de conheci-

mento de RNAs possuem v

arias deﬁci

encias. Dentre elas podem ser citadas:

• Em m

etodos decomposicionais, a diﬁculdade de se associar uma func¸

determinada a um neur

onio individual de uma Rede Neural Artiﬁcial, de-

vido ao fato de que muitas vezes o conhecimento encontra-se distribu

ıdo

na rede.

• Em m

etodos pedag

ogicos, n

ao h

a garantias de que as representac¸

oes

extra

ıdas expressem a forma pela qual a Rede Neural Artiﬁcial realiza a

classiﬁcac¸

ao, pois n

ao fazem nenhuma an

alise dos par

ametros internos

da rede e se a performance de classiﬁcac¸

ao da RNA for elevada, o conjunto

de dados por ela rotulado ser

a t

ao parecido com o conjunto de dados

original que pouca informac¸

ao pode ser extra

ıda sobre a forma utilizada

pela RNA para realizar sua classiﬁcac¸

ao.

• M

etodos ecl

eticos n

ao solucionam os problemas das duas anteriores e

geralmente s

ao complexos e ineﬁcientes.

1.2 Organizac¸

ao da Tese

Esse cap

ıtulo apresentou o projeto de pesquisa abordando a sua motivac¸

ao,

objetivos e justiﬁcativa. O Cap

ıtulo 2 apresentar

a uma vis

ao geral sobre a

area

de Aprendizado de M

aquina. O Cap

ıtulo 3 cont

em revis

ao sobre a extrac¸

ao de

conhecimento para m

etodos de Aprendizado de M

aquina n

ao-simb

olicos. O

Cap

ıtulo 4 apresentar

a o m

etodo de extrac¸

ao de conhecimento para t

ecnicas

de aprendizado de m

aquina caixa-preta proposto nessa tese. O Cap

ıtulo 5

descrever

a os experimentos realizados, discutindo seus resultados. Por ﬁm, o

26 Cap

ıtulo 1

Cap

ıtulo 6 conclui a tese com algumas considerac¸

oes sobre o atual est

agio do

trabalho.

CAP

ITULO

Aprendizado de M

aquina

esde o in

ıcio da Computac¸

ao, fazer com que as m

aquinas apren-

dam t

em sido um desaﬁo perseguido por v

arios pesquisadores. Os

benef

ıcios de se ter programas que melhoram automaticamente

atrav

es de experi

encia s

ao inestim

aveis. Alguns avanc¸os t

em sido realizados

em direc¸

ao a esse objetivo e a linha de pesquisa que aborda esse tema

e cha-

mada Aprendizado de M

aquina (AM) (Mitchel, 1997).

Nesse trabalho, o principal interesse est

a na tarefa particular de aprender

(induzir) func¸

oes gerais a partir de exemplos de treinamento. Os paradigmas

de aprendizado por exemplos mais utilizados s

ao o aprendizado supervisi-

onado, o aprendizado n

ao-supervisionado e o aprendizado por reforc¸o. Na

Sec¸

ao 2.1 s

ao descritos esses tr

es paradigmas.

area de AM pode ser dividida em duas grandes sub-

areas: Aprendi-

zado de M

aquina simb

olico e Aprendizado de M

aquina n

ao-simb

olico ou sub-

simb

olico. As t

ecnicas de AM simb

olico s

ao aquelas em que o conhecimento

aprendido

e representado em uma forma de f

acil compreens

ao por seres hu-

manos. Exemplos dessas t

ecnicas incluem os algoritmos de induc¸

ao de

arvo-

res de decis

ao e regras de decis

ao (ver Figura 2.1 e Tabela 2.5). J

a as t

ecnicas

de AM n

ao-simb

olico utilizam representac¸

oes de dif

ıcil compreens

ao por seres

humanos, em sua maioria, modelos matem

aticos complexos. Por esse motivo,

essas t

ecnicas s

ao usualmente chamadas de t

ecnicas caixa-preta. Redes Neu-

rais Artiﬁciais (RNAs) (Braga et al., 2000; Haykin, 1998) e M

aquinas de Vetores

de Suporte (Support Vector Machines - SVMs) (Cristianini and Shawe-Taylor,

2000) s

ao exemplos destas t

ecnicas.

ao se pode dizer que uma

unica dessas t

ecnicas

e superior

as outras

para todos os casos. Portanto, para cada problema de aprendizado, deve-

se analisar qual t

ecnica possui as melhores caracter

ısticas para lidar com

o problema. As caracter

ısticas que fazem uma t

ecnica de aprendizado ser

28 Cap

ıtulo 2

melhor para determinados tipos de problema s

ao coletivamente chamadas na

literatura da

area de bias indutivo (Mitchel, 1997).

Para muitos problemas, como os de an

alise de conjuntos de dados de alta

dimensionalidade, as t

ecnicas de AM n

ao-simb

olico possuem um bias indutivo

mais apropriado. Por exemplo, em an

alise de express

ao g

enica, as bases de

dados s

ao grandes e de alta dimensionalidade (milhares de atributos). Mui-

tos m

etodos tradicionais t

em diﬁculdades em lidar com esse tipo de dados

enquanto as SVMs s

ao apropriadas para lidar com dados de alta dimensio-

nalidade (Furey et al., 2000; Brown et al., 2000; Ding and Dubchak, 2001).

Por

em, para muitos destes problemas, o entendimento do conhecimento ad-

quirido pela t

ecnica para a resoluc¸

ao do problema

e de grande import

ancia.

Surgiu ent

ao a necessidade da elaborac¸

ao de m

etodos de extrac¸

ao de conhe-

cimento para t

ecnicas de AM n

ao-simb

olico. Esses m

etodos s

ao discutidos no

Cap

ıtulo 3.

Nas Sec¸

oes 2.2 e 2.3, ser

ao apresentadas algumas t

ecnicas de AM, tanto

simb

olico como n

ao-simb

olico, com o objetivo de dar ao leitor um maior en-

tendimento das diferentes abordagens empregadas e a Sec¸

ao 2.5 conclui o

cap

ıtulo com algumas considerac¸

oes ﬁnais.

2.1 Paradigmas de Aprendizado

De acordo com o tipo da tarefa de aprendizado e as informac¸

oes dispon

ıveis

para o treinamento,

e poss

ıvel dividir as t

ecnicas de aprendizado de m

aquina

em tr

es paradigmas: aprendizado supervisionado, aprendizado n

ao-supervi-

sionado e aprendizado por reforc¸o. Nessa sec¸

ao esses tr

es paradigmas ser

sucintamente apresentados.

2.1.1 Aprendizado Supervisionado

No aprendizado supervisionado,

e apresentado ao sistema de aprendizado um

conjunto de exemplos rotulado. Isso signiﬁca que entre os v

arios atributos

de um exemplo, um

e destinado

a sa

ıda desejada, o r

otulo. Ou seja, h

a um

mapeamento expl

ıcito entre os atributos do exemplo e a sa

ıda correta que o

sistema de aprendizado, ap

os treinado, deve retornar ao lhe ser apresentado

o exemplo. Ele

e chamado de aprendizado supervisionado pois

e como se

houvesse um professor informando qual a sa

ıda correta para cada exemplo.

O aprendizado supervisionado pode ser ainda dividido em dois grupos,

classiﬁcac¸

ao e regress

ao, de acordo com o tipo de sa

ıda retornada pelo sis-

tema de aprendizado.

Nas tarefas de classiﬁcac¸

ao, o sistema de aprendizado possui um con-

junto discreto e determinado de sa

ıdas poss

ıveis. O tipo mais simples de

Aprendizado de M

aquina 29

classiﬁcac¸

e a que tem sa

ıda bin

aria, ou seja, a que pode retornar ape-

nas uma entre duas classes: sim ou n

ao; 0 ou 1; presente ou ausente; etc.

Existe tamb

em a classiﬁcac¸

ao multi-classes, em que mais de duas classes

ao poss

ıveis para a sa

ıda: Vermelho, Verde ou Azul; 0, 1, 2, 3 ou 4; Ade-

nina (A), Citosina (C), Guanina (G) e Timina (T); etc. Finalmente, existe a

classiﬁcac¸

ao hier

arquica, em que as classes obedecem uma hierarquia. Nesse

tipo de classiﬁcac¸

ao, os exemplos s

ao classiﬁcados em classes de uma

arvore

de categorias. Em uma

arvore de categorias, cada n

o corresponde a uma

classe. Como resultado, existe um relacionamento hier

arquico entre as clas-

ses representadas pela

arvore.

a em tarefas de regress

ao, a sa

ıda do sistema de aprendizado

e um valor

cont

ınuo. Exemplos: Altura de uma pessoa, variando numa faixa entre 1,00m

e 2,55m; O

angulo que um rob

o deve girar para seguir uma rota, variando

entre 0 e 360 graus.

Os sistemas de aprendizado normalmente utilizam uma base de exemplos

para realizar a etapa de treinamento. Nessa etapa, os exemplos s

ao apresen-

tados ao sistema de aprendizado para que ele formule sua hip

otese sobre a

func¸

ao alvo a ser aprendida. Esses exemplos geralmente s

ao representados

na forma de tabelas atributo-valor. Um exemplo de uma tabela atributo-valor

para a tarefa de classiﬁcac¸

ao bin

aria est

a na Tabela 2.1. Os atributos (Qua-

lidade, Entrega, Prec¸o, Pagamento e Garantia) de cada exemplo representam

as condic¸

oes de compra de um produto analisadas por um cliente. A

ultima

coluna, o r

otulo, representa a decis

ao tomada pelo cliente. Nesse caso, o ob-

jetivo do sistema

e prever se o cliente ir

a ou n

ao comprar um produto, dadas

determinadas condic¸

oes.

Exemplo Qualidade Entrega Prec¸ o Pagamento Garantia Comprar

1 Alta Imediata Alto A vista 1 ano Sim

2 Baixa Imediata Alto Parcelado 6 meses N

3 Alta 30 dias Alto Parcelado 1 ano N

4 M

edia Imediata Alto A vista 2 anos Sim

5 M

edia 30 dias Baixo Parcelado 1 ano N

6 Baixa Imediata Baixo A vista 1 ano Sim

7 Alta 30 dias Baixo Parcelado 2 anos Sim

8 M

edia 30 dias Baixo Parcelado 1 ano N

9 Baixa 30 dias Baixo A vista 6 meses N

Tabela 2.1: Tabela atributo valor com exemplos para classiﬁcac¸

ao.

Um exemplo de uma tabela atributo-valor para a tarefa de regress

ao est

a na

Tabela 2.2. O atributo

Angulo

e a entrada e o r

otulo Seno

e a sa

ıda da func¸

30 Cap

ıtulo 2

Seno(

Angulo). Nesse caso, o objetivo do sistema de aprendizado

e induzir uma

func¸

ao que aproxima a func¸

ao Seno.

Exemplo

Angulo Seno

1 0 0

2 30 0,5

3 60 0,86603

4 90 1

5 120 0,86603

6 150 0,5

7 180 0

8 210 -0,5

9 240 -0,86603

10 270 -1

11 300 -0,86603

12 330 -0,5

13 360 0

Tabela 2.2: Tabela atributo valor com exemplos para regress

ao.

2.1.2 Aprendizado N

ao-Supervisionado

No aprendizado n

ao-supervisionado, os exemplos de treinamento n

ao s

ao ro-

tulados, ou seja, a func¸

ao a ser aprendida n

e deﬁnida explicitamente. Ao

inv

es disso, o sistema de aprendizado deve descobrir padr

oes nos dados que

permitam agrupar os exemplos apresentados. O n

umero de grupos formado

pode ser deﬁnido pelo usu

ario do sistema de aprendizado, ou o pr

oprio sis-

tema pode tentar descobrir quantos grupos devem ser formados. Essa tarefa,

o agrupamento,

e mais conhecida na comunidade por seu nome em ingl

es:

clustering.

O agrupamento pode ser utilizado em bioinform

atica, por exemplo, para

agrupar genes que tenham func¸

ao semelhante, facilitando a descoberta da

func¸

ao de novos genes.

No aprendizado n

ao-supervisionado tamb

em s

ao usadas tabelas atributo-

valor para a fase de treinamento. A Tabela 2.3 apresenta um exemplo de

tabela atributo valor para o aprendizado n

ao-supervisionado. Essa tabela foi

baseada no conjunto de dados

Iris, do Reposit

orio de AM da UCI (Blake and

Merz, 1998). As entradas representam os valores de 4 atributos: comprimento

da s

epala, largura da s

epala, comprimento da p

etala e largura da p

etala. To-

dos os valores est

ao em formato cont

ınuo (ponto ﬂutuante) com uma casa

decimal. Os exemplos est

ao distribu

ıdos em 3 grupos de ﬂores:

Iris setosa,

Aprendizado de M

aquina 31

Iris versicolor e

Iris virginica. Por

em, como pode ser observado, n

ao h

a um

otulo na tabela para indicar o tipo de ﬂor.

Exemplo Comp. S

epala Larg. S

epala Comp. P

etala Larg. P

etala

1 5.1 3.5 1.4 0.2

2 4.9 3.0 1.4 0.2

3 4.7 3.2 1.3 0.2

4 5.0 3.6 1.4 0.2

5 7.0 3.2 4.7 1.4

6 6.4 3.2 4.5 1.5

7 6.9 3.1 4.9 1.5

8 5.5 2.3 4.0 1.3

9 6.3 3.3 6.0 2.5

10 5.8 2.7 5.1 1.9

11 7.1 3.0 5.9 2.1

12 6.3 2.9 5.6 1.8

Tabela 2.3: Tabela atributo valor com exemplos para agrupamento.

2.1.3 Aprendizado por Reforc¸ o

O aprendizado por reforc¸o pode ser considerado como um caso especial do

aprendizado supervisionado. A diferenc¸a entre eles reside no fato de que, no

aprendizado por reforc¸o, n

e informado ao sistema de AM a resposta correta

para os padr

oes de entrada, apenas lhe

e informado se uma determinada

resposta

e satisfat

oria ou n

ao.

Durante o treinamento, a cada ac¸

ao que leva a estados satisfat

orios, o

sistema de AM reforc¸a a tend

encia do sistema em realizar a ac¸

ao em quest

ao.

O contr

ario ocorre com ac¸

oes que n

ao levem a estados satisfat

orios, ou seja,

a tend

encia do sistema em realizar estas ac¸

oes

e enfraquecida (Braga et al.,

2000).

Esta Tese n

ao entra em detalhes sobre o aprendizado por reforc¸o e o apren-

dizado n

ao-supervisionado pois esses temas est

ao fora do escopo deste traba-

lho.

2.2 Aprendizado de M

aquina Simb

olico

Como dito anteriormente, as t

ecnicas de AM simb

olico s

ao aquelas em que o

conhecimento adquirido pelo sistema de aprendizado

e representado em uma

forma de f

acil compreens

ao por seres humanos. Nessa sec¸

ao ser

ao apresenta-

dos duas das mais conhecidas t

ecnicas de AM simb

olico:

Arvores de Decis

e Regras de Decis

ao.

32 Cap

ıtulo 2

2.2.1

Arvores de Decis

ao s

ao utilizadas para a tarefa de classiﬁcac¸

ao de padr

oes

(aprendizado supervisionado). Uma

Arvore de Decis

e uma estrutura de

dados em que cada n

o intermedi

ario representa um teste com um ou mais

atributos e cada n

o folha representa uma decis

ao. O resultado do teste em um

o deﬁne por qual ﬁlho deste n

o o processo de decis

ao deve continuar. Para

decidir a classe de um determinado padr

ao, comec¸a-se pela raiz da

arvore e

segue-se efetuando testes at

e que se chegue a um n

o folha. Um exemplo de

uma

arvore de decis

ao pode ser visto na Figura 2.1. Essa ﬁgura mostra uma

arvore de decis

ao para classiﬁcar tipos de ve

ıculos.

Figura 2.1:

Arvore de Decis

ao.

Para obter uma

arvore de decis

ao para classiﬁcar padr

oes a partir de um

certo conjunto de exemplos,

e realizado um processo chamado induc¸

ao de

arvores de decis

ao. Existem diversos algoritmos para realizar a induc¸

ao de

arvores de decis

ao. Um dos mais conhecidos

e o algoritmo C4.5 (Quinlan,

1988).

Assim como o C4.5, a maioria dos algoritmos para induc¸

ao de

arvores de

decis

ao s

ao variac¸

oes de um algoritmo guloso (greedy) b

asico, que faz uma

busca top-down no espac¸o de poss

ıveis

arvores de decis

ao (Mitchel, 1997).

Esse algoritmo b

asico comec¸a escolhendo qual atributo ser

a testado na raiz

arvore. Para isso, todos os atributos s

ao avaliados estatisticamente para

determinar qu

ao bem cada atributo, individualmente, classiﬁca os exemplos

de treinamento. O melhor

e selecionado e utilizado como teste na raiz da

arvore. N

os ﬁlhos s

ao criados para cada poss

ıvel valor deste atributo. Os

exemplos de treinamento s

ao ent

ao divididos entre os n

os ﬁlhos de acordo

com o resultado do teste do n

o raiz. O processo

e ent

ao repetido para cada n

ﬁlho, utilizando os exemplos a eles designados. Um n

o folha

e criado quando

Aprendizado de M

aquina 33

apenas exemplos de uma

unica classe s

ao designados a um n

o ﬁlho. A classe

desses exemplos

e atribu

ıda a esse n

o folha e o processo n

e repetido para

esse n

2.2.2 Regras de Decis

Um conjunto de regras de decis

e uma outra forma de representar o co-

nhecimento adquirido atrav

es do treinamento de um sistema de aprendizado

simb

olico.

Elas podem ser obtidas diretamente do conjunto de exemplos, ou podem

ser geradas a partir de uma

arvore de decis

ao. No

ultimo caso, cada caminho

que parte do n

o raiz da

arvore de decis

ao e alcanc¸a um n

o folha corresponde a

uma regra. O algoritmo C4.5rules (Quinlan, 1988) emprega essa abordagem e,

em disso, ele generaliza as regras apagando condic¸

oes irrelevantes que n

afetam a conclus

ao. J

a o algoritmo CN2 (Clark and Niblett, 1989a)

e um exem-

plo de algoritmo que induz regras diretamente dos exemplos de treinamento.

Regras de decis

ao podem ser divididas em dois tipos: regras ordenadas e

regras n

ao ordenadas. A seguir ser

ao discutidos esses dois tipos de regras.

Regras Ordenadas

Nas regras ordenadas, a ordem das regras

e importante para a decis

ao da

classe de um exemplo por elas classiﬁcado. Comec¸a-se confrontando o exem-

plo com a primeira regra e se as condic¸

oes da regra n

ao forem satisfeitas pelo

exemplo, segue-se confrontando o exemplo com as outras regras, em ordem,

e que as condic¸

oes de uma das regras do conjunto sejam satisfeitas pelo

exemplo, ou acabem as regras induzidas. Nesse caso, a regra padr

ao, normal-

mente associada

a classe majorit

aria

e utilizada para classiﬁcar o exemplo.

Caso as condic¸

oes de alguma regra sejam satisfeitas, o processo p

ara e o

exemplo

e classiﬁcado segundo a classe atribu

ıda

a conclus

ao da regra.

Para induzir um conjunto de regras ordenadas a partir dos exemplos de

treinamento, costuma-se utilizar a seguinte abordagem. A cada iterac¸

ao,

busca-se por um conjunto de condic¸

oes que cubram positivamente muitos

exemplos do conjunto de treinamento e cubram negativamente poucos ou ne-

nhum exemplo. Cobrir positivamente um exemplo signiﬁca que as condic¸

oes

da regra s

ao satisfeitas pelo exemplo e que a classe do exemplo

e a mesma da

conclus

ao da regra. Cobrir negativamente signiﬁca que apesar de satisfeitas

as condic¸

oes da regra, a classe do exemplo

e diferente da classe atribu

ıda

conclus

ao da regra. Ao encontrar tal conjunto de condic¸

oes, a regra gerada

adicionada a uma lista de regras e todos os exemplos do conjunto de treina-

Classe que possui o maior n

umero de exemplos no conjunto de treinamento.

34 Cap

ıtulo 2

mento cobertos por essa regra s

ao removidos, tanto os cobertos positivamente

quanto os negativamente. O processo

e repetido com os exemplos restantes,

e que nenhum novo conjunto de condic¸

oes possa ser encontrado ou n

existam mais exemplos a serem cobertos.

Para facilitar a compreens

ao desse processo, ser

a utilizado um exemplo

adaptado de (Milar

e, 2003). A Tabela 2.4 apresenta um conjunto de exem-

plos de treinamento em que cada linha

e um exemplo representando um de-

terminado dia. A classe de cada exemplo pode ser viajar ou ﬁcar em casa,

dependendo das condic¸

oes meteorol

ogicas daquele dia, representadas pelos

atributos do exemplo.

Exemplo Tempo Temperatura Umidade Vento Viajar?

1 ensolarado 25 72 sim viajar

2 ensolarado 28 91 sim ﬁcar

3 ensolarado 22 70 n

ao viajar

4 ensolarado 23 95 n

ao ﬁcar

5 ensolarado 30 85 n

ao ﬁcar

6 nublado 23 90 sim viajar

7 nublado 29 78 n

ao viajar

8 nublado 19 65 sim ﬁcar

9 nublado 26 75 n

ao viajar

10 nublado 20 87 sim viajar

11 chuvoso 22 95 n

ao viajar

12 chuvoso 19 70 sim ﬁcar

13 chuvoso 23 80 sim ﬁcar

14 chuvoso 25 81 n

ao viajar

15 chuvoso 21 80 n

ao viajar

Tabela 2.4: Conjunto de dados Viagem.

Na Tabela 2.5

e apresentado um conjunto de regras ordenadas induzido a

partir desse conjunto de exemplos. Tamb

em s

ao apresentados nessa tabela,

ao lado de cada regra, os exemplos positivamente cobertos (PC) e os exemplos

negativamente cobertos (NC).

Regras N

ao Ordenadas

A induc¸

ao de regras n

ao ordenadas comec¸a com a escolha de uma classe.

Em seguida, todas as regras para essa classe s

ao induzidas e esse processo

repetido para todas as outras classes presentes no conjunto de dados.

Para cada classe, comec¸a-se com o conjunto de dados completo e depois

da induc¸

ao de cada regra, removem-se os conjuntos por ela cobertos positiva-

mente. Quando n

ao for mais poss

ıvel encontrar uma regra que cubra exem-

Aprendizado de M

aquina 35

Regra Condic¸

oes e Conclus

oes PC NC

R1 se umidade < 83 ent

ao classe = viajar 1, 3, 7, 8, 12, 13

9, 14, 15

R2 sen

ao se temperatura ≥ 23 ent

ao classe = ﬁcar 2, 4, 5 6

R3 sen

ao se tempo = chuvoso ent

ao classe = viajar 11

R4 sen

ao classe padr

ao = viajar 10

Tabela 2.5: Conjunto de regras ordenadas para o conjunto de dados Viagem.

plos dessa classe, ou quando n

ao h

a mais exemplos dessa mesma classe, o

processo de induc¸

ao de regras para a pr

oxima classe

e iniciado.

O processo de induc¸

ao de regras termina quando as regras para todas as

classes do conjunto de dados tenham sido induzidas e

e criada a regra padr

ao,

que assume a classe majorit

aria e s

e disparada caso nenhuma das outras

regras sejam disparadas.

Um exemplo de conjunto de regras de decis

ao n

ao ordenadas para o mesmo

conjunto de dados da Tabela 2.4

e apresentado na Tabela 2.6, juntamente

com os exemplos positivamente cobertos (PC) e negativamente cobertos (NC)

de cada regra.

Regra Condic¸

oes e Conclus

oes PC NC

R1 se tempo = nublado ent

ao classe = viajar 6, 7, 9, 10 8

R2 se (tempo = chuvoso) ∧ (vento = n

ao) ent

ao 11, 14, 15

classe = viajar

R3 se (tempo = ensolarado) ∧ (umidade > 77) ent

ao 2, 4, 5

classe = ﬁcar

R4 se (tempo = chuvoso) ∧ (vento = sim) ent

ao 12, 13

classe = ﬁcar

R5 se (tempo = nublado) ∧ (temperatura < 20) ent

ao 8

classe = ﬁcar

R6 sen

ao classe padr

ao = viajar

Tabela 2.6: Conjunto de regras n

ao ordenadas para o conjunto de dados Via-

gem.

Uma vez que as regras n

ao s

ao ordenadas, para utilizar esse conjunto de

regras para predizer a classe de um novo exemplo, deve-se veriﬁcar todas elas

e determinar quais regras cobrem o novo exemplo. Por

em, como o exemplo

pode disparar regras que possuem conclus

oes diferentes, ou seja, classiﬁcam

o exemplo em classes diferentes, um m

etodo para realizar o desempate en-

tre as regras

e necess

ario. Pode-se para isso, adicionar um

ındice do poder

36 Cap

ıtulo 2

preditivo

a cada regra.

Uma forma de criar esse

ındice consiste em contar o n

umero de exemplos

que a regra cobre positivamente e negativamente. Para isso, pode-se adicionar

a cada regra, uma lista [η

, η

, ..., η

N cl

]. Com η

sendo o total de exemplos

da classe C

cobertos pela regra. Para exempliﬁcar essa abordagem, foi adici-

onado ao conjunto de regras n

ao ordenadas anteriormente induzido uma lista

com as freq

encias de cobertura de cada regra para cada classe. Isso pode ser

visto na Tabela 2.7.

Regra Condic¸

oes e Conclus

oes [η

viajar

, η

ficar

]

R1 se tempo = nublado ent

ao classe = viajar [4,1]

R2 se (tempo = chuvoso) ∧ (vento = n

ao) ent

ao [3,0]

classe = viajar

R3 se (tempo = ensolarado) ∧ (umidade > 77) ent

ao [0,3]

classe = ﬁcar

R4 se (tempo = chuvoso) ∧ (vento = sim) ent

ao [0,2]

classe = ﬁcar

R5 se (tempo = nublado) ∧ (temperatura < 20) ent

ao [0,1]

classe = ﬁcar

R6 sen

ao classe padr

ao = viajar [9,6]

Tabela 2.7: Regras n

ao ordenadas com o

ındice do poder de predic¸

ao das

regras.

Se um novo exemplo disparar as regras R1 e R4, a cobertura total das duas

regras ser

a [4,3], uma vez que a regra R1 cobre 4 exemplos da classe viajar e

1 da classe ﬁcar e a regra R4 n

ao cobre nenhum da classe viajar e 2 da classe

ﬁcar. Nesse caso, a sa

ıda do sistema para esse exemplo ser

a a classiﬁcac¸

viajar.

2.3 Aprendizado de M

aquina N

ao-Simb

olico

Nessa sec¸

ao ser

ao apresentadas algumas t

ecnicas de AM n

ao-simb

olico, que,

como j

a citado, representam o conhecimento adquirido em uma forma de

dif

ıcil compreens

ao por seres humanos. Particularmente, ser

ao apresentadas

as RNAs e os LMCs, que s

ao de grande interesse para esse trabalho.

2.3.1 Redes Neurais Artiﬁciais

Redes Neurais Artiﬁciais s

ao modelos computacionais distribu

ıdos que t

sido utilizados com frequ

encia em problemas de reconhecimento de padr

oes.

Tendo como fonte de inspirac¸

ao o c

erebro humano, foram criados v

arios mo-

delos de Redes Neurais Artiﬁciais (RNAs) (Braga et al., 2000). O processa-

Aprendizado de M

aquina 37

mento em RNAs se d

a por meio da combinac¸

ao em rede de diversos n

os sim-

ples que realizam processamentos independentes, inspirados nos neur

onios

de sistemas nervosos biol

ogicos. Desse modo, paralelismo e robustez s

ao ca-

racter

ısticas inerentes

as RNAs.

O mais famoso e utilizado modelo de RNA

e o Multi Layer Perceptron (MLP),

ou Perceptron de m

ultiplas camadas. Utilizando o algoritmo de treinamento

backpropagation, ele

e capaz de aproximar qualquer tipo de func¸

ao multi-

vari

avel, incluindo problemas n

ao linearmente separ

aveis, dados um conjunto

de exemplos e uma arquitetura de rede adequados. O aprendizado do back-

propagation

e do tipo supervisionado (Rumelhart et al., 1986).

Outro modelo importante

e o modelo Self Organizing Maps (SOM), tamb

conhecido como Rede de Kohonen. As redes SOM s

ao capazes de realizar a ta-

refa de agrupamento (aprendizado n

ao-supervisionado). Essa rede apresenta

uma forte inspirac¸

ao neuroﬁsiol

ogica por ser baseada no mapa topol

ogico pre-

sente no c

ortex cerebral (Braga et al., 2000).

A seguir, com o objetivo de exempliﬁcar o conceito de RNAs, os dois mode-

los j

a citados ser

ao descritos. Por

em, existem dezenas de outros modelos na

literatura, como: redes sem pesos, redes recorrentes, redes de Hopﬁeld, redes

RBF, entre outros (Haykin, 1998).

Multi Layer Perceptron / Backpropagation

O modelo MLP

e uma extens

ao do modelo Perceptron de uma camada. A

grande vantagem do modelo MLP sobre o Perceptron de uma camada

e que ele

pode resolver problemas n

ao linearmente separ

aveis.

Uma rede MLP com uma camada intermedi

aria pode aproximar qualquer

func¸

ao cont

ınua, enquanto uma rede com duas ou mais camadas intermedi-

arias pode aproximar qualquer func¸

ao matem

atica (Cybenko, 1988).

Antes de entrar nos detalhes da rede MLP, ser

a apresentado em linhas ge-

rais o modelo Perceptron. O modelo de neur

onio utilizado na rede Perceptron

cont

em diversas entradas que s

ao ponderadas por pesos. O aprendizado no

Perceptron de uma camada

e dado por meio da adaptac¸

ao dos pesos de suas

entradas. A Figura 2.2 mostra um modelo da rede Perceptron.

A seguir ser

a descrito o processo de aprendizado da rede Perceptron. Pri-

meiramente, iniciam-se os pesos com valores aleat

orios. Ent

ao, apresenta-se

cada exemplo do conjunto de treinamento

a rede e alteram-se os pesos sempre

que a rede erra na classiﬁcac¸

ao de um exemplo. Esse processo

e repetido at

que a rede n

ao cometa mais erros de classiﬁcac¸

ao ou um determinado n

umero

de ciclos de aprendizado seja conclu

ıdo. Para alterar os pesos,

e utilizada a

seguinte express

ao de ajuste de pesos:

38 Cap

ıtulo 2

Figura 2.2: Rede Perceptron.

←− ω

+ ∆ω

(2.1)

em que

∆ω

= η(d − y)x

(2.2)

O s

ımbolo d representa a sa

ıda esperada para o exemplo apresentado, y

a sa

ıda gerada pela rede, e η

e a taxa de aprendizado. Essa taxa

e utilizada

para deﬁnir os efeitos da alterac¸

ao dos pesos em cada passo do aprendizado e

e tipicamente um valor baixo como 0.1.

A rede MLP pode ser vista como um conjunto de v

arias redes Perceptron

simples. A rede

e disposta em camadas interconectadas. A sa

ıda dos n

os de

uma camada

e geralmente conectada

a entrada de todos os n

os da pr

oxima

camada. Um exemplo de uma t

ıpica rede MLP pode ser visto na Figura 2.3.

O problema dessa rede est

a em como corrigir os pesos dos n

os das cama-

das intermedi

arias. Como determinar o erro nos n

os intermedi

arios? Esse

problema foi resolvido pelo algoritmo de treinamento backpropagation. Nesse

algoritmo, o treinamento ocorre em duas fases, forward e backward. Na fase

forward, um exemplo de treinamento

e apresentado

a rede na camada de en-

trada. Os valores da entrada s

ao propagados pela rede, passando por seus

pesos e func¸

oes de ativac¸

ao at

e chegar

a camada de sa

ıda, onde a sa

ıda da

rede

e deﬁnida. Na fase backward, a sa

ıda desejada e a sa

ıda da rede s

ao com-

paradas para deﬁnir o erro na camada de sa

ıda, que

e utilizado para ajustar

os pesos dessa camada. Este erro

e ent

ao propagado para os n

os das camada

anteriores, ponderado pelos pesos das conex

oes entre eles e os n

os da camada

atual. Atrav

es desse erro ponderado, pode-se calcular o ajuste dos pesos para

as camadas intermedi

arias. O Algoritmo 1 descreve o de treinamento backpro-

Aprendizado de M

aquina 39

Figura 2.3: Rede Neural MLP.

pagation em pseudoc

odigo.

Self Organizing Maps - SOM

A rede SOM realiza um mapeamento dos padr

oes de entrada, que podem pos-

suir uma alta dimensionalidade, para um espac¸o de menor dimens

ao, tipi-

camente 2D. Nesse processo, procura-se manter as caracter

ısticas espaciais

do conjunto de exemplos. Ou seja, exemplos que est

ao pr

oximos no espac¸o

original, ser

ao atribu

ıdos a neur

onios pr

oximos topologicamente no mapa de

caracter

ısticas SOM. Por causa dessa caracter

ıstica, as redes SOM s

ao muito

usadas para visualizac¸

ao.

A arquitetura da rede SOM consiste em um reticulado de neur

onios. Cada

neur

onio tem conex

oes laterais com seus vizinhos. A forma mais comum de

uma rede SOM

e a de uma grade bidimensional, apesar de existirem redes com

3 ou mais dimens

oes. Essa arquitetura pode ser visualisada na Figura 2.4.

Cada n

o da rede SOM possui um n

umero de pesos igual ao n

umero de atri-

butos do conjunto de treinamento utilizado. A rede SOM realiza o aprendizado

competitivo, ou seja, seus n

os competem entre si para se aperfeic¸oar. A cada

exemplo de treinamento apresentado, deﬁne-se qual n

o possui o conjunto de

pesos mais pr

oximo ao conjunto de atributos do exemplo atual segundo uma

func¸

ao de dist

ancia, normalmente a dist

ancia euclidiana. Esse n

e chamado

de n

o vencedor. O vencedor e seus vizinhos (deﬁnidos por uma regi

ao de

vizinhanc¸a) s

ao ent

ao atualizados de forma a ﬁcaram um pouco mais pareci-

dos com o exemplo atual (segundo a taxa de aprendizagem). A vizinhanc¸a e a

40 Cap

ıtulo 2

Algoritmo 1: Algoritmo backpropagation

Inicializar os pesos da rede e os par

ametros do algoritmo.1

repita2

para cada exemplo de treinamento X fac¸ a3

A entrada

e apresentada

a primeira camada da rede (C0).4

para cada camada Ci a partir da camada C0 fac¸a5

os o c

alculo dos sinais de sa

ıda dos n

os da camada Ci, estes6

servem como entrada para a deﬁnic¸

ao das sa

ıdas dos n

os da

camada Ci+1.

ﬁm7

As sa

ıdas produzidas pelos n

os da

ultima camada s

ao comparadas8

as sa

ıdas desejadas.

para cada camada Ci a partir da

ultima, at

e a camada C0 fac¸ a9

Os n

os da camada atual (Ci) ajustam seus pesos de forma a10

reduzir seus erros.

O erro dos n

os das camadas Ci-1 s

ao calculados utilizando os11

erros dos n

os da camada Ci a eles conectados, ponderados

pelos pesos das conex

oes entre eles.

ﬁm12

ﬁm13

e alcanc¸ar um erro m

ınimo ou o n

umero m

aximo de ciclos ;14

taxa de aprendizagem s

ao deﬁnidos com valores altos no in

ıcio do treinamento.

Normalmente, a vizinhanc¸a inicial engloba toda a rede e vai diminuindo at

incluir somente os n

os com ligac¸

oes diretas com o n

o vencedor. O Algoritmo 2

apresenta o treinamento da rede SOM em pseudoc

odigo.

Algoritmo 2: Algoritmo de treinamento da rede SOM

Inicializar os par

ametros do algoritmo.1

Inicializar os pesos aleatoriamente com valores pequenos.2

repita3

para cada exemplo de treinamento fac¸a4

Deﬁnir o n

o vencedor utilizando a func¸

ao de dist

ancia.5

Atualizar os pesos desse n

o e de seus vizinhos.6

se o n

umero do ciclo for m

ultiplo de N ent

ao7

Reduzir a taxa de aprendizado.8

Reduzir a

area de vizinhanc¸a.9

ﬁm10

ﬁm11

e algum crit

erio de parada ;12

2.3.2 Classiﬁcadores de Margens Largas

Classiﬁcadores de Margens Largas (Large Margin Classiﬁers - LMCs) s

ao aque-

les que implicitamente ou explicitamente utilizam o conceito de maximizac¸

Aprendizado de M

aquina 41

Figura 2.4: Rede Neural SOM.

de margens para a construc¸

ao de suas fronteiras de decis

ao. Margem aqui

deﬁnida como a dist

ancia entre a fronteira de decis

ao utilizada pelo classiﬁ-

cador e os exemplos a ele apresentados. Fundamentados na TAE (Teoria do

Aprendizado Estat

ıstico) (Lorena and de Carvalho, 2003), esses classiﬁcadores

em provado possuir um grande poder de generalizac¸

ao.

Para ilustrar esse conceito, observe o conjunto de dados linearmente se-

par

avel da Figura 2.5.

Figura 2.5: Um conjunto de dados linearmente separ

avel.

Um conjunto linearmente separ

avel

e aquele no qual

e poss

ıvel separar

todos os exemplos de diferentes classes por meio de um hiperplano. A func¸

linear que deﬁne esse hiperplano pode ser considerada um classiﬁcador linear.

A seguinte equac¸

ao representa um poss

ıvel classiﬁcador linear:

f(x) = sgn(w · x + b) (2.3)

na qual w · x

e o produto escalar entre os vetores w e x, w

e o vetor normal

ao hiperplano, b

e o bias e sgn()

e a func¸

ao sinal.

A tarefa de aprendizado ent

ao se resume a deﬁnir os valores de w e b apro-

42 Cap

ıtulo 2

priados para os dados do conjunto de treinamento. Por

em, como pode ser

visto na Figura 2.6, v

arias hip

oteses podem ser induzidas para o hiperplano

separador. Uma boa heur

ıstica ent

ao seria escolher a hip

otese que apresenta

a m

axima margem de separac¸

ao entre os exemplos e o hiperplano separador.

A Figura 2.6 mostra duas hip

oteses para o hiperplano separador, representa-

das pelas linhas cont

ınuas. As linhas tracejadas representam as margens de

separac¸

ao. A hip

otese a) n

ao leva em considerac¸

ao o conceito de maximizac¸

de margens, enquanto a hip

otese b) utiliza a um hiperplano que maximiza a

margem de separac¸

ao.

Figura 2.6: Duas formas de separar o mesmo conjunto de dados. O hiperplano

de a) n

ao maximiza as margens de separac¸

ao enquanto do de b) determina

uma grande margem de separac¸

ao entre a fronteira de decis

ao e os exemplos.

Duas propriedades dos Classiﬁcadores de Margens Largas justiﬁcam a

constatac¸

ao emp

ırica de que os LMCs induzem hip

oteses mais conﬁ

aveis.

Uma

e a robustez em relac¸

ao aos padr

oes, pois dado um exemplo x longe

da borda de decis

ao, ocasionais perturbac¸

oes em x n

ao levar

ao a classiﬁca-

c¸

oes incorretas. A outra

e a robustez em relac¸

ao aos par

ametros do modelo,

pois se a margem do classiﬁcador

e grande, uma pequena perturbac¸

ao nos

par

ametros n

ao afeta a classiﬁcac¸

ao dos dados (Smola et al., 1999).

em disso, a Teoria do Aprendizado Estat

ıstico (TAE) prov

e limites no erro

de um classiﬁcador linear para exemplos novos com base na margem. Isso

indica que a maximizac¸

ao de margens leva a bons resultados em termos de

generalizac¸

ao. O relat

orio t

ecnico de Lorena and de Carvalho (2003) sobre

Classiﬁcadores de Margens Largas descreve em detalhes a TAE.

As SVMs s

ao LMCs muito conhecidos e utilizados. A seguir ser

ao descritas

sucintamente principais caracter

ısticas das SVMs.

Dados os exemplos de treinamento X

, y

, i = 1...N, y

∈ −1, 1, X

∈ R

em que

e o r

otulo da classe, uma SVM primeiramente mapeia os dados para o espac¸o

de caracter

ısticas H, usando um mapeamento Φ,

Aprendizado de M

aquina 43

Φ : R

→ H (2.4)

O mapeamento Φ

e implementado por uma func¸

ao kernel K que satisfaz

as condic¸

oes de Mercer (Cristianini and Shawe-Taylor, 2000) de modo que

K(X

, X

) = Φ(X

) · Φ(X

). Ent

ao, no espac¸o de caracter

ısticas H de alta di-

mens

ao,

e encontrado o hiperplano de separac¸

otimo por meio da maximi-

zac¸

ao da margem e limitac¸

ao do n

umero de erros de treinamento. A func¸

ao de

decis

ao pode ser dada por:

f(X) = sgn(W · Φ(X) − b)

f(X) = sgn(



i=1

Φ(X

) · Φ(X) − b) (2.5)

f(X) = sgn(



i=1

K(X

, X) − b)

Se α

e diferente de 0, o exemplo correspondente x

e um vetor suporte.

Para treinar uma SVM

e necess

ario descobrir α

, i = 1 at

e N. Isso pode ser feito

minimizando a seguinte func¸

ao de custo quadr

atica:

maximize L

(α) =



i=1

−



i=1



j=1

K(X

, X

)

com 0 ≤ α

≤ Ci = 1...N (2.6)



i=1

= 0

em que C

e uma par

ametro escolhido pelo usu

ario. Valores altos de C corres-

pondem a penalidades mais altas alocadas aos erros de treinamento. Uma vez

que K

e semi-positivo deﬁnido e as restric¸

oes deﬁnem um conjunto convexo,

a otimizac¸

ao anterior reduz-se para uma programac¸

ao quadr

atica convexa.

2.4 Algoritmos Gen

eticos

Os Algoritmos Gen

eticos

ao programas evolutivos baseados na teoria de

selec¸

ao natural e na hereditariedade. Eles baseiam-se no pressuposto de que,

em uma dada populac¸

ao, indiv

ıduos com boas caracter

ısticas gen

eticas t

maiores chances de sobreviv

encia e de produzirem indiv

ıduos cada vez mais

aptos. Como resultado, os indiv

ıduos menos aptos tender

ao a desaparecer.

Essa sec¸

e baseada no Cap

ıtulo 9 do livro Sistemas Inteligentes (Rezende, 2002)

44 Cap

ıtulo 2

Assim, Algoritmos Gen

eticos favorecem a combinac¸

ao dos indiv

ıduos mais

aptos, ou seja, os candidatos mais promissores para a soluc¸

ao de um dado

problema.

Quando Algoritmos Gen

eticos s

ao empregados para resoluc¸

ao de proble-

mas do mundo real, cada indiv

ıduo da populac¸

ao, denominado cromossomo,

normalmente corresponde a uma poss

ıvel soluc¸

ao para o problema. Um me-

canismo de reproduc¸

ao, baseado em processo evolutivo,

e aplicado sobre a

populac¸

ao atual com o objetivo de explorar o espac¸o de busca e encontrar

melhores soluc¸

oes para o problema.

Toda tarefa de busca ou otimizac¸

ao possui v

arios componentes, entre eles:

o espac¸o de busca, onde s

ao consideradas todas as possibilidades de soluc¸

de um determinado problema, e a func¸

ao de avaliac¸

ao (ou func¸

ao de custo),

que

e uma maneira de avaliar os elementos do espac¸o de busca. Existem

diversos m

etodos de busca e func¸

oes de avaliac¸

ao (Ginsberg, 1993).

As t

ecnicas de busca e otimizac¸

ao tradicionais iniciam seu processamento

com um

unico candidato que, iterativamente,

e manipulado utilizando al-

gumas heur

ısticas, normalmente est

aticas, diretamente associadas ao pro-

blema a ser solucionado. Geralmente, estes processos heur

ısticos n

ao s

algor

ıtmicos e sua simulac¸

ao em computadores pode ser muito complexa.

Apesar de estes m

etodos n

ao serem suﬁcientemente robustos, isto n

ao im-

plica que eles sejam in

uteis. Na pr

atica, eles s

ao amplamente utilizados, com

sucesso, em in

umeras aplicac¸

oes (Winston, 1992).

Por outro lado, as t

ecnicas de Computac¸

ao Evolutiva operam sobre uma

populac¸

ao de candidatos em paralelo. Assim, elas podem fazer a busca em di-

ferentes

areas do espac¸o de soluc¸

ao, alocando um n

umero de membros apro-

priado para a busca em v

arias regi

oes. Como resultado, tais t

ecnicas t

em uma

maior chance de atingir as

areas mais promissoras do espac¸o de busca. Os

Algoritmos Gen

eticos diferem dos m

etodos tradicionais de busca e otimizac¸

ao,

principalmente em quatro aspectos:

1. trabalham com uma codiﬁcac¸

ao do conjunto de par

ametros e n

ao com os

oprios par

ametros;

2. trabalham com uma populac¸

ao e n

ao com um

unico ponto;

3. utilizam informac¸

oes de custo ou recompensa e n

ao derivadas ou outro

conhecimento auxiliar e

4. utilizam regras de transic¸

ao probabil

ısticas e n

ao determin

ısticas.

Algoritmos Gen

eticos t

em se mostrado muito eﬁcientes para a busca de

soluc¸

oes

otimas, ou aproximadamente

otimas em uma grande variedade de

Aprendizado de M

aquina 45

problemas, pois n

ao imp

oem muitas das limitac¸

oes encontradas nos m

etodos

de busca tradicionais. Al

em de seguir uma estrat

egia de gerar e testar soluc¸

oes

muito elegante, por serem baseados na evoluc¸

ao biol

ogica, s

ao capazes de

identiﬁcar e explorar aspectos do ambiente onde o problema esta inserido e

convergir globalmente para soluc¸

oes

otimas, ou aproximadamente

otimas (Hol-

land, 1975).

“Quanto melhor um indiv

ıduo se adaptar ao seu meio ambiente, maior ser

sua chance de sobreviver e gerar descendentes”: este

e o conceito b

asico da

selec¸

ao natural (Darwin, 1859), mecanismo da evoluc¸

ao gen

etica biol

ogica. A

area biol

ogica mais proximamente ligada aos Algoritmos Gen

eticos

e a Gen

tica Populacional.

E interessante observar que pesquisadores e usu

arios referem-se a “Algo-

ritmos Gen

eticos” ou a “um Algoritmo Gen

etico” e n

ao “ao Algoritmo Gen

etico”,

pois Algoritmos Gen

eticos s

ao uma classe de procedimentos com um conjunto

de passos distintos e bem especiﬁcados, onde cada uma destes passos possui

muitas poss

ıveis variac¸

oes.

Antes de prosseguir com a an

alise das caracter

ısticas destes algoritmos,

alguns conceitos b

asicos s

ao necess

arios. Estes conceitos podem ser natu-

ralmente expostos explicando o funcionamento b

asico destes algoritmos. Ini-

cialmente,

e gerada uma populac¸

ao formada por um conjunto aleat

orio de

indiv

ıduos que podem ser vistos como poss

ıveis soluc¸

oes do problema.

Durante o processo evolutivo, esta populac¸

e avaliada: para cada in-

div

ıduo

e dada uma nota, ou

ındice, reﬂetindo sua habilidade de adaptac¸

a determinado ambiente. Uma porcentagem dos mais adaptados

e mantida,

enquanto os outros s

ao descartados (darwinismo). Os membros mantidos

pela selec¸

ao podem sofrer modiﬁcac¸

oes em suas caracter

ısticas fundamen-

tais atrav

es de mutac¸

oes e cruzamento (crossover) ou recombinac¸

ao gen

etica

gerando descendentes para a pr

oxima gerac¸

ao. Este processo, chamado de

reproduc¸

ao,

e repetido at

e que uma soluc¸

ao satisfat

oria seja encontrada.

Embora possam parecer simplistas do ponto de vista biol

ogico, estes algo-

ritmos s

ao suﬁcientemente complexos para fornecer mecanismos poderosos e

robustos de busca adaptativa (Goldberg, 1989).

2.4.1 Caracter

ısticas Gerais

Algoritmos Gen

eticos s

ao algoritmos de otimizac¸

ao global, baseados nos me-

canismos de selec¸

ao natural e da gen

etica. Eles empregam uma estrat

egia de

busca paralela e estruturada, embora aleat

oria, direcionada

a busca de pon-

tos de “alta aptid

ao”, ou seja, pontos nos quais a func¸

ao a ser minimizada (ou

maximizada) tem valores relativamente baixos (ou altos). Apesar de aleat

orios,

46 Cap

ıtulo 2

AGs n

ao s

ao buscas aleat

orias n

ao direcionadas, pois exploram informac¸

oes

hist

oricas para encontrar novos pontos de busca onde s

ao esperados melhores

desempenhos.

Isto

e feito atrav

es de processos iterativos, onde cada iterac¸

e chamada

de gerac¸

ao. Durante cada iterac¸

ao, os princ

ıpios de selec¸

ao e reproduc¸

ao aplicados a uma populac¸

ao de candidatos que pode variar, dependendo

da complexidade do problema e dos recursos computacionais dispon

ıveis.

Atrav

es da selec¸

ao, se determina quais indiv

ıduos conseguir

ao se reproduzir,

gerando um n

umero determinado de descendentes para a pr

oxima gerac¸

ao,

com uma probabilidade determinada pelo seu

ındice de aptid

ao. Em outras

palavras, os indiv

ıduos com maior adaptac¸

ao relativa t

em maiores chances de

se reproduzir.

Algoritmo 3: Algoritmo Gen

etico

t = 0;1

Gerar Populac¸

ao Inicial P (0);2

para cada indiv

ıduo i da populac¸

ao atual P (t) fac¸a3

Avaliar aptid

ao do indiv

ıduo i;4

ﬁm5

enquanto o crit

erio de parada n

ao for satisfeito fac¸a6

t = t + 1;7

Selecionar populac¸

ao P(t) a partir de P(t-1);8

Aplicar operadores de cruzamento sobre P(t);9

Aplicar operadores de mutac¸

ao sobre P(t);10

Avaliar P(t);11

ﬁm12

Durante esse processo, os melhores indiv

ıduos, assim como alguns dados

estat

ısticos, podem ser coletados e armazenados para avaliac¸

ao.

Esse ciclo

e geralmente repetido v

arias vezes at

e que um crit

erio de para te-

nha sido satisfeito. O Algoritmo 3 apresenta o funcionamento de um algoritmo

gen

etico t

ıpico em pseudo-c

odigo.

Os AGs, apesar de aparentemente simples, s

ao capazes de resolver pro-

blemas complexos de uma forma muito elegante. Al

em disso, eles n

ao s

limitados por suposic¸

oes sobre o espac¸o de busca, relativas a continuidade,

exist

encia de derivadas, etc. Buscas em problemas reais s

ao repletas de des-

continuidades, ru

ıdos e outros problemas. M

etodos que dependam fortemente

de restric¸

oes de continuidade e exist

encia de derivadas s

ao adequados apenas

para problemas em um dom

ınio limitado (Goldberg, 1989).

Aprendizado de M

aquina 47

2.4.2 Representac¸

O primeiro aspecto a ser considerado antes da utilizac¸

ao de AGs para a solu-

c¸

ao de um problema de busca ou otimizac¸

e a representac¸

ao deste problema

de maneira que os AGs possam trabalhar adequadamente sobre ele.

O AG processa populac¸

oes de indiv

ıduos ou cromossomos. O cromossomo

e uma estrutura de dados, geralmente vetores ou cadeias de valores bin

arios

(estrutura mais tradicional, por

em nem sempre a mais indicada), que repre-

senta uma poss

ıvel soluc¸

ao do problema a ser otimizado. Em geral, o cromos-

somo representa o conjunto de par

ametros da func¸

ao objetivo cuja resposta

ser

a maximizada ou minimizada. O conjunto de todas as conﬁgurac¸

oes que o

cromossomo pode assumir forma o seu espac¸o de busca. Se o cromossomo re-

presenta n par

ametros de uma func¸

ao, ent

ao o espac¸o de busca

e um espac¸o

com n dimens

oes. A maioria das representac¸

oes s

ao genot

ıpicas, utilizam

vetores de tamanho ﬁnito em um alfabeto tamb

em ﬁnito.

Tradicionalmente, o gen

otipo de um indiv

ıduo

e representado por um vetor

bin

ario, onde cada elemento de um vetor denota a presenc¸a (1) ou aus

encia

(0) de uma determinada caracter

ıstica. Os elementos podem ser combinados

formando as caracter

ısticas reais do indiv

ıduo, ou seja o seu fen

otipo . Te-

oricamente, esta representac¸

e independente do problema, pois uma vez

encontrada a representac¸

ao em vetores bin

arios, as operac¸

oes padr

ao podem

ser utilizadas, facilitando o seu emprego em diferentes classes de problemas

(Spears et al., 1993).

A representac¸

ao bin

aria

e historicamente importante, uma vez que foi uti-

lizado nos trabalhos pioneiros de (Holland, 1975). Esta representac¸

ao ainda

e a mais utilizada, por ser de f

acil utilizac¸

ao e manipulac¸

ao, al

em de ser sim-

ples de analisar teoricamente. Contudo, se um problema tem par

ametros

cont

ınuos e o usu

ario desejar trabalhar com uma maior precis

ao, provavel-

mente ele acabar

a utilizando longos cromossomos para representar soluc¸

oes,

utilizando, assim, uma grande quantidade de mem

oria. Tamb

em n

ao h

a uni-

formidade nos operadores (Ex.: se o valor real de um gene for codiﬁcado por

um vetor bin

ario, a mutac¸

ao nos primeiros valores bin

arios do gene afetar

mais a aptid

ao do cromossomo que a mutac¸

ao nos seus

ultimos valores).

A representac¸

ao do cromossomo usando n

umeros reais

e mais natural-

mente compreendida pelo ser humano do que aquela usando uma cadeia de

bits. Al

em disso, a representac¸

ao por valores reais requer menos mem

oria.

A utilizac¸

ao de representac¸

oes em n

ıveis de abstrac¸

ao mais altos tem sido

investigada. Como estas representac¸

oes s

ao mais fenot

ıpicas, facilitariam sua

utilizac¸

ao em determinados ambientes, onde essa transformac¸

ao “fen

otipo -

48 Cap

ıtulo 2

gen

otipo”

e muito complexa. Neste caso, precisam ser criados os operadores

espec

ıﬁcos para utilizar estas representac¸

oes.

2.4.3 Selec¸

O princ

ıpio b

asico do funcionamento dos AGs

e que um crit

erio de selec¸

vai fazer com que, depois de muitas gerac¸

oes, o conjunto inicial de indiv

ıduos

gere indiv

ıduos mais aptos. O Algoritmo Gen

etico comec¸a com uma populac¸

inicial de N cromossomos. Quando n

ao existe nenhum conhecimento pr

evio

sobre a regi

ao do espac¸o de busca onde se encontra a soluc¸

ao do problema,

os cromossomos s

ao gerados aleatoriamente. Se houver um conhecimento a

priori sobre a regi

ao em que est

a localizada a soluc¸

ao, ou seja, forem conheci-

das soluc¸

oes aceit

aveis que podem estar pr

oximas

a(s) soluc¸

ao(

oes)

otima(s),

os cromossomos iniciais podem ser deﬁnidos de forma determin

ıstica.

Para que o processo de selec¸

ao privilegie os indiv

ıduos mais aptos, a cada

cromossomo da populac¸

e atribu

ıdo um valor dado por uma func¸

ao f

apt

denominada func¸

ao de aptid

ao. Esta func¸

ao recebe como entrada os valores

do gene do cromossomo e fornece como resultado a sua aptid

ao. A aptid

pode ser vista como uma nota que mede o qu

ao boa

e a soluc¸

ao codiﬁcada

por um indiv

ıduo. A aptid

e baseada no valor da func¸

ao objetivo, que

espec

ıﬁca para cada problema.

Para alguns m

etodos de selec¸

ao,

e desej

avel que o valor de aptid

ao de cada

indiv

ıduo seja menor que 1 e que a soma de todos os valores de aptid

ao seja

igual 1 (f

apt

< 1 e



apt

) = 1). Para isso, para cada indiv

ıduo

e calculada

a aptid

ao relativa (f

rel

). A aptid

ao relativa para um dado indiv

ıduo

e obtida

dividindo o valor de sua aptid

ao pela soma dos valores de aptid

ao de todos os

indiv

ıduos da populac¸

ao.

Uma func¸

ao objetivo (tamb

em chamada de func¸

ao de avaliac¸

ao ou func¸

de custo)

e geralmente uma express

ao matem

atica que mede o quanto uma

soluc¸

ao esta pr

oxima ou distante da soluc¸

ao desejada (satisfaz o objetivo do

problema). Muitas vezes ela inclui tamb

em restric¸

oes que devem ser satis-

feitas pela soluc¸

ao. Alguns problemas de otimizac¸

ao procuram maximizar o

valor da func¸

ao objetivo, isto

e, encontrar soluc¸

oes que produzam o maior va-

lor poss

ıvel para a func¸

ao objetivo (Ex.: deﬁnir o n

umero m

aximo de caixas

que podem ser colocadas dentro de um dep

osito). Outros problemas procuram

minimizar o valor da func¸

ao objetivo (Ex.: encontrar a soluc¸

ao mais barata).

Existem ainda func¸

oes que procuram satisfazer a mais de um objetivo, encon-

tradas em problemas de otimizac¸

ao multi-objetivo.

Associada uma nota ou aptid

ao a cada indiv

ıduo da populac¸

ao, o processo

de selec¸

ao escolhe ent

ao um subconjunto de indiv

ıduos da populac¸

ao atual,

Aprendizado de M

aquina 49

gerando uma populac¸

ao intermedi

aria. V

arios m

etodos de selec¸

ao t

em sido

propostos. A maioria deles procura favorecer indiv

ıduos com maiores notas

de aptid

ao, embora n

ao exclusivamente, a ﬁm de manter a diversidade da

populac¸

ao. Entre eles, podemos citar o m

etodo do Torneio, que foi utilizado

neste trabalho.

Quando o m

etodo de selec¸

ao por torneio

e utilizado, n indiv

ıduos da popu-

lac¸

ao s

ao escolhidos aleatoriamente, com a mesma probabilidade. O cro-

mossomo com maior aptid

ao dentre estes n cromossomos

e selecionado para

a populac¸

ao intermedi

aria. O processo se repete at

e que a populac¸

ao in-

termedi

aria seja preenchida. Geralmente, o valor utilizado para n

e 3. A

utilizac¸

ao de selec¸

ao por torneio para n = 3

e ilustrada na Figura 2.7.

Figura 2.7: M

etodo de selec¸

ao por torneio.

2.4.4 Operadores Gen

eticos

Um conjunto de operac¸

oes

e necess

ario para que, dada uma populac¸

ao, seja

poss

ıvel gerar populac¸

oes sucessivas que (espera-se) melhorem sua aptid

com o tempo. Estes operadores s

ao: cruzamento (crossover) e mutac¸

ao. Eles

ao utilizados para assegurar que a nova gerac¸

ao seja totalmente nova, mas

possua, de alguma forma, caracter

ısticas de seus pais, ou seja, a populac¸

ao se

diversiﬁca e mant

em caracter

ısticas de adaptac¸

ao adquiridas pelas gerac¸

oes

anteriores. Para prevenir que os melhores indiv

ıduos n

ao desaparec¸am da

populac¸

ao pela manipulac¸

ao dos operadores gen

eticos, eles podem ser auto-

maticamente colocados na pr

oxima gerac¸

ao, atrav

es de uma pol

ıtica elitista.

O princ

ıpio b

asico dos operadores gen

eticos

e transformar a populac¸

atrav

es de sucessivas gerac¸

oes, estendendo a busca at

e chegar a um re-

sultado satisfat

orio. Os operadores gen

eticos s

ao necess

arios para que a

populac¸

ao se diversiﬁque e mantenha caracter

ısticas de adaptac¸

ao adquiri-

das pelas gerac¸

oes anteriores.

O operador de mutac¸

e necess

ario para a introduc¸

ao e manutenc¸

ao da

diversidade gen

etica da populac¸

ao, alterando arbitrariamente um ou mais

componentes de uma estrutura escolhida, como

e ilustrado na Figura 2.8,

50 Cap

ıtulo 2

fornecendo assim, meios para introduc¸

ao de novos elementos na populac¸

ao.

Desta forma, a mutac¸

ao assegura que a probabilidade de se chegar a qualquer

ponto do espac¸o de busca nunca ser

a zero, al

em de contornar o problema de

ınimos locais, pois com este mecanismo, altera-se levemente a direc¸

ao da

busca. O operador de mutac¸

e aplicado aos indiv

ıduos com uma proba-

bilidade dada pela taxa de mutac¸

ao (0 ≤ P

≤ 1); geralmente se utiliza uma

taxa de mutac¸

ao pequena (0, 001 ≤ P

≤ 0, 1), pois

e um operador gen

etico

secund

ario.

Figura 2.8: Exemplo de mutac¸

ao.

O cruzamento

e o operador respons

avel pela recombinac¸

ao de caracter

ıs-

ticas dos pais durante a reproduc¸

ao, permitindo que as pr

oximas gerac¸

oes

herdem essas caracter

ısticas. Ele

e considerado o operador gen

etico predomi-

nante, por isso

e aplicado com probabilidade dada pela taxa de cruzamento

(0 ≤ P

≤ 1), que deve ser maior que a taxa de mutac¸

ao. Esta taxa

e usu-

almente 0, 6 ≤ P

≤ 0, 99. Este operador pode, ainda, ser utilizado de v

arias

maneiras. As mais utilizadas s

ao:

Cruzamento de um-ponto: um ponto de cruzamento

e escolhido e a partir

deste ponto as informac¸

oes gen

eticas dos pais ser

ao trocadas. As informac¸

oes

anteriores a este ponto em um dos pais s

ao ligadas

as informac¸

oes posteriores

a este ponto no outro pai, como

e mostrado no exemplo da Figura 2.9.

Figura 2.9: Exemplo de cruzamento de um ponto.

Cruzamento multi-pontos:

e uma generalizac¸

ao da id

eia de troca de ma-

terial gen

etico atrav

es de pontos, onde v

arios pontos de cruzamento podem

ser utilizados. O funcionamento deste operador pode ser visto na Figura 2.10,

para o caso de 2 pontos.

Cruzamento uniforme: n

ao utiliza pontos de cruzamento, mas determina,

atrav

es de uma m

ascara, quais os genes de cada cromossomo que cada ﬁlho

herdar

a. Um exemplo da troca de informac¸

oes provocada por este operador

pode ser visto na Figura 2.11. Um valor 1 na m

ascara indica que o gene

correspondente do pai A ser

a herdado pelo ﬁlho C e o gene correspondente do

Aprendizado de M

aquina 51

Figura 2.10: Exemplo de cruzamento de dois pontos.

pai B ser

a herdado pelo ﬁlho D. Para um valor igual a 0 na m

ascara, ocorre o

inverso.

Figura 2.11: Um exemplo de Cruzamentouniforme.

2.4.5 Par

ametros Gen

eticos

O desempenho de um Algoritmo Gen

etico

e fortemente inﬂuenciado pela deﬁ-

nic¸

ao dos par

ametros a serem utilizados. Portanto,

e importante analisar

como tais par

ametros podem ser utilizados em face das necessidades do pro-

blema e dos recursos dispon

ıveis (Jong, 1980). A seguir s

ao discutidos alguns

crit

erios para a escolha dos principais par

ametros:

• Tamanho da Populac¸

ao. O tamanho da populac¸

ao afeta o desempenho

global e a eﬁci

encia dos AGs. Com uma populac¸

ao pequena o desem-

penho pode cair, pois deste modo a populac¸

ao fornece uma pequena co-

bertura do espac¸o de busca do problema. Uma grande populac¸

ao ge-

ralmente fornece uma cobertura representativa do dom

ınio do problema,

em de prevenir converg

encias prematuras para soluc¸

oes locais ao inv

de globais. No entanto, para se trabalhar com grandes populac¸

oes, s

necess

arios mais recursos computacionais, ou que o algoritmo trabalhe

por um per

ıodo de tempo muito maior.

• Taxa de Cruzamento. Quanto maior for esta taxa, mais rapidamente no-

vas estruturas ser

ao introduzidas na populac¸

ao. Mas se esta for muito

alta, estruturas com boas aptid

oes poder

ao ser retiradas mais rapida-

mente que a capacidade da selec¸

ao em criar melhores estruturas. Se

esta taxa for muito baixa, a busca pode estagnar.

• Taxa de Mutac¸

ao. Uma baixa taxa de mutac¸

ao previne que a busca ﬁque

estagnada em subregi

oes do espac¸o de busca. Al

em disso, possibilita que

52 Cap

ıtulo 2

qualquer ponto do espac¸o de busca seja atingido. Com uma taxa muito

alta a busca se torna essencialmente aleat

oria.

• Intervalo de Gerac¸

ao. Controla a porcentagem da populac¸

ao que ser

substitu

ıda para a pr

oxima gerac¸

ao. Com um intervalo grande, a maior

parte da populac¸

ao ser

a substitu

ıda. U intervalo muito grande pode levar

a perda de estruturas de alta aptid

ao. Com um intervalo pequeno, o

algoritmo pode se tornar muito lento.

• Crit

erio de Parada. Diferentes crit

erios podem ser utilizados para ter-

minar a execuc¸

ao de um Algoritmo Gen

etico: ap

os um dado n

umero de

gerac¸

oes, quando a aptid

ao m

edia ou do melhor indiv

ıduo n

ao melhorar

mais ou quando as aptid

oes dos indiv

ıduos de uma populac¸

ao se torna-

rem muito parecidas. Quando se conhece a resposta m

axima da func¸

objetivo,

e poss

ıvel utilizar este valor como crit

erio de parada.

2.5 Considerac¸

oes Finais

Esse cap

ıtulo apresentou uma vis

ao geral sobre os principais conceitos de

Aprendizado de M

aquina que foram utilizados nesse trabalho. O pr

oximo

cap

ıtulo ir

a apresentar alguns m

etodos de extrac¸

ao de conhecimento para

ecnicas de aprendizado de m

aquina n

ao-simb

olico encontradas na literatura

durante o desenvolvimento dessa tese.

CAP

ITULO

Extrac¸

ao de Conhecimento em

ecnicas de AM Caixa-Preta

m grande esforc¸o j

a foi dedicado ao estudo de m

etodos para ex-

trac¸

ao do conhecimento embutido em RNAs treinadas, sendo essa

uma

area com mais de vinte anos de pesquisas. Nos

ultimos anos,

poucos trabalhos tem sido realizados nessa

area. Por

em, recentemente surgiu

o interesse em m

etodos de extrac¸

ao espec

ıﬁcos para Classiﬁcadores de Mar-

gens Largas, mais especiﬁcamente para as M

aquinas de Vetores de Suporte

(SVMs).

Apesar de compartilhar muitos dos conceitos j

a investigados pela

area de

extrac¸

ao de conhecimento de RNAs, esta nova

area de pesquisa ainda encontra-

se em sua inf

ancia e um dos primeiros trabalhos relacionados

a esse tema (se

ao for o primeiro) data de 2002, intitulado “Rule extraction from support vector

machines” (N

nez et al., 2002).

Portanto, este cap

ıtulo tratar

a inicialmente da extrac¸

ao de conhecimento de

RNAs treinadas, relacionando os trabalhos j

a realizados na

area e os conceitos

deﬁnidos por esses trabalhos, alguns dos quais podem ser facilmente adap-

tados para as SVMs e outras t

ecnicas de AM caixa-preta. A seguir, dois dos

trabalhos mais recentes na

area de extrac¸

ao de regras de SVMs ser

ao sucinta-

mente comentados. Por ﬁm, o Sistema NNRules de extrac¸

ao de conhecimento

de RNAs proposto por Milar

e (2003) ser

a descrito em maior detalhe, pois ele

foi o ponto de partida para o m

etodo de extrac¸

ao de conhecimento proposto

nessa tese.

ao v

arias as formas de se classiﬁcar os m

etodos de extrac¸

ao de conhe-

cimento de RNAs treinadas encontrados na literatura (Andrews et al., 1995;

Tickle et al., 1998). A taxonomia mais usada e abrangente

e a que classiﬁca a

ecnica de acordo com a forma pela qual ela analisa o conhecimento adquirido

54 Cap

ıtulo 3

pela RNA. Essa classiﬁcac¸

ao divide os m

etodos em pedag

ogicos, decomposici-

onais e ecl

eticos. A seguir, essa classiﬁcac¸

ao ser

a descrita e m

etodos de cada

uma de suas classes ser

ao exempliﬁcados, tentando, sempre que poss

ıvel,

generalizar seus conceitos de forma a n

ao restringir sua aplicac¸

as RNAs.

3.1 M

etodos Pedag

ogicos

Os m

etodos pedag

ogicos extraem o conhecimento sem analisar as caracter

ısti-

cas internas do classiﬁcador. Essas t

ecnicas realizam um mapeamento entre

os atributos de entrada e sa

ıda do classiﬁcador sem levar em considerac¸

quaisquer passos intermedi

arios.

Exemplos dessa categoria s

ao: o m

etodo de Saito and Nakano (1988), que

utiliza busca em largura para encontrar combinac¸

oes de valores para as uni-

dades de entrada que ativam cada uma das unidades de sa

ıda; o m

etodo

de Gallant (1993), que

e similar ao de Saito e Nakano e utiliza heur

ısticas para

reduzir o espac¸o de busca; o m

etodo Validity Interval Analysis (Thrun, 1995),

que testa as regras propagando intervalos de ativac¸

ao especiﬁcados por meio

de programac¸

ao linear, e denominados intervalos de validade por meio de uma

RNA; e o m

etodo TREPAN (Craven and Shavlik, 1996), que constr

arvores de

decis

ao utilizando os exemplos de treinamento com que a RNA foi treinada e,

em uma de suas variac¸

oes, inclui exemplos artiﬁciais gerados pelo TREPAN,

ambos classiﬁcados pela RNA.

ıticas t

em sido feitas aos m

etodos que utilizam exemplos artiﬁciais, pois

e f

acil validar a exist

encia de tais exemplos no mundo real, o que pode

levar o m

etodo a gerar regras desnecessariamente complexas ou com perda

de precis

ao e ﬁdelidade. Por

em, um dos problemas dos m

etodos pedag

ogicos

que n

ao utilizam exemplos artiﬁciais

e que quando o classiﬁcador do qual

se pretende extrair as regras tem um desempenho de classiﬁcac¸

ao pr

oximo ao

otimo, o conjunto de dados por ele rotulado pouco difere do conjunto de dados

original utilizado para trein

a-lo. Com isso, apesar da ﬁdelidade alcanc¸ada por

esses m

etodos (medida pela porcentagem de exemplos em que o classiﬁcador

concorda com as regras extra

ıdas) ser alta,

e pouco prov

avel que as regras

reﬂitam o conhecimento armazenado no classiﬁcador. Esse problema tem

sido negligenciado em muitos trabalhos da

area.

Em geral, os m

etodos dessa categoria podem ser aplicados em qualquer

ecnica de aprendizado de m

aquina, como SVMs e Comit

es de Classiﬁcado-

res, sem maiores problemas, uma vez que n

ao fazem nenhuma an

alise nos

par

ametros internos da t

ecnica utilizada.

Extrac¸

ao de Conhecimento em T

ecnicas de AM Caixa-Preta 55

3.2 M

etodos Decomposicionais

Os m

etodos decomposicionais decomp

oem uma RNA em diversas redes de ape-

nas uma camada e uma unidade. Cada unidade intermedi

aria e de sa

ıda

ent

ao descrita por um conjunto de regras. Por ﬁm, estas regras s

ao combina-

das em um conjunto que descreve o comportamento da RNA como um todo.

Exemplos dessa categoria s

ao: o m

etodo KT (Fu, 1991, 1994), que busca

por combinac¸

oes de pesos que, quando satisfeitos, garantem que uma unidade

ser

a ativada independentemente do valor de outras entradas para a unidade;

o m

etodo M-of-N de Towell and Shavlik (1993), que

e similar ao KT e que

busca, para cada unidade, por conjuntos de conex

oes de entrada cuja soma

dos pesos excedam o seu bias, independente dos pesos associados a outras

conex

oes de entrada, extraindo regras do tipo m-de-n

; o m

etodo desenvolvido

por Blasig (1994), que utiliza uma func¸

ao especial de custo para encorajar uni-

dades intermedi

arias e de sa

ıda a assumirem um estado favor

avel

a extrac¸

de regras, durante o treinamento, de forma que cada unidade possa ser di-

retamente traduzida em uma regra; e o m

etodo desenvolvido por Setiono and

Liu (1995), que modiﬁca o processo de treinamento da RNA para simpliﬁcar

o processo de extrac¸

ao de regras, extraindo conjuntos de regras concisos de

redes que apresentam um n

umero pequeno de unidades intermedi

arias.

3.3 M

etodos Ecl

eticos

Os m

etodos ecl

eticos s

ao abordagens h

ıbridas que extraem o conhecimento de

RNAs aliando a an

alise individual das unidades com a an

alise das entradas e

ıdas da rede.

Um exemplo de m

etodo dessa categoria

e o algoritmo DEDEC, proposto por

Tickle et al. (1994). Esse m

etodo extrai regras if-then de redes MLP treinadas

com o algoritmo backpropagation (Braga et al., 2000; Haykin, 1998).

3.4 M

etricas

Abaixo est

ao relacionadas algumas das m

etricas que foram deﬁnidas para a

avaliac¸

ao de m

etodos de extrac¸

ao de conhecimento de RNAs, mas que t

em sido

aplicadas

a outros m

etodos de extrac¸

ao tamb

em (Mitra et al., 2002; Craven

and Shavlik, 1999):

• Precis

ao ou Acur

acia: Porcentagem de classiﬁcac¸

oes corretas obtidas pe-

las regras extra

ıdas.

Uma express

ao m-de-n

e uma express

ao booleana que

e satisfeita quando ao menos m

(um limite inteiro) de n condic¸

oes booleanas s

ao satisfeitas.

56 Cap

ıtulo 3

• Precis

ao do Usu

ario: N

umero de classiﬁcac¸

oes corretas de uma classe

dividido pelo n

umero de classiﬁcac¸

oes dessa classe.

• Fidelidade: Porcentagem do conjunto de teste em que as regras extra

ıdas

e o m

etodo de aprendizado de m

aquina n

ao-simb

olico concordam (clas-

siﬁcam o exemplo na mesma classe).

• Cobertura: Porcentagem de exemplos de um conjunto de teste em que

pelo menos uma regra

e disparada.

• Tamanho da base de regras: N

umero de regras extra

ıdas. Quanto mais

baixo seu valor, mais compacta

e a base de regras.

• Complexidade computacional: Medida em termos de tempo de CPU re-

querido.

• Compreensibilidade: Conjunto de fatores que determinam a facilidade de

entendimento de uma regra. Considerac¸

ao apenas de atributos relevan-

tes, tamanho da base de regras, etc.

• Escalabilidade: Diz respeito a como o tempo de execuc¸

ao e a compre-

ensibilidade dos modelos extra

ıdos variam em func¸

ao de fatores como

dimensionalidade, tamanho do conjunto de treinamento e complexidade

do algoritmo de aprendizado de m

aquina n

ao-simb

olico.

• Generalidade: Proporc¸

ao em que o algoritmo de extrac¸

ao de conheci-

mento n

ao requer treinamentos especiais ou restric¸

oes no algoritmo de

aprendizado de m

aquina n

ao-simb

olico.

3.5 Extrac¸

ao de Conhecimento de SVMs

Nessa sec¸

ao ser

ao relacionados sucintamente dois trabalhos recentes de ex-

trac¸

ao de conhecimento de M

aquinas de Vetores de Suporte encontrados na

literatura.

Um dos poucos m

etodos de extrac¸

ao de conhecimento projetados especiﬁ-

camente para M

aquinas de Vetores de Suporte

e o SVM+Prototypes proposto

por N

nez et al. (2002).

E um m

etodo decomposicional que extrai tanto regras

proposicionais como regras em que as condic¸

oes s

ao equac¸

oes matem

aticas

de elips

oides.

Esse m

etodo realiza um processo iterativo. Seu algoritmo

e exposto em

pseudoc

odigo no Algoritmo 4.

Extrac¸

ao de Conhecimento em T

ecnicas de AM Caixa-Preta 57

Algoritmo 4: Algoritmo SVM+Prototypes

Treinar uma SVM;1

Dividir os dados em dois subconjuntos, determinados pela classiﬁcac¸

ao2

da SVM;

i = 1;3

repita4

para cada subconjunto fac¸a5

Encontrar i clusters (novos subconjuntos);6

Calcular o prot

otipo ou centr

oide de cada cluster;7

para cada novo subconjunto fac¸a8

Encontrar o vetor de suporte que est

a mais longe do prot

otipo;9

Usar o prot

otipo como centro e o vetor de suporte como v

ertice10

para criar um hipercubo no espac¸o de entrada;

ﬁm11

ﬁm12

para cada hipercubo fac¸a13

Fazer um teste de partic¸

ao para minimizar o n

ıvel de sobreposic¸

ao14

entre os cubos em que a classe predita

e diferente (uma

alternativa

e testar se todos os cantos do hipercubo s

ao da mesma

classe e, se forem, o teste

e positivo);

ﬁm15

Converter todos os hipercubos com partic¸

ao negativa em regras;16

Incrementar i;17

e n

ao existirem hipercubos com teste de partic¸

ao positivos OU i == Imax18

;

Converter todos os hypercubos correntes em regras;19

58 Cap

ıtulo 3

O principal problema desse algoritmo

e que as regras extra

ıdas n

ao s

nem exclusivas e nem exaustivas, o que resulta em regras conﬂitantes ou

faltantes na classiﬁcac¸

ao de novas inst

ancias.

Outro trabalho recente realiza a extrac¸

ao de regras de M

aquinas de Vetores

de Suporte Lineares via Programac¸

ao Matem

atica.

Esse trabalho, proposto por Fung et al. (2008) descreve um m

etodo para

a convers

ao de SVMs lineares em um conjunto de regras sem sobreposic¸

ao.

Nesse m

etodo, cada iterac¸

ao do algoritmo de extrac¸

ao de regras

e formulada

como um problema de otimizac¸

ao com restric¸

oes.

A vantagem desse m

etodo reside na necessidade de resolver apenas proble-

mas de otimizac¸

ao simples, em poucas vari

aveis.

3.6 Sistema NNRules

Nessa sec¸

ao, os m

etodos utilizados no sistema NNRules para a extrac¸

ao de

conhecimento compreens

ıvel de redes neurais treinadas (RNAs) s

ao sucinta-

mente descritos. Esses m

etodos foram propostos por Milar

e (2003). Alguns

experimentos com os m

etodos do sistema NNRules foram realizados e s

apresentados no Cap

ıtulo 5

3.6.1 M

etodo baseado em Aprendizado de M

aquina Simb

olico

O m

etodo baseado em Aprendizado de M

aquina (AM) simb

olico utiliza sistemas

de AM simb

olicos para extrair representac¸

oes simb

olicas de RNAs. Uma das

principais caracter

ısticas dos sistemas de AM simb

olicos

e a sua habilidade

em representar a hip

otese induzida como estruturas simb

olicas, geralmente

compreens

ıveis para humanos. A Figura 3.1 mostra um esquema geral desse

etodo.

Sistema de

Aprendizado

Simbólico

Exemplos

Rotulados

pela RNA

Exemplos

RNA

Treinada

(Hipótese h)

Classificador

Simbólico h´

Figura 3.1: Esquema geral do m

etodo baseado em sistemas de AM simb

olicos.

Nesse m

etodo, uma RNA

e treinada como o conjunto de dados E. Ap

os o

treinamento, a RNA

e usada como uma “caixa preta” para classiﬁcar o con-

junto de dados E, criando novos valores para o atributo classe. Os novos

valores do atributo classe reﬂetem o conhecimento aprendido pela RNA, isso

e, reﬂetem a hip

otese h induzida pela RNA. O conjunto de dados rotulado pela

RNA

e fornecido como entrada para o sistema de AM simb

olico. O sistema de

AM simb

olico induz uma representac¸

ao simb

olica baseada nos novos r

otulos

atribu

ıdos pela RNA aos exemplos. Desse modo, o classiﬁcador simb

olico h



Extrac¸

ao de Conhecimento em T

ecnicas de AM Caixa-Preta 59

induzido pelo sistema de AM simb

olico visa aproximar a hip

otese h induzida

pela RNA. Esse m

etodo

e similar ao m

etodo TREPAN (Craven, 1996), no entanto

ele n

ao gera novos exemplos artiﬁcialmente como o TREPAN faz.

Uma das qualidades desse m

etodo

e que qualquer sistema de AM simb

olico

pode ser utilizado para induzir um classiﬁcador simb

olico a partir do con-

junto de dados rotulado pela RNA. Desse modo, o m

etodo

e simples e f

acil de

usar, uma vez que ele permite o uso de qualquer sistema de AM simb

olico.

Nesse trabalho, os sistemas de AM simb

olico C4.5, C4.5rules (Quinlan, 1988) e

CN2 (Clark and Niblett, 1989b) foram utilizados.

3.6.2 M

etodo Baseado em Algoritmos Gen

eticos

O m

etodo baseado em Algoritmos Gen

eticos (AGs) visa otimizar a representac¸

simb

olica extra

ıda das RNAs por sistemas de AM simb

olicos. A Figura 3.2

mostra um esquema geral desse m

etodo.

Classificador

Simbólico

’

Sistema de

Aprendizado

Simbólico

1

2

Classificador

Simbólico

’

Classificador

Simbólico

’

PBM

Conversor

PBM

Conversor

PBM

Conversor

Classifcador

Formato PBM

h ’

Classifcador

Formato PBM

h ’

Classifcador

Formato PBM

h ’

Exemplos

Rotulados

por RNAs

Classificador

Formato PBM

h ’

Classificador

Simbólico

Algoritmo

Genético

Sistema de

Aprendizado

Simbólico

Sistema de

Aprendizado

Simbólico

Classificador

Formato PBM

Classificador

Formato PBM

Figura 3.2: Esquema geral do m

etodo baseado em AGs.

AGs s

ao m

etodos de busca e otimizac¸

ao inspirados no processo de evoluc¸

e selec¸

ao natural. Um AG utiliza uma populac¸

ao de indiv

ıduos para resol-

ver um determinado problema. Cada indiv

ıduo da populac¸

ao corresponde a

uma poss

ıvel soluc¸

ao para o problema. Um mecanismo de reproduc¸

e apli-

cado

a populac¸

ao atual, gerando uma nova populac¸

ao. A populac¸

ao normal-

mente evolui atrav

es de diversas gerac¸

oes at

e que uma soluc¸

ao apropriada seja

alcanc¸ada. AGs iniciam sua operac¸

ao gerando uma populac¸

ao inicial formada

por um grupo de indiv

ıduos aleat

orios, que podem ser vistos como primeiros

palpites para resolver um problema em particular. A populac¸

ao inicial

e avali-

ada e para cada indiv

ıduo, uma nota (chamada ﬁtness)

e calculada, reﬂetindo

a qualidade da soluc¸

ao associada a ela.

60 Cap

ıtulo 3

Suponha que uma RNA induz a hip

otese h a partir de um conjunto de dados

E. Como no m

etodo baseado em AM simb

olico, o conjunto de dados E utili-

zado para treinar a RNA

e rotulado pela RNA, originando o conjunto de dados



. Esse conjunto de dados

e utilizado como entrada para p sistemas de AM

simb

olico. Como resultado, os classiﬁcadores simb

olicos h



, h



, ...h



ao in-

duzidos. Cada classiﬁcador aproxima a hip

otese induzida pela RNA para uma

partic¸

ao particular. Infelizmente, cada sistema de AM simb

olico representa o

conceito induzido em uma linguagem diferente, diﬁcultando a integrac¸

ao des-

ses classiﬁcadores. Ent

ao,

e necess

ario traduzir a representac¸

ao desse clas-

siﬁcadores para uma linguagem comum. Para fazer tal traduc¸

ao, foi utilizado

o trabalho de Prati et al. (2002), que prop

oe uma sintaxe padr

ao para repre-

sentar regras chamada PBM. Assim, cada classiﬁcador simb

olico

e traduzido

para o formato PBM (Figure 3.2.a).

Em uma segunda fase, um AG

e empregado para integrar as p hip

oteses h



em uma

unica hip

otese com maior ﬁdelidade com h. As regras que comp

os p classiﬁcadores podem ser usadas para codiﬁcar os v

arios indiv

ıduos da

populac¸

ao inicial do AG. Assim, cada indiv

ıduo na populac¸

ao inicial

e formado

por um conjunto de regras, em que cada regra

e aleatoriamente extra

ıda de um

dos p classiﬁcadores. Ap

os v

arias gerac¸

oes, o melhor indiv

ıduo da populac¸

atual

e utilizado como o conjunto de regras otimizado. Esse conjunto de regras

e ent

ao utilizado para explicar o comportamento da RNA (Figure 3.2.b).

Em uma terceira fase opcional, um p

os-processamento

e aplicado ao me-

lhor indiv

ıduo removendo as regras que n

ao s

ao disparadas. Esse p

os-proces-

samento pode aumentar a compreensibilidade do conjunto de regras.

3.7 Considerac¸

oes Finais

Esse cap

ıtulo apresentou os conceitos da extrac¸

ao de conhecimento em t

ecni-

cas de AM caixa-preta e uma revis

ao de diversos m

etodos encontrados na

literatura. O pr

oximo cap

ıtulo ir

a apresentar o m

etodo RankSim, proposto

nessa Tese.

CAP

ITULO

etodo Proposto

esse cap

ıtulo ser

a descrito o m

etodo RankSim, proposto nessa Tese,

para a extrac¸

ao de conhecimento simb

olico a partir de modelos

caixa-preta de aprendizado de m

aquina em problemas de classi-

ﬁcac¸

ao bin

aria, ou seja, problemas de apenas duas classes.

A motivac¸

ao para esse m

etodo vem da percepc¸

ao de que a maioria dos

etodos pedag

ogicos existentes enfrentam o problema da falta de informac¸

sobre o que foi realmente aprendido pelo modelo n

ao-simb

olico (Redes Neu-

rais Artiﬁciais, M

aquinas de Vetores de Suporte, entre outros) quando estes

apresentam uma alta taxa de acerto. Por exemplo, se uma M

aquina de Ve-

tores de Suporte classiﬁcar corretamente todos os exemplos que lhes forem

apresentados, o conjunto de exemplos por ela rotulado ser

a id

entico ao con-

junto de exemplos original. Nesse caso, n

e muito interessante utilizar um

etodo pedag

ogico tradicional, uma vez que isso equivale a usar os exem-

plos originais para extrair regras. Sendo assim, se o classiﬁcador simb

olico

tamb

em tiver uma taxa de acerto elevada, a ﬁdelidade ser

a elevada, mesmo

que o classiﬁcador simb

olico classiﬁque os exemplos com uma fronteira de de-

cis

ao signiﬁcativamente diferente da fronteira de decis

ao utilizada pelo modelo

gerado pelo m

etodo caixa-preta.

No m

etodo proposto nesta tese, utilizamos mais informac¸

ao do que a dis-

ponibilizada pela sa

ıda bin

aria de classiﬁcac¸

ao do modelo caixa-preta. Utili-

zamos a informac¸

ao da sa

ıda num

erica dos modelos caixa-preta em um algo-

ritmo gen

etico que otimiza a similaridade dos rankings do modelo caixa-preta e

das regras extra

ıdas. A seguir, na Sec¸

ao 4.1,

e feita a descric¸

ao da arquitetura

do m

etodo e na Sec¸

ao 4.2

e apresentada a func¸

ao de avaliac¸

ao utilizada no

algoritmo gen

etico. A Sec¸

ao 4.4 apresenta as considerac¸

oes ﬁnais do cap

ıtulo.

62 Cap

ıtulo 4

4.1 Descric¸

ao do M

etodo RankSim

arios modelos caixa-preta, incluindo M

aquinas de Vetores de Suporte e Redes

Neurais Artiﬁciais representam sua sa

ıda de forma num

erica. Para chegar

a um valor de classiﬁcac¸

ao, ou classe,

e necess

ario utilizar uma func¸

ao de

limiar para discretizar essa sa

ıda num

erica. No caso mais comum, a sa

ıda

ent

ao passa a ser bin

aria, classiﬁcando as inst

ancias em r

otulos positivos ou

negativos.

etodos pedag

ogicos tradicionais utilizam apenas a informac¸

ao desses r

tulos, por

em, em alguns modelos caixa-preta, a sa

ıda num

erica nos informa

o grau de conﬁabilidade que o modelo tem em sua resposta. Por exemplo, se

um modelo for treinado para retornar +1 para os casos positivos e -1 para os

casos negativos, com limiar em 0, isso signiﬁca que respostas pr

oximas de +1

ou -1 tem maior conﬁabilidade do que as pr

oximas de 0.

Sendo assim,

e poss

ıvel criar um ranking ordenado por conﬁabilidade das

ıdas do m

etodo caixa-preta, partindo do exemplo positivo mais conﬁ

avel,

passando por uma regi

ao de incerteza, at

e o exemplo negativo mais conﬁ

avel.

Regras induzidas por t

ecnicas de aprendizado de m

aquina simb

olico tam-

em podem atribuir um valor de conﬁabilidade para suas sa

ıdas e, sendo

assim, tamb

e poss

ıvel criar um ranking ordenado das sa

ıdas do conjunto

de regras.

Na abordagem proposta, as regras utilizadas s

ao n

ao-ordenadas e todas as

regras disparadas para um dado exemplo s

ao avaliadas. A classiﬁcac¸

e dada

por meio da avaliac¸

ao das matrizes de conting

encia das regras disparadas.

As matrizes de conting

encia indicam as freq

encias dos exemplos cobertos

pela regra classiﬁcados como verdadeiros positivos, falsos positivos, verdadei-

ros negativos e falsos negativos. Verdadeiros positivos s

ao os exemplos da

classe positiva que foram corretamente classiﬁcados pela regra. Falsos positi-

vos s

ao os exemplos da classe negativa que foram incorretamente classiﬁcados

pela regra. Analogamente, os verdadeiros negativos s

ao os exemplos da classe

negativa que foram corretamente classiﬁcados pela regra e os falsos negati-

vos s

ao os exemplos da classe positiva que foram incorretamente classiﬁcados

pela regra.

Para decidir a classiﬁcac¸

ao de um novo exemplo, as matrizes de contin-

encia das regras disparadas s

ao totalizadas, fazendo o c

alculo do

ındice de

acur

acia menos erro das regras, que

e calculado subtraindo do percentual de

exemplos cobertos corretamente o percentual de exemplos corretos incorreta-

mente, para cada classe. A classe com o melhor

ındice

e a escolhida.

em de determinar a classiﬁcac¸

ao de novos exemplos, os

ındices calcu-

etodo Proposto 63

lados por meio da matriz de conting

encia podem ser utilizados para estimar

a probabilidade de que a classiﬁcac¸

ao seja correta. Para isso, pode-se utili-

zar freq

encias calculadas pela Equac¸

ao 4.1, em que ECC s

ao os exemplos

de treinamento cobertos corretamente pelas regras e ECI s

ao os exemplos

cobertos incorretamente.

P rob =

ECC

ECC + ECI

(4.1)

Essa an

alise simples pode gerar estimativas pouco conﬁ

aveis em termos

absolutos. Uma das formas alternativas encontradas na literatura para a

estimac¸

ao de probabilidades

e utilizac¸

ao da correc¸

ao de Laplace. A correc¸

de Laplace adiciona um exemplo virtual para cada classe como pode ser visto

na equac¸

ao 4.2, na qual k

e o n

umero de classes.

P rob =

ECC + 1

ECC + ECI + k

(4.2)

Essa correc¸

ao visa reduzir o impacto das mudanc¸as que pequenas altera-

c¸

oes em ECC ou ECI podem provocar na estimativa. Por

em, como em nosso

etodo estamos apenas interessados na estimativa da conﬁabilidade relativa

entre os exemplos apresentados para gerar o ranking, que n

e alterado uti-

lizando a correc¸

ao de Laplace, por simplicidade, em nossos experimentos em-

pregamos a Equac¸

ao 4.1.

Com isso em vista, o m

etodo proposto visa n

ao somente ter ﬁdelidade de

classiﬁcac¸

ao mas tamb

em maximizar a similaridade entre os rankings dos

modelos caixa-preta e os rankings das regras extra

ıdas.

Para isso, utilizamos uma abordagem inspirada no trabalho de Milar

e (2003),

descrito na Sec¸

ao 3.6, em que regras s

ao geradas por algoritmos simb

olicos e

otimizadas por algoritmos gen

eticos para maximizar a ﬁdelidade.

A diferenc¸a

e que, ao inv

es de utilizar a ﬁdelidade como func¸

ao de avaliac¸

para a otimizac¸

ao do algoritmo gen

etico, criamos uma nova m

etrica que mede

a semelhanc¸a entre os rankings para ser utilizada como func¸

ao de avaliac¸

ao.

Nessa abordagem, temos duas variac¸

oes:

• As regras da populac¸

ao inicial do algoritmo gen

etico s

ao induzidas a par-

tir do conjunto de exemplos originais.

• O conjunto de exemplos utilizado para a induc¸

ao do conjunto de regras

da populac¸

ao inicial do algoritmo gen

etico

e rotulado pelo modelo caixa-

preta.

A Figura 4.1 representa a arquitetura do m

etodo RankSim. Nela est

contempladas as duas abordagens.

64 Cap

ıtulo 4

4.2 Func¸

ao de Avaliac¸

Para calcular a func¸

ao de avaliac¸

ao do algoritmo gen

etico empregado no m

todo proposto, deﬁnimos uma m

etrica para medir a similaridade entre os ran-

kings. Essa m

etrica visa atribuir alta similaridade para pares de rankings em

que a somat

oria das dist

ancias entre as posic¸

oes dos exemplos em um ran-

king em relac¸

as posic¸

oes dos exemplos no outro ranking seja m

ınima. Essa

etrica

e representada pela Equac¸

ao 4.3:

RankSim = 1 −



i=0

|P osRegras(i) − P osCP reta(i)|

n

/2

(4.3)

Nessa equac¸

ao, n

e o n

umero de exemplos utilizados para construir o ran-

king, P osRegras()

e uma func¸

ao que retorna a posic¸

ao do exemplo i no ranking

das regras do indiv

ıduo avaliado, P osCP reta(i)

e a um func¸

ao que retorna

a posic¸

ao do exemplo i no ranking gerado pelo modelo caixa-preta. Desse

modo, RankSim

e o valor da func¸

ao de avaliac¸

ao, que retorna 1 para rankings

enticos, e 0 para o pior caso deﬁnido em nossa m

etrica, em que os rankings

est

ao invertidos. O c

alculo

e feito somando-se as diferenc¸as entre P osRegras(i)

e P osCP reta(i) em m

odulo para cada exemplo no conjunto de exemplos utili-

zado no treinamento, dividindo o resultado pelo termo n

/2, que garante

que o resultado ﬁcar

a entre zero e um pois representa o pior caso e, por ﬁm,

subtrai-se esse valor de 1 para que a resposta seja 1 para rankings de maior

similaridade.

Com isso, pudemos obter uma func¸

ao com sa

ıda normalizada entre 0 e

1, o que facilita a execuc¸

ao do algoritmo gen

etico, e que penaliza fortemente

exemplos que seriam classiﬁcados incorretamente por regras com alta con-

ﬁabilidade e penaliza apenas minimamente pequenas trocas de posic¸

ao em

locais pr

oximos no ranking.

4.3 Caracter

ısticas do Algoritmo Gen

etico

No Algoritmo Gen

etico empregado neste trabalho, cada indiv

ıduo

e um con-

junto de regras.

A populac¸

ao inicial

e composta de indiv

ıduos que representam subconjun-

tos aleat

orios de todas as regras geradas por v

arios indutores simb

olicos,

partir de um conjunto de dados que foi utilizado para treinar o modelo caixa-

preta.

Os operadores gen

eticos utilizados foram cruzamento e mutac¸

ao. O cru-

zamento

e assim

etrico, ou seja, duas posic¸

oes s

ao escolhidas, uma para cada

indiv

ıduo pai e os ﬁlhos s

ao gerados recombinando os segmentos dos pais.

Sendo assim, o tamanho dos indiv

ıduos

e vari

avel. A mutac¸

e realizada pela

etodo Proposto 65

remoc¸

ao ou inclus

ao de regras que n

ao faziam parte dos pais.

Um exemplo de cruzamento

e dado na Tabela 4.1. Cada n

umero

e um

ındice para uma das regras da base de regras geral.

Tabela 4.1: Operac¸

ao de Cruzamento

pai1 04 02 | 12 08 14

pai2 03 05 11 | 09 13

ﬁlho1 04 02 09 13

ﬁlho2 03 05 11 12 08 14

Os par

ametros do Algoritmo Gen

etico s

ao:

• ng - n

umero de gerac¸

oes;

• ni - n

umero de indiv

ıduos;

• ti - tamanho inicial do indiv

ıduo (n

umero de regras);

• pc - probabilidade de cruzamento;

• pm - probabilidade de mutac¸

ao.

Nos experimentos do Cap

ıtulo 5 foram utilizados os par

ametros ng = 20,

ni = 20, ti = 10, pc = 0.25 e pm = 0.01 em todos os conjuntos de dados.

4.4 Considerac¸

oes Finais

Em nossos experimentos, utilizamos M

aquinas de Vetores de Suporte como o

modelo caixa-preta do qual as regras foram extra

ıdas. Nesse tipo de modelo

caixa-preta, altos valores em sua sa

ıda signiﬁcam uma maior dist

ancia do

exemplo em relac¸

a fronteira de decis

ao trac¸ada pelo modelo. Acreditamos

portanto que a otimizac¸

ao da similaridade entre os rankings nesse caso pode

levar

a induc¸

ao de regras que aproveitem as caracter

ısticas de classiﬁcador de

margens largas encontradas nas M

aquinas de Vetores de Suporte.

A seguir, no Cap

ıtulo 5, ser

ao apresentados esses experimentos e as algu-

mas discuss

oes a respeito dos resultados obtidos.

66 Cap

ıtulo 4

Figura 4.1: M

etodo RankSim

CAP

ITULO

Experimentos Realizados

s experimentos descritos a seguir investigam o uso de regras pro-

duzidas por sistemas de Aprendizado de M

aquina (AM) simb

olicos e

otimizadas por Algoritmos Gen

eticos (AGs) para explicar o conheci-

mento embutido em modelos de aprendizado de m

aquina caixa-preta.

Os experimentos est

ao divididos em duas fases. Na primeira fase, os m

todos propostos por Milar

e (2003), originais e adaptados para a extrac¸

ao de

regras de SVMs, foram aplicados para realizar a extrac¸

ao de regras de RNAs e

SVMs empregadas para identiﬁcar promotores em seq

encias de nucleot

ıdeos

de E. Coli e para identiﬁcar junc¸

oes de splice de humanos. Na segunda

fase, foram realizados experimentos com o m

etodo RankSim, proposto nessa

tese, para essas mesmas bases e em mais 14 bases do Reposit

orio de AM da

UCI (Blake and Merz, 1998).

5.1 Fase I - Estudo preliminar de extrac¸

ao de regras

de RNAs e SVMs por m

etodos de AM e AGs

A Sec¸

ao 5.1.1 explica sucintamente os problemas de biologia molecular in-

vestigados. A Sec¸

ao 5.1.2 apresenta os conjuntos de dados utilizados nos

experimentos. A Sec¸

ao 5.1.3 descreve os experimentos conduzidos. Por ﬁm, a

Sec¸

ao 5.1.4 apresenta os resultados obtidos.

5.1.1 Identiﬁcac¸

ao de Promotores e S

ıtios de Splice

Um dos maiores problemas em biologia molecular

e a identiﬁcac¸

ao de genes

em seq

encias de DNA. A alta complexidade e variabilidade dos genes torna

apropriado o uso de t

ecnicas de AM, entre elas est

ao as RNAs e SVMs. Duas

abordagens computacionais usualmente empregadas para o reconhecimento

de genes s

ao: busca por sinal e busca por conte

udo. A busca por sinal envolve

a localizac¸

ao de marcas na seq

encia associados com a presenc¸a de um gene.

68 Cap

ıtulo 5

Dentre essas marcas, podemos citar promotores e junc¸

oes de splice (Craven

and Shavlik, 1994a).

Na maioria dos organismos, exceto os v

ırus de RNA, mol

eculas de DNA

(

Acido Desoxirribonucl

eico) codiﬁcam as informac¸

oes gen

eticas em uma se-

encia de estruturas chamadas nucleot

ıdeos, que podem ser de quatro ti-

pos: Adenina (A), Citosina (C), Guanina (G) e Timina (T). Essa informac¸

organizada em genes posicionados ao longo da mol

ecula de DNA. Os genes s

seq

encias de nucleot

ıdeos que s

ao transcritos em mRNA (

Acido Ribonucl

eico

mensageiro) que

e ent

ao traduzido em prote

ınas. Esse processo

e chamado de

express

ao g

enica (Lewin, 2000).

O processo de transcric¸

ao inicia com a ligac¸

ao da RNA-polimerase a um

ıtio espec

ıﬁco de uma seq

encia de DNA. Esse s

ıtio

e chamado promotor. O

promotor

e uma seq

encia de DNA que difere das seq

encias que s

ao transcri-

tas ou traduzidas, j

a que sua func¸

e: ser reconhecido por prote

ınas. Ent

ao,

ele deve ser longo o suﬁciente para que possa ser unicamente reconhecido. O

tamanho apropriado varia com o tamanho do genoma. Por exemplo, em um

genoma bacterial, doze pares de bases constituem um sinal promotor apropri-

ado.

O problema de reconhecimento de promotores est

a relacionado a identi-

ﬁcar se uma dada seq

encia de tamanho ﬁxo cont

em um promotor (Y) ou

ao (N). Para realizar essa tarefa, classiﬁcadores baseados em RNAs podem ser

induzidos.

A express

ao g

enica em organismos eucariotos

e diferente da dos organis-

mos procariotos. Genes eucariotos s

ao compostos de segmentos alternados

de exons e introns. Exons s

ao regi

oes que codiﬁcam a prote

ına ﬁnal. Introns

intermediam os exons e n

ao codiﬁcam prote

ınas. O processo de express

enica em eucariotos inclui um passo adicional, a eliminac¸

ao de introns da

mol

ecula de mRNA. Esse processo

e conhecido como splicing. A fronteira en-

tre exons e introns

e chamada junc¸

ao de splice (ou s

ıtios de splice).

O problemas do reconhecimento de junc¸

oes de splice tratado nesse traba-

lho

e a identiﬁcac¸

ao de tr

es tipos de seq

encias de tamanho ﬁxo: seq

encias

contendo um s

ıtio intron/exon (IE), um s

ıtio exon/intron (EI) e seq

encias que

ao cont

em um s

ıtio de splice.

5.1.2 Conjuntos de Dados

O conjunto de dados promoters (Promoter Gene Sequences Database) utilizado

nesse trabalho foi extra

ıdo do Reposit

orio de AM da UCI (Blake and Merz,

1998). Esse conjunto de dados cont

em 106 exemplos. Cada um dos 57 atri-

butos pode assumir um de quatro valores representando os nucleot

ıdeos (A,

Experimentos Realizados 69

C, T, G). Esse

e um problema de classiﬁcac¸

ao bin

aria, o que signiﬁca que cada

exemplo

e classiﬁcado como sendo um promotor ou n

ao. Esse conjunto de

dados

e balanceado, tendo 50% de exemplos em cada classe.

Os conjuntos de dados spliceN e spliceEI foram adaptados do “Splice-

junction Gene Sequences Database”, tamb

em extra

ıdo do Reposit

orio de AM

da UCI. O conjunto de dados spliceEI cont

em 1527 exemplos de s

ıtios de

splice divididos em duas classes: “Exon-Intron” 50% e “Intron-Exon” 50%. O

conjunto de dados spliceN cont

em 3175 exemplos divididos em duas classes:

“S

ıtio de Splice” 50% e “N

ao S

ıtio de Splice” 50%. Em ambos os conjuntos

de dados, cada um dos 60 atributos pode assumir valores representando um

dos quatro nucleot

ıdeos (A, C, T, G). Exemplos com atributos desconhecidos

foram removidos.

5.1.3 Experimentos

Os tr

es conjuntos de dados foram divididos utilizando a metodologia k-fold

stratiﬁed cross-validation (Weiss and Kulikowski, 1991), com k = 10, obtendo

10 conjuntos de treinamento e 10 conjuntos de teste para cada conjunto de

dados. Em seguida, cada conjunto de treinamento foi subdividido em um

conjunto de treinamento menor, contendo 90 dos exemplos de treinamento, e

conjunto de validac¸

ao, contendo 10 dos exemplos de treinamento.

Os algoritmos simb

olicos C4.5, C4.5rules e CN2 foram executados com seus

valores de par

ametros padr

ao em todas as partic¸

oes para todos os conjuntos

de dados. Como resultado, 90 classiﬁcadores foram induzidos. O erro m

edio

estimado dos 10 classiﬁcadores de cada sistema de AM simb

olico foi medido

usando o conjunto de teste.

arias redes MLP foram treinadas com o algoritmo backpropagation with

momentum utilizando seus par

ametros padr

ao, uma para cada conjunto de

dados. A mesma metodologia de validac¸

ao-cruzada empregada para os sis-

temas de AM simb

olico foi utilizada. A topologia das RNAs treinadas com o

conjunto de dados promoters continha uma camada de entrada com 228 uni-

dades, uma camada escondida com 456 unidades e uma camada de sa

ıda

com uma

unica unidade. A topologia para as RNAs treinadas para ambos os

conjuntos de dados spliceN e spliceEI cont

em uma camada de entrada com

240 unidades, uma camada escondida com 480 unidades e uma camada de

ıda com uma

unica unidade. Para realizar os experimentos, o simulador

SNNS foi empregado (Zell, 1995). Para determinar a classe da sa

ıda de uma

RNA, uma func¸

ao limite foi empregada. A classe da sa

ıda da RNA

e 1 se o valor

do n

o de sa

ıda for maior que 0.5, e a classe ser

a 0, caso contr

ario.

SVMs com kernel gaussiano e par

ametros padr

ao foram treinadas, uma

70 Cap

ıtulo 5

para cada conjunto de dados. Foi utilizado para isso o indutor SVMTorch (Col-

lobert and Bengio, 2001).

Em seguida, os m

etodos descritos na Sec¸

ao 3.6 foram empregados para

extrair regras a partir das RNAs treinadas. Os resultados foram medidos e tes-

tes de hip

oteses foram realizados. Utilizando uma adaptac¸

ao desses m

etodos

para SVMs, os experimentos foram realizados novamente para extrair regras a

partir das SVMs treinadas para comparar os resultados. Esses resultados s

apresentados na pr

oxima sec¸

ao.

5.1.4 Resultados

A Tabela 5.1 mostra a taxa de erro obtida pelas RNAs, SVMs e os sistemas de

AM simb

olico C4.5, C4.5rules e CN2.

Os resultados dos sistemas de AM simb

olico com os conjuntos de dados

originais foram utilizados apenas para comparac¸

ao com as RNAs e SVMs. Os

melhores resultados est

ao em negrito. Pode ser observado que a RNA foi me-

lhor que os sistemas de AM simb

olicos para os conjuntos de dados promoters

e spliceEI. Nesses mesmos conjuntos de dados, a SVM foi melhor que a RNA.

O C4.5, um dos sistemas de AM simb

olico, obteve o melhor resultado para o

conjunto de dados spliceN.

Tabela 5.1: Taxa de Erro (m

edia e desvio padr

ao)(%).

promoters spliceEI spliceN

C4.5 16.91 ± 2.25 4.65 ± 0.54 4.16 ± 0.37

C4.5rules 15.18 ± 2.11 4.91 ± 0.40 4.72 ± 0.46

CN2 26.27 ± 4.21 5.77 ± 0.77 5.79 ± 0.46

RNA 14.09 ± 3.16 4.00 ± 0.44 6.55 ± 0.53

SVM 12.36 ± 2.16 2.88 ± 0.15 5.48 ± 0.36

A taxa de inﬁdelidade entre os m

etodos de extrac¸

ao de conhecimento e as

RNAs e SVMs foi medido usando o conjunto de teste. A taxa de inﬁdelidade

e a porcentagem dos exemplos do conjunto de teste em que a classiﬁcac¸

feita por uma RNA ou SVM discorda da classiﬁcac¸

ao feita pelo m

etodo utilizado

para explicar o comportamento da RNA ou SVM. A Tabela 5.2 mostra a taxa

de inﬁdelidade obtida pelos m

etodos de extrac¸

ao de conhecimento de RNAs

e a Tabela 5.3 mostra a taxa de inﬁdelidade obtida pelos mesmos m

etodos,

adaptados para extrac¸

ao de conhecimento de SVMs. AGPP

e o m

etodo baseado

em AGs com a fase de p

os-processamento descrita na Sec¸

ao 3.6.2.

A compreensibilidade sint

atica do conhecimento extra

ıdo pelos m

etodos de

extrac¸

ao de conhecimento foi medida utilizando o n

umero de regras induzi-

das e o n

umero m

edio de condic¸

oes induzidas por regra. As tabelas 5.4 e 5.5

mostram o n

umero m

edio de regras induzidas e as tabelas 5.6 e 5.7 mostram

Experimentos Realizados 71

o n

umero de condic¸

oes por regra induzida, para os casos de RNAs e SVMs res-

pectivamente. Em todas as tabelas os melhores resultados est

ao em negrito.

Tabela 5.2: Taxa de inﬁdelidade (RNAs - m

edia e desvio padr

ao)(%).

promoters spliceEI spliceN

C4.5 33.00 ± 4.28 5.96 ± 0.59 6.90 ± 0.38

C4.5rules 28.45 ± 4.32 6.48 ± 0.42 6.90 ± 0.42

CN2 30.09 ± 4.22 6.22 ± 0.93 8.66 ± 0.55

AG 28.18 ± 4.52 6.15 ± 0.56 9.10 ± 0.72

AGPP 27.18 ± 4.11 6.55 ± 0.65 10.45 ± 0.89

Tabela 5.3: Taxa de inﬁdelidade (SVMs - m

edia e desvio padr

ao)(%).

promoters spliceEI spliceN

C4.5 22.63 ± 3.21 3.80 ± 0.32 5.64 ± 0.32

C4.5rules 17.09 ± 2.78 5.31 ± 0.71 6.55 ± 0.40

CN2 23.54 ± 4.89 8.12 ± 0.58 7.40 ± 0.43

AG 17.00 ± 4.00 4.13 ± 0.49 6.24 ± 0.55

AGPP 26.27 ± 4.67 5.37 ± 0.74 8.54 ± 1.69

Tabela 5.4: N

umero de regras induzidas (RNAs - m

edia e desvio padr

ao).

promoters spliceEI spliceN

C4.5 15.70 ± 0.54 33.40 ± 1.40 85.90 ± 1.85

C4.5rules 6.90 ± 0.50 21.90 ± 0.84 60.40 ± 1.26

CN2 12.60 ± 0.34 44.60 ± 1.34 107.20 ± 0.90

AG 21.10 ± 2.46 37.60 ± 5.33 46.00 ± 11.06

AGPP 6.80 ± 0.74 16.00 ± 2.65 20.40 ± 4.46

Tabela 5.5: N

umero de regras induzidas (SVMs - m

edia e desvio padr

ao).

promoters spliceEI spliceN

C4.5 15.10 ± 1.19 34.00 ± 0.77 85.90 ± 2.41

C4.5rules 7.30 ± 0.47 22.00 ± 0.56 61.30 ± 1.40

CN2 12.30 ± 0.21 41.80 ± 0.76 112.00 ± 1.37

AG 15.30 ± 1.96 50.70 ± 6.73 89.90 ± 5.82

AGPP 5.20 ± 0.92 16.20 ± 2.57 31.20 ± 3.82

O teste de hip

oteses 10-fold cross-validated paired test Dietterich (1997) foi

utilizado para comparar as taxas de inﬁdelidade e compreensibilidade entre os

etodos de extrac¸

ao de conhecimento. De acordo com esse teste, a diferenc¸a

entre dois algoritmos

e estatisticamente signiﬁcante com 95% de conﬁabili-

dade, se o resultado desse teste

e maior do que 2.262 em valor absoluto.

72 Cap

ıtulo 5

Tabela 5.6: N

umero m

edio de condic¸

oes por regra induzida (RNAs - m

edia e

desvio padr

ao).

promoters spliceEI spliceN

C4.5 2.27 ± 0.03 4.21 ± 0.08 4.06 ± 0.04

C4.5rules 1.40 ± 0.03 2.23 ± 0.03 2.39 ± 0.02

CN2 1.98 ± 0.02 2.64 ± 0.03 3.30 ± 0.02

AG 2.01 ± 0.03 3.15 ± 0.08 3.45 ± 0.03

AGPP 1.78 ± 0.74 2.45 ± 0.13 2.77 ± 0.06

Tabela 5.7: N

umero m

edio de condic¸

oes por regra induzida (SVMs - m

edia e

desvio padr

ao).

promoters spliceEI spliceN

C4.5 2.24 ± 0.07 4.20 ± 0.05 4.06 ± 0.05

C4.5rules 1.52 ± 0.05 2.24 ± 0.04 2.37 ± 0.04

CN2 1.96 ± 0.02 2.59 ± 0.03 3.27 ± 0.02

AG 1.99 ± 0.07 3.42 ± 0.19 3.32 ± 0.21

AGPP 1.78 ± 0.09 2.30 ± 0.04 2.70 ± 0.14

As Tabelas 5.8 e 5.9 mostram os resultados do 10-fold cross-validated pai-

red test para RNAs e SVMs respectivamente. O s

ımbolo  indica que o m

etodo

baseado em AGs superou o m

etodo baseado em AM simb

olico enquanto o

ımbolo  indica que a superac¸

ao tem um n

ıvel de conﬁanc¸a maior que 95. Por

outro lado, os s

ımbolos  e  indicam que o m

etodo baseado em AM simb

olico

superou o m

etodo baseado em AG.

Comec¸ando com as RNAs, em relac¸

a taxa de inﬁdelidade, pode ser visto

que o m

etodo baseado em AGs foi melhor que as abordagens baseadas em

AM simb

olico para o conjunto de dados promoters, embora n

ao com 95 de

conﬁabilidade. Para o conjunto de dados spliceN, as abordagens baseadas

em AM simb

olico foram melhores que o m

etodo baseado em AGs com 95% de

conﬁanc¸a em quatro experimentos. Para o conjunto de dados spliceEI, os

resultados foram similares para todos os m

etodos.

Olhando o n

umero de regras, o m

etodo baseado em AGs foi melhor para

ambos os conjuntos de dados spliceEI e spliceN. Para o conjunto de dados

promoters, as abordagens simb

olicas foram melhores do que o m

etodo baseado

em AGs em tr

es experimentos e piores em dois deles, considerando apenas os

experimentos em que o teste de hip

oteses apresentou 95% de conﬁabilidade.

Finalmente, levando em considerac¸

ao o n

umero de condic¸

oes por regra, os

resultados obtidos foram similares para todos os conjuntos de dados.

No caso das SVMs, em relac¸

a taxa de inﬁdelidade, pode ser visto que

o m

etodo baseado em AGs foi melhor que as abordagens baseadas em AM

simb

olico para o conjunto de dados promoters e sua extens

ao com a fase de

Experimentos Realizados 73

Tabela 5.8: Resultados do 10-Fold Cross-Validated Paired t Test (RNAs).

promoters

Inﬁdelidade No. de Regras Cond./Regra

AG AGPP AG AGPP AG AGPP

C4.5      

C4.5rules      

CN2      

spliceEI

Inﬁdelidade No. de Regras Cond./Regra

AG AGPP AG AGPP AG AGPP

C4.5      

C4.5rules      

CN2      

spliceN

Inﬁdelidade No. de Regras Cond./Regra

AG AGPP AG AGPP AG AGPP

C4.5      

C4.5rules      

CN2      

os-processamento (AGPP) foi pior em todos os casos, embora n

ao com 95%

de conﬁabilidade. Para o conjunto de dados spliceEI, o m

etodo baseado em

AGs foi melhor que as abordagens baseadas em AM simb

olico com 95% de

conﬁabilidade em dois experimentos e pior em um deles. Para o conjunto de

dados spliceN, o m

etodo baseado em AGs foi melhor com 95% de conﬁabilidade

em apenas um experimento.

Quanto ao n

umero de regras, o m

etodo baseado em AGs com a fase de p

os-

processamento (AGPP) foi melhor em todos experimentos em todos os con-

juntos de dados com 95% de conﬁabilidade. A vers

ao sem a fase de p

os-

processamento foi pior em quase todos os experimentos. Somente no con-

junto de dados spliceN o m

etodo baseado em AGs sem o p

os-processamento

foi melhor em um dos experimentos.

Assim como no caso das RNAs, levando em considerac¸

ao o n

umero de

condic¸

oes por regra, os resultados obtidos foram similares para todos os con-

juntos de dados.

Por ﬁm, o 10-Fold Cross-Validated Paired t Test foi utilizado para comparar

os m

etodos de extrac¸

ao de conhecimento quando utilizados para extrair regras

de RNAs e quando utilizados para extrair regras de SVMs.

A Tabela 5.10 apresenta os resultados destes testes. O s

ımbolo ♦

e uti-

lizado para indicar a abordagem que obteve o melhor resultado e o s

ımbolo

 indica que o resultado

e estatisticamente signiﬁcante com mais de 95% de

conﬁabilidade.

E interessante notar que, em relac¸

a taxa de inﬁdelidade, quase todos

os experimentos tiveram melhores resultados quando aplicados a SVMs, sendo

74 Cap

ıtulo 5

Tabela 5.9: Resultados do 10-Fold Cross-Validated Paired t Test (SVMs).

promoters

Inﬁdelidade No. de Regras Cond./Regra

AG AGPP AG AGPP AG AGPP

C4.5      

C4.5rules      

CN2      

spliceEI

Inﬁdelidade No. de Regras Cond./Regra

AG AGPP AG AGPP AG AGPP

C4.5      

C4.5rules      

CN2      

spliceN

Inﬁdelidade No. de Regras Cond./Regra

AG AGPP AG AGPP AG AGPP

C4.5      

C4.5rules      

CN2      

Tabela 5.10: Comparac¸

ao da aplicac¸

ao de m

etodos de extrac¸

ao de regras em

RNAs e em SVMs).

promoters

Inﬁdelidade No. de Regras Cond./Regra

RNA SVM RNA SVM RNA SVM

C4.5  ♦ ♦

C4.5rules  ♦ ♦

CN2 ♦ ♦ ♦

AG ♦ ♦ ♦

AGPP ♦ ♦ ♦

spliceEI

Inﬁdelidade No. de Regras Cond./Regra

RNA SVM RNA SVM RNA SVM

C4.5  ♦ ♦

C4.5rules ♦ ♦ ♦

CN2 ♦ ♦ ♦

AG  ♦ ♦

AGPP ♦ ♦ ♦

spliceN

Inﬁdelidade No. de Regras Cond./Regra

RNA SVM RNA SVM RNA SVM

C4.5 ♦ ♦ ♦

C4.5rules ♦ ♦ ♦

CN2 ♦  ♦

AG   ♦

AGPP ♦ ♦ ♦

que 5 obtiveram 95% de conﬁabilidade no teste de hip

oteses. Apenas um expe-

rimento, no conjunto de dados spliceEI, obteve um melhor resultado quando

aplicado

a RNAs, e mesmo assim, n

ao com 95% de conﬁabilidade.

Em relac¸

ao ao n

umero de regras, os m

etodos foram melhores quando apli-

Experimentos Realizados 75

cados a RNAs nos conjuntos de dados spliceEI e spliceN e piores para o con-

junto promoters, por

em, de todos os experimentos, apenas dois obtiveram 95%

de conﬁabilidade.

Finalmente, em relac¸

ao ao n

umero de condic¸

oes por regra, os resultados

foram similares e nenhum experimento apresentou 95% de conﬁabilidade.

Esses resultados nos motivaram a investigar melhor a aplicac¸

ao de AGs

para otimizar regras geradas por sistemas de AM simb

olico para a extrac¸

ao de

regras. A comparac¸

ao entre a extrac¸

ao de regras de RNAs e SVMs utilizando

os m

etodos propostos por Milar

e (2003) foi bem interessante. Notou-se que

em relac¸

a ﬁdelidade, os m

etodos obtiveram melhores resultados quando

aplicados a SVMs.

Uma poss

ıvel explicac¸

ao para isso

e o fato de as SVMs terem tido uma

acur

acia maior na classiﬁcac¸

ao do que as RNAs. Observou-se ent

ao que a

ﬁdelidade dos m

etodos

e elevada em situac¸

oes em que ambos os sistemas de

aprendizado, caixa-preta e simb

olicos, t

em acur

acia elevada na classiﬁcac¸

do conjunto de dados original. Por

em, nesses casos em que a SVM tem alta

acur

acia de classiﬁcac¸

ao, observa-se que o conjunto de dados rotulado pela

SVM

e muito parecido com o conjunto de dados original e, sendo assim, as

regras extra

ıdas, apesar da alta ﬁdelidade, podem n

ao reﬂetir a forma com a

qual a SVM classiﬁca os exemplos.

Esse foi um dos fatores que nos motivaram a investir na investigac¸

ao da

extrac¸

ao de regras de SVMs, pois na

epoca n

ao encontramos nenhum trabalho

publicado com esse tema.

5.2 Fase II - Experimentos com o m

etodo RankSim

Nessa fase foram realizados experimentos com diversos conjuntos de dados

utilizando o m

etodo RankSim para extrair regras dos modelos induzidos por

SVMs. Nesses experimentos, o RankSim foi utilizado no modo classe original,

isto

e, sem que a SVM rotulasse os exemplos para a gerac¸

ao das regras a

serem otimizadas pelo algoritmo gen

etico. Nosso objetivo

e veriﬁcar se, com

a informac¸

ao obtida por meio da comparac¸

ao da similaridade dos rankings,

poss

ıvel extrair regras com boa ﬁdelidade e boa acur

acia, mesmo quando n

a r

otulos atribu

ıdos pela SVM aos exemplos.

A seguir, s

ao apresentados os resultados para os 17 conjuntos de dados

utilizados, retirados do Reposit

orio de AM da UCI (Blake and Merz, 1998).

Na Tabela 5.11 h

a um resumo das caracter

ısticas desses conjuntos. Assim

como na Fase I, os conjuntos de dados foram divididos utilizando a metodo-

logia k-fold stratiﬁed cross-validation, com k = 10, obtendo 10 conjuntos de

treinamento e 10 conjuntos de teste para cada conjunto de dados.

76 Cap

ıtulo 5

Para cada conjunto de dados, tr

es tabelas s

ao apresentadas. Na primeira

tabela, comparamos a acur

acia de tr

es indutores simb

olicos, da SVM e das

regras extra

ıdas pelo RankSim. Para cada uma dessas comparac¸

oes foi utili-

zado o teste de hip

oteses 10-fold cross-validated paired test, descrito na sec¸

anterior. Por ﬁm, a ﬁdelidade

e apresentada na

ultima coluna. Na segunda ta-

bela,

e apresentado o n

umero de regras geradas por cada indutor simb

olico e

o teste de hip

oteses tamb

e utilizado para realizar a comparac¸

ao com as re-

gras extra

ıdas. Analogamente, na terceira tabela, o n

umero de condic¸

oes por

regra de cada indutor

e apresentado e a mesma metodologia de comparac¸

utilizada.

Tabela 5.11: Descric¸

ao dos Conjuntos de Dados

Conjunto # Exemplos # Atributos Classe Classe Maj. (%)

breast 683 9 (positive,negative) 65.00

bupa 345 6 (positive,negative) 57.98

ecoli 336 7 (iMU,remainder) 89.58

ﬂag 194 28 (white,remainder) 91.24

ﬂare 1066 10 (positive,negative) 79.41

Glass 214 9 (Ve-win-ﬂoat-proc,rem.) 92.06

Haberman 306 3 (Die,Survive) 82.93

heart 267 22 (positive,negative) 55.55

pima 768 8 (1,0) 65.23

ionosphere 351 33 (positive,negative) 64.10

New-thyroid 215 5 (hypo,remainder) 83.72

Post-operative 90 8 (S,remainder) 73.33

Satimage 6435 36 (4,remainder) 90.27

SpliceN 3175 60 (positive,negative) 50.00

SpliceEI 1527 60 (EI,IE) 50.00

promoters 106 57 (positive,negative) 50.00

German 1000 20 (Bad,Good) 70.00

5.2.1 Conjunto breast

Como pode ser observado na Tabela 5.12, para esse conjunto de dados, to-

dos os classiﬁcadores, com excec¸

ao do CN2, tiveram uma boa acur

acia, com

um erro m

edio baixo. O RankSim, al

em de obter uma boa acur

acia, tamb

obteve uma boa ﬁdelidade. Isso signiﬁca que ele conseguiu, por meio da simi-

laridade dos rankings, escolher boas regras, em sua maioria provenientes do

C4.5 e C4.5rules, uma vez que a acur

acia do CN2 foi baix

ıssima. No teste de

hip

oteses, apenas o CN2 foi pior em acur

acia, com 95% de conﬁabilidade, em

relac¸

ao ao RankSim. A diferenc¸a de acur

acia entre o RankSim e os outros n

e signiﬁcativa.

Em relac¸

ao ao n

umeros de regras, apresentados na Tabela 5.13, novamente

o CN2 foi pior, com 95% de conﬁabilidade em relac¸

ao ao RankSim. Os outros

Experimentos Realizados 77

Tabela 5.12: Conjunto breast - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 4.68 4.83 56.48 5.27 4.98 5.26

Desvio Padr

ao 0.47 0.54 0.59 0.80 1.25 0.98

Teste T -0.26 -0.15 33.04 0.20

sistemas induziram menos regras do que o RankSim, mas n

ao tiveram 95%

de conﬁabilidade no teste de hip

oteses.

Tabela 5.13: Conjunto breast - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 10.60 9.40 15.30 11.90

Desvio Padr

ao 0.56 0.40 0.47 1.35

Teste T -0.83 -1.73 2.68

Em condic¸

oes por regra, a Tabela 5.14 mostra que o RankSim foi melhor

que o C4.5 e pior que o C4.5rules, com 95% de conﬁabilidade, e foi equivalente

ao CN2.

Tabela 5.14: Conjunto breast - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 3.98 2.32 2.72 2.85

Desvio Padr

ao 0.12 0.05 0.04 0.17

Teste T 8.41 -2.79 -0.76

5.2.2 Conjunto bupa

Neste conjunto de dados houve um equil

ıbrio estat

ıstico na acur

acia de todos

os classiﬁcadores, por

em, o melhor foi o C4.5rules, como pode ser veriﬁcado

na Tabela 5.15.

E interessante notar que nesse conjunto de dados, a taxa de

ﬁdelidade do RankSim

e maior que sua taxa de acur

acia, apesar de ambos

valores serem relativamente altos.

Tabela 5.15: Conjunto bupa - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 35.08 31.29 34.44 37.97 36.29 31.89

Desvio Padr

ao 2.55 1.79 3.12 2.25 1.83 1.85

Teste T -0.36 -1.83 -0.50 0.49

De acordo com a Tabela 5.16, em relac¸

ao ao n

umero de regras, o C4.5rules

78 Cap

ıtulo 5

foi melhor que o RankSim com 95% de conﬁabilidade. Os outros indutores

foram piores que o RankSim.

Tabela 5.16: Conjunto bupa - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 29.50 15.70 31.80 28.10

Desvio Padr

ao 1.97 1.10 0.70 3.10

Teste T 0.83 -4.78 1.31

A Tabela 5.17 mostra que, em relac¸

a quantidade de condic¸

oes por regra,

o RankSim foi melhor que o C4.5 e pior que o C4.5rules e CN2, todos com

95% de conﬁabilidade.

Tabela 5.17: Conjunto bupa - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 5.96 3.11 3.37 4.20

Desvio Padr

ao 0.22 0.07 0.04 0.16

Teste T 20.22 -6.93 -5.00

5.2.3 Conjunto ecoli

Assim como no conjunto bupa, pode se veriﬁcar no conjunto ecoli, na Ta-

bela 5.18, que a ﬁdelidade do m

etodo RankSim foi maior que sua acur

acia,

por

em, nesse caso, tanto a acur

acia quanto a ﬁdelidade apresentam boas ta-

xas. Comparativamente, a acur

acia do RankSim foi pior que a do C4.5 com

95% de conﬁabilidade, pior que a do C4.5rules, por

em, foi melhor que a do

CN2 com 95% de conﬁabilidade e foi praticamente equivalente

a da SVM no

teste de hip

oteses T.

Tabela 5.18: Conjunto ecoli - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 7.74 8.94 30.53 11.02 10.41 5.35

Desvio Padr

ao 1.27 1.19 2.99 0.91 1.01 1.45

Teste T -2.87 -1.34 6.06 0.41

Como pode ser visto na Tabela 5.19, nesse conjunto de dados, o RankSim

foi melhor que todos os outros indutores em relac¸

a quantidade de regras

induzidas, sendo que em relac¸

ao ao C4.5 a diferenc¸a

e estatisticamente signi-

ﬁcante com 95% de conﬁabilidade.

Experimentos Realizados 79

Tabela 5.19: Conjunto ecoli - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 10.00 7.40 14.40 6.80

Desvio Padr

ao 1.24 0.50 0.34 0.79

Teste T 2.63 0.97 7.58

a em relac¸

ao ao n

umero de condic¸

oes por regra, a Tabela 5.20 mostra que

o RankSim ganha apenas do C4.5, com 95% de conﬁabilidade, e perde para

os outros indutores.

Tabela 5.20: Conjunto ecoli - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 4.31 2.47 2.45 2.74

Desvio Padr

ao 0.31 0.10 0.04 0.30

Teste T 7.82 -0.98 -0.97

5.2.4 Conjunto ﬂag

Na Tabela 5.21 vemos mais um conjunto em que a ﬁdelidade foi maior do que

a acur

acia do m

etodo RankSim. A acur

acia do RankSim nesse conjunto de

dados foi maior do que a dos dois indutores simb

olicos e pior do que a do

C4.5rules, por

em nenhum resultado obteve 95% de conﬁabilidade no teste T.

Tabela 5.21: Conjunto ﬂag - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 15.45 10.79 14.81 10.84 11.84 6.16

Desvio Padr

ao 2.01 1.17 0.12 1.45 1.72 1.46

Teste T 1.50 -0.82 1.66 -0.59

Em relac¸

ao ao n

umero de regras,

e poss

ıvel veriﬁcar, na Tabela 5.22, que

o RankSim foi inferior ao C4.5 e superior ao CN2 com 95% de conﬁabilidade.

Em relac¸

ao ao C4.5rules, o RankSim foi inferior, mas n

ao com 95% de conﬁa-

bilidade.

Tabela 5.22: Conjunto ﬂag - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 1.00 8.50 17.80 9.80

Desvio Padr

ao 0.00 0.69 0.42 0.92

Teste T -9.60 -1.13 7.75

80 Cap

ıtulo 5

Na Tabela 5.23 veriﬁca-se que, em relac¸

ao ao n

umero de condic¸

oes por

regra, no conjunto ﬂag, o RankSim foi superior em todos os casos e o resultado

do teste T atestou 95% de conﬁabilidade para o C4.5 e CN2.

Tabela 5.23: Conjunto ﬂag - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 3.00 1.86 2.25 1.70

Desvio Padr

ao 0.00 0.09 0.05 0.09

Teste T 14.24 2.06 7.35

5.2.5 Conjunto ﬂare

Na Tabela 5.24

e poss

ıvel notar que, apesar do grande erro de classiﬁcac¸

das regras geradas pelo CN2, o m

etodo RankSim conseguiu ﬁltrar essas re-

gras e selecionar as regras que, pela similaridade de rankings, tivessem mais

chance de ter uma boa ﬁdelidade. Nota-se tamb

em que a acur

acia do m

etodo

RankSim foi a maior entre todos os classiﬁcadores, com 95% de conﬁabilidade

em relac¸

ao ao C4.5 e ao CN2.

Tabela 5.24: Conjunto ﬂare - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 19.51 18.57 80.52 18.39 17.35 7.41

Desvio Padr

ao 0.49 0.91 2.13 0.50 0.80 1.17

Teste T 3.97 1.91 28.86 1.56

E interessante notar tamb

em, na Tabela 5.25, que o CN2, que foi o pior

classiﬁcador,

e tamb

em o com o maior n

umero de regras. Isso signiﬁca que

apesar da abundancia das regras do CN2, que tiveram uma acur

acia ruim,

o RankSim conseguiu evitar a selec¸

ao dessas regras. Quanto ao n

umero de

regras do SimRank, ele s

o teve menos regras que o CN2, sendo superado nessa

etrica pelo C4.5 com 95% de conﬁabilidade.

Tabela 5.25: Conjunto ﬂare - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 2.80 13.00 83.00 14.40

Desvio Padr

ao 1.80 0.73 1.79 1.80

Teste T -4.81 -0.68 27.49

No n

umero de condic¸

oes por regra, ilustrado na Tabela 5.26, o RankSim

apenas foi melhor que o CN2, com 95% de conﬁabilidade. Perdendo para o

C4.5rules, com 95% de conﬁabilidade, e para o C4.5.

Experimentos Realizados 81

Tabela 5.26: Conjunto ﬂare - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 3.01 2.13 3.55 3.07

Desvio Padr

ao 0.01 0.12 0.02 0.09

Teste T -0.69 -5.73 5.37

5.2.6 Conjunto glass

No conjunto glass, a Tabela 5.27 mostra que a acur

acia do RankSim foi infe-

rior

a dos outros indutores. Sua ﬁdelidade, foi um pouco melhor do que sua

acur

acia.

Tabela 5.27: Conjunto glass - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 8.42 7.97 16.23 7.92 16.47 14.13

Desvio Padr

ao 1.19 1.24 0.12 0.69 4.17 5.30

Teste T -2.01 -2.19 -0.06 -1.99

Por

em, nesse conjunto o m

etodo RankSim foi o que teve o menor n

umero

de regras, como pode ser visto na Tabela 5.28.

Tabela 5.28: Conjunto glass - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 8.00 7.80 13.80 7.70

Desvio Padr

ao 0.54 0.51 0.29 0.45

Teste T 0.41 0.15 14.08

Em relac¸

ao ao n

umero de condic¸

oes por regra, a Tabela 5.29 indica que o

etodo RankSim foi equivalente ao C4.5rules, melhor que o C4.5 e pior que o

CN2. Esses

ultimos dois resultados com 95% de conﬁabilidade.

Tabela 5.29: Conjunto glass - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 4.13 2.36 1.85 2.55

Desvio Padr

ao 0.14 0.08 0.02 0.12

Teste T 8.80 -1.70 -5.46

5.2.7 Conjunto haberman

Esse resultado em especial

e bem interessante pois, como pode ser visto na

Tabela 5.30, o m

etodo RankSim teve uma acur

acia melhor do que todos os

82 Cap

ıtulo 5

outros indutores, sendo que, para o C4.5 e C4.5rules, o teste T relatou mais

do que 95% de conﬁabilidade. E, novamente, o erro m

edio da ﬁdelidade foi

menor do que o erro m

edio da acur

acia.

Tabela 5.30: Conjunto haberman - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 29.74 29.74 29.82 28.15 25.81 13.44

Desvio Padr

ao 2.03 2.03 1.64 2.03 2.08 2.23

Teste T 2.46 2.46 1.25 1.37

Conforme exposto na Tabela 5.31, o n

umero de regras induzidas pelo Rank-

Sim por

em foi bem acima do n

umero de regras induzidas pelo C4.5 e C4.5rules

e bem abaixo do n

umero de regras induzido pelo CN2, todos os resultados com

95% de conﬁabilidade no teste T.

Tabela 5.31: Conjunto haberman - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 3.10 4.40 51.20 15.10

Desvio Padr

ao 0.38 0.27 1.26 1.22

Teste T -12.42 -8.70 16.69

Em relac¸

ao ao n

umero de condic¸

oes por regra, na Tabela 5.32, o RankSim

foi melhor que o CN2 e pior que os demais, com 95% de conﬁabilidade.

Tabela 5.32: Conjunto haberman - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 2.54 1.96 3.25 3.02

Desvio Padr

ao 0.13 0.08 0.02 0.06

Teste T -3.28 -11.10 3.30

5.2.8 Conjunto heart

Como pode ser visto na Tabela 5.33, o conjunto heart

e um dos poucos em que

a ﬁdelidade foi pior do que a acur

acia do m

etodo. Os resultados sugerem que

isso se deve

a baixa acur

acia alcanc¸ada pela SVM nesse conjunto de dados e

os indutores simb

olicos, por terem induzido boas regras, n

ao geraram regras

que resultassem em uma alta similaridade.

Conforme a Tabela 5.34, no conjunto heart, o m

etodo RankSim apresentou

o maior n

umero de regras entre os indutores simb

olicos, em dois casos o

resultado foi signiﬁcativo com 95% de conﬁabilidade.

Experimentos Realizados 83

Tabela 5.33: Conjunto heart - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 22.59 19.26 46.32 40.00 20.74 36.30

Desvio Padr

ao 1.95 2.33 1.87 2.46 2.42 2.69

Teste T 0.86 -0.74 8.97 8.05

Tabela 5.34: Conjunto heart - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 17.80 12.70 20.40 23.00

Desvio Padr

ao 0.79 0.93 0.58 2.13

Teste T -2.55 -5.21 -1.13

No n

umero de condic¸

oes por regra, pode ser visto na Tabela 5.35 que o

RankSim s

o foi melhor que o C4.5. Em todos os resultados a signiﬁc

ancia

teve 95% de conﬁabilidade.

Tabela 5.35: Conjunto heart - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 4.87 2.89 3.23 3.56

Desvio Padr

ao 0.12 0.06 0.03 0.12

Teste T 13.54 -4.69 -2.79

5.2.9 Conjunto pima

Como pode ser visto na Tabela 5.36, em relac¸

ao a acur

acia, o SimRank teve

um desempenho melhor do que o CN2 e a SVM com 95% de conﬁabilidade.

Em relac¸

ao aos outros indutores a diferenc¸a foi pequena. Nesse conjunto, a

ﬁdelidade foi um pouco melhor do que a acur

acia.

Tabela 5.36: Conjunto pima - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 24.22 25.13 44.94 35.81 26.30 25.13

Desvio Padr

ao 1.18 1.16 0.77 1.14 1.69 1.87

Teste T -1.46 -0.87 8.86 5.64

Em relac¸

ao ao n

umero de regras, na Tabela 5.37 pode ser visto que o

etodo RankSim foi melhor que o CN2 e pior que o C4.5rules, com 95% de

conﬁabilidade. Al

em disso, o RankSim foi um pouco pior que o C4.5 nesse

quesito.

84 Cap

ıtulo 5

Tabela 5.37: Conjunto Pima - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 23.60 12.40 45.20 25.50

Desvio Padr

ao 2.16 0.88 0.85 3.89

Teste T -0.63 -3.83 5.01

Em condic¸

oes por regra, na Tabela 5.38 pode ser identiﬁcado que o Rank-

Sim superou o C4.5 e foi superado pelo C4.5rules e pelo CN2, com 95% de

conﬁabilidade.

Tabela 5.38: Conjunto Pima - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 5.94 3.18 3.47 4.10

Desvio Padr

ao 0.29 0.14 0.04 0.22

Teste T 12.20 -5.21 -2.84

5.2.10 Conjunto ionosphere

Conforme a Tabela 5.39, no conjunto ionosphere, a acur

acia do SimRank

superou a do CN2 e foi superada pela da SVM, com 95% de conﬁabilidade.

Nesse conjunto, a ﬁdelidade tamb

em teve um resultado melhor que a acur

acia.

Tabela 5.39: Conjunto ionosphere - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 10.26 9.69 49.95 6.56 14.78 10.51

Desvio Padr

ao 1.66 1.43 1.13 1.48 2.74 1.96

Teste T -1.53 -1.87 10.29 -4.00

Em relac¸

ao ao n

umero de regras, a Tabela 5.40 mostra que o RankSim foi

melhor que o CN2 com 95% de conﬁabilidade. A diferenc¸a em relac¸

ao aos

outros indutores n

ao foi estatisticamente signiﬁcante.

Tabela 5.40: Conjunto ionosphere - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 14.20 10.40 18.40 12.60

Desvio Padr

ao 0.76 0.58 0.58 1.68

Teste T 1.16 -1.62 3.48

A Tabela 5.41 mostra que em relac¸

ao ao n

umero de condic¸

oes por re-

gra, o m

etodo SimRank foi melhor que o C4.5 e pior que os outros indutores

simb

olicos, com 95% de conﬁabilidade.

Experimentos Realizados 85

Tabela 5.41: Conjunto ionosphere - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 5.80 2.35 2.58 4.10

Desvio Padr

ao 0.16 0.11 0.04 0.20

Teste T 9.06 -8.38 -7.32

5.2.11 new-thyroid

No conjunto new-thyroid, pode ser observado na Tabela 5.42 que a acur

acia

do m

etodo foi melhor que a do CN2, com 95% de conﬁabilidade e tamb

em foi

melhor que a do C4.5, perdendo somente para a SVM e para o C4.5rules por

uma diferenc¸a m

ınima. A ﬁdelidade do m

etodo nesse conjunto foi melhor do

que sua acur

acia, mesmo com esses valores de erro baixos.

E interessante

ressaltar que, nesse conjunto de dados, o CN2 teve uma acur

acia extrema-

mente baixa, enquanto os outros indutores tiveram uma boa acur

acia.

Tabela 5.42: Conjunto new-thyroid - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 4.59 2.77 50.39 1.86 2.79 1.84

Desvio Padr

ao 1.66 1.40 1.64 1.02 1.02 1.01

Teste T 1.47 -0.03 18.38 -0.82

Em relac¸

ao ao n

umero de regras, a Tabela 5.43 indica que o m

etodo s

o foi

pior que o C4.5, por

em, nenhum resultado teve 95% de conﬁabilidade no teste

Tabela 5.43: Conjunto new-thyroid - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 4.60 5.80 6.00 5.50

Desvio Padr

ao 0.43 0.29 0.21 0.58

Teste T -1.20 0.46 0.96

Na Tabela 5.44

e poss

ıvel ver que o RankSim foi melhor que os outros indu-

tores simb

olicos, sendo que, no caso do C4.5, foi com 95% de conﬁabilidade.

Tabela 5.44: Conjunto new-thyroid - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 2.90 1.94 2.02 1.84

Desvio Padr

ao 0.14 0.04 0.07 0.13

Teste T 9.73 0.85 1.29

86 Cap

ıtulo 5

5.2.12 Conjunto post-operative

Nesse conjunto de dados, todos os indutores tiveram uma acur

acia baixa,

com excec¸

ao do CN2 que teve uma excelente acur

acia.

E interessante notar

que, como o objetivo do algoritmo gen

etico

e otimizar a similaridade entre

os rankings e a SVM teve uma acur

acia baixa nesse conjunto de dados, o

etodo RankSim n

ao aproveitou a acur

acia das regras do CN2 e a ﬁdelidade

do m

etodo nesse conjunto foi bem maior do que sua acur

acia, como pode ser

observado na Tabela 5.45.

Tabela 5.45: Conjunto post-operative - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 32.36 42.36 5.78 43.61 43.61 20.28

Desvio Padr

ao 4.20 5.54 0.14 4.83 4.22 5.14

Teste T -2.00 -0.39 -8.97 0.00

Na Tabela 5.46

e poss

ıvel observar que, em relac¸

ao ao n

umero de regras, o

etodo RankSim somente foi melhor que o CN2, com 95% de conﬁabilidade.

Tabela 5.46: Conjunto post-operative - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 1.40 5.00 22.80 15.10

Desvio Padr

ao 0.27 0.26 0.53 1.18

Teste T -10.98 -8.44 5.44

Em relac¸

ao ao n

umero de condic¸

oes por regra, novamente o RankSim foi

melhor do que o CN2 e pior que o C4.5rules e C4.5, sendo que somente o

ultimo resultado n

ao teve 95% de conﬁabilidade, como pode ser visto na Ta-

bela 5.47.

Tabela 5.47: Conjunto post-operative - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 2.73 2.42 3.04 2.89

Desvio Padr

ao 0.18 0.06 0.04 0.06

Teste T -0.72 -5.12 3.32

5.2.13 Conjunto satimage

No conjunto satimage, como mostra a Tabela 5.48, o RankSim foi melhor que

o CN2 e pior que os outros indutores no quesito acur

acia, com 95% de conﬁ-

abilidade. Nesse conjunto a ﬁdelidade tamb

em foi mais alta que a acur

acia.

Experimentos Realizados 87

Tabela 5.48: Conjunto satimage - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 8.97 7.60 78.13 8.35 13.04 8.64

Desvio Padr

ao 0.26 0.26 0.02 0.13 1.86 3.56

Teste T -2.05 -2.66 34.93 -2.52

Como mostra a Tabela 5.49, em n

umero de regras, o RankSim foi muito

melhor que os outros indutores, com 95% de conﬁabilidade.

Tabela 5.49: Conjunto satimage - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 153.20 41.30 69.90 18.60

Desvio Padr

ao 2.35 1.90 1.28 2.65

Teste T 38.71 7.86 17.04

Por

em, em relac¸

as condic¸

oes por regra, o RankSim s

o foi melhor que o

C4.5, com 95% de conﬁabilidade, como mostra a Tabela 5.50.

Tabela 5.50: Conjunto satimage - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 12.33 4.59 3.25 7.91

Desvio Padr

ao 0.24 0.15 0.03 0.49

Teste T 8.99 -6.16 -9.56

5.2.14 Conjunto spliceN

Nesse conjunto, como pode ser visto na Tabela 5.51, a acur

acia do RankSim

foi melhor do que a do CN2 e pior do que a dos outros indutores, com 95% de

conﬁabilidade. A similaridade foi equivalente

a acur

acia.

Tabela 5.51: Conjunto spliceN - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 5.95 4.47 69.97 3.28 17.42 17.73

Desvio Padr

ao 0.33 0.26 0.36 0.35 4.57 4.62

Teste T -2.60 -2.85 11.10 -3.28

Em relac¸

ao ao n

umero de regras, como mostra a Tabela 5.52, o m

etodo

RankSim foi melhor com 95% de conﬁabilidade em todos os casos.

Em relac¸

ao ao n

umero de condic¸

oes por regra, como mostra a Tabela 5.53,

o RankSim foi melhor que o CN2 e com 95% de conﬁabilidade foi melhor que

o C4.5 e pior que o C4.5rules.

88 Cap

ıtulo 5

Tabela 5.52: Conjunto spliceN - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 88.00 63.40 120.70 23.10

Desvio Padr

ao 1.26 0.81 0.99 4.41

Teste T 14.25 8.54 21.56

Tabela 5.53: Conjunto spliceN - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 4.10 2.34 3.44 3.27

Desvio Padr

ao 0.03 0.02 0.01 0.08

Teste T 11.30 -12.95 2.12

5.2.15 Conjunto spliceEI

Na Tabela 5.54 pode ser observado que a acur

acia do RankSim foi melhor do

que a do CN2 e pior nos outros casos, com 95% de conﬁabilidade em todos os

testes exceto para o C4.5.

Tabela 5.54: Conjunto spliceEI - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 5.76 5.10 60.94 2.16 9.09 8.64

Desvio Padr

ao 0.67 0.54 0.46 0.60 1.72 1.33

Teste T -2.05 -2.60 26.69 -3.93

Em relac¸

ao ao n

umero de regras, como pode ser visto na Tabela 5.55, o

RankSim foi melhor que o CN2 com 95% de conﬁabilidade, melhor que C4.5 e

pior que o C4.5rules.

Tabela 5.55: Conjunto spliceEI - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 35.20 26.10 45.20 27.10

Desvio Padr

ao 1.11 0.94 1.08 3.45

Teste T 1.92 -0.27 6.17

Na Tabela 5.56,

e poss

ıvel veriﬁcar que o RankSim foi superior, no quesito

umero de condic¸

oes por regra ao C4.5 e inferior aos outros, com 95% de

conﬁabilidade.

5.2.16 Conjunto promoters

Na Tabela 5.57

e possivel ver que no conjunto promoters, a acur

acia do

etodo RankSim foi superior a do CN2 com 95% de conﬁabilidade, superior

Experimentos Realizados 89

Tabela 5.56: Conjunto spliceEI - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 4.43 2.38 2.69 2.91

Desvio Padr

ao 0.06 0.03 0.03 0.08

Teste T 13.49 -6.16 -2.62

ao C4.5 e inferior ao C4.5rules.

Tabela 5.57: Conjunto promoters - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 17.91 15.09 58.11 8.27 15.91 16.91

Desvio Padr

ao 2.86 3.51 3.14 2.13 3.30 3.77

Teste T 0.43 -0.14 9.21 -2.11

a em n

umero de regras, a Tabela 5.58 mostra que o m

etodo RankSim foi

pior que o C4.5rules com 95% de conﬁabilidade, pior que o CN2 e melhor que

o C4.5.

Tabela 5.58: Conjunto promoters - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 16.90 9.60 14.60 15.40

Desvio Padr

ao 0.78 0.43 0.27 0.92

Teste T 1.45 -4.50 -0.97

Em condic¸

oes por regra, a Tabela 5.59 mostra que o m

etodo RankSim foi

melhor que o C4.5 e CN2, por

em, foi pior que o C4.5rules, com 95% de conﬁ-

abilidade.

Tabela 5.59: Conjunto promoters - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 2.43 1.67 2.06 1.97

Desvio Padr

ao 0.04 0.03 0.01 0.03

Teste T 9.19 -8.79 2.51

5.2.17 Conjunto german

No conjunto german,

e poss

ıvel ver na Tabela 5.60, que em acur

acia o Rank-

Sim foi melhor que o CN2 e que a SVM com 95% de conﬁabilidade, melhor que

o C4.5 e pior que o C4.5rules.

90 Cap

ıtulo 5

Tabela 5.60: Conjunto german - Acur

acia e Fidelidade (%).

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

Erro M

edio 31.90 27.80 45.38 32.80 29.80 14.40

Desvio Padr

ao 0.90 1.04 1.04 0.81 0.55 1.42

Teste T 1.63 -1.47 12.48 2.54

Na Tabela 5.61

e poss

ıvel veriﬁcar que em relac¸

ao ao n

umero de regras o

RankSim foi melhor que todos os outros indutores, em dois casos com 95% de

conﬁabilidade no teste T.

Tabela 5.61: Conjunto german - N

umero de Regras.

C4.5 C4.5Rules CN2 RankSim

Regras 89.50 25.40 82.50 25.20

Desvio Padr

ao 3.83 2.37 2.04 5.07

Teste T 8.33 0.03 9.44

Por ﬁm, Tabela 5.62

e poss

ıvel veriﬁcar que em condic¸

oes por regra, o

RankSim apenas foi melhor que o C4.5, com 95% de conﬁabilidade.

Tabela 5.62: Conjunto german - N

umero de Condic¸

oes por Regra.

C4.5 C4.5Rules CN2 RankSim

Condic¸

oes por Regra 5.53 2.74 3.61 4.21

Desvio Padr

ao 0.12 0.07 0.03 0.12

Teste T 12.63 -11.64 -5.05

5.3 Considerac¸

oes Finais

Este cap

ıtulo apresentou os resultados experimentais desta Tese. Sumari-

zando os resultados, s

ao apresentadas as tabelas 5.63, 5.64 , 5.65 e 5.66.

Segundo a Tabela 5.63, o m

etodo proposto apresentou elevada ﬁdelidade,

com erro inferior a 10% em 7 dos conjuntos de dados e inferior a 20% em 13

dos conjuntos. Para v

arios conjuntos de dados, a acur

acia m

edia obtida pelo

etodo proposto, RankSim, foi semelhante a acur

acia obtida pelas t

ecnicas

simb

olicas.

E importante observar que as regras do RankSim foram otimi-

zadas para melhorar a ﬁdelidade, n

ao a acur

acia. Nesse sentido, observa-se

que o objetivo foi atingido pois em 13 dos 17 conjuntos, a ﬁdelidade teve um

erro m

edio menor do que o erro m

edio da acur

acia. Mesmo assim, em dois

dos conjuntos de dados investigados, haberman e ﬂare, a acur

acia obtida pelo

etodo RankSim foi superior a acur

acia obtida por todas as t

ecnica sinb

olicas.

A menos da base pos-operative, RankSim foi sempre superior

a t

ecnica CN2.

Experimentos Realizados 91

Tabela 5.63: Acur

acia e Fidelidade(%)

C4.5 C4.5Rules CN2 SVM RankSim Fidelidade

breast 4.68 4.83 56.48 5.27 4.98 5.26

bupa 35.08 31.29 34.44 37.97 36.29 31.89

ecoli 7.74 8.94 30.53 11.02 10.41 5.35

ﬂag 15.45 10.79 14.81 10.84 11.84 6.16

ﬂare 19.51 18.57 80.52 18.39 17.35 7.41

glass 8.42 7.97 16.23 7.92 16.47 14.13

haberman 29.74 29.74 29.82 28.15 25.81 13.44

heart 22.59 19.26 46.32 40.00 20.74 36.30

pima 24.22 25.13 44.94 35.81 26.30 25.13

ionosphere 10.26 9.69 49.95 6.56 14.78 10.51

new-thyroid 4.59 2.77 50.39 1.86 2.79 1.84

post-operative 32.36 42.36 5.78 43.61 43.61 20.28

satimage 8.97 7.60 78.13 8.35 13.04 8.64

spliceN 5.95 4.47 69.97 3.28 17.42 17.73

spliceEI 5.76 5.10 60.94 2.16 9.09 8.64

promoters 17.91 15.09 58.11 8.27 15.91 16.91

German 31.90 27.80 45.38 32.80 29.80 14.40

As tabelas 5.64 e 5.65 mostram o n

umero m

edio de regras e o n

umero

de m

edio de condic¸

oes ou antecedente por regras, que podem ser utilizadas

como medidas de compreensibilidade do conjunto de regras. De acordo com

os valores apresentados, a compreensibilidade das regras geradas pelo Rank-

Sim foram semelhantes aos das t

ecnicas simb

olicas. V

arias vezes o RankSim

apresentou em m

edia menos regras e menor n

umero m

edio de antecedentes

por regra. Na maoiria das vezes, RankSim gerou menos regras que o CN2.

Tabela 5.64: N

umero de Regras

C4.5 C4.5Rules CN2 RankSim

breast 10.60 9.40 15.30 11.90

bupa 29.50 15.70 31.80 28.10

ecoli 10.00 7.40 14.40 6.80

ﬂag 1.00 8.50 17.80 9.80

ﬂare 2.80 13.00 83.00 14.40

glass 8.00 7.80 13.80 7.70

haberman 3.10 4.40 51.20 15.10

heart 17.80 12.70 20.40 23.00

pima 23.60 12.40 45.20 25.50

ionosphere 14.20 10.40 18.40 12.60

new-thyroid 4.60 5.80 6.00 5.50

post-operative 1.40 5.00 22.80 15.10

satimage 153.20 41.30 69.90 18.60

spliceN 88.00 63.40 120.70 23.10

spliceEI 35.20 26.10 45.20 27.10

promoters 16.90 9.60 14.60 15.40

German 89.50 25.40 82.50 25.20

92 Cap

ıtulo 5

Tabela 5.65: N

umero de Condic¸

oes por Regra

C4.5 C4.5Rules CN2 RankSim

breast 3.98 2.32 2.72 2.85

bupa 5.96 3.11 3.37 4.20

ecoli 4.31 2.47 2.45 2.74

ﬂag 3.00 1.86 2.25 1.70

ﬂare 3.01 2.13 3.55 3.07

glass 4.13 2.36 1.85 2.55

haberman 2.54 1.96 3.25 3.02

heart 4.87 2.89 3.23 3.56

pima 5.94 3.18 3.47 4.10

ionosphere 5.80 2.35 2.58 4.10

new-thyroid 2.90 1.94 2.02 1.84

post-operative 2.73 2.42 3.04 2.89

satimage 12.33 4.59 3.25 7.91

spliceN 4.10 2.34 3.44 3.27

spliceEI 4.43 2.38 2.69 2.91

promoters 2.43 1.67 2.06 1.97

German 5.53 2.74 3.61 4.21

Por ﬁm, na Tabela 5.66 apresentamos os resultados iniciais de uma com-

parac¸

ao, utilizando a m

etrica ﬁdelidade, entre as duas variantes do m

etodo

RankSim (uma utilizando exemplos originais e a outra utilizando exemplos

rotulados pela SVM) e o m

etodo NNRules. Todos os experimentos foram reali-

zados com os mesmos par

ametros do algoritmo gen

etico e da SVM.

Nesses experimentos, foi poss

ıvel observar que, dos 13 conjuntos de da-

dos utilizados nesses experimentos, o RankSim Original foi o melhor m

etodo

em 7 conjuntos, RankSim Rotulado foi o melhor em 3 conjuntos e o NNRu-

les foi o melhor em 3 conjuntos. Mais experimentos e os testes de hip

oteses

necess

arios para validar essa comparac¸

ao ser

ao realizados nos trabalhos fu-

turos.

No pr

oximo cap

ıtulo, as principais conclus

oes deste trabalho s

ao apresen-

tadas.

Experimentos Realizados 93

Tabela 5.66: Fidelidade: RankSim Original, RankSim Rotulado e NNRules

RankSim Orig RankSim Rotulado NNRules SVM

breast 5.26% ± 0.98 9.22% ± 2.89 4.54% ± 0.51

bupa 31.89% ± 1.85 35.31% ± 2.87 35.67% ± 2.15

ecoli 5.35% ± 1.45 7.73% ± 1.67 8.63% ± 1.21

ﬂag 6.16% ± 1.46 5.13% ± 1.08 12.37% ± 2.37

ﬂare 7.41% ± 1.17 7.50% ± 0.98 18.95% ± 0.51

glass 14.13% ± 5.30 20.74% ± 5.92 12.21% ± 2.67

haberman 13.44% ± 2.23 12.45% ± 2.24 28.12% ± 1.41

heart 36.30% ± 2.69 34.44% ± 2.65 20.37% ± 2.01

pima 25.13% ± 1.87 28.64% ± 2.08 25.40% ± 1.21

ionosphere 10.51% ± 1.96 11.13% ± 2.39 10.83% ± 1.94

new±thyroid 1.84% ± 1.01 2.75% ± 1.55 4.16% ± 1.72

post±operative 20.28% ± 5.14 19.17% ± 6.86 40.28% ± 2.52

German 14.40% ± 1.42 16.40% ± 2.08 28.20% ± 0.94

CAP

ITULO

Conclus

este cap

ıtulo apresentamos as principais conclus

oes deste trabalho.

Na Sec¸

ao 6.1 apresentamos um resumo dos objetivos e resultados

alcanc¸ados. Na Sec¸

ao 6.2 apresentamos as limitac¸

oes dos m

etodos

propostos neste trabalho e,por ﬁm, na Sec¸

ao 6.3 apresentamos os trabalhos

futuros.

6.1 Resumo dos objetivos e resultados

O objetivo principal deste trabalho foi investigar e propor m

etodos para ex-

trac¸

ao de conhecimento, na forma de regras, a partir de modelos de classiﬁ-

cadores induzidos por t

ecnicas caixa-preta de Aprendizado de M

aquina. No

decorrer do trabalho, o foco foi direcionado para as M

aquinas de Vetores de

Suporte (SVMs), pois era uma

area que estava em ascens

ao e n

ao haviam tra-

balhos sobre extrac¸

ao de regras para esse tipo de t

ecnica de Aprendizado de

aquina at

e ent

ao. Por

em, o m

etodo

e geral o suﬁciente para ser aplicado a

qualquer t

ecnica de Aprendizado de M

aquina caixa-preta em que seja poss

ıvel

criar rankings de suas sa

ıdas.

Durante o trabalho, surgiu a quest

ao da falta de informac¸

ao sobre o co-

nhecimento adquirido por t

ecnicas caixa-preta quando utilizados m

etodos de

extrac¸

ao de regra pedag

ogicos. Uma alternativa para minimizar este problema

proposto

e utilizar a informac¸

ao dos rankings das sa

ıdas geradas por essas

ecnicas e a otimizac¸

ao de regras que tamb

em gerem um ranking com alta

similaridade com os rankings gerados por essas t

ecnicas.

Optamos ent

ao por inovar e propor um m

etodo de extrac¸

ao de conheci-

mento pedag

ogico que n

ao utiliza o conjunto de dados rotulado pela t

ecnica

de aprendizado de m

aquina caixa-preta para gerar as regras e sim um sub-

conjunto das regras geradas por v

arios indutores simb

olicos sobre o conjunto

de dados original. Esse subconjunto

e escolhido por meio de um Algoritmo

96 Cap

ıtulo 6

Gen

etico que tem como func¸

ao de avaliac¸

ao uma m

etrica que mede a si-

milaridade entre o ranking gerado pela t

ecnica de Aprendizado de M

aquina

caixa-preta da qual se quer extrair as regras e um indiv

ıduo da populac¸

ao do

Algoritmo Gen

etico que representa um subconjunto das regras geradas pelos

indutores simb

olicos escolhidos.

Os experimentos mostraram que essa

e uma abordagem promissora. N

apenas para a explicac¸

ao do comportamento de t

ecnicas de aprendizado de

aquina caixa-preta, mas tamb

em pode ser uma abordagem capaz de gerar

regras que herdem caracter

ısticas desej

aveis da t

ecnica caixa-preta da qual

as regras foram extra

ıdas, por exemplo, as fronteiras de decis

ao de margens

largas deﬁnidas por SVMs.

6.2 Limitac¸

oes

Este trabalho mostra que

e poss

ıvel realizar a extrac¸

ao de regras por simi-

laridade de rankings, por

em, muito ainda precisa ser feito para melhorar a

qualidade dos rankings e das pr

oprias regras geradas. Em v

arios casos os

resultados indicaram alta ﬁdelidade e acur

acia, mas em outros a ﬁdelidade

deixou muito a desejar, mostrando que o m

etodo ainda n

e consistente para

todos os dom

ınios de aplicac¸

ao.

A qualidade do subconjunto ﬁnal de regras que faz parte do indiv

ıduo es-

colhido depende diretamente da variabilidade dos bias indutivos nas regras

que formam a populac¸

ao inicial. Portanto, julgamos que para obter resulta-

dos melhores que os atuais, ser

a necess

ario aumentar o n

umero de indutores

simb

olicos utilizados para gerar as regras. Desta forma, o Algoritmo Gen

etico

ter

a mais chance de encontrar um conjunto de regras com bias mais pr

oximo

ao da t

ecnica de aprendizado de m

aquina caixa-preta.

6.3 Trabalhos futuros

Uma das variac¸

oes desse m

etodo

e gerar as regras da populac¸

ao inicial utili-

zando conjuntos de dados rotulados pela t

ecnica de Aprendizado de M

aquina

caixa-preta, assim como nos m

etodos pedag

ogicos tradicionais, e ent

ao rea-

lizar a otimizac¸

ao da similaridade de rankings. Experimentos iniciais j

a fo-

ram realizados, como descrito no Cap

ıtulo 5, mas ainda

e necess

ario executar

mais experimentos e testes de hip

oteses comparando as duas abordagens do

etodo RankSim com outros m

etodos.

Outro trabalho futuro

e a inclus

ao de mais indutores simb

olicos para a

gerac¸

ao de regras da populac¸

ao inicial para que, como j

a comentado, tenha-

mos maior variabilidade de bias indutivo nas regras dos indiv

ıduos do Algo-

ritmo Gen

etico.

Conclus

ao 97

Ainda com o objetivo de aumentar a variabilidade do bias indutivo, ser

estudadas formas de realizar mutac¸

oes nos antecedentes das regras extra

ıdas

durante a execuc¸

ao do Algoritmo Gen

etico.

em disso, especializando-se mais ainda no dom

ınio das SVMs, pretende-

se tamb

em explorar a gerac¸

ao de exemplos artiﬁciais a partir dos vetores de

suporte deﬁnidos pelas SVMs utilizando os pr

oprios vetores como exemplos e

criando novos atrav

es de operadores de mutac¸

ao e cruzamento, utilizando os

atributos dos vetores de suporte como cromossomos. Ent

ao pretende-se uti-

lizar esses exemplos artiﬁciais como conjunto de treinamento no momento de

gerar os rankings, de forma que os rankings das regras tenham alta simila-

ridade com um ranking gerado a partir de exemplos que explorem melhor as

margens das fronteiras de decis

ao das SVMs.

Refer

encias Bibliogr

aﬁcas

Alexander, J. A. and Dietterich, T. G. (1995). Template-based algorithms for

connectionist rule extraction. In Advances in Neural Information Processing

Systems, volume 7, pages 609–616, Cambridge, MA. MIT Press.

Andrews, R., Diederich, J., and Tickle, A. B. (1995). Survey and critique

of techniques for extracting rules from trained artiﬁcial neural networks.

Knowledge-Based Systems Journal, 8(6):373–389.

Behloul, F., Lelieveldt, B. P. F., Boudraa, A., and Reiber, J. H. C. (2002). Opti-

mal design of radial basis function neural networks for fuzzy-rule extraction

in high dimensional data. Pattern Recognition, 35(3):659–675.

Ben-Hur, A., Horn, D., Siegelmann, H. T., and Vapnik, V. N. (2000). A support

vector clustering method. In Proceedings of the International Conference on

Pattern Recognition (ICPR’00), volume 2, pages 724–727.

Blake, C. and Merz, C. (1998). UCI repository of machine learning databases.

Blasig, R. (1994). Gds: Gradient descent generation of symbolic classiﬁcation

rules. In Advances in Neural Information Processing Systems, volume 6,

pages 1093–1100, San Francisco, CA. Morgan Kaufmann.

Braga, A. P., de Carvalho, A. C. P. L. F., and Ludemir, T. B. (2000). Redes

Neurais Artiﬁciais: Teoria e aplicac¸

oes. Livros T

ecnicos e Cient

ıﬁcos.

Brown, M. P. S., Grundy, W. N., Cristianini, N., Sugnet, C. W., Furey, T. S.,

Jr., M. A., and Haussler, D. (2000). Knowledge-based analysis of microarray

gene expression data by using support vector machines. Proc. Natl. Acad.

Sci. USA, 97(1):262–267.

Clark, P. and Niblett, T. (1989a). The cn2 induction algorithm. Machine Lear-

ning, 3:261–284.

Clark, P. and Niblett, T. (1989b). The CN2 Induction Algorithm. Machine

Learning, 3:261–284.

100 Cap

ıtulo 6

Collobert, R. and Bengio, S. (2001). SVMTorch: Support vector machines

for large-scale regression problems. Journal of Machine Learning Research,

1:143–160.

Craven, M. and Shavlik, J. (1996). Extracting tree-structured representations

of trained networks. In Advances in Neural Information Processing Systems,

volume 8, pages 24–30. MIT Press.

Craven, M. W. (1996). Extracting Comprehensible Models from Trained Neural

Networks. PhD thesis, University of Wisconsin - Madison.

Craven, M. W. and Shavlik, J. W. (1994a). Machine learning approaches to

gene recognition. IEEE Expert, 9(2):2–10.

Craven, M. W. and Shavlik, J. W. (1994b). Using sampling and queries to

extract rules from trained neural networks. In Proceedings of the 11th Inter-

national Conference on Machine Learning, pages 37–45. Morgan Kaufmann.

Craven, M. W. and Shavlik, J. W. (1999). Rule Extraction: Where Do We

Go from Here? University of Wisconsin Machine Learning Research Group

Working Paper 99-1.

Cristianini, N. and Shawe-Taylor, J. (2000). An Introduction to Support Vector

Machines and other kernel-based learning methods. Cambridge University

Press.

Cybenko, G. (1988). Continuos valued neural networks with two hidden layers

are sufﬁcient. Technical report, Department of Computer Science, Tufts

University.

Darwin, C. (1859). On the Origin of Species by Means of Natural Selection.

Murray, London.

Dietterich, T. G. (1997). Approximate Statistical Tests for Comparing Super-

vised Classiﬁcation Learning Algorithms. Neural Computation, 10(7):1895–

1924.

Ding, C. H. Q. and Dubchak, I. (2001). Multi-class protein fold recogni-

tion using support vector machines and neural networks. Bioinformatics,

4(17):349–358.

Duch, W., Adamczak, R., Grabczewski, K., Zal, G., and Hayashi, Y. (2000).

Fuzzy and crisp logical rule extraction methods in application to medical

data. Computational Intelligence and Applications, 23:593–616.

Refer

encias Bibliogr

aﬁcas 101

Fu, L. (1991). Rule learning by searching on adapted nets. In Proceedings of

the Ninth National Conference on Artiﬁcial Intelligence, pages 590–595. Mit

Press.

Fu, L. (1994). Rule generation from neural networks. IEEE Transactions on

Systems, Man, and Cybernetics, 24(8):1114–1124.

Fung, G., Sandilya, S., and Rao, R. B. (2008). Rule extraction from linear

support vector machines via mathematical programming. In Diederich, J.,

editor, Rule Extraction from Support Vector Machines, volume 80 of Studies in

Computational Intelligence, pages 83–107. Springer.

Furey, T. S., Christianini, N., Christianini, N., Duffy, N., Bednarski, D. W.,

Schummer, M., and Hauessler, D. (2000). Support vector machine classiﬁ-

cation and validation of cancer tissue samples using microarray expression

data. Bioinformatics, 16(10):906–914.

Gallant, S. I. (1993). Neural Network Learning and Expert Systems. MIT Press.

Ginsberg, M. (1993). Essentials of Artiﬁcial Intelligence. Academic

Press/Morgan Kaufmann, San Francisco.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine

Learning. Addison-Wesley Publishing Company, Reading, Massachusetts.

Hayashi, Y. (1991). A neural expert system with automated extraction of fuzzy

if-then rules. In Advances in Neural Information Processing Systems, vo-

lume 3, pages 578–584, San Mateo, CA. Morgan Kaufmann.

Haykin, S. (1998). Neural Networks: A Comprehensive Foundation. Prentice

Hall, 2 edition.

Holland, J. H. (1975). Adaptation in Natural and Artiﬁcial Systems. University

of Michigan Press.

Huss, M., Bostr

om, H., Asker, L., and Coster, J. (2001). Learning to recognize

brain speciﬁc proteins based on low-level features from on-line prediction

servers. In BIOKDD01 - Workshop on Data Mining in Bioinformatics.

Jackson, J. C. (1995). The Harmonic Si

eve: A Novel Application of Fourier

Analysis to Machine Learning Theory and Practice. PhD thesis, School of

Computer Science, Carneggie Mellon University, Pittsburgh, PA. CMU-CS-

95-183.

102 Cap

ıtulo 6

Jong, K. D. (1980). Adaptive system design: A genetic approach. IEEE Tran-

sactions on Systems, Man and Cybernetics, SMC-10(9):566–574.

Lewin, B. (2000). Genes VII. Oxford University Press.

Lorena, A. C., Batista, G. E. A. P. A., Carvalho, A. C. P. L. F., and Monard,

M. C. (2002). The inﬂuence of noisy patterns in the performance of learning

methods in the splice junction recognition problem. In Proceedings of the VII

Brazilian Symposium on Neural Networks. IEEE Computer Society Press.

Lorena, A. C. and de Carvalho, A. C. P. L. F. (2003). Introduc¸

ao aos classi-

ﬁcadores de margens largas. Technical Report 195, Instituto de Ci

encias

Matem

aticas e de Computac¸

ao - Universidade de S

ao Paulo, S

ao Carlos -

SP.

Martineli, E. (1999). Extrac¸

ao de conhecimento de redes neurais artiﬁciais.

Master’s thesis, ICMC-USP.

Milar

e, C. R. (2003). Extrac¸

ao de conhecimento de redes neurais artiﬁciais

utilizando sistemas de aprendizado simb

olico e algoritmos gen

eticos. PhD

thesis, Universidade de S

ao Paulo, S

ao Carlos - SP.

Milar

e, C. R., de Carvalho, A. C. P. L. F., and Monard, M. C. (2002). Extracting

knowledge from artiﬁcial neural networks: an empirical comparison of tre-

pan and symbolic learning algorithms. In MICAI 2002: Advances in Artiﬁcial

Intelligence, volume 2313 of Lecture Notes in Computer Science: Lecture Notes

in Artiﬁcial Intelligence, pages 272–281, Merida, Yucatan, Mexico. Springer.

Milar

e, C. R., Batista, G. E. A. P. A., and Monard, M. C. (1997). Uma Ferra-

menta para Extrac¸

ao de Conhecimento de Redes Neurais. In XXV Semin

ario

Integrado de Software e Hardware - SEMISH, pages 59–70.

Mitchel, T. M. (1997). Machine Learning. McGraw-Hill.

Mitra, S., Pal, S. K., and Mitra, P. (2002). Data mining in soft computing

framework: A survey. IEEE Transactions on Neural Networks, 13(1):3–14.

Mukherjee, N. and Mukherjee, S. (2002). Predicting signal peptides with sup-

port vector machines. In Pattern Recognition with Support Vector Machines,

volume 2388 of Lecture Notes in Computer Science, pages 1–7. Springer.

nez, H., Angulo, C., and Catal

a, A. (2002). Rule extraction from support

vector machines. In Verleysen, M., editor, ESANN 2002, 10th Eurorean Sym-

posium on Artiﬁcial Neural Networks, Bruges, Belgium, April 24-26, 2002,

Proceedings, pages 107–112.

Refer

encias Bibliogr

aﬁcas 103

Prati, R. C., Baranauskas, J. A., and Monard, M. C. (2002). Padronizac¸

da sintaxe e informac¸

oes sobre regras induzidas a partir de algoritmos de

aprendizado de m

aquina simb

olico. Revista Eletr

onica de Iniciac¸

ao Cient

ıﬁca,

2(3).

Quinlan, J. R. (1988). C4.5 Programs for Machine Learning. Morgan Kaufmann

Publishers, CA.

Rezende, S. O. (2002). Sistemas Inteligentes. Manole.

Rumelhart, D., Hilton, G., and Williams, R. (1986). Learning Internal Repre-

sentations by Error Propagation. In Parallel Distributed Processing: Explo-

rations in the Microstructure of Cognition, volume 1. MIT Press, Cambridge,

MA.

Saito, K. and Nakano, R. (1988). Medical Diagnostic Expert System Based on

PDP Model. In Proceedings of the IEEE International Conference on Neural

Networks, pages 255–262, San Diego, CA. IEEE Press.

Schellharmmer, I., Diederich, J., Towsey, M., and Brugman, C. (1997). Kno-

wledge extraction and recurrent neural networks: an analysis of an elman

network trained on a natural language learning task. Technical Report 97-

IS1, Queensland University of Technology, Australia.

Schmitz, G. P. J., Aldrich, C., and Gouws, F. S. (1999). Ann-dt: An algo-

rithm for extraction of decision trees from artiﬁcial neural networks. IEEE

Transactions on Neural Networks, 10(6):1392–1401.

Sethi, I. K. and Yoo, J. H. (1994). Symbolic approximation of feedforward

neural networks. In Pattern Recognition in Pratice, volume 4, pages 313–

324, North-Holland, New York, NY.

Setiono, R. and Liu, H. (1995). Understanding neural networks via rule ex-

traction. In Proceedings of the Fourteenth International Joint Conference on

Artiﬁcial Intelligence, pages 480–485, Montreal, Quebec. Morgan kaufmann.

Smola, A. J., Barlett, P., Sch

olkopf, B., and Schuurmans, D. (1999). Advances

in Large Margin Classiﬁers. MIT Press.

Spears, W. M., De Jong, K. A., B

ack, T., Fogel, D. B., and de Garis, H. (1993).

An overview of evolutionary computation. In Brazdil, P. B., editor, Proc. of

the European Conf. on Machine Learning, pages 442–459, Berlin. Springer.

104 Cap

ıtulo 6

Tan, A. H. (1994). Rule learning and extration with self-organizing neural

network. In Proceedings of the 1993 Connectionist Models Summer School,

pages 192–199, Hillsdale, NJ. Lawrence Erlbaum Associates.

Thrun, S. (1994). Extracting provably correct rules from artiﬁcial neural

networks. Technical Report IAI-TR-93-5, Institut f

ur Informatik III, Uni-

versit

at Bonn.

Thrun, S. (1995). Extracting rules from artiﬁcial neural networks with dis-

tributed representations. In Advances in Neural Information Processing Sys-

tems, volume 7, pages 505–512, Cambridge, MA. MIT Press.

Tickle, A. B., Andrews, R., Golea, M., and Diederich, J. (1998). The truth

will come to light: Directions and challenges in extracting the knowledge

embedded within trained artiﬁcial neural networks. IEEE Transactions on

Neural Networks, 9(6):1057–1068.

Tickle, A. B., Orlowski, M., and Diederich, J. (1994). Dedec: Decision detection

by rule extraction from neural network. Technical report, QUT NRC.

Towell, G. and Shavlik, J. W. (1993). The extraction of reﬁned rules from

knowledge-based neural networks. Machine Learning, 131(1):71–101.

Weiss, S. M. and Kulikowski, C. A. (1991). Computer Systems that Learn.

Classiﬁcation and Prediction Methods from Statistics, Neural Nets, Machine

Learning, and Expert Systems. Morgan Kaufmann, San Mateo, CA.

Winston, P. (1992). Artiﬁcial Intelligence. Addison-Wesley.

Zell, A. (1995). Stuttgart Neural Network Simulator. http://www.

ra-informatik.uni-tuebingen.de/SNNS/.

Zhou, Z. and Jiang, Y. (2002). Medical diagnosis with c4.5 rule preceded

by artiﬁcial neural network ensemble. IEEE Transactions on Information

Technology in Biomedicine. to appear.

Zien, A., R

atsch, G., Mika, S., Sch

olkopf, B., Lengaeuer, T., and M

uller, K. R.

(2000). Engineering suppot vector machine kernels that recognize transla-

tion initiation sites in dna. Bioinformatics, 16(9):799–807.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 