Soutenance de thèse de Doctorat Dimitre Kostadinov

Personnalisation de l’information : une approche de gestion de profils et de

reformulation de requêtes

Soutenance de thèse de Doctorat

Dimitre Kostadinov

UNIVERSITE DE VERSAILLESSAINT-QUENTIN-EN-YVELINES

Versailles, le 19 Décembre 2007

ACCES PERSONNALISE A DES MASSES DE DONNEES

Dimitre Kostadinov19/12/2007 2

Système d’Accès aux Données

Accès classique à un système d’information multi sources

Accès à un ensemble de sources de données distribuées, hétérogènes et autonomes

Comment résoudre le problème de la surcharge

d’information ?Est-ce que les données

sont récentes ?Est- ce je peux lire les

fichiers avec mon ordinateur ?SELECT *

FROM Publication WHERE sujet = ‘JAVA’


Système d’Accès aux Données

Accès personnalisé à un système d’information multi sources

Accès à un ensemble de sources de données distribuées, hétérogènes et autonomes

SELECT * FROM Publication WHERE sujet = ‘JAVA’

JAVA: langage de programmationFraîcheur < 1 moisFormats fichiers {PDF, PS}


Cadre du travail: Projet APMD Objectifs du projet APMD (2004-2007)

– modélisation et évolution des profils, – exécution adaptative de requêtes,– influence de la qualité sur la personnalisation,– évaluation et la validation des approches proposées dans le projet.

Partenaires– PRiSM (Versailles)– CLIPS-IMAG (Grenoble)– IRISA (Lannion)– IRIT (Toulouse)– LINA (Nantes)– LIRIS (Lyon)

Prolongé par une collaboration avec Alcatel-Lucent …


Plan

Contexte

Contributions– Modélisation de l’utilisateur (définition de la notion de profil)– Exploitation du profil dans la reformulation de requêtes

Evaluations

Conclusions et perspectives

Partie 1Modélisation de l’utilisateur


Modèle utilisateur ?

Centré sur plusieurs notions dont les définitions sont floues

– Profil– Contexte– Préférences

Chaque application possède

– Son propre modèle utilisateur

– Sa propre approche d’accès personnalisé

Référence (s) Modèle utilisé Proposition

(Chomicki 02) formules de préférences Opérateur Best

(Borzsonyi et al. 01) clause Skyline Opérateur Skyline

(Kießling 02) opérateurs supportant des préférences

Preference SQL

(Ciro et al. 04) mots clés pondérés similarité entre profil et documents

(Sorensen et al. 95) séquences de termes Filtrage des articles de Usenet News

(Cherniack et al. 03) fonctions d'utilité Caches personnalisés

(Koutrika et al. 04b), (Acqua et al. 02), (Gaasterland et al. 94)

préférences à la clause de Horn enrichissement requêtes

(Koutrika et al. 04, 05) ensemble de prédicats pondérés Enrichissement de requêtes

(Cranor et al. 03) (P3P)

3 catégories d’attributs : démographiques, professionnelles, de comportement

Sécurité des données

(Amato et al. 99) 4 catégories de connaissances: données personnelles, données collectées, données de livraison, données de comportement

Accès à une librairie digitale


Notion de préférence

Préférence – expressions permettant de hiérarchiser les concepts

auxquels on s’intéresse

Typologie des préférences

PréférenceSimple PréférenceComposée

BinaireUnitaire

Indépendante Prioritaire

compose

1..n

0..nPréférence

Ensembliste


Exemples

Préférences simples– Unitaire : poids

Film.genre=‘action’ 0.8

– binaire : >>

action >> drame

– Ensembliste : LOWEST

LOWEST(prix)

Préférences Composées– indépendante

(action >> drame) (anglais >> français)

– prioritaire &

(action >> drame) &

(anglais >> français)


Dichotomie profil/contexte

Profil – ensemble d’informations

décrivant les centres d’intérêt de l’utilisateur, plus un ensemble de préférences

Contexte– description de

l’environnement d’interaction entre l’utilisateur et le système

Profil

Contexte

Contextualisation


Meta modèle du profil utilisateur

DimensionIDdimensionnom

ProfilIDprofilpropriétaire

SousDimensionIDsousDimensionnom

Attribut

