Data Mining - Classificação 2014-2 (1)

Prévia do material em texto

Univ. Tecnológica Federal do Paraná
Campus Medianeira
Prof. M.Sc. Alan Gavioli
alan@utfpr.edu.br
DATA MINING
CLASSIFICAÇÃO
TAREFAS DE MINERAÇÃO:
CLASSIFICAÇÃO
O QUE É CLASSIFICAÇÃO?
 Definição:
 Consiste em determinar uma função que mapeia
(classifica) um registro de dados em uma dentre
diversas classes pré-definidas.
 Cada registro pertence a uma classe, indicada
pelo valor de um atributo-alvo. Cada registro
consiste de um atributo-alvo e de um conjunto
de atributos de predição.
O QUE É CLASSIFICAÇÃO?
 Definição (continuação):
 O objetivo é descobrir uma relação entre os
atributos de predição e o atributo-alvo,
utilizando registros cuja classificação já é
conhecida (conjunto de treinamento).
 O relacionamento descoberto é então usado
para predizer a classe (o valor do atributo-
alvo) de um novo registro ainda não
classificado.
EXEMPLO: CONJ. DE TREINAMENTO 
PARA O ATRIBUTO-ALVO JogarTênis
Atributos de predição Atributo-alvo 
EXEMPLO: CONJ. DE TREINAMENTO 
PARA O ATRIBUTO-ALVO JogarTênis
Alguns registros que permitem a mineração de regras de classificação:
EXEMPLO: CONJ. DE TREINAMENTO 
PARA O ATRIBUTO-ALVO JogarTênis
Regras de classificação correspondentes aos registros marcados:
- SE Céu = “Ensolarado” e Temperatura = “Quente” e 
Umidade = “Alta” ENTÃO JogarTênis = NÃO
- SE Céu = “Nublado” ENTÃO JogarTênis = SIM
- SE Céu = “Chuvoso” e Vento = “Fraco” ENTÃO 
JogarTênis = SIM
A ESCOLHA DOS
ATRIBUTOS DE PREDIÇÃO
 Não há uma regra geral quanto à quantidade de
atributos de uma tabela/fonte de dados que devem
ser usados como de predição.
 Também não há uma regra geral quanto à
quantidade de atributos de predição que devem
aparecer no lado esquerdo das regras (isto fica
claro no slide anterior).
 Resumindo: cada caso é um caso...
OS 2 PASSOS DA TAREFA
DE CLASSIFICAÇÃO
 Passo 1 – Construção do Modelo de
Classificação:
 Descrição de um conjunto de classes pré-
determinadas:
• Cada tupla/registro conhecida é considerada como
pertencente a uma classe pré-definida, determinada
pelo valor de seu atributo-alvo;
• O conjunto de tuplas usado na construção do modelo é
denominado conjunto de treinamento;
• O modelo pode ser representado por regras de
classificação, árvores de decisão ou fórmulas
matemáticas.
OS 2 PASSOS DA TAREFA
DE CLASSIFICAÇÃO
 Passo 2 – Utilização do Modelo de
Classificação:
 Usado para a classificação futura ou de registros
com valores desconhecidos;
 Correção estimada do modelo:
• Uso de conjunto de teste: rótulo conhecido é
comparado ao rótulo fornecido automaticamente pelo
modelo;
• Conjunto de teste deve ser diferente do conjunto
de treinamento.
CLASSIFICAÇÃO: 1º PASSO
Conjunto de 
Treinamento
Algoritmos de
Classificação
SE Céu = “Nublado”
ENTÃO
JogarTênis = SIM
Classificador
(Modelo)
CLASSIFICAÇÃO: 2º PASSO
ClassificadorConjunto
de Teste
Dados
Desconhecidos
(X23, Nublado, Boa, Alta, Fraco)
Joga Tênis?
SIM
APLICAÇÕES PRÁTICAS
 Algumas aplicações típicas:
 Aprovação de crédito em bancos;
 Marketing dirigido;
 Diagnóstico médico;
 Definição de perfil de clientes em seguradoras,
operadoras de telefonia e de cartões de crédito;
 Piloto automático de um Cessna:
• Treinado por três pilotos;
• Obteve um desempenho melhor que os três.
 Classificação de imagens.
