Expérimentations et résultats – Extraction de connaissances en WUM

By 4 May 2013

4.6 Expérimentations et résultats

Nous donnons ci-après quelques indices relatifs à l’opération d’acquisition et de préparation de données d’usage que nous avons traité dans cette expérience, ainsi qu’aux résultats de leur segmentation.

4.6.1 Recueil de traces de navigation

Il est difficile de pénétrer dans la vie privée des individus en pistant leur usage du web. Ceci le témoigne le nombre restreint des personnes ayant accepté de participer à l’étude, qui en général appartiennent à un notre entourage le plus proche. De plus, le BHO exploité étant, comme déjà expliqué, désinstallable, nous avons perdu plus de cinq logs pour lesquels les machines concernées ont été réinitialisées. Le tableau suivant montre les propriétés des logs collectés.

N° log Nombre d’utilisateurs Nombre de lignes Taux dans le log  global
Log1 3 38863 0.46
Log2 1 1542 0.02
Log3 1 1813 0.02
Log4 1 27707 0.33
Log5 1 5539 0.07
Log6 1 8757 0.10
Total 8 84221

Figure 18. Quelques caractéristiques des logs collectés

Nous extrayons, dans les deux listes suivantes, parmi les 13700 urls différentes consignées (dont 2121 distinctes au premier niveau de l’url), les 10 tops sites en termes de fréquentation (nombre de visites), et durée de visite (stay time). Ces données confirment les usages courants du web : recherche d’information, communication, navigation, divertissement, téléchargement…etc.

Fréquence des visites Durée de visite
http://www.google.com http://www.mail.live.com
http://www.mail.live.com http://www.google.com
http://www2.jeux.com http://mail.yahoo.com
http://www.mail.yahoo.com http://www.symantec.com/avcenter
http://www.gigapedia.info http://www.echoroukonline.com/ara
http://avunet.free.fr http://www.pdfchm.com/book
http://bntmofeid.com http://www.developpez.net/forums
http://www.toupty.com http://bntmofeid.com
http://www.sciencedirect.com http://www.eclipse.orh
http://www.pdfchm.com/book http://www2jeux.com

Figure 19. Les urls les plus fréquents

4.6.2 Préparation des logs

Les indicateurs de prétraitement des logs sont fonction de la taille du log, des technologies de construction des sites fréquentés, et évidemment des performances de la machine utilisée. Un fichier rapport est généré par l’application consignant les résultats des différentes étapes de la chaîne de traitement. Ce rapport (Cf. annexe n° 3) est complété par plusieurs boites de dialogue informatives à l’issue de chaque étape.

Boite de dialogue informant sur le taux de nettoyage
Figure 20. Boite de dialogue informant sur le taux de nettoyage

Le tableau suivant donne les résultats des différentes étapes, relevés aux fins de confrontation, pour le plus long, et le plus petit des logs (les deux premiers), et pour le log consolidé.

LogsOpération Log1 Log2 Log consolidé
Chargement (nombre de lignes) 38863 1542 84221
Filtrage d’items inutiles
Macs absents 2889 0 3005
Urls invalides 14499 91 19761
Eliminations des évènements pour frames 17938 401 41187
Taux de nettoyage physique 63.99% 27.37% 58.97%
Fenêtres non terminées (nombre) 122 6 428
Surfs reconstruits (nombre) 356 60 1044
Suppression d’items aberrants (MinTime=20 secondes)
Les surfs 43 20 245
Les pages 739 52 2475
Les fenêtres 43 20 248
Taux de compactage de surfs en sessions 45.05% 82.50% 48.94%

Figure 21. Quelques indices de la chaîne de prétraitement

Afin de donner un aperçus sur la complexité des différents algorithmes développés et testés, nous montrons dans le tableau suivant les temps de calcul, précision aux secondes seulement, pour le log consolidé, relevés sur deux machines distinctes.

