Fouille du web

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La fouille du Web est l'application des techniques d'exploration de données en vue de découvrir des constantes, schémas ou modèles, dans les ressources d'internet ou les données le concernant. Selon ses cibles, la fouille du web peut être divisée en trois types : la fouille de l'usage du web, la fouille du contenu du web, la fouille de la structure du web[1].

Fouille de l'usage du web[modifier | modifier le code]

Le processus de fouille de l'usage du web

La fouille de l'usage du web (Web usage mining ou Web log mining) est le processus d'extraction d'informations utiles stockées dans les logs des serveurs web (l'historique des transactions des utilisateurs) ou bien les informations données par les intervenant du web (FAI, Panélistes, ..). En analysant ces flux de clics, on cherche à découvrir des informations sur le comportement de l'utilisateur sur internet. L'analyse de l'usage du web se développe en trois étapes distinctes[2], dont la première peut être décomposée en quatre sous-étapes[3] :

  • Le prétraitement
    • La mise au propre des données (Data cleaning )
    • L'identification des transactions
    • L'intégration des données en provenance de plusieurs sources
    • La transformation
  • La Modélisation des données et la recherche des motifs intéressants
  • L'analyse des motifs intéressants

Ces trois étapes, à savoir le pré-traitement, la découverte des motifs, l'analyse des motifs, telles qu'elles sont décrites dans l'architecture WEBMINER[2], correspondent aux phases de préparation des données, de modélisation et d'évaluation de la méthode CRISP_DM[3].

Les fichiers Logs[modifier | modifier le code]

La matière première de la fouille de l'usage du web est constituée des fichiers «logs». Outre les formats propriétaires, il en existe deux formats : le CLF[4] (« Common log format ») et le XLF[5] (« Extended log format »)[6].

Format des fichiers «logs» CLF
Adresse IP Date/Heure Type Url demandée protocole HTTP Code Retour Taille
150.3.220.18 18/April/2011:17:45:33 GET http://fr.wikipedia.org/wiki/Exploration_de_donn%C3%A9es HTTP/1.1 200 20933
Format des fichiers «logs» XLF
Adresse IP Date/Heure Type Url demandée protocole HTTP Code Retour Taille Url d'origine (« Referer ») Navigateur (« User Agent ») Système d'exploitation du poste Client
150.3.220.18 18/April/2011:17:45:33 GET http://../wiki/Exploration_de_donn%C3%A9es HTTP/1.1 200 20933 http://../wiki/Gestion_des_connaissances MSIE 9.0 Windows NT 7.1

Il existe des outils d'analyse des fichiers logs comme Webtrends, Web Analytics qui permettent d'exploiter ces fichiers[7].

Le prétraitement[modifier | modifier le code]

  • Le Data Cleaning

La mise au propre des données consiste à enlever toutes les données qui ne sont pas utiles à l'analyse. On supprime de l'ensemble des données à fouiller les références aux fichiers CSS, images, et audio, ainsi que le nombre d'octets transférés et la version des protocoles utilisés. Les Web crawlers et les Spiders ne sont pas des acteurs dont le comportement est intéressant à analyser - puisqu'ils explorent systématiquement toutes les pages d'un site - mais heureusement laissent des traces -pour les mieux éduqués d'entre eux- qui permettent de supprimer les données les concernant[8].

Une Pageview[9] est l'ensemble des objets contenus dans une page et avec lesquels l'utilisateur a interagi. Cette étape consiste donc à identifier, à partir des fichiers logs, tous les évènements déclenchés par l'utilisateur (clicks, vue détaillée, ajout au panier, etc.) mettant en jeu des objets des pages du site, en essayant de reconstituer les Pageviews. Chaque Pageview est représentée par un identifiant, et contient des informations comme le type de page (page d'information, d'index, de produit, ..) et des informations sur les objets visités[10].

