Classificação
Arvores de Decisão
AULAS 8 e 9
Data Mining
Classificação
Nome
Idade
Renda
Profissão
Classe
Daniel
≤ 30
Média
Estudante
Sim
João
31..50
Média-Alta
Professor
Sim
Carlos
31..50
Média-Alta Engenheiro
Maria
31..50
Baixa
Vendedora
Não
Paulo
≤ 30
Baixa
Porteiro
Não
Otavio
> 60
Média-Alta Aposentado
Sim
Não
SE Idade ≤ 30 E Renda é Média ENTÃO Compra-Produto-Eletrônico = SIM.
.
Mestrado em Ciencia da Computacao
2
Etapas do Processo
Amostras
Classificadas
REGRAS
Banco de
Testes
Classificador
REGRAS CONFIÁVEIS
Mestrado em Ciencia da Computacao
3
Métodos de Classificação

Classificadores eager (espertos)
A partir da amostragem, constroem um modelo de classificação capaz de classificar novas tuplas.
Uma vez pronto o modelo, as amostras não são mais utilizadas na classificação de novos
objetos (tuplas)





Arvores de Decisão
Redes Neuronais
Redes Bayseanas
Máquinas de Suporte Vetorial
Classificadores lazy (preguiçosos)
Cada nova tupla é comparada com todas as amostras e é classificada segundo a classe
da amostra à qual é mais similar.

Método kNN (k-nearest-neighbor)

Case-Based Reasoning (CBR)

Outros Métodos


Algoritmos Genéticos
Conjuntos Difusos
Mestrado em Ciencia da Computacao
4
Critérios de Comparação dos Métodos





Acurácia – capacidade de classificar corretamente
novas tuplas
Rapidez – tempo gasto na classificacao
Robustez – habilidade de classificar corretamente em
presenca de ruidos e valores desconhecidos
Escalabilidade – eficiencia do classificador em
grandes volumes de dados
Interpretabilidade – facilidade de um usuario
entender as regras produzidas pelo classificador
Mestrado em Ciencia da Computacao
5
Acurácia – Taxa de erros



Acc(M) = porcentagem das tuplas dos dados de
teste que sao corretamente classificadas.
Err(M) = 1 – Acc(M)
Matriz de Confusão
Classes Preditas
C1
Classes Reais
C2
C1
Positivos
Falsos
verdadeiros Negativos
C2
Falsos
Positivos
Negativos
verdadeiros
Mestrado em Ciencia da Computacao
6
Outras medidas mais precisas

Exemplo : acc(M) = 90%
C1 = tem-câncer (4 pacientes)
C2 = não-tem-câncer (500 pacientes)
Classificou corretamente 454 pacientes que não tem câncer
Não acertou nenhum dos que tem câncer
Pode ser classificado como “bom classificador”
mesmo com acurácia alta ?
% pacientes classificados corretamente

Sensitividade = true-pos
com câncer dentre todos os que
pos
realmente tem câncer

Especificidade = true-neg
neg
% pacientes classificados corretamente

Precisão
=
true-pos
true-pos + falso-pos
com câncer dentre todos os que foram
classificados com câncer
Mestrado em Ciencia da Computacao
7
Processo de Classificação
Amostras
Deriva Modelo
(Regras)
Calcula Acuracia
Dados
Dados
de teste
Mestrado em Ciencia da Computacao
8
Preparação dos Dados



Limpeza dos dados : remove ruidos e resolve
problemas de dados incompletos
Análise de Relevância : elimina atributos
irrevelantes para a classificação
Transformação dos dados



Categorização
Generalização
Ex: Rua pode ser substituido por Cidade
Normalização : todos os valores dos atributos em [0,1]
Mestrado em Ciencia da Computacao
9
Árvore de Decisão
IDADE
≤ 30
>60
31-50
51-60
PROFISSÃO
RENDA
Não
B
Sim
Med
M
Não
Sim
M-A
Prof
A
Sim
Sim
Sim
Sim
Eng
Vend
Não
Sim
Se Idade ≤ 30 e Renda é Baixa então Não compra Eletrônico
Se Idade = 31-50 e Prof é Médico então compra Eletrônico
Mestrado em Ciencia da Computacao
10
Como criar uma Árvore de Decisão
– Algoritmo ID3
A
CASO 1
B
C
CLASSE
a1 b1 c1
C1
a1 b2 c1
X
a2 b1 c1
X
a2 b2 c2
X
a1 b2 c2
X
X
Mestrado em Ciencia da Computacao
11
Como criar uma Árvore de Decisão
A
CASO 2
B
C
CLASSE
a1 b1
c1
X
a1 b2
c1 A
X
a2 b1
c1
Y
a2 b2
c2
X
Y
a1
A
B
C
a1 b2 c2
CLASSE
a1
b1
c1
a1
b2
a1
b2
Atributo-Teste =
a2
O que mais reduz
a entropia
A
B
C
CLASSE
X
a2
b1
c1
Y
c1
X
a2
b2
c2
X
c2
Y
LISTA-ATRIBUTOS = { A, B, C }
Mestrado em Ciencia da Computacao
12
Como criar uma Árvore de Decisão
A
a1
a2
A
BC C
a1
b1
c1
X
a1
b2
c1
X
A
a1
B
b2 Cc2 CLASSE
Y
c1
X
Atributo-Teste =
CLASSE
a1 b1 c1
X
a1 b2 c1
X
O que mais reduz a entropia
=C
c2
A
Y
B
C
a1 b2 c2
CLASSE
Y
LISTA-ATRIBUTOS = { B, C }
Mestrado em Ciencia da Computacao
13
Qual é o Atributo-Teste ?

Divide-se o nó segundo cada atributo.

