Prétraitement & Extraction de Connaissances en Web Usage Mining

By 3 May 2013

“…les systèmes transactionnels. La fouille de données, ou l’extraction de connaissances à partir de données (ECD), est alors apparu comme un champ de recherche pluridisciplinaire dont l’objectif est d’extraire des informations valides, préalablement inconnues, mais notamment compréhensibles et potentiellement utiles, à partir de bases de données…”

Université Kasdi Merbah de Ouargla
Faculté des Sciences et Sciences de l’Ingénieur

Département des Mathématiques et d’Informatique
Option : Informatique et Communication Electronique

Mémoire En vue de l’obtention du diplôme de Magister – Spécialité : Informatique

Prétraitement & Extraction de Connaissances en Web Usage Mining
S2WC2 : un WUM Framework Centré Utilisateur

Présenté le 27 Mai 2009

Par Slimane OULAD NAOUI

Devant le jury composé de :
Présidente Fatima-zohra Laalam MC, Université de Ouargla
Examinateurs Lamri Douidi MC, Université de Sétif
Rapporteur Samir Zidat MC, Université de Batna
Mahieddine Djoudi MC, Université de Poitiers
Co-Rapporteur Chaabane Khentout MC, Université de Sétif

Remerciements :
Ce travail est le résultat du concours de plusieurs personnes.
En premier lieu, je tiens à exprimer mes vifs remerciements à monsieur Mahieddine Djoudi, Maître de Conférences à l’université de Poitiers, pour la confiance qu’il m’a témoignée en proposant ce sujet, et pour avoir pris la peine d’en être aussi le rapporteur. Je le remercie également pour son suivi constant tout au long de ce mémoire.

Mes remerciements vont aussi à monsieur Chaabane Khentout, Maître de Conférences à l’université Ferhat Abbas de Sétif, d’avoir accepté de co-rapporter ce mémoire et pour l’intérêt accordé à ce travail.
Je ne peux ignorer le patronage de Messieurs Boualem Touati et Mustapha Bouakaz, respectivement Directeur de l’informatique et responsable régional au sein de la CNAS, de m’avoir autorisé à poursuivre ces études, et pour leurs encouragements.

Je remercie les membres du jury, Mme. Laalam Fatima-Zohra, Maître de Conférences à l’université de Ouargla, MM. Douidi Lamri et Zidat Samir Maîtres de Conférences respectivement à l’université de Sétif, et de Batna, de m’avoir honoré par leur participation, pour l’intérêt porté à ce mémoire et d’avoir accepté de l’évaluer.
Je remercie Monsieur Adelhakim Harrouz, chef de département informatique ainsi que tous ses collaborateurs pour leur suivi et soutien.
Je suis aussi reconnaissant à monsieur Djelloul Ziadi, Professeur à l’université de Rouen, d’avoir consacré un peu de son précieux temps, en m’accueillant dans son domicile, et discutant autour du sujet.

Durant la préparation de ce mémoire, j’ai pu entretenir des échanges avec des chercheurs et des groupes, je remercie en particulier monsieur Ricco Rakotomalala, maître de conférences à l’université de Lyon, pour les discussions autour de sa plateforme Tanagra, et les membres de Databionics Research Group pour celles concernant l’outil ESOM.
Je voudrais remercier ceux qui ont accepté de participer à cette étude, en me permettant de pénétrer dans leurs vies, et m’autorisant à installer mon outil « espion » sur leurs postes, et m’offrant ainsi leurs traces de navigation. Merci à B.S., A.S., L.C., MS.M., R.ON, Z.D., et M.D.

En fin, je dois rendre hommage à mes parents, qui m’ont toujours aidé et entouré de la plus grande affection malgré tout ce que nous avons subi. Merci aussi à ma femme qui m’a encouragé et soutenu avec persévérance. A mes trésors : Aicha affifa, et Nasrine, qui avec leurs cris et sourires m’ont apaisé dans les moments les plus difficiles.

Résumé :

Ce mémoire traite minutieusement la problématique du Web Usage Mining (WUM), une des instances du Web Mining, consistant à analyser, en utilisant les techniques de la fouille de données, les fichiers logs issus de l’interaction des utilisateurs avec le Web. Ce domaine relativement nouveau, prend de plus en plus d’intérêt aussi bien dans les secteurs académiques que professionnels, compte tenu de ses enjeux scientifiques et socio-économiques importants.

Contrairement à de nombreux travaux en WUM, qui ont pris comme objet d’étude les logs consignés par les serveurs Web, nous développons dans ce travail une approche différente centrée utilisateur, jugée plus précise et efficace.