MachinesTâches AMD Duron à 900 MH,256 MO RAM P4, 1 GO deRAM
Chargement 23’ et 35’’ 5’ et 56’’
Filtrage d’items inutiles 3’ et 10’’ 4’ et 32’’
Eliminations des évènements pour frames 1h, 14’ et 32‘’ 25’ et 35’’
Nettoyage physique 8’ et 15’’ 6’ et 36’’
Détection des fenêtres non terminées 39’ et 42’’ 14’ et 45‘’
Reconstruction de surfs 6’ et 8’’ 3’ et 48’’
Suppression d’items aberrants(MinTime=20 secondes) 0’ et 14’’ 0’ et 16’’
Compactage de surfs en sessions 0’ et 55’’ 0’ et 19’’

Figure 22. Temps de calcul sur deux machines distinctes

4.6.3 Segmentation

Dans notre application nous avons prévu de générer les fichiers nécessaires à l’alimentation des outils d’ECD décrits plus haut. Le module de génération de ces fichiers les produits formatés selon plusieurs options : éléments à inclure, prise en compte ou non des durées de visites, normalisation des valeurs, fenêtre maximale pour chaque item…etc.

Paramètres exploités dans l’alimentation des outils ECD
Figure 23. Paramètres exploités dans l’alimentation des outils ECD

Les clusters (en nombre de 6) obtenus par ESOM sont illustrés dans la figure suivante.
Les données utilisées dans ce résultat sont les identifiants de pages uniquement.

La carte obtenue par ESOM-DataBionic
Figure 24. La carte obtenue par ESOM-DataBionic

Les sessions groupées en 9 segments, pour simplifier selon seulement la période de début de navigation et les catégories des deux premières pages, générés par Tanagra en passant par une ACP, sont montrées dans la figure suivante.

La carte obtenue par Tanagra
Figure 25. La carte obtenue par Tanagra

Nous donnons ci-dessous une présentation des propriétés de chaque cluster constituant la carte de la figure N° 25.

Cluster N° 120 sessions effectuées dans les 3 périodes de la journée (M/S/N). concernent des pages de Recherche, ou autres non classées suivies de séances De RI (google/msn), ou de Mail (hotmail, Yahoo), ou encore des téléchargements Cluster N°2De 4 sessions la nuit (N) pour des téléchargements et des jeux Cluster N° 338 sessions, la nuit (N) pour des Mail (hotmail), en passant par msn, ou yahoo mail, en retournant vers Yahoo ! france
Cluster N° 433 sessions le matin ou le soir (M/S) pour des jeux, forums, téléchargements et des sites algériens Cluster N° 580 sessions le soir (S), pour des RI (msn/google) puis web arab ou Mail yahoo suivi de Yahoo ! France ou msn Cluster N° 68 sessions la nuit (N), RI google ou Yahoo mail, suivi de pages de téléchargement et développement
Cluster N° 746 sessions le matin (M), pour des séances de RI msn puis Mail via Hotmail, ou Mail Yahoo, puis Yahoo ! France, forums, des téléchargement ou Jeux Cluster N° 836 sessions le soir (S), pour des séances de RI msn puis Mail via Hotmail, ou Mail Yahoo, puis Yahoo ! France, des forums, des téléchargement ou Jeux Cluster N° 927 sessions dans toute les périodes de la journée (M/S/N), pour RI (msn/google), suivies de Recherche, sites algériens, autres non classées

Figure 26. Différents segments de la carte obtenue

Conclusion générale et perspectives :

Compte tenu du succès flagrant du web, de gigantesques fichiers de traces de navigation laissées par les internautes durant leurs surfs sont continuellement générés. L’analyse de ces fichiers volumineux par les techniques de la fouille de données, appelée Web Usage Mining, peut fournir des connaissances très utiles. Ces dernières peuvent servir dans divers domaines, tels que la personnalisation de sites web, l’amélioration du trafic dans les réseaux, l’analyse de sécurité…etc.

