HistClass -Proposta de um algoritmo não paramétrico

Universidade Nova de Lisboa Faculdade de Ciências e Tecnologia Departamento de Informática

Indução de Árvores de Decisão HistClass - Proposta de um algoritmo não paramétrico

José Manuel Matos Ribeiro da Fonseca

Lisboa, 1994

À Lurdes, à Inês, ao nosso futuro.

1

Sumário Esta tese apresenta um estudo de vários algoritmos de indução de árvores de decisão, sendo contemplados algoritmos bastante populares nesta área tais como o ID3, C4.5 e o CART, entre outros, sendo ainda apresentado um algoritmo de indução original. Depois de situado o leitor no âmbito deste trabalho e justificada a opção efectuada em favor das árvores de decisão para o estudo de grandes volumes de dados, bem como para a geração de classificadores automáticos, são apresentadas e discutidas detalhadamente as várias técnicas utilizadas na geração de uma árvore de decisão. Seguidamente é introduzido um algoritmo não paramétrico original ao qual foi dado o nome de HistClass. Este novo algoritmo, que foi estudado com vista ao tratamento de problemas de grandes dimensões, contendo atributos discretos e/ou contínuos, é pormenorizadamente descrito, sendo também apresentado sumariamente o software de apoio desenvolvido para a avaliação dos seus resultados. Finalmente, os algoritmos ID3, CART, C4.5 e HistClass são comparados entre si, em termos de desempenho de classificação. Para esta comparação, é utilizado um conjunto de problemas típicos de aprendizagem automática que, sendo do domínio público, permitem uma posterior análise comparativa com outros trabalhos nesta área.

3

Abstract This thesis assesses decision tree algorithms, covering very popular ones such as ID3, C4.5 and CART. An original decision tree algorithm is proposed. After a brief introduction, this thesis presents the justification for selecting decision trees for the processing of large quantities of data and automatic classifiers generation. Then, a selection of techniques for the generation of decision trees is presented. After this theoretical overview, HistClass, a non-parametric, induction algorithm is introduced. This algorithm, designed essentially for the processing of large problems involving large amounts of data and containing discrete and/or continuous attributes is described in detail. Further, the software specifically developed for evaluation of the algorithm performance is discussed. Finally, the algorithms ID3, CART, C4.5 and HistClass are compared from the point of view of performance. For the performance evaluation, a complete set of typical, public domain, machine learning examples is used. These examples allow the comparison of the results obtained here and others developed in this area.

5

Simbologia =

Igual

≠

Diferente

<

Menor que

>

Maior que

≤

Menor ou igual

≥

Maior ou igual

∀

Quantificador universal

[a,b[

Intervalo fechado em a e aberto em b

]a,b]

Intervalo aberto em a e fechado em b

π

pi

exp()

Função exponencial

∫ dz

Integral em ordem a z

|A|

Cardinalidade do conjunto A

AI B

Intersecção de conjuntos

AU B

União de conjuntos

R*( d)

Erro real de um classificador d

R(d)

Erro de resubstituição ou erro aparente de um classificador d

R ts ( d )

Erro do classificador d estimado com base num conjunto de teste independente

R cv ( d )

Erro do classificador d estimado por camadas ou por validação cruzada Estimação "honesta" do erro do classificador d

e0( d )

Erro do classificador d estimado por bootstrapping e0 7

8

Simbologia

B623( d )

Erro do classificador d estimado por bootstrapping .623

R α ( T)

Valor do custo/complexidade da árvore T

r ( η)

Erro aparente do nó η

xn

n-ésimo valor do vector de atributos

x m ,n

Valor do n-ésimo atributo do m-ésimo exemplo

p(a)

Probabilidade do acontecimento a

p(a|b)

Probabilidade condicionada do acontecimento a em relação ao acontecimento b

σ2

Variância de uma distribuição Gaussiana

I nm

n-ésimo intervalo de segmentação com base no m-ésimo atributo

a

2

Soma do quadrado do coeficientes do vector a

Δx

Incremento de x

Pn

Ponto n do conjunto de treino

C

Conjunto das classes do problema

CL ,CR

Conjunto das classes do ramo esquerdo e direito de um nó

E

Erro de classificação

a i , j , a i , bi , b

Coeficientes de uma rede neuronal

t

Conjunto de treino

tL,tR

Conjunto de treino dos descendentes esquerdo e direito de um nó

sm

Partição com base na característica m

Sm , Sm

Conjunto das partições possíveis num dado nó com base no atributo m e suas complementares

ωj

Número de ocorrências da distribuição j

δ

Patamar definido pelo utilizador

m(A)

Massa probabilística do conjunto A

Φ

Função de impuridade

log 2

Logaritmo na base 2

Bel(A)

Medida de crença

Pl(A)

Medida de plausibilidade

~ T

Conjunto dos nós terminais

Σ

Somatório

Simbologia

9

a∈A

Relação de pertença

a∉A

Relação de não pertença

β

Constante de proporcionalidade

max f ( x)

Máximo de f(x) em relação a x

min f ( x)

Mínimo de f(x) em relação a x

η

Nó de uma árvore de decisão

min(a,b)

Mínimo entre a e b

λ(a|b)

Qualidade relativa da partição b em relação a a

I(x;y|z)

Informação mútua entre as variáveis x e y condicionada à variável z

Conf(m)

Medida de confusão

Diss(m)

Medida de dissonância

χ2

Teste do qui-quadrado

pi , ps

Limites de confiança inferior e superior da distribuição binomial

α

Factor de confiança

Folha(η)

Função que devolve verdadeiro se η é um nó terminal, falso caso contrário

Passo j

Passo utilizado para o histograma do j-ésimo atributo

Inc(x) ∂x

Função que incrementa x de uma unidade

x

x

∂t dx dt

Derivada parcial de x em ordem a t Derivada total de x em ordem a t

9

Índice de matérias Sumário .................................................................................................................................................. 3 Abstract.................................................................................................................................................. 5 Simbologia ............................................................................................................................................. 7 Índice de matérias ................................................................................................................................ 11 Índice de figuras .................................................................................................................................. 15 Índice de tabelas .................................................................................................................................. 17 Capítulo 1. Introdução ........................................................................................................................ 19 1.1. Motivação ............................................................................................................................ 19 1.2. Outros tipos de classificadores ............................................................................................ 20 1.3. Classificadores baseados em árvores de decisão ................................................................. 23 1.4. Objectivos do trabalho desenvolvido .................................................................................. 25 Capítulo 2. Estimação da qualidade de um classificador ................................................................... 27 2.1. Estimação de custos ............................................................................................................. 27 2.2. Estimação por resubstituição ou erro aparente .................................................................... 29 2.3. Estimação por utilização de um conjunto independente ..................................................... 29 2.4. Estimação por camadas ou validação cruzada ..................................................................... 30 2.5. Estimação por bootstrapping ............................................................................................... 31 2.5.1.

Bootstrapping e0 ......................................................................................................... 32

2.5.2.

Bootstrapping .623 ...................................................................................................... 32

2.6. Qual o melhor método? ....................................................................................................... 33 Capítulo 3. Técnicas de construção de árvores de decisão ................................................................. 35 3.1. Como efectuar a partição em cada nó .................................................................................. 35 3.1.1.

Partições baseadas em características discretas .......................................................... 35

3.1.1.1. Um ramo por cada valor do atributo .................................................................... 36 3.1.1.2. A solução de Hunt (CLS) .................................................................................... 36 3.1.1.3. Características ordenadas .................................................................................... 36 3.1.1.4. Agrupamento de valores de características em dois conjuntos ........................... 36 11

12

Índice de Matérias 3.1.1.5. Agrupamento de valores de características em vários conjuntos......................... 37 3.1.2.

Partições baseadas em características contínuas ......................................................... 37

3.1.2.1. Testes simples ou pesquisa exaustiva .................................................................. 38 3.1.2.2. Testes múltiplos ................................................................................................... 38 3.1.2.3. Combinação linear de características ................................................................... 40 3.1.2.4. Utilização de redes neuronais .............................................................................. 44 3.1.3.

Valores desconhecidos ................................................................................................ 45

