Université de la Manouba
Ecole Nationale des Sciences de l'Informatique
Cycle des Etudes Doctorales
Mémoire de Mastère

présenté en vue de l'obtention du
Diplôme de Mastère en Informatique

Option : Génies Documentiel et Logiciel
Par
Malika CHARRAD

Techniques d'extraction de connaissances appliquées aux

données du Web

Réalisé au sein du

Laboratoire de Recherche en Génies Documentiel et Logiciel

sous l'encadrement du
Professeur Mohamed BEN AHMED (RIADI)
&
le co-encadrement du
Professeur Yves LECHEVALLIER (INRIA)

Soutenu le Samedi 17 Décembre 2005 devant le jury d'examen :

Pr. Khaled GHEDIRA : Président

Dr. Naoufel KRAIEM : Examinateur

Pr. Mohamed BEN AHMED : Encadrant Pr. Yves LECHEVALLIER : Invité

« J'apprends encore, mon instruction n'est point encore achevée. Le cours de ma vie n'est
qu'une longue éducation »

C.A. Helvétius

A tous ceux qui me sont chers, Je dédie ce travail

Remerciements

Que Monsieur Mohamed BEN AHMED, professeur à l'Ecole Nationale des Sciences de l'Informatique et directeur du laboratoire RIADI, trouve ici le témoignage de ma profonde reconnaissance. Ses encouragements, mais aussi ses critiques, ont largement contribué à l'aboutissement de ce mémoire. Je le remercie vivement de m'avoir toujours poussé vers l'avant.

Je tiens également à remercier Monsieur Yves LECHEVALLIER, professeur chercheur à l'Institut Nationalde Recherche en Informatique et Automatique (INRIA), non seulement pour ses précieux conseils et ses orientations, mais aussi pour sa disponibilité. Sa sensibilisation à la recherche et à l'innovation m'ont aidé à la réalisation de ce travail.

Mes remerciements vont également aux membres du jury d'avoir accepté d'évaluer mon travail.

Qu'il me soit permis de remercier également mes amis et mes collègues qui, tous d'une manière différente, mais toujours dans un but constructif, ont contribué à ce que je puisse aboutir à la réalisation de ce

mémoire.

Enfin, merci à mes parents pour le soutien et l'encouragement qu'ils m'ont apporté tout au long de travail.

Résumé- La croissance de l'usage du WWW fût accompagnée d'un intérêt particulier à l'analyse des données de l'usage de l'Internet afin de bien servir les utilisateurs du Web et leur présenter un contenu personnalisé. Un des axes les plus importants du Web mining est le Web Usage Mining qui s'intéresse à l'extraction des patrons d'accès au Web à partir des données de l'usage. L'approche que nous proposons dans le cadre de ce mémoire afin d'aider à comprendre le comportement des internautes comporte trois phases : prétraitement des fichiers Logs, classification des pages et classification des internautes. Dans la phase de prétraitement, les requêtes sont organisées en visites qui représentent les unités d'interaction entre les utilisateurs du Web et le serveur web. Dans la phase de classification des pages, une représentation interne du site Web est créée à partir des fichiers Logs afin d'extraire des chemins de navigation. Des paramètres introduits à partir des statistiques sur les accès aux pages sont utilisés pour la catégorisation des pages Web en pages auxiliaires et pages de contenu. Les requêtes aux pages de contenu servent à la découverte des motifs de navigation. Afin de construire des segments d'utilisateurs, deux méthodes hybrides de classification automatiques basées sur l'analyse en composantes principales, l'analyse des correspondances multiples et les cartes topologiques de Kohonen sont appliquées aux visites. Une expérience effectuée sur les fichiers Logs extraits du Centre de Calcul elKhawarizmi prouve l'efficacité de cette méthodologie.

Abstract- With the ever growing usage of the WWW, there is significant interest in analyzing web usage data to better serve users, and apply the knowledge to be able to present personalized content for different user segments. An important area in web mining is web usage mining, the discovery of patterns in the browsing and navigation data of web users. The approach we proposed to help understand users' behaviors on a web site consists of three steps: preprocessing of log files, web pages classification and users clustering. In Preprocessing, requests to the web site are processed to be organized into sessions which represent units of interaction between web users and the web server. In pages classification, an internal representation of the web site is created from logs to extract frequent paths and parameters are introduced from pages access statistics to help classify web pages into two major categories: auxiliary pages and content pages. Requests to content pages are used to discover browsing patterns. In order to build users' profiles, two hybrid clustering methods based on Principle Component Analysis, Multiple Correspondences Analysis and Self Organizing maps are applied to web usage sessions. An Experiment on the HTTP log files extracted from the Center of Calculation elKhawarizmi web server shows that the approach is efficient and practical.

Table des figures

2.1 Schéma illustratif des champs d'une requête 10

2.2 Exemple d'arbre d'un site 12

3.1 Processus du Web Usage Mining 15

3.2 Réseau linéaire de compétition de type »gagnant emporte tout» 26

4.1 Architecture de la carte de Kohonen 37

4.2 Caractéristiques d'un neurone de la grille de Kohonen 37

4.3 Algorithme de Kohonen 39

5.1 Processus de prétraitement 46

5.2 Processus de transformation des fichiers Log 50

5.3 Algorithme d'identification des utilisateurs 50

5.4 Algorithme d'identification des visites 52

5.5 Fichier Log avant transformation 53

5.6 Exemple d'exécution de l'algorithme d'identification des visites . 53

5.7 Fichier Log après transformation 54

5.8 Exemple de pages contenant plusieurs images 54

5.9 URLs des images contenues dans la page 55

5.10 Algorithme de filtrage des visites et des requêtes 55

5.11 Succession chronologique des étapes de prétraitement 59

5.12 Schéma relationnel 60

5.13 Fichier d'enregistrement d'accès 61

6.1 Exemple de visite 64

6.2 Indexation des pages de la visite 64

6.3 Arbre du site 65

6.4 Matrice d'hyperliens 65

6.5 Matrice d'accès 66

6.6 Projection des variables sur les axes factoriels 68

6.7 Projection des individus sur les axes factoriels 68

6.8 Caractérisation des pages 69

6.9 Classification des pages 69

6.10 Etapes de classification des utilisateurs 70

TABLE DES FIGURES ii

6.11 Etapes de classification des requêtes 70

6.12 Projection de la variable »Statut_200» sur les deux premiers axes

factoriels 71 6.13 Projection de la variable »plateforme» sur le troisième plan factoriel 71 6.14 Grille résultant de l'application des cartes de Kohonen 72 6.15 Caractérisation des classes résultant de l'application des cartes de

Kohonen 73

6.16 Carte de Kohonen après division en aires logiques et labellisation 73

6.17 Etapes de classification des visites 74

6.18 Résultat de l'application de l'ACP à la base des visites 75

6.19 Résultat de la classification des visites 75

6.20 Visite à classifier 77

7.1 Analyse en composantes principales à l'aide de SPAD 80

7.2 Hybridation des méthodes à l'aide de Tanagra 80

7.3 Représentation de la carte dans les deux espaces d'entrée et de sortie 82
7.4 Etats de la carte en fonction du nombre d'itérations. 83

Liste des tableaux

Table des matières

1 Introduction 1

1.1 Contexte 1

1.2 Description du problème 2

1.3 Contribution du mémoire 2

1.4 Plan du mémoire 3

TABLE DES MATIÈRES vi

6 Classification des utilisateurs 63

6.1 Classification des pages 63

6.1.1 Reconstruction de la topologie du site 63

6.1.2 Matrice d'hyperliens 65

6.1.3 Matrice d'accès 66

6.1.4 Collecte d'informations sur les accès 67

6.1.5 Application de l'analyse en composantes principales . . . 67

6.2 Classification des utilisateurs 69

6.2.1 Découverte de motifs de navigation 70

6.2.2 Construction de groupes d'utilisateurs 74

6.3 Procédure de classification d'une visite 76

6.4 Conclusion 77

7 Outils d'investigation 78

7.1 Langage SQL 78

7.2 Logiciels d'analyse des données et de classification 79

7.3 Matlab pour la visualisation des cartes de Kohonen 80

7.4 Conclusion 83

8 Conclusion 84

Bibliographie 86

Netographie 90

Glossaire 91

III Annexes 94

Chapitre 1

Introduction

La caractérisation des internautes fréquentant un site Web et l'identification de leurs motifs de navigation est un problème incontournable pour les concepteurs de sites Web qui visent à assister l'internaute, prédire son comportement et personnaliser la consultation. Ces trois considérations ont motivé d'importants efforts dans l'analyse des traces des internautes sur les sites Web et l'adaptation des méthodes de classification aux données du Web durant ces dernières années. Le présent travail s'inscrit dans ce courant de recherche, en proposant une méthodologie de traitement des fichiers Logs permettant d'étudier le comportement des utilisateurs d'un site Web et ce en exploitant différentes méthodes de classification, en particulier les cartes topologiques de Kohonen.