IDattributnomtypeValeurstructureValeur

ValeurAttributIDvaleurvaleur

1..n

0..n

0..n

1..n

1..n

DonnéesLivraison

DomaineIntérêt

Qualité

DonnéesPersonnelles

Sécurité

< TypeDe

< TypeDe

< TypeDe< TypeDe

< TypeDe


DomaineIntérêt

Ontologie

GrapheConceptuel1..n

VecteurMotsCles

1..n

LienSém

1..n

2..20..n

Historique

Concept

FormulesDisj

ListeExemples

Action

entre

Axiome

1..n 1..n

ConjPrédicats

Prédicat

1..n

1..n

ValeurAttribut opérateur

1..1 1..n

Contenu

concerne

1..1

1..n

Domaine d’intérêt

Exemple

1..n

1..n

0..n 1..1

0..n


Exemples

Exemple 1 : mots clés

Profil de Paul

Dim: Domaine d’Intérêt

(film, action, drame, Bruce

Willis, anglais)

Exemple 2 : ontologie

Profil de Paul

Dim: Domaine d’IntérêtFilm

Genre

action drame

Casting

Bruce Willis

Langue

anglais

Exemple 3 : prédicats

Profil de Paul

Dim: Domaine d’Intérêt

Film.genre=‘action’

Film.genre=‘drame’

Acteur.nom=‘Bruce Willis’

Film.langue=‘anglais’

Exemple 4 : historique

Profil de Paul

Dim: Domaine d’IntérêtFilm Action

Armageddon vu annonce, téléchargé

Titanic recommandé à un ami

Shrek vu annonce


Contexte

DimensionContexte

Temporelle Spatiale

Matériel Logiciel

1..n

Mobile FixeDateMoment

LocalitéCoordonné

Equipement

0..10..1

Méta modèle de contexte

TypeDe >TypeDe >

< TypeDe

Rapport technique [Abbar et al. 07]


Exemples

Contexte Maison Temporelle moment Equipement taille écran système bande passante

Contexte Bureau Temporelle date Spatiale coordonnée GPS Equipement taille écran bande passante


Liens entre les méta modèles

Préférencede Contexte

Préférencede Profil

ElémentContexte

Préférence

ElémentProfil

ProfilContextualiséSelon >

DéfiniSur >

TypeDe >

ContextualiséSelon >

Contexte

0..n 1..n 1..n 0..n

< TypeDe

DéfiniSur > DéfiniSur >

< DéfiniSur


ExempleProfil de Paul

Données personnelles

téléphone =

01 11 11 11 11 si contexte Maison

01 22 22 22 22 si contexte Bureau

0.9

0.7

0.7

0.2

0.9

0.3

0.8

Contexte Maison Temporelle moment Equipement taille écran système bande passante

Contexte Bureau Temporelle date Spatiale coordonnée GPS Equipement taille écran bande passante

si contexte Maison

{Film.genre=‘dessin animé’

Film.genre=‘comédie’

Film.langue=‘français’ }

si contexte Bureau

Domaine d’Intérêt

{Film.genre=‘action’

Film.genre=‘drame’

Acteur.nom=‘Bruce Willis’

Film.langue=‘anglais’ }


Plateforme de gestion des méta données

Implémente– Les méta modèles– Les opérations sur

les méta modèles

Composants– Gestionnaire de

profils– Gestionnaire de

contextes– Gestionnaire de

préférences


– Validation– Intégration– Adaptation

Bilan

Clarification des notions de profil et de contexte– approche multidimensionnelle

Support à la définition des notions de profil et contexte– manuel ou automatique

Ensemble d’opérations de manipulation– instanciation– appariement– Importation

Partie 2Exploitation du profil utilisateur pour la

reformulation de requêtes


Objectif Proposer une méthode de reformulation de

requêtes qui tient compte de– la distribution de l’information– profil utilisateur

SOURCE 1SOURCE 1 SOURCE 2SOURCE 2 SOURCE 3SOURCE 3 SOURCE nSOURCE n

LIENS SEMANTIQUES

SCHEMA VIRTUEL

Réécritures enrichies

{Q’1, Q’2, …, Q’m}

Pu

Q

ReformulationReformulation


Hypothèses de base

Profil– ensemble de prédicats pondérés