Pour ce faire, un outil d’acquisition de traces de navigations coté client est d’abord développé. Basé sur la technique des Browser Helper Object, cet outil présente plusieurs avantages dont les plus prépondérants sont la légèreté, l’exploitation simple, et l’altération quasi-nulle de l’environnement de l’utilisateur.

En deuxième lieu, une application de prétraitement des données est élaborée afin de préparer les logs bruts. Celle-ci intègre plusieurs algorithmes originaux et propres au format du log défini, en vue de le nettoyer, d’en reconstituer les sessions des utilisateurs, et d’opérer certaines tâches de formatage final.

La dernière étape de ce travail est consacrée à la segmentation par les cartes auto-organisatrices de Kohonen des sessions des clients, en se servant d’un outil libre d’extraction de connaissances.

Mots clés : Web Usage Mining, Extraction de Connaissances, Prétraitement, Browser Helper Object, Segmentation de Sessions Web, Cartes de Kohonen.

Abstract :

This memory deals, meticulously, with the Web Usage Mining (WUM) problematic. A part of the Web Mining, this subject consists to analyse, using data mining techniques, the web log files issued from the web-user interactions. This relatively new domain, takes more and more interest in both academic and professional sectors considering its important scientific and socio-economic issues.

Contrary to many works in WUM, which took as object of study logs recorded by Web servers; we develop in this memory a different approach, qualified as user-centric, judged more accurate end effective.

To do so, we develop first a client side tool, in order to collect the user navigation trails. Based on Browser Helper Object, this tool has several advantages as the lightness, the simple exploitation, and almost absence of changes in user environment.

Secondly, we elaborate a pre-processing application to prepare the raw client logs. This application includes numerous algorithms and modules, which are originals and appropriates to the log defined format, in order to clean it, reconstruct user sessions and to do some final formatting tasks.

The last stage in our work is devoted to the task of client web session clustering using Kohonen Self organizing Maps, with the use of a free knowledge discovery tool.

Keywords: Web Usage Mining, Knowledge Discovery, Pre-processing, Browser Helper Object, Web Session Clustering, SOM.

Introduction générale
Introduction :

Depuis son apparition, le Web n’a cessé de grandir à des facteurs exponentiels aussi bien sur l’aspect volume d’information et complexité de la topologie, qu’à celui de la diversité des contenus et des services offerts. Ce phénomène l’a transformé, malgré son âge encore jeune, en un média obscur à toute prise d’informations utiles. Le constat est alors que la crise de l’abondance dans le Web est devenue plus difficile à maîtriser que celle de la pénurie d’information qu’on connaît avant l’avènement de ce service dans Internet.

Mais, même s’il est reconnu que l’usage des systèmes de recherche d’information (SRI), développés bien avant, ont assistés de manière significative les humains dans la localisation des informations désirées stockées dans de grandes banques informationnelles à structures souvent normalisées. Ces outils ont montrés, néanmoins, leurs limites face à la complexité du Web, car il ne s’agit pas simplement de repérer des informations ; mais de faire émerger celles pouvant être considérées plus précieuses à partir de données énormes, hétérogènes, hyperliées, non structurées, distribuées, et en perpétuels changements.

D’un autre coté et dans un pareil souci, la communauté bases de données a commencé, à partir des milieux des années 90, de se franchir du triplet classique de gestion de données : stockage-accès-manipulation, pour s’intéresser à la question de la valorisation des masses de données immenses et dormantes collectées dans les systèmes transactionnels. La fouille de données, ou l’extraction de connaissances à partir de données (ECD), est alors apparu comme un champ de recherche pluridisciplinaire dont l’objectif est d’extraire des informations valides, préalablement inconnues, mais notamment compréhensibles et potentiellement utiles, à partir de bases de données en constante expansion, pouvant servir dans l’élaboration de décisions stratégiques.

Après une courte période, durant laquelle les outils d’ECD exploités sur des données classiques (issues dans la majorité des cas de bases de données relationnelles) ont connu un succès indéniable, des ébauches de travaux ont été proposées visant l’étude de l’applicabilité des techniques d’ECD aux données du web. Ceci a donné ainsi naissance au Web Mining, un domaine qui rapidement été admis un sujet de recherche à part entière.

En fonction du type de données à fouiller, nous distinguons trois grandes classes dans le Web mining à savoir : le Web content mining (WCM) si nous considérons l’analyse du contenu du Web, le Web structure mining (WSM) si nous examinons sa structure et le Web usage mining (WUM) si nous nous focalisons sur l’étude de l’usage du Web.

Motivations

