Mineração de Preferências
(a partir de amostras superiores e
inferiores) J.Pei et al. KDD 2008
AULA 18
Data Mining
Profa. Sandra de Amo
Modelo de Preferências



Seja D = {D1,...,Dk} um conjunto de atributos
Uma preferência sobre Di é uma relação de
ordem parcial >i sobre os valores de Di
Composição pareto: > = (>1,...,>k)
O > O’ se e somente se:



Existe i tal que O.i >i O’.i
Para todo j ≠ i : O.j >j O’.j ou O.j = O’.j
Composição pareto é uma preferência sobre
D se for uma ordem parcial
Amostras Superiores e Inferiores
Seja O um conjunto de objetos sobre D = {D1,...,Dk}
S⊆O,Q⊆O
S : Amostras Superiores
s ϵ O não é dominado por nenhum outro objeto de O
Q : Amostras Superiores
q ϵ O é dominado por algum objeto de O
Atributos Determinados e
Indeterminados






D = conjunto dos atributos
D = D+ U DD+ = Conjunto dos atributos determinados
Preferências sobre os valores destes atributos é universal –
partilhada pela maioria dos usuários
Exemplo: Preço do imóvel – o menor preço é sempre o
preferido
D- = Conjunto dos atributos indeterminados

Preferências sobre os valores destes atributos varia para
cada usuário

Exemplo: Área do Imóvel
Satisfying Preference Set (SPS)
•
O que é um SPS(S,Q) ?
• Dados os conjuntos de amostras S e Q, um
SPS(S,Q) é uma order pareto
• > = (>1,…,>k) tal que:
• Todos os objetos de S são superiores com
relação a >
• Todos os objetos de Q são inferiores com
relação a >
Exemplo 1
•
Existência de SPS nem sempre é garantida !
det
indet
S = {O1, O3}
Q = {O2}
Quem pode dominar O2 ?
O3, O4, O5 não podem : pois a1 > a2
a1 > a2 > a3
Logo, somente O1 pode dominar O2
Sugirindo que: c1 > c2
MAS: Se c1 > c2: O3 seria dominado por O1 e portanto não seria superior.
Exemplo 2
•
Pode haver diversos SPS associados a (S,Q)
det
indet
S = {O1}
Q = {O4}
R1 = { {b1 >B b2} , {c1 >C c2} } é uma SPS(S,Q)
R2 = { {b3 >B b2} } é uma SPS(S,Q)
a1 > a2 > a3
Noção de qualidade: minimalidade
R: relação (pares de objetos)
E(R) = fecho transitivo de R
Complexidade de R = |E(R)|
Objetivo: encontrar um SPS com complexidade mínima.
Exercício: Mostrar que
|E(>)| = Πi (|E(>i)| + |Di|) - Πi |Di|
Onde > = composição pareto das ordens locais >i
Problemas Teóricos
Problema 1 (P1 - Existência) – Problema de Decisão
Dado um conjunto O de objetos sobre os atributos D = D+ U D- e S, Q  O,
existe um SPS(S,Q) tal que:
•
S corresponde a amostras superiores
•
Q corresponde a amostras inferiores ?
P1(d) = P1 com d atributos indeterminados
Este problema é NP-Completo.
Prova:
- O problema 3SAT se reduz ao P1(2).
- É possivel mostrar redução de P1(d) para P1(d+1).
Problemas Teóricos
Problema 2 (P2 - Minimalidade) – Problema de
Otimização
Dado um conjunto O de objetos sobre os
atributos D = DU U DI e S, Q  O, encontrar
um SPS(S,Q) tal que:
•
•
•
S corresponde a amostras superiores
Q corresponde a amostras inferiores
SPS(S,Q) é minimal
Proposta: Método Guloso
•
•
Input: conjunto O de objetos sobre os
atributos D = D+ U D- e S, Q  O
Output: SPS satisfazendo S e Q
isto é:
elementos de S são superiores
elementos de Q são inferiores
Dominância Parcial
•
•
•
Seja D = D+ U D>D = ordem pareto sobre D
Se O1 >D+ O2 então
•
O1 >D O2 depende somente das preferências sobre os não-determinados D-
-
O1 domina parcialmente O2 se O1 >D+ O2
-
Se O1 domina O2 então O1 domina parcialmente O2
- Se O1 não domina parcialmente O2 então O1 não domina O2
Exemplo : O1 = (Preço = 250, Área = 100, Local = Centro)
O2 = (Preço = 300, Área = 150, Local = Bairro Martins)
Sem mesmo conhecer as preferências sobre os atr. Indeterminados Area e
Local pode-se afirmar que O2 não domina O1, pois não domina
parcialmente O2.
Descobrindo Preferências para
Satisfazer as Amostras Inferiores
Passo 1: Podagem de Q
Elimina amostras que não trazem informação
importante sobre as preferências nos atributos
indeterminados.
Para cada q ϵ Q:
P(q) = objetos de O que dominam parcialmente q



Se existe objeto p ϵ P(q) tal que p.D- = p.D- (coincide em todos os
atributos indeterminados) então é inferior independentemente das
preferências sobre Dq pode ser eliminado de Q
q é dito trivialmente inferior.
Descobrindo Preferências para
Satisfazer as Amostras Inferiores
Passo 2: Construção da tabela das
Condições de Preferências
-
Para cada q ϵ Q:
-
-
-
-
Considera-se todos os objetos de O que podem dominar q nos atributos
não determinados = P(q)
Sabe-se que tais objetos existem: q é inferior, e q não é trivialmente
inferior
Para cada objeto p ϵ P(q): constrói-se as condições que devem ser
satisfeitas para q ser dominado por p
Notação: Cq(p) = condições que devem ser satisfeitas para q ser
dominado por p.
det
Não-det
EXEMPLO
- O10 é parcialmente
dominado por O4
- O10 e O4 coincidem
em D3 e D4
Logo: O10 é removido
removido
Método Exaustivo para Satisfazer Q

