Mineração de dados

Classificação: conceitos básicos e árvores de decisão

Apresentação adaptada do material de apoio do livro: Introduction to Data Mining

Tan, Steinbach, Kumar

Classificação: Definição

Dada uma coleção de registros (conjunto de treinamento,training set )– cada registro contém um conjunto de atributos, e um dos

atributos é a classe. Encontre um modelo para o atributo classe como

uma função dos valores de outros atributos. Objetivo: a classe deve ser atribuída tão

acuradamente quanto possível para novos registros.– Um conjunto de teste (test set) é usado para determinar a

acurácia do modelo. Geralmente o conjunto de dados é dividido em conjunto de treinamento e conjunto de teste.

Ilustrando a Tarefa de Classificação

Apply

Model

Induction

Deduction

Learn

Model

Model

Tid Attrib1 Attrib2 Attrib3 Class

1 Yes Large 125K No

2 No Medium 100K No

3 No Small 70K No

4 Yes Medium 120K No

5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No

8 No Small 85K Yes

9 No Medium 75K No

10 No Small 90K Yes 10

Tid Attrib1 Attrib2 Attrib3 Class

11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ?

14 No Small 95K ?

15 No Large 67K ? 10

Test Set

Learningalgorithm

Training Set

Exemplos de Tarefas de Classificação

Predizer se um tumor é benigno ou maligno

Classificar transações de cartões

de crédito como legítimas ou

fraudulentas

Classificar estruturas secundárias de

proteínas como alpha-helix,

beta-sheet, or random coil

Categorizar textos como da área de finanças,

previsão de tempo, esportes, cultura, etc.

Técnicas de Classificação

Métodos baseados em árvores de decisão Métodos baseados em regras Raciocínio baseado em memória Redes neurais Naïve Bayes e Redes Bayesianas Máquinas de Vetores de Suporte (Support Vector

Machines)

Exemplo de uma árvore de decisão

Tid Refund MaritalStatus

TaxableIncome Cheat

1 Yes Single 125K No

2 No Married 100K No

3 No Single 70K No

4 Yes Married 120K No

5 No Divorced 95K Yes

6 No Married 60K No

7 Yes Divorced 220K No

8 No Single 85K Yes

9 No Married 75K No

10 No Single 90K Yes10

categoric

al

categoric

al

continuous

class

Refund

MarSt

TaxInc

YESNO

NO

NO

Yes No

Married Single, Divorced

< 80K > 80K

Atributo teste

Dados de treinamento

Modelo: árvore de decisão

Outro exemplo de árvore de decisão

Tid Refund MaritalStatus

TaxableIncome Cheat

1 Yes Single 125K No

2 No Married 100K No

3 No Single 70K No

4 Yes Married 120K No

5 No Divorced 95K Yes

6 No Married 60K No

7 Yes Divorced 220K No

8 No Single 85K Yes

9 No Married 75K No

10 No Single 90K Yes10

categóric

o

categóric

o

contínuo

classeMarSt

Refund

TaxInc

YESNO

NO

NO

Yes No

Married Single,

Divorced

< 80K > 80K

Pode haver mais de um árvore para o mesmo conjunto de dados

Classificação usando árvores de decisão

Apply

Model

Induction

Deduction

Learn

Model

Model

Tid Attrib1 Attrib2 Attrib3 Class

1 Yes Large 125K No

2 No Medium 100K No

3 No Small 70K No

4 Yes Medium 120K No

5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No

8 No Small 85K Yes

9 No Medium 75K No

10 No Small 90K Yes 10

Tid Attrib1 Attrib2 Attrib3 Class

11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ?

14 No Small 95K ?

15 No Large 67K ? 10

Test Set

TreeInductionalgorithm

Training Set

Decision Tree

Aplicando o modelo nos dados de teste

Refund

MarSt

TaxInc

YESNO

NO

NO

Yes No

Married Single, Divorced

< 80K > 80K

Refund Marital Status

Taxable Income Cheat

No Married 80K ? 10

Comece pela raíz da árvore.Dado para teste

Aplicando o modelo nos dados de teste

Refund

MarSt

TaxInc

YESNO

NO

NO

Yes No

Married Single, Divorced

< 80K > 80K

Refund Marital Status

Taxable Income Cheat

No Married 80K ? 10

Dado para teste

Aplicando o modelo nos dados de teste

Refund

MarSt

TaxInc

YESNO

NO

NO

Yes No

Married Single, Divorced

< 80K > 80K

Refund Marital Status

Taxable Income Cheat

No Married 80K ? 10