Requêtes– conjonctives du type SPJ

Définition des sources – vues sur le schéma virtuel (LAV)

Problèmes terminologiques résolus


Problématique

Reformulation des requêtes utilisant le profil– quelle partie du profil est pertinente à ajouter à une requête ?

• métrique de couverture

– quelle partie du schéma virtuel est nécessaire pour couvrir le profil sélectionné ?• recherche d’un sous-ensemble de relations virtuelles et des chemins de

jointures les reliant

– quelles sources de données sont les plus appropriées pour la réécriture des requêtes ?• matching des attributs, identification de prédicats conflictuels, redondants

Définition de benchmarks d’évaluation– à la compilation– à l’exécution


Insuffisance des techniques de base

Réécriture (Halevy et al. 96), (Duschka et al. 97), (Halevy et al. 01), …– prend en compte l’aspect multi source (réécriture à travers des vues)– mais ne tient pas compte du profil utilisateur

Enrichissement (Koutrika et al. 04, 05)– prend en compte le profil utilisateur (ajout de prédicats dans la

requête)– mais ne tient pas compte des mappings multi sources

(pas de réécriture)

Les 2 techniques sont complémentaires


Enrichissement

Pu Qu

RéécritureQ’u

{Schémas Sources}

{Q’’u}

SchémaVirtuel

Première approche : composition des techniques de base

Enrichissement-réécriture R(E)

Réécriture-enrichissement E(R)

Enrichissement

PuQu

Réécriture{Q’u}

{Q’’u}

{Schémas Sources}


Limites des approches séquentielles

Approche R(E) Approche E(R)Avantages + prend en compte tous les

prédicats du profil non conflictuels avec ceux de la requête

+ tient compte des définitions des sources pour la sélection des prédicats du profil utilise uniquement des prédicats pertinents

Inconvénients - peut utiliser des prédicats qui a) ne peuvent pas être réécrits b) sont déjà satisfaits pas l’ensemble des définitions des sources

- impossibilité d’exprimer certains prédicats du profil sur les sources choisies


Deuxième approche : réécriture de requêtes guidée par le profil

Idées directrices– confronter le profil utilisateur et le schéma virtuel

• sous ensemble de prédicats• sous-schéma virtuel

– sélectionner les relations virtuelles sur la base de préférence (taux de prédicats pertinents)

• étendre la requête avec les relations choisies

– faire une réécriture personnalisée• ne produire que les réécritures enrichissables


Principe général

Expansion de la requête

profil utilisateur

requêteutilisateur

Schéma Virtuel

Enrichissementfinal

sources pertinentes

réécritures

Schémas des sources de données

requête utilisateurreformulée

requêteétendue

Identification dessources pertinentes

Combinaison dessources pertinentes


Etape 1: Expansion de la requête

Principe généralProfil Schéma virtuel

R1

R3

R2

R4

R6

R5

Qu

Match

R1

R3

R2

R4

R4

R3

R2

OrdonnancementAjout à QQ’u


Problématique de l’expansion de la requête

Identification des relations sémantiquement liées à la requête

Recherche des chemins de jointure entre la requête et les relations virtuelles

Choix des chemins de jointure

Minimisation du nombre de nouvelles relations


Principe d’expansion1. Actualisation des poids des prédicats2. Choix des relations virtuelles3. Ajout des relations virtuelles à la requête


Principe d’expansion1. Actualisation des poids des prédicats

– Prise en compte de la distance entre les relations de la requête et les autres relations virtuelles

• Fonction de la distance entre la requête et la relation sur laquelle est exprimé le prédicat

2. Choix des relations virtuelles3. Ajout des relations virtuelles à la requête

€

nw( p,Qu ,Sv ) = λEJRp w( p)

Hypothèse : = 0.8

R3.a=‘x’ 0.5

nw = 0.820.5 = 0.32

0.32R5

R6R7

R8

R1 R2

R3

R4

Qu


Principe d’expansion1. Actualisation des poids des prédicats2. Choix des relations virtuelles

– somme des pertinences des relations choisies > (seuil de la portée pertinente)– pertinence d’une relation = couverture pondérée du profil utilisateur par les prédicats exprimés sur la relation

3. Ajout des relations virtuelles à la requête

R5

R6R7

R8

