Indução de Árvore de Decisão
Jacques Robin
Roteiro
1.
2.
3.
4.
5.
6.
7.
8.
9.
Entrada e saída da indução de árvore decisão
Tarefas de aprendizagem implementadas por ID3
Exemplo
Algoritmo básico e complexidade
Heurísticas de escolha do atributo de partição de exemplos
Poda da árvore para evitar overfitting
Atributos numéricos, multi-valorados, nulos e numerosos
Árvores de regressão e de modelo
Vantagens e limitações de ID3
Entrada e saída da
indução de árvore de decisão (ID3)
age
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
income student
high
high
high
medium
low
low
low
medium
low
medium
medium
medium
high
medium
no
no
no
no
yes
yes
yes
no
yes
yes
yes
no
yes
no
credit
rating
buys
computer
fair
excellent
fair
fair
fair
excellent
excellent
fair
fair
fair
excellent
excellent
fair
excellent
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no
age?
30..40
<=30
student?
no
yes
no
yes
>40
credit rating?
yes
excellent
fair
no
yes
Tarefas de aprendizagem
realizáveis por ID3
 Classificação:
 Atributos classificadores nos ramos
 Valores da classe nas folhas
 Regressão:
 Valores das variáveis fornecidas nos ramos
 Valor da variável a estimar nas folhas
 Previsão temporal:
 Valores passadas do atributo a prever nos ramos
 Valor futura do atributo a prever nas folhas
 Detecção de padrão:
 Valores antecedentes da associação nos ramos
 Valores conseqüentes da associação nas folhas
 Controle:
 Atributos descrevendo situação nos ramos
 Ação a executar nessa situação nas folhas
 Otimização:
 Valores das variáveis do domínio da função a otimizar nos ramos
 Valor da imagem máxima ou mínima da função das folhas
Expressividade das árvores de decisão
 Representação como programa
lógico:
age?
30..40
<=30
student?
no
yes
no
yes
>40
credit rating?
yes
excellent
fair
no
yes
buy(X,computer) :- age(X) <= 30,
student(X), creditRating(X,fair).
buy(X,computer) :- age(X) >= 30,
age(X) <= 40.
buy(X,computer) :- age(X) > 40,
creditRating(X,fair).
Expressividade das árvores de decisão
 Representação proposicional:
age?
30..40
<=30
student?
no
yes
no
yes
>40
credit rating?
yes
excellent
fair
no
yes
((under30  student)  30something
 (over40  fairCreditRating)
 buyComputer
 ((under30   student) 
 (over40  excellentCreditRating)
  buyComputer)
 (under30  30something  over40)
  (under30  30something)
  (under30  over40)
  (over40  30something)
 (fairCreditRating
 excellentCreditRating)
  (fairCreditRating
 excellentCreditRating)
Expressividade das árvores de decisão
 Pode representar qualquer função booleana
 No entanto, algumas funções – como a função de paridade ou de
maioria – só podem serem representadas por uma árvore de tamanho
exponencial no número de atributos
 Cardinal do espaço de hipótese de uma tarefa de aprendizagem com
6 atributos booleanos: 18.446.744.073.709.551.661
 Mesmo para problemas pequenos:
 Aprender árvores pequenos o suficiente para serem inteligível e então
validáveis
 Requer heurísticas (i.e., viés) podendo a busca no espaço de hipótese de
maneira violenta
 Em recuperação de informação utiliza-se geralmente um número de
atributo igual a o número de palavras na língua utilizada nos
documentos ...
Algoritmo básico de ID3
 Escolher dentro do conjunto de atributo atual A = {A1,..., Ak}
o atributo Ai que separa melhor o conjunto atual de exemplos
E em termos dos valores do atributo a prever P
 Dividir E em termos dos valores de Ai = {Vi1,..., Vik}
i.e., E =  Ej, x  Ej, Ai(x) = Vij,
criando um novo arco teste Ai(x) = Vii na árvore para cada Ej
 Para todos Ei ainda heterogêneos em termos do valor de P
i.e., x,y  Ei, P(x)  P(y),
 Recursivamente reaplicar algoritmo sobre Ej com o conjunto de
atributo A´= A – {Ai}
 Continuar até que:
 Todos os Ej seja homogêneos em termos do valor de P
 Não tenha mais atributos a processar, i.e., A´= 
Viés de aprendizagem de ID3
age
 Árvore aprendida com viés de ID3
 Número de bits: 3
<=30
30..40
>40
student
buy
+
-
-
+
credit
excel
fair
-
+
+
 Árvore “aprendida” sem viés
 Número de bits: 6
age
BC
<=30
30..40
>40
income
income
income
high
medium
low
high
medium
low
high
medium
low
student
student
student
student
student
student
student
student
student
+
-
+
-
+
-
+
-
+
-
+
-
+
-
+
-
+
-
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
CR
e
f
?
?
e
f
e
f
e
?
?
f
e
?
f
e
f
e
?
?
?
f
e
?
f
e
f
?
?
e
f
?
e
f
e
f
e
f
e
f
e
?
?
?
?
?
?
?
?
f
e
f
e
f
e
f
?
?
Heurísticas de escolha de atributo de
partição de exemplos
 Ganho da informação
 Índice GINI
Ganho da informação
 Informação (em número de bits) esperada necessária para
classificar, em m classes, amostra arbitrária de s exemplos:
m
I( s1,s2,...,sm )  
i 1
si
si
log 2
s
s
Si = numero de exemplos de classe i
 Informação esperada necessária para classificar, em m classes, dado
o valor, entre V valores possíveis, do atributo A (entropia de A):
s1 j  ... smj
E(A) 
I ( s1 j ,...,smj ) Si j = numero de exemplos de classe i
s
com valor j para atributo A
j 1
v
 Ganho de informação pelo conhecimento do valor de A:
Gain(A) I(s1, s 2 ,...,sm)  E(A)
Exemplo de escolha de atributo baseado
na heurística do maior ganho de informação
5
4
E ( age) 
I ( 2,3) 
I ( 4,0)
14
14
5

I (3,2)  0.694
14
Class p: buysComputer = “yes”
 Class n: buysComputer = “no”
 I(p, n) = I(9, 5) = 0.940
 Entropia para age:

age
<=30
30…40
>40
pi
2
4
3
ni
3
0
2
I(pi, ni)
0.971
0
0.971
age <= 30 para 5/14 dos exemplos
dos quais 2 buyComputer = yes
e 3 buyComputer = no
age
income
student
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
high
high
high
medium
low
low
low
medium
low
medium
medium
medium
high
medium
no
no
no
no
yes
yes
yes
no
yes
yes
yes
no
yes
no
credit
rating
fair
excellent
fair
fair
fair
excellent
excellent
fair
fair
fair
excellent
excellent
fair
excellent
buys
computer
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no
Gain(age)  I ( p, n)  E (age)  0.246
Gain(income)  0.029
Gain( student )  0.151
Gain(credit _ rating )  0.048
Exemplo de ID3
age
income
student
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
high
high
high
medium
low
low
low
medium
low
medium
medium
medium
high
medium
no
no
no
no
yes
yes
yes
no
yes
yes
yes
no
yes
no
credit
rating
fair
excellent
fair
fair
fair
excellent
excellent
fair
fair
fair
excellent
excellent
fair
excellent
buys
computer
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no
age?
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e11
e12
e13
e14
<=30
31..40
+: e9, e11
+: e3, e7, e12, e13
-: e1, e2, e8
>40
+: e4, e5, e10
-: e6, e14
Exemplo de ID3
age?
<=30
31..40
+: e9, e11
+: e3, e7, e12, e13
-: e1, e2, e8
income
student
high
high
medium
low
medium
no
no
no
yes
yes
credit
rating
fair
excellent
fair
fair
excellent
buys
computer
no
e1
no
e2
no
e8
yes
e9
yes
e11
student?
no
yes
+: e9, e11
-: e1, e2, e8
>40
+: e4, e5, e10
-: e6, e14
Exemplo de ID3
age?
<=30
31..40
>40
+: e9, e11
+: e3, e7, e12, e13
+: e4, e5, e10
-: e1, e2, e8
-: e6, e14
student?
income
student
medium
low
low
medium
medium
no
yes
yes
yes
no
credit
rating
fair
fair
excellent
fair
excellent
buys
computer
yes
e4
yes
e5
no
e6
yes
e10
no
e14
credit rating?
no
yes
excellent
fair
+: e9, e11
-: e1, e2, e8
-: e6, e14
+: e4, e5, e10
Poda de árvores para evitar overfitting
 Broto de decisão: árvore de decisão de profundidade 1
 Em muitos casos, tão precisão se não melhor sobre conjunto de teste do
que árvore de decisão completa gerada por ID3
 Caso também de kNN, Classificador Bayesiana Ingênuo e Regra de
Classificação 1R, i.e., regra da forma: atributo a = v  classe = c
 Em processo de aprendizagem qualquer, sempre começar pelo uso desses
métodos simplórios, pós as vezes eles são suficientes, e sempre eles
constituem um caso base para a avaliação de métodos mais sofisticados
 Sugere idéia de podar árvores geradas por ID3 para melhorar sua
generalidade
 Pré-poda:
 Introduzir novo ramo na árvore apenas para gerar divisão de exemplos
estatisticamente significativa (por exemplo usando um test 2
 Pós-poda:
 Podar árvore completa testando diferencia de precisão sobre outro conjunto
de exemplos de duas operações de poda, colapso de ramo e subida de ramo
Operações de pós-poda: colapso de ramo
age?
age?
30..40
<=30
student?
no
yes
no
yes
>40
<=30
30..40
credit rating?
yes
excellent
fair
no
yes
>40
credit rating?
no
yes
excellent
fair
no
yes
Operações de pós-poda: elevação de ramo
age?
student?
30..40
<=30
student?
no
yes
no
yes
yes
>40
no
yes
credit rating?
age?
credit rating?
excellent
fair
<=30
30..40
>40
excellent
fair
no
yes
no
yes
yes
no
yes
Pós-poda
 Processa a árvore de baixo para cima estimando benefício, em cada
nó, de uma das duas operações
 Divide conjunto de exemplos em 3 partes:
 Conjunto de construção da árvore
 Conjunto de poda da árvore
 Conjunto de teste da árvore podada
 Problemático com conjunto de exemplos pequenos:
 Solução de C4.5
 Executa poda sobre mesmo conjunto do que a construção, usando um
estimador estatístico diferente do ganho de informação usado para
construção
Complexidade de ID3
 Abstrair e exemplos de treinamento,
cada um descrito por a atributos
por uma árvore de decisão de profundidade O(log n)
 Execução: O(log n)
 Treinamento sem poda: O(mn log n)
 Pós-poda: O(n (log n)2)
Outras dificuldades práticas
 Atributos multi-valorados
 ID3 supõe que cada atributo de cada exemplo possui apenas um único
valor
 Nem é sempre o caso: ex, filhos de uma pessoa
 Atributos com distribuição de valores muito desigual
 ID3 tende a gerar broto de decisão
Atributos numerosos
 Ganho de informação super-estima atributos com muitos valores
distintos
 Atributos com um valor distinto por exemplo, completamente inútil
para classificação, no entanto com maior ganho de informação
 Uma solução simples: usar razão do ganho sobre número de valores
do atributo
Atributos nulos
 Utilização:
 Como classificar novo exemplo com atributo nulo ?
 Prever valor nulo como sendo valor adicional
 Treinamento:
 Simplesmente excluir exemplos ou atributos com valores nulos não é
sempre viável porque:
 As vezes exemplo com valor nulo para determinado atributo, é extremamente
informativo com respeito a outros atributos,
 ou atributo com valor com valor nulo para determinado exemplo, é
extremamente informativo via seus valores para outros exemplos
 tamanho e dimensionalidade dos exemplos de treinamento ficam baixo demais
 É necessário modificar a fórmula do ganho de informação para a tornar
tolerante a valores nulos
Atributos numéricos
 Qual é a partição em faixa de valores que maximiza o ganho de
informação ?
Árvore de regressão
Regressão linear paramêtrica:
PRP = - 56.1 + 0.049MYCT + 0.015MMIN + 0.006MMAX + 0.630CACH - 0.270CHMIN + 1.46CHMAX
Árvore de regressão para mesma tarefa:
Árvore de modelo
Árvore de modelo para mesma tarefa:
LM1: PRP = 8.29 + 0.004 MMAX + 2.77 CHMIN
LM2: PRP = 20.3 + 0.004 MMIN – 3.99 CHMIN + 0.946 CHMAX
LM3: PRP = 38.1 + 0.012 MMIN
LM4: PRP = 19.5 + 0.002 MMAX + 0.698 CACH + 0.969 CHMAX
LM5: PRP = 285 – 1.46 MYCT + 1.02 CACH – 9.39 CHMIN
LM6: PRP = -65.8 + 0.03 MMIN – 2.94 CHMIN + 4.98 CHMAX
Vantagens de ID3
Muito versátil
Algoritmo de aprendizagem muito simples, e então fácil de entender
Muito bem estudado
Eficiente e escalável
Disponível na grande maioria das caixas de ferramenta gerais para
aprendizagem
 Processa cada exemplo apenas uma única vez





Limitações de ID3
 Redundância para
representar sem muita
redundância funções sem
ordem claro de poder
separativo dos exemplos
entre atributos
 Não pode aprender
relacionamentos genéricos
entre vários indivíduos,
 ex: árvore de decisão
definindo conceito de mãe,
de ancestral ?
 Não é incremental: todos
os exemplos tem que ser
disponíveis com
antecedência