Techniques d'extraction de connaissances appliquées aux données du Web

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

3.1	Niveaux de collecte des données	17
3.2	Principales techniques d'identification des internautes	20
5.1	Création de nouvelles variables	56
5.2	Transformation de la variable URL	57
5.3	Identification du système d'exploitation	58
5.4	Décryptage du User-Agent	59
5.5	Tableau récapitulatif des résultats	62
6.1	Variables utilisées dans l'ACM	71
6.2	Variables utilisées dans l'ACP	74
6.3	Caractérisation des classes d'utilisateurs par les variables »naviga-
	teur» et »plateforme»	76

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

I 2	Etat de l'art Web Mining et Web Usage Mining					4 5
	2.1		Web Mining			5
			2.1.1 Processus du Web Mining			5
			2.1.2 Axes de développement du Web Mining			7
	2.2		Web Usage Mining			8
			2.2.1 Motifs du Web Usage Mining			8
			2.2.2 Données de l'usage			9
			2.2.3 Diverses approches d'analyse			12
	2.3		Conclusion			13
3	Processus du Web Usage Mining					14
	3.1		Processus du Web Usage Mining			14
	3.2		Collecte des données			15
			3.2.1 Données enregistrées au niveau du serveur			16
			3.2.2 Données enregistrées au niveau du client			16
			3.2.3 Données enregistrées au niveau du Proxy			16
	3.3		Prétraitement des données			17
			3.3.1 Nettoyage des données			17
			3.3.2 Transformation des données			18
	3.4		Fouille de données			21
			3.4.1 Méthodes statistiques unidimensionnelles			22
			3.4.2 Méthodes statistiques multidimensionnelles			22
TABLE DES MATIÈRES 3.4.3 Méthodes d'association 3.4.4 Méthodes basées sur l'intelligence artificielle (réseaux de neurones) 3.5 Analyse 3.5.1 Visualisation 3.5.2 OLAP 3.5.3 Bases des données relationnelles 3.5.4 Agents intelligents 3.6 Conclusion						v 24 25 27 27 27 27 28 28
4		Méthodes de classification				29
		4.1	Méthodes factorielles			29
			4.1.1	Analyse en composantes principales (ACP)		29
			4.1.2	Analyse factorielle des correspondances (AFC)		34
			4.1.3	Analyse factorielle des correspondances multiples		36
		4.2	Cartes topologiques de Kohonen			37
			4.2.1	Architecture de la carte topologique		37
			4.2.2	Propriétés de la carte topologique		38
			4.2.3	Algorithme d'apprentissage de Kohonen		38
			4.2.4	Principaux paramètres de la carte topologique		39
			4.2.5	Etude de la qualité d'apprentissage des cartes topologiques		41
			4.2.6	Analyse de la carte topologique		43
			4.2.7	Avantages et limites de la carte de Kohonen		44
		4.3	Conclusion			44
II Méthodologie et application 5 Prétraitement des données					45 46
5.1			Méthodologie de prétraitement		46
			5.1.1	Processus de prétraitement	46
			5.1.2	Nettoyage des données	46
			5.1.3	Transformation des fichiers Log	50
			5.1.4	Retraitement des fichiers Log	54
			5.1.5	Modélisation des unités d'analyse	59
			5.1.6	Schéma relationnel	60
5.2			Résultats de l'analyse des fichiers Log du CCK		61
			5.2.1	Corpus expérimental	61
			5.2.2	Résultats	61
5.3			Conclusion		62

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