JIRC09 / NEGRE Elsa Exploration collaborative de cubes de données NEGRE Elsa Université François Rabelais Tours JIRC09 22 Janvier 2010

1/30JIRC’09 / NEGRE Elsa

Exploration collaborative de cubes de données

NEGRE ElsaUniversité François Rabelais Tours

JIRC’09 22 Janvier 2010


Plan

1. Contexte / Problématique

2. BD multidimensionnelles

3. Intuitions

4. Recommandation de requêtes

5. Expérimentations et Résultats

6. Conclusion et Perspectives


Contexte / Problématique

• Problématique : Comment aider l’utilisateur à avancer dans son exploration du cube de données en lui proposant des requêtes pertinentes ?

• Contexte : – Informations → Exploration de cubes de données– Plusieurs utilisateurs


Plan



3. Intuitions






Modélisation des bases de données multidimensionnelles

• Dimension (D) sort(TEMPS)={DateV, Mois, Trimestre, Année, AllT}

• Fait (F) sort(VENTES)={Immatriculation, DateV, CodeVille, NomM, Valeur}

• Cube N-dimensionnel, C = <D1, …, DN, F>MesVentes = <MESURES,VEHICULES,GEOGRAPHIE,TEMPS,VENTES>

Schéma en étoile inspiré par [Golfarelli+:IJCIS’98]

1. Introduction2. BDM3. Intuitions4. Recommandation5. Expérimentations6. Conclusion et Perspectives


Le langage MDX [Microsoft:1998]

• Requête : {Rouge} X {Centre, Limousin} X πAnnée(Temps) X {Montant}

• Références :{<Montant, Rouge, Centre, 2007>, <Montant, Rouge, Limousin, 2007> <Montant, Rouge, Centre, 2008>, <Montant, Rouge, Limousin, 2008>}

• Résultat :

< Montant,Rouge,Centre,2008,110000

00 >



Analyse multidimensionnelle• Interrogation : Quelles sont les mauvaises ventes ?

• Réponse : Les véhicules réalisant des mauvaises ventes sont les véhicules rouges et les véhicules bleus dans la ville de Tours.

• Session d’analyse [Sarawagi:VLDB’00] : s1 = q1 → q2 → q3

– q1 = Ventes dans les départements de la région Centre, quels que soient les véhicules et les informations temporelles

– q2 = Ventes dans les villes d’Indre-et-Loire, quels que soient les véhicules et les informations temporelles

– q3 = Ventes de véhicules selon leur couleur dans les villes d’Indre-et-Loire, quelles que soient les informations temporelles



Environnement1. Introduction2. BDM3. Intuitions4. Recommandation5. Expérimentations6. Conclusion et Perspectives


Plan



3. Intuitions




3. Intuitions


Intuitions

RIWeb Usage Mining

e-commerce

Utiliser les comportements connus d'une population pour envisager les futures actions d'un utilisateur particulier

et Rechercher, par comparaison, les utilisateurs ayant des comportements semblables

OLAP

Exploitation des précédentes sessions des autres utilisateurs pour générer des recommandations

1. Introduction2. BDM3. Intuitions4. Recommandation5. Expérimentations6. Conclusion et Perspectives Filtrage collaboratif en :


Problèmes / Solutions

• Problèmes :1. Comment déterminer la similarité entre

deux sessions/séquences de requêtes ?2. Comment déterminer la similarité entre

deux requêtes ?3. Dans quel ordre présenter les requêtes

recommandées ?

• Solutions :1. Distance entre séquences de requêtes2. Distance entre requêtes3. Ordonnancement de requêtes



Plan1. Contexte / Problématique


3. Intuitions

4. Recommandation de requêtes1. Jkjhkjhk2. Kjkjjk3. Kjkjk



4. Recommandation de requêtesa. Distances entre sessionsb. Cadre générique de génération de

recommandationsc. Instanciations du cadre


Distances entre références• Références :

