Embed Size (px)
Citation preview
CEA462 – Sistemas de Apoio à Decisão – Slide 1
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
Mineração de DadosMineração de Dados(Data Mining)(Data Mining)
CEA462 – Sistemas de Apoio à Decisão – Slide 2
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
Como Construir uma Árvore de Decisão
Encontrar a árvore ótima é computacionalmente inviável
Algoritmo de Hunt:
ID3
C4.5
CART
CEA462 – Sistemas de Apoio à Decisão – Slide 3
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 – Iterative Dichotomizer 3
Cada vértice é associado ao atributo mais informativo que ainda não tenha sido considerado.
Para medir o nível de informação de um atributo se utiliza o conceito de entropia.
Menor o valor da entropia, menor a incerteza e mais utilidade tem o atributo para a classificação.
CEA462 – Sistemas de Apoio à Decisão – Slide 4
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
O número de combinações possíveis são:
Aspecto: sol, nublado, chuvaTemperatura: quente, agradável, frioUmidade: alta, normalVento: fraco, forte (3 x 3 x 2 x 2 = 36)
CEA462 – Sistemas de Apoio à Decisão – Slide 5
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
• Qual é o atributo mais relevante para prever a classe a qual pertencem os dados ?
– Ganho da Informação: o ganho de informação do atributo X, é a diferença entre a informação necessária para identificar um elemento de T e a informação necessária para identificar um elemento de T depois que o valor de atributo X tenha sido considerado:
Ganho ( X,T) = Info (T) – Σ TX / T * Info (X, T )
O algoritmo ID3
CEA462 – Sistemas de Apoio à Decisão – Slide 6
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Conjunto de registros T com 14 registros. Duas partições Sim e Não, com probabilidade 9/14 e 5/14.
Info(T) = I( 9/14, 5/14 ) = -(9/14 . Log2 (9/14) + 5/14 . Log2 (5/14)) = 0.94
CEA462 – Sistemas de Apoio à Decisão – Slide 7
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Info ( Aspecto, T ) = sol/T * I (sol) + nublado/T * I (nublado) + chuva/T * I (chuva)
Info ( Aspecto, T ) = 5/14 * I (2/5, 3/5) + 4/14 * I (4/4 , 0) + 5/14 * I (3/5,2/5) = 0.693Info ( Aspecto, T ) = 5/14 * I (2/5, 3/5) + 4/14 * I (4/4 , 0) + 5/14 * I (3/5,2/5) = 0.693
CEA462 – Sistemas de Apoio à Decisão – Slide 8
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Info(T) = 0.94Info(Aspecto, T) = 0.693Ganho ( Aspecto, T ) = 0.94 - 0.693 = 0.247
CEA462 – Sistemas de Apoio à Decisão – Slide 9
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto • Com o objetivo de criar árvores de decisão
pequenos, para identificar poucas regras, o atributo escolhido para nó da árvore é o atributo de maior ganho.
O algoritmo ID3
CEA462 – Sistemas de Apoio à Decisão – Slide 10
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto • Passo 1:
Se todos os dados estão classificados em alguma das classes então parar ;senãoselecionar ( utilizando alguma heurística)algum atributo A com valores v1, v2, . . .,vn e criar um nó de decisão.
O algoritmo ID3
CEA462 – Sistemas de Apoio à Decisão – Slide 11
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto • Passo 2 : particionar o conjunto de dados
de treino T, em subconjuntos t1, t2, . . . , tn de acordo com os valores do atributo A
• Passo 3 : aplicar o algoritmo recursivamente para cada conjunto de dados ti
O algoritmo ID3
CEA462 – Sistemas de Apoio à Decisão – Slide 12
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
CEA462 – Sistemas de Apoio à Decisão – Slide 13
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Info ( Sol ) = 0.971Info ( Nublado ) = 0.0Info ( Chuva ) = 0.971
Info ( Aspecto ) = 0.693( 5/14 * 0.971 + 4/14 * 0.0 + 5/14 * 0.971 )Ganho ( Aspecto ) = 0.94 - 0.693 = 0.247
CEA462 – Sistemas de Apoio à Decisão – Slide 14
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Info ( Quente ) = 1.0Info ( Agradável ) = 0.919Info ( Fria ) = 0.811
Info (Temperatura ) = 0.912( 4/14 * 1.0 + 6/14 * 0.919 + 4/14 * 0.811 )Ganho ( Temperatura ) = 0.94 - 0.912 = 0.028
CEA462 – Sistemas de Apoio à Decisão – Slide 15
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Info ( Alta ) = 0.984Info ( Normal ) = 0.592
Info (Umidade ) = 0.636( 7/14 * 0.984 + 7/14 * 0.592 )Ganho (Umidade ) = 0.94 - 0.788 = 0.152
CEA462 – Sistemas de Apoio à Decisão – Slide 16
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Info ( Forte ) = 1.0Info ( Fraco ) = 0.811
Info ( Vento ) = 0.892( 6/14 * 1.0 + 8/14 * 0.541 )Ganho ( Vento ) = 0.94 - 0.738 = 0.048
CEA462 – Sistemas de Apoio à Decisão – Slide 17
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Ganho ( Aspecto ) = 0.247Ganho ( Temperatura ) = 0.028Ganho ( Umidade ) = 0.152Ganho ( Vento ) = 0.048
Aspecto
SolChuva
Nublado
Decisão = Sim
Info ( Sol ) = 0.971Info ( Nublado ) = 0.0Info ( Chuva ) = 0.971
CEA462 – Sistemas de Apoio à Decisão – Slide 18
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
CEA462 – Sistemas de Apoio à Decisão – Slide 19
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
O algoritmo ID3 - Exemplo
Aspecto
SolChuva
Nublado
Decisão = SimUmidade
AltaNormal
Decisão = Sim
Decisão = Não
Vento
Forte
Fraco Decisão = Não
Decisão = Sim
CEA462 – Sistemas de Apoio à Decisão – Slide 20
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
• É uma extensão do ID3:• Construí árvores de decisão, com valores
desconhecidos para alguns atributos.
• Trabalha com atributos que apresentam valores contínuos.
• Utiliza o conceito de poda (pruning) de árvores.
Algoritmo C4.5
CEA462 – Sistemas de Apoio à Decisão – Slide 21
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
• Quando existem atributos desconhecidos para alguma variável, os mesmos são considerado como uma nova categoria.
• Quando existem variáveis com atributos contínuos , o algoritmo cria intervalos segundo as alterações na variável de decisão.
Algoritmo C4.5
CEA462 – Sistemas de Apoio à Decisão – Slide 22
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
Poda de árvores de decisão
• Poda da árvore, significa substituir uma parte da árvore (sub-árvore) por uma folha, com o objetivo de simplificar as regras de decisão.
• A poda tem lugar quando o valor esperado do erro da sub-árvore é maior que o erro da folha que o fico em seu lugar.
CEA462 – Sistemas de Apoio à Decisão – Slide 23
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
Poda de árvores de decisão
• O processo de poda pode ser feito da seguinte maneira:
1. Percorre a árvore em profundidade.2. Para cada nó de decisão calcula:
erro no nósoma dos erros nos nós
descendentes3. Se o erro do nó é menor à soma dos
erros dos nós descendentes então o nó é transformado em folha
CEA462 – Sistemas de Apoio à Decisão – Slide 24
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
Poda de árvores de decisão
Erro de classificação de um nodoErro de classificação de um nodo
N - n + k - 1N - n + k - 1EEst(Nodo) = EEst(Nodo) =
N + kN + k
N - Número de exemplos classificados no N - Número de exemplos classificados no nodonodo
n - Número de exemplos pertencentes à classe n - Número de exemplos pertencentes à classe maioritária (com mais exemplos)maioritária (com mais exemplos)
k - Número de classes total do problemak - Número de classes total do problema
CEA462 – Sistemas de Apoio à Decisão – Slide 25
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
Poda de árvores de decisão
Erro Estático = 0.429Erro Estático = 0.429 Erro Estático = 0.333Erro Estático = 0.333(5-3+2-1)/(5+2)...(5-3+2-1)/(5+2)...
n,mn,m significa n exemplos da classe C1 e m exemplos da classe C2 significa n exemplos da classe C1 e m exemplos da classe C2
Erro Estático = 0.375Erro Estático = 0.375
CEA462 – Sistemas de Apoio à Decisão – Slide 26
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
Poda de árvores de decisão
• .
CEA462 – Sistemas de Apoio à Decisão – Slide 27
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
• CART: Classification And Regression Trees
• Uma árvore de classificação utilizando a Metodologia CART traduz o resultado de uma partição binária recursiva dos dados base da modelagem
• Estabelece uma relação entre as varáveis independentes (X), com uma única variável dependente, ou resposta.
• O modelo é ajustado mediante sucessivas divisões binárias no conjunto de dados , para tornar os sub-conjuntos cada vez mais homogêneos.
• Para selecionar a melhor partição, procura-se minimizar a impureza dos nós utilizando o índice GINI.
O algoritmo CART
CEA462 – Sistemas de Apoio à Decisão – Slide 28
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
• As árvores obtidas através desse algoritmo possui muitos níveis, o que a torna pouco eficiente
• É flexível, entretanto , é complexo tornando o calculo dos resultados muito demorado para grandes conjuntos de dados
• Pode utilizar diferentes tipos de atributos: contínuas, ordinais e nominais.
O algoritmo CART
CEA462 – Sistemas de Apoio à Decisão – Slide 29
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
• Os procedimentos do CART são:
• Definir o conjunto de regras para realizar a divisão de um nó em dois nós filhos. As perguntas do algoritmo têm como resposta apenas “sim” ou “não”.
• Encontrar a melhor divisão através do critério Gini.• Repetir o processo de divisão até que esta seja
impossível ou interrompida.• Aplicar o processo de pós-podagem para encontrar a
árvore com o menor custo, ou seja, aquela que possui menor taxa de erro e menor complexidade.
O algoritmo CART
CEA462 – Sistemas de Apoio à Decisão – Slide 30
Uni
vers
idad
e Fe
dera
l de
Our
o Pr
eto
Exercícios – 1 ponto – Entrega: 17/111- Dada a árvore de decisão, verifique se é necessário a realização da poda, de acordo com o algoritmo C4.5. Justifique sua resposta.
A
[ 3 1 ]B[ 7 2 ]
D = S
D = N
C
D = N
D = S[ 7 1 ]
[ 9 4 ]
[ 0 1 ]
[ 2 0 ]
[ 0 1 ]