Dans ce mémoire, nous nous intéressons plus particulièrement au Web Usage Mining, qui consiste à analyser, en utilisant les techniques d’ECD, les données issues de l’interaction des utilisateurs avec le Web. Ces données, dites traces de navigation, sont laissées par les internautes lors de leurs surfs, et consignées dans des fichiers de type log. Elles peuvent être relevées, selon la position de la sonde de recueil de données, par les serveurs web, les serveurs proxy, ou les postes des utilisateurs.

Les objectifs dans ce domaine sont aussi divers que la modélisation mathématique du trafic dans le but d’améliorer les systèmes de communication, les programmes et les équipements utilisés sur les réseaux pour les uns ; la description et l’interprétation d’un point de vue sociologique des différentes catégories d’usages et d’utilisateurs pour les autres. Les applications, qui en résultent sont nombreuses. D’une part, l’ingénierie des réseaux constitue un débouché évident aux études visant à analyser et à modéliser le trafic. D’autre part, des analyses plus fines, souvent centrées sur des utilisateurs du Web, aboutissent à une meilleure compréhension des situations d’usage et des pratiques des internautes et peuvent être exploitées pour la conception de services plus adaptés aux profils des utilisateurs. Plus concrètement, le WUM est réputé bien accueilli dans la restructuration, l’adaptation et la personnalisation de sites Web, dans le marketing en ligne et les systèmes de recommandation en e-commerce, dans l’analyse de trafic et l’organisation d’architectures réseaux afin d’améliorer leurs performances, dans l’amélioration des systèmes de recherche d’information, et dans plusieurs autres applications basées sur le Web.

A l’instar des données de contenu du Web, les données de son usage ont atteint à leur tour des dimensions colossales. A titre indicatif, les fichiers logs de certains sites populaires collectaient des traces de navigation de l’ordre de gigaoctets par heure. Ces volumes énormes de ce type de fichiers constituent une des difficultés majeures à leur manipulation par les algorithmes de fouille, même les plus astucieux entre eux.

De plus, il a été prouvé dans de nombreux travaux que ces données sont dans une forme très brute et inappropriée pour une application directe et fructueuse des techniques d’ECD. Ces aléas inhérents aux données d’usage du Web, qui les rendent incohérentes, erronées et non fiables et limitent leur exploitation naturelle, sont dus à plusieurs facteurs dont les plus prépondérants sont la nature même du protocole http, l’organisation hiérarchique de l’Internet, et les progrès dans la technologie de construction de sites web.

Partant du principe que la qualité des connaissances extraites à partir de ces fichiers est fortement liée et conditionnée par la validité des données recueillies, une phase de préparation de ces données s’avère donc nécessaire. Cette phase, dite de prétraitement, à pour objectif d’adapter les données logs à la technique de fouille envisagée. Pour ce faire, elle consiste en vue d’aboutir à des objets « fouillables », d’une part à réduire la taille des données en éliminant celles inutiles à l’analyse et présentant du bruit, et d’autre part de corriger les incohérences existantes. Cette phase inclut souvent une étape de formatage des données corrigées obtenues. Eu égard aux volumes gigantesques et la nature des données de faible qualité qu’elle traite, la phase de prétraitement est donc très complexe, fastidieuse et consomme un temps énorme, mais reste, en revanche, primordiale dans tout projet de WUM.

Actuellement, la quasi-totalité des travaux en WUM ont pris comme matière d’étude les logs issus des serveurs web. Ce type de logs centré serveur et largement exploités, outre qu’ils sont limités à un seul site, ils sont devenus actuellement standardisés et validés dans leurs formats de données, la technique utilisée dans leur recueil, et dans la suite des tâches nécessaires à leur prétraitement.

Dans ce travail nous proposons, par contre, une investigation des fichiers logs consignés sur les postes des utilisateurs. Cette approche est encore un champ d’activité en devenir, du fait des différents choix technologiques possibles et du degré de finesse des informations que l’on souhaite recueillir. Elle est réputée être plus riche et plus précise, car elle opère sur la source des actions de l’utilisateur, et permet ainsi de mieux décrire son comportement. Elle est préférée, en plus, du fait qu’elle permet de surmonter plusieurs problèmes relatifs à la préparation des données collectées.

Contributions

Trois principales contributions sont introduites dans notre travail. La première est une étude des principaux travaux de prétraitement et d’extraction de connaissances de tous les types de fichiers logs, donnant lieu à un état de l’art dans ce domaine. La seconde est le développement d’un outil simple, mais efficace, de collecte de traces de navigation coté client, et sa mise en ligne pour les utilisateurs ayant accepté de participer à l’étude. Le troisième apport est la construction d’une application de prétraitement de données. Elle inclut plusieurs modules de préparation des logs des utilisateurs (nettoyage, sessionisation, formatage, et exports vers des plateformes libres d’ECD), et une modélisation pour l’application, aux données d’usage du web, d’une technique célèbre de segmentation : les cartes auto-organisatrises de Kohonen.

