FERNANDO ARENA VARELLA

Classificadores Baseados em Regras

Roteiro

1. Características2. Ordenamento de Regras3. Métodos Diretos de Extração de

Regras4. Métodos Indiretos de Extração de

Regras5. Conclusão

Características

Classificação a partir de um conjunto de regras: “if ... then ... else”

Similar às árvores decisão

Regras podem ser facilmente entendidas por humanos

Definições

Representadas na forma normal disjuntiva:

R = (r1 ∨ r2 ∨ ... rk)R = conjunto de regras (ruleset)ri = regra de classificação -> (Condição) → yi

Condição = (A1 op v1) ∧ (A2 op v2) ∧ .. (Ai op vi) seqüência de pares valor-atributo antecedente (ou precondição)

yi = Classe predita conseqüente

Definições

Uma regra r cobre um registro x quando seu antecedente casa com os atributos de x

Analogamente, diz-se que uma regra r foi engatilhada (triggered) sempre que cobrir um registro

r1: (Gives Birth = no) ∧ (Aerial Creature = yes) → Birdr2: (Gives Birth = no) ∧ (Aquatic Creature = yes) → Fishr3: (Gives Birth = yes) ∧ (Body Temperature = warm blooded) →

Mammalsr4: (Gives Birth = no) ∧ (Aerial Creature = no) → Reptilesr5: (Aquatic Creature = semi) → Amphibians

Exemplo

r1 cobre o primeiro vertebrado – todas as precondições são satisfeitas

o segundo vertebrado não engatilha r1 – ambas precondições falham

Name Body Temperature

Skin Cover

Gives Birth

Aquatic

Aerial Has Legs

Hibernates

hawk warm-blooded

feathers no no yes yes no

grizzly bear warm-blooded

fur yes no no yes yes

Métricas

Cobertura (Coverage) – Fração de registros de um conjunto de dados (D) que satisfazem o antecedente de uma regra (A)

Coverage(x) = A / D

Acurácia (Accuracy/confidence) – Fração de registros que satisfazem o antecedente e o conseqüente de uma regra (A ∩ y)

Accuracy(r) = (A ∩ y) / A

Name Body Temperature

Skin Cover

Gives Birth

Aquatic

Aerial Has Legs

Hibernates

Class Label

human warm hair yes no no yes no mammals

python cold scales no no no no yes reptiles

salmon cold scales no yes no no no fishes

whale warm hair yes yes no no no mammals

frog cold none no semi no yes yes amphibians

komodo cold scales no no no yes no reptiles

dragon bat warm hair yes no no yes yes mammals

pigeon warm feathers no no yes yes no birds

cat warm fur yes no yes yes no mammals

guppy cold scales yes yes no no no fishes

alligator cold scales no semi no yes no reptiles

penguin warm feathers no semi no yes no birds

porcupine warm quills yes no no yes yes mammals

eel cold scales no yes no no no fishes

salamander cold none no semi no yes yes amphibians

Métricas

Considerando a regra r3r3: (Gives Birth = yes) ∧ (Body Temperature = warm blooded) →

Mammals

Cobre 5 registros do dataset, logo, sua cobertura é de 33% (5/15)

Dos 5 registros, todos são mammals, logo, a acurácia é de 100% (5/5)

Propriedades

Regras Mutuamente Exclusivas: quando não existem 2 regras no ruleset que são engatilhadas pelo menos registro

Regras Exaustivas: quando há uma regra para cada combinação de atributos/valores

A combinação das duas propriedades garantirá que qualquer registro será coberto por exatamente uma regra

Ordenamento

Regras Ordenadas: as regras possuem um valor de prioridade Quando mais de uma regra é engatilhada, a decisão é

feita baseada na lista de prioridades (decision list)

Regras Sem Ordenamento: o conseqüente das regras engatilhadas é colocado em uma lista de votos, ao final, ganha o que tiver mais votos Construção do modelo é mais eficiente, entretanto, a

classificação é mais custosa

Esquemas de Ordenamento

Rule-Based Ordering Scheme: Ordena as regras de acordo com alguma métrica

(normalmente a sua qualidade) Regras com menos qualidade podem ser difíceis de

interpretar (assume a negação de todas as regras anteriores)