– r1 : <Montant, Rouge, Blois, 2008>– r2 : <Montant, Rouge, Tours, 2008>– r3 : <Montant, Rouge, Vendome, 2008>

37000Tours

IndreEtLoire

41100Vendome

41000Blois

LoirEtCher

33000

AllG

BordeauxGironde

CentreAquitaine

• Distance de Hamming : simplicité d’utilisation mais grossière– dh(r1,r2) = 0 + 0 + compare(Blois,Tours) + 0 = 1

– dh(r1,r3) = 0 + 0 + compare(Blois,Vendome) + 0 = 1

• Distance basée sur le plus court chemin : prise en compte des hiérarchies : compliquée mais fine– dsp(r1,r2) = 0 + 0 + dm(Blois,Tours) + 0 = 4– dsp(r1,r3) = 0 + 0 + dm(Blois,Vendome) + 0 = 2

dh(r1,r2) = dh(r1,r3) et dsp(r1,r2) ≠ dsp(r1,r3)



Distance de Hausdorff• Requêtes :

– q1 : Montant des ventes de véhicules rouges à Blois quelle que soit l’année : {<Montant, Rouge, Blois, AllT>} = {r1

1}– q2 : Montant des ventes de véhicules rouges ou bleus à Tours

en 2008 : {<Montant, Rouge, Tours, 2008>, <Montant, Bleu, Tours, 2008>} = {r2

1, r22}

• Distance de Hausdorff entre requêtes :

= 7

r11

r21

r22

q1 q2

5

5

7

7



Distance entre sessions (1) • Sessions :

• s1 : q3

• s2 : q1 → q2

• Distance de Levenshtein entre sessions• dLevenshtein(s1, s2) = dLevenshtein(q3, q1→q2)

– Opérations :• Substitution d’une requête q par une requête q’ • Insertion (suppression) d’une requête

– Possibilités :• e1 : q3 q1 (q1→q2)

• e2 : q3 Ø q1 (q1→q2)

– Coût• Si chaque opération vaut 1• coût(e1) = 2 < coût(e2) = 3

– Distance entre sessions = coût minimal• dLevenshtein(s1, s2) = 2

subst(q3,q1) ajout(q2)

ajout(q1) ajout(q2)suppr(q3)



• Dans notre contexte : – Coût des opérations :

• Substitution d’une requête q par une requête q’ = dH(q,q’)

• Ajout (suppression) de requête = α

– Exemple : • Sessions :

– s1 : q3

– s2 : q1 → q2

• e1 : q3 q1 (q1→q2)

• dLevenshtein(s1, s2) = coût(e1) = dH(q1,q3) + α

Distance entre sessions (2)

subst(q3,q1) ajout(q2)



Présentation du cadre

Match Rep



ClusterH

K-médoïdes

Médoïde du successeur

Suffixes de gc

dH(q3,q4) < dH(q3,q5) [Hamming]

Classes : c1={q1}, c2={q2,q2

2,q3,q32},

c3={q4}, c4={q5,q6}



EdSP

Identité

DernierDistance de Levenshtein



Plan1. Contexte / Problématique


3. Intuitions


5. Expérimentations et Résultats1. Jjhhj2. Kjkjkjk


5. Expérimentations et Résultatsa. Le systèmeb. Notre générateurc. Les tests


Le système1. Introduction2. BDM3. Intuitions4. Recommandation5. Expérimentations6. Conclusion et Perspectives


Notre générateur

– Le cube• Base de données FoodMart (OLAP Mondrian

[Pentaho:2009])

– Les sessions :• 300 références max. par requête MDX• X sessions• Y requêtes max. par session• Z dimensions pour le pool de départ

– Propriétés : • Variation de la densité des logs générés grâce à Z• Obtention des requêtes successives grâce aux

opérateurs de Sarawagi (Diff, Relax, Excep)



Analyse de performance

• Observations– Augmentation linéaire du temps avec la taille des logs– Temps acceptable < 1 sec. (sauf EdSP)