5%

32%

40%

20%

R1 R2

R3

R4

3%

€

rel(Pu,Qu,R j )j

∑ > μ

Objectif : Satisfaire au moins 90% du profil utilisateur ( = 0.9)

Il faut étendre Qu avec {R3, R4 }R3, R4 Qu

R4 R3 R6 R5R1

92%

0%

0%

0%40% 32% 20% 5% 3%


Il faut étendre Qu avec {R3, R4 }R3, R4

1ere itération :Plus courts chemins : R1-R6-R3R2-R7-R3R2-R8-R4

5%0%0%

2e itération:Plus courts chemins : R3-R4

Ajout de R3

Ajout de R4

Principe d’expansion1. Actualisation des poids des prédicats2. Choix des relations virtuelles3. Ajout des relations virtuelles à la requête

– Minimiser le nombre de nouvelles relations (Steiner Tree Problem (Hwang et al. 1992))– Utiliser une heuristique (Minimum Cost Paths Heuristic (Takahashi et al. 1980))

R5

R6R7

R8

5%

32%

40%

20%

R1 R2

R3

R4

3%

Qu


Etape 2: identification des sources pertinentes


profil utilisateur

requêteutilisateur

Schéma Virtuel

Enrichissementfinal

sources pertinentes

réécritures



requêteétendue


Combination dessources pertinentes


Objectif

Trouver les sources permettant de calculer les résultats de la requête– sources contributives pour la réécriture de la requête

Choisir les sources les plus pertinentes– enrichissables par les prédicats du profil utilisateur


Problèmes à résoudre

Trouver les sources contributives– contenant des données de même nature que celles

recherchées par la requête– satisfaisant les prédicats de la requête

• Sélections• Jointures

Elagage des sources non pertinentes – introduction d’une métrique de pénalité


Principe de l’identification des sources pertinentes

Recherche des sources contributives pour la réécriture de la requête

• construction d’un ensemble de descripteurs de sources (MCDs)

(type MiniCon Halevy et al. 2001)

Filtrage des sources– pénalité d’une source (MCD) > seuil de pénalité

• Couverture pondérée du profil par les prédicats exclus par la source

– Conflictuels avec la définition de la sources

– Inexprimables sur la source


Q’u(idV, prix, lieu_depart, moyen, comfort) :- voyage(idV, prix, lieu_depart, lieu_arrivee, nbre_jours, idT, idH),transport(idT, moyen, type_trajet, comfort), hotel(idH, nbre_etoiles, nom, region, lieu_depart, idR)

lieu_arrivee='Madrid.

(1)(2)(3)

Exemple d’identification des sources pertinentes

Pénalité(ParisVacances) = CP(Pu, {a, b}) = 0.43

ParisVacancesParisVacances(idV, prix, lieu_depart, lieu_arrivee, idT):-(idV, prix, lieu_depart, lieu_arrivee, idT):-

VOYAGEVOYAGE(idV, prix, nbre_jours, lieu_depart, lieu_arrivée, idT, idH),(idV, prix, nbre_jours, lieu_depart, lieu_arrivée, idT, idH),

lieu_depart = ‘Paris’. lieu_depart = ‘Paris’.

Profil utilisateur Pu{ VOYAGE.nbre_jours>7 1.0 (a)

VOYAGE.lieu_depart=’Toulouse’ 0.8 (b)

TRANSPORT.moyen='avion’ 0.5 (c)

HOTEL.nbre_etoiles>3 0.4 (d)

TRANSPORT.comfort>2 0.4 (e)

VOYAGE.lieu_depart = ‘Paris’ 0.2 (f)

HOTEL.region=‘centre ville’ 0.2 (g)

RESTO.catégorie=‘gastronomique’ 0.1 (h) }

Source contributive pour la relation VOYAGE

?


Etape 3: Combinaison des descripteurs


profil utilisateur

requêteutilisateur

Schéma Virtuel

Enrichissementfinal

sources pertinentes

réécritures



requêteétendue




Problématique de la combinaison de sources

Problème combinatoire

Compatibilité des sources (MCDs)

Pertinence des réécritures par rapport au contenu du profil utilisateur


ID Source Contributive pour

a HOTELSDUMONDE Hotel

b PARISVACANCES Voyage,Hotel