Ce n'est pas tant l'identité de la personne physique qui est intéressant ici - ce qui poserait certainement des problèmes éthiques - mais plutôt celle du visiteur virtuel. Il est nécessaire de savoir si un visiteur revient sur un site après une première visite, par exemple, mais aussi de séparer des logs de deux visiteurs différents. Ceci se fait à l'aide de cookies déposés sur le poste du visiteur par le site, si l'utilisateur accepte de coopérer. Bien souvent les utilisateurs n'acceptent pas les cookies et on doit utiliser des méthodes heuristiques pour séparer les enregistrements issus des logs[11].

Il s'agit de segmenter l'activité du visiteur en différentes sessions qui correspondent à une seule visite du site. Là encore cela peut se faire soit à l'aide de cookies, soit par des méthodes heuristiques.

  • La complétion du chemin de navigation

Parce que tout n'est pas mémorisé dans les logs des serveurs - comme lorsque le visiteur revient sur une page déjà vue en utilisant le bouton Retour de son navigateur qui utilise l'historique stocké sur son poste - il est nécessaire de détecter les sauts entre deux pages non contiguës et de compléter le chemin de navigation entre ces deux pages. Une manière de faire est de suivre le chemin le plus court entre les deux pages.

La modélisation des données[modifier | modifier le code]

Toujours pour suivre séquentiellement le processus illustré par l'image en haut à gauche, nous allons modéliser les données et introduire les notions de matrice PFM et matrice UPM. Soient P=(p_1,p_2,..,p_n) n Pageviews et T=(t_1,t_2,..,t_m) m transactions composées de sous-ensembles de P telles que t = ( (p{_1}^t,w(p{_1}^t),(p{_2}^t,w(p{_2}^t),...,(p{_l}^t,w(p{_l}^t)) où les p{_i}^t sont des pageviews de P et w(p{_i}^t) est le poids accordé à p{_i}^t[12],[13].

Fouille du contenu du web[modifier | modifier le code]

La fouille du contenu du web (« Web content mining ») est le processus d'extraction d'informations contenues dans les documents stockés sur internet. Ces documents peuvent être des fichiers textes, audios, vidéos, etc. Ce type d'exploration met en œuvre des techniques de traitement automatique du langage naturel (« natural language processing (NLP) ») et de recherche d'information[14] (« Information Retrieval (IR) »). Dans ce cadre, le web sémantique est un effort d'évolution globale du Net pour une lecture facilitée des données, en particulier par les agents extérieurs aux entrepôts de données. Les techniques d'exploration de données les plus utilisées sont la classification, la segmentation (« Clustering ») et l'association. Il s'agit donc plus d'exploration descriptive que d'exploration prédictive.

Fouille de la structure du web[modifier | modifier le code]

La fouille de la structure du web (« Web structure mining ») est le processus d'analyse des relations, inconnues à priori, entre documents ou pages stockés sur internet. Il y a plusieurs techniques de fouille : la classification, le « Clustering », le « Ranking ».

Classification[modifier | modifier le code]

Dans la classification, il s'agit de prévoir la classe[15] d'une page internet en fonction de mots sur la page, les relations entre pages, les ancres, d'autres attributs des pages et des liens[16].

Clustering[modifier | modifier le code]

Le but de la classification non supervisée[17] est de trouver des classes naturelles non prévues à l'avance. On peut regrouper des objets, des collections d'objets reliés entre eux, ou d'autres sous-graphes. On peut par exemple ainsi trouver des hubs et des sites miroirs.

Ranking[modifier | modifier le code]

