Classificação Arvores de Decisão AULA 7 Data Mining Sandra de Amo

ClassificaçãoArvores de Decisão

AULA 7

Data Mining

Sandra de Amo

Mestrado em Ciencia da Computacao 2

Aprendem a partir de seus vizinhosAULA 9

DATA MINING

Sandra de Amo

Classificadores Lazy


Classificação

Nome Idade Renda Profissão ClasseDaniel ≤ 30 Média Estudante Sim

João 31..50 Média-Alta Professor Sim

Carlos 31..50 Média-Alta Engenheiro Sim

Maria 31..50 Baixa Vendedora Não

Paulo ≤ 30 Baixa Porteiro Não

Otavio > 60 Média-Alta Aposentado Não

SE.

Idade ≤ 30 Renda é Média Compra-Produto-Eletrônico = SIM. E ENTÃO


Etapas do Processo

REGRAS

Classificador

Amostras Classificadas Banco de

Testes

REGRAS CONFIÁVEIS


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


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


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

C1 C2

C1 Positivos

verdadeiros

Falsos Negativos

C2 Falsos

Positivos

Negativos

verdadeiros

Classes Preditas

Classes Reais


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âncerNão acertou nenhum dos que tem câncer

Pode ser classificado como “bom classificador” mesmo com acurácia alta ?

Sensitividade = true-pos pos

Especificidade = true-neg neg

Precisão = true-pos true-pos + falso-pos

% pacientes classificados corretamente com câncer dentre todos os que foram classificados com câncer

% pacientes classificados corretamente com câncer dentre todos os que realmente tem câncer


Processo de Classificação

Dados

Amostras

Dados de teste

Deriva Modelo(Regras)

Calcula Acuracia


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]


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.

Classificadores Lazy


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.


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.


Diferentes valores de K

K = 1 K = 2 K = 3


Algumas questões Como calcular a distância entre duas tuplas ?

Para atributos contínuos : distância Euclidiana d(x,y) = √ Σn

i=1 (xi – yi)2

Para atributos categóricosSe xi = yi então xi – yi = 0Se 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.


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.


ExemploID 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

Compra-computador

X = (≤ 30, Média,Sim,Bom)


ExemploDistâ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) 1,73


Exemplo K = 5 Os 5 vizinhos mais próximos são X1 = ( ≤ 30 Alta Sim Bom) Classe = Não X2 = (≤ 30 Média Não Bom) Classe = Não X3 = ( ≤ 30 Baixa Sim Bom) Classe = Sim X4 = ( > 40 Média Sim Bom) Classe = Sim X5 = (≤ 30Média Sim Exc. ) Clase = Sim

Logo, X é classificada na classe = Sim


Constróem um modelo de classificação.

Modelo é utilizado para classificar nova tupla.

Classificadores Eager


Modelo: Árvore de Decisão IDADE

RENDAPROFISSÃO

≤ 30

BM

M-A A

>60 51-6031-50

MedProf

VendEng

Não

Sim

Sim SimSimNão Não

Sim

SimSim

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


Como criar uma Árvore de Decisão – Algoritmo ID3

C1CASO 1

A B C CLASSE

a1 b1 c1 X

a1 b2 c1 X

a2 b1 c1 X

a2 b2 c2 X

a1 b2 c2 X


Como criar uma Árvore de DecisãoA B C CLASSE

a1 b1 c1 X

a1 b2 c1 X

a2 b1 c1 Y

a2 b2 c2 X

a1 b2 c2 YA B C CLASSE

a1 b1 c1 X

a1 b2 c1 X

a1 b2 c2 Y

CASO 2

LISTA-ATRIBUTOS = {

Atributo-Teste =

O que mais reduz a entropia

A B C CLASSE

a2 b1 c1 Y

a2 b2 c2 X

A

a1 a2

A, B, C }


Como criar uma Árvore de Decisão

A B C CLASSE

a1 b2 c2 Y

A B C CLASSE

a1 b1 c1 X

a1 b2 c1 X

a1 b2 c2 YA B C CLASSE

a1 b1 c1 X

a1 b2 c1 X

LISTA-ATRIBUTOS = {

Atributo-Teste =

O que mais reduz a entropia = C

Aa1 a2

B, C }

C

c1 c2

X Y


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.


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


Um ExemploAparê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


1a divisão possível : Aparência APARÊNCIA

Sol ChuvaEnc

BomBomBom

Bom Bom

Bom

BomBom

BomBom

RuimRuim Ruim

Ruim

Entrop(D) = 5/14 * Entrop(F1) + 4/14*Entrop(F2) + 5/14*Entrop(F3)

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

= 0.693


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


Comparando as 4 possibilidades Info(Aparência) = 0.247

Info(Temperatura) = 0.029

Info(Humidade) = 0.152

Info(Vento) = 0.020


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


Algoritmo ID3Gera-á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) 5. Etiqueta N com o atributo X6. Para cada valor a do atributo X

1. 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

2. Se A’ é vazio: transforma o nó F numa folha com label C onde C é a classe mais frequente de A

3. Caso contrário: chama a rotina Gera(A’, Cand-List-{X}) e associa ao nó F a árvore resultante deste cálculo.


Implementações Christian Borgelt's Webpageshttp://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


Exercicio : amostrasA 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


Exercicio - TestesA 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


Acurácia, Sensividade, PrecisãoA B C D CLASSE

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

Documents

Classificação Arvores de Decisão AULA 7 Data Mining Sandra de Amo