1

Techniques de généralisation des URLs pour l'analyse des usages du Web

Yves Lechevallier, Florent Masseglia, Doru Tanasa et Brigitte Trousse

Projet AxIS, INRIA Rocquencourt & Projet AxIS, INRIA Sophia Antipolis,

E-mail : Prénom.Nom@inria.frURL : http://www-sop.inria.fr/axis/

FDC, EGC 2006, Lille, 17.01.2006

2

Plan

Motifs séquentiels

Exemple motivant

État de l’art

Principe général

Exemple d’application

Expérimentation

Conclusions

3

Item : un « article »

Transaction : un client + un itemset + une date

Séquence : liste ordonnée d’itemsets

Séquence de données : représente les achats d’un client. Soit T1, T2, … Tn les transactions de Cj, la séquence de données Cj est :

< itemset(T1) itemset(T2) … itemset(Tn)>

Support (S) : pourcentage de séquences de données contenant Ss1 = <a1a2…an> et s2 = <b1b2…bn>

s1 s2 (incluse) si i1 < i2 < … in | a1 bi1 , …, an bin

S – Motif fréquent ssi Supp(S) φ – support minimum

GWUM

Motifs séquentiels

4

Extraction de motifs séquentiels dans le cas classique (sur la base d’URLs) :

C1 : accueil_FM publications_FM accueil_Inria

C2 : accueil_BT publications_BT Logiciels_AxIS

C3 : publications_AxIS accueil_FM publications_FM

C4 : accueil_AxIS accueil_BT publications_BT

Avec un support de 50%, 2 comportements extraits :

1. accueil_FM publications_FM

2. accueil_BT publications_BT

Avec un support de 100%, aucun comportement fréquent…

GWUM

Exemple motivant

5

Objectif de notre travail : extraire des motifs séquentiels basés non plussur des URLs mais sur des caractéristiquescaractéristiques de ces URLs.

Caractéristiques possibles :

- Mots clés spécifiés dans un moteur et qui ont permis d’accéder à cette URL.- Mots clés extraits à partir du contenu :

• TF/IDF• Pronoms• TreeTagger• Sémantique (« manuel utilisateur de cet appareil photo » ou alors

« l’appareil photo est vendu avec son manuel utilisateur »)•…

- Informations de surface (répartitions des informations, etc.)- Autres ?

Quel intérêt pour les motifs séquentiels ? Reprenons l’exemple précédent…

GWUM

6

- Page Web de Brigitte Trousse -

Bienvenue.

Je suis chercheur(se?) à l’Inria Sophia Antipolis.Je suis responsable de l’équipe AxIS.

Mes thèmes de recherche sont : -ECD-Data Mining-I.A.

Vous pouvez consulter tout plein de rubriques me concernant sur cette page.

En particulier mes publications.

Referer :

•ECD•Data Mining•I.A.•Brigitte Trousse

GWUM

7

- Page Web de Florent Masseglia -

Bienvenue.

Je suis chercheur(!) à l’Inria Sophia Antipolis dans l’équipe AxIS.

Mes thèmes de recherche sont : -ECD-Data Mining-Motifs Séquentiels

Vous pouvez consulter tout plein de rubriques me concernant sur cette page.

En particulier mes publications.

Referer :

•ECD•Data Mining•Motifs Séquentiels•Florent Masseglia

GWUM

8

Referer :

•ECD•Data Mining•Motifs Séquentiels•Florent Masseglia

Referer :

•ECD•Data Mining•I.A.•Brigitte Trousse

Classe 1 :« ECD, Data Mining »

• Une première caractéristique : les mots clé du referer.

• Une seconde caractéristique : le contenu de la page.

« Les pages publications_BT et publications_FM sont des pages de la classe PUBLICATIONS »

GWUM

9

Avec un support de 100%, aucun comportement fréquent…

Avec un support de 50%, 2 comportements extraits :

1. accueil_FM publications_FM

2. accueil_BT publications_BT

AVANTAVANT

APRESAPRES

Avec un support de 100%, il existeil existeun comportementun comportement fréquent :

« Classe 1 » PUBLICATIONS

« 100% des utilisateurs consultent une page qui parle de data mining ou d’ECD puis une page de publications »

10

« 100% des utilisateurs consultent une page qui parle de data mining ou d’ECD puis une page de publications »

C1 : accueil_FM publications_FM accueil_Inria

C3 : accueil_BT publications_BT Logiciels_AxIS

C2 : publications_AxIS accueil_FM publications_FM

C4 : accueil_AxIS accueil_BT publications_BT

GWUM

11

État de l’art

WUM (Spiliopoulou et al. 1999), WebTool (Masseglia et al. 2000),

AxisLogMiner (Tanasa 2005)

Dimensionnalité des données affecte les résultats

2 solutions :• Grouper dans des sous-logs les utilisateurs ayant des objectifs de navigation

communs (Masseglia et al. (2003), Tanasa (2005))

• Généraliser les pages Web (syntaxique Fu et al. 1999) (sémantique Tanasa et al. 2005)