1.1 Contexte

Au cours de ces dernières années, avec la croissance exponentielle du nombre des documents en ligne et des nouvelles pages chaque jour, le Web est devenu la principale source d'information. Ce développement a entraîné une croissance rapide de l'activité sur le Web, et une explosion des données résultant de cette activité. En effet, le nombre des utilisateurs d'Internet dans le monde a atteint 938.7 millions au mois de Juillet 2005¹, ce qui correspond à un taux de pénétration de 14.6% et le nombre de sites Web a atteint 70.39 millions au mois d'Août 2005, soit une augmentation de 2.8 millions par rapport au mois de juillet selon l'enquête de Netcraft². Pour analyser ce nouveau type de données, sont apparues de nouvelles méthodes d'analyse regroupées sous le terme »Web Mining» dont les trois axes de développement actuels sont le Web Content Mining (WCM) qui s'intéresse à l'analyse du contenu des pages Web, le Web Structure Mining (WSM), qui s'intéresse à l'étude des liens entre les sites Web et le Web Usage Mining (WUM) qui s'intéresse à l'étude de l'usage du Web.

¹www. Internetworldstats.com 2www.netcraft.com

Cette dernière branche du Web Mining, définie comme étant l'application du processus d'Extraction des Connaissances à partir de bases de Données (ECD) aux données issues des fichiers Logs HTTP est devenue une pratique de plus en plus courante et indispensable. En effet, les créateurs des sites Web intéressés par la fidélisation des internautes fréquentant leurs sites et cherchant à attirer de nouveaux visiteurs ont besoin d'analyser le comportement des internautes afin d'extraire des patrons d'accès au Web en vue d'une amélioration et une personnalisation des sites.

1.2 Description du problème

Récemment, de nombreux travaux en Web Usage Mining ont été menés. Certains de ces travaux se sont concentrés sur l'étude de la première phase du processus du WUM à savoir le prétraitement des données [Tan, 03], d'autres, se sont intéressés à la détermination des modèles comportementaux des internautes fréquentant les sites Web. Ce second axe est le centre d'intérêt de notre travail de recherche, objet du présent mémoire. En effet, en supposant qu'il existe une certaine corrélation entre les différentes pratiques des visiteurs sur un site donné et leurs caractéristiques personnelles, notre objectif consiste à construire des profils de navigation enrichis de traits d'utilisateurs. En d'autres termes, nous cherchons à identifier et à qualifier des groupes d'utilisateurs par rapport à leurs motifs de navigation sur un site donné ou des traits représentant des centres d'intérêts. Ce problème de classification a été traité dans de nombreux travaux en appliquant différentes méthodes : BIRCH³ dans [Fu, 00], CLIQUE dans [Per, 98], EM⁴ dans [Cad, 00], une classification non supervisée basée sur un réseau de neurones dans[Ben, 03]. Notre propos dans cette étude consiste à transformer les données présentes dans les fichiers Logs d'un site Web en des connaissances utiles en procédant à un prétraitement de ces fichiers et à une classification non supervisée des visites effectuées par les internautes, basée sur l'algorithme des cartes topologiques de Kohonen et ce afin d'identifier des typologies de visites explicatives du comportement des utilisateurs sur le site Web.

1.3 Contribution du mémoire

Nous proposons dans ce mémoire une méthodologie de traitement des fichiers Logs permettant de passer d'un ensemble de requêtes enregistrées dans les Logs à un modèle comportemental des utilisateurs du site Web en considération. L'apport de ce travail réside principalement dans trois points:

³Balanced Iterative Reducing and Clustering using Hierarchies ⁴Expectation-Maximization algorithm

- Proposer une méthodologie détaillée de prétraitement des fichiers Logs : proposer des heuristiques d'identification des robots Web, des algorithmes pour l'identification des sessions et des visites.

- Associer la classification des pages à la classification des usagers du site Web. En d'autres termes, exploiter les résultats de la classification des pages dans la classification des internautes.

- Intégrer et combiner différentes techniques de fouille des données pour la classification des utilisateurs.

1.4 Plan du mémoire

Ce mémoire est organisé en deux parties distinctes. La première partie présente une étude de l'art sur le Web Mining, le Web Usage Mining et les méthodes de classification, objets des trois premiers chapitres. La seconde partie composée des trois derniers chapitres est consacrée à la présentation de la méthodologie proposée pour l'extraction des connaissances à partir des fichiers Logs et les résultats de son application sur des données réelles. Plus précisément, le quatrième chapitre est dédié au prétraitement des fichiers Logs permettant d'aboutir à des données structurées et prêtes à l'application des méthodes de fouille des données. Le cinquième chapitre présente les résultats de l'application de ces méthodes sur les données des fichiers Logs du Centre de Calcul elKhawarizmi. Le dernier chapitre présente l'ensemble des outils utilisés pour le prétraitement et la classification.

Première partie

Etat de l'art

Chapitre 2

Web Mining et Web Usage

Mining

Le Web Mining, défini comme l'application des techniques du Data Mining* aux données du Web (documents, structure des pages, des liens...), s'est développé à la fin des années 1990 afin d'extraire des informations pertinentes sur l'activité des internautes sur le Web. Dans ce chapitre, structuré en deux sections, nous présentons dans la première le Web Mining, en particulier ses objectifs et les axes de son développement. Dans la seconde, nous nous intéressons au troisième axe de développement du Web Mining, le Web Usage Mining, en particulier les motifs du WUM, les données de l'usage et les diverses approches d'analyse.

2.1 Web Mining

Le Web Mining poursuit deux principaux objectifs:

1. L'amélioration et la valorisation des sites Web : L'analyse et la compréhension du comportement des internautes sur les sites Web permet de valoriser le contenu des sites en améliorant l'organisation et les performances des sites.

2. La personnalisation: Les techniques de Data Mining appliquées aux données collectées sur le Web permettent d'extraire des informations intéressantes relatives à l'utilisation du site par les internautes. L'analyse de ces informations permet de personnaliser le contenu proposé aux internautes en tenant compte de leurs préférences et de leur profil.

2.1.1 Processus du Web Mining

Le processus du Web Mining se déroule en trois étapes :

1. Collecte des données sur l'utilisateur,

2. Utilisation de ces données à des fins de personnalisation,

3. Présentation à l'utilisateur d'un contenu ciblé.

Données du Web et leurs sources

[Sri, 00]classifie les données utilisées dans le Web Mining en quatre types :

- Données relatives au contenu : données contenues dans les pages Web (textes, graphiques),

- Données relatives à la structure : données décrivant l'organisation du contenu (structure de la page, structure inter-page),

- Données relatives à l'usage: données fournissant des informations sur l'usage telles que les adresses IP, la date et le temps des requêtes,

- Données relatives au profil de l'utilisateur : données fournissant des informations démographiques sur les utilisateurs du site Web.

Ces données sont généralement stockées dans un Data-Warehouse, appelé data-Webhouse, dont l'objectif de construction est de collecter des données propres à la fréquentation des sites Web afin d'analyser les comportements de navigation. Les principales sources des données permettant d'alimenter les Data-Webhouses sont :

- Les fichiers Logs du serveur Web: il s'agit du journal des connexions qui
conserve une trace des requêtes et des opérations traitées par le serveur.

- Les bases de données clients : ce sont les sources des données des entreprises.

- Les cookies (ou Témoins) : ce sont des fichiers que le serveur d'un site Web glisse au sein du disque dur de l'internaute le plus souvent à son insu (fichiers temporaires ou dossier Cookies) afin de stocker de l'information et mémoriser ses visites. Il permet, par exemple de l'identifier lorsqu'il revient visiter un site régulièrement.

Terminologie

La compréhension du processus du Web Mining nécessite la définition de certains termes qui se répèteront tout au long de ce mémoire. Cette définition est faite sur la base des recommandations du W3C relatives à la normalisation de la terminologie [Lav, 99].

- Une vue de page (ou »page diffusée») est le chargement complet d'une page Web suite à une action de l'utilisateur sur la page (un clic).

- Une session utilisateur est l'ensemble des requêtes explicites effectuées par l'utilisateur durant la période d'analyse.

- Une visite est un sous-ensemble des vues de pages consécutives d'une session durant une connexion. On parle aussi de »navigation». La pratique courante considère qu'une absence de consultation de nouvelles pages sur le site dans un délai excédant 30 minutes met fin à la visite.

- La notion de »visiteur» est à comprendre au sens d'individu. On appelle ainsi »nombre de visiteurs» le nombre d'individus ayant consulté le site pendant une période donnée.

- Un épisode est un sous-ensemble de clics d'une visite pour la réalisation d'un objectif. Il s'agit d'une phase de la navigation.

- Un motif de navigation est un usage du site par ses utilisateurs Limites du Web Mining

Plusieurs problèmes se posent lors d'une étude de Web Mining:

- Le stockage des données requiert de très grands espaces. Il nécessite souvent une machine spécifique.

