Click here to load reader

Lesson 4: Decision Trees

  • View
    2.135

  • Download
    6

Embed Size (px)

DESCRIPTION

The objective of this lesson is to introduce the most popular algorithms for decision tree induction (ID3, c5.4) based on a greedy search strategy. More information is given in the course site: https://sites.google.com/site/gladyscjaprendizagem/program/decision-trees

Text of Lesson 4: Decision Trees

  • 1. Captulo 4
    Aprendizagem de rvores de Deciso

2. Figura extrada dos acetatos deIntroduction to Data Mining P. Tan, M.Steinbach, V.Kumar
Aprendizagem SupervisadaEsquema Geral
Um conjunto de treino com exemplos rotulados usado para treinar o classificador. Cada exemplo representa um objecto descrito pelos seus atributos e a sua classe.
1. Um algoritmo de aprendizagem executado para induzir umclassificador a partir do conjunto de treino
conjunto de exemplos sem rtulos
2. Uma vez construdo o classificador, este pode ser usado para classificar futuros exemplos
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
3. Modelos de Classificao Supervisada
rvores de decisoQuinlan, 1986; Breiman y col. 1984
Classificadores baseados em regrasClark y Nibblet, 1989; Cohen, 1995; Holte, 1993
Classificadores baseados em instncias
Classificadores kNNCovert & Hart, 1967; Dasarathy, 1991
Classificadores Bayesianos
Nave BayesDuda & Hart, 1973
Redes BayesianasPearl, 1988
Redes NeuronaisMcCulloch & Pitts, 1943
Mquinas de suporte vectorialCristianini & ShaweTaylor,2000
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
4. Problema de Classificao: x1, x2- 2 variveis preditoras5 classes C
f:x1x2 C
Figura extrada dos acetatos sobre rvores de deciso de Joo Gama
rvore de Deciso
raiz
regra
n de deciso
Cada n de deciso contem um teste num atributo
Cada ramo descendente corresponde a um possvel valor deste atributo.
Cada folha est associada a uma classe.
Cada percurso na rvore (da raiz folha) corresponde a uma regra de classificao.
folhas
IFx1 < a1ANDx2< a3THEN
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
5. Problema de Classificao: x1, x2- 2 variveis preditoras5 classes C
f:x1x2 C
Figura extrada dos acetatos sobre rvores de deciso de Joo Gama
rvore de decisoEspao de Atributos
No espao definido pelos atributos:
cada folha corresponde a uma regio: um hiper-rectngulo
a interseco dos hiper-rectngulos = vaza
a unio dos hiper-rectngulos = espao completo
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
6. Figura extrada dos acetatos deIntroduction to Data Mining P. Tan, M.Steinbach, V.Kumar
rvore de Deciso Exemplo 2: Atribuio de Crdito Bancrio
Conjunto de Treino
Refund
Yes
No
Aprender
Marital State
NO
Married
Single, Divorced
TaxInc
NO
< 80K
> 80K
YES
NO
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
7. NO
Figura extrada dos acetatos deIntroduction to Data Mining P. Tan, M.Steinbach, V.Kumar
rvore de Deciso Exemplo 2: Atribuio de Crdito Bancrio
Conjunto de Treino
Outra rvore para representar o mesmo problema
MarSt
Single, Divorced
Married
Refund
NO
No
Yes
TaxInc
> 80K
< 80K
YES
NO
Usando diferentes algoritmos podemos obter diferentes rvores para ajustar (representar) os mesmos dados
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
8. Refund
No
Yes
No
MarSt
NO
Married
Single Divorced
TaxInc
NO
Married
< 80K
> 80K
YES
NO
Figura extrada dos acetatos deIntroduction to Data Mining P. Tan, M.Steinbach, V.Kumar
rvores de DecisoClassificao de um novo exemplo
Novo exemplo
Comear pela raiz da rvore
Atribuir Cheat = No(engano, fraude)
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
9. Esta rvore de deciso foi obtida com a implementao do algoritmo C4.5 no software RapidMiner
rvores de Deciso & Lgica
Cada classe = disjuno de conjunes das condies aplicadas aos valores dos diversos atributos
Os ramos na rvore so disjuntos
Cada ramo na rvore = conjuno de condies
Will I play golf today? = Yes
(Outlook=overcast) (Outlook=rainWind = false) (Outlook = sunnyHumidity = 80K
Cheat
Dont
Cheat
dividir
Refund =NO MaritalStat.= Single/Divorced
Income< 80K
dividir
Income> 80K
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
17. Algoritmos da famlia TDIDTPseudocdigo
Entrada: conjunto de exemplos Exs,conjunto de Atributos Ats
Sada: rvore de deciso
funoGeraArvore(Exs, Ats) {
se (exemplos(Exs) so todos da mesma classe c C)
retornar folha com valor da classe c
se (Ats = )
retornar folha com o valor da classe maioritria em Exs
A selecciona em Ats o atributo que maximizacritrio_diviso(Exs)
para cada valorv no domnio do atributo AExs(v){Exs A = v }
se (Exs(v) = ) SA(v) folha com o valor da classe maioritria em Exscaso contrrio
SA(v) GeraArvore(Exs(v), AtsA}
}
retornar A como n de deciso eSA(v) como sub-rvores descendentes
}
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
18. Como especificar a condio de teste do atributo?
Depende do tipo de atributo
Nominal
Ordinal
Contnuo
Depende de como dividir
em dois (2-way split)
em vrios (multi-way split)
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
19. CarType
Family
Luxury
Sports
CarType
CarType
{Family, Luxury}
{Sports, Luxury}
{Sports}
{Family}
Partio de Atributos Nominais
Multi-way split:Usar tantas parties quantos valores
Binary split:Dividir os valores em dois subconjuntos. Precisa-se encontrar o particionamento ptimo
OR
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
20. Partio de Atributos Ordinais
Size
Small
Large
Medium
Size
Size
Size
{Medium, Large}
{Small, Medium}
{Small, Large}
{Small}
{Large}
{Medium}
Multi-way split:Usar tantas parties quantos valores
Binary split:Dividir os valores em dois subconjuntos. Precisa-se encontrar o particionamento ptimo
OR
OR
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
21. Partio de Atributos Contnuos
Multi-way split:
os intervalos podem ser determinados usando um mtodo de discretizao (iguais intervalos, iguais frequncias, etc.)
Binary split:(A < v) or (A v)
considerar todas as possveis parties e seleccionar a melhor
pode resultar computacionalmente custoso
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
22. Qual atributo seleccionar?

  • Greedy TDIDT:(estratgia gulosa ou mope)