Les objectifs que nous nous sommes fixés en menant cette étude consistent tout d’abord à explorer le domaine du Web Usage Mining à travers ses principaux travaux, ses applications, et ses liens avec les domaines connexes, et ensuite de forger une approche un peu différente.

A l’opposé des méthodes de fouille de logs centrés serveur, nous avons pu monter un framework de WUM en adoptant une approche centré utilisateur. Cet environnement inclut trois composants : un collecteur de traces de navigation coté client, et une application de prétraitement de données que nous avons développés, auxquels il a été greffé un outil libre d’extraction de connaissances.

Si le problème de la disponibilité des données à analyser ne se pose pas dans les approches centrées serveur, où leur recueil est assuré automatiquement, nous avons montré dans ce mémoire, que cette question constitue l’un des obstacles majeurs qu’il faut surmonter, si nous adoptons une méthode centrée utilisateur. A cet effet, un outil léger reposant sur les BHO a été implémenté. Il présente de nombreux avantages en vue de garantir la réussite de l’opération de collecte de traces. Ce dispositif comporte, néanmoins quelques insuffisances. En effet, la version actuelle, outre qu’elle est tributaire à la coopération de l’usager, elle est trop dépendante à son environnement.

De plus, les données produites peuvent être accessibles aux utilisateurs et manquent ainsi de protection.

Il serait intéressant d’améliorer, dans des versions futures, l’efficacité de l’outil de collecte de traces de navigation, en songeant par exemple de le combiner avec d’autres techniques de recueil de données, telles que les packets-sniffers, ou des modules distants, si un domaine spécifié est l’objet de l’analyse. Il est également primordial de revoir le format du fichier log, et d’y attacher des stratégies de sécurité. La mise en place d’un serveur et d’une base de données sur le Web pour la collecte et le transfert de ces traces, en veillant à optimiser l’usage de la connexion Internet du client, permettrait d’accroître la fiabilité de l’étape de recueil de données.

La deuxième préoccupation, après celle de la disponibilité des traces, concerne la qualité des données recueillies. Dans cette étude, nous avons confirmé que les logs issues des postes clients sont, à leurs tours et à l’instar des logs serveur, inconsistants et requièrent une préparation sérieuse. Plus de 80% du temps consacré à ce travail a été alloué à cette phase fondamentale. Une application de prétraitement englobant différents modules a été élaborée pour atteindre cet objectif. Plusieurs algorithmes, originaux et propres au format de données défini dans l’étape d’acquisition de traces, pour le nettoyage, la reconstruction de surfs, et le formatage y sont implémentés.

Nous pensons que ces modules fixent la majorité des incohérences décelées, hormis celles exigeant des connaissances à l’échelle planétaire du web, ou un temps de réflexion et d’expérimentation considérable, comme les requêtes publicitaires et les frames, pour lesquelles nous avons tenté de proposer des heuristiques. Notons, que la phase de prétraitement peut être allégée, si les tâches préliminaires de filtrage et de formatage simple seraient intégrées dans l’outil d’acquisition de données.

La phase de découverte de connaissances, quant à elle, a consisté à alimenter des outils libres d’ECD, en respectant les formats des fichiers exigés en entrée, et ainsi d’exploiter les résultats qu’ils fournissent.

Les résultats prototypiques obtenus, comme nous pouvons remarquer, ne sont pas totalement évidents, ceci n’est pas surprenant vis-à-vis de la nature du log qui a fait l’objet de nos expérimentations. En effet, le log traité enregistre les traces de navigation d’un nombre très limité d’utilisateurs, ayant presque tous un profil identique, pendant une durée relativement courte. De plus, et pour des raisons de simplification de légers remaniements ont été opérés sur le log consolidé consistant à éliminer les logs ayant une contribution insignifiante, ceci afin d’écarter le bruit qu’ils peuvent engendrer. Par ailleurs, la séparation des segments produits n’est pas perceptible du fait que les logs ramassés, comme confirmer ultérieurement par nos usagers, ne reflètent pas contrairement à ce qui est attendu les motifs d’accès d’une seule personne, mais des requêtes entremêlées de plusieurs utilisateurs partageant la même machine en utilisant le même compte système, contrairement aux consignes qui leurs ont été données.