c LYONVACANCES Voyage

d LYONVACANCES Hotel

e SNCF Transport

f TRANSPORTAERIEN Transport

g VOYAGERPARTOUT Transport

ab ac ad ae af ag

Seuil de pénalité = 0.5

a c e gb d f0 0.45

Relations de la requête étendue : { VOYAGE, TRANSPORT, HOTEL }

0.45 0.08 0.1 0.0 0.0

bc bd be bf bg cgcfce df dg ef eg fgde

acf acg

0.45 0.1 0.00.0 0.55 0.450.45 0.18 0.080.080.54 0.55 0.45 0.45

0.45 0.45

Redondantes : ab, ad, bc, bd, ef, eg, fg

Pénalité > seuil : be, cd, ce

Réécritures : bf, bg , acf, acg

cd

Solution proposée

Utiliser un algorithme par niveaux (Apriori (Agrawal et al. 94))

– Élaguer les combinaisons de MCDs ayant une grande pénalité

– La pénalité est monotone


Etapes de l’algorithme


profil utilisateur

requêteutilisateur

Schéma Virtuel

Enrichissementfinal

sources pertinentes

réécritures



requêteétendue




Enrichissement final

Objectif– Ajouter les prédicats du profil aux réécritures candidates

Etape préparé par les étapes précédentes– Connaissance des prédicats exclus

• déduction des prédicats à utiliser

– Connaissance des définitions des sources• Identification des prédicats déjà satisfaits par les sources

Principe– Ajout de la conjonction des prédicats du profil à la requête


Exemple d’enrichissement final

RW(idV, prix, lieu_depart, moyen, comfort):-RW(idV, prix, lieu_depart, moyen, comfort):-

, nbre_etoiles>3, comfort>2

Profil utilisateur{ VOYAGE.nbre_jours>7 1.0 (a)

VOYAGE.lieu_depart=’Toulouse’ 0.8 (b)

TRANSPORT.moyen='avion’ 0.5 (c)



VOYAGE.lieu_depart = ‘Paris’ 0.2 (f)

HOTEL.region=‘centre ville’ 0.2 (g)

RESTO.catégorie=‘gastronomique’ 0.1 (h) }



Conflictuels avec Qu

Pas considérés lors de l’expansion

Exclus par les sources (pénalité)

Déjà satisfaits par les sources

A ajouter

TransportAerienTransportAerien((idT, comfort), idT, comfort), moyen = ‘avion’moyen = ‘avion’

lieu_arrivee='Madrid‘, nbre_jours=4lieu_arrivee='Madrid‘, nbre_jours=4

ParisVacancesParisVacances(idV, prix, lieu_depart, lieu_arrivee, (idV, prix, lieu_depart, lieu_arrivee,

nbre_jours, moyen, nom, nbre_etoiles, idT),nbre_jours, moyen, nom, nbre_etoiles, idT),

lieu_depart = ‘Paris’lieu_depart = ‘Paris’


Plan

Contexte


Evaluations



Evaluation des approches de reformulation de requêtes

Proposition d’un benchmark– Construction d’une plateforme de données (Peralta 2007)– Dérivation d’un benchmark à partir de la plateforme

Définition de métriques d’évaluation– Niveau compilation des requêtes– Niveau exécution des requêtes


Plateforme des tests Principe de construction

Caractéristiques

Données IMDb

Données MovieLens

Extraction

Extraction

Nettoyage etréconciliation

des données BDintégrée

Génération derequêtes et de profils

ProfilsRequêtes

Bons résultats

Schéma cible

Nombre de tables dans la BD intégrée 52

Nombre de films 3 881

Nombre d’évaluations de films 1 000 194

Nombre d’utilisateurs 6 040

Nombre de requêtes générées 6 041

Nombre de profils générés 120 800

+ référentiel de résultats pertinents pour chaque couple (profil, requête)


Etapes de construction du benchmark

Caractéristiques

Benchmark des tests

Simulationdu

système distribué

Choix des requêtes et des profils

Choix des paramètres

ProfilsRequêtes

Bons résultats

BDintégrée

Schéma cible

Schéma virtuel

Requêtes de médiation

Sources

Profils etRequêtesretenus

Schéma virtuel 49 relations

