Arvores de Classificacao
Extraccao de Conhecimento– Mestrado em Engenharia Informatica –
– Licenciatura em Engenharia Informatica e Computacao –
Rui CamachoLIACC/FEUP Universidade do Porto
www.fe.up.pt/∼ec
Novembro 2005
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Topicos
I O que sao
I Como se constroem
I Exemplos
I Topios avancados sobre Arvores de Decisao
I wrappers
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Arvores de Decisao
Bibliografia
I Machine Learning,Tom MitchellMcGraw-Hill, 1997
I C4.5: programs for machine learning,Ross QuinlanMorgan Kaufmann Publishers, 1993
I Classificatin and Regression Trees,Leo Breiman, J. Friedman, R. Olshen e C.StoneChapman & HallEllis-Horwood editors, 1984
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Sistemas
I ID3 (Ross Quinlan, 1986)
I C4.5 (Ross Quinlan, 1993)
I C5.0/See5 (Ross Quinlan)
I CART (Leo Breiman et al, 1980)
I Random Forest (RF) (Leo Breiman et al)
I ASSISTANT86 (Ivan Bratko et al)
I Ltree (Joao Gama)
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Aplicacoes
I Construcao/utilizacao de Classificadores ;-)
I Processo automatico de aquisicao de Conhecimentoexemplo: sistema KARDIO (Bratko, Lavrac, Mozetic, Kononenko)
I Explicitacao de ConhecimentoArvores de Decisao como pos-processamento para “sistemas opacos” (ex:RN)
exemplo: C4.5 + boxes
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Arvore de Decisao para “decidir ir jogar Tenis”
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Arvore para prever Riscos com Cesarianas (C-Section Risk)
Construıda a partir de 1000 registos de mulheresOs exemplos negativos sao as C-sections
[833+, 167−] .83 + .17−FetalP resentation = 1 : [822+, 116−] .88 + .12−| PreviousC section = 0 : [767+, 81−] .90 + .10−| | Primiparous = 0 : [399+, 13−] .97 + .03−| | Primiparous = 1 : [368+, 68−] .84 + .16−| | | FetalD istress = 0 : [334+, 47−] .88 + .12−| | | | BirthW eight < 3349 : [201+, 10.6−] .95 + .05−| | | | BirthW eight >= 3349 : [133+, 36.4−] .78 + .22−| | | FetalD istress = 1 : [34+, 21−] .62 + .38−| PreviousC section = 1 : [55+, 35−] .61 + .39−FetalP resentation = 2 : [3+, 29−] .11 + .89−FetalP resentation = 3 : [8+, 22−] .27 + .73−
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Representacao
Representacao das Arvores de Decisao:
I Cada no interno efectua um teste a um atributo
I Cada ramo corresponde a um valor para o atributo testado
I Cada folha atribui uma classificacao
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Quando decidir usar uma A.D.?
I Instancias/casos codificaveis por pares atributo-valor
I Funcao pretendida e conjunto de valores discretos
I Pode ser necessario haver hipoteses disjuntas
I Possibilidade de haver ruıdo nos dados
Exemplos:
I Tarefa de diagnostico medico ou de um equipamento
I Analise de risco de credito
I Modelizar preferencias de marcacao de reunioes
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Escolha do valor de controlo dos elevators
altitude altitude desvio velocidade elevators(referencia) altitude subida
2500 2495 -5 100 nao altere2500 2500 0 100 empurre2500 2505 5 100 empurre2500 2495 -5 0 puxe2500 2500 0 0 nao altere2500 2505 5 0 empurre2500 2495 -5 -100 puxe2500 2500 0 -100 puxe2500 2505 5 -100 nao altere2400 2395 -5 100 nao altere2400 2400 0 100 empurre2400 2405 5 100 empurre2400 2395 -5 0 puxe2400 2400 0 0 nao altere2400 2405 5 0 empurre2400 2395 -5 -100 puxe2400 2400 0 -100 puxe2400 2405 5 -100 nao altere
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Escolha do valor dos elevators (cont.)
altitude altitude desvio velocidade elevatorsreferencia altitude subida
2600 2595 -5 100 nao altere2600 2600 0 100 empurre2600 2605 5 100 empurre2600 2595 -5 0 puxe2600 2600 0 0 nao altere2600 2605 5 0 empurre2600 2595 -5 -100 puxe2600 2600 0 -100 puxe2600 2605 5 -100 nao altere
velocidade subita e climb rate
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Escolha do valor de controlo dos elevators
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Top-Down Induction of Decision Trees
Ciclo principal:
1. At ← o “melhor” atributo para o teste do proximo no
2. Aceitar At como atributo a testar no no
3. Para cada valor possıvel de At criar um descendente do no
4. Distribuir os exemplos de treino pelas folhas actuais
5. Se os exemplos de treino sao correctamente classificadosentao PARE caso contrario repita recursivamente o processopara cada no descendente
Questao central: Qual e o melhor atributo?
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Entropia
I S e uma amostra do conjunto de treino
I pa e a proporcao de exemplos da classe “a” em S
I pb e a proporccao de exemplos da classe “b” em S
I A Entropia mede o grau de impureza de S
Entropia(S) ≡ −pa log2 pa − pb log2 pb
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Entropia
Entropia(S) = numero esperado de bits necessarios para codificara classe (“a” ou “b”) de um elemento de S escolhidoaleatoriamente com distribuicao uniforme (sob o optimo, codigo decomprimento mınimo)
Porque?Da Teoria da Informacao: um codido de comprimento optimoatribui − log2 p bits a uma mensagem que tenha probabilidade p.
Logo, o numero esperado de bits para codificar “a” ou “b” deelementos selecionados aleatoriamente de S e:
pa(− log2 pa) + pb(− log2 pb)
Entropia(S) ≡ −pa log2 pa − pb log2 pb
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Ganho de Informacao
Ganho(S,A) = reducao esperada na entropia por usar o atributo A
Ganho(S ,A) ≡ Entropia(S) −∑
v∈Valores(A)
|Sv ||S |
Entropia(Sv )
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Conjunto de treino
Day Outlook Temperature Humidity Wind PlayTennis
D1 Sunny Hot High Weak NoD2 Sunny Hot High Strong NoD3 Overcast Hot High Weak YesD4 Rain Mild High Weak YesD5 Rain Cool Normal Weak YesD6 Rain Cool Normal Strong NoD7 Overcast Cool Normal Strong YesD8 Sunny Mild High Weak NoD9 Sunny Cool Normal Weak YesD10 Rain Mild Normal Weak YesD11 Sunny Mild Normal Strong YesD12 Overcast Mild High Strong YesD13 Overcast Hot Normal Weak YesD14 Rain Mild High Strong No
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Espaco de Hipoteses procurado pelo ID3
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
O Espaco das Hipoteses
I O espaco das hipoteses e completo!I A funcao solucao esta garantidamente la ...
I Calcula uma unica hipotese (Qual?)I Sem back tracking
I Mınimos locais...
I Escolhas feitas na procura baseadas em EstatısticasI Robusta em dados com ruıdos...
I Inductive bias: em caso de proximidade “prefira as arvoresmais pequenas”
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Procura do ID3 no Espaco das Hipoteses
I Das arvores mais simples para as mais complexas
I Procura tipo hill-climbing
I Preferir arvores mais simples em caso de alternativassemelhantes (search bias)
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Inductive Bias no ID3
H e o produto cartesiano das instancias X
I Preferencia por arvores pequenas, e pelas que tem atributoscom maior ganho de informacao perto da raiz
I Bias e uma preferencia por algumas hipoteses, e nao umarestricao do espaco de hipoteses H
I Princıpo de Occam’s razor: prefira a hipotese mais simplesque explique os dados
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Princıpio de Occam’s Razor
Porque preferir a hipotese mais simples?
Argumentos a favor:I Ha mais hipoteses simples do que complexas
→ uma hipotese simples que explique os dados e menos provavelque seja coincidencia
→ uma hipotese complexa que explique os dados pode ser umacoincidencia
Argumentos contra:I Ha muitas maneiras de definir pequenos conjuntos de
hipotesesI exemplo: todas as arvores com um numero primo de nos que
usam atributos comecados com “Z”I O que ha de tao especial nos conjuntos pequenos baseados no
tamanho da hipotese?
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Inductive Bias – Preferencias
language bias Preferencia determinada pelo poder derepresentacao da linguagem escolhida.Tambem conhecido como restriction bias
search bias Preferencia por determinadas alternativas durante aprocura no espaco das hipoteses.Tambem conhecido como preference bias
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Sobre-ajuste em Arvores de Decisao
Considere a adicao do exemplo, com ruıdo, numero 15:
Sunny , Hot, Normal , Strong , PlayTennis = No
Qual o efeito sobre a arvore anterior?
Sobre-ajuste e traducao de overfitting
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Sobre-ajuste
Considere que o erro da hpotese h no
I conjunto de treino e: errotreino(h)
I na distribuicao toda D dos dados: erroD(h)
A hipotese h ∈ H sobre-ajusta os dados de treino se existir umahipotese alternativa h′ ∈ H tal que
errotreino(h) < errotreino(h′)
eerroD(h) > erroD(h′)
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Evitar o sobre-ajustamento
Como evitar o sobre-ajustamento?
I Pare de crescer a arvore quando a divisao nao eestatisticamente significativa
I Cresca a arvore completa e remova posteriormente “nosinuteis” (post-prune)
Como seleccionar “a melhor” arvore:
I Meca o desempenho no conjunto de treino
I Meca o desempenho num conjunto a parte (de validacao)
I MDL: minimise tamanho(arvore) +tamanho(malclassificados(arvore))
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Poda tipo Reduced-Error
Divida os dados num conjunto de treino e de validacao
Faca ate que o pruning seja prejudicial:
1. Avalie o impacto do pruning no validation set em cada nopossıvel (mais os seus descendentes)
2. De modo ganancioso remova o no que tiver maiormelhoramento de accuracy no no conjunto de validacao
I Produz a versao mais pequena da subarvore mais precisa
I E se a quantidade de dados for limitada?
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Regra de “Pos-Poda”
1. Converta a arvore num conjunto equivalente de regras
2. Faca o pruning de cada regra de modo independente dasoutras
3. Ordene as regras finais na sequencia desejada para utilizacao
Provavelmente o metodo mais usado (e.g., C4.5)
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Converter uma Arvore em Regras
IF (Outlook = Sunny) ∧ (Humidity = High)THEN PlayTennis = No
IF (Outlook = Sunny) ∧ (Humidity = Normal)THEN PlayTennis = Yes
. . .
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Atributos com Valores Contınuos
Gerar dinamicamente um atributo discreto para o teste deatributos contınuos
I Temperature = 82.5
I (Temperature > 72.3) = t, f
Temperature: 40 48 60 72 80 90PlayTennis: No No Yes Yes Yes No
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Atributos com muitos valores
Problema:
I Se um atributo tem muitos valores, Ganho vai escolhe-lo
I Considere a utilizacao da Data = Nov 16 2004 como atributo
Uma abordagem: use antes o GainRatio
GainRatio(S ,A) ≡ Gain(S ,A)
SplitInformation(S ,A)
SplitInformation(S ,A) ≡ −c∑
i=1
|Si ||S |
log2|Si ||S |
em que Si e um subconjunto de S para o qual A tem valor vi
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Atributos com Custos
Considere
I Diagnostico medico, TestAoSangue tem custo 150 (euro)
I Robotica, Width from 1ft tem custo 23 sec.
Como construir uma arvore consistente com custo esperado baixo?Uma abordagem: substituir ganho por
I Tan and Schlimmer (1990)
Ganho2(S ,A)
Custo(A).
I Nunez (1988)2Ganho(S ,A) − 1
(Custo(A) + 1)w
em que w ∈ [0, 1] determina a importancia do custo
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Lidar com Valores desconhecidos de Atributos
E se for desconhecido o valor do atributo A nalguns exemplos?Use na mesma o conjunto de treino
I Se o no n testa A, atribua o valor mais comum de A entre osexemplos que chegaram a esse no n
I Atribua o valor mais comum de A entre os outro sexemploscom o memso valor da classe
I Atribua probabilidades pi a cada possivel valor vi de AI Atribua um afraccao pi de exemplo a cada descendente na
arvore
Classifique novos exemplos da mesma maneira
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Attribute spaceregions boundaries parallel to the axis
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Attribute spaceregions boundaries not parallel to the axis
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
cart decision tree for setting elevators
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
Parameterised tree for setting elevators
climbRateGoal and altitudeGoal are the parameters
Rui Camacho Extraccao de Conhecimento
Arvores de Classificacao
C4.5
Ross Quinlan 1984
I Ganho de Informacao usado como criterio de escolha dosatributos
I gain / gain ratio
I windowing
I subsetting de valores de atributos
Rui Camacho Extraccao de Conhecimento