Dado para teste

Aplicando o modelo nos dados de teste

Refund

MarSt

TaxInc

YESNO

NO

NO

Yes No

Married Single, Divorced

< 80K > 80K

Refund Marital Status

Taxable Income Cheat

No Married 80K ? 10

Dado para teste

Aplicando o modelo nos dados de teste

Refund

MarSt

TaxInc

YESNO

NO

NO

Yes No

Married Single, Divorced

< 80K > 80K

Refund Marital Status

Taxable Income Cheat

No Married 80K ? 10

Dado para teste

Aplicando o modelo nos dados de teste

Refund

MarSt

TaxInc

YESNO

NO

NO

Yes No

Married Single, Divorced

< 80K > 80K

Refund Marital Status

Taxable Income Cheat

No Married 80K ? 10

Assign Cheat to “No”

Dado para teste

Classificação com árvore de decisão

Apply

Model

Induction

Deduction

Learn

Model

Model

Tid Attrib1 Attrib2 Attrib3 Class

1 Yes Large 125K No

2 No Medium 100K No

3 No Small 70K No

4 Yes Medium 120K No

5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No

8 No Small 85K Yes

9 No Medium 75K No

10 No Small 90K Yes 10

Tid Attrib1 Attrib2 Attrib3 Class

11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ?

14 No Small 95K ?

15 No Large 67K ? 10

Test Set

TreeInductionalgorithm

Training Set

Decision Tree

Indução de árvores de decisão

Vários algoritmos:

– Hunt’s Algorithm (um dos primeiros)

– CART

– ID3, C4.5

– SLIQ,SPRINT

Estrutura geral do algorítmo de Hunt

Seja Dt o conjunto de registros de teste que alcança o nodo t

Procedimento geral:

– Se Dt só contém registros que pertencem a mesma classe yt, então t é um nodo folha rotulado como yt

– Se Dt é um conjunto vazio, então t é um nodo folha rotulado com a classe default, yd

– Se Dt contém registros que pertencem a mais de uma classe, use um atributo teste para dividir os dados em subconjuntos menores. Recursivamente aplique o procedimento para cada subconjunto.

Tid Refund Marital Status

Taxable Income Cheat

1 Yes Single 125K No

2 No Married 100K No

3 No Single 70K No

4 Yes Married 120K No

5 No Divorced 95K Yes

6 No Married 60K No

7 Yes Divorced 220K No

8 No Single 85K Yes

9 No Married 75K No

10 No Single 90K Yes 10

Dt

?

Hunt’s Algorithm

Don’t Cheat

Refund

Don’t Cheat

Don’t Cheat

Yes No

Refund

Don’t Cheat

Yes No

MaritalStatus

Don’t Cheat

Cheat

Single,Divorced

Married

TaxableIncome

Don’t Cheat

< 80K >= 80K

Refund

Don’t Cheat

Yes No

MaritalStatus

Don’t Cheat

Cheat

Single,Divorced

Married

Indução da árvore

Estratégia gulosa.

– Divida os registros baseado no atributo teste que otimiza um certo critério.

Questões

– Determine como dividir os registrosComo especificar qual o atributo teste?Como determinar a melhor divisão?

– Determine quando parar de dividir

Como especificar qual o atributo teste?

Depende do tipo dos atributos

– Nominal (categórico,...)

– Ordinal

– Contínuo

Depende do tipo de divisão

– divisão binária

– divisão em múltiplos caminhos

Divisão baseada em atributos nominais

Divisão múltipla: Use tantas partições quantos forem

os valores distintos do atributo.

Divisão binária: Divide em dois subconjuntos. Necessidade de encontrar o particionamento ótimo.

CarTypeFamily

Sports

Luxury

CarType{Family, Luxury} {Sports}

CarType{Sports, Luxury} {Family} OU

Divisão múltipla : Use tantas partições quantos forem os valores distintos do atributo

Divisão binária: Divide em dois subconjuntos. Necessidade de encontrar o particionamento ótimo.

E esta divisão?

Divisão baseada em atributos ordinais

SizeSmall

Medium

Large

Size{Medium,

Large} {Small}

Size{Small,

Medium} {Large}OU

Size{Small, Large} {Medium}

Divisão baseada em atributos contínuos

Diferentes formas de tratar

– Discretização para formar um atributo ordinal categórico Estático – discretizar uma vez no início Dinâmico – intervalos podem ser determinados por mesmo tamanho, mesma freqüência, clustering.

– Decisão binária: (A < v) or (A v) considera todas as divisões possíveis e usa a melhor