3.1.3.1. Tratamento por exclusão ...................................................................................... 46 3.1.3.2. Introdução do valor desconhecido ....................................................................... 46 3.1.3.3. Partições alternativas ........................................................................................... 46 3.2. Como calcular medidas de incerteza ................................................................................... 48 3.2.1.

Aproximação frequencista das probabilidades ............................................................ 48

3.2.2.

Aproximação baseada no critério de Laplace .............................................................. 48

3.2.3.

Critério das massas probabilísticas .............................................................................. 49

3.3. Eleição da melhor característica .......................................................................................... 50 3.3.1.

Critério da impuridade ................................................................................................. 51

3.3.1.1. Critério de Gini .................................................................................................... 52 3.3.1.2. Critério da entropia .............................................................................................. 53 3.3.2.

Critério de paridade ..................................................................................................... 53

3.3.3.

Critério de Laplace ...................................................................................................... 54

3.3.4.

Medida da confusão ..................................................................................................... 54

3.3.5.

Pesagem do desconhecimento ..................................................................................... 55

3.4. Determinação da classe associada à folha ........................................................................... 56 3.4.1.

Atribuição da classe mais provável ............................................................................. 56

3.4.2.

Determinação baseada na noção de custos .................................................................. 56

3.5. Aplicação de janelas sobre o conjunto de treino.................................................................. 57 3.5.1.

Janela aleatória ............................................................................................................ 58

3.5.2.

Janela de distribuição normalizada .............................................................................. 58

Capítulo 4. Limitação na dimensão das árvores de decisão ............................................................... 59 4.1. Métodos de limitação durante a construção ......................................................................... 60 4.1.1.

Paragem baseada na informação mútua ...................................................................... 61

4.1.2. Paragem baseada no teste de independência estatística ou teste do quiquadrado 61 4.1.3.

Paragem baseada na regra de entropia delta ................................................................ 61

4.2. Técnicas de poda .................................................................................................................. 62 4.2.1.

Poda pelo algoritmo Laplaciano .................................................................................. 62

4.2.2.

Poda por minimização do custo-complexidade ........................................................... 63

4.2.3.

Poda baseada no erro ................................................................................................... 69

4.2.4.

Poda segundo Guo e Gelfand ...................................................................................... 72

Índice de Matérias

13

Capítulo 5. Descrição do trabalho efectuado ...................................................................................... 75 5.1. Percurso da investigação ..................................................................................................... 75 5.2. Motivações para o estudo das árvores de decisão ............................................................... 77 5.3. Algoritmo HistClass ............................................................................................................ 77 5.3.1.

Tratamento de atributos contínuos .............................................................................. 78

5.3.2.

Tratamento de atributos discretos ............................................................................... 84

5.4. Software desenvolvido ........................................................................................................ 85 5.4.1.

Formato dos ficheiros utilizados ................................................................................. 85

5.4.2.

Descrição do software implementado ......................................................................... 86

5.4.3.

Opções do programa HistClass ................................................................................... 88

Capítulo 6. Algoritmos de indução de árvores de decisão ................................................................. 91 6.1. Algoritmos e software de apoio.............................................................................................. 91 6.1.1.

ID3............................................................................................................................... 91

6.1.2.

CART .......................................................................................................................... 94

6.1.3.

C4.5 ............................................................................................................................. 96

6.2. Apresentação e comparação de resultados ............................................................................. 98 6.2.1.

Exemplos no domínio discreto .................................................................................... 98

6.2.1.1. O problema dos votos ............................................................................................ 99 6.2.1.2. The Monk's Problems............................................................................................. 100 6.2.2. Exemplos no domínio contínuo ou mistos ..................................................................... 102 6.2.2.1.Caracterização das bases de dados utilizadas no domínio contínuo ou mistas ....... 102 6.2.3. Resultados obtidos.......................................................................................................... 103 Capítulo 7. Conclusões e trabalho futuro ........................................................................................... 105 Anexo A. Dedução das equações de aprendizagem backpropagation................................................ 109 Anexo B. Algoritmo de pesquisa de combinações lineares................................................................ 113 Anexo C. Comandos disponíveis e exemplo de execução do programa CART ................................ 117 Anexo D. Comandos disponíveis e exemplo de execução do programa C4.5 ................................... 125 Anexo E. Breve resumo de características das bases de dados utilizadas .......................................... 129 Agradecimentos .................................................................................................................................. 135 Bibliografia ......................................................................................................................................... 137

14

Índice de Matérias

Índice de figuras 1.1 - Exemplo de classificação por proximidade. ................................................................................ 21 1.2 - Exemplo de uma pequena rede neuronal..................................................................................... 22 1.3 - Exemplo de um classificador baseado numa árvore de decisão.................................................. 24 2.1 - Relação entre o conjunto de treino e o conjunto de teste ............................................................ 29 2.2 - Relação entre o conjunto de treino e o conjunto de teste. ........................................................... 30 2.3 - Relação entre o conjunto de treino e o conjunto de teste. ........................................................... 30 3.1 - Segmentação do primeiro atributo. ............................................................................................. 39 3.2 - Distibuição das classes A e B...................................................................................................... 40 3.3 - Descrição pseudo-código do algoritmo de perturbação de hiperplanos. ..................................... 43 3.4 - Topologia da rede proposta para a partição do universo em cada nó não terminal. ................... 44 3.5 - Árvore de decisão com partições alternativas. ............................................................................ 46 3.6 - Exemplo de duas partições. ......................................................................................................... 51 4.1 - Evolução do erro aparente e do erro real em função do número de nós da árvore de decisão. .. 60 4.2 - Exemplos de remoção de nós. ..................................................................................................... 62 4.3 - 1ª árvore da sequência de redução para o problema Heart. ......................................................... 66 4.4 - Sequência de redução para o problema Heart. ............................................................................ 67 4.5 - Árvore considerada ideal para o problema Heart. ....................................................................... 69 4.6 - Limites inferior e superior da distribuição binomial. .................................................................. 70 4.7 - Árvore inicial do problema Heart................................................................................................ 71 4.8 - Árvore resultante do algoritmo de poda baseado no erro............................................................ 71 5.1 - Exemplo do histograma de um atributo. ..................................................................................... 78 5.2 - Exemplo de histograma de um atributo com ruído. .................................................................... 79 5.3 - Exemplo de histograma de um atributo e respectivos pontos de cisão. ...................................... 80 5.4 - Exemplo de histograma de um atributo capaz de diferenciar duas classes. ................................ 81 5.5 - Exemplo de histogramas para um atributo em função da classe. ................................................ 81 5.6 - Exemplo de histogramas por atributo/classe para um exemplo com 4 classes. .......................... 82 5.7 - Histograma da figura 5.6 depois de eliminadas as zonas de indefinição. ................................... 83 5.8 - Histograma depois de aplicado o processamento de eliminação de riscas não significativas. ... 83 5.9 - Exemplo de histograma de um atributo discreto. ........................................................................ 84 5.10 - Nó criado com base no atributo apresentado na figura 5.9. ...................................................... 85 15

16

Índice de figuras

5.11 - Formato do ficheiro de descrição. ............................................................................................. 85 5.12 - Formato do ficheiro de dados. ................................................................................................... 86 5.13 - Exemplo do ficheiro de descrição do problema Heart. ............................................................. 86 5.14 - Exemplo do ficheiro de dados do problema Heart. ................................................................... 86 6.1 - Mapa de Karnaught para o exemplo de resolução do ID3. ......................................................... 92 6.2 - Árvore gerada pelo ID3 para o problema da tabela anterior. ...................................................... 92 6.3 - Árvore gerada pelo ID3 com base num subconjunto do conjunto de treino composto por 12 exemplos. ..................................................................................................................................... 93 6.4 - Árvores produzidas pelos três algoritmos para o problema Vote................................................ 99 A.1 - Estrutura de uma rede neuronal de duas camadas com q neurónios na camada de entrada e um neurónio na camada de saída...................................................................................................... 109 B.1 - Árvores geradas pelo algoritmo CART sem e com combinação linear de atributos. ............... 114 B.2 - Partições resultantes das árvores geradas pelo algoritmo CART sem e com combinação linear de atributos. ..................................................................................................................................... 114 C.1 - Conteúdo do ficheiro Heart.cmd. .............................................................................................. 119 C.2 - Árvore gerada pelo programa CART para o exemplo Heart. ................................................... 124 D.1 - Árvore gerada pelo programa C4.5 para o exemplo Heart. ...................................................... 127