L'idée est qu'une page est importante si beaucoup d'autres pages pointent vers elle, et qu'elle est encore plus importante si des pages importantes pointent vers elle. Inversement, si une page pointe vers d'autres pages importantes, sa fiabilité et sa crédibilité en sont augmentées. La représentation de ces liens est inspirée par celle en vigueur dans l'étude des réseaux sociaux, et dans celle des citations de documents. La difficulté est de formaliser le concept de page «importante». Dans ce but, l'outil mathématique utilisé pour représenter la structure du web est le graphe ( orienté ou non) dans lequel les sommets représentent les pages web et les arcs (arêtes) les liens entrants ou sortants. Les deux références dans l'Analyse de liens sont PageRank et HITS ; ce sont deux algorithmes qui utilisent les concepts de Centralité (« Centrality »), de Prestige (« Prestige »), de Concentrateur (« Hub ») et d'Autorité (« Authority »).

Centralité[modifier | modifier le code]

Une page est centrale[18] (localement) si elle a plus de liens entrants ou sortants que ses voisines. Si on représente le web par un arc non orienté, le degré de centralité d'une page i - noté C_D(i) est le nombre d'arêtes du nœud i divisé par le nombre total d'arêtes possibles, soit

C_D(i) = \frac{d(i)}{n-1}

Si la structure (locale) du web est représentée par un graphe orienté, alors on compte seulement les arcs sortant de i : d_s(i).
Une autre approche de la centralité est la proximité : une page est centrale si la distance entre elle et ses voisines est courte. Si d(i,j) est le plus petit nombre de liens entre les pages i et j, alors la centralité de proximité est donnée par :

C_C(i) = \frac{n-1}{\sum_{j=1}^n d(i,j)}

La centralité d'intermédiation mesure l'importance des pages par lesquelles on doit passer pour voyager d'une page à une autre. Si on veut aller de la page j à la page k, et qu'il faille passer par i, alors i est centrale par rapport à j et k, et on mesure cette importance par la formule :

C_B(i) = \frac{ 2 \sum_{j<k} \frac{p_{jk}(i)}{p_{jk}}}{(n-1)(n-2)}p_{jk}(i) et le nombre de plus courts chemins passant par i, et p_{jk} le nombre de plus courts chemins allant de j à k

Prestige[modifier | modifier le code]

Toujours inspirée[18] par l'analyse des réseaux sociaux, la notion de prestige est une autre manière de mesurer l'importance d'une page ou d'un document. Une page prestigieuse est une page à laquelle un grand nombre d'autres pages se lient - elle reçoit un grand nombre de liens. La mesure du prestige d'une page ou d'un document i est définie par son degré d'entrées :

P_D(i) = \frac{d_e(i)}{n-1}d_e(i) est le nombre de liens entrants sur la page i

On voit ainsi que, dans la représentation du web par un graphe orienté, le degré de centralité est mesuré pat les liens sortants, alors que celui de prestige est mesuré par les liens entrants.
Le degré de prestige d'une page i ne considère que les pages directement liées à i. Le prestige de proximité considère l'ensemble des pages reliées directement ou indirectement à la page i. Si on note I_i cet ensemble, alors on mesure le prestige de proximité de la page i par:

P_P(i) = \frac{\sum_{j=1}^n d(i,j)}{|I_i|} d(i,j) est le plus court chemin entre i et j et |I_i| est le cardinal de I_i

Si une page prestigieuse se lie à la page i, par le fait, celle-ci hérite d'une partie du prestige de la première. c'est le prestige de rang ou de classe « Rank prestige », défini par :

P_R(i) =  A_{1i}P_R(1) +  A_{2i}P_R(2) + .. +  A_{ni}P_R(n)A_{ji} = 1 si j est reliée à i, 0 sinon et P_R(j) le prestige de rang/classe de j

.

On[18] remarque donc que si P = (P_R(1), P_R(2), .. ,P_R(n))^T alors P = A^TP A =[A_{ij}]  A_{ij}=1 si i, j sont reliées , 0 sinon. On en déduit que P est un vecteur propre de A^T.

Concentrateur et autorité[modifier | modifier le code]

Exemple de page concentrateur et de page autorité