Finalement, et c’est le plus important à notre avis, la fonction de similarité utilisée dans le regroupement des surfs est la distance euclidienne. Celle-ci ne peut représenter de manière fidèle les proximités réelles entre motifs d’accès. L’incorporation des données sémantiques, à la fois dans la phase de prétraitement et d’extraction de connaissances, permettrait sans doute l’obtention de résultats plus significatifs et explicites. Cet axe, en puisant des avancées dans le domaine du web sémantique, et en ciblant un domaine spécifié avec l’exploration d’autres techniques de fouille, et impliquant une population plus large pendant une durée plus longue, peut être retenu comme l’une des extensions majeures à ce travail. Plus particulièrement nous envisageons, dans la suite, d’affiner d’abord la mesure de similarité afin d’améliorer la qualité de la segmentation. L’approche sera intégrer dans plusieurs applications dans une perspective de personnalisation. A titre d’exemple l’association de l’aspect usage de cette étude, avec un mécanisme d’expansion de requêtes des utilisateurs fondé sur un thésaurus dédié dans le cadre de la de la recherche d’information sur le web, permettra d’accroître la qualité de la fonction de recherche. L’approche peut aussi être intégrée dans des modules d’assistance à la navigation, ou dans l’adaptation à l’expérience de l’utilisateur des plateformes de e-learning. .

Lire le mémoire complet ==> (Prétraitement & Extraction de Connaissances en Web Usage Mining)
S2WC2 : un WUM Framework Centré Utilisateur
Mémoire En vue de l’obtention du diplôme de Magister – Option : Informatique et Communication Electronique
Département des Mathématiques et d’Informatique – Spécialité : Informatique
Université Kasdi Merbah de Ouargla – Faculté des Sciences et Sciences de l’Ingénieur

Table des matières

Introduction générale 1

Introduction 1

Motivations 2

Contributions 4

Organisation du mémoire 4

Chapitre 1 : Fouille de données concepts et terminologie 6

1.1 Facteurs d’émergence 6

1.2 Fouille de données et extraction de connaissances 8

1.2.1 Définitions de la fouille de données : 9

1.2.1.1 Définition 1 9

1.2.1.2 Définition 2 10

1.2.1.3 Définition 3 10

1.2.2 Les tâches en fouille de données 11

1.2.2.1 La description 11

1.2.2.2 L’analyse d’association 12

1.2.2.3 La classification 13

1.2.2.4 La segmentation 14

1.2.2.5 La prédiction 16

1.2.2.6 L’analyse d’exception et de déviation 16

1.3 Processus d’extraction de connaissances 16

1.3.1 Préparation des données 17

1.3.2 Fouille de données 18

1.3.3 Analyse des résultats 18

1.4 Principales techniques de fouille de données 20

1.4.1 Techniques statistiques et probabilistes 20

1.4.1.1 La régression linéaire simple, multiple et logistique 20

1.4.1.2 Les tests statistiques 21

1.4.1.3 L’Analyse en Composante Principale (ACP) 21

1.4.1.4 Les réseaux bayésiens (RB) 22

1.4.2 Les réseaux de neurones (RN) 22

1.4.3 K-means 24

1.4.4 Les plus proches voisins (PPV, kNN) 24

1.4.5 Arbres de décision (Decision tree) 25

1.4.6 Le classificateur naïf de Bayes 26

1.4.7 Algorithme Apriori de recherche de règles associatives 27

1.4.8 Autres techniques 28

1.5 Limites de la fouille de données et sujets ouverts 28

Chapitre 2 : De la fouille de données a la fouille du Web 30

2.1 Préambule 30

2.2 Propriétés des données du web 31

2.2.1 La taille énorme 31