Class-Based Ordering Scheme: Regras da mesma classe ficam próximas Pode favorecer classes com maior freqüência

Construção de um Classificador baseado em Regras

Métodos Diretos de extração de regras: Extrai as regras diretamente dos dados

Métodos indiretos de extração de regras: Extrai as regras a partir de outros modelos de

classificação Normalmente utilizados para simplificar o outro

modelo

Métodos Diretos de Extração de Regras

Utiliza algoritmo de cobertura seqüencial dos dados

As regras crescem de modo guloso

Crescimento segue alguma estratégia de crescimento Métricas de qualidade Ordenamento das classes Custo da classificação errônea de alguma classe

Algoritmo de Cobertura Seqüencial

1. Inicia com um conjunto vazio de regras2. Gera uma regra, utilizando a função Learn-One-

Rule3. Adiciona a regra ao conjunto de regras

4. Remove os registros cobertos pela regra gerada5. Repete 2, 3 e 4 até cobrir todos registros

Uma regra é desejável quando: Cobre o maior número possível dos registros positivos; Não cobre nenhum (ou quase nenhum) dos registros

negativos

Exemplo da Cobertura Seqüencial

Passo 1

Passo 2

Exemplo da Cobertura Seqüencial

Passo 3 Passo 4

Função Learn-One-Rule

Objetivos: Cobrir o maior número possível de positivos, e Cobrir o menor número possível de negativos

Gerar a melhor regra possível é muito custoso computacionalmente

Solução: as regras são desenvolvidas gradativamente Pára quando o critério de parada é alcançado Após a parada, a regra é podada para diminui

2 Estratégias: Geral-para-específico Específico-para-geral

Crescimento geral-para-específico de regras

1. Inicia com uma regra r: {} → y Antecedente é um conjunto vazio, ou seja, qualquer

condição implica na classe y

2. Escolhe um par valor-atributo inicial para formar o antecedente

3. Escolhe, gulosamente, o próximo par4. Repete passo 3 até alcançar o critério de

parada (quando o novo par não incrementa a qualidade da regra)

Crescimento de Regras – Geral-para-específico

{} => Mammals

Skin Cover = hair => Mammals

Body Temp = warm-blooded => Mammals

{} => Mammals

Body Temp = warm-blooded, Has Legs=

yes => Mammals

Body Temp = warm-blooded, Gives Birth =

yes => Mammals. . .

Crescimento específico-para-geral

1. Um dos registros positivos é randomicamente selecionado

2. O conjunto de pares valor-atributo formará a semente inicial

3. Remove um dos pares (de modo que a regra cubra mais exemplos positivos)

4. Repete passo 3 até alcançar o critério de parada (quando começar a cobrir exemplos negativos)

Crescimento de Regras – Específico-para-geral

. . .

Body Temperature=warm-blooded, Skin Cover=hair, Gives Birth=yes, Aquatic creature=no, Aerial Creature=no, Has Legs=yes, Hibernates=no

=> Mammals

Body Temperature=warm-blooded, Gives Birth=yes,

Aquatic creature=no, Aerial Creature=no, Has Legs=yes,

Hibernates=no => Mammals

Body Temperature=warm-blooded, Skin Cover=hair, Gives Birth=yes, Aquatic

creature=no, Aerial Creature=no, Has Legs=yes

=> Mammals

Métricas de Avaliação de Regras

Utilizadas para decidir qual par será incluído (removido) da regra

Accuracy não é suficiente Leva em conta a qualidade dos acertos, mas Não considera a cobertura dos registros

Exemplo

Conjunto de dados com 60 exemplos positivos e 100 exemplos negativos

Regra r1: cobre 50 positivos e 5 negativosRegra r2: cobre 2 positivos e 0 negativos

Acurácia de r1 = 90%, Acurácia de r2 = 100%

Outras métricas de avaliação

Método estatístico de avaliação

Medidas Laplace e m-estimate

FOIL’s information gain

Teste estatístico

k = número de classes / fi = exemplos que são cobertos da classe i ei = freqüência esperada para uma regra com predição randômica

R1: e+ = 55 x 60 / 160 = 20.625 / e- = 55 x 100 / 160 = 34.375

R(r1) = 2 x [50 x log2(50/20.625) + 2 x log2(5/ 34.375)] = 99.9

R2: e+ = 2 x 60 / 160 = 0.75 / e- = 2 x 100 / 160 = 1.25

R(r2) = 2 x [2 x log2(2/ 0.75) + 0 x log2(0/ 1.25)] = 5.66

Laplace e m-estimate

n = cobertura da regra k = número total de classes f+ = exemplos positivos cobertos p+ = probabilidade a priori

Levam em conta a cobertura dos dados

Laplace(r1) = 51/57 = 89.47% m-estimate(r1) = (55 + 2 x 0,375) / 57 = 0,97

Laplace(r2) = ¾ = 75% m-estimate(r2) = (2 + 2 x 0,375) / 4 = 0,6875

FOIL’s Information Gain

pi = número de exemplos positivos cobertos pela regra

ni = número de exemplos negativos cobertos pela regra

Considera o ganho obtido pela adição de um par valor-atributo à regra

Regras com maior suporte (maior cobertura dos positivos) terão um maior ganho

Acurácia também influencia ganho

Poda de Regras

São aplicadas as mesmas técnicas utilizadas em árvores de decisão

Se o erro geral diminuir após a simplificação de uma regra, ela é mantida

Normalmente é aplicada após a geração de cada regra

Também é utilizada para evitar sub(super)-especialização

Cobertura Seqüencial

1. Inicia com um conjunto vazio de regras2. Gera uma regra, utilizando a função Learn-

One-Rule3. Adiciona a regra ao conjunto de regras

4. Remove os registros cobertos pela regra gerada

5. Repete 2 e 3 até cobrir todos registros

Eliminação de Instâncias

Evitar a geração de regras repetidas

Evitar super-avaliação de uma regra Caso os exemplo positivos ainda estejam presentes

Evitar sub-avaliação de uma regra Caso os exemplos negativos ainda estejam presentes

Eliminação de Instâncias

Accuracy R1 = 12/15 (80%)

Accuracy R2 = 7/10 (70%)

Accuracy R3= 8/12 (66,7%)

Accuracy R3’= 5/7 (71,42%) após remoção dos exemplos

cobertos por R1

Estudo de caso: RIPPER

Um dos algoritmos mais utilizados para construção de modelos de classificação baseados em regras

Trabalha com um conjunto de validação, para evitar super-especialização

RIPPER: 2 classes

Assume com default a classe mais freqüente

Gera as regras para cobrir a outra classe (minoria)

Exemplos que não engatilham nenhuma regra serão preditos como sendo da classe default

RIPPER: multiclasse

Toma uma classe como default (a classe mais freqüente)

Ordena as classes de forma decrescente Gera, seqüencialmente, as regras para

cobertura de uma classe Para cada classe, trata os registros que pertencem a

ela como exemplos positivos, e todos outros como negativos

Aplica a poda (teste é feito contra um conjunto de validação)

Adiciona as regra e passa para a próxima classe (seguindo a ordem decrescente)

Não gera regras para a classe default

Métodos Indiretos de Extração de Regras

Extrai regras a partir de árvores de decisão

A princípio, todo caminho da raiz até uma folha pode ser visto como um regra Os testes encontrados ao longo do caminho são

transformados em pares valor-atributo A classe da folha é atribuída ao conseqüente da regra

O conjunto de regras gerado será exaustivo, e conterá regras mutuamente exclusivas

Simplificação de Regras

r2’: (Q = Yes) → +r3: (P = Yes) ∧ (R = No) → +

r2: (P = No) ∧ (Q = Yes) → +r3: (P = Yes) ∧ (R = No) → +r5: (P = Yes) ∧ (R = Yes) ∧ (Q = Yes) → +

Conclusão

A expressividade das regras é equivalente a uma árvore de decisões

A performance também é equivalente

Gera modelos facilmente interpretáveis

Recomendado para o tratamento de conjuntos de dados com classes desbalanceadas

Referências

Tan, P-N., Steinbach, M., Kumar, V., “Introduction to Data Mining”. Addison Wesley, 2006

Tan, P-N., Steinbach, M., Kumar, V., “Classification: Alternative Techniques – Lecture Notes”. Disponível em http://www-users.cs.umn.edu/~kumar/dmbook/index.php

Dúvidas?

Fim