Un concentrateur[19] (« Hub ») est une page servant d'index, de répertoire guidant les utilisateurs vers les pages d'autorité[20]. Dans la représentation du Web par un graphe orienté, un concentrateur a énormément d'arcs sortants. Typiquement, un portail wiki et une catégorie sont des concentrateurs. Une autorité[19] (« Authority ») est une page dont le contenu est de qualité ou fait autorité sur le sujet de son contenu, et ainsi les webmasters croient en son contenu et lient leurs pages à celle-ci. Une autorité a énormément de liens entrants.

Soit donc G=(V,E) un graphe orienté, et L=[L_{ij}] la matrice de contiguïté définie par L_{ij} = 1 si (i,j)  \in E , 0 sinon. Le score d'autorité et le score de concentrateur sont définis par

a(i)=\sum_{(i,j) \in E} h(j) et h(i)=\sum_{(i,j) \in E} a(j)
si a=(a(1),a(2), ..,a(n))^T et h=(h(1),h(2), .. ,h(n))^T alors a=L^Th et h=La

PageRank et HITS[modifier | modifier le code]

PageRank est l'algorithme de « ranking » des pages internet utilisé par Google, HITS (pour « Hypertext Induced Topic Search ») est celui utilisé par Clever d'IBM. Le premier algorithme s'inspire des notions de centralité et de prestige[18], tandis que le second utilise les concepts de concentrateur et d'autorité[19].

Algorithme PageRank[modifier | modifier le code]
Algorithme HITS[modifier | modifier le code]

L'algorithme HITS construit les scores a et h par itérations successives. Si a_k et h_k représentent les scores à la k^{\text{ème}} itération, on a a_k=L^TLa_{k-1} et h_k=LL^Th_{k-1} avec a_0=(1,1,..,1), et h_0=(1,1,..,1), d'où l'algorithme convergeant suivant[21] :
_____________________________
Algorithme HITS: par itérations
_____________________________
a_0 \leftarrow h_0 \leftarrow (1,1,..,1)
k \leftarrow 1
Faire

a_k \leftarrow L^TLa_{k-1}
h_k \leftarrow LL^Th_{k-1}
a_k \leftarrow \frac{a_k}{||a_k||}
h_k \leftarrow \frac{h_k}{||h_k||}
k \leftarrow k+1

Tant que ||a_k -a_{k-1}||<\epsilon_a et ||h_k -h_{k-1}||<\epsilon_h
Retourner a_k ~,~ h_k

Applications[modifier | modifier le code]

Robot d'indexation[modifier | modifier le code]

Les robots d'indexation ( nommés aussi « Spider » ou « Web Crawler ») sont des outils qui parcourent l'internet de façon méthodique et automatique. Ils peuvent copier des sites entiers sur le disque dur d'une machine - pour en faire un site miroir par exemple -, ils servent à vérifier les liens, à indexer, les moteurs de recherche les utilisent.

Ces araignées du Web peuvent se spécialiser dans la recherche de pages dans certaines catégories[22] préalablement définies. Un classifier[18] est construit en utilisant des pages échantillons étiquetées pour indiquer à quelles catégories elles appartiennent. Le classifier ainsi formé peut aider le « Web Crawler » à choisir les pages pouvant appartenir aux catégories auxquelles on s’intéresse. Le classifier utilisé par Soumen Chakrabarti[22] utilise la méthode naïve bayésienne.

Les « Spider » peuvent aussi rechercher des pages orientées dans des domaines, sur des sujets spécifiques. Ce sont les « Topical Crawler »[23]. L'idée est que des pages reliées contiennent des indications sur leur contenu réciproque, et d'une manière plus générale, que des pages «proches» ont des contenus similaires, soit lexicalement, soit sémantiquement.

Exemples[modifier | modifier le code]

Problèmes éthiques[modifier | modifier le code]