2.2.2 L’hétérogénéité 32

2.2.3 La distribution 32

2.2.4 La non structuration 32

2.2.5 La dynamicité 33

2.2.6 L’hyper-liaison 33

2.3 Taxonomie pour le web mining 33

2.3.1 Web content mining 34

2.3.1.1 Découverte de ressources 35

2.3.1.2 Extraction, sélection et prétraitement 35

2.3.1.3 Généralisation 36

2.3.1.4 Analyse 37

2.3.2 Web structure mining 37

2.3.2.1 PageRank 37

2.3.2.2 HITS 38

2.3.3 Web usage mining 39

2.4 WEB MINING ET DOMAINES CONNEXES 40

2.4.1 Web mining et recherche d’information (WM&RI) 40

2.4.2 Web mining et bases de données (WM&BDD) 42

2.4.3 Web mining et approche agent (WM&AGENTS) 43

2.4.4 Web mining et Web sémantique (WM&WS) 44

Chapitre 3 : WEB USAGE MINING, Etat de l’art et problématique 46

3.1 Introduction 46

3.2 Etude du comportement des utilisateurs sur le web 46

3.3 Processus standardise en WUM 48

3.3.1 Définitions 49

3.4 Recueil de données 51

3.4.1 Recueil coté serveur (1-site : N-utilisateurs) 51

3.4.2 Recueil coté Proxy (N-sites : M-utilisateurs) 53

3.4.3 Recueil coté client (N-sites : 1-utilisateur) 54

3.5 Prétraitement 55

3.5.1 Nettoyage 57

3.5.2 Reconstruction de sessions 60

3.5.2.1 Identification des utilisateurs 60

3.5.2.2 Détermination des sessions 62

3.5.2.3 Complétude des parcours de navigation 63

3.5.3 Formatage 64

3.5.4 Intégration d’autres données 65

3.6 Extraction de connaissances et applications 66

3.6.1 L’analyse statistique 66

3.6.2 OLAP 68

3.6.3 Les règles associatives 68

3.6.4 La segmentation 70

3.6.5 La classification 73

3.6.6 Les motifs séquentiels 74

3.7 Analyse des connaissances 77

3.8 WUM et vie privée 78

Chapitre 4 : S2WC2, un Framework pour la segmentation de sessions web cote client 80

4.1 Introduction 80

4.2 Architecture 80

4.3 Collecteur de traces de navigation 82

4.3.1 Approche 83

4.3.2 Avantages & inconvénients 83

4.3.3 Schéma du fichier log 85

4.4 Prétraitement 89

4.4.1 Nettoyage 90

4.4.1.1 Fusion et export vers une base de données 90

4.4.1.2 Traitement des urls 92

4.4.1.3 Filtrage des items inutiles 93

4.4.1.4 Question des pages avec frames 95

4.4.2 Reconstruction des surfs 97

4.4.2.1 Détection et résolution des fenêtres non terminées 98

4.4.2.2 Algorithme de sessionisation 99

4.4.2.3 Des surfs aux sessions 102

4.4.3 Formatage 103

4.4.3.1 Calcul des durées de visite 104

4.4.3.2 Post filtrage des items insignifiants ou aberrants 104

4.4.4 Traitement du contenu 105

4.4.4.1 Catégorisation semi-automatique de pages 105
4.5 Segmentation 106
4.5.1 Mesures de similarité 107
4.5.1.1 Similarité entre pages web 107
4.5.1.2 Similarité entre surfs web 109
4.5.2 Modélisation 109
4.5.3 Les cartes de Kohonen 110
4.5.4 Outils libres d’ECD 111
4.5.4.1 Weka 111
4.5.4.2 Tanagra 112
4.5.4.3 ESOM DataBionic Tools 112
4.6 Expérimentations et résultats 113
4.6.1 Recueil de traces de navigation 113
4.6.2 Préparation des logs 114
4.6.3 Segmentation 116
Conclusion générale et perspectives