Fouille du web

Exploration de données
Articles principaux
Exploration de données
Fouille de données spatiales
Fouille du web
Fouille de flots de données
Fouille de textes
Fouille d'images
Fouille audio
Articles annexes
Logiciels de fouille de données
Algorithme de fouille de flots de données
Aide
Glossaire du data mining
Contextes liés
Probabilités et statistiques
Information géographique
Imagerie numérique
Informatique
Linguistique
Internet

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

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

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

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].

L'identification des Pageview

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, ...) 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].

L'identification du visiteur

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].

L'identification des sessions

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 par exemple 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

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

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

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

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

Le but de la classification non supervisée^[17] est de trouver des classes naturelles non prévue à 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

L'idée est qu'une page est importante si beaucoup d'autre 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é

Une page est centrale^[18] (localement) si elle a plus de liens entrants ou sortant 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)}$ où

p j k (i)

et le nombre de plus courts chemins passant par

i

, et

p j k

le nombre de plus courts chemins allant de

j

k

Prestige

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}$ où

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 math>i</math> ne considère que les pages directement liées à math>i</math>. 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|}$ où

d (i, j)

est le plus court chemin entre

i

j

| 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 1 i P R (1) + A 2 i P R (2) + .. + A n i P R (n)

où

A j i = 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 T P$ où $A = [A i j]$ où $A i j = 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é

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é à énormément de liens entrants.

Soit donc $G = (V, E)$ un graphe orienté, et $L = [L i j]$ la matrice de contiguïté définie par $L i j = 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

h = (h (1), h (2),.., h (n)) T

alors $a = L T h$ et $h = L a$

PageRank et HITS

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

Algorithme HITS

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 ème$ itération, on a $a k = L T L a k - 1$ et $h k = L L T h 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

Robot d'indexation

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

Myspiders^[24]
ScrapePro Crawler

Problèmes éthiques

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

Liens internes

Liens externes

Références

↑ (en)Patricio Galeas, « Patricio.Galeas.org Web site ». Consulté le 11 juin 2011
↑ ^{a et b} (en)Bamshad Mobasher, « Web Usage Mining Architecture ». Consulté le 11 juin 2011
↑ ^{a et b} (en)[PDF]José M. Domenech, Javier Lorenzo, « A Tool for Web Usage Mining ». Consulté le 11 juin 2011
↑ (en)W3C, « Common log Format ». Consulté le 11 juin 2011
↑ (en)W3C, « Extended log Format ». Consulté le 11 juin 2011
↑ Tufféry 2010, p. 640
↑ (en)Hm2k, Andremoz, « List of Web Analytics Software ». Consulté le 11 juin 2011
↑ (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
↑ (en)W3C, « Definitions du W3c ». Consulté le 11 juin 2011
↑ (en)[PDF]Bamshad Mobasher, « Automatic personalization based on web usage mining », p. 146. Consulté le 11 juin 2011
↑ (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
↑ (en)[PDF]S. Orlando, « Web Usage Mining adapté de présentations de B. Berendt, Bamshad Mobasher et M. Spiliopoulou ». Consulté le 11 juin 2011
↑ (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
↑ (en)[PDF]Jaideep Srivastava, « Web Mining :Accomplishments & Future Directions ». Consulté le 11 juin 2011
↑ (en)[PDF]Lise Getoor, « Link Mining: A New Data Mining Challenge ». Consulté le 11 juin 2011
↑ (en)[PDF]Qing Lu, Lise Getoor, « link-based classification ». Consulté le 11 juin 2011
↑ (en)[PDF]Miguel Gomes da Costa Júnior, Zhiguo Gong, « Web Structure Mining: An Introduction ». Consulté le 11 juin 2011
↑ ^{a, b, c, d et e} Liu 2010, p. 238-245
↑ ^{a, b et c} (en)[PDF]Jon M. Kleinberg, « Authoritative Sources in a Hyperlinked Environment ». Consulté le 11 juin 2011
↑ (en)[PDF]Magdalini Eirinaki, « Web Mining : A Roadmap », p. 6. Consulté le 11 juin 2011
↑ Liu 2010, p. 257-258
↑ ^{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
↑ (en)[PDF]P. Srinivasan, F. Menczer, G. Pant, « A General Evaluation Framework for Topical Crawlers ». Consulté le 11 juin 2011
↑ (en)[PDF]Gautam Pant, Filippo Menczer, « MySpiders: Evolve Your Own Intelligent Web Crawlers ». Consulté le 11 juin 2011
↑ (en)[PDF]Lita van Wel, Lambèr Royakkers, « Ethical issues in web data mining ». Consulté le 11 juin 2011

Notes

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

Bibliographie

Bing Liu, Web Data Mining, Berlin, Springer, 2010, 532 p. (ISBN 9783642072376) .
Stéphane Tufféry, Data Mining et statistique décisionnelle, Paris, éditions Technip, 2010, 705 p. (ISBN 978-2-7108-0946-3)

Portail de l’informatique
Portail des probabilités et des statistiques

Catégories :

Ingénierie décisionnelle
Exploration de données

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fouille du web de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

Fouille de textes — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes … Wikipédia en Français
Fouille d'images — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes … Wikipédia en Français
Fouille de flots de données — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes … Wikipédia en Français
Fouille de données spatiales — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes … Wikipédia en Français
Fouille audio — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes … Wikipédia en Français
Fouille De Textes — La fouille de textes ou l extraction de connaissances dans les textes est une spécialisation de la fouille de données et fait partie du domaine de l intelligence artificielle. Cette technique est souvent désignée sous l anglicisme text mining. C… … Wikipédia en Français
Fouille de texte — Fouille de textes La fouille de textes ou l extraction de connaissances dans les textes est une spécialisation de la fouille de données et fait partie du domaine de l intelligence artificielle. Cette technique est souvent désignée sous l… … Wikipédia en Français
Fouille de données — Exploration de données L’exploration de données, aussi connue sous les noms fouille de données, data mining (forage de données) ou encore Extraction de Connaissances à partir de Données (ECD en français, KDD en Anglais), a pour objet l’extraction … Wikipédia en Français
Logiciels de fouille de données — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes … Wikipédia en Français
Algorithme de fouille de flots de données — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Fouille du web

Sommaire