Fórmulas de Preferências
Condicionais
[Wilson 2004]
AULA 15
Data Mining
Sandra de Amo
Fórmulas de Preferência Condicional
R (Y1,…,Yn,….,X,…)
 Conditional Preference Rules (cp-rules)
φ : Y1 = a1 ˄ … ˄ Yn = an
Conditions over Attributes Y1,…,Yn
X = x > X = x’
[Z]
Preference over Attribute X
 Conditional Preference Theory = a finite set of cp-rules
Atributos que são excluídos da exigência Ceteris Paribus
Exemplo
φ : D = Hitchcock
G = thriller > G = drama
ρ : Year = 1960
D = Hitchcock > D = D.Lynch [ Actor ]
[ Actor ]
Toda CP-Net é uma teoria de
preferência condicional
G
D
c>d
t >c
d: b > w
d: w > h
t: h > w
t: w > b
c: w > b
c: b > h
G= c > G = d
G=t>G=c
[ø]
[ø]
G = d  D=b > D=w
G = d  D=w > D=h
G = t  D=h > D=w
G = t  D=w > D=b
G = c  D=w > D=b
G = c  D=b > D=h
[ø]
[ø]
[ø]
[ø]
[ø]
[ø]
Ordem de Preferência induzida por
uma Teoria de Pref. Condicional
 Cada cp-rule φ induz uma ordem de preferência >φ
Usa a semântica ceteris paribus para os atributos que não estão em
Z U Y e que são diferentes de X
 Exemplo: BD(Category, Director, Year, Actor)
φ : Category = comedy
Director = F. Capra >Director = Hitchcock [Year]
O1 = (Cat=comedy, Dir = F.Capra, Year = 1960, Actor = J.Stewart)
O2 = (Cat=comedy, Dir = Hitchcock,Year = 1954, Actor = J.Stewart)
O1 >φ O2
Ceteris paribus
Ordem de Preferência
 Uma cp-theoria Ψ induz uma ordem de preferência >Ψ
Para cada fórmula φ de Ψ considera-se a ordem induzida > φ
Considera-se a união de todas estas ordens U>φ,
para φ em Ψ
A ordem de preferência induzida pela teoria =
fecho transitivo de U>φ, para φ em Ψ
>Ψ = fecho transitivo de U>φ, para φ em Ψ
Ordem de Preferência
Teoria Ψ = { φ , ρ }
 Considera-se todos os pares de tuplas que podese ordenar diretamente utilizando a regra φ
 Considera-se todos os pares de tuplas que podese ordenar diretamente utilizando a regra ρ
 Considera-se a união destes dois conjuntos de
pares de tuplas.
 Inclui-se neste conjunto todos os pares de tuplas
obtidos por transitividade.
Ordem de Preferência
R(A,B,C)
Tuplas ordenadas diretamente
pela regra φ
abc
Tuplas ordenadas diretamente
pela regra ρ
ab’c
ab’c’
a’b’c
a’bc
a’b’c’
abc’
Primeira iteração da transitividade
Segunda iteração da transitividade
a’bc’
Exemplo
Teoria Ψ = { φ , ρ }
φ : Dir = Hitchcock
ρ : Year = 1960
Cat. = thriller > Cat. = drama
[ Actor ]
Dir. = Hitchcock > Dir. = D.Lynch [ Actor ]
O1 = (Cat=thriller, Dir = Hitchcock, Year = 1960, Actor = J.Stewart)
O2 = (Cat=drama, Dir = Hitchcock, Year = 1960, Actor = P. Newman)
O3 = (Cat=drama, Dir = D.Lynch, Year = 1960, Actor = A. Hopkins)
O1 > φ O2
O1 >Ψ O3
O2 > ρ O3
Grafo de Dependência
Grafo associado a uma teoria Ψ
Vértices: atributos que aparecem em Ψ
 Arcos: (Y,X) onde Y aparece do lado
esquerdo da regra e X do lado direito da
regra na parte da ordenação

Exemplo
φ1 : Dir = Lynch
[Y]
[C]
φ3 : Year = 1954
Cat. = thriller > Cat. = drama
Dir. = Hitchcock > Dir. = D.Lynch
Dir. = D.Lynch > Dir. = Hitchcock
φ4 : Cat = drama
Dir = D.Lynch > Dir = Hitchcock
[Y]
φ2 : Year = 1960
D
Y
C
Ordens Locais

ordem sobre o domínio dos atributos:
 Sejam
A1,…,An = atributos que aparecem na
parte esquerda das regras
 Sejam B1, …, Bk = atributos que aparecem na
parte direita das regras (parte da ordenação)
 Cada tupla t sobre os atributos (A1,…,An)
determina uma ordem local sobre o domínio do
atributo Bj, ( 1 ≤ j ≤ k )
Consistência Local

Uma teoria é localmente consistente se as
ordens locais produzidas em cada atributo
do lado direito são irreflexivas.
Teoria Consistente

A cp-teoria Ψ é consistente se >Ψ é irreflexiva
Não se pode deduzir o1 >Ψ o2 e o2 >Ψ o1

Teste de Consistência (Wilson 2004)
Ψ é consistente se
seu grafo de dependência é acíclio e
Ψ é localmente consistente
Exemplo
φ1 : Dir = Lynch
Cat = thriller > Cat = drama
[Y]
φ2 : Year = 1960
[C]
φ3 : Year = 1954
Dir = Hitchcock > Dir = D.Lynch
Dir = Hitchcock > Dir = Lynch
φ4 : Cat = drama
Dir = D.Lynch > Dir = Hitchcock
[Y]
D
Attributes = Y, D, C
Y
C
Database:
O1 = (1960, Lynch, thriller)
O2 = (1960, Hitch, drama)
O3 = (1954, Lynch, drama)
O2 > O1 > O3 > O2
Dom(Y) = {1960, 1954}
Dom(D) = {Hitch, Lynch}
Dom(C) = {t, d}
O1: hitch>lynch
dom(D)
thriller>drama
dom(C)
O2: hitch >lynch
dom(D)
O3: hitch > lynch
dom(D)
Ordem local sobre dom(D)
não é irreflexiva !
Tuplas Preferidas
Lista os atributos (X1,…,Xn) na ordem
compatível com o grafo de dependência
graph(Ψ)
 Pega o melhor valor x1 de dom(X1)
 Pega o melhor valor x2 de dom(X2) conditionado
a x1
 …
Observação:
como a ordem não é total, podem haver
diversas tuplas preferidas

Exemplo
φ1 : Dir = Hitchcock
φ2 : Year = 1960
Cat. = thriller > Cat. = drama
Dir. = Hitchcock > Dir. = D.Lynch
φ3 : Year = 1954
Dir. = D.Lynch > Dir. = Hitchcock
φ3 : Year = 1954
Cat = drama > Cat = comedy
D
Y>D>C
Y
C
Melhor valor para Y : qualquer um
Y = 1960
Best D = Hitch
D = Hitch
Best C = thriller
O = (1960, Hitch, thriller) é uma tupla
preferida.
Y = 1954
Best D = Lynch
D = Lynch
Best C = drama
O = (1954, Lynch, drama)
é outra tupla preferida