Divisão baseada em atributos contínuos

TaxableIncome> 80K?

Yes No

TaxableIncome?

(i) Binary split (ii) Multi-way split

< 10K

[10K,25K) [25K,50K) [50K,80K)

> 80K

Indução de árvores

Estratégia gulosa.

– Divida os registros baseado no atributo teste que otimiza um certo critério.

Questões

– Determine como dividir os registrosComo especificar qual o atributo teste?Como determinar a melhor divisão?

– Determine quando parar de dividir

Como determinar a melhor divisão

OwnCar?

C0: 6C1: 4

C0: 4C1: 6

C0: 1C1: 3

C0: 8C1: 0

C0: 1C1: 7

CarType?

C0: 1C1: 0

C0: 1C1: 0

C0: 0C1: 1

StudentID?

...

Yes No Family

Sports

Luxury c1c10

c20

C0: 0C1: 1

...

c11

Antes da divisão: 10 registros da classe 0, 10 registros da classe 1

Qual divisão é a melhor?

Como determinar a melhor divisão

Estratégia gulosa :

– Nós com distribuição de classe homogenea são preferidos

Necessita da medida da “impureza” do nó:

C0: 5C1: 5

C0: 9C1: 1

Não-homogênea,

Alto grau de impureza

Homogêneo,

baixo grau de impureza

Medidas de impureza de um nó

Índice de Gini

Entropia

Erro de classificação

Como encontrar a melhor divisão?

B?

Sim Não

Nodo N3 Nodo N4

A?

Sim Não

Nodo N1 Nodo N2

Antes da divisão:

C0 N10 C1 N11

C0 N20 C1 N21

C0 N30 C1 N31

C0 N40 C1 N41

C0 N00 C1 N01

M0

M1 M2 M3 M4

M12 M34Ganho = M0 – M12 vs M0 – M34

Medida da impureza: GINI

Índice Gini para um nó t :

(Nota: p( j | t) é a freqüência relativa da classe j no nó t).

– Máximo (1 - 1/nc) quando os registros estão igualmente distribuídos entre todas as classes (pior)

– Mínimo (0.0) quando todos os registros pertencem a uma classe (melhor)

j