- L'architecture des sites évolue régulièrement. Par conséquent, il est parfois difficile d'opérer des comparaisons entre les différentes périodes d'analyse.

- La situation géographique des visiteurs est déterminée à partir des extensions des adresses (.fr, .uk,.com,). Cependant une adresse se terminant par .com n'est pas forcément localisée aux Etats-Unis car cette extension est également devenue une extension commerciale.

2.1.2 Axes de développement du Web Mining

Les trois axes de développement du Web Mining sont : le Web Content Mining, le Web Structure Mining et le Web Usage Mining.

Web Content Mining

Le Web Content Mining (WCM) consiste en une analyse textuelle avancée intégrant l'étude des liens hypertextes et la structure sémantique des pages Web. Ainsi, les techniques de description, de classification et d'analyse de chaînes de caractères du Text Mining sont très utiles pour traiter la partie textuelle des pages. Le WCM s'intéresse également aux images. Il permet, par exemple, de quantifier les images et les zones de texte, pour chaque page. Ainsi par l'analyse conjointe de la fréquentation des pages, il est possible de déterminer si les pages contenant plus d'images sont plus visitées que les pages contenant plus de texte.

Web Structure Mining

Il s'agit d'une analyse de la structure du Web i.e. de l'architecture et des liens qui existent entre les différents sites. L'analyse des chemins parcourus permet, par exemple, de déterminer combien de pages consultent les internautes en moyenne et ainsi d'adapter l'arborescence du site pour que les pages les plus recherchées soient dans les premières pages du site. De même, la recherche des associations entre les pages consultées permet d'améliorer l'ergonomie du site par création de nouveaux liens.

Web Usage Mining

Cette dernière branche du Web Mining consiste à analyser le comportement de l'utilisateur à travers sa navigation, notamment l'ensemble des clics effectués sur le site (on parle d'analyse du clickstream). Cette approche permet de mesurer l'audience et la performance d'un site Web (combien de temps passé par page, combien de visites, à quel moment, qui est l'utilisateur, quelle est la fréquence de ses consultations,..). L'intérêt du WUM est d'enrichir les sources de données de l'entreprise (bases de données clients, bases marketing,...) par les données brutes du clickstream afin d'affiner les profils clients ainsi que les modèles comportementaux.

2.2 Web Usage Mining

[Tan, 03] définit le WUM comme étant l'application du processus d'Extraction des Connaissances à partir de bases de Données (ECD) aux données issues des fichiers Logs HTTP afin d'extraire des modèles comportementaux d'accès au Web en vue de répondre aux besoins des visiteurs de manière spécifique et adaptée (personnaliser les services) et faciliter la navigation.

2.2.1 Motifs du Web Usage Mining

Selon [Mic, 02], il y a cinq motifs du WUM :

1. Évaluation et caractérisation générale de l'activité sur un site Web : l'objectif est l'observation et non pas la modélisation. Les techniques d'analyse utilisées sont souvent simples. Elles relèvent, en effet, du dénombrement et des statistiques simples (moyennes, histogramme, indices, tris croisés).

2. Amélioration des modes d'accès aux informations : le WUM permet de comprendre comment les utilisateurs se servent d'un site, d'identifier les failles dans la sécurité et les accès non autorisés.

3. Modification de la structure : le WUM peut révéler le besoin de restructurer des pages et des liens afin d'améliorer la structure du site Web. En effet,

les pages considérées comme similaires par des techniques de classification peuvent être reliées de manière hypertextuelle.

4. Personnalisation de la consultation : cet enjeu important pour de nombreuses applications Internet ou sites de e-commerce consiste à proposer des recommandations dynamiques à un utilisateur en se basant sur son profil et une base de connaissances d'usages connus.

5. Mise en oeuvre de l'intelligence économique: cet objectif concerne en particulier les sites marchands. Il s'agit de comprendre quand, comment et pourquoi l'utilisateur est attiré par ce site, les produits qu'il faut lui proposer à la vente...etc.

2.2.2 Données de l'usage

Les principales données exploitées dans le WUM proviennent des fichiers Logs. Cependant, il existe d'autres sources d'informations qui pourraient être exploitées à savoir les connaissances sur la structure des sites Web et les connaissances sur les utilisateurs des sites Web.

Fichiers Logs HTTP

Présentation des fichiers Log HTTP: Un Log file (en français, journal de bord des connexions ou fichier journal) est un fichier créé par un logiciel spécifique installé sur le serveur Web permettant de garder une trace des requêtes reçues et des opérations effectuées par le serveur. Il existe plusieurs formats des fichiers Logs Web, mais le format le plus courant est le CLF (Common Log file Format). Selon ce format six informations sont enregistrées:

1. le nom du domaine ou l'adresse de Protocole Internet (IP) de la machine appelante,

2. le nom et le login HTTP de l'utilisateur (en cas d'accès par mot de passe),

3. la date et l'heure de la requête,

4. la méthode utilisée dans la requête (GET, POST, etc.) et le nom de la ressource Web demandée (l'URL de la page demandée),

5. le statut de la requête i.e. le résultat de la requête (succès, échec, erreur, etc.),

6. la taille de la page demandée en octets.

Le format ECLF (Extended Common Log file Format), supporté par certains serveurs Web, représente une version plus complète du CLF. En effet, il indique en plus l'adresse de la page de référence (où se trouvait l'internaute lorsqu'il a lancé la requête (referrer)) et l'identification de l'agent client (le nom du navigateur Web et le système d'exploitation).

FIG. 2.1 : Schéma illustratif des champs d'une requête

Problèmes spécifiques aux données des fichiers Logs : Bien que les données fournies par les fichiers Logs soient utiles, il importe de prendre en compte les limites inhérentes à ces données lors de leur analyse et de leur interprétation. Parmi les difficultés qui peuvent survenir:

- Les requêtes inutiles² : Chaque fois qu'il reçoit une requête, le serveur enregistre une ligne dans le fichier Log. Ainsi, pour charger une page, il y'aura autant de lignes dans le fichier que d'objets contenus sur cette page (les éléments graphiques). Un prétraitement est donc indispensable pour supprimer les requêtes inutiles.

- Les firewalls : Ces protections d'accès à un réseau masquent l'adresse IP des utilisateurs. Toute requête de connexion provenant d'un serveur doté d'une telle protection aura la même adresse et ce, quel que soit l'utilisateur. Il est donc impossible, dans ce cas, d'identifier et de distinguer les visiteurs provenant de ce réseau.

- Le Web caching: Afin de faciliter le trafic sur le Web, une copie de certaines pages est sauvegardée au niveau du navigateur local de l'utilisateur ou au niveau du serveur proxy afin de ne pas les télécharger chaque fois qu'un utilisateur les demande. Dans ce cas, une page peut être consultée plusieurs fois sans qu'il y' ait autant d'accès au serveur. Il en résulte que les requêtes correspondantes ne sont pas enregistrées dans le fichier Log.

- L'utilisation des robots : Les annuaires du Web, connus sous le nom de moteurs de recherche, utilisent des robots qui parcourent tous les sites Web

afin de mettre à jour leur index de recherche. Ce faisant, ils déclenchent des requêtes qui sont enregistrées dans tous les fichiers Logs des différents sites, faussant ainsi leurs statistiques.

- L'identification des utilisateurs : L'identification des utilisateurs à partir du fichier Log n'est pas une tâche simple. En effet, en employant le fichier Log, l'unique identifiant disponible est l'adresse IP et »l'agent» de l'utilisateur. Cet identifiant présente plusieurs limites [Sri, 00] :

- Adresse IP unique / Plusieurs sessions serveurs: La même adresse IP peut être attribuée à plusieurs utilisateurs accédant aux services du Web à travers un unique serveur Proxy.

- Plusieurs adresses IP / Utilisateur unique: Un utilisateur peut accéder au Web à partir de plusieurs machines.

- Plusieurs agents / Utilisateur unique : Un internaute qui utilise plus d'un navigateur, même si la machine est unique, est aperçu comme plusieurs utilisateurs.

- L'identification des sessions : Toutes les requêtes provenant d'un utilisateur identifié constituent sa session. Le début de la session est défini par le fait que l'URL de provenance de l'utilisateur est extérieure au site [Lec, 03]. Par contre, aucun signal n'indique la déconnexion du site et par suite la fin de la session.

- Le manque d'information : Le fichier Log n'apporte rien sur le comportement de l'utilisateur entre deux requêtes : Que fait ce dernier? Est-il vraiment en train de lire la page affichée? De plus, le nombre de visites d'une page ne reflète pas nécessairement l'intérêt de celle-ci. En effet, un nombre élevé de visites peut simplement être attribué à l'organisation d'un site et au passage forcé d'un visiteur sur certaines.

Autres sources des données

