Mineração de Preferências

(a partir de amostras superiores e inferiores)

J.Pei et al. KDD 2008AULA 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 Superioress ϵ O não é dominado por nenhum outro objeto de O

Q : Amostras Superioresq ϵ O é dominado por algum objeto de O

Atributos Determinados e Indeterminados D = conjunto dos atributos D = D+ U D- D+ = 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 !

S = {O1, O3} Q = {O2}

Quem pode dominar O2 ?

O3, O4, O5 não podem : pois a1 > a2

Logo, somente O1 pode dominar O2Sugirindo que: c1 > c2

det indet

a1 > a2 > a3

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

a1 > a2 > a3

S = {O1} Q = {O4}

R1 = { {b1 >B b2} , {c1 >C c2} } é uma SPS(S,Q)

R2 = { {b3 >B b2} } é uma SPS(S,Q)

Noção de qualidade: minimalidade

R: relação (pares de objetos)E(R) = fecho transitivo de RComplexidade 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ãoDado 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 indeterminadosEste 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 InferioresPasso 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 D-

q pode ser eliminado de Q q é dito trivialmente inferior.

Descobrindo Preferências para Satisfazer as Amostras InferioresPasso 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.

EXEMPLO

removido

det Não-det

- O10 é parcialmente dominado por O4 - O10 e O4 coincidem em D3 e D4

Logo: O10 é 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 GeralPara 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)ExemploR = {>3, >4} |D3| = 5, |D4| = 3Iteraçã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 = 0Complexidade 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