MOMENTO DE PRATICAR!
ÁRVORES DE DECISÃO
 Estrutura amplamente aplicada para representar o
aprendizado de regras de classificação.
 Tem estrutura de árvore e inclui características de um
fluxograma.
 Os nós internos denotam testes em atributos e os ramos
representam saídas dos testes.
 Nós-folha representam rótulos de classe (valores do atributo-
alvo).
 Função aprendida: representada por uma árvore de decisão
(ou conjunto de regras IF-THEN).
ÁRVORE DE DECISÃO:
EXEMPLO
 Conceito a aprender: devo jogar tênis?
ÁRVORE DE DECISÃO:
DISJUNÇÃO DE CONJUNÇÕES
 Representação por meio de regras:
IF (céu = ensolarado AND umidade = normal) OR
(céu = nublado) OR
(céu = chuvoso AND vento = fraco)
THEN JogarTênis = SIM
ÁRVORES DE DECISÃO
 Cada nível da árvore corresponde a um dos
atributos de predição.
 Para decidir qual atributo deve ser inserido em
cada nível da árvore, encontre aquele com o maior
ganho de informação.
 Execute novamente o passo anterior, agora para
selecionar o segundo atributo, e assim
sucessivamente para todos.
ESCOLHA DO MELHOR ATRIBUTO 
PARA UM NÍVEL DA ÁRVORE
 Medida baseada em ganho de informação,
calculado pela entropia.
 Entropia: medida de “impureza” numa coleção de
exemplos de treinamento S.
 Entropia = 0: todos membros da mesma classe
 Entropia = 1: coleção com mesmo número de positivos
(+) e negativos (–).
 Entropia(S) = – (p+) log2 (p+) – (p–) log2 (p–)
p+ : proporção de exs. positivos em S
p- : proporção de exs. negativos em S
ENTROPIA
 Entropia(S) = – (p+) log2 (p+) – (p–) log2 (p–)
 Ex: se S tem 14 exemplos, sendo 9 positivos e 5
negativos, tem-se:
Entropia(S) = – (9/14) log2 (9/14) – (5/14) log2 (5/14)
= 0.940
 OBS: 0 log2 0 = 0
GANHO DE INFORMAÇÃO
 Mede a redução esperada na entropia, causada
pela partição nos exemplos segundo um atributo.
 Ganho(S,A): ganho de informação de um atributo
A, relativo à coleção de exemplos S.
EXEMPLO: CONJ. DE TREINAMENTO 
PARA O ATRIBUTO-ALVO JogarTênis
EXEMPLO: QUAL É O MELHOR ATRIBUTO 
DE CLASSIFICAÇÃO PARA O 1º NÍVEL?
Algoritmo ID3, de J. Ross Quinlan: analisa todos os exemplos 
para decidir o atributo classificador.
CONSTRUÇÃO DA ÁRVORE DE 
DECISÃO COM ID3
Ganho(S, céu) = 0.246; Ganho(S, umidade) = 0.151
Ganho(S, vento) = 0.048; Ganho(S, temperatura) = 0.029
CONSTRUÇÃO DA ÁRVORE DE 
DECISÃO COM ID3
Ganho(Sensolarado, umidade) = 0.970 – (3/5)0.0 – (2/5)0.0 = 0.970 
Ganho(Sensolarado, tempe) = 0.970 – (2/5)0.0 – (2/5)1.0 – (1/5)0.0 = 0.570;
Ganho(Sensolarado, vento) = 0.970 – (2/5)1.0 – (3/5).918 = 0.019
Que atributo deve 
ser testado aqui?
CARACTERÍSTICAS DO
ALGORITMO ID3
 Preferência por árvores pequenas:
 Sua busca no espaço de hipóteses aumenta a árvore
somente até o tamanho necessário para classificar o
conjunto de exemplos de treinamento disponível.
 Coloca mais perto da raiz aqueles atributos
que oferecem o maior ganho de informação.
 Outros algoritmos para árvores de decisão:
 CART (Breiman, Friedman, et. al.);
 C4.5 e C5.0 (Quinlan);
 J48.
ÁRVORES DE DECISÃO
EXEMPLO PARA CLASSIFICAÇÃO
 Suponha que um pequeno conjunto de dados, com 40 registros, foi
escolhido como de treinamento (adaptado do UCI Repository, por Ross
Quinlan).
ÁRVORES DE DECISÃO
EXEMPLO PARA CLASSIFICAÇÃO
 O objetivo é predizer o valor de um atributo mpg (milhas por
galão, que no caso brasileiro seria algo similar a “km/l”) como
sendo “bom” ou “ruim”, que indicará se um carro é
econômico ou não em relação ao consumo de combustível.
 Tendo o conjunto de treinamento, o primeiro passo é
determinar qual deve ser o primeiro atributo de predição a
ser testado na árvore de decisão, com base no cálculo do
ganho de informação associado a cada atributo. Em seguida,
repete-se esse passo de seleção do atributo de predição
recursivamente, para os demais níveis da árvore.
ÁRVORES DE DECISÃO
EXEMPLO PARA CLASSIFICAÇÃO
 Atributo-alvo: classificação de milhas por galão
(mpg).
 Para este exemplo, a análise do ganho de
informação estabeleceu a seguinte ordem para
utilização dos atributos de predição na árvore:
 Quantidade de cilindros (cylinders).
 Fabricante (maker).
 Potência em cv (horsepower).
 Aceleração (acceleration).
 Anos do modelo (modelyear).
ÁRVORES DE DECISÃO
EXEMPLO PARACLASSIFICAÇÃO
 Primeiro nível da árvore:
 Note 2 coisas: definiu-se que quando houver empate (p. ex.: no caso
de 3 cilindros), a previsão para mpg será considerada como “ruim”;
além disso, quando houver a concentração total dos registros em
uma das possibilidades de classificação (p. ex.: no caso de 5 e 6
cilindros), a predição será concluída e não haverá subárvores.
ÁRVORES DE DECISÃO
EXEMPLO PARA CLASSIFICAÇÃO
 Passo de recursão:
ÁRVORES DE DECISÃO
EXEMPLO PARA CLASSIFICAÇÃO
 Passo de recursão (continuação):
EXEMPLO PARA CLASSIFICAÇÃO:
Segundo Nível da Árvore de Decisão
ÁRVORES DE DECISÃO
CASOS-BASE
 Há 2 casos-base que devem ser observados
durante a construção da árvore:
 Caso-base 1: se todos os registros no
subconjunto de dados corrente têm a mesma
saída, então não execute recursão.
 Caso-base 2: se todos os registros têm
exatamente o mesmo valor para um novo
atributo de entrada, então ignore esse atributo e
considere o próximo.
ÁRVORES DE DECISÃO
CASOS-BASE
ÁRVORES DE DECISÃO
ERRO DO CONJUNTO DE TREINAMENTO
 Para cada registro completo, siga a árvore de
decisão para ver o que ela iria prever.
 Para quantos registros a previsão da árvore de
decisão não é igual ao valor real no banco de
dados?
 Essa quantidade é chamada de Erro do Conjunto
de Treinamento. Quanto menor, melhor!
 Onde está o erro neste conjunto de treinamento?
 Apenas um dos 40 registros do conjunto de treinamento não
corresponde à previsão da árvore. Assim: 1/40 = 2,5% de erro.
USO EFETIVO DE
ÁRVORES DE DECISÃO
 Árvores de decisão não costumam ser usadas para
prever valores de atributo-alvo de conjuntos de
treinamento, que já são dados conhecidos.
 É mais comum vê-las sendo utilizadas para prever
valores de atributo-alvo para dados futuros, que
ainda sejam desconhecidos.
MOMENTO DE PRATICAR!
PROBLEMAS GERAIS
 Estratégia de aumentar a árvore o mínimo
necessário pode trazer problemas quando:
 Há ruído nos dados;
 Número de exemplos de treinamento é pequeno (não
representativo da função buscada).
 Problema: ruído nos dados:
 Ex: Dois ou mais exemplos com mesma descrição (em
termos dos atributos de predição), mas classificação
diferente.
 Soluções possíveis: 1) cada folha é rotulada com a
classificação majoritária; ou 2) folhas indicam
probabilidade de ocorrência de cada classificação (relativa
à frequência da classificação).
ERRO DO CONJUNTO DE TESTE
 Suponha que sejam deixados de fora alguns dados
conhecidos quando é feito o aprendizado da árvore
de decisão.
 Mas, uma vez construída a árvore, deseja-se ver o
quão bem a árvore prevê esses dados.
 Esta é uma boa simulação do que acontece quando
tenta-se prever dados futuros e é chamada de
Erro do Conjunto de Teste.
ERRO DO CONJUNTO DE TESTE
 Suponha, por exemplo, que tem-se um conjunto de teste com
352 registros para o caso da mineração de regras de
associação que visa prever a classificação de consumo de
automóveis. Logo:
 O Erro do Conjunto de Teste é pior do que o Erro do Conjunto
de Treinamento.
Qtde de 
erros
Tam. do 
conjunto
Porcentagem 
errada
Conjunto de 
treinamento
1 40 2,50
Conjunto de teste 74 352 21,02
OVERFITTING
 Essa possível grande diferença entre os valores dos erros
associados ao conjunto de treinamento e ao conjunto de teste
se deve ao overfitting.
 Definição: se o algoritmo de aprendizado de máquina insere
“ruído” (isto é, dá atenção e considera partes dos dados que
são irrelevantes), isto é overfitting.
 Fato (teórico e empírico): se o algoritmo de aprendizado de
máquina comete overfitting, então ele pode ter um
desempenho não tão bom com o conjunto de teste.
 É um problema que pode ocorrer com qualquer algoritmo de
aprendizado.
EVITANDO OVERFITTING
 Geralmente não sabemos antecipadamente quais
são as variáveis irrelevantes para a construção de
uma árvore de decisão.
 Além disso, essa irrelevância pode depender do
contexto.
 P. ex., se x é o atributo-alvo e é determinado por
x = a AND b, então b é uma variável irrelevante apenas na
porção da árvore em que a é falso.
 Porém, pode-se usar Estatística para se obter um
alerta sobre a ocorrência de overfitting, e então
“podar” a árvore para eliminar regras que geram
erros.
EVITANDO OVERFITTING
 O teste Qui-Quadrado (chi-squared), proposto por
Karl Pearson (1900), geralmente é utilizado em
situações em que há muitos testes a serem feitos e
pelo menos dois resultados categóricos possíveis,
com o objetivo de se averiguar quais variáveis de
entrada são realmente importantes para dividir a
população em sub-populações.
 Há uma grande quantidade de bibliografias que
tratam da aplicação do teste Qui-Quadrado para
determinar a relevância de variáveis na construção
de árvores de decisão.
ENTRADAS COM VALORES 
DETALHADOS
 O que se deve fazer se algumas variáveis de entrada tiverem
diversos valores detalhados?
 Ideia 1: ramificar a árvore para cada valor possível.
ENTRADAS COM VALORES 
DETALHADOS
 Ideia 1: ramificar a árvore para cada valor possível.
 Note a complexidade da análise.
ENTRADAS COM VALORES 
DETALHADOS
 Ideia 2: divisões por
limiares (é a melhor
opção).
RESUMO SOBRE CLASSIFICAÇÃO
 Árvores de decisão são praticamente um padrão
para especificar regras de classificação, pois:
 São fáceis de entender;
 São fáceis de implementar;
 São fáceis de usar;
 Possuem baixo custo computacional.
REFERÊNCIAS BIBLIOGRÁFICAS
 ELMASRI, R.; NAVATHE, S. Fundamentals of Database Systems. 4
ed. New York: Addison-Wesley, 2003.
 HAN, J.; KAMBER, M. Data Mining: Concepts and Techniques. 2 ed.
San Francisco: Morgan Kaufmann, 2006.
 VERCELLIS, C. Business Intelligence: Data Mining and
Optimization for Decision Making. New York: Wiley, 2009.
 WILLIAMS, G.; HEGLAND, M.; ROBERTS, S. A Data Mining Tutorial.
In: 2nd IASTED International Conference on Parallel and Distributed
Computing and Networks (PDCN’98). 1998.
 http://dms.irb.hr/tutorial/tut_main.php
 http://www.information-management.com
 http://archive.ics.uci.edu/ml/
 http://www.worldscibooks.com/compsci/6604.html
 http://www.aaai.org/AITopics/pmwiki/pmwiki.php/AITopics/DecisionTr
ees#web
 http://webdocs.cs.ualberta.ca/~aixplore/learning/DecisionTrees/index.html