tjptGINI 2)]|([1)(

C1 0C2 6

Gini=0.000

C1 2C2 4

Gini=0.444

C1 3C2 3

Gini=0.500

C1 1C2 5

Gini=0.278

Exemplos do cálculo do índice GINI

C1 0 C2 6

C1 2 C2 4

C1 1 C2 5

P(C1) = 0/6 = 0 P(C2) = 6/6 = 1

Gini = 1 – P(C1)2 – P(C2)2 = 1 – 0 – 1 = 0

j

tjptGINI 2)]|([1)(

P(C1) = 1/6 P(C2) = 5/6

Gini = 1 – (1/6)2 – (5/6)2 = 0.278

P(C1) = 2/6 P(C2) = 4/6

Gini = 1 – (2/6)2 – (4/6)2 = 0.444

Divisão baseda no índice GINI

Usado nos métodos CART, SLIQ, SPRINT. Quando um nó p é dividido em k partições (filhos), a

qualidade da divisão é calculada como,

onde, ni = número de registros no filho i,

n = número de registros no nó p.

k

i

isplit iGINI

n

nGINI

1

)(

Índice Gini para atributos categóricos

CarType{Sports,Luxury}

{Family}

C1 3 1

C2 2 4

Gini 0.400

CarType

{Sports}{Family,Luxury}

C1 2 2

C2 1 5

Gini 0.419

CarType

Family Sports Luxury

C1 1 2 1

C2 4 1 1

Gini 0.393

Multi-way split Binary split (find best partition of values)

Atributos contínuos: cálculo do índice Gini

Usar decisão binária baseada em um valor

Várias possibilidades para a escolha do valor de corte

– Número de possíveis cortes = número de valores distintos

Cada valor de corte tem uma matriz associada

– Contadores de classe para cada partição possível, A < v and A v

Método simples para escolher o melhor valor de corte

– Para cada v, varra os dados para realizar a contagem e calcular o índice Gini

– Computacionalmente ineficiente! Reptição do trabalho.

TaxableIncome> 80K?

Yes No

Atributos contínuos: cálculo do índice Gini

Para uma computação eficiente: para cada atributo contínuo,– Classifique os valores do atributo em ordem crescente– percorra os dados, atualizando a matriz de contadores e calculando o

índice Gini– Escolha a posição de corte que tem o menor índice Gini

Cheat No No No Yes Yes Yes No No No No

Taxable Income

60 70 75 85 90 95 100 120 125 220

55 65 72 80 87 92 97 110 122 172 230

<= > <= > <= > <= > <= > <= > <= > <= > <= > <= > <= >

Yes 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0

No 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0

Gini 0.420 0.400 0.375 0.343 0.417 0.400 0.300 0.343 0.375 0.400 0.420

Split Positions

Sorted Values

Divisão baseada em entropia

Entropia em um nó t:

(Nota: p( j | t) é a freqüência relativa da classe j no nó t).

– Mede a homogeneidade de um nó. Máximo (log nc) quando os registros estão igualmente

distribuídos entre todas as classes

Mínimo (0.0) quando todos os registros pertencem a uma classe

– O cálculo baseado em entropia é similar ao baseado no índice Gini

j

tjptjptEntropy )|(log)|()(

Exemplos de cálculo da entropia

C1 0 C2 6

C1 2 C2 4

C1 1 C2 5

P(C1) = 0/6 = 0 P(C2) = 6/6 = 1

Entropia = – 0 log 0 – 1 log 1 = – 0 – 0 = 0

P(C1) = 1/6 P(C2) = 5/6

Entropia = – (1/6) log2 (1/6) – (5/6) log2 (1/6) = 0.65

P(C1) = 2/6 P(C2) = 4/6

Entropia = – (2/6) log2 (2/6) – (4/6) log2 (4/6) = 0.92

j

tjptjptEntropy )|(log)|()(2

Divisão baseada em entropia ...

Ganho de Informação (Information Gain):

O nó pai p é dividido em k partições;

ni é o número de registros na partição i

– Mede a redução da entropia em função da divisão. Escolhe a divisão que obtém maior redução (maximiza o ganho)

– Usado nos métodos ID3 e C4.5

– Desvantagem: Tende a preferir divisões que resultam em grande número de partições, cada uma delas sendo pequena mas pura.

k

i

i

splitiEntropy

nn

pEntropyGAIN1

)()(

Splitting Based on INFO...

Razão de ganho (Gain Ratio):

O nó pai p é dividido em k partições;

ni é o número de registros na partição i

– Ajusta o Ganho de Informação pela entropia do particionamento (SplitINFO). Particionamento de alta entropia (grande número de pequenas partições) é penalizado.

– Usado no C4.5– Projetado para evitar as desvantagens do Ganho de

Informação

SplitINFO

GAINGainRATIO Split

split

k

i

ii

nn

nn

SplitINFO1

log

Exemplo:

caso montante idade salário conta empréstimo 1 médio sênior baixo sim não 2 médio sênior baixo não não 3 baixo sênior baixo sim sim 4 alto média baixo sim sim 5 alto jovem alto sim sim 6 alto jovem alto não não 7 baixo jovem alto não sim 8 médio média baixo sim não 9 médio jovem alto sim sim 10 alto média alto sim sim 11 médio média alto não sim 12 baixo jovem baixo não sim 13 baixo sênior alto sim sim 14 alto média baixo não não

Entropia e Ganho de Informação

Considerando apenas 2 valores possíveis, a entropia é dada pela fórmula:

Entropia (S) = - (p+ log2 p+ + p- log2 p-)

Onde:

S é a totalidade de amostras do conjunto (todos os registros)

p+ é a proporção de amostras positivas

p- é a proporção de amostras negativas

Exemplo:

Se S é uma coleção de 14 exemplos com 9 instâncias positivas e 5 negativas, então:

Entropia (S) = - (9/14) Log 2 (9/14) – (5/14) Log 2 (5/14) = 0.940

Nodo raiz

Selecionando o melhor atributo:

Entropia(S) = - 9/14 log2 (9/14) - 5/14 log 2 (5/14) = 0,940

caso montante idade salário conta empréstimo1 médio sênior baixo sim não2 médio sênior baixo não não3 baixo sênior baixo sim sim4 alto média baixo sim sim5 alto jovem alto sim sim6 alto jovem alto não não7 baixo jovem alto não sim8 médio média baixo sim não9 médio jovem alto sim sim10 alto média alto sim sim11 médio média alto não sim12 baixo jovem baixo não sim13 baixo sênior alto sim sim14 alto média baixo não não

Entropia(montante=médio) = - 2/5 log2 (2/5) - 3/5 log 2 (3/5) = 0,971

Entropia(montante=baixo) = - 4/4 log2 (4/4) - 0/4 log2 (0/4) = 0

Entropia(montante=alto) = - 3/5 log2 (3/5) - 2/5 log2 (2/5) = 0,971

Gain (S,montante) = 0,940 - (5/14) 0,971 - (4/14) 0 - (5/14) 0,971 = 0,246

Gain (S,idade) = 0,940 - (4/14) 1 - (5/14) 0,971 - (5/14) 0,722 = 0,049

Gain (S,salário) = 0,940 - (7/14) 0,592 - (7/14) 0,985 = 0,151

Gain (S,conta) = 0,940 - (8/14) 0,811 - (6/14) 1 = 0,047

Escolha do próximo atributo

Qual atributo pode ser testado aqui?

montante

médio baixo alto

?? sim

{C1,C2,...C14}[9+, 5-]

{C1,C2,C8,C9,C11}[2+, 3-]

{C3,C7,C12,C13}[4+, 0-]

{C4,C5,C6,C10,C14}[3+, 2-]

Escolha o próximo atributo

Qual é o melhor atributo?

Smédio = {C1,C2,C8,C9,C11}

Gain (Smédio, idade) = 0,971 - (2/5)0 - (2/5)1 - (1/5)0 = 0,571

Gain (Smédio, salário) = 0,971 - (3/5)0 - (2/5)0 = 0,971

Gain (Smédio, conta) = 0,971 - (3/5)0,918 - (2/5)1= 0,020

montante

médio baixo alto

?salário sim

{C1,C2,...C14}[9+, 5-]

{C1,C2,C8,C9,C11}[2+, 3-]

{C3,C7,C12,C13}[4+, 0-]

{C4,C5,C6,C10,C14}[3+, 2-]

baixo alto

{C1,C2,C8}[0+, 3-]

{C9,C11}[2+, 0-]

Resultado

montante

médio baixo alto

contasalário

baixo alto não sim

E=simE=não E=não E=sim

E=sim

Divisão baseada em erro de classificação

Erro de classificação no nó t :

Mede o erro de classificação em um nó. Máximo (1 - 1/nc) quando os registros são igualmente

distribuídos entre todas as classes (pior) Mínimo (0.0) quando todos os registros pertencem à mesma

classe (melhor)

)|(max1)( tiPtErrori

Exemplos de cálculo de erro de classificação

C1 0 C2 6

C1 2 C2 4

C1 1 C2 5

P(C1) = 0/6 = 0 P(C2) = 6/6 = 1

Error = 1 – max (0, 1) = 1 – 1 = 0

P(C1) = 1/6 P(C2) = 5/6

Error = 1 – max (1/6, 5/6) = 1 – 5/6 = 1/6

P(C1) = 2/6 P(C2) = 4/6

Error = 1 – max (2/6, 4/6) = 1 – 4/6 = 1/3

)|(max1)( tiPtErrori

Comparação entre os critérios de divisão

Para problemas com duas classes:

Indução de árvores

Estratégia gulosa.

– Divida os registros baseado no atributo teste que otimiza um certo critério.

Questões

– Determinar como dividir os registrosComo especificar qual o atributo teste?Como determinar a melhor divisão?

– Determinar quando parar de dividir

Critérios de parada para a indução de árvores

Pare de expandir um nó quando todos os registros pertencem à mesma classe

Pare de expandir um nó quando todos os registros tiverem os mesmos valores de atributo

Classificação baseada em árvores de decisão

Vantagens:

– Construção barata

– Extremamente rápido para classificar novos registros

– Fácil interpretação de árvores pequenas

– A acurácia é comparável a outros métodos de classificação para muitos conjuntos de dados

Exemplo: C4.5

Algoritmo simples, em profundidade. Usa o Ganho de Informação (Information Gain) Classifica atributos contínuos em cada nó. Exige que todos os dados caibam em memória. Não indicado para grandes conjuntos de dados.

– Necessita classificação em disco.

O Software pode ser baixado do site:http://www.cse.unsw.edu.au/~quinlan/c4.5r8.tar.gz

Questões práticas de classificação

Sub e super-especialização (Underfitting and Overfitting)

Valores faltantes

Custo da classificação

Sub e super-especialização (Exemplo)

500 pontos circulares e 500 pontos triangulares data.

Pontos circulares:

0.5 sqrt(x12+x2

2) 1

Pontos triangulares:

sqrt(x12+x2

2) > 0.5 or

sqrt(x12+x2

2) < 1

Sub e super-especialização

Overfitting

Sub-especialização: quando o modelo é simples demais, os erros com os dados de treinamento e de teste são grandes

Super-especialização em função do ruído

A fronteira de decisão é distorcida pelo ruído