Modelos de Preferências
AULA 15
DATA MINING
Sandra de Amo
Preferências
Inteligência Artificial: interesse se concentra


formalismos para especificação de preferências
métodos de dedução de preferências
Banco de Dados: interesse se concentra em


Estender Algebra Relacional com operadores de
preferência
Projetar e implementar linguagens permitindo consultas
do tipo: “Quais os restaurantes que melhor atendem
minhas preferências de localização, facilidades de
estacionamento, menu variado e preço ?”
Problema – Fase 1

Fase da Elicitação das Preferências

Quantitativa: usuário fornece um rank para cada
objeto do banco de dados.
 infactível quando o banco de dados é grande.
 Depende da disponibilidade do usuário

Qualitativa: usuário especifica um conjunto de
“regras” de preferência.
Problema – Fase 2

Fase do Raciocínio – em caso de elicitação
quantitativa



Sistema automático assume certas
premissas extras que devem ser satisfeitas
pelo conceito de “preferência”
Sistema automático deduz a ordem de
preferência entre dois objetos quaisquer
Sistema automático calcula os k-melhores
objetos de acordo com as preferências do
usuário.
Modelos de Preferências

Preferências não-condicionais



Composição Pareto (Ex. Skyline)
Composição com Priorização
Preferências Condicionais (ou Contextuais)



CP-Nets
TCP-Nets
Fórmulas de Preferências Condicionais
Exemplo – Filme(G, D)
Regras de Preferência:
1.
Prefiro comédias a dramas e suspense a comédias.
2.
Prefiro mais os dramas de Bergman do que os de Woody
Allen e mais os dramas de W.A do que os de Hitchcock.
3.
Prefiro mais as comédias de W.A do que as B. E mais as de
B. do que as de Hitchcock.
4.
Quanto a thrillers eu prefiro muito mais os de Hitchcock do
que os de WA e os de B. Entretanto se for preciso escolher
entre um thriller de WA e um de B., prefiro aqueles de B.
5.
Quanto aos filmes de Woody Allen, prefiro mais as
comédias do que os dramas.
Modelo: CP-Net
G
c>d
t >c
Dom(G) = {c,d,t}
Dom(D) = {w, b, h}
D
d: b > w
d: w > h
t: h > w
t: w > b
c: w > b
c: b > h
O que é uma CP-Net ?

Grafo = (V,E)



V : vértices = atributos do banco de dados
E : arestas – existe aresta de A para B se a
preferência entre os valores de B depende de
valores do atributo A.
Tabelas de preferência condicionais
associadas a cada vértice.

A ordem sobre os valores dos atributos é total.
Como uma CP-Net ordena tuplas

Premissas assumidas:

Semântica Ceteris Paribus:



R(A,B,C)
Uma regra F (que só diz respeito aos atributos A e B)
pode comparar dois objetos t1(x1,x2,x3) e
t2(y1,y2,y3), somente se x3 = y3
Ceteris paribus: Todos os valores de atributos que
não aparecem na regra devem ser iguais nos dois
objetos.
Ordem de Preferência é transitiva.
Exemplo 1
(d,b)
(c,w)
(t,h)
(d,w)
(c,b)
(t,w)
(d,h)
(c,h)
(t,b)
É possível comparar (c,w) e (t,b) ?
É possivel comparar (c,h) e (d,b) ?
Exemplo 2
Jantar(Sopa, Vinho)
Dom(Sopa) = {p,l} Dom(Vinho) = {b, t}
1. Prefiro sopa de peixe a sopa de legumes.
2. Caso for sopa de peixe, prefiro vinho branco
para acompanhar.
3. Caso for sopa de legumes, prefiro vinho
tinto.
Exemplo 2 – continuação
S
p>l
(p,b)
(p,t)
(l,t)
W
p: b > t
l: t > b
(l,b)
Neste caso, todas as tuplas são comparáveis.
A CP-Net induz uma única ordem total sobre o
conjunto de todas as tuplas
Exercício
Preferências no vestuário: (Paletó, Calça, Camisa)
Dom(Paletó) = {branco, preto}
Dom(Calça) = {branco, preto}
Dom(Camisa) = {branco,vermelho}
1.
Prefiro paletó e calça pretos do que brancos.
2.
Se o paletó e calça são da mesma cor, então prefiro uma camisa
vermelha mais do que branca.
3.
Se o paletó e calça são de cores diferentes, então neste caso prefiro uma
camisa branca do que uma vermelha.
Pede-se:


Dar a CP-Net correspondente
Determinar a ordem (parcial) induzida pela CP-Net sobre todas as
combinações possiveis de meu vestuário.
CP-Net satisfatível