Ex. http://www-sop.inria.fr/axis/Publications/2005/all.html

Extraction des MS en tenant compte d’une hiérarchie manuelle (Srikant

et Agrawal 1996)

Interêt de notre travail : construction automatique de la classification

GWUM

projets

12

Principe General

GWUM

13

Exemple d’application

Informations du referer :• Utilisation du champ referer du fichier log (requêtes provenant des

moteurs de recherche – MR)

• Pour une page => plusieurs referers MR => plusieurs mots clés

• Normalisation des mots clés à l’aide de TreeTagger (transformation du mot dans sa racine syntaxique – lemmatisation)

• Classification croisée sur une table de contingence => 10 classes

Informations sur le contenu :• Prise en compte de la partie textuelle d’une page

• Sélection des mots représentatifs de chacune des pages en appliquant un algorithme classique (ex. Korfhage (1997))

• Une proposition inspirée de TF/IDF a été faite dans Sellah (2005)

GWUM

14

Les données log du mois d’octobre 2005 pour le site Web d’INRIA Sophia Antipolis

•Données initiales (avant prétraitement) :• 1 328 MO

• 5 840 576 lignes (requêtes)

•Données finales (après prétraitement)• 183 MO

• 845 208 requêtes

• 173 848 sessions = couples (IP, User Agent) = utilisateur

• 258 061 navigations (visites uniques avec des intervalles < 30 minutes entre 2 requêtes)

• 62 721 URLs différents

• ~20% des URLs catégorisées (par les mots clés du referer)

GWUM

Experimentation

15

0

10

20

30

40

50

60

70

80

90

100

Support

Nb

mo

tifs

URL ONLY URL & CLASS

GWUM

Experimentation

16

Conclusions

•Méthodologie WUM basé sur une catégorisation des pages

•Informations extraites soit de :• la page elle-même

• l’utilisation de la page (l’accès à la page)

•L’expérimentation montre l’avantage d’une telle approche (gain en terme de motifs séquentiels découverts)

•Travail en cours avec de nombreuses perspectives :• Interprétation des résultats obtenus (motifs)

• Exploration d’autres critères permettant de catégoriser les pages (contenu, langage, présentation de la page, images, profils des utilisateurs ayant accède aux pages, leur pays, etc.)

• Mixage des critères (motifs complexes présentant plusieurs catégories)

GWUM

17

Techniques de généralisation des URLs pour l'analyse des usages du Web

Yves Lechevallier, Florent Masseglia, Doru Tanasa et Brigitte Trousse

Projet AxIS, INRIA Sophia Antipolis & Projet AxIS, INRIA Rocquencourt,

E-mail : Prénom.Nom@inria.frURL : http://www-sop.inria.fr/axis/

FDC, EGC 2006, Lille, 17.01.2006

18

References

Masseglia 1999

Masseglia 2003

Sellah 2005

Tanasa 2005

19

Les sites Web de l’INRIA

Un institut de recherche = 7 sites Web différentes :

INRIA Siège http://www.inria.fr/

INRIA Rocquencourt http://www-rocq.inria.fr/

INRIA Sophia Antipolis http://www-sop.inria.fr/

INRIA Lorraine http://www.loria.fr/

INRIA Rhône-alpes http://www.inrialpes.fr/

INRIA Rennes http://www.irisa.fr/

INRIA Futurs http://www-futurs.inria.fr/

20

Les projets-equipes de l’INRIA

•168 projets INRIA en Nov. 2005

•29 projets INRIA sur Sophia

•~50 anciens projets, mais présents sur le Web

•Organisés en 5 thèmes avec des sous-thèmes:

• Com : Systèmes communicants (4)

• Cog : Systèmes cognitifs (4)

• Sym : Systèmes symboliques (3)

• Num : Systèmes numériques (4)

• Bio : Systèmes biologiques (1)

  Sous-thème

 Equipes A B C D

COM 6 1 3 2 0

COG 6 2 2 1 1

SYM 6 1 4 1

NUM 7 2 0 2 3

BIO 4 4

Thè

me

INRIA Sophia

21

Le site Web de Sophia

•Pages d’un projets-equipe (e.g. AxIS) :

http://www-sop.inria.fr/axis/Publications/

•Ex. de requête (ligne dans le fichier log du serveur www-sop.inria.fr) pour cette page :

200.23.5.196 - - [01/Oct/2005:00:00:03 +0200] "GET /axis/Publications/ HTTP/1.1" 200 3754 "/axis/" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.0; .NET CLR 1.1.4322)« 

•Plus de 62 000 URLs (demandés dans le log d’octobre 2005)

22

Les données log du mois d’octobre 2005pour le site Web d’INRIA Sophia Antipolis

•Données initiales (avant prétraitement) :• 1 328 MO

• 5 840 576 lignes (requêtes)

•Données finales (après prétraitement)• 183 MO

• 845 208 requêtes

• 173 848 sessions = couples (IP, User Agent) = utilisateur

• 258 061 navigations (visites uniques avec des intervalles < 30 minutes entre 2 requêtes)

• 62 721 URLs différents

• dont 22 352 .html externes