Índice de tabelas 2.1 - Exemplo de uma matriz de custos para um problema com 3 classes. ......................................... 28 2.2 - Exemplo de uma matriz de confusão para um problema com 3 classes. .................................... 28 3.1 - Exemplo de aplicação do algoritmo de agrupamento de valores a uma característica com 4 valores possíveis. ......................................................................................................................... 37 3.2 - Vectores de caracterização das 3 classes..................................................................................... 39 3.3 - Frequências das três classes na folha. ......................................................................................... 57 3.4 - Probabilidades das três classes na folha. ..................................................................................... 57 3.5 - Matriz de custos do problema. .................................................................................................... 57 3.6 - Custos associados a cada uma das classes. ................................................................................. 57 4.1 - Valores de α para a sequência de redução do problema Heart. .................................................. 66 4.2 - Valores do limite superior do erro de classificação para cada nó da árvore da figura 4.7. ......... 72 5.1 - Tabela exemplificativa da influência do valor da entropia para a paragem no desenvolvimento da árvore. .......................................................................................................................................... 88 5.2 - Tabela de opções do programa HistClass. .................................................................................. 89 6.1 - Conjunto de treino correspondente ao mapa de Karnaught anterior. .......................................... 92 6.2 - Resultados obtidos pelo ID3 com e sem janela. .......................................................................... 94 6.3 - Resultados obtidos para o problema Vote. .................................................................................. 99 6.4 - Descrição dos atributos do problema Monks. ........................................................................... 100 6.5 - Resultados obtidos para o problema Monk1. ............................................................................ 101 6.6 - Resultados obtidos para o problema Monk2. ............................................................................ 101 6.7 - Resultados obtidos para o problema Monk3. ............................................................................ 101 6.8 - Resumo das características dos diversos problemas de testes dos algoritmos. ......................... 102 6.9 - Resumo dos resultados obtidos pelos diversos algoritmos. ...................................................... 103 C.1 - Comandos disponíveis no programa CART. ............................................................................ 118 D.1 - Comandos disponíveis no programa C4.5................................................................................ 125 E.1 - Tabela de sumário das características do exemplo Austral. ..................................................... 129 E.2 - Tabela de sumário das características do exemplo Diabetes. ................................................... 130 E.3 - Significado dos atributos do problema Diabetes. ..................................................................... 130 E.4 - Tabela de sumário das características do exemplo Heart. ........................................................ 130 E.5 - Significado dos atributos do problema Heart. .......................................................................... 130 17

18

Índice de tabelas

E.6 - Tabela de sumário das características do exemplo Ionospher. ................................................. 131 E.7 - Tabela de sumário das características do exemplo Iris. ............................................................ 131 E.8 - Significado dos atributos do problema Iris. .............................................................................. 131 E.9 - Tabela de sumário das características do exemplo Liver. ......................................................... 131 E.10 - Tabela de sumário das características do exemplo Satelite. ................................................... 131 E.11 - Tabela de sumário das características do exemplo Segment. ................................................. 132 E.12 - Significado das classes do problema Segment. ....................................................................... 132 E.13 - Significado dos atributos do problema Segment..................................................................... 132 E.14 - Tabela de sumário das características do exemplo Vehicule. ................................................. 133 E.15 - Distibuição dos exemplos do problema Vehicule por classes. ............................................... 133 E.16 - Significado dos atributos do problema Vehicule. ................................................................... 133 E.17 - Tabela de sumário das características do exemplo Wine. ....................................................... 133

CAPÍTULO 1 Introdução Faz-se neste capítulo uma apresentação do trabalho efectuado no âmbito desta tese bem como do contexto científico em que este se integra.

1.1. Motivação A estimação da classe a que um objecto pertence através de um conjunto de medidas que o descreve é um problema típico de uma área científica normalmente identificada por reconhecimento de padrões. Várias e muito distintas aproximações têm sido adoptadas com vista à solução deste problema. Desde as aproximações puramente estatísticas até às soluções baseadas em redes neuronais um longo caminho foi percorrido, tendo todas elas as suas vantagens e desvantagens. Coloca-se então a questão de porquê as árvores de decisão? A grande motivação para o desenvolvimento deste trabalho sobre indução de árvores de decisão é dada não pela particular eficiência deste tipo de técnicas no que diz respeito à classificação mas pela grande inteligibilidade dos resultados que produz. Técnicas como as baseadas em redes neuronais que obtêm níveis de desempenho na classificação verdadeiramente impressionantes, têm o inconveniente de ser particularmente difícil a interpretação de como processam os dados, representando assim um limitado auxílio à compreensão do fenómeno por parte do utilizador. Como é evidente, este é um pormenor de importância diminuta ou mesmo nula em algumas aplicações. No entanto, a capacidade de fornecer uma explicação para o problema é, em algumas situações, não apenas um subproduto mas um objectivo primordial. Este é o caso de toda uma área que está neste momento em grande evolução e que se dedica ao descobrimento de conhecimento em grandes quantidades de informação. Esta nova área surge da necessidade de extrair algum conhecimento de entre as enormes quantidades de dados que são neste momento armazenados em suporte informático. Estima-se que nos nossos dias a quantidade de informação duplica todos os 20 meses. Por exemplo, espera-se que os satélites de observação da terra produzam nos finais dos anos 90 cerca de um terabyte (1015 bytes) de informação por dia. Muitos outros exemplos de ambientes em que a quantidade de informação disponível é

19

20

Introdução

completamente impossível de manipular de forma manual poderiam ser dados. Em muitos destes casos, a existência de uma forma de aquisição automática de conhecimento pode revelar-se de uma utilidade fantástica. A aplicação de técnicas de aprendizagem automática1 à descoberta de conhecimento constitui neste momento uma área de grande dinâmica e da qual se esperam grandes resultados. Embora esta seja uma área ainda muito recente, algumas aplicações estão já desenvolvidas e fornecendo resultados muito interessantes em áreas tão distintas como [Piatetsky-Shapiro, 1990]: • Medicina: biomedicina, efeitos secundários provenientes do consumo de drogas, contenção de custos em hospitais, análises genéticas, etc. • Finanças: aprovação de crédito, predição de situações de bancarrota, detecção de fraudes em seguros, detecção de situações de acesso não autorizado a cartões de crédito, etc. • Agricultura: classificação de doenças em produtos agrícolas. • Social: informação demográfica, tendência de voto, resultados eleitorais. • Marketing e vendas: identificação de grupos económico-sociais com comportamentos particulares, análise de produtos, predição de vendas, etc. • Seguros: detecção de pedidos de indemnização excessivos ou fraudulentos, etc. • Engenharia: diagnóstico automóvel, bases de dados CAD, estimação de empregos, etc. • Física e química: electroquimica, pesquisa da superconductividade, etc. • Militar: análise de informações várias, correlação de informações, aplicações várias consideradas secretas. • Policiamento: fugas ao fisco, verificação de impressões digitais, recuperação de objectos roubados, etc. • Ciências espaciais: astronomia, análise de informação espacial, etc. Pelos exemplos acima citados é fácil adivinhar-se o interesse crescente que este tipo de estudos está a suscitar. Diversas técnicas são aplicáveis tanto para a descoberta de conhecimento como para a construção de classificadores automáticos em geral.

1.2. Outros tipos de classificadores Dá-se seguidamente uma panorâmica das várias técnicas utilizadas na construção de classificadores automáticos sendo discutidas algumas das vantagens e desvantagens apresentadas por cada uma delas. Classificadores baseados em exemplos

1Machine

Learning

Introdução

21

A memorização dos vários exemplos fornecidos para a aprendizagem pode ser utilizada para a construção de classificadores automáticos. Quando se pretenda estimar a classe de um novo exemplo, pode então procurar-se o exemplo mais parecido e atribuir ao exemplo em causa a sua classe. Este é o caso dos classificadores do tipo nearest neighbor [Pao, 1989; Haralick, 1992].

?

Classe A

Classe B

Classe C