0,1

10

1000

0 500 1000 1500 2000 2500 3000

Taille des logs (nb req)

Tem

ps (m

s))

ClusterH EdH ClusterSP EdSP



Validation croisée (1)

Log

Sessions courantes de taille n

Log initial

sc = q1 → … → qn-1 → ? (qat)

qrec = qat ?




• Exemple : – qat = {<Montant, Rouge, Blois, 2008>}

– qrech = {<Montant, Rouge, Tours, 2009>}

– Précision(qrech) = 2/4 = 1/2




• Observations :– x% des sessions ont une F-mesure ≥ y– F-mesure augmente lorsque la densité augmente– ClusterH : performances moins bonnes pour densité faible– Distance de Hamming favorisée par calcul de rappel/précision

F-Mesure : Densité Faible

00,10,20,30,40,50,60,70,80,9

1

0 20 40 60 80 100% de sessions

F-M

esu

re

F-Mesure : Densité Forte

00,10,20,30,40,50,60,70,80,9

1

0 20 40 60 80 100% de sessions

F-M

esu

re


Plan



3. Intuitions



6. Conclusion et Perspectives6. Conclusion et Perspectives


Conclusion

• Recommandation de requêtes MDX– Méthode collaborative de guidage de l’utilisateur pour

l’exploration de gros volumes de données• Prétraitement du log de requêtes• Génération de requêtes candidates• Ordonnancement des recommandations candidates

– 4 instanciations

• Expérimentations : RecoOLAP– Comparaison des différentes instanciations– Efficacité de notre technique



Perspectives (1)

• Améliorer les performances du système

• D’autres types de recommandations– Exemple : Sessions ne différant que d’une sélection

Recommandation



Perspectives (2)

• Expérimentations sur données réelles– IRSA (Institut interRégional pour la SAnté)– Elaboration des sessions en cours

• Contribution à un système collaboratif de gestion de requêtes– Plateforme de génération de recommandations– Adapter l’approche aux besoins des utilisateurs

• Diverses méthodes de calcul de sessions / requêtes candidates• Prendre en compte les valeurs des mesures [Giacometti+:DOLAP’09]• Diverses techniques (collaborative, contenu

[Chatzopoulou+:SSDBM’09], prise en compte du contexte et du profil de l’utilisateur [Jerbi+:ICEIS’09, Bellatreche+:DOLAP’05, Golfarelli+:SSDBM’09])

– Possibilités sophistiquées de gestion de requêtes [Khoussaïnova+:CIDR’09]




ANNEXES


Défaveur de SP

• La requête attendue– qat = {<Montant, Rouge, Blois, 2008>}

• Les recommandations – qreco

h = {<Montant, Rouge, Tours, 2009>}

– qrecosp = {<Montant, AllV, LoirEtCher, AllT>}

• Raisons – dH

h (qat, qrecoh) = 0+0+1+1 = 2

– dHsp (qat, qreco

sp) = 0+1+1+1 = 3

• Précision =

– Précision(qrecoh) = 2/4 = 1/2

– Précision(qrecosp) = 1/4

)(

)()(

at

recoat

qmembres

qmembresqmembres


BD : Recommandation vs. Personnalisation

• Personnalisation : – ajout de conditions de sélection en fonction du

profil de l’utilisateur.La requête personnalisée est incluse dans la

requête initiale.Q : ventes de véhicules à Tours en 2007Q* : ventes de véhicules bleus ou rouges à Tours en 2007

• Recommandation : La requête recommandée est :– soit une requête issue d’un ensemble de requêtes, – soit une requête calculée.La requête recommandée n’est pas forcément

incluse dans la requête initiale.Q : ventes de véhicules à Tours en 2007Q* : ventes de véhicules en région Centre en 2008


Combinaisons

Documents

JIRC09 / NEGRE Elsa Exploration collaborative de cubes de données NEGRE Elsa Université François Rabelais Tours JIRC09 22 Janvier 2010