Fast Effective Rule Induction
(Willian W. Cohen)
Leandro Zulian Gallina
Sílvia Regina Vargas Gomes
CMP259 – Descoberta de Conhecimento em Bancos de Dados
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
2
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
3
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
4
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
5
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
6
Overfitting
CMP259
7
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
8
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
9
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
10
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 atributovalor 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
11
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
12
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
13
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
14
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
15
Cobertura Sequencial
CMP259
16
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 negativas para prevenir a subestimação da próxima regra gerada
CMP259
17
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
18
Como aprender uma regra?
geral ao específico
CMP259
19
Como aprender uma regra?
específico ao geral
CMP259
20
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
21
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
predominância das classes dentro do dataset.
CMP259
a
22
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
23
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
24
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
25
RIPPER
RIPPER(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 Ruleset
else
add rule to Ruleset
remove examples covered by rule on (Pos, Neg)
endif
endwhile
OptimizeRuleset(Ruleset, PrunePos, PruneNeg)
return Ruleset
end
CMP259
26