Figura 1.1 - Exemplo de classificação por proximidade. Uma das grandes vantagens apresentadas por estes métodos prende-se com a facilidade de integrar novo conhecimento. Com efeito, bastará juntar aos exemplos memorizados os novos exemplos para que a nova informação seja assimilada. Por outro lado, a sua construção é extremamente simples não envolvendo praticamente qualquer processamento. Este tipo de classificadores levanta no entanto algumas questões: - Quais os exemplos a guardar? Se todos os exemplos forem guardados, a quantidade de informação armazenada pode facilmente tornar-se incomportável e a pesquisa demasiado lenta. Se apenas alguns deles forem guardados como efectuar essa selecção? De modo a contornar este inconveniente podem ser guardados apenas protótipos representativos de grupos de exemplos. Desta forma, fica um tanto comprometida a facilidade de integração de novo conhecimento. Existem alguns estudos no sentido de se encontrarem regras que permitam definir quando se deverá alterar o conjunto de protótipos. - Como medir a semelhança entre os exemplos? A medida de semelhança entre vectores heterodimensionais, misturando atributos contínuos e discretos coloca vários problemas. Também a existência de atributos irrelevantes pode criar dissemelhanças importantes, afectando de forma decisiva os resultados da classificação. - Como comparar o exemplo a classificar com os exemplos memorizados? Deverá ser atribuída ao novo exemplo a classe do vector que se considera possuir maior semelhança ou a classe mais frequente de entre o conjunto de n exemplos com maior semelhança? Por último, o principal defeito deste método é, na perspectiva do autor, a pouca ou nenhuma informação sobre a essência do fenómeno por ele fornecida.

22

Introdução

Classificadores com base em redes neuronais As redes neuronais artificiais têm tido uma evolução histórica bastante curiosa. Depois de nos anos 60 terem conhecido um enorme sucesso e causado grande furor nos meios científicos [Nilsson, 1965], foram votadas ao abandono até aos anos 80, época em que se assistiu ao seu ressurgimento com um fulgor renovado devido ao advento do método de aprendizagem backpropagation. Este adormecimento de duas décadas deveu-se às grandes limitações apontadas às capacidades de aprendizagem deste tipo de arquitecturas, que só na passada década foram ultrapassadas. No seu exemplo mais típico, uma rede neuronal artificial é formada por três tipos de elementos a que se dá o nome de neurónios: os neurónios da camada de entrada que introduzem os dados na rede, os neurónios das camadas internas e os neurónios da camada de saída que produzem o resultado. Cada ligação entre neurónios possue um peso, tendo cada neurónio, em geral, um nível de patamar que influência directamente a sua saída. A

C E

B

D

Figura 1.2 - Exemplo de uma pequena rede neuronal. O valor de excitação I de cada neurónio é calculado efectuando a soma das suas várias entradas pesadas pelos respectivos coeficientes (pesos) ao que é somado o seu valor de patamar. Para o cálculo da sua resposta este valor é então aplicado à sua função de transferência. Uma das funções de transferência mais vulgares é a indicada na expressão (1.1). Repare-se que enquanto que o valor de entrada I pode variar entre -∞ e +∞, o valor da sua saída está, neste caso, limitado entre 0 e 1.

O=

1 −I

e +1

onde I =

∑w v

i i

+T

(1.1)

i

Embora a expressão (1.1) seja das mais vulgares muitas outras podem ser utilizadas, como é o caso da expressão (3.16) utilizada no parágrafo 3.1.2.4. A resposta global da rede é portanto ditada pelos valores apresentados pelos seus neurónios da camada de saída. Normalmente associa-se a cada neurónio da camada de saída uma dada classe e o objectivo é que a rede, na presença de um dado exemplo, active a saída correspondente à classe a que esse exemplo pertence. A aprendizagem das redes neuronais consiste então em ajustar os pesos e os valores de patamar de cada um dos neurónios da rede, de forma a que esta tenha a capacidade de classificar correctamente todos, ou quase todos, os exemplos presentes no conjunto de treino. Segundo o método de aprendizagem backpropagation, os exemplos do conjunto de treino são mostrados um a um à rede, sendo calculada a diferença entre a saída obtida e a desejada. Esse valor de erro é então propagado da camada de saída para a camada de entrada (daí o nome de backpropagation) sendo efectuado um ajuste nos valores dos pesos e dos patamares dos neurónios das diversas camadas

Introdução

23

tendente à diminuição do erro obtido usando para tal um método de gradiente. Embora este seja o método de aprendizagem mais conhecido existe um grande número de métodos alternativos apresentando todos eles as suas vantagens e desvantagens. Classificadores baseados em algoritmos genéticos Os algoritmos genéticos constituem uma aproximação interessante aos classificadores automáticos. O princípio base deste tipo de algoritmos é extremamente simples. O primeiro passo será a geração de uma população de classificadores de forma completamente aleatória que devem ser codificados na forma de genes (considera-se um gene uma sequência de bits que codifica um conjunto de valores). Na criação do conjunto inicial de classificadores, é possível a utilização de alguns critérios que evitem o aparecimento de "aberrações". Este conjunto de classificadores deverá então ser avaliado individualmente em relação à sua qualidade na predição da classe dos vários exemplos do conjunto de treino. Definem-se então 3 operações básicas que constituem a essência de qualquer algoritmo genético: • Reprodução: cada gene é escolhido aleatoriamente para reprodução com uma probabilidade proporcional à sua qualidade na resolução do problema. De forma análoga os genes são eliminados com uma probabilidade inversamente proporcional ao seu desempenho. • Cruzamento: a reprodução entre dois genes seleccionados para se reproduzirem entre si é efectuada cruzando a informação genética de ambos através da geração de novos elementos formados por pedaços copiados aleatoriamente a partir de cada um dos seus progenitores. • Mutação: de forma a criar novos indivíduos que consigam fugir à normalidade e constituir novas e diferentes propostas, a informação genética dos novos elementos é alterada de forma aleatória depois de efectuado o cruzamento. Desta forma consegue-se fugir de máximos locais, ou seja, de situações em que, apenas por cruzamento, seria impossível evoluir. Repare-se que a evolução se deve ao facto de serem escolhidos para reprodução os mais aptos e eliminados os menos adaptados. É de salientar que os algoritmos genéticos permitem a optimização de funções podendo ser, em princípio, aplicados na optimização de qualquer tipo de classificadores.

1.3. Classificadores baseados em árvores de decisão Os classificadores baseados em árvores de decisão remontam aos anos 50, sendo uma referência fundamental o trabalho de Hunt, onde vários trabalhos de indução são apresentados [Hunt, 1966]. Posteriormente, talvez o trabalho mais importante seja o extraordinário livro de Breiman, Friedman, Olshen e Stone, em que o algoritmo CART é apresentado [Breiman, 1984]. Também o trabalho de Quinlan [Quinlan, 1986] teve grande aceitação nesta área científica tendo servido de inspiração a muitos dos sistemas posteriormente apresentados e em particular ao seu trabalho C4.5 [Quinlan, 1993].

24

Introdução

A filosofia de funcionamento de qualquer algoritmo baseado em árvores de decisão é bastante simples. Na verdade, embora contendo por vezes diferenças importantes na forma de efectuar este ou aquele passo, qualquer algoritmo desta categoria se baseia na estratégia de dividir para conquistar. De uma forma geral, esta filosofia baseia-se na sucessiva divisão do problema em vários subproblemas de menores dimensões, até que uma solução para cada um dos problemas mais simples possa ser encontrada. Fundamentados neste princípio, os classificadores baseados em árvores de decisão procuram encontrar formas de dividir sucessivamente o universo em vários subconjuntos (criando para tal nós contendo os testes respectivos) até que cada um deles contemple apenas uma classe ou até que uma das classes demonstre uma clara maioria não justificando posteriores divisões (gerando nessa situação uma folha contendo a classe maioritária). Como é evidente, a classificação consiste apenas em seguir o caminho ditado pelos sucessivos teste colocados ao longo da árvore até que seja encontrada uma folha que conterá a classe a atribuir ao novo exemplo. V3

>3

estimação por camadas use a estimação por camadas. Todas as técnicas indicadas nestas heurísticas, são técnicas de re-amostragem de modo a garantir que todos os exemplos do conjunto de treino inicial são usados tanto para o treino do classificador como para o seu teste. Este facto elimina a possibilidade de escolha de conjuntos de treino/teste incaracterísticos e consequente obtenção de resultados excessivamente optimistas ou pessimistas.

