CMP259 1

Fast Effective Rule Induction(Willian W. Cohen)

Leandro Zulian GallinaSílvia Regina Vargas Gomes

CMP259 – Descoberta de Conhecimento em Bancos de Dados

CMP259 2

Objetivos do artigo

• Trabalhos anteriores– Nomeadamente, IREP

• Experimentos com o IREP– Aqui a gente meio que só cita e ignora

• Melhorias para o IREP– IREP*– RIPPER-k

CMP259 3

Conceitos de Classificação

• Tarefa de aprender um modelo de classificação– Atribui a cada conjunto de atributos um valor de

uma classe pré-definida

• O modelo deve:– Ser adequado aos dados de entrada (training set)– Predizer corretamente as classes de dados não

vistos antes (test set)

CMP259 4

Construindo árvores de decisão

• Número de árvores possíveis: exponencial• Método da força bruta impraticável• Algoritmos para induzir árvore de decisão– Mesmo que não seja a ótima

CMP259 5

Construindo árvores de decisão

• Algoritmos:– Hunt– ID3– C4.5– CART

• Comum: estratégia gulosa– Crescer a árvore de decisão tomando decisões

localmente ótimas

CMP259 6

Pruning (Poda)

• Árvores de decisão muito grandes => OVERFITTING (Super-especialização)

• Caminhos muito específicos são desnecessários

• Poda remove caminhos extras

CMP259 7

Overfitting

CMP259 8

Tipos de Poda

• Pré-poda:– Faz a poda no momento em que as regras são

geradas– Estabelece uma condição de parada quando uma

regra é adicionada sem que haja ganho

• Pós-poda– Faz a poda somente quando toda a árvore de

decisão já foi gerada

CMP259 9

Pruning (Poda)

• Pré-poda– Vantagem: Mais rápida;– Desvantagem: Difícil determinar condição de parada (pode

gerar underfitting/manter overfitting)

• Pós-poda– Vantagem: Mais precisa;– Desvantagem: O conjunto de treinamento precisa ser

dividido em growing set e pruning set– Apenas os dados do growing set são utilizáveis para

aprender as regras

CMP259 10

REP (Reduced Error Pruning)

• Algoritmo que usa pós-poda• São aplicados operadores de poda• Poda termina quando aplicação da poda faz

com que aumente o erro no pruning set• Desvantagem: tempo de processamento de

até O(n4)

CMP259 11

Classificação baseada em regras

• O que são regras de classificação?– São regras no formato IF-THEN– A parte IF forma uma condição sobre o conjunto de

dados– A parte THEN contém a classe a ser atribuída– Condições proposicionais com comparações atributo-

valor e cláusulas de Horn de primeira ordem.• Por que regras?– Porque as hipóteses são melhor entendidas e melhor

lidas por conjuntos de regras IF-THEN

CMP259 12

Classificação baseada em regras

• Exemplo de regra:– (Gives Birth = no) and (Aerial Creature = yes)

Birds• Métricas de avaliação de regras:– Ni: número de regras cobertas pela regra i– ni: número de regras corretamente classificadas

pela regra i.– cobertura: Ni / |total de tuplas no dataset|– acurácia: ni / Ni

CMP259 13

Classificação baseada em regras

• Conflito de resolução:– Uma instância “ativa” mais de uma regra.– Regras ordenadas: maior prioridade à regra com o

requisito mais forte (ex.: a regra possui maior quantidade de atributos)

– Regras desordenadas: a decisão da regra que vai ser atribuída para classificar um registro é feita por votação. A votação geralmente envolve a acurácia da regra.

CMP259 14

Abordagens para classificação

• Métodos diretos– As regras são aprendidas diretamente do dataset• IREP, RIPPER

• Métodos indiretos– A árvore de decisão é construída e, após, as regras

são derivadas• C4.5rules

CMP259 15

Cobertura Sequencial

• Seja E o conjunto de registros de treinamento• Repita:– Aprender uma regra (LearnOneRule) com alta

acurácia e qualquer cobertura– Remover os registros cobertos pela regra (todos!)– Adicionar a regra ao final da lista de regras

• Até que todos os registros sejam cobertos• Inserir a regra padrão ao final da lista de

regras ({} class)

CMP259 16

Cobertura Sequencial

CMP259 17

Cobertura Sequencial

• Eliminação de instâncias– Eliminar instâncias para que a nova regra gerada

não seja igual a anterior– Eliminar instâncias positivas para garantir que a

próxima regra é diferente– Eliminar instâncias negati-vas para prevenir a subesti-mação da próxima regra ge-rada

CMP259 18

Como aprender uma regra? (LearnOneRule)

• Geral ao específico– Começar com a hipótese mais geral e ir refinando

de acordo com um parâmetro (acurácia)

• Específico ao geral– Começar com a regra mais específica e ir

generalizando passo a passo.

• Estratégia “Rule-growing”

CMP259 19

Como aprender uma regra?

geral ao específico

CMP259 20

Como aprender uma regra?

específico ao geral

CMP259 21

Avaliação da regra

• FOIL’s information gain:– usa o suporte da regra (número de positivos

cobertos pela regra – pi)

– prefere regras com alto suporte e alta acurácia– r: A + cobre p0 exemplos positivos e n0

negativos. r’: A and B + cobre p1 exemplos positivos e n1 negativos

– FOIL = p1 x (log2(p1/(p1+n1)) / log2(p0/(p0+n0)))

CMP259 22

RIPPER

• 2 classes: escolher uma classe para ser a positiva. A outra é negativa e padrão.

• k classes: escolher a classe positiva da vez e todas as outras classes são tratadas como negativas– ordenar as classes de acordo com a

predominância das classes dentro do dataset.

CMP259 23

RIPPER

• Aprendendo uma regra:– Começar da regra vazia (geral a específica)– Adicionar condições desde que elas melhorem o

information gain– Parar quando a regra não cobrir mais exemplos negativos– Podar a regra imediatamente usando o reduced error

pruning• medida de poda: v = (p-n)/(p+n)

– Método da poda: deletar os condicionais de forma a melhorar v.

CMP259 24

RIPPER

• Construindo o conjunto de regras– Usar o algoritmo de cobertura sequencial• Achar a melhor regra que cobre um conjunto de

registros positivos• Eliminar as instâncias do conjunto de dados

– A cada nova regra aprendida, verificar se o REP ultrapassa 0.5• Se sim, retornar o conjunto de regras• Caso contrário, adicionar a regra ao conjunto de regras

e remover as instâncias cobertas pela regra do dataset

CMP259 25

RIPPER

• Otimizando o conjunto de regras– Para cada regra r no conjunto de regras R• Considerar duas novas regras:

– r’: aprende uma nova regra do zero usando o pruning set– r*: adiciona condicionais para melhorar a regra r usando

também o pruning set

• Comparar as três regras e escolher a que minimiza o valor de acordo com o MDL

CMP259 26

RIPPERRIPPER(Pos,Neg)begin

Ruleset := {}while Pos {}

split (Pos, Neg) into (GrowPos, GrowNeg) and (PrunePos, PruneNeg)

Rule := GrowRule(GrowPos,GrowNeg)Rule := PruneRule(Rule, PrunePos, PruneNeg)if REP of rule on (PrunePos, PruneNeg) > 0.5

return Rulesetelse

add rule to Rulesetremove examples covered by rule on (Pos, Neg)

endifendwhileOptimizeRuleset(Ruleset, PrunePos, PruneNeg)return Ruleset

end