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)  ‘crédito bom’
• casado  ‘crédito bom’
• 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
• Um algoritmo de classificação induz (infere, aprende)
padrões de classificação – modelo – dos dados
• Confiabilidade do modelo
– Divisão dos dados em conjunto de treinamento (conjuntotreinamento) e conjunto de teste (conjunto-teste)
– Um algoritmo de classificação induz (infere, aprende)
padrões de classificação – modelo – de conjuntos de
treinamento (depende da técnica utilizada)
– 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 aos dados
minerados
– Baixas taxas de erro significam que o modelo é um
espelho dos dados
• Síntese dos dados (importante)
– 'Altas' taxas de erro não significam
necessariamente que o modelo é ruim
• O modelo não é uma síntese perfeita dos dados, mas
possivelmente
• Baixas taxas de erro nos testes
Qualidade de um Modelo (3)
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 execução
– Estimativa da acurácia de execução
– Numa análise comparativa, é comum situações
como
Marcus Sampaio
DSC/UFCG
ID3
espelho
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)
• Ver, no livro-texto, como a entropia é calculada
– ‘A olho nu’, podia ser também Umidade
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
• Induzir uma árvore-espelho não necessariamente leva à
melhor acurácia de execução
• 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
• Um tipo de ‘sujeira’
– Algoritmos sofisticados, como o J48, preferem
errar no treinamento para acertar no teste!
Construção de Árvores (9)
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
– Atributos numéricos  ‘Discretização’
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