Mineração de Preferências
Contextuais sobre dados de
preferência “pairwise”
Data Mining
AULA 19 – Parte I
Sandra de Amo
LIG - Université Grenoble 2011
1
Referências

ICTAI 2012
Sandra de Amo, Marcos L. Bueno, Guilherme Alves, Nádia F.
Silva: CPrefMiner: An Algorithm for Mining User Contextual
Preferences based on Bayesian Networks. In: 24th IEEE International
Conference on Tools with Artificial Intelligence (ICTAI 2012), 2012, Atenas.

Journal of Information and Data Management (JIDM 2013)
Sandra de Amo. ; Bueno, M.L. ; ALVES, G. ; Silva, F. N. Mining User
Contextual Preferences. Journal of Information and Data Management
(JIDM) , Vol. 4 (1), 2013, pages 37-46.
LIG - Université Grenoble 2011
2
Modelos de Preferências

Séjours
Enfoque Quantitativo

Modelo:
Score : Tuplas  N

Ordem total sobre as
tuplas
Saison
Cadre
Pâcques
urbain
3
Vac-été
plage
4
Vac-hiver
montagne 2
Vac-hiver
Historique 5
Noel
LIG - Université Grenoble 2011
urbain
1
3
Outros quantitativos

Rankings <p1,p2,...,pn>

Pares (p1,p2)

Triplas (p1,p2,n), onde n = grau de preferência
LIG - Université Grenoble 2011
4
Modelos de Preferências

Enfoque Qualitativo
 Modelo
Conjunto finito de regras:
SE condição1 E Contexto1
ENTÃO Escolha1
SE condição1 E Contexto2
ENTÃO Escolha2
....
 Ordem Parcial sobre
as tuplas
REGRAS
SE a viagem é durante as férias
de verão e viajo com minha
família ENTÃO prefiro ir à praia
do que à uma cidade histórica.
SE a viagem é durante as férias
de verão e viajo sozinho ENTÃO
prefiro ir à uma cidade histórica
do que à praia.
LIG - Université Grenoble 2011
5
Mineração de Preferências
Contextuais
LIG - Université Grenoble 2011
6
O que queremos minerar ?

Regras de Preferências ?




A = a1 > A = a2
B = b1 > B = b2
A = a ^ B = b  C = c1 > C = c2
C = c2  D = d1 > D = d2
LIG - Université Grenoble 2011
7
O que queremo minerar ?
P[A = a1 > A = a2] : 0.8
A
B
C

Uma rede de preferências D


P[B = b1 > B = b2] : 0.7
P[ (C=c1 > C=c2) |
A = a1, B = b1 ] = 0.6
P[ (D=d1 > D=d2) | C = c1 ]
= 0.75
Um grafo de preferências
Para cada vértice do grafo:
uma tabela de probabilidades condicionais
de escolha dos valores do vértice com relação aos
valores de seus pais.
LIG - Université Grenoble 2011
8
Como são os dados de entrada a serem
minerados ?

Pares de tuplas expressando a preferência
do usuário.
(t1,t2)  t1
(t1,t3)  t3
(t2,t4)  t2
(t4,t5)  t5
....
LIG - Université Grenoble 2011
9
Como medir a qualidade de uma rede de
preferências ?
(t1,t2)  t1
(t2,t3)  t3
(t2,t4)  t2
(t1,t3)  t1
(t1,t4)  t1
Rede de Preferências
(t1,t2)  t1
(t2,t3)  t2
(t2,t4)  t2
(t1,t3)  ?
(t1,t4)  ?
Dados de testes
Conjunto de pares
Conjunto de pares
ee tuplas classificados
de tuplas
pela rede de pref. R
classificados pelo usuário
Accuracy(R) = Total de tuplas corretamente ordenadas por R = 2/5
Total de tuplas
Precision(R) = Total de tuplas corretamente ordenadas por R = 2/3
Total de tuplas ordenadas por R
LIG - Université Grenoble 2011
10
Como uma rede ordena tuplas ?
P[A = a1 > A = a2] = 0.8
Comparer le tuples
P[B = b1 > B = b2] = 0.7
A
t1(a1,b1,c1,d1)
t2(a2,b2,c2,d1)
B
C
Dif(t1,t2) = {A, B,C}
P[ (C=c1 > C=c2) | A = a1, B=b1] = 0.8
P[ (C=c1 > C=c2) | A = a1, B=b2] = 0.4
P[ (C=c1 > C=c2) | A = a2, B=b1] = 0.6
P[ (C=c1 > C=c2) | A = a2, B=b2] = 0.7
Inf(Dif) = {A,B}
P[A = a1 > A = a2, B = b1> B=b2] = 0.56
P[A = a1 > A = a2, B = b2> B=b1] = 0.24
P[A = a2 > A = a1, B = b1> B=b2] = 0.14
P[A = a2 > A = a1, B = b2> B=b1] = 0.06
D
P[ (D=d1 > D=d2) | C = c1 ]
= 0.75
t1 > t2 : 0.56
t1 < t2 : 0.06
t1 ~ t2 : 0.48 (incomparables)
LIG - Université Grenoble 2011
11
Formalisation du Problème

Entrée: un echantillon de pairs de tuples
(x,y), où x est préférée à y

Sortie: un réseau bayésien de préférences
(réseau probabiliste de préférences) ayant
une “bonne” accuracy et une “bonne”
précision.
LIG - Université Grenoble 2011
12
Duas etapas:
P[A = a1 > A = a2] : 0.8
A
1. Minerar
a topologia
da rede
P[B = b1 > B = b2] : 0.7
B
C
P[A = a1, B = b1 |
C=c1 > C=c2 ] = 0.6
D
2. Descobrir as tabelas de
probabilidades
associadas a cada nó
LIG - Université Grenoble 2011
P[ C = c1 |
D=d1 > D=d2] = 0.75
13
Mineração da Topologia
da Rede
Dados D
A
A
C
B
D
E
B
A
C
F
Score(S1,D) = N1
D
E
B
D
C
F
Score(S2,D) = N2
LIG - Université Grenoble 2011
E
F
Score(S3,D) = N3
14
Aspectos importantes :

Estratégia de busca das estruturas
 Impossível de gerar todas as estruturas
possíveis
 Necessidade de empregar uma heurística

Como definir o score de uma estrutura ?
LIG - Université Grenoble 2011
15
Técnica utilizada para minerar a estrutura
da rede a partir dos dados de preferência



Algoritmo Genético
Função score particular
Detalhes nos seguintes artigos:
ICTAI 2012, JIDM 2013
LIG - Université Grenoble 2011
16
Resultados em dados sintéticos
Numero de atributos
LIG - Université Grenoble 2011
17
Dados Reais

Dados de avaliações de filmes do Group Lens
www.grouplens.org

Dados sobre os filmes: IMDB
www.imdb.com

Dados coletados e pré-processados, disponíveis
em
LIG - Université Grenoble 2011
18
Resultados em dados reais (filmes)
Tempo para construir o modelo de Mineração
LIG - Université Grenoble 2011
19