Aprendizagem de regras proposicionais
de classificação e associação
TAIAS 2
Ivan Teixeira
João Batista
Árvores de Decisão
Estratégia de dividir para conquistar
Tempo?
Não
Que dia?
Sim
Seg
Sim
Hora?
Sim
Não
Sim
Regras de classificação
ANTECEDENTES
CONSEQUÊNCIA
•Cada antecedente: teste valor de um atributo da
instância para classificar.
•Conseqüência: classificação da instância.
Ex: IF tempo = sol AND dia = Dom THEN racha
(T = sol)  (D = Dom) => racha
Regras de Classificação vs. Árvores
Regras de classificação podem ser convertidas em
árvores de decisão e vice-versa
 Porém:

• a conversão é em geral não trivial
• dependendo da estrutura do espaço de instâncias, regras ou
árvores são mais concisas ou eficientes
Regras são compactas
 Regras são em geral altamente modulares (mas
raramente são completamente modulares)

Vantagens de Árvores de Decisão
Exemplo de conversão árvore -> regras
X > 1.2
não
b
IF x >1.2 AND y > 2.6 THEN
class = a
sim
If x < 1.2 then class = b
Y > 2.6
não sim
b
If x > 1.2 and y < 2.6 then
class = b
a
• Sem mecanismo de interpretação preciso regras podem ser ambíguas
• Instâncias podem “passar através” de conjunto de regras não
sistematicamente “fechado”
Vantagens de Regras de Classificação
Exemplo de conversão regra/árvore
If x=1 and y=1
x
1
2
y
1 2
3
then class = a
a
z
If z=1 and w=1
1 2
3
then class = b
w
b
b
1
3
2
a
b
b
•Árvores são redundantes e não incrementais
•Árvores não são ambíguas e não falham em
classificar
3
Hipótese do Mundo fechado

Classificação de alvo booleano em um mundo fechado.
IF tempo = sol AND dia = Dom THEN racha
IF tempo = sol AND dia = Sab THEN racha
Construindo regras

Algoritmo de Cobertura:
selecionar uma classe e
procurar uma forma de
cobrir todas as instâncias.



y
1
b b a aa a
b bb a a
b
b b a b
1.2
x
Passo inicial
• if ? then class = a
Primeiro passo
• if x > 1.2 then class = a
Essa regra cobre, tanto os bs
quanto os as
Segundo passo
• if x > 1.2 e y > 1 then class = a
Essa regra cobre somente a’s.
Algoritmo de cobertura
Para cada classe C
Inicialize E como sendo a instância do conjunto
Enquanto E contém instâncias na classe C
Crie uma regra R sem antecedentes que prediz a classe C
Enquanto R não for perfeita e houver mais atributos
Para cada atributo A não mencionado em R e cada valor V
Considere a adição de A=V nos antecedentes de R
Selecione A e V que maximize Heuristic-function()
Adicione A=V nos antecedentes de R
Remova as instâncias cobertas por R de E
Função heurística
Correctness based Heuristic
MAXIMIZAR
Número dessa instâncias
que pertencem à classe da regra
Número de instâncias que
disparam a regra
p
t
Information based Heuristic
MAXIMIZAR
p
P

p log  log 
t
T

Calcula o ganho de informação levando
em conta o número de instâncias positivas
Comparando os critérios
Os dois critério classificam corretamente todas as
instâncias.
 Correctness Based

• Privilegia regras 100% corretas mesmo com cobertura baixa
• Trata primeiro os casos especiais

Information Based
• Privilegia regras de alta cobertura mesmo com precisão baixa
• Trata primeiro os casos gerais
Exemplo
Atributo-valor
cbh
ibh
age = young
2/8
0.35
age = pre-presbyopic
1/8
-0.12
age = presbyopic
1/8
-0.12
spectacle prescription = myope
3/12
0.53
spectacle prescription = hypermetrope
1/12
-0.3
astigmatism = no
0/12
0.0
astigmatism = yes
4/12
1.2
tear production rate= reduced
0/12
0.0
tear production rate = normal
4/12
1.2
Regras boas e regras ruins
As heurísticas exibidas anteriormente causam
overfit se usados isoladamente
 Gerar regras que não são perfeitas no conjunto de
treinamento ...
 ... mas que são melhores na generalização do
problema.
 Solução: contrabalançar a precisão de uma regra nos
exemplos e a qualidade de uma regra no problema

Qualidade de uma regra
T
t
P
p
Probabilidade de uma regra aleatória ter um p igual a
um valor qualquer i:
P[i de t estarem em P] =
 p  T  P 
 

 i  t  i 
T 
 
t 
Qualidade de uma regra
A qualidade de uma regra é a probabilidade de uma
regra gerada aleatoriamente ter um desempenho
melhor ou igual à regra.
 Para uma regra R:

min(t , P )  p  T  P 
min(t , P )
M(R) =

i p
P[i de t estarem em P] =

i p
 

 i  t  i 
T 
 
t 
Exemplo
IF astigmatism = yes AND tear production = normal
THEN recommendation = hard
• p/t = 4/6
• P/T = 4/24
 4  24  4 
 

4
4  6  4 

m( R)   P ri,6,4,24 
 0,0014 0,14%
 24
i 4
 
6
Ou seja, apenas 0,14% de chance de uma regra gerada
aleatoriamente ser melhor do que esta regra.
Gerando boas regras
1. Gerar regras 100% precisas ou perfeitas
• IF A=a AND B=b AND C=c THEN D=d

Precisão = 100%, qualidade = baixa
2. Os testes do antecedente da regra são tirados
gradualmente para tentar melhorar a qualidade da
regra.
• IF A = a AND B=b THEN D=d

precisão < 100%, qualidade = alta
Dessa forma as regras são melhores na generalização do
problema.
Listas de regras
Lista ordenada de decisão formada por regras que
são interpretadas seqüencialmente
 A primeira regra disparada leva a instância
 Algoritmo de geração de listas de regras:

Até que E esteja vazio
para cada classe C contida em E
-gere uma regra R perfeita para a classe C pelo cobertura
-calcule a medida de valor m(R) para a regra e para a
regra m(R-) com a condição final retirada
-enquanto m(R)<m(R-) retire a condição final da regra e
repita o passo anterior
-das regras geradas escolha a que tem o menor m(R)
retire de E as instâncias cobertas por R
continue
Conjunto de teste
A medida de probabilidade da qualidade de uma
regra e uma forma eficiente de comparar a
qualidade entre duas regras.
 Mas não tem muito valor estatístico porque e
aplicada sobre os mesmo dados usados no
crescimento da regra.
 Solução (Reduced Error-Prunning):

• Dividir os dados de forma que as medida sobre a qualidade
de uma regra sejam feitas em uma conjunto separado
Usando um conjunto de testes
CONJUNTO DE CRESCIMENTO
• Usado para construir as regras
CONJUNTO DE PODA
• Usado para verificar a qualidade da poda
Problemas ...
• Como separar os conjuntos.
• Instâncias chaves podem ser alocadas para o
conjunto de poda.
Conjuntos

Variando o conjunto de poda é possível evitar perda
de informação.
Usando um conjunto de testes
Inicialize E com o conjunto de instancias
Divida E em Crescimento S1 e Poda S2 em uma razão 2:1
Para cada classe C para qual S1 e S2 tenham instancia
- Use o algoritmo de cobertura para para criar uma
regra perfeita para a classe C
- Calcule w(R) para a regra em S2, e para a regra
com o ultimo teste retirado w(R-)
- Enquanto w(R-) > w(R-), remova o ultimo teste e
repita o passo anterior
Das regras geradas selecione a que tiver o maior w(R)
Remova as instancias de E cobertas pela nova regra
Continue
Possibilidades:
•W(R) = qualidade da regra
•W(R) = [p+(N - n)] / T
Indução de regras com árvores de decisão




Árvores contém regras.
Uma árvore de decisão parcial é criada para extrair
apenas uma regra.
Combina dividir-conquistar das árvores de decisão e
separar-conquistar do algoritmo de cobertura.
É mais eficiente sobre dados com ruído.
Gerando Árvores Parciais
Arvore-Parcial(S)
Escolher o melhor teste para dividir a arvore em nos
Ordenar os nos em ordem crescente de entropia
Enquanto ( Houver um no X que foi expandido e
Todos os nos expandidos ate agora são folhas)
- Arvore-Parcial(X)
Se (todos os nos expandidos são folhas e erro estimado da subarvore
gerada > erro estimado do no)
-desfazer a expansao transformar o no em folha
Retornar a regra representada pela folha com maior cobertura
Árvores parciais

São árvores incompletas que contém galhos para
subárvores inexploradas.
Prunning
4
6
Prunning
8
A substituição
não
Nova regra
representa mais o
ganho em performance
Regras com exceção
É uma forma natural de encarar as regras, afinal
“toda regra tem um exceção”.
 Uma regra geral é construída ...
 Essa regra tem exceções ...
 E essas exceções tem suas exceções.
 É mais fácil de entender as regras geradas e é mais
natural para os humanos.

Regras com exceção
As regras e suas exceções

3 classes com 50 instâncias de cada: 150 instâncias
Iris setosa
50/150
P Length>2.45
P Width<1.75
P Length<5.35
Iris vesicolor
49/52
P Length>4.95
P Width> 1.55
Iris Virginica
2/2
S Length< 4.95
S Width>2.45
Iris Virginica
1/1
P Length>3.35
Iris virginica
47/48
P Length<4.85
S Length<5.95
Iris Vesicolor
1/1
Regras com exceção
Regra 1
Regra 1.1
Regra 1.2
Aprendizagem de regras proposicionais com
algoritmo de cobertura: características


Tarefas: classificação e
descrição de associação
Ambiente pode ser:
•
•
•
•



não acessível, não episódico 
contínuo, ruidoso

estático, grande

não relacional, não diverso
Supervisionado:
• E+ ou E+  E-


Treino antes da ação

Não incremental
Não iterativo
Top-down
Guloso
Global
Não aproveita conhecimento
prévio para podar busca da
hipótese
Não aproxima qualquer função
• apenas hiperplanos
Regras de associação
vs. Regras de classificação

Conseqüência:
• qualquer atributo no lugar de apenas um atributo destacado
para classificação
• vários atributos no lugar de um

Uso diferente:
• Apenas descreve regularidade nos dados
• ex: IF racha = sim AND dia = Dom
•
THEN tempo = sol AND hora = 16

Construção:
• Podem usar algoritmo de cobertura
• Não é viável na prática devido à necessidade de considerar
todas as combinações, de todos os valores possíveis, de
todos atributos
Gerando regras de associação
umidade = normal
umidade = alta
umidade = baixa
IF
IF
IF
IF
IF
IF
IF
...
? THEN umidade
? THEN umidade
? THEN umidade
? THEN umidade
? THEN umidade
? THEN umidade
? THEN umidade
tempo = sol
tempo = chuva
tempo = nublado
= normal
= normal
= normal
= normal
= normal
= normal
= normal
AND
AND
AND
AND
AND
AND
vento = sim
vento = não
vento = médio
tempo = sol
tempo = sol AND ventando = sim
tempo = sol AND ventando = não
tempo = chuva
tempo = chuva AND ventando = sim
tempo = chuva AND ventando = não
 a  i  3 1  3  2  3 3
   v     3     3     3  63

i 1  i 
 1
 2
 3
a
Algoritmo específico para construir regras de
associação

Idéia:
• focalizar em regras que tenham alta cobertura
• inicialmente, abstrair o conceito de regra processando pares
de atributos-valores (itens)
2 fases:
 A/ iteração:

1. busca itens com cobertura mínima predefinida
2. busca pares de itens construindo-os a partir dos itens do passo
precedente
...
N. busca N tuplas de itens construindo-os a partir dos N-1 tuplas
do passo precedente
...

B/ construir regras a partir do N tuplas de itens
Itens
Um par
Tempo=sol(5)
Dois pares
Três pares
Tempo = sol (2)
Tempo = sol(2)
Temper. = normal Temper. = hot
Umidade = alta
Temper. = frio(5)
Tempo = sol(3)
Umidade = alta
Tempo=sol(2)
Umidade=alta
Vento=não
Tempo=chuva(5)
Tempo=sol(2)
Umiade=normal
Tempo=sol(2)
Umidade=normal
Jogar=sim
Quatro pares
Tempo = sol(2)
Temper. = hot
Umidade = alta
Jogar = no
Tempr.=frio (2)
Umidade=norma
Vento=não
Jogar=sim
Tempo=sol(2)
Umidade=alta
Vento=não
Jogar=não
Gerando regras dos itens gerados

Produzir regras precisas a partir de um item
O item com três pares:
umidade = normal , vento = não e jogar = sim
Gera as regras:
IF umidade = normal AND vento = não THEN jogar = sim
IF umidade = normal AND jogar = sim THEN vento = não
IF vento = não AND jogar = sim THEN umidade = normal
IF umidade = normal THEN vento = não AND jogar = sim
IF vento = não THEN umidade = normal AND jogar = sim
IF jogar = sim THEN vento = não AND umidade = normal
IF ? THEN vento = não AND umidade = normal AND jogar = sim
4/4
4/6
4/6
4/7
4/8
4/9
4/12
Diminuindo o processamento
Mesmo restringindo o domínio o custo para gerar
regras de associação é alto.
 Uma alternativa para diminuir o processamento é:

• iniciar o processamento atribuindo um valor alto para a
cobertura mínima
• diminuir esse valor em cada interação até que se tenha a
quantidade de regras desejadas.
Perguntas ?
Hora?
Fim
Pergunta?
Sim
Fim.
Quem?
Responde
Fim
Bibliografia



Artificial Intelligence a Modern Approach, S. Russell & P.
Norvig, 1995, Prentice-Hall
Machine Learning, T. Mitchell, 1997, McGraw-Hill,
Data Mining: Practical Machine Learning Tools and Techniques
with Java Implementations, I.H. Witten
& E. Frank, 1999, Morgan Kaufmann,