23. guia a procura sobre o espao de possveis rvores 24. particiona os exemplos segundo um teste do atributo que optimiza um critrio de diviso 25. constri a rvore de uma forma recursiva e descendenteBefore Splitting: 10 records of class 0, 10 records of class 1
Qual atributo escolher para testar num dado n? Qual a melhor condio de teste?
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
26. Qual a melhor diviso?
Uma diviso que mantm as propores de classes em todas as parties intil
Uma diviso onde em cada partio todos os exemplos so da mesma classe tem utilidade mxima
Ns com distribuio de classe homognea so preferidos
Valorizar a impureza das parties medir impureza de um n
N no-homogneo
Alto grau de impureza
N homogneo
Semimpureza
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
27. Medidas de Impureza de um N
Para um problema com duas classes
Gini Index
Entropy
Misclassification error
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
28. Entropia Medida de Impureza
A entropia mede o grau de impureza de um conjunto de exemplos
Dado um conjunto S com exemplos pertencentes a m classes, c1, c2, , cm,a entropia definida pela seguinte expresso
onde pj proporo de exemplos da classe cj
Para uma varivel aleatria discretaX que toma valores x1, x2, . xn com pi = P(X=xi)

  • A entropia tem mximo (log2pi) se pi= pj para qualquer i j (distribuio uniforme), max=1 se 2 classes

29. Entropia(X) = 0 se existe um i tal que pi= 1(assumindo que 0 * log2 0 = 0) 30. Entropia uma medida muito usada em Teoria da Informao (TI): 31. mede a quantidade de informao que existe numa v.a. X definida em bits 32. interpretada como o nmero esperado de bits que so necessrios para codificar a v.a. X 33. - log2 p(x) representa o nmero de bits necessrio para codificar um smbolo x com probabilidade de ocorrncia p(x) segundo a codificao de ShannonAprendizagemComputacional Gladys Castillo,Universidade de Aveiro
34. Entropia Exemplos
Problema de classificao binrio
Distribuio dos exemplos por classes
P(C1) = 0/6 = 0 P(C2) = 6/6 = 1
Entropy = 0 log 0 1 log 1 = 0 0 = 0
P(C1) = 1/6P(C2) = 5/6
Entropy = (1/6) log2 (1/6) (5/6) log2 (1/6) = 0.65
maior impureza, maior entropia
P(C1) = 2/6P(C2) = 4/6
Entropy = (2/6) log2 (2/6) (4/6) log2 (4/6) = 0.92
P(C1) = 3/6P(C2) = 3/6
Entropy = (1/2) log2 (1/2) (1/2) log2 (1/2) = 1
AprendizagemComputacional Gladys Castillo,Universidade de Aveiro
35. M0
M2
M3
M4
M1
M12
M34
Qual a melhor diviso?
medida de impureza antes da partio
Antes da partio:
A?
B?
Yes
No
Yes
No
Node N1
Node N2
Node N3
Node N4
medida de impureza depois da partio
medida de impureza depois da partio
Ganho = M0 M12 vsM0 M34
AprendizagemComputacional Gladys Casti