Fouille du web

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 ces 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

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 intervenants du web (FAI, Panélistes, etc..). 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].

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, 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, etc..) 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 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 ${\displaystyle P=(p_{1},p_{2},..,p_{n})}$ n Pageviews et ${\displaystyle T=(t_{1},t_{2},..,t_{m})}$ m transactions composées de sous-ensembles de P telles que ${\displaystyle t=((p{_{1}}^{t},w(p{_{1}}^{t}),(p{_{2}}^{t},w(p{_{2}}^{t}),...,(p{_{l}}^{t},w(p{_{l}}^{t}))}$ où les ${\displaystyle p{_{i}}^{t}}$ sont des pageviews de ${\displaystyle P}$ et ${\displaystyle w(p{_{i}}^{t})}$ est le poids accordé à ${\displaystyle 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 a 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é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

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é

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 ${\displaystyle i}$ - noté ${\displaystyle C_{D}(i)}$ est le nombre d'arêtes du nœud ${\displaystyle i}$ divisé par le nombre total d'arêtes possibles, soit

${\displaystyle 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 ${\displaystyle i}$ : ${\displaystyle 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 ${\displaystyle d(i,j)}$ est le plus petit nombre de liens entre les pages ${\displaystyle i}$ et ${\displaystyle j}$, alors la centralité de proximité est donnée par :

${\displaystyle C_{C}(i)={\frac {n-1}{\sum _{j=1}^{n}d(i,j)}}}$

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

${\displaystyle C_{B}(i)={\frac {2\sum _{j<k}{\frac {p_{jk}(i)}{p_{jk}}}}{(n-1)(n-2)}}}$ où ${\displaystyle p_{jk}(i)}$ et le nombre de plus courts chemins passant par ${\displaystyle i}$, et ${\displaystyle p_{jk}}$ le nombre de plus courts chemins allant de ${\displaystyle j}$ à ${\displaystyle 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 ${\displaystyle i}$ est définie par son degré d'entrées :

${\displaystyle P_{D}(i)={\frac {d_{e}(i)}{n-1}}}$ où ${\displaystyle d_{e}(i)}$ est le nombre de liens entrants sur la page ${\displaystyle i}$

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

${\displaystyle P_{P}(i)={\frac {\sum _{j=1}^{n}d(i,j)}{|I_{i}|}}}$ où ${\displaystyle d(i,j)}$ est le plus court chemin entre ${\displaystyle i}$ et ${\displaystyle j}$ et ${\displaystyle |I_{i}|}$ est le cardinal de ${\displaystyle I_{i}}$

Si une page prestigieuse se lie à la page ${\displaystyle 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 :

${\displaystyle P_{R}(i)=A_{1i}P_{R}(1)+A_{2i}P_{R}(2)+..+A_{ni}P_{R}(n)}$ où ${\displaystyle A_{ji}=1}$ si j est reliée à ${\displaystyle i}$, 0 sinon et ${\displaystyle P_{R}(j)}$ le prestige de rang/classe de ${\displaystyle j}$

.

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

Concentrateur et 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 ${\displaystyle G=(V,E)}$ un graphe orienté, et ${\displaystyle L=[L_{ij}]}$ la matrice de contiguïté définie par ${\displaystyle L_{ij}=1}$ si ${\displaystyle (i,j)\in E}$, 0 sinon. Le score d'autorité et le score de concentrateur sont définis par

${\displaystyle a(i)=\sum _{(i,j)\in E}h(j)}$ et ${\displaystyle h(i)=\sum _{(i,j)\in E}a(j)}$

si ${\displaystyle a=(a(1),a(2),..,a(n))^{T}}$ et ${\displaystyle h=(h(1),h(2),..,h(n))^{T}}$ alors ${\displaystyle a=L^{T}h}$ et ${\displaystyle h=La}$

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 ${\displaystyle a_{k}}$ et ${\displaystyle h_{k}}$ représentent les scores à la ${\displaystyle k^{\text{ème}}}$ itération, on a ${\displaystyle a_{k}=L^{T}La_{k-1}}$ et ${\displaystyle h_{k}=LL^{T}h_{k-1}}$ avec ${\displaystyle a_{0}=(1,1,..,1)}$, et ${\displaystyle h_{0}=(1,1,..,1)}$, d'où l'algorithme convergeant suivant^[21] :
_____________________________
Algorithme HITS : par itérations
_____________________________
${\displaystyle a_{0}\leftarrow h_{0}\leftarrow (1,1,..,1)}$
${\displaystyle k\leftarrow 1}$
Faire

${\displaystyle a_{k}\leftarrow L^{T}La_{k-1}}$

${\displaystyle h_{k}\leftarrow LL^{T}h_{k-1}}$

${\displaystyle a_{k}\leftarrow {\frac {a_{k}}{||a_{k}||}}}$

${\displaystyle h_{k}\leftarrow {\frac {h_{k}}{||h_{k}||}}}$

${\displaystyle k\leftarrow k+1}$

Tant que ${\displaystyle ||a_{k}-a_{k-1}||<\epsilon _{a}}$ et ${\displaystyle ||h_{k}-h_{k-1}||<\epsilon _{h}}$
Retourner ${\displaystyle 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^[23] 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 »^[24]. 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

• Aleph Search Clear de la société aleph-networks.

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.

Notes et références

Notes

Références

Voir aussi

Articles connexes

• Glossaire du data mining
• Web profond

Bibliographie

• Bing Liu, Web Data Mining, Berlin, Springer, 2010, 532 p. (ISBN 978-3-642-07237-6).
• Stéphane Tufféry, Data Mining et statistique décisionnelle : l'intelligence des données, Paris, éditions Technip, 2010, 705 p. (ISBN 978-2-7108-0946-3, lire en ligne)

Liens externes

• GM Crawl Site Officiel

• Portail de l’informatique
• Portail des probabilités et de la statistique
• Portail des données