34

Estimação da qualidade de um classificador

CAPÍTULO 3 Técnicas de construção de árvores de decisão Faz-se neste capítulo uma apresentação de várias técnicas para a solução dos diversos problemas que se colocam à construção de árvores de decisão. Diversos métodos para o cálculo e escolha da melhor partição em cada nó, para a limitação no crescimento da árvore e para o tratamento de valores desconhecidos no conjunto de treino e nos valores a classificar são, neste capítulo, apresentados e comparados entre si.

3.1. Como efectuar a partição em cada nó O tipo de partição efectuada em cada nó pode afectar de forma decisiva o desempenho da árvore de decisão produzida. A realização de testes simples sobre uma só variável definindo apenas um valor de patamar a partir do qual é decidido qual o caminho a percorrer na árvore, o cálculo de intervalos conduzindo à construção de árvores n-árias ou a combinação linear e não linear de características para a definição das partições efectuadas em cada nó, constituem opções que apresentam vantagens e desvantagens que merecem uma discussão detalhada. Também o tipo das características - discretas ou contínuas - implicam um tratamento distinto que será em seguida debatido.

3.1.1. Partições baseadas em características discretas O tratamento de características discretas é distinto daquele que é possível aplicar a características contínuas. Com efeito, a limitada cardinalidade deste tipo de características permite o cálculo de partições tendo em conta este facto e possibilitando por vezes, um grande poder descriminante. Embora seja possível efectuar combinações de características discretas para o cálculo de partições, este tipo de testes não se encontra em nenhum dos algoritmos tratados nesta tese, sendo estes efectuados sempre sobre variáveis simples.

35

36

Técnicas de construção de árvores de decisão

3.1.1.1. Um ramo por cada valor do atributo O teste mais vulgar é aquele que atribui a cada valor da característica em causa um ramo próprio. Este tipo de partição, embora permita extrair da característica todo o seu conteúdo informativo, tem como principal desvantagem a criação de um grande número de ramos muitas vezes completamente desnecessários, o que implica a formação de árvores de dimensões muitas vezes exageradas. Por outro lado, a avaliação do valor das partições é normalmente influenciada pelo número de subconjuntos a que estas conduzem, tornando bastante difícil a comparação de partições baseadas em características de cardinalidades muito diferentes.

3.1.1.2. A solução de Hunt (CLS) A solução apresentada por [Hunt, 1966] sugeria para este problema a criação de nós binários atribuindo a um dos ramos um dos valores da característica eleita e ao outro todos os outros valores. Esta solução é naturalmente limitada não aproveitando obviamente todo o poder de descriminação da característica. Tem no entanto, a vantagem da grande simplicidade e inteligibilidade resultante, especialmente útil quando os resultados da geração do classificador automático se destinam a ser interpretados por um utilizador humano.

3.1.1.3. Características ordenadas Define-se uma característica ordenada como sendo aquela que permite a definição de uma relação de ordem entre os seus possíveis valores. Quando se trata de valores deste tipo, é possível a definição de testes binários do tipo xn≤C, possibilitando a construção de árvores binárias [Breiman, 1984]. Para uma característica de cardinalidade N serão possíveis N-1 diferentes partições deste tipo que se torna necessário testar de modo a podermos garantir a escolha da melhor delas. Este método tem o inconveniente de, por vezes, não utilizar todas as capacidades de cada característica, proporcionando, no entanto, uma árvore bastante inteligível pelo observador humano.

3.1.1.4. Agrupamento de valores de características em dois conjuntos Um outra forma de calcular partições binárias sobre características discretas é também apresentado em [Breiman, 1984]. Este método, não limitado às características ordenadas, baseia-se na criação de dois subconjuntos de valores associados respectivamente, ao ramo esquerdo e direito do nó em desenvolvimento. Dado que todos os subconjuntos possíveis deverão ser testados de modo a garantir a selecção da melhor partição, um total de 2N-1-1 partições deverão ser testadas (2N-1 pois metade dos conjuntos possíveis são complementares conduzindo a partições semelhantes e -1 pois o conjunto vazio não leva a qualquer partição sendo portanto desnecessário considerá-lo). Este método tem a desvantagem de necessitar de um grande número de testes quando a cardinalidade das características é elevado. Por exemplo, para um característica com apenas 20 valores diferentes será necessário testar 220-1-1=524287 partições o que se pode tornar impraticável.

Técnicas de construção de árvores de decisão

37

3.1.1.5. Agrupamento de valores de características em vários conjuntos De modo a permitir o agrupamento de valores em vários conjuntos com uma complexidade de cálculo razoável, é apresentado em [Quinlan, 1993] um algoritmo que, embora não encontre forçosamente a melhor partição possível, permite encontrar uma solução que se verifica experimentalmente ser normalmente de boa qualidade. Para tal, começa por se calcular o valor da solução atribuindo a cada diferente valor da característica um ramo próprio. Seguidamente, testam-se todas as combinações possíveis de dois valores. Se nenhuma destas soluções for considerada pelo critério de avaliação adoptado (as funções de avaliação serão discutidas em detalhe no parágrafo 3.3) melhor que a anterior, o processo pára, sendo a solução anterior adoptada como solução final. Senão, é repetido o processo tendo como base a melhor das soluções anteriores. Vejamos um hipotético exemplo para uma característica com 4 valores distintos - A,B,C,D: Agrupamentos de atributos 1 {A} , {B} , {C} , {D} 2 {A , B} , {C} , {D} 3 {A , C} , {B} , {D} 4 {A , D} , {B} , {C} 5 {A} , {B , C} , {D} 6 {A} , {B , D} , {C} 7 {A} , {B} , {C , D} 8 {A , D , B} , {C} 9 {A , D , C} , {B} 10 {A , D} , {B , C}

Valor de avaliação 0.457 0.435 0.521 0.531 0.499 0.501 0.512 0.467 0.501 0.498

Tabela 3.2 - Exemplo de aplicação do algoritmo de agrupamento de valores a uma característica com 4 valores possíveis. Neste exemplo seria escolhida a solução quatro pois, sendo a melhor das soluções do segundo passo (2,3,4,5,6 e 7) e vantajosa em relação à inicial (1) não é superada por nenhuma das soluções do terceiro passo (8, 9 e 10). Note-se que não se pode garantir que a solução encontrada é a melhor possível pois em cada passo é escolhida a solução que permite uma maior melhoria imediata e que pode não coincidir com a solução intermédia que levaria à melhor solução final. Este é, no entanto, o preço da simplicidade do algoritmo.

3.1.2. Partições baseadas em características contínuas As características contínuas permitem uma maior variedade de testes implicando, em geral, uma maior complexidade de cálculo.

3.1.2.1. Testes simples ou pesquisa exaustiva A construção de árvores de decisão com base em testes simples, surge como a forma mais elementar de efectuar a construção de árvores de decisão com base em características contínuas. A escolha do

38

Técnicas de construção de árvores de decisão

binómio característica/ponto de cisão é efectuada de modo a que a partição daí resultante maximize o critério de valor adoptado. Deverão ser testadas e avaliadas quanto à sua qualidade todas as partições possíveis com base em cada uma das características, sendo escolhido o conjunto característica/ponto de cisão considerada de maior valor pelo critério de avaliação adoptado. Um método possível e provavelmente o mais simples, será ordenar todos os valores de um dado atributo por ordem crescente ou decrescente e testar a partição resultante da adopção de um ponto de cisão dado pelo valor médio entre cada dois valores consecutivos. Assim, para um problema com N exemplos contendo M características teremos um total de (N-1)*M partições possíveis cuja qualidade será necessário comparar. O volume de cálculo daí resultante pode, por vezes, ser excessivo. Embora este tratamento possa parecer semelhante ao dado às características discretas ordenadas, surge um pequeno pormenor importante. Dado que se está a trabalhar com valores contínuos, é necessário, neste caso, definir onde se efectua o ponto de cisão quando se encontram os dois valores - v1 e v2 entre os quais se pretende efectuar a partição. Na verdade, embora do ponto de vista do conjunto de treino seja indiferente efectuar a partição baseada em qualquer um dos testes xn≤v1 ou xnUj e por baixo caso contrário. Podemos portanto, fixando os valores de ai para i=1,...,d excepto am, e sabendo de que lado do hiperplano desejamos colocar cada ponto, podemos obter N restrições para o valor de am usando os N pontos do conjunto de treino. O problema é agora encontrar um valor para am que satisfaça o maior número possível de restrições (se conseguirmos satisfazer todas elas teremos uma partição perfeita). Este é, no entanto, um problema bastante simples. Se o novo hiperplano - substituindo am pelo seu novo valor - obtiver uma impuridade menor é adoptado o novo valor. Se a impuridade for idêntica à anterior mas o hiperplano tiver uma diferente localização o novo valor será adoptado com probabilidade ProbEstag. Este valor de probabilidade, que representa a probabilidade de um hiperplano ser alterado para um outro com diferente localização mas igual impuridade, é inicializado a 1 cada vez que se dá um decréscimo de impuridade e decresce exponencialmente cada vez que se dá uma situação de igual impuridade. Este algoritmo pode ser resumido em pseudo-código como se segue:

Técnicas de construção de árvores de decisão

43

Perturbação(H,m) { for j=1 to n Calcula(Uj) OrdenaCrescente(U1,...,Un) am1=melhor partição(U1,...,Un) H1=hiperplano que resulta da substituição de am por am1 se (impuridade(H1)0.5. Se o classificador atribuir aleatoriamente a cada amostra a classe um ou dois de acordo com a sua probabilidade de ocorrência o erro será: p(1-p)+(1-p)p = 2p(1-p)

(4.1)

o que, dado que p>0.5 será superior a (1-p) que seria o erro do classificador que simplesmente atribuísse a todas as amostras a classe mais provável. Para o caso prático apresentado no parágrafo anterior, teríamos 2*0.75(1-0.75)=0.375 o que confirma os resultados práticos obtidos por Quinlan. A título de exemplo mostra-se seguidamente um gráfico obtido a partir de [Breiman, 84 página 60] que nos dá uma ideia da evolução do erro de classificação aparente e do erro real em função da dimensão da árvore de classificação (erro real calculado com base nos resultados de classificação dum conjunto de teste independente). 100% 90% 80%

Erro estim a d o

70%

Erro rea l

60% 50% 40% 30% 20% 10% 0% 71

63

58

40

34

19

10

9

7

6

5

2

1

Número de nós termina is

Figura 4.1 - Evolução do erro aparente e do erro real em função do número de nós da árvore de decisão. Note-se o mínimo existente para o erro real quando a árvore possui dez nós tal como o facto do erro estimado crescer sempre à medida que o número de nós vai sendo reduzido. De forma a contornar o problema do crescimento exagerado das árvores de decisão, duas aproximações distintas podem ser adoptadas. A primeira aproximação tem como objectivo a paragem na construção da árvore logo que se considere ter sido atingido um nível de pormenor apropriado. A segunda adopta uma estratégia literalmente diferente sendo um processo a posteriori que visa, depois de desenvolvida a árvore ao seu máximo pormenor, reduzi-la às suas dimensões óptimas.

4.1. Métodos de limitação durante a construção Uma das hipóteses de limitar a dimensão das árvores de decisão é a interrupção do seu desenvolvimento em face de uma determinada condição. A grande vantagem deste tipo de métodos, em contraste com os métodos de poda, consiste no facto de se evitar a construção de um estrutura que virá mais tarde a ser destruída pela poda. O critério de paragem pode ser diverso tendo como característica comum o facto de se considerar estar na presença de uma folha mesmo quando o conjunto de exemplos sob consideração não pertencem apenas a uma classe.

Limitação na dimensão das árvores de decisão

61

4.1.1. Paragem baseada na informação mútua Um dos critérios de paragem que podem ser utilizados baseia-se na informação mútua. Segundo este critério, se o ganho de informação obtido com o "melhor" atributo for inferior a um determinado δ o nó em causa é considerado ser uma folha e o desenvolvimento pára.

I( C; A) = H( C) − H( C|A) En substituir o nó por uma folha com o erro E´n, senão, substituir o erro En por E´n.

Limitação na dimensão das árvores de decisão

Eʹ′n =

63 k

1 N

∑N E i

i

(4.6)

i =1

Onde: Ni - Número de exemplos abrangidos pelo i-ésimo descendente. Ei - Erro no nó i-ésimo descendente. k - número de descendentes do nó n. Adoptando a sugestão dada em (3.61) a equação anterior viria:

Eʹ′n =

1 N+k

k

∑( N i =1

i

+ 1) E i

(4.7)

4.2.2. Poda por minimização do custo-complexidade A técnica de poda por minimização do custo-complexidade baseia-se nos seguintes passos: 1º passo - Criar uma árvore inicial tão grande quanto o necessário de modo a produzir um valor de erro estimado suficientemente baixo. 2º passo - Podar sucessivamente a árvore criando um conjunto de árvores de menores dimensões. 3º passo - Utilizar uma estimação de erro "honesta" de modo a seleccionar a melhor das árvores criadas no ponto anterior. Colocam-se então duas questões fundamentais: como efectuar a poda de modo a criar a sucessão de árvores de menores dimensões ? Como estimar de uma forma "honesta" o erro de cada uma dessas árvores ? Vejamos passo por passo como efectuar as várias fases do algoritmo. 1º passo - criação da árvore inicial O primeiro passo é a construção de uma árvore de classificação tão grande quanto necessário - Tmax de modo a que se proceda de seguida à sua redução. Esta árvore inicial deverá ser tão grande quanto possível sendo normalmente limitada apenas pelo volume de processamento e armazenamento envolvidos. A dimensão desta árvore inicial não é no entanto crítica, desde que suficientemente grande. 2º passo - Criar uma sucessão de árvores de classificação por redução da árvore inicial. É interessante observar o enorme número de subárvores que é possível obter por redução mesmo a partir de árvores de pequenas dimensões. De modo a tornar o processo computacionalmente suportável, é então necessário fazer a poda de uma forma criteriosa evitando a geração de um número demasiado elevado de subárvores seleccionando à partida a "melhor" árvore de cada dimensão. Este processo implica a adopção de um critério de comparação entre árvores de iguais dimensões considerando para tal o número de nós terminais. Embora o erro estimado por resubstituição seja, como já vimos, um valor de significado relativamente pobre surge como a forma mais natural de comparar entre si árvores de iguais dimensões.

64

Limitação na dimensão das árvores de decisão

A ideia da poda por minimização do custo-complexidade é fundamentalmente fazer reflectir no processo de redução da árvore simultaneamente o critério de complexidade e o critério de custo (ou simplesmente erro para o caso de custos unitários). Seja o erro aparente num determinado nó η com um conjunto de treino t dado por:

r (η) = 1 − max p( j| t ) j

(4.8)

A contribuição de cada nó para o erro aparente total será portanto:

R (η) = p(η) * r (η)

(4.9)

~ Como é evidente, sendo T o conjunto dos nós terminais de uma qualquer árvore T, o seu erro aparente total, pode ser calculado com sendo:

R ( T) =

∑ R(η)

~ η∈T

(4.10)

Assim, define-se o valor de custo-complexidade de uma árvore T o valor dado pela expressão: ~ (4.11) R α ( T) = R ( T) + α T Onde: R(T) - erro aparente da árvore T ~ T - número de nós terminais da árvore α - constante ≥ 0 a que se dá o nome de factor de complexidade. Consegue-se assim obter uma combinação linear entre o custo da árvore e a sua complexidade. O objectivo deste tipo de poda será então encontrar a árvore que minimiza o valor de Rα fazendo variar valor de α desde 0 até que se esteja na presença de uma árvore com apenas um nó. Repare-se que, se α =0 e dado que o valor mínimo de R(T) se verifica para a maior árvore possível, será escolhida a árvore inicial Tmax. Por outro lado, para valores de α muito altos, o factor complexidade será sobrevalorizado levando a que seja seleccionada uma árvore que no limite será constituída apenas pelo primeiro nó. Vejamos então como gerar a sequência de árvores das quais se escolherá a mais apropriada. Denotam-se por ηl e ηr os descendentes esquerdo e direito de um nó η. Começando com α1=0 teremos

R α ( T) = R ( Tmax ) . Verifica-se para qualquer árvore : R (η) ≥ R (ηl ) + R (ηr )

(4.12)

Para encontrar a primeira árvore T1 visitar todos os nós de Tmax e se R (η) = R (ηl ) + R (ηr ) eliminar ηl e ηr. Este primeiro passo constitui um pré-processamento que se destina a eliminar todos os nós inúteis de forma a criar uma primeira árvore a partir da qual iniciar a verdadeira sequência de redução. O processo de redução efectua-se da seguinte forma. Seja {η} o nó que resulta da eliminação do ramo Tt. Para todos os ramos da árvore dado que R α ( Tt ) = R ( Tt ) + α T! t e que R α ({η}) = R ({η}) + α (note-se que {η} = 1), enquanto se verificar R α ( Tt ) < R α ( {η}) significa que Tt constitue melhor solução que {t}. Coloca-se então a questão de qual o valor de α para o qual teremos R α ( Tt ) = R α ( {η}) . Para o ~ sabermos teremos de resolver a equação R ( Tt ) + α Tt = R ({η}) + α de onde, resolvendo em ordem a α teremos:

Limitação na dimensão das árvores de decisão

α=

65

R ({η}) − R ( Tt ) ~ Tt − 1

(4.13)

É interessante olhar para a expressão 4.13 na perspectiva de que ela nos dá a variação do erro por nó terminal eliminado, ou seja:

α=

Δ R( T) ~ ΔT

(4.14)

Embora a equação 4.12 esteja limitada a nós com dois descendentes a sua generalização é óbvia: N

R (η) ≥

∑ R( η ) i

(4.15)

i =1

Onde: N - número de descendentes do nó η. Dever-se-á então escolher o chamado elo mais fraco, ou seja, o ramo que contem um valor de α mais baixo. Este valor de α é portanto o valor para o qual terá de se efectuar a primeira redução na árvore T1 para o que se reduz de Tt. O processo é então repetido tendo como ponto de partida o valor de α encontrado nesta interacção e a árvore que resulta da árvore inicial depois de retirado Tt. Este processo será repetido até que se encontre uma árvore contendo apenas um nó findo o qual, teremos uma sequência de árvores e respectivos valores de α tais que:

T1 ≻ T2 ≻... ≻ {η}

α1 < α 2 ε

(B.7)

4º passo - Transpor o vector encontrado para a escala original, não normalizada. É interessante observarmos qual o comportamento do programa CART, que utiliza este algoritmo para a pesquisa de combinações lineares entre os atributos, perante um problema com 30 exemplos, 14 da classe 0 e 16 da classe 1, com os valores dos atributos entre -1 e 1, sendo a classe 0 caracterizada por y>x e a classe 1 por y≤x. De forma a podermos ter uma ideia da vantagem de ser efectuada uma pesquisa deste tipo vejamos também quais os resultados obtidos pelo mesmo algoritmo sem tirar partido da combinação linear entre atributos.

y=0.03

-0.59x+0.81y-0.04 1

x=0.21 1

Figura B.2 - Árvores geradas pelo algoritmo CART sem e com combinação linear de atributos. A partição do espaço efectuada em cada um dos casos é representada na figura seguinte:

Figura B.4 - Partições resultantes das árvores geradas pelo algoritmo CART sem e com combinação linear de atributos. Repare-se na muito melhor generalização conseguida pela solução com combinação linear de atributos que não só consegue classificar correctamente todos os exemplos, o que não acontece com a outra solução, como se aproxima muito mais da solução ideal. Esta tendência para uma maior eficiência por

Algoritmo de pesquisa de combinações lineares

115

parte da solução utilizando combinações lineares é ainda mais evidente se tentarmos resolver um problema em tudo idêntico a este mas tendo no conjunto de treino 2000 exemplos. O elevado número de exemplos torna o problema especialmente difícil para a solução sem combinações entre atributos levando a que seja gerada uma árvore contendo 24 nós e 25 folhas que obtém um erro de 2% na validação cruzada. Por outro lado, a solução encontrada utilizando combinações entre atributos possue apenas um nó e duas folhas consistindo aproximadamente na recta x>y que consegue obter um erro de 0% na validação cruzada.

116

Algoritmo de pesquisa de combinações lineares

ANEXO C Comandos disponíveis e exemplo de execução do programa CART • Resumo dos comandos disponíveis Apresenta-se seguidamente um breve resumo dos comandos do programa CART. Este resumo visa apenas dar um ideia da variedade de comandos disponíveis não pretendendo de forma alguma constituir um guia de utilização do produto.

Comando Adjust Boptions

Build Case Category Cdf Charset Dos Error Fedit Format Fpath Help Hist Idvar

Significado Permite o ajuste de parâmetros críticos na gestão da memória Permite a especificação de vários parâmetros de geração das árvores de decisão tais como: limitação no crescimento da árvore inicial, número de alternativas em cada nó, número de árvores apresentadas no relatório, máximo número de classes, número de exemplos mínimo para validação por conjunto independente, tipo de relatório, etc. Lê o conjunto de treino e gera a árvore de decisão. Classifica caso-a-caso. Identifica variáveis discretas. Opcionalmente especifica o número de diferentes níveis e valores mínimos. Cálculo de distribuições, densidades ou distribuições inversas. Especifica o tipo de caracteres utilizados. Suspende o programa CART e lança uma instância do sistema operativo. Especifica o método de estimação de erro utilizado (validação cruzada, conjunto independente, estimação por resubstituição). Permite a edição de ficheiros de texto com vista ao desenvolvimento de ficheiros de comandos. Especifica a precisão com que os valores numéricos são mostrados. Define a directoria de trabalho para os vários comandos. Fornece breves explicações sobre os vários comandos. Gera gráficos de baixa resolução das variáveis. Selecciona uma variável para que seja salva ou afixada juntamente com todos os comandos de escrita no écran ou em ficheiros.

117

118

Comandos disponíveis e exemplo de execução do programa CART Limit

Linear Loptions Macro Memory Method Misclass Model Names New Note Options Output Page Pick

Priors

Quit Rem Seed Select Submit Switchto Tree Use Weight Xyplot

Especifica limites no crescimento das árvores. Permite a definição do número de exemplos abaixo do qual um nó não será mais expandido, profundidade máxima da árvore, número máximo de exemplos no conjunto de treino, máximo número de exemplos no conjunto de teste, etc. Selecciona a pesquisa de combinações lineares de variáveis contínuas. Controla um conjunto de opções binárias de controle da amostragem de resultados. Permite a execução de um ficheiro de macros. Fornece informação sobre o uso de memória e respectivas necessidades. Permite especificar o método de escolha da melhor característica (por omissão é utilizado o método de Gini). Permite especificar custos de classificação. Especifica a variável dependente e opcionalmente um subconjunto das variáveis independentes para a predição. Mostra os valores das variáveis do conjunto de treino. Anula todas as opções re-inicializando o programa. Escreve uma linha de texto no dispositivo de saída corrente. Mostra as opções correntes. Redirecciona os resultados para uma impressora, para o écran ou para um ficheiro. Permite especificar opções relacionadas com a formatação dos resultados (dimensões da página, títulos, tipo de impressora, etc). Permite rever a sequência de geração de árvores mostrando com detalhe a árvore especificada através do seu número de nós, número de sequência ou valor de complexidade. Permite ainda alterar a precisão de amostragem do valor de complexidade e o número de árvores mostradas na lista de geração de árvores. Permite definir probabilidades a priori para as classes. É possível adoptar a percentagem observada nos exemplos que se encontram simultaneamente no conjunto de treino e de teste, no conjunto de treino, no conjunto de teste, prioridades uniformes (1/número de classes), média entre as percentagens no dois conjuntos e as prioridades uniformes ou especificar as probabilidades classe por classe. Termina o programa e regressa ao sistema operativo. Permite inserir comentários na sequência de comandos (útil para ficheiros de comandos). Permite inicializar o gerador pseudo-aleatório com um valor dado pelo utilizador. Permite especificar um critério para a selecção de um subconjunto de exemplos na construção de árvores. Permite a execução de uma sequência de comandos a partir de um ficheiro de texto. Permite comutar para outro módulo SYSTAT e opcionalmente executar um ficheiro de comandos nesse módulo. Usado em conjunto com o comando build cria os ficheiros onde a informação sobre a árvore gerada é guardada para posterior análise. Abre um ficheiro SYSTAT para análise e lista o nome das variáveis contidas nesse ficheiro. Identifica uma variável para ser usada como peso de classificação. Produz gráficos a duas dimensões de baixa resolução das variáveis no conjunto de treino. Tabela C.1 - Comandos disponíveis no programa CART.

Comandos disponíveis e exemplo de execução do programa CART

119

• Exemplo de execução O exemplo transcrito neste anexo é o resultado da execução dos comandos contidos no ficheiro Heart.cmd. Conteúdo do ficheiro Heart.cmd output heart.res format=6 use heart tree heart category class=2,v2,v3,v6,v7,v9,v13 priors data model class error cross=10 build

Significado Resultados colocados no ficheiro heart.res Valores mostrados com 6 casas decimais Valores no ficheiro heart.sys Árvore colocada no ficheiro heart.tr1 e heart.tr2 Variável discreta Class com dois valores possíveis. Definição das variáveis v2, v3, v6, v7, v9 e v13 como discretas Distibuição de prob. para as classes baseadas no conj. treino Variável dependente Class Estimação de erro por validação cruzada de 10 camadas Gera árvore

Figura C.1 - Conteúdo do ficheiro Heart.cmd. ######################################## ############################################################ ###### ## ## ###### ######## ## ######## ### ## ## ## ### ## ## #### ## ### ## ## ### ## ## ## ## ### #### ### ## ######## ## ## ### ## ## ### ## ## ## ## ###### ## ###### ## ## ## ## #########################################################(R) ###################################### CART VERSION 1.01 (INTERFACE 5.02) COPYRIGHT, 1993 SYSTAT, INC. 60000 PREPROCESSOR WORKSPACE ELEMENTS. 625000 TREE BUILDING WORKSPACE ELEMENTS. SYSTAT BASIC WORKSPACE CLEARED. >submit heart VARIABLES IN SYSTAT RECT FILE ARE: V1 V2 V3 V6 V7 V8 V11 V12 V13

V4 V9 CLASS

V5 V10

HEART.SYS: 31142 BYTES, 270 RECORDS. SYSTAT BASIC WORKSPACE CLEARED. RECORDS READ: 270 RECORDS WRITTEN IN LEARNING SAMPLE: 270

Número de exemplos lidos Nº de exemplos no conj. de treino

AUTOMATIC LEVEL SETTINGS NAME LEVELS MINIMUM -------------------------------------V2 2 0 V3 4 1 V6 2 0 V7 3 0 V9 2 0 V13 5 3 CLASS 2 1 DATA

PRIORS:

0.555556

0.444444

CURRENT MEMORY REQUIREMENTS TOTAL: 17448 DATA: AVAILABLE: 625000 SURPLUS: 607552

3780

270 Observations in the learning sample. File: HEART.SYS ============= TREE SEQUENCE ============= Dependent variable: CLASS

Necessidades de memória ANALYSIS: 13668

Ficheiro de dados utilizado Sequência de redução

120

Comandos disponíveis e exemplo de execução do programa CART

Terminal Cross-Validated Resubstitution Complexity Tree Nodes Relative Cost Relative Cost Parameter -----------------------------------------------------------------1 19 0.550000 +/- 0.058562 0.166667 0.000000 2 18 0.550000 +/- 0.058562 0.166667 0.000010 3 15 0.508333 +/- 0.056540 0.191667 0.003714 4 11 0.516667 +/- 0.056780 0.233333 0.004640 5* 8 0.483333 +/- 0.055877 0.283333 0.007417 6** 6 0.500000 +/- 0.056667 0.325000 0.009269 7 4 0.541667 +/- 0.058392 0.416667 0.020380 8 2 0.675000 +/- 0.062542 0.533333 0.025936 9 1 1.000000 +/- 0.000064 1.000000 0.207417 Initial misclassification cost = 0.444444 Initial class assignment = 1 CROSS VALIDATION RELATIVE COST VS. NUMBER OF NODES -------------------------------------------------------------1.000064 |* | | | 0.928488 | | | | 0.856912 | | | | 0.785336 | | | . | 0.713760 | | | * | 0.642184 | | | . . . .| 0.570608 | . . . | | * . * *| 0.499032 | . * * * * . .| | . . | 0.427457 | . . | -------------------------------------------------------------1.000000 | 10.000000 | 19.000000 5.500000 14.500000 C.V. & RESUB (*) RELATIVE COST VS. NUMBER OF NODES -------------------------------------------------------------1.000064 |* | | | 0.895890 | | | | 0.791715 | | | | 0.687540 | * | | | 0.583365 | | | * * * * * *| 0.479191 | * * | | * | 0.375016 | | | * | 0.270841 | * | | * | 0.166667 | * * *| -------------------------------------------------------------1.000000 | 10.000000 | 19.000000 5.500000 14.500000 COMPLEXITY VS. NUMBER OF NODES -------------------------------------------------------------0.207417 |* | | | 0.181490 | | | | 0.155563 | | | | 0.129636 | | | | 0.103709 | | | | 0.077782 | | | | 0.051854 | | | | 0.025927 | * * | | * * |

Comandos disponíveis e exemplo de execução do programa CART

121

0.000000 | * * * *| -------------------------------------------------------------1.000000 | 10.000000 | 19.000000 5.500000 14.500000 =========================== CLASSIFICATION TREE DIAGRAM ===========================

| --------------------------1-------------------------| | ------------2---------------------4----------| | | | --------3--------------5------| | | | Terminal Regions 1

2

3

4

5

6

================ NODE INFORMATION ================ * * *

Node 1 was split on variable V13 A case goes left if variable V13 = (3,4,5) Improvement = 0.133150 C. T. = 0.207407

*

* 1 * * * * * * * * * * 152 118 * * *

*

*

* * *

Node 1 2 4

* *

* 2 * * * * * *

* *

*

* * *

* 4 * * * * * *

* * *

* 2 * * * * * * * * * * 101 51 * *

Cases 270 152 118

Class 1 1 2

Number Of Cases Top Left Right 150 119 31 120 33 87

Class 1 2 1 2 3 4 5

Surrogate V9 V8 V2 V3 V10

1 2 3 4 5

Competitor V3 V12 V9 V8 V10

Cost 0.444444 0.217105 0.262712 Top 0.555556 0.444444

Split s 0 r 150.500000 s 0 s 1,2,3 s 1.550000

Within Node Prob. Left Right 0.782895 0.262712 0.217105 0.737288

Assoc. 0.245762 0.237288 0.228812 0.228812 0.220338

Split 1,2,3 0.500000 0 147.500000 1.700000

Improve. 0.086822 0.073604 0.043772 0.124630 0.066610 Improve. 0.124630 0.109989 0.086822 0.080584 0.079299

Node 2 was split on variable V3 A case goes left if variable V3 = (1,2,3) Improvement = 0.031098 C. T. = 0.025926

*

* ---*--| | | | | 1 | | | | | -------

Node 2 -1 3

* * * *

*

*

* 3 * * * * * *

Class 1 2

Cases 152 101 51

Class 1 1 1

Number Of Cases Top Left Right 119 91 28 33 10 23

1 2 3 4 5

Surrogate V9 V8 V4 V12 V10

1 2 3 4 5

Competitor V12 V8 V10 V1 V9

Cost 0.217105 0.099010 0.450980 Top 0.782895 0.217105

Split s 0 r 125.500000 s 167.000000 s 2.500000 s 3.100000 Split 0.500000 119.500000 2.100000 57.500000 0

Within Node Prob. Left Right 0.900990 0.549020 0.099010 0.450980

Assoc. 0.196078 0.137255 0.058822 0.039214 0.039214

Improve. 0.017244 0.018630 0.004582 0.017571 0.017571 Improve. 0.029491 0.023779 0.023779 0.019263 0.017244

122

Comandos disponíveis e exemplo de execução do programa CART * * * *

*

*

3 * * * * * * * * * 31 20 * * *

Node 3 was split on variable V12 A case goes left if variable V12 156

25

V12

0

1