Connaissances sur le site Web : Les pages d'un site sont matérialisées par une adresse Internet spécifique, appelée adresse d'allocation de la ressource (Uniform Resource Locator). La structure d'un site Internet simple peut être représentée par un arbre dont la racine correspond à la page d'accueil du site.

FIG. 2.2 : Exemple d'arbre d'un site

Chaque point (ou noeud) présente l'adresse d'une page particulière, et les segments reliant ces points indiquent la présence d'un lien hypertexte amenant aux sous-branches immédiates de l'arbre. D'après le schéma ci-dessus, il est possible de retracer le chemin de navigation de l'internaute sur le site. Cependant, il n'est pas toujours aisé de représenter l'architecture d'un site, en particulier les sites complexes.

Connaissances sur les utilisateurs du site : Les connaissances sur les utilisateurs d'un site sont obtenues directement auprès des utilisateurs eux-mêmes dans l'approche panéliste (âge, sexe, ancienneté sur le Web). Dans le cas des sites à base d'inscription, ces connaissances sont recueillies directement à partir du login et du profil de l'utilisateur donnés par l'internaute au moment de l'inscription. Ces données dites explicites, fournies directement par les internautes sont très souvent erronées. Il est également possible d'acquérir des connaissances sur les utilisateurs du site en reconstituant leurs profils en fonction de leurs activités passées sur le Web.

2.2.3 Diverses approches d'analyse

Il existe plusieurs méthodes d'analyse du trafic sur un site Web dont les plus connues sont: l'analyse des Logs, l'analyse distante et les panels.

Analyse des fichiers Logs

L'analyse des fichiers Logs consiste à collecter automatiquement à partir des fichiers Logs les navigations de tous les utilisateurs. Cette analyse permet de quantifier la fréquentation des pages d'un site donné, déterminer les parcours de navigation, les motifs de navigation et les profils des usagers du site considéré. La faiblesse de cette approche est d'offrir peu d'information sur l'utilisateur [Che, 02].

Analyse distante

