Classificação
Arvores de Decisão
AULA 7
Data Mining
Sandra de Amo
Classificadores Lazy
Aprendem a partir de seus vizinhos
AULA 9
DATA MINING
Sandra de Amo
Mestrado em Ciencia da Computacao
2
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
3
Etapas do Processo
Amostras
Classificadas
REGRAS
Banco de
Testes
Classificador
REGRAS CONFIÁVEIS
Mestrado em Ciencia da Computacao
4
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
5
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
presença de ruidos e valores desconhecidos
Escalabilidade – eficiência do classificador em
grandes volumes de dados
Interpretabilidade – facilidade de um usuário
entender as regras produzidas pelo classificador
Mestrado em Ciencia da Computacao
6
Acurácia – Taxa de erros



Acc(M) = porcentagem das tuplas dos dados de
teste que são 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
7
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
8
Processo de Classificação
Amostras
Deriva Modelo
(Regras)
Calcula Acuracia
Dados
Dados
de teste
Mestrado em Ciencia da Computacao
9
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
10
Classificadores Lazy
Aprendem a partir de seus vizinhos
Não constrói um modelo de classificação.
Para cada nova tupla que se quer classificar, o banco
de dados de treinamento é analisado.
Mestrado em Ciencia da Computacao
11
História




Método introduzido nos anos 50.
Muito dispendioso computacionalmente.
Só ganhou popularidade a partir dos anos 60,
como o aumento da capacidadecomputacional
dos computadores.
Muito usado na área de Reconhecimento de
Padrões.
Mestrado em Ciencia da Computacao
12
Descrição do Método KNN






Dados: Banco de Dados de m tuplas classificadas (a1,...,an,C)
Uma tupla X = (x1,...,xn) não classificada
Os valores dos atributos são normalizados.
Valor normalizado = (v.real - MinA)/(MaxA – MinA)
Calcula-se a distância de X a cada uma das tuplas do banco
de dados.
Pega-se as k tuplas do banco de dados mais próximas de X.
A classe de X é a classe que aparece com mais frequência
entre as k tuplas mais próximas de X.
Mestrado em Ciencia da Computacao
13
Diferentes valores de K
K=1
K=2
Mestrado em Ciencia da Computacao
K=3
14
Algumas questões

Como calcular a distância entre duas tuplas ?


Para atributos contínuos : distância Euclidiana
d(x,y) = √ Σni=1 (xi – yi)2
Para atributos categóricos
Se xi = yi então xi – yi = 0
Se xi e yi são distintos: xi – yi = 1

Como lidar com valores incompletos (ausentes) ao calcular a
distância entre duas tuplas X e Y ?



Se xi e yi são ausentes: xi – yi = 1
Se xi é ausente e yi não: xi – yi = max { |1 – yi|, |0 – yi| }
Como determinar o melhor valor de K (=número de vizinhos)
?
Obtido repetindo-se os experimentos.
Mestrado em Ciencia da Computacao
15
Vantagens e Desvantagens

Performance




Não constrói um modelo de classificação.
Processo de classificação de uma tupla é lento.
Classificadores Eager gastam tempo para construir o
modelo. O processo de classificação de uma tupla é
rápido.
Sensível a ruídos


KNN faz predição baseando-se em informações locais à
tupla sendo classificada.
Arvores de decisão, redes neurais e bayesianas encontram
modelo global que se leva em conta todo o banco de
dados de treinamento.
Mestrado em Ciencia da Computacao
16
Exemplo
Compra-computador
ID
IDADE
RENDA
ESTUDANTE
CREDITO
CLASSE
1
≤ 30
Alta
Não
Bom
Não
2
≤ 30
Alta
Sim
Bom
Não
3
31...40
Alta
Não
Bom
Sim
4
> 40
Média
Não
Bom
Sim
5
> 40
Baixa
Sim
Bom
Sim
6
> 40
Baixa
Sim
Excelente
Não
7
31...40
Baixa
Sim
Excelente
Sim
8
≤ 30
Média
Não
Bom
Não
9
≤ 30
Baixa
Sim
Bom
Sim
10
> 40
Média
Sim
Bom
Sim
11
≤ 30
Média
Sim
Excelente
Sim
12
31...40
Média
Não
Excelente
Sim
13
31...40
Alta
Sim
Bom
Sim
14
> 40
Média
Não
Excelente
Não
Mestrado em Ciencia da Computacao
X = (≤
30, Média,Sim,Bom)
17
Exemplo
Distância
VALOR
d(X,1)
1,41
d(X,2)
1
d(X,3)
1,73
d(X,4)
1,41
d(X,5)
1,41
d(X,6)
1,73
d(X,7)
1,73
d(X,8)
1
d(X,9)
1
d(X,10)
1
d(X,11)
1
d(X,12)
1,73
d(X,13)
1,41
d(X,14)
Mestrado em Ciencia da Computacao
1,73
18
Exemplo


K=5
Os 5 vizinhos mais próximos são

X1 = ( ≤ 30
X2 = (≤ 30
X3 = ( ≤ 30
X4 = ( > 40
X5 = (≤ 30

Logo, X é classificada na classe = Sim




Alta
Média
Baixa
Média
Média
Sim
Não
Sim
Sim
Sim
Bom)
Bom)
Bom)
Bom)
Exc. )
Classe = Não
Classe = Não
Classe = Sim
Classe = Sim
Clase = Sim
Mestrado em Ciencia da Computacao
19
Classificadores Eager
Constróem um modelo de classificação.
Modelo é utilizado para classificar nova tupla.
Mestrado em Ciencia da Computacao
20
Modelo: Á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
21
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
22
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
23
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
24
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
25
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
26
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
27
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
28
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
29
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
30
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
31
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
32
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
33
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
34
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
35
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
36