Marcus Sampaio
DSC/UFCG
Os slides 3-15 foram copiados de Pang-Ning Tan
Classificação: Definição
Marcus Sampaio
DSC/UFCG
• Dada uma coleção de instâncias (conjunto
de treinamento)
– Cada instância contém um conjunto de atributos, um dos
atributos é a classe  classificação supervisionada
• A meta é induzir um modelo para o atributo
classe como uma função de valores de
outros atributos
• Objetivo: instâncias novas ou de previsão
devem ser classificadas tanto
acuradamente quanto possível
– Um conjunto de teste é usado para ajudar a estimar a
acurácia de previsão do modelo
Ilustração da Tarefa de
Classificação
Tid
Attrib1
Attrib2
Attrib3
Class
1
Yes
Large
125K
No
2
No
Medium
100K
No
3
No
Small
70K
No
4
Yes
Medium
120K
No
5
No
Large
95K
Yes
6
No
Medium
60K
No
7
Yes
Large
220K
No
8
No
Small
85K
Yes
9
No
Medium
75K
No
10
No
Small
90K
Yes
Marcus Sampaio
DSC/UFCG
Learning
algorithm
Induction
Learn
Model
Model
10
Training Set
Tid
Attrib1
Attrib2
11
No
Small
55K
?
12
Yes
Medium
80K
?
13
Yes
Large
110K
?
14
No
Small
95K
?
15
No
Large
67K
?
10
Test Set
Attrib3
Apply
Model
Class
Deduction
Exemplos de Tarefas de
Classificação
Marcus Sampaio
DSC/UFCG
• Predizer tumores em células: benigno, maligno
• Classificar transações de cartão de
crédito: legítimas, fraudulentas
• Classificar estruturas secundárias
de proteínas: “alpha-helix”, “beta-sheet”,
“random coil”
• Categorizar notícias como finanças,
tempo, esporte, etc
Modelos de Classificação
• Árvores de Decisão
• Regras de Classificação
• Modelos Estatísticos
– Naïve Bayes
– Bayesian Belief Network*
• Support Vector Machines*
• Redes Neurais*
*- Não serão vistos
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
Árvore de Decisão
Tid Refund Marital
Status
Taxable
Income Cheat
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced 95K
Yes
6
No
Married
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
60K
Splitting Attributes
Refund
Yes
No
NO
MarSt
Single, Divorced
TaxInc
< 80K
NO
NO
> 80K
YES
10
Training Data
Married
Model: Decision Tree
Outro Exemplo de
Árvore de Decisão
Marcus Sampaio
DSC/UFCG
MarSt
10
Tid Refund Marital
Status
Taxable
Income Cheat
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced 95K
Yes
6
No
Married
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
60K
Married
NO
Single,
Divorced
Refund
No
Yes
NO
TaxInc
< 80K
NO
> 80K
YES
There could be more than one tree that
fits the same data! The induced tree is
algorithm-dependent
Acurácia de Treinamento
Marcus Sampaio
DSC/UFCG
• Cada árvore induzida terá uma acurácia de
treinamento
– Acurácia 100%: cada regra (ramo da árvore) com
acurácia = 100%
– Acurácia de treinamento 100%   Alta acurácia
de teste
• Veremos as explicações, adiante
Marcus Sampaio
DSC/UFCG
Testando o Modelo
Test Data
Start from the root of tree.
Refund
Yes
10
No
NO
MarSt
Single, Divorced
TaxInc
< 80K
NO
Married
NO
> 80K
YES
Refund Marital
Status
Taxable
Income Cheat
No
80K
Married
?
Marcus Sampaio
DSC/UFCG
Testando o Modelo
Test Data
Refund
Yes
10
No
NO
MarSt
Single, Divorced
TaxInc
< 80K
NO
Married
NO
> 80K
YES
Refund Marital
Status
Taxable
Income Cheat
No
80K
Married
?
Marcus Sampaio
DSC/UFCG
Testando o Modelo
Test Data
Refund
Yes
10
No
NO
MarSt
Single, Divorced
TaxInc
< 80K
NO
Married
NO
> 80K
YES
Refund Marital
Status
Taxable
Income Cheat
No
80K
Married
?
Marcus Sampaio
DSC/UFCG
Testando o Modelo
Test Data
Refund
Yes
10
No
NO
MarSt
Single, Divorced
TaxInc
< 80K
NO
Married
NO
> 80K
YES
Refund Marital
Status
Taxable
Income Cheat
No
80K
Married
?
Marcus Sampaio
DSC/UFCG
Testando o Modelo
Test Data
Refund
Yes
10
No
NO
MarSt
Single, Divorced
TaxInc
< 80K
NO
Married
NO
> 80K
YES
Refund Marital
Status
Taxable
Income Cheat
No
80K
Married
?
Marcus Sampaio
DSC/UFCG
Testando o Modelo
Test Data
Refund
Yes
Refund Marital
Status
Taxable
Income Cheat
No
80K
Married
?
10
No
NO
MarSt
Single, Divorced
TaxInc
< 80K
NO
Married
NO
> 80K
YES
Assign Cheat to “No”
Test Accuracy?!
Qualidade de Modelos
Marcus Sampaio
DSC/UFCG
• Acurácias de treinamento e teste
– Alta acurácia significa que o modelo é um espelho
dos dados
• Síntese dos dados (importante)
– Alta acurácia de treinamento não significa
necessariamente que o modelo terá alta acurácia
de teste
• Pode haver regras cobrindo poucas instâncias
– Sem validade estatística, o que levaria a erro nos teste
– Overfitting
• Alta acurácia de treinamento  Baixa acurácia de teste
Marcus Sampaio
DSC/UFCG
• Em resumo
– Modelo-espelho
• Bom para conhecer os dados
– Alta acurácia de teste
• Importante para acertar com o o conjunto de previsão
– Estimativa da acurácia de previsão
– Numa análise comparativa, é comum situações
como
Complementaridade de Algoritmos
de Árvore de Decisão
Marcus Sampaio
DSC/UFCG
ID3
(WEKA)
Acurácia de
treinamento
Acurácia de
teste
Acurácia de
previsão
alta
média
média
J48
(WEKA)
Análise
média
ID3 é bom
para
síntese dos
dados
alta
J48 tende a
ser melhor
para testes
alta
J48 tende a
ser mais
confiável
que ID3
Árvores 1R
Marcus Sampaio
DSC/UFCG
• Árvores de decisão com um só nível (fora a
raiz)  árvores 1R
• O interessante e surpreendente é que árvores
1R podem ser confiáveis
– Alta acurácia de previsão
• Exemplo: Prever a realização de jogo, dadas
as condições meteorológicas
– Problema do tempo
Marcus Sampaio
DSC/UFCG
Estado
Temp
Umid
Vento
Jogo
ensol
quente
alta
falso
não
ensol
quente
alta
verdade
não
nublado
quente
alta
falso
sim
chuvoso
amena
alta
falso
sim
chuvoso
fria
normal
falso
sim
chuvoso
fria
normal
verdade
não
nublado
fria
normal
verdade
sim
ensol
amena
alta
falso
não
ensol
fria
normal
falso
sim
Marcus Sampaio
DSC/UFCG
chuvoso
amena
normal
falso
sim
ensol
amena
normal
verdade
sim
nublado
amena
alta
verdade
sim
nublado
quente
normal
falso
sim
chuvoso
amena
alta
verdade
não
Atenção: Não é o mesmo conjunto das provas  sim e não invertidos
Marcus Sampaio
DSC/UFCG
Estado
Ensolarado
Chuvoso
Nublado
Não
Sim
Sim
Algoritmo de Indução de
Árvores 1R
Marcus Sampaio
DSC/UFCG
Para cada atributo ( atributo de classificação)
Para cada valor do atributo, faça
Conte quantas vezes cada classe aparece
Encontre a classe mais freqüente
Forme um ramo da árvore
Calcule a taxa de erro da árvore candidata
Escolha uma das árvores candidatas com a menor taxa de
erro
Marcus Sampaio
DSC/UFCG
atributo
regras
erros
total de
erros
1
estado
ensolarado  não
nublado  sim
chuvoso  sim
2/5
0/4
2/5
4/14
2
temperatur
a
quente  não*
amena  sim
fria  sim
2/4
2/6
1/4
5/14
3
umidade
alta  não
normal  sim
3/7
1/7
4/14
4
ventania
falso  sim
verdade  não*
2/8
3/6
5/14
*- Escolha aleatória
Algoritmo
Marcus Sampaio
DSC/UFCG
• Interpretação da árvore
– Com possivelmente alta probabilidade, existirá
jogo (previsão) quando o tempo estiver nublado ou
chuvoso (vocês estão percebendo que isto é coisa
de inglês, ou da "commonwealth“, ou do livrotexto), mas não quando o tempo estiver
ensolarado
Árvores de Decisão
Stricto Sensu
Marcus Sampaio
DSC/UFCG
Análise de Crédito
Salário
1.000
4.000
1.500
7.500
1.800
Educação
secundária
graduado
graduado
pós-grad
pós-grad
Status
rejeitado
aceito
rejeitado
aceito
aceito
Salário
< 2.000
 2.000
Conj. de Treinamento
Educação
aceito
pós-grad
aceito
 graduado
rejeitado
Construção de Árvores
Marcus Sampaio
DSC/UFCG
• Problema recursivo
– Seleciona-se um atributo para ser o atributo-raiz
da árvore
– Cada valor do atributo é um ramo da árvore
• Decompõe o conjunto-treinamento em sub-conjuntos, um
para cada valor do atributo (intervalo, às vezes)
– Em princípio, quando todas as instâncias em um
ramo tiverem a mesma classificação, o processo
de decomposição pára
• Não esquecer que acurácia de treinamento de 100%
pode não ser o objetivo
• Como determinar cada atributo-raiz?
– A determinação é baseada no conceito de entropia
Marcus Sampaio
DSC/UFCG
• Entropia
– Conceito emprestado da Termodinâmica, que
significa grau de desordem das moléculas de um
gás  entropia do gás
• Exemplo: o problema do tempo
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• O primeiro atributo-raiz a ser escolhido é
Estado
– Menor entropia (entropia: grau de desordem)
• Ver, no livro-texto, como a entropia é calculada
– A ‘olho nu’, podia ser também Umidade
– Note que o algoritmo 1R, por outras vias  menor
taxa de erro  chega a conclusões similares
menor entropia, mas pára no primeiro nível da
árvore
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• Umidade é o segundo nodo do primeiro ramo
da árvore
– Note que não há necessidade de dividir os
conjuntos de instâncias deste modo
• Induzir uma árvore-espelho não necessariamente leva à
melhor acurácia de previsão
• A aplicação recursiva da mesma idéia conduz
à árvore final para o problema do tempo
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• Exercício
– Calcule a acurácia de treinamento da árvore do
slide anterior
Marcus Sampaio
DSC/UFCG
• Idealmente, o processo termina quando todos
os nós-folhas são puros, isto é, todos os
conjuntos de instâncias têm a mesma classe
• Entretanto, pode não ser possível alcançar
esta 'feliz' situação
– Podemos ter duas instâncias do conjuntotreinamento com os mesmos valores do conjunto
de atributos, porém com classes diferentes
• Um tipo de ‘sujeira’
• Uma ‘feliz’ situação pode não ser desejável:
algoritmos sofisticados, como o J48, preferem
errar no treinamento para acertar na previsão!
Algoritmos Que Induzem
Árvores
Marcus Sampaio
DSC/UFCG
• ID3
– Objetiva 100% de acurácia de treinamento
• Bom para conhecer os dados de mineração
• C4.5
– Produz modelos em geral mais confiáveis que o ID3
– Pode se afastar do conjunto de treinamento
• Mecanismo de poda (“pruning”), para a solução do problema de
“overfitting”
• J.48
– Versão WEKA do C4.5
• C5.0 (See5)
– Versão comercial do C4.5
• Outros algoritmos
– Ver a biblioteca WEKA
Poda ("Pruning")
Marcus Sampaio
DSC/UFCG
• Principal técnica para contornar “overfitting”
• Exemplo: os dados a minerar referem-se a
contratos de trabalho
Antes da Poda
Marcus Sampaio
DSC/UFCG
Acurácia de Treinamento = 100%
Depois da Poda
Marcus Sampaio
DSC/UFCG
Acurácia de Treinamento < 100%, mas o modelo se torna mais
confiável (acurácia de previsão)
Conclusões sobre
Árvores de Decisão
Marcus Sampaio
DSC/UFCG
• Os algoritmos de indução de árvores são muito
eficientes, em termos de tempo
• Algoritmos de navegação em árvores, para previsão,
são extremamente eficientes
• Árvores de decisão são fáceis de interpretar, se a sua
complexidade for simples ou mediana
– Muito frequentemente, não é assim
• Impossibilidade de gerar ‘galhos’ com negação ou disjunção
• Os algoritmos de árvores de decisão induzem
modelos tão eficientes, na média, quanto os
algoritmos que induzem outros tipos de modelo
• Um processo de MD deve decidir entre n modelos,
incluindo árvores e outros tipos de modelo
– Não existe o melhor modelo, mas
– Existe o melhor modelo para um dado problema!