L'analyse distante repose sur l'utilisation des marqueurs HTML à placer sur chacune des pages du site étudié. Le marquage consiste à placer une petite image (visible ou non) appelée marqueur sur l'ensemble des pages Web à auditer. Le marqueur s'implante sur un site Web afin de compter »les pages chargées». A chaque chargement de page, le marqueur transmet au serveur les données collectées (date et heure de la requête, informations sur le navigateur, résolution de l'écran). Cette méthode fournit une mesure directe de l'information (en temps réel). En revanche, elle nécessite le marquage de toutes les pages, ce qui est presque impossible dans le cas des sites volumineux.

Panels

Cette approche permet d'analyser les usages de l'Internet en utilisant des panels d'utilisateurs représentatifs de la population des internautes. Les données à analyser sont de deux types : d'une part les données personnelles recueillies auprès de chaque panéliste (âge, sexe, ancienneté sur le Web), d'autre part, toutes les activités des panélistes sur Internet suivies et capturées à l'aide d'un logiciel implanté sur leurs ordinateurs. Cette approche présente l'inconvénient de ne pas offrir une étude précise d'un site donné et n'est utilisable que par des sites à très fort trafic.

Autres approches

[Che, 02] propose l'approche SurfMiner qui combine l'approche panéliste et l'approche reposant sur l'analyse des fichiers Logs afin de mettre en évidence les usages d'un site associés à des descriptions d'utilisateurs. Cette approche repose sur l'hypothèse qu'il existe une certaine corrélation entre les pratiques différentes des utilisateurs et leurs caractéristiques personnelles. Elle consiste à extraire des motifs fréquents de navigation des utilisateurs de référence et découvrir des relations entre les motifs découverts et des traits d'utilisateurs.

2.3 Conclusion

Ce premier chapitre a servi d'introduction au domaine lié à notre étude. Nous avons défini certaines notions relatives au Web Mining et plus particulièrement, au Web Usage Mining sur lequel porte notre étude. Le chapitre suivant est consacré à la présentation du processus du Web Usage Mining, en particulier les différentes étapes de ce processus.

Chapitre 3

Processus du Web Usage Mining

Le processus du Web Usage Mining (WUM) est communément divisé en trois étapes principales : prétraitement des données, fouille de données et analyse des résultats. Une étape préalable consiste à collecter les données du Web à analyser. Nous présentons dans ce chapitre chacune de ces étapes ainsi qu'une description détaillée des données et traitements nécessaires à sa réalisation.

3.1 Processus du Web Usage Mining

Le WUM (fig. 3.1) consiste en »l'application des techniques de fouille des données pour découvrir des patrons d'utilisation à partir des données du Web dans le but de mieux comprendre et servir les besoins des applications Web» [Coo, 00]. La première étape dans le processus de WUM, une fois les données collectées, est le prétraitement des fichiers Logs qui consiste à nettoyer et transformer les données. La deuxième étape est la fouille des données permettant de découvrir des règles d'association, un enchainement de pages Web apparaissant souvent dans les visites et des »clusters» d'utilisateurs ayant des comportements similaires en terme de contenu visité. L'étape d'analyse et d'interprétation clôt le processus du WUM. Elle nécessite le recours à un ensemble d'outils pour ne garder que les résultats les plus pertinents.

Serverside data

Intermediary
data

Client-side
data

Collecte des données

Prétraitement des
données

- Nettoyage des données

- Transformation des données

Data Webhouse

Fouille des données

- Méthodes statistiques unidimensionnelles - Méthodes statistiques multidimensionnelles

- Méthodes d'association

- Méthodes basées sur l'IA

Analyse

- Visualisation

- OLAP

- Bases des données relationnelles - Agents intelligents

Personnalisation du Web

Rapport d'évaluation
du Web

FIG. 3.1 : Processus du Web Usage Mining

3.2 Collecte des données

La première phase dans le processus du WUM consiste à collecter les données du Web à analyser. Les deux sources principales des données collectées sont les données enregistrées au niveau du serveur et les données enregistrées au niveau du client. Une autre source consiste aux données enregistrées au niveau du serveur Proxy, intermédiaire dans la communication client-serveur.

3.2.1 Données enregistrées au niveau du serveur

Chaque demande d'affichage d'une page Web de la part d'un utilisateur, peut générer plusieurs requêtes. Des informations sur ces requêtes (notamment les noms des ressources demandées et les réponses du serveur Web) sont stockées dans les fichiers Log du serveur Web. L'enregistrement des données dans les Logs du serveur (server-side Log files) permet d'identifier l'ensemble d'utilisateurs accédant au site Web. De plus, les Logs du serveur fournissent des données sur le contenu, des informations sur la structure et des méta-informations sur les pages Web (taille du fichier, date de la dernière modification) [Sri, 00]. Cependant, les fichiers Log des serveurs Web présentent des problèmes majeurs comme signalé dans le chapitre précédent.

3.2.2 Données enregistrées au niveau du client

Les données sont collectées au niveau du poste client à travers des agents implémentés en Java ou en Java script. Ces agents sont incorporés dans les pages Web (sous forme d'appliquettes java, par exemple) et utilisés pour une collecte directe des informations à partir du poste client (exemples d'informations : le temps d'accès et d'abandon du site, l'historique de navigation) .Une autre technique de collecte des données consiste à utiliser une version modifiée du navigateur [Tau, 97]. Cette technique permet d'enregistrer les pages Web visitées par un utilisateur ainsi que le temps d'accès et le temps de réponse et les envoyer au serveur. La première méthode permet de collecter des données sur un utilisateur navigant sur un seul site Web. Par contre, un browser modifié permet la collecte des données sur un utilisateur navigant sur plusieurs sites Web. Le problème qui se pose dans le second cas est comment convaincre les internautes d'utiliser ce navigateur modifié dans leurs navigations sachant qu'il peut être considéré comme une menace de leur vie privée [Sri, 00]. Les informations enregistrées au niveau du poste client sont plus fiables que les informations enregistrées au niveau du serveur puisqu'elles permettent de résoudre le problème du caching et l'identification des sessions [Pie, 03].

3.2.3 Données enregistrées au niveau du Proxy

Le serveur Proxy joue le rôle d'intermédiaire entre des clients Web et des serveurs Web. C'est également un vaste espace disque servant au stockage des pages Web consultées par les utilisateurs (Web-cache server). En effet, pour toute requête émise sur une page, le Proxy, après consultation de son disque local, transmet la requête au serveur Web si le document n'est pas disponible à son niveau. Une fois l'information retournée par le serveur, le Proxy en effectue une copie locale sur son disque puis la transmet à l'initiateur de la requête. Le serveur Proxy garde la trace de toutes les communications établies dans des fichiers Logs

semblables à ceux des serveurs Web. Ces traces peuvent révéler les requêtes HTTP émises par plusieurs clients vers plusieurs serveurs Web et servir ainsi de source de données pour caractériser le comportement de navigation d'un groupe anonyme d'utilisateurs partageant un même serveur Proxy [Sri, 00]. Cependant, les mêmes problèmes cités précédemment (problème du caching et d'allocation des adresses IP) sont présents au niveau du Proxy. Le tableau suivant présente les différents niveaux de collecte des données résultant de la navigation d'un ou de plusieurs utilisateurs sur un ou plusieurs sites.

TAB. 3.1 : Niveaux de collecte des données

3.3 Prétraitement des données

Le prétraitement des données se décompose en deux phases principales : une phase de nettoyage des données et une phase de transformation.

3.3.1 Nettoyage des données

Le nettoyage des données est une étape cruciale dans le processus du WUM en raison du volume important des données enregistrées dans les fichiers Log Web. En effet, la dimension de ces fichiers dans les sites Web et les portails Web très populaires peut atteindre des centaines de géga-octets par heure. L'étape du nettoyage consiste à filtrer les données inutiles à travers la suppression des requêtes ne faisant pas l'objet de l'analyse et celle provenant des robots Web. La suppression du premier type de requêtes dépend selon [Tan, 03] de l'intention de l'analyste. En effet, si son objectif est de trouver les failles de la structure du site Web ou d'offrir des liens dynamiques personnalisés aux visiteurs du site Web, la suppression des requêtes auxiliaires comme celles pour les images ou les fichiers multimédia est possible. Par contre, quand l'objectif est le »Web pre-fetching* », il ne faut pas supprimer ces requêtes puisque dans certains cas les images ne sont pas incluses dans les fichiers HTML mais accessibles à travers des liens, ainsi l'affichage de ces images indique une action de l'utilisateur.

La suppression du second type de requêtes i.e. les entrées dans le fichier Log produites par les robots Web (WR) permet également de supprimer les sessions non intéressantes. En effet, les WRs suivent automatiquement tous les liens d'une page Web. Il en résulte que le nombre de demandes d'un WR dépasse en général le

nombre de demandes d'un utilisateur normal. [Tan, 03] a utilisé trois heuristiques pour identifier les requêtes et les visites issues des WRs :

1. Identifier les adresses IPs qui ont formulé une requête à la page »robots .txt».

2. Utiliser des listes des »User agents» connus comme étant des WRs.

3. Utiliser un seuil pour »la vitesse de navigation» BS (Browsing Speed), qui représente le rapport entre le nombre de pages consultées pendant une visite de l'utilisateur et la durée de la visite. Si BS est supérieure à deux pages par seconde et la visite dépasse 15 pages, alors la visite a été initiée par un WR.

3.3.2 Transformation des données

Cette phase regroupe plusieurs tâches telles que l'identification des utilisateurs et des sessions et l'identification des visites.

Identification des utilisateurs et des sessions

Plusieurs méthodes ont été proposées pour identifier les internautes:

L'adresse IP Les adresses IP toujours disponibles et ne nécessitant au-

cun traitement préalable peuvent être utilisées pour identifier les internautes. Cependant, leur utilisation présente principalement deux limites. D'une part, les internautes utilisant un serveur Proxy sont identifiés par l'unique adresse IP de ce serveur. Ainsi, le site visité ne peut déceler s'il s'agit d'un ou de plusieurs visiteurs. D'autre part, l'attribution dynamique des adresses IPs ne permet une identification valable que pour une seule session ininterrompue i.e. si l'internaute interrompt sa visite en se déconnectant un bref instant, son adresse IP aura changé bien qu'il s'agit toujours du même utilisateur.

Les Cookies (Client Side Storage) Ces fichiers peuvent contenir des

information telles que la date et l'heure de la visite, la page visitée, un code d'identification du client, .. etc. Chaque fois que l'utilisateur introduit une URL, le navigateur parcourt les cookies. Si l'un d'entre eux contient cette URL, la partie du cookie contenant les données associées est transférée conjointement à la requête afin de permettre au serveur d'identifier la provenance de cette requête. Cette méthode présente plusieurs avantages. En effet, les cookies permettent une identification s'étalant sur plusieurs sessions. Ils permettent également de stocker plus qu'un simple code d'identification et de collecter et d'enregistrer des informations directement exploitables par le serveur (comme le mot de passe); Cependant, l'identification par cookies présente des inconvénients. D'une part, les

cookies identifient la machine, et non l'utilisateur¹, d'autre part, ils nécessitent l'acceptation de l'utilisateur qui peut à tout moment désactiver leur chargement. Deux autres problèmes sont également à considérer. Le premier est celui des firewalls qui peuvent interdire l'écriture de cookies. Le second est relié au nombre limité des cookies. En effet, un client ne peut pas avoir plus de 300 cookies sur son disque et un serveur ne peut créer que 20 cookies maximum chez le client.

Le Mot de passe Pour qu'un serveur puisse identifier un visiteur de

manière certaine, l'internaute doit s'identifier lui-même à l'aide d'un pseudonyme (Login) et un mot de passe (Password). Ainsi, le serveur est sûr de l'identité de son visiteur. Cette technique permet d'identifier les internautes de façon permanente et fiable mais elle requiert la participation de l'utilisateur et ne peut être réalisée à son insu. Le serveur devra donc attendre que son visiteur s'enregistre et ne pourra profiter des requêtes effectuées en dehors de l'identification. Pour remédier à cet inconvénient, les mots de passe et les pseudonymes sont souvent enregistrés dans un cookie. L'indentification établie lors d'une session ultérieure portera alors sur la machine et non plus sur l'utilisateur².

L'identifiant de session Les identifiants de session permettent à un site

entièrement dynamique d'identifier les internautes individuellement. Ils reposent sur la technologie PHP. Cette technique permet d'attacher un identifiant à chacun des liens hypertextes présents sur une page. Lors de la première requête émise, le serveur attribue arbitrairement à cette requête un identifiant de session, la réponse du serveur sera une page préparée dynamiquement. Le serveur peut ainsi insérer l'identifiant de session dans tous les liens hypertextes de cette page. Lorsque l'utilisateur clique sur l'un de ces liens, sa requête contiendra automatiquement l'identifiant qui lui a été attribué au départ. Cette technique est très fiable mais limite l'identification du visiteur à une seule session.

D'autres méthodes ont été proposées afin de résoudre le problème de l'identification de l'utilisateur. Dans [Coo, 99], la méthode proposée combine l'utilisation de la topologie du site et des informations contenues dans le referrer. Si une requête de page provient de la même adresse IP que les requêtes précédentes sans qu'il y'ait d'hyperliens directs entre les pages demandées, alors l'utilisateur n'est plus le même. Cependant cette méthode n'identifie pas complètement l'utilisateur. [Sch, 01] emploie une technique différente pour identifier l'utilisateur. Cette technique consiste à inclure, pour chaque utilisateur, un identifiant unique généré par le serveur Web dans les URLs des pages Web du site. Cependant, cette technique nécessite l'intervention de l'internaute qui doit créer un signet, qui inclut

¹Si plusieurs personnes utilisent un même ordinateur, la pertinence du cookie est fortement réduite. De même, si une personne emploie plusieurs ordinateurs, le site est incapable de reconnaître l'utilisateur. Le cookie est donc inadapté à la mobilité des internautes.

²Un utilisateur différent peut cependant accéder au site sous la même identité.

l'identifiant comme une partie de l'URL dans l'une des pages afin d'identifier l'utilisateur s'il revient au site.

Le tableau ci-dessous proposé par [Gav, 02] présente une comparaison entre les principales techniques d'identification des internautes.

TAB. 3.2 : Principales techniques d'identification des internautes Identification des visites

Une fois l'utilisateur identifié par l'une de méthodes décrites ci-dessus, il est possible de reconstituer sa session en regroupant les requêtes contenues dans les fichiers Log et émises par cet utilisateur. Selon [Spi, 99], les méthodes d'identification des sessions des utilisateurs peuvent être classifiées en méthodes basées sur le contexte (exemple : accès à des pages de types spécifiques) et méthodes basées sur le temps (exemple : limite seuil de temps de consultation d'une page). Les méthodes basées sur le temps sont les plus couramment utilisées. Elles consistent à considérer que l'ensemble des pages visitées par un utilisateur constitue une visite unique si les pages sont consultées pendant un intervalle de temps ne dépassant pas un certain seuil temporel³. Ce »temps de vue de pages⁴» varie de 25,5 minutes [Cat, 95] à 24 heures [Yan, 96]. Le temps de vue de pages couramment utilisé est de 30 minutes [Coo, 99]. Cependant, l'utilisateur peut passer plus de trente minutes à lire la même page ou quitter son poste pendant un moment et retourner pour consulter la même page. De plus, l'utilisateur du cache peut donner l'impression que la session est finie alors qu'il consulte les pages enregistrées par le cache.

³Cet intervalle de temps correspond à une absence de requêtes, on parle de seuil temporel d'inactivité.

⁴Page viewing time, terme introduit par Shahabi [Sha, 97].

Selon les critères empiriques de Kimball [Kim, 00], une visite est caractérisée par une série d'enregistrements séquentiellement ordonnés, ayant la même adresse IP et le même nom d'utilisateur, ne présentant pas de rupture de séquence de plus d'une certaine durée.

Identification des épisodes

L'objectif de l'identification des épisodes est de créer des classes de référence significatives pour chaque utilisateur. Selon [Coo, 97], les épisodes dépendent du comportement de navigation de l'utilisateur. En se basant sur cette hypothèse, les auteurs proposent de classifier les pages d'un site en:

- Pages auxiliaires : contiennent les hyperliens primaires aux autres pages Web et utilisées pour la navigation.

- Pages de contenu: contiennent des informations intéressantes aux utilisateurs.

- Pages hybrides : contiennent les deux types d'information.

Cette classification basée sur le contexte dépend de l'utilisateur. En effet, une page de navigation (ou auxiliaire) pour un utilisateur peut être une page de contenu pour un autre. Suivant cette classification, il existe trois méthodes d'identification des épisodes : la référence-avant maximale (MF-Maximal Forward reference), le typage des pages et la longueur de la référence.

Selon la méthode »Référence-avant maximale»⁵ , proposée par [Chen, 96], un épisode est défini par un ensemble de pages visitées par un utilisateur à partir de la première page enregistrée dans le fichier Log jusqu'à l'apparition de la première référence en arrière⁶. Ainsi, cette méthode ne considère pas une deuxième fois les pages qui ont été traversées par l'utilisateur lors de sa visite, ce qui ne convient pas à certaines classes d'applications où il est important de prédire les types de référence en arrière. D'autre part, le Web caching empêche les références en arrière d'être enregistrées dans les fichiers Log.

La méthode »typage de pages» [Coo, 99] est semblable à la méthode »longueur de référence». La différence entre les deux méthodes consiste dans l'algorithme de classification basé sur les données d'usage pour la méthode longueur de référence et sur le contenu de la page pour la méthode typage de page.

3.4 Fouille de données

Une fois les fichiers Log retravaillés en sessions, les données sont analysées à l'aide de plusieurs outils statistiques appropriés regroupés dans une boîte à outils

⁵Les références avant-maximale sont des pages de contenu accessibles à travers les pages auxiliaires.

⁶Une référence en arrière est une page qui est déjà incluse dans l'épisode.

nommée »Data Mining».

Le Data Mining consiste à »utiliser un ensemble de techniques statistiques qui, en »fouillant» un grand nombre de données structurées, permettent de découvrir et de présenter des informations à valeur ajoutée dans une forme interprétable facilement par un individu». Dans le cadre du Web Mining, il s'agit d'extraire des informations à valeur ajoutée à partir des données collectées sur les internautes afin de mieux les connaître. Les méthodes appliquées au WUM se répartissent en quatre grandes familles [Mic, 02].

3.4.1 Méthodes statistiques unidimensionnelles

Ces méthodes permettent une analyse exploratoire des données à travers les indicateurs statistiques (moyenne, écart-type,...) et la représentation graphique (histogrammes, boîte de dispersion,...);

Les indicateurs d'audience éditoriale selon la terminologie du CRESP⁷ (Centre d'étude des supports de Publicité) sont :

- Le nombre de pages demandées ou vues (i.e. totalement téléchargées),

- Le nombre de pages provenant de mémoires caches ou de serveurs Proxy, - Le nombre de visiteurs,

- Le nombre de pages vues par visite,

- L'origine géographique des consultations,

- La durée de consultation par visite.

3.4.2 Méthodes statistiques multidimensionnelles

Ces méthodes (Factorisation, segmentation, classification, ) permettent, en réduisant l'espace et en fournissant des représentations graphiques, d'exploiter, de fouiller et de représenter des grands ensembles des données.

Méthodes factorielles

Les méthodes factorielles se proposent de fournir des représentations synthétiques, souvent sous forme graphique, de vastes ensembles de valeurs numériques. L'analyse en composantes principales (ACP) est une technique permettant de réduire un système complexe de corrélations en un nombre inférieur de dimensions. Elle s'applique sur des tableaux dont les lignes sont des individus et les colonnes des variables numériques. L'analyse factorielle des correspondances (AFC) traite des variables qualitatives. Elle s'applique sur des tableaux de contingence. Son extension, l'analyse factorielle des correspondances multiples (AFCM) s'applique sur des grands tableaux de variables nominales où les lignes sont les individus et les colonnes des variables descriptives [Leb, 00].

⁷http ://www.cesp.org/

Méthodes de classification automatique

La classification automatique, appelée aussi classification non supervisée, segmentation ou également clustérisat ion, consiste à rechercher des groupes homogènes inconnues au départ dans une population d'individus représentés par une ou plusieurs variables. Le Data Mining propose plusieurs méthodes de classification automatique telle que la classification ascendante hiérarchique, la classification descendante hiérarchique, la méthode des centres mobiles...etc. Cependant, l'adaptation des méthodes de segmentation au données du Web est difficile vu la taille des tableaux des données tant pour les sessions que pour les pages différentes [Lec, 03]. En effet, dans [Fu, 00], les données sont segmentées, après réduction de dimension, en utilisant un algorithme BIRCH de segmentation hiérarchique introduit par [Zha, 96]. Dans [Ben, 03], une classification non supervisée basée sur un réseau de neurones est utilisée pour grouper les sessions similaires en classes.

Dans le domaine du WUM, il existe deux types de classes à découvrir [Sri, 00] : classes d'usagers et classes de pages. La segmentation des utilisateurs a pour objectif d'établir des groupes d'internautes ayant des comportements de navigation similaires. L'examen de ces groupes permet d'associer un profil à chaque classe d'utilisateurs. La segmentation des pages Web consultées par les internautes permet de découvrir des groupes de pages ayant des contenus reliés ce qui facilite la tâche des navigateurs et des robots. Ces deux types de segmentation servent, dans le cadre d'anticipation de besoins, à créer des pages Web statiques ou dynamiques et proposer des hyperliens aux internautes suivant leurs profils ou leurs historiques de navigation.

Méthodes de classification supervisée

La classification⁸ supervisée cherche à déterminer l'appartenance d'un événement à des classes préalablement identifiées par segmentation. Dans le domaine du WUM, la classification consiste à affecter chaque internaute à une catégorie de comportement de navigation i.e. elle vise à relier les caractéristiques sociodémographiques d'un internaute à son comportement. Pour ce faire, de nombreuses méthodes de classification sont utilisées telles que les arbres de décision, les réseaux de neurones et le raisonnement à base de mémoire.

D'autres méthodes ne faisant pas partie des techniques du Data Mining ont été également utilisées. Une première méthode consiste à utiliser les algorithmes de filtrage collaboratif. Cette technique statistique effectue des comparaisons entre les données sur le nouveau visiteur et celles sur les internautes ayant visité le site avant lui afin de l'assigner à une catégorie d'internautes ayant des profils similaires, à l'aide d'un calcul de proximité suivi d'une fixation de seuil. Une deuxième méthode d'attribution du visiteur au segment consiste à impliquer l'utilisateur

qui devrait choisir sa catégorie. Cette méthode est utilisée en cas de collecte de données ponctuelle (l'utilisateur fournit les données lors de son enregistrement sur le site, au début de la session) avec un profil temporaire. Une autre façon de procéder à l'attribution d'un profil à un segment est de minimiser un indice multicritère. Cette technique est relativement similaire à celle employée par les algorithmes de filtrage collaboratif. En effet, un indice est calculé pour chaque profil et est comparé à ceux des segments prédéfinis. L'attribution se fait au segment présentant la distance minimale entre son indice et celui du profil du visiteur.

3.4.3 Méthodes d'association

Les règles d'association est une méthode de fouille des données non supervisée qui consiste à déterminer les valeurs associées parmi les données. Une règle d'association est une règle de la forme : Si condition (prémisse) alors résultat. Par exemple, Si X et Y alors Z.

Le choix d'une règle d'association nécessite de définir des indicateurs servant à sa validation, à savoir le support, la confiance et l'amélioration de la règle.

- Support d'une règle

Le support d'une règle indique le pourcentage d'enregistrements qui vérifient la règle. C'est la fréquence d'apparition simultanée des articles qui apparaissent dans la prémisse et dans le résultat, soit

Support = freq (condition et résultat) Supp(X Y) = | X&Y | / | BD |

où IX&YI est le nombre d'enregistrements contenant X et Y et IBDI le nombre total de transactions.

- Confiance associée à une règle

La confiance d'une règle mesure la validité de la règle. C'est égal au pourcentage d'enregistrements qui vérifient la conclusion parmi ceux qui vérifient la prémisse. La confiance est le rapport entre le nombre de transactions où tous les articles figurant dans la règle apparaissent et le nombre de transactions où les articles de la partie condition apparaissent, soit

La confiance est basée sur la probabilité conditionnelle:

Conf(X Y) = P(XY) / P(X) = P(Y/X)

- Définition de l'amélioration

Amélioration = Confiance / freq(résultat)

Une règle est considérée intéressante lorsque l'amélioration est supérieure à 1.

Dans le WUM, les associations se font sur les pages dans le but de découvrir les pages visitées ensembles et de prévoir le comportement d'un internaute en se basant sur les requêtes qu'il a effectué. Les règles d'association sont surtout utiles dans le cas de l'étude du trafic sur les sites Web commerciaux. Parmi les algorithmes d'association, l'algorithme APRIORI développé par IBM est le plus souvent utilisé.

3.4.4 Méthodes basées sur l'intelligence artificielle (réseaux de neurones)

Par analogie avec les neurones biologiques, les réseaux de neurones sont des ensembles de calculateurs numériques (neurones formels) agissant comme des unités élémentaires, reliés entre eux par des interconnexions pondérées qui transmettent des informations numériques d'un neurone formel à un autre.

Apprentissage à l'aide d'un réseau de neurones

L'apprentissage d'un réseau de neurones artificiels est induit par une procédure itérative d'ajustement de ses paramètres internes (poids synaptiques et nombres de neurones). En apprentissage supervisé, des exemples (observations) auxquels sont associées des réponses désirées sont présentés au réseau. La sortie produite par le réseau en réponse à une observation donnée est comparée à la réponse désirée (variable de sortie). La différence entre la réponse désirée et la réponse du réseau est alors utilisée pour adapter les paramètres du réseau de façon à corriger son comportement. Ce processus est répété de façon itérative jusqu'à obtenir le meilleur comportement. En apprentissage non supervisé, le réseau catégorise les variables d'entrée sans avoir à déterminer les variables de sortie c'est à dire il évolue tout seul vers son état stable. Cet apprentissage est destiné à l'élaboration d'une représentation interne de l'espace des données d'entrée en identifiant la structure statistique des variables d'entrée sous une forme plus simple ou plus explicite. Ce type d'apprentissage est utilisé dans les réseaux compétitifs, en particulier dans les cartes de Kohonen.

Dans le WUM, le but d'un réseau neuronal est de recréer artificiellement l'expertise qu'aurait une personne habituée à classifier les profils dans les segments prédéfinis (apprentissage supervisé) ou découvrir des nouveaux segments rassemblants des individus ayant des profils similaires (apprentissage non supervisé).

Réseaux compétitifs

Les interconnexions des neurones formels donnent naissance à des réseaux à structures variées dont la plus utilisée est l'organisation en couches successives. Une telle structure diffuse l'information de la couche d'entrée, composée par les neurones formels recevant les informations primitives, vers la couche de sortie, contenant les neurones finaux transmettant les informations de sortie traitées par la totalité du réseau, tout en traversant une ou plusieurs couches intermédiaires, dites couches cachées. Parmi les réseaux de neurones structurés en couches successives, les réseaux compétitifs. Les réseaux compétitifs sont des réseaux qui reproduisent une particularité du fonctionnement biologique des neurones, à savoir l'inhibition latérale. En effet, chaque neurone d'entrée est relié à chaque neurone de sortie et chaque neurone de sortie inhibe tous les autres et s'auto excite. Le degré de l'inhibition est proportionnel à l'amplitude de sortie du neurone⁹ et est une fonction de la distance. En effet, lorsqu'un neurone est excité, il transmet son excitation aux neurones voisins dans un rayon très court et inhibe par contre les neurones situés à plus grande distance.

La figure 3.2 illustre les connexions de compétition pour un des neurones du réseau compétitif. Les connexions d'inhibition et la connexion de contre-réaction sont illustrées pour le 2ème neurone seulement et se répètent pour chaque neurone.

FIG. 3.2 : Réseau linéaire de compétition de type »gagnant emporte tout»

Quand une forme est présentée à l'entrée du réseau compétitif, elle est projetée sur chacun de neurones de la couche de compétition. Une compétition est alors organisée afin de déterminer le neurone gagnant dont le vecteur de poids est le plus près de la forme présentée à l'entrée. Cette architecture permet au réseau de reproduire l'organisation topographique des formes d'entrée. Il existe plusieurs types de réseaux compétitifs tels que les mémoires auto-associatives et les cartes de Kohonen.

3.5 Analyse

L'analyse des modèles est la dernière étape dans le processus du WUM. La méthodologie de l'analyse dépend essentiellement des objectifs de la mise en oeuvre du WUM. Plusieurs techniques ont été développées pour permettre l'analyse des modèles découverts. Parmi ces techniques, la visualisation des données, un mécanisme de requêtes de bases des données relationnelles, les opérations OLAP (On Line Analytical Processing) et les systèmes multi-agents.

3.5.1 Visualisation

La visualisation consiste à »représenter de façon vivante et assimilable des informations (statistiques) en les simplifiant et les schématisant» [Leb, 00]. Les techniques de visualisation ont pour objectif de présenter de façon intelligible la structure d'un ensemble d'objets. Il existe deux types de techniques de visualisation : les techniques traditionnelles qui regroupent les camemberts, les histogrammes, les boites à moustaches, les histogrammes croisés.., et les techniques multidimensionnelles qui regroupent les quatre catégories suivantes : les représentations par pixels*, les techniques de factorisation*, les coordonnées parallèles d'Inselberg* et les techniques hiérarchiques*. Certaines méthodes de classification sont également utilisées pour la visualisation à savoir les arbres (dendrogrammes,...) et les cartes de Kohonen.

3.5.2 OLAP

OLAP (On Line Analytical Processing) est une méthode d'analyse en ligne des données stockées dans les bases de données. Les solutions OLAP reposent sur un même principe : restructurer et stocker dans une forme multidimensionnelle, connue sous le nom d'hypercube, les données issues de fichiers ou de bases relationnelles. Cet hypercube organise les données le long de dimensions représentées par les variables à prendre en compte dans l'analyse. Le processus d'analyse multidimensionnelle nécessite l'accès à un volume important de données et des moyens adaptés pour les analyser. Depuis 1993, OLAP a donné lieu à plusieurs déclinaisons: MOLAP*, ROLAP*, HOLAP*...

3.5.3 Bases des données relationnelles

Le succès de la technologie des bases des données relationnelles provient de l'existence d'un langage de requêtes déclaratif et de haut niveau qui permet de spécifier les conditions à remplir par les données et restreindre l'analyse sur une partie de la base vérifiant certaines conditions. Les bases de données permettent

de construire des »pages dynamiques», c'est-à-dire des pages qui n'existent pas a priori sur le Web ou sur l'Intranet mais qui sont construites à partir des requêtes particulières des utilisateurs. Le serveur garde en mémoire une banque de données structurée par champs homogènes. L'information souhaitée est retrouvée en formulant des requêtes.

3.5.4 Agents intelligents

Dans un contexte de veille stratégique, les agents intelligents sont susceptibles d'intervenir aux différentes étapes du traitement de l'information. Ils assurent ainsi :

- la recherche et la collecte : celle-ci peut se faire de manière »intelligente» par l'utilisation de méta-moteurs perfectionnés (WebSeeker, Copernic Pro), d'outils d'analyse linguistique des requêtes (Autonomy, DigOut4U) ou par exploration de liens hypertextes à partir d'une URL donnée, sans utilisation d'un moteur de recherche,

- l'analyse : les agents de recherche de l'information permettent de traiter l'information de manière à faciliter son utilisation soit en la condensant, soit en la représentant sous une autre forme (graphiques, schémas, etc.),

- le Filtrage, l'édition, l'archivage et la mise à jour des résultats (WebSeeker, BullsEye),

- la diffusion: ils permettent d'acheminer l'information à la personne cible.

3.6 Conclusion

Dans ce chapitre, nous avons présenté les différentes phases du processus du WUM. Comme la phase de la fouille des données est le centre d'intérêt de notre étude, nous consacrons le chapitre suivant à la description des méthodes de classification que nous utiliserons ultérieurement.

Chapitre 4

Méthodes de classification

Si dans les années 80, on distingue deux grands types de méthodes, les méthodes de partitionnement et les méthodes hiérarchiques, depuis d'autres approches (réseaux de neurones,...) ont vu le jour. Le choix de la méthode la plus adaptée dépend de la nature des variables, de la problématique posée et souvent des habitudes du domaine d'étude. Dans ce chapitre, nous présentons deux méthodes factorielles de classification, à savoir l'analyse en composantes principales et l'analyse des correspondances et une méthode connexioniste, les cartes topologiques de Kohonen.

4.1 Méthodes factorielles

L'objectif visé par l'analyse factorielle est la réduction de l'information en passant d'un grand nombre de variables, à un nombre restreint de méta-variables, appelés facteurs. L'essentiel de la démarche des méthodes factorielles est commun entre elles. Les »inputs» d'une analyse factorielle sont dans tous les cas l'espace, les points, les masses affectées aux points et la métrique. Les »outputs» sont les axes d'inertie, les coordonnées des points sur ces axes et divers indicateurs nommés »aides à l'interprétation». D'une méthode d'analyse factorielle à une autre, seuls varient les »inputs» i.e. les définitions des points, des masses et de la métrique [Jam, 99].

4.1.1 Analyse en composantes principales (ACP)

L'ACP est une méthode factorielle ayant pour but de déterminer un sous- espace vectoriel de dimension (k) inférieure à la dimension de l'espace d'entrée (k<p) et qui offre le maximum d'inertie expliquée pour y projeter le nuage de points de l'espace d'entrée R^p. En d'autres termes, réduire le nombre de variables à quelques facteurs significatifs et déterminer les relations de proximité entre

points individus et points variables. La démarche d'une ACP est présentée dans ce qui suit.

Calcul de la matrice d'inertie

Soit le tableau X (xij ; i=1..n; j=1. .p) formé de n points Xi munis de masses pi positives, décrits chacun par p variables:

La matrice d'inertie V s'écrit V=X'MX où X est la matrice à n lignes et p colonnes. Les lignes de X sont les vecteurs Xi, M est la matrice carrée diagonale d'ordre n des poids pi (généralement pi = 1/n).

V peut aussi s'écrire V=ZZ' avec Z= X'M¹=². Cette matrice a les propriétés suivantes :

- V est symétrique.

- V est diagonalisable et ses valeurs et vecteurs propres sont réels.

- Les vecteurs propres associés à des valeurs propres différentes sont orthogonaux.

- V est semi-définie positive et donc pour tout vecteur U de Rⁿ (espace d'entrée) on a U'VU positif. Toute valeur propre de V est donc supérieure ou égale à zéro.

- La trace de V, qui est la somme de toutes les valeurs propres, est égale à Tr(V)=P

i

i

Détermination des axes factoriels

Les axes engendrés par les vecteurs U1, . .Uk, vecteurs propres associés aux valeurs propres de V sont les axes principaux d'inertie. La k ième composante principale, ou le k ième facteur est le vecteur dont les composantes sont les coordonnées des points du nuage sur le k ième axe principal d'inertie Uk. Comme le nombre d'individus est n, ce vecteur a n composantes, c'est donc un élément de l'espace Rⁿ des variables.

Pour déterminer l'espace de projection à inertie expliquée maximale il faut déterminer ses k axes. Le premier est l'axe à inertie expliquée maximum. Pour

le déterminer, il suffit de chercher l'axe associé au premier vecteur propre de la matrice V. On désignera par U1le vecteur associé à la plus grande valeur propre 1. L'inertie expliquée par cet axe est égale à:

ë / ëi
1 ?i

Remarquons que l'inertie qui n'est pas expliquée par un sous-espace vectoriel donné l'est totalement par le sous-espace supplémentaire (ensemble des axes qui lui sont orthogonaux). Connaître le reste de l'inertie expliquée revient donc à déterminer les axes associés aux autres vecteurs propres.

Combien de facteurs faut-il retenir?

Retenir tous les facteurs équivaut à garder toute l'information initiale mais sans contribuer à la simplification de la structure des liaisons entres variables. Inversement, ne garder qu'un petit nombre de facteurs peut revenir à n'expliquer qu'un pourcentage trop faible de variance totale, et donc à résumer de façon excessive la complexité de la structure des liaisons entres variables, à moins que quelques facteurs seulement suffisent à expliquer une proportion importante de la variance totale. Généralement, la méthode adoptée est de garder les premiers axes factoriels dont la proportion expliquée de la variance atteint une proportion fixée, par exemple 80% (»critère» de »Jolie»). Il s'agit des premiers facteurs car leur pouvoir d'explication décroît du fait de leur ordonnancement par valeurs décroissantes de leur variance ®.

Représentation des individus

Les axes factoriels constituent une nouvelle base de l'espace Rp. Il est donc nécessaire de calculer les coordonnées des points sur ces axes pour les représenter dans la nouvelle base et plus précisément sur uniquement k axes.

La coordonnée ® d'un point Xi sur un axe U_® correspond à la projection du point sur l'axe, qui est aussi égal au produit scalaire entre Xi et le vecteur U_® de l'axe:

p

u_á i á ?= á

= =

'

( ) U X x u h

i ih

h 1

Pour interpréter les résultats d'une analyse en composantes principales nous avons aussi besoin de connaître:

- Pour chaque point Xi, la contribution du point à l'inertie du nuage. Cette contribution indique quels sont les points qui ont joué un rôle important dans l'analyse.

2

( )
i

CONTR i p i X i

( ) =

I o

( )

avec I(o) = Tr(V)

- Pour chaque axe U_® et chaque point Xi, la contribution du point à l'inertie expliquée par l'axe:

=

CTR_á

( )
i

p_i

u á

ë á

Les CTRs permettent d'interpréter un axe en identifiant les points qui ont le plus contribué à son positionnement. Notons que nous avons toujours :

n

?= =

CTR i

á ( )1

1

i

2

- Pour chaque point Xi et pour chaque axe U_®, on calcule la part de l'inertie du point restituée par l'axe et égale à:

2 ( )

u i

COS i á

( ) =

X_i

á 2

C'est en fait le carré du cosinus de l'angle formé par l'axe U_® et le point Xi.

COS i

2 =

á ( )1

p

?=

á 1

Représentation des points variables

Généralement, les variables utilisées dans l'ACP sont centrées. Le nuage des individus est donc centré. Son centre de gravité est situé à l'origine, ce qui n'est pas le cas pour le nuage des variables. Chaque variable Y correspond à une colonne du tableau X munie d'une masse unitaire. On utilisera comme représentation des variables la notation Z^® :

á 1 / 2 á 1 á

? ?

Z = M Y = n Y

? ?

? ?

car M est une matrice diagonale dont tous les termes sont égaux à 1/n. Toutes les variables Z sont normées et les points variables se situent à une

distance égale à 1 de l'origine. Elles sont donc sur la sphère de rayon 1. D'autre

part la distance entre deux variables est :

d²(Z^a,Z^fi )= Z^a --Z^fi2 = Za 2 #177; Z^{fi 2}--2 Z^a,Z^fi =2(1-- Z^a,Z^fi )

avec <Z^, , Z^E,> désigne le produit scalaire de deux variables.

Par ailleurs, le produit scalaire de deux vecteurs A et B est égal au produit des normes et du cosinus de l'angle entre les des deux vecteurs, donc

fi )

Z^a,Z^fi = _Za Zfi cos(Za,Zfi)=cosga,Z

car les variables sont normées. Ainsi,

)

d²(Z^a,Z^fi)=2(1--cosg^a,Z^fi

fi n

fi

Comme les variables sont centrées réduites, le coefficient de corrélation 1/2,E, est égal à

a

Z

=

1,z72 xi^axi t

=

afi

i=1 n i4

On peut donc dire que

)

pafi =COSga,Zfi

Les remarques suivantes seront utilisées pour donner un sens aux différents axes factoriels en fonction de la position des variables :

- Deux points variables confondus ont un coefficient de corrélation égal à 1.

- Deux points variables formant un angle de 90°ont un coefficient de corrélation linéaire égal à zéro.

- Deux points variables formant un angle de 180°ont un coefficient de corrélation linéaire égal à -1 (anti-corrélées).

- Pour comparer des points entre eux, il faut qu'ils soient proches de la circonférence du cercle de corrélation.

- Par contre, on ne peut rien dire quand les variables sont agglomérées au centre du cercle, ou de la sphère unité.

Aides à l'interprétation

L'ordre à suivre dans l'exploitation des indicateurs est le suivant :

1. Chercher les i correspondant aux CTR,(i) les plus forts. Sélectionner l'ensemble I' c I des points i tels que la somme des CTR, soit élevée (par exemple 0.8). L'interprétation de l'axe reposera sur l'examen de ces points.

2. Regarder le signe de 1,(i) pour i E I'. Ce signe indique si les points interviennent sur l'axe du côté positif ou du côté négatif.

. ?=

i ₁ n ij

n =

j

, ?

n j =

.

i=1

n ij , n n i 1

= =

.. .

? ? =

i=1 j

n. j

3. Examiner les COS² _®(i) pour i I^'. Si COS² _®(i) est fort, le point i est pratiquement aligné sur l'axe ®, il ne joue pas donc un grand rôle sur les autres axes. Inversement, si COS² _®(i) est faible, le point i joue un rôle important sur d'autres axes factoriels.

4.1.2 Analyse factorielle des correspondances (AFC)

L'analyse factorielle des correspondances (AFC) est une technique statistique développée pour mettre en évidence des correspondances entre des variables qualitatives décrivant une population. L'AFC est également une méthode de réduction de dimensionnalité qui facilite la représentation géométrique des individus et des caractères.

Cette méthode a pour objectifs de :

- Représenter graphiquement et de manière optimale des individus (lignes) en minimisant la déformation du nuage de points,

- Représenter graphiquement les variables (colonnes) dans un espace explici-

tant au mieux les liaisons initiales (