Fouille du web

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

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

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

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.

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 »).

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

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}}$.

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 ${\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 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].

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

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.

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

• Glossaire du data mining
• Web profond

• 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)

• GM Crawl Site Officiel

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