Sources 52 dont 23 contiennent des prédicats de sélection

Échantillon de requêtes 13 requêtes

Échantillon de profils 15 profils

Valeur du seuil de pénalité De 0 à 0.5 pour portée pertinente = 0.5

Valeur de la portée pertinente De 0.1 à 0.7 pour seuil de pénalité = 0.3

Système distribué


Métriques d’évaluation

Niveau compilation– Couverture des prédicats du profil

• Couverture pondérée

– Temps de réponse de la reformulation

Niveau exécution– Rappel

• nombre de résultats pertinents obtenus / nombre total de résultats pertinents

– Précision• nombre de résultats pertinents obtenus / nombre total de résultats

obtenus


Profils 6 prédicats ; requêtes 5 relations

0%

10%

20%

30%

40%

50%

60%

70%

0.1 0.2 0.3 0.4 0.5 0.6 0.7

seuil de la portée pertinente

couverture du profil

R/P R(E) E(R)

Profils 6 predicats ; requêtes 3 relations

0

2

4

6

8

10

12

0.1 0.2 0.3 0.4 0.5 0.6 0.7

seuil de la portée pertinente

temps de réponse en sec.

R/P R(E) E(R)

Temps de reformulation d'une requête

0

10

20

30

40

50

60

70

80

1 2 3 4 5 6 7 8 9

nombre de relations dans la requête à réécrire

temps de réponse en sec.

Résultats des tests au niveau compilation

Couverture du profil utilisateur

Temps de réponse

Profils 6 prédicats ; requêtes 3 relations

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

0.1 0.2 0.3 0.4 0.5 0.6 0.7

relevant scope

couverture du profil

R/P R(E) E(R)

R/P

R(E)

E(R)


Intervalle de Rappel en % R/P R(E) E(R)

[50, 60) 2,3%

[60, 70) 10,4%

[70, 80) 11,6% 0,4%

[80, 90) 56,8% 0,4%

[90, 100) 8,5% 52,5% 5,0%

100 10,4% 46,7% 95,0%

Gain de précision par rapport à MiniCon R/P R(E) E(R)

[8, 10) 2,3%

[6, 8) 7,3%

[4, 6) 11,2%

[2, 4) 25,1%

[0, 2) 22,8% 29,0% 6,9%

0 0,8% 34,0% 88,0%

(0,-2] 20,8% 37,1% 5,0%

(-2, -4] 7,3%

(-4, -6] 2,3%

Résultats des tests au niveau exécution

Rappel

PrécisionApproche Pourcentage de

cas où elle a obtenu la meilleure précision

R/P 69,5 %

R(E) 21,2 %

E(R) 19,3 %

MiniCon 19,7 %


Position par rapport aux travaux similaires

Enrichissement de requêtes (Koutrika et al. 04, 05)– calcul de préférences implicites (expansion)– travail au niveau des prédicats– pas de distribution de l’information

Réécriture de requêtes – algorithme MiniCon (Halevy et al. 01)

• recherche de toutes les réécritures candidates possibles• pas d’expansion de la requête • pas de prise en compte du profil utilisateur

– choix des sources à base de critères de qualité (Naumann et al. 98)• filtrage de sources à base de facteurs de qualité• pas d’expansion de la requête

– calcul des top K chemins de navigation entre sources (Vidal et al. 06)• chaque source est assimilée à un concept• PB : trouver un chemin d’une source à une autre


Plan

Contexte


Evaluations



Conclusion

Modélisation des connaissances décrivant l’utilisateur– Méta modèles de profil, contexte et préférences– Gestionnaire des méta modèles

Exploitation du profil utilisateur pour la reformulation de requêtes– Définition et analyse de deux approches séquentielles– Algorithme de réécriture guidé par le profil utilisateur

Evaluation des approches de reformulation de requêtes– Niveau compilation– Niveau exécution


Perspectives

Calcul d’autres résultats que ceux de la requête initiale– Relâcher les prédicats de la requête initiale

Faire un enrichissement au niveau des sources– sources multi relations

Prise en compte d’autres dimensions du profil– choix des sources en fonction de la qualité

Prise en compte d’autres types de préférences– Préférences sous forme d’ordres partiels


Questions ?

Documents

Soutenance de thèse de Doctorat Dimitre Kostadinov