Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
Classificação Supervisionada
Marcus Sampaio
DSC/UFCG
• Entrada
– Um BD de tuplas, cada uma com um valor (classe) de
um atributo de classificação
• Saída: um modelo / perfil para cada classe
– Classe ‘crédito bom’
– (25 <= idade <= 40 e renda > 10k) ou (casado = SIM)
• Aplicações
– Análise de crédito (bom para concessão, ruim para
concessão)
– Perfil de cliente usuário de crédito (adimplemte,
inadimplente)
Marcus Sampaio
DSC/UFCG
Classificação Supervisionada (2)
• Organização prévia de dados em classes –
supervisão
– Dados: conjunto de casos, ou instâncias
– Classe: valor de um atributo de classificação
• Divisão dos dados em conjunto de treinamento
(conjunto-treinamento) e conjunto de teste (conjuntoteste)
• Um algoritmo de classificação induz (infere, aprende)
padrões de classificação – modelo – do conjunto de
treinamento
• O modelo é testado com o conjunto de testes O
modelo aprovado é usado para classificar novos
casos  conjunto de execução.
Qualidade de um Modelo
Marcus Sampaio
DSC/UFCG
• Acurácia, desempenho e taxa de erro são sinônimos
• Um algoritmo de classificação classifica ou prediz a
classe de cada instância de teste, utilizando o modelo
inferido no treinamento
– Se a classificação for correta, então sucesso senão erro
– A taxa de erro é justamente a proporção de erros sobre o
conjunto total de instâncias testadas, ou simplesmente, taxa
de erro
– O complemento da taxa de erro é a taxa de acerto
– É mais comum referir-se a acurácia como sendo a taxa de
acerto
Qualidade de um Modelo (2)
Marcus Sampaio
DSC/UFCG
• É interessante também medir a taxa de erro
(acerto) da aplicação do modelo ao conjunto
de treinamento
– Baixas taxas de erro significam que o modelo é um
espelho do conjunto-treinamento
• Síntese do conjunto-treinamento (importante)
– 'Altas' taxas de erro não significam
necessariamente que o modelo é ruim
• O modelo não é uma síntese perfeita do conjuntotreinamento, mas possivelmente
• Baixas taxas de erro nos testes
Qualidade de um Modelo (3)
Marcus Sampaio
DSC/UFCG
• Em resumo
– Alta acurácia de treinamento
• Bom para conhecer os dados
– Alta acurácia de teste
• Importante para acertar como o conjunto de execução
– Numa análise comparativa, é comum situações
como
Marcus Sampaio
DSC/UFCG
ID3
acurácia
de treinamento
acurácia
de teste
acurácia
de execução
alta
média
J48
Análise
média
ID3 para
conhecer
os dados
alta
J48 é
melhor
para o conj.
de exec.
J48 é 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 alcançar um nível de acurácia
muito bom
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
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
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
Escolha a árvore 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 (3)
Marcus Sampaio
DSC/UFCG
• Interpretação da árvore
– Aparentemente, existe jogo quando o tempo está
nublado ou chuvoso (vocês estão percebendo que
isto é coisa de inglês ou da "commonwealth"!),
mas não quando está ensolarado
Marcus Sampaio
DSC/UFCG
Árvores de Decisão
Análise de Crédito
s a la ry
e d u c a t io n
la b e l
10000
h ig h s c h o o l
re je c t
40000
u n d e r g ra d u a t e
ac c ept
15000
u n d e r g ra d u a t e
re je c t
75000
g ra d u a t e
ac c ept
18000
g ra d u a t e
ac c ept
salário
< 20.000
≥ 20.000
educação
aceito
 graduado
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
• Como determinar cada atributo-raiz?
Marcus Sampaio
DSC/UFCG
Construção de Árvores (3)
Marcus Sampaio
DSC/UFCG
• O primeiro atributo-raiz a ser escolhido é
Estado
– Menor entropia (entropia: grau de desordem)
Marcus Sampaio
DSC/UFCG
Construção de Árvores (5)
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 nodo
• A aplicação recursiva da mesma idéia conduz
à árvore final para o problema do tempo
Marcus Sampaio
DSC/UFCG
Construção de Árvores (7)
Marcus Sampaio
DSC/UFCG
• Exercício
– Verifique se a árvore é perfeita, isto é, todos os
nós folhas são puros – uma única classe
Construção de Árvores (8)
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
– Algoritmos sofisticados, como o J48, preferem
errar no treinamento para acertar no teste!
III.3 Construção de Árvores
Marcus Sampaio
DSC/UFCG
• Um conjunto puro pode não ser significativo
– Pouco freqüente, ou estatisticamente inválido
(“overfitting”)
• Como conseqüência de “overfitting”, a árvore pode ser
larga e profunda
– Pouco legível
• “Overfitting” se dá geralmente em atributos
com muitos valores.
III.4 Algoritmos de Árvores
Marcus Sampaio
DSC/UFCG
• ID3
– Bom para conhecer o conjunto de treinamento
• C4.5
– Produz modelos mais confiáveis que o ID3
– Pode se afastar do conjunto de treinamento
• Mecanismo de poda (“pruning”)
• J.48
– Versão WEKA do C4.5
• C5.0 (See5)
– Versão comercial do C4.5
• Outros algoritmos
Poda ("Pruning")
Marcus Sampaio
DSC/UFCG
Poda ("Pruning") (2)
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
NaïveBayes
Marcus Sampaio
DSC/UFCG
• Na modelagem estatística, todos os atributos
são considerados igualmente importantes e
independentes um do outro, dada uma classe
• Apesar desta suposição irrealista, ela conduz
a um esquema bastante simples, com
resultados surpreendentemente bons
• A idéia é contar quantas vezes cada par
atributo-valor ocorre com cada valor do
atributo-classe
• Este método simples e intuitivo é baseado na
Regra de Bayes, de probabilidade condicional
Marcus Sampaio
DSC/UFCG
Es
ta
do
sim
não
ensolarado
2
3
nublado
4
chuvoso
/Tem
pera
tura
sim
não
quente
2
2
0
amena
4
2
3
2
fria
3
1
ensolarado
2/9
3/5
quente
2/9
2/5
nublado
4/9
0/5
amena
4/9
2/5
chuvoso
3/9
2/5
fria
3/9
1/5
Marcus Sampaio
DSC/UFCG
/Umi
da
de
sim
não
alta
3
4
normal
6
alta
normal
/Ven
ta
nia
Jo
go
sim
não
sim
não
falso
6
2
9
5
1
verdade
3
3
3/9
4/5
falso
6/9
2/5
6/9
1/5
verdade
3/9
3/5
9/14
5/14
Marcus Sampaio
DSC/UFCG
Estado
Temp.
Umidade
Ventania
Jogo
ensol.
fria
alta
verdade
?
NaïveBayes (5)
Marcus Sampaio
DSC/UFCG
• Probabilidade de ter jogo (tem_jogo = 'sim')
– 2/9 x 3/9 x 3/9 x 3/9 x 9/14 = 0.0053
• Probabilidade de não ter jogo (tem_jogo =
'não')
– 3/5 x 1/5 x 4/5 x 3/5 x 5/14 = 0.0206
• Conclusão: para o dia testado, ensolarado,
frio, ventoso e com umidade alta, é quatro
vezes mais provável que não haja jogo
NaïveBayes (6)
Marcus Sampaio
DSC/UFCG
• Probabilidades em percentagem
– sim = 0.0053 / (0.0053 + 0.0206) = 20.5%
– não = 0.0206 / (0.0053 + 0.0206) = 79.5%