Organisation du mémoire

Ce mémoire est organisé comme suit.

Un premier chapitre est consacré exclusivement, logique oblige, à la fouille de données. Nous y rappelons les concepts de bases de ce domaine, et expliquons le processus standard d’un projet d’ECD. Les différentes tâches que la fouille de données est amenée à effectuer sont aussi présentées, avec un résumé des principales techniques d’ECD. Ce chapitre est clôturé en dressant les limites, ainsi que les sujets ouverts en ECD.

Le Web Mining est exploré dans le second chapitre, nous passons en revue notamment les deux premières instances de ce champ de recherche à savoir le WCM et le WSM. Afin de situer les recherches, le lien du Web Mining et ses contours avec des domaines connexes sont aussi éclairés dans ce chapitre.

Un état de l’art sur le WUM est présenté plus en détail dans le troisième chapitre. En effet, nous comparons les différentes approches de recueil de traces de navigation, et discutons les opérations nécessaires au prétraitement des fichiers logs. Nous faisons également le tour des principaux travaux d’extraction de connaissances, et les applications typiques en WUM.

Nous réservons le dernier chapitre, pour décrire notre expérience dans la construction d’un framework pour la segmentation de sessions web coté utilisateur, baptisé S2WC2. Un outil de collecte de trace de navigation coté client, et de nombreux algorithmes de préparation sont parfaitement présentés. Nous discutons dans la dernière partie de ce chapitre les résultats obtenus en utilisant deux implémentations différentes des cartes de Kohonen dans deux plateformes libres d’ECD.

Ce mémoire est achevé par des remarques de conclusion et des voies pouvant constituées des améliorations et des extensions à ce travail.

Partie Pourcentage dans le mémoire
Introduction 4%
Fouille de données (Data Mining) 20%
Fouille du Web (Web Mining) 14%
Web Usage Mining 28%
Le Framework S2WC2 32%
Conclusion 2%

Sommaire:
Introduction générale
Chapitre 1 : Fouille de données concepts et terminologie
1.1 Facteurs d’émergence
1.2 Fouille de données et extraction de connaissances
1.3 Processus d’extraction de connaissances
1.4 Principales techniques de fouille de données
1.5 Limites de la fouille de données et sujets ouverts
Chapitre 2 : De la fouille de données a la fouille du Web
2.1 Préambule
2.2 Propriétés des données du web
2.3 Taxonomie pour le web Mining
2.4 Web mining et domaines connexes
Chapitre 3 : WEB USAGE MINING, Etat de l’art et problématique
3.2 Etude du comportement des utilisateurs sur le web
3.3 Processus standardise en WUM
3.4 Recueil de données
3.5 Prétraitement
3.6 Extraction de connaissances et applications
3.7 Analyse des connaissances
3.8 WUM et vie privée
Chapitre 4 : S2WC2, un Framework pour la segmentation de sessions web cote client
4.2 Architecture
4.3 Collecteur de traces de navigation
4.4 Prétraitement
4.5 Segmentation
4.6 Expérimentations et résultats
Conclusion générale et perspectives

Sommaire :

  1. La fouille de données : concepts et facteurs d’émergence
  2. Les tâches en fouille de données
  3. Le processus d’extraction de connaissances ECD en WUM
  4. Les techniques de fouille de données et ses limites
  5. De la fouille de données à la fouille du Web : les propriétés
  6. Web content mining : Extraction, sélection et prétraitement
  7. Web structure mining : PageRank, HITS et Web usage mining
  8. Le Web mining et les domaines associés : RI, BDD, AGENTS et WS
  9. Comportement des utilisateurs sur le Web et Processus en WUM
  10. Recueil de données : coté serveur, coté Proxy et coté client
  11. Le processus de prétraitement en WUM : le nettoyage des données
  12. Reconstruction des sessions et Processus de prétraitement en WUM
  13. Le formatage et l’intégration d’autres données d’usage
  14. Extraction de connaissances en WUM et applications
  15. L’ECD : la classification et les motifs séquentiels
  16. WUM et vie privée – Analyse des connaissances en WUM
  17. S2WC2, un Framework pour la Segmentation de Sessions Web Coté Client
  18. Reconstruction des surfs : Algorithme de sessionisation
  19. Les techniques d’ECD : le formatage et la segmentation
  20. Les cartes de Kohonen et Outils libres d’ECD
  21. Expérimentations et résultats – Extraction de connaissances en WUM