Marcus SampaioDSC/UFCG

Marcus SampaioDSC/UFCG

Classificação Supervisionada

• 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 SampaioDSC/UFCG

• 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 (conjunto-

treinamento) 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

Classificação Supervisionada (2)

Marcus SampaioDSC/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

Marcus SampaioDSC/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 (2)

Marcus SampaioDSC/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

Qualidade de um Modelo (3)

Marcus SampaioDSC/UFCG

ID3 J48 Análise

espelhoalta média

ID3 para conhecer os dados

acurácia de teste média alta

J48 é melhor

para o conj. de exec.

acurácia de execu-

ção

J48 é mais confiável que ID3

Marcus SampaioDSC/UFCGÁrvores 1R

• Á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 SampaioDSC/UFCG

Estado Temp Umid Vento Jogoensol 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 SampaioDSC/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 SampaioDSC/UFCG

Chuvoso

Estado

EnsolaradoNublado

SimNão Sim

Marcus SampaioDSC/UFCG

Algoritmo de Indução deÁrvores 1R

Para cada atributoPara cada valor do atributo, faça

Conte quantas vezes cada classe apareceEncontre a classe mais freqüente

Forme um ramo da árvoreCalcule a taxa de erro da árvore

Escolha a árvore com a menor taxa de erro

Marcus SampaioDSC/UFCG

  atributo regras erros total de erros

1 estado ensolarado nãonublado simchuvoso sim

2/50/42/5

4/14

2 temperatura

quente não*amena simfria sim

2/42/61/4

5/14

3 umidade alta nãonormal sim

3/71/7

4/14

4 ventania falso simverdade não*

2/83/6

5/14

*- Escolha aleatória

Marcus SampaioDSC/UFCGAlgoritmo (3)

• 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 SampaioDSC/UFCG

Árvores de Decisão

salary education label10000 high school reject40000 under graduate accept15000 under graduate reject75000 graduate accept18000 graduate accept

aceito rejeitado

salário

≥ 20.000< 20.000

graduado

aceitoeducação

Análise de Crédito

< graduado

Marcus SampaioDSC/UFCGConstrução de Árvores

• 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 SampaioDSC/UFCG

Marcus SampaioDSC/UFCGConstrução de Árvores (3)

• 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 SampaioDSC/UFCG

Marcus SampaioDSC/UFCGConstrução de Árvores (5)

• 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 SampaioDSC/UFCG

Marcus SampaioDSC/UFCGConstrução de Árvores (7)

• Exercício– Verifique se a árvore é perfeita, isto é, todos os

nós folhas são puros – uma única classe

Marcus SampaioDSC/UFCGConstrução de Árvores (8)

• 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 conjunto-

treinamento 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!

Marcus SampaioDSC/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’

Construção de Árvores (9)

Marcus SampaioDSC/UFCGAlgoritmos de Árvores

• 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

Marcus SampaioDSC/UFCGPoda ("Pruning")

Marcus SampaioDSC/UFCGPoda ("Pruning") (2)