Les problèmes éthiques sont identiques à ceux posés par l'exploration de données[25], c'est-à-dire essentiellement des problèmes liés à la vie privée, et à l'utilisation détournée (de leur objectif initial et sorties de leur contexte) des données récoltées.

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) Patricio Galeas, « Patricio.Galeas.org Web site » (consulté le 11 juin 2011)
  2. a et b (en) Bamshad Mobasher, « Web Usage Mining Architecture » (consulté le 11 juin 2011)
  3. a et b (en)[PDF]José M. Domenech, Javier Lorenzo, « A Tool for Web Usage Mining » (consulté le 11 juin 2011)
  4. (en) W3C, « Common log Format » (consulté le 11 juin 2011)
  5. (en) W3C, « Extended log Format » (consulté le 11 juin 2011)
  6. Tufféry 2010, p. 640
  7. (en) Hm2k, Andremoz, « List of Web Analytics Software » (consulté le 11 juin 2011)
  8. (en)[PDF]Anália Loureço, Ronnie Alves, Orlando Belo, « When the Hunter Becomes the Prey – Tracking down Web Crawlers in Clickstreams » (consulté le 11 juin 2011)
  9. (en) W3C, « Definitions du W3c » (consulté le 11 juin 2011)
  10. (en)[PDF]Bamshad Mobasher, « Automatic personalization based on web usage mining » (consulté le 11 juin 2011), p. 146
  11. (en)[PDF]Robert Cooley, Bamshad Mobasher, Jaideep Srivastava, « Data Preparation for Mining World Wide Web Browsing Patterns, paragraphe 5.2 » (consulté le 11 juin 2011)
  12. (en)[PDF]S. Orlando, « Web Usage Mining adapté de présentations de B. Berendt, Bamshad Mobasher et M. Spiliopoulou » (consulté le 11 juin 2011)
  13. (en)[PDF]Bamshad Mobasher, « Web Usage Mining chapitre 12 du livre de Bing liu, Springer, 2010, isbn978-3-642-07237-6 » (consulté le 11 juin 2011)
  14. (en)[PDF]Jaideep Srivastava, « Web Mining :Accomplishments & Future Directions » (consulté le 11 juin 2011)
  15. (en)[PDF]Lise Getoor, « Link Mining: A New Data Mining Challenge » (consulté le 11 juin 2011)
  16. (en)[PDF]Qing Lu, Lise Getoor, « link-based classification » (consulté le 11 juin 2011)
  17. (en)[PDF]Miguel Gomes da Costa Júnior, Zhiguo Gong, « Web Structure Mining: An Introduction » (consulté le 11 juin 2011)
  18. a, b, c, d et e Liu 2010, p. 238-245
  19. a, b et c (en)[PDF]Jon M. Kleinberg, « Authoritative Sources in a Hyperlinked Environment » (consulté le 11 juin 2011)
  20. (en)[PDF]Magdalini Eirinaki, « Web Mining : A Roadmap » (consulté le 11 juin 2011), p. 6
  21. Liu 2010, p. 257-258
  22. a et b (en)[PDF]Soumen Chakrabarti, Byron E. Dom, David Gibson, Jon Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins, « Mining the Link Structure of the World Wide Web » (consulté le 11 juin 2011)
  23. (en)[PDF]P. Srinivasan, F. Menczer, G. Pant, « A General Evaluation Framework for Topical Crawlers » (consulté le 11 juin 2011)
  24. GM Crawl : identifier et capter les données pertinentes (2014)
  25. (en)[PDF]Lita van Wel, Lambèr Royakkers, « Ethical issues in web data mining » (consulté le 11 juin 2011)

Notes[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Web mining » (voir la liste des auteurs)

Bibliographie[modifier | modifier le code]

  • Bing Liu, Web Data Mining, Berlin, Springer,‎ 2010, 532 p. (ISBN 9783642072376).Document utilisé pour la rédaction de l’article
  • Stéphane Tufféry, Data Mining et statistique décisionnelle, Paris, éditions Technip,‎ 2010, 705 p. (ISBN 978-2-7108-0946-3)