Para cada q ϵ Q





Seleciona um objeto p de P(q)
Constrói-se a ordem imposta pelas condições
Cq(p).
Calcula-se o tamanho de cada uma destas
ordens (cardinalidade)
Pega a ordem com a menor cardinalidade.
Método exaustivo é exponencial no número
de objetos inferiores
Algoritmo Baseado em Termos –
Esquema Geral
Para cada atributo não-determinado:
 Adiciona-se iterativamente termos t : a > b até que todas as
amostras inferiores sejam satisfeitas.
 Os termos t escolhidos para serem inseridos são avaliados segundo
2 critérios:




Complexidade do Incremento CI(t): mede o quanto a inserção do termo
vai aumentar a cardinalidade da relação de preferência pareto final.
Cobertura das Amostras Cov(t): quantidade de amostras inferiores que
ficam satisfeitas após a inserção do termo t.
Score(t) = Cov(t)/CI(t)
Termos com maior score são os escolhidos.
Basta que para
um p todas as
Condições de Cq(p)
sejam satisfeitas
para q ser removido
Como calcular o Incremento CI(t)
Exemplo
R = {>3, >4} |D3| = 5, |D4| = 3
Iteração k : R = { { a1 >3 a2}, ø }
|E(R)| = (1+5)*3 – 5*3 = 3
Iteração k+1: a3 >3 a1 é selecionado
|E(R)| = (3+5)*3 – 5*3 = 9
CI(t) = 9 – 3 = 6
Como calcular a cobertura Cov(t)


Cobertura do termo t com respeito a uma condição Cq(p)
 Cov(t, Cq(p)) = 1/|Cq(p)| se t ϵ Cq(p)
 Cov(t, Cq(p)) = 0 se t  Cq(p)
Exemplo: Considere Co2(O1) = (a3 >3 a2)  (b3 >4 b1)
t = b3 >4 b1
Cov(t, Co2(O1)) = ½


Considera-se também a cobertura do termo t com respeito aos
termos implicados
Cobertura do termo t com respeito a uma amostra q


Cov(t,q) = max {Cov(t’, Cq(p)}, t’ ϵ Imp(t), p ϵ P(q)
Cobertura do termo t com respeito ao conjunto de amostras Q

Cov(t) = Σq Cov(t,q)
Exemplo de aplicação do Algoritmo
Cálculo do score de t = a1 >3 a2
Cov(t,O2) = 0, Cov(t,O5) = ½,
Cov(t,O7) = ½, Cov(t,O8) = 0
Logo: Cov(t) = ½ + ½ = 1
Complexidade antes = 5.3 – 5.3 = 0
Complexidade depois = (1+5).3 – 5.3 = 3
Logo: CI(t) = 3

Score (t) = 1/3
Após a seleção de
b3 >3 b1 na 1a iteração:
• Condição CO8(O6) é satisfeita.
• Logo O8 é removido de Q
• a4>3 a5 não aparece em
nenhuma condição restante,
• a4>3 a5 é retirada da lista
de termos a serem testados na
Iteração 2
Resultado Final: R = { {a1 >3 a2}, {b1 >4 b2, b3 >4 b1, b3 >4 b2} } , |E(R)| = 21
Discussão


Muitas vezes os SPS minimos não são
atingidos, o SPS retornado não é otimal.
Exemplo: que CI(b1>4 b2) = 12 (muito
grande)
Algoritmo baseado em Condição
Ao invés de calcularmos o score de um termo, estamos interessados em
calcular o score de uma condição inteira Cq(p)
Score(Cq(p)) = Cov(Cq(p)) / CI(Cq(p))
Cov(Cq(p)) = Σ Cov(t), t ϵ Cq(p)
Exemplo de Aplicação do Algoritmo
Resultado Final:
R = { {a3 >3 a2, a4 >3 a2}, {b3 >4 b1, b3 >4 b2} }
|E(R)| = 20
Como satisfazer as amostras Superiores


Termos (ou condições) não satisfatórios: violam alguma amostra
superior.
Exemplo:




Suponha que O3 é superior
se CO5(O1) = (a3 >3 a2)  (b3 >4 b2) escolhida pelo algoritmo
Neste caso: O1 dominaria O3, violando a condição de superioridade de
O3.
Amostras superiores são utilizadas como verificadores.



Ao final de cada iteração, um termo t é selecionado (com o melhor
score)
Antes de inserí-lo no resultado, testa-se se ele não viola uma amostra
superior.
Se for o caso, o termo é removido da lista e outro termo com score
imediatemente abaixo é selecionado.
Resultados Experimentais sobre dados
Reais



Dados sobre jogos da NBA (www.nba.com)
Dados contém informações estatisticas sobre 3924
jogadores de 1946 a 2006.
Atributos






Média de pontos por jogo (PTS)
Média de “tomadas de bola” (STL)
Média de “bloqueios” (BLK)
Média de “rebotes” (REB)
Média de “passes” (AST)
Preferências do senso comum: maiores valores para
cada atributo.
Testes com o algoritmo guloso (2 versões)






REB e AST foram utilizados como indeterminados nos testes
PTS, STL, BLK : determinados
Deseja-se avaliar se as preferências mineradas sobre REB e AST
são coerentes com o senso comum.
Medida de avaliação: pct = Ra/Rt
 Rt = quantidade de termos minerados
 Ra = termos minerados que são coerentes com o senso comum
 pct = acurácia do algoritmo
REB tem 23 valores distintos, AST tem 12 valores distintos
Amostras superiores e inferiores são obtidas através de escolhas
reais de usuários.
Resultados