Para cada divisão calcula-se a entropia
produzida caso fosse escolhido este atributo.

Considera-se o atributo cuja divisão resulta
numa maior redução da entropia.
Mestrado em Ciencia da Computacao
14
Informação ganha na divisão

Entrop(A) = -NC1 log2 NC1 - NC2 log2 NC2
Tot

Tot
Tot
Tot
Entrop(D) = NF1 * Entrop(F1) + NF2 * Entrop(F2)
Tot
Tot

Info(Divisão) = Entrop(A) – Entrop (D)

Maior Info(Divisão)  Atributo escolhido
Mestrado em Ciencia da Computacao
15
Um Exemplo
Aparência
Temperatura
Humidade
Vento
Classe
Sol
Quente
Alta
Não
Ruim
Sol
Quente
Alta
Sim
Ruim
Encoberto
Quente
Alta
Não
Bom
Chuvoso
Agradavel
Alta
Não
Bom
Chuvoso
Frio
Normal
Não
Bom
Chuvoso
Frio
Normal
Sim
Ruim
Encoberto
Frio
Normal
Sim
Bom
Sol
Agradavel
Alta
Não
Ruim
Sol
Frio
Normal
Não
Bom
Chuvoso
Agradavel
Normal
Não
Bom
Sol
Agradavel
Normal
Sim
Bom
Encoberto
Agradavel
Alta
Sim
Bom
Encoberto
Quente
Normal
Não
Bom
Chuvoso
Agradavel
Alta
Sim
Ruim
Mestrado em Ciencia da Computacao
16
1a divisão possível : Aparência
APARÊNCIA
Sol
Bom
Bom
Bom
Ruim
Ruim
Enc
Bom
Bom
Bom
Bom
Chuva
Bom
Bom
Bom
Ruim
Ruim
Entrop(D) = 5/14 * Entrop(F1) + 4/14*Entrop(F2) + 5/14*Entrop(F3)
= 0.693
Entrop(F1) = -3/5*log2(3/5) - 2/5*log2 (2/5) = 0.971
Entrop(F2) = - 4/4*log2 (4/4) = 0
Entrop(F3) = - 3/5*log2(3/5) - 2/5*log2(2/5) = 0.971
Mestrado em Ciencia da Computacao
17
Redução da Entropia
Entrop(A) = - (9/14 * log2 (9/14) + 5/14* log2(5/14)) =
= 0.940
INFO(APARÊNCIA) = Entrop(A) – Entrop(D) =
= 0.940 - 0.693 = 0.247
Mestrado em Ciencia da Computacao
18
Comparando as 4 possibilidades

Info(Aparência) = 0.247

Info(Temperatura) = 0.029

Info(Humidade) = 0.152

Info(Vento) = 0.020
Mestrado em Ciencia da Computacao
19
Algoritmo ID3

Input: Banco de dados de amostras A (com os valores dos
atributos categorizados), lista de atributos Cand-List

Output : Uma árvore de decisão
Begin
Gera-árvore(A, Cand-List)
End
Mestrado em Ciencia da Computacao
20
Algoritmo ID3
Gera-árvore(A, Cand-List)
Cria um nó N; Associa a este nó o banco de dados A
Se todas as tuplas de A são da mesma classe C: transforma N numa folha com label C e
PÁRA
Caso contrário: Se Cand-List = vazio então transforma N numa folha com label igual a
classe mais frequente de A
Caso contrário: X:= Ganho(Cand-List)
% esta função retorna o atributo X com maior ganho de informação (que causa maior
redução de entropia)
Etiqueta N com o atributo X
Para cada valor a do atributo X




5.
6.
1.
2.
3.
Cria nó-filho F ligado a X por um ramo com label a e associa a este nó o
conjunto A’ de amostras que tem X = a
Se A’ é vazio: transforma o nó F numa folha com label C onde C é a classe
mais frequente de A
Caso contrário: chama a rotina Gera(A’, Cand-List-{X}) e associa ao nó F a
árvore resultante deste cálculo.
Mestrado em Ciencia da Computacao
21
Implementações

Christian Borgelt's Webpages
http://www.borgelt.net//software.html
Software Weka
Machine Learning Software in Java

http://www.cs.waikato.ac.nz/ml/weka/
Dados reais para testes
UCI Machine Learning Repository

http://archive.ics.uci.edu/ml/datasets.html
Mestrado em Ciencia da Computacao
22
Exercicio : amostras
A
B
C
D
CLASSE
a1
b1
c1
d1
SIM
a1
b1
c2
d1
NAO
a2
b2
c1
d1
SIM
a2
b2
c2
d2
NAO
a1
b2
c2
d1
NAO
a2
b1
c2
d2
SIM
a3
b2
c2
d2
SIM
a1
b3
c1
d1
SIM
a3
b1
c1
d1
NAO
Mestrado em Ciencia da Computacao
23
Exercicio - Testes
A
B
C
D
CLASSE
a2
b2
c2
d1
SIM
a1
b1
c2
d2
NÃO
a2
b2
c1
d3
SIM
a2
b2
c2
d1
SIM
a1
b2
c2
d2
NÃO
a2
b1
c2
d1
SIM
a3
b3
c2
d2
SIM
a1
b3
c1
d1
NÃO
a3
b3
c1
d1
NÃO
Mestrado em Ciencia da Computacao
24
Acurácia, Sensividade, Precisão
A
B
C
D
a2
b2
c2
d1
a1
b1
c2
d2
a2
b2
c1
d3
a2
b2
c2
d1
a1
b2
c2
d2
a2
b1
c2
d1
a3
b3
c2
d2
a1
b3
c1
d1
a3
b3
c1
d1
Mestrado em Ciencia da Computacao
CLASSE
25