Uma CP-Net N é satisfatível se e somente se
existe uma ordem TOTAL entre os objetos
que é compatível com a ordem dos valores de
cada domínio de atributo X induzida pelos
valores dos atributos dos pais de X na CP-Net
e supondo a semântica ceteris paribus.
Exemplo
(d,b)
(c,w)
(t,h)
(d,w)
(c,b)
(t,w)
(d,h)
(c,h)
(t,b)
É possível comparar (c,w) e (t,b) ?
É possivel comparar (c,h) e (d,b) ?
Exemplo: CP-Net não satisfatível
A
B
a : b > b’
a’ : b’ > b
c : a > a’
c’ : a’ > a
C
Tuplas em ordem de preferência
(a, b, c)
(a, b’,c)
(a’,b’,c)
b : c > c’
(a’,b,c)
b’ : c’ > c
(a’,b,c’)
(a, b, c’)
(a, b’,c’)
(a, b’,c)
Condição suficiente para ser
satisfatível (consistente)


Grafo é acíclico
Neste caso é possível construir ordem total
compatível com a CP-Net.
Aciclicidade não é necessária para
consistência da CP-Net
a : b > b’
a’: b’ > b
A
B
b : a > a’
b’: a’ > a
a’b
ab’
ab
a’b’
CP-Net é consistente,
embora o grafo seja
cíclico
a : b > b’
a’: b’ > b
A
B
b : a’ > a
b’: a > a’
ab
ab’
a’b
a’b’
CP-Net não é
consistente !
Como construir uma ordem total
quando o grafo é acíclico




Considera-se os atributos sem “pais”.
Ordena-se os valores destes atributos segundo
a ordem total ditada pelas tabelas destes
atributos.
Retira-se estes atributos.
Repete o processo para os atributos restantes,
para cada combinação de valores dos atributos
retirados.
Exemplo
G
D
c>d
t >c
d: b > w
d: w > h
t: h > w
t: w > b
c: w > b
c: b > h
(d,b)
(c,w)
(t,h)
(d,w)
(c,b)
(t,w)
(d,h)
(c,h)
(t,b)
É possível comparar (c,w) e (t,b) ?
É possivel comparar (c,h) e (d,b) ?
Ordem compatível com a CP-Net não é
única
(d,b)
(c,w)
(t,h)
(d,w)
(c,b)
(t,w)
(d,h)
(c,h)
(t,b)
É possível comparar (c,w) e (t,b) ?
É possivel comparar (c,h) e (d,b) ?
Exercicio
Construir duas ordens totais compatíveis com a CP-Net
A a > a’
B a: b > b’
a’: b’> b
C
b: c > c’
b’: c’> c
Discussão (1)
Ordem induzida por uma CP-Net =
Intersecção de todas as ordens totais compatíveis
= ordem parcial


Problemas de se encontrar uma ordem quando
o grafo é cíclico: CP-Net pode ser
inconsistente (não necessariamente, como já
vimos)
Tuplas Preferidas



Mesmo que existam diferentes ordens
compatíveis com a CP-Net, a tupla preferida é
única.
Tupla preferida pode ser construída
independentemente da particular ordem
compatível.
Esta tupla é preferida com relação a qualquer
ordem compatível com a CP-Net.
Algoritmo de construção da tupla
preferida
Seja X = (X1,X2, ..., Xn) os atributos da relação
 Considera-se os atributos sem pais na CP-Net.
 Para estes atributos considera-se seus
melhores valores.
 Retira-se estes atributos da CP-Net e repete-se
o processo para os demais atributos, levandose em conta os valores assumidos pelos
atributos retirados.
Exemplo
G
c>d
t >c
Gênero = thriller
Diretor = Hithcock
D
d: b > w
d: w > h
t: h > w
t: w > b
c: w > b
c: b > h
Tupla preferida = (t,h)
Exercício
Preferências no vestuário: (Paletó, Calça, Camisa)
Dom(Paletó) = {branco, preto}
Dom(Calça) = {branco, preto}
Dom(Camisa) = {branco,vermelho}
1.
Prefiro paletó e calça pretos do que brancos.
2.
Se o paletó e calça são da mesma cor, então prefiro uma camisa
vermelha mais do que branca.
3.
Se o paletó e calça são de cores diferentes, então neste caso prefiro uma
camisa branca do que uma vermelha.
Pede-se:

Qual o vestuário preferido ?
Discussão (2): ordem estrita versus
ordem não-estrita.


Pode-se definir CP-Net sem exigir ordem total
nos domínios dos atributos.
Neste caso, a tupla preferida não é única.
Discussão (3)
Tupla preferida pode existir mesmo se a CP-Net for inconsistente !
c: a > a’
c’: a’> a
abc
A
ab’c
B
ac: b > b’
a’c’:b> b’
a’c: b’> b
ac’:b’> b
ab’c’
C
b: c > c’
b’: c’> c
a’b’c
a’bc
a’b’c’
abc’
a’bc’
Tupla preferida = (a,b,c)