2.3.2 Web structure mining
Le Web Structure Mining (WSM) se focalise sur l’analyse de la structure des liens entre les pages ou les sites Web, qui constitue une source riche d’information. Les recherches consacrées à cette branche du WM sont inspirées des travaux sur l’étude des réseaux sociaux (réseaux entre des groupes de personnes ou d’institutions ayant des interactions entre eux) et l’analyse de citations1 (Kosala et al., 2000).
Le WSM inclut l’étude de la topologie du Web (Page et al., 1998), la catégorisation de pages en pages de contenu (authoritatives) et pages de lien (hubs), et la génération d’informations de communauté sur la base de similarité entre les pages ou sites Web (Chakrabarti et al., 1999), (Chakrabarti, 2003). L’analyse de la structure du Web utilise plusieurs algorithmes, dont les plus célèbres sont PagRank (Page et al., 1998) et HITS (Kleinberg, 1999).
2.3.2.1 PageRank
Développé dans l’université de Stanford par Brin et Page (Page et al., 1998), puis intégré dans le moteur de recherche Google, PageRank est un algorithme d’analyse de structure des liens entre pages très puissant (Zhang et al., 2006).
1 Elles font partie des conventions de l’écriture scientifique. Elles permettent à un auteur citant de préciser dans quels travaux il a puisé ses idées. Quand cette convention est respectée, les citations constituent un indicateur d’influence ou d’impact des auteurs cités.
A l’inverse de HITS, PageRank calcul une seule mesure de qualité (on dit aussi popularité ou prestige) pour une page au moment du crawl. Cette mesure et alors combinée avec un autre score similaire à ceux utilisés dans les systèmes de recherche d’information (SRI) lors de l’interrogation. Il est réputé être plus efficace, car la mesure de popularité d’une page est précalculée indépendamment de la requête. Actuellement, il permet de capturer la notion d’importance d’une page en se basant sur les informations des liens.
Ainsi, l’intérêt d’une page A dans le résultat est fonction du nombre de pages qui pointent vers elle, c’est l’idée empruntée du principe des citations dans la littérature scientifique. De plus, et afin d’éviter les liens vains, qui peuvent être de nos jours générés facilement de manière artificielle, cet algorithme étend l’idée des citation, en prenant en compte non seulement le nombre de liens référençant une page mais aussi l’importance et le poids des pages pointant vers elle (Zhang et al., 2006).
L’expression suivante donne la formule de calcul du score r(v), d’une page v utilisé dans PageRank, 2 étant une constante de normalisation, pa et ch deux fonctions représentant les parents et les fils d’une page (Baldi et al., 2003) :
Figure 4. Score d’une page dans PageRank
Remarquons que chaque parent w contribue par une quantité proportionnelle à son score r (w) et inversement proportionnelle à son degré de sortie.
2.3.2.2 HITS
L’algorithme HITS (Hyperlink Induced Topic Search) proposé par Kleinberg (Kleinberg, 1999) s’appuie sur un principe simple : toutes les pages n’ont pas la même importance, et ne jouent pas le même rôle. Certaines sont importantes ayant un contenu informatif (authoritative ou de référence), et d’autres sont des pages hubs contenant des liens vers des pages de référence.
Contrairement à PageRank, HITS démarre par un graphe d’une requête qu’il soumis à un SRI standard, pour collecter un premier ensemble de pages liées au sujet recherché (les nœuds du graphe) appelé ensemble racine (root set) noté R. Ce dernier est utilisé pour obtenir un deuxième ensemble étendu (expanded set) noté E, par l’ajout de tous les nœuds fils, et un nombre fixe de nœuds parents de l’ensemble racine. Vu le nombre important de nœuds pouvant être impliqués, et afin d’alléger l’algorithme, les arrêtes représentant les liens qui relient les nœuds du même serveur seront éliminés. Ils sont seulement considérés comme des liens de navigation.
L’algorithme se fonde sur le calcul du score d’ « authority » d’une page P noté a(p) et celui de hub noté h(p), de manière récursive similaire à PageRank. Le score d’authority (de hub) d’une page est proportionnel à la somme des scores hub (d’authority) des pages qui pointent vers (pointées par) elle.
2.3.3 Web usage mining
Si le WCM et le WSM utilisent les données Web primaires ou réelles, le Web Usage Mining (WUM) opère sur les données secondaires de celui-ci, générées par l’interaction des utilisateurs avec les sites Web (Kosala et al., 2000).
Avec le succès et la popularité du Web, de grandes quantités de données sont générées chaque jour par les serveurs Web, en enregistrant dans des fichiers de type log (journaux) les traces de navigation, appelée aussi clickstream (flux continu de clics), (Kimball et al., 2000), englobant les parcours et les actions, effectuées par les utilisateurs lors de leurs visites.
Le WUM est donc la découverte et l’extraction de connaissances à partir des données d’interaction des utilisateurs avec le Web, sous forme de modèles et de motifs de navigation, en utilisant les techniques du data mining (Cooley et al., 1997).
De par la nature distribuée du Web, la journalisation (logging) dans le cadre du WUM peut être effectuée dans trois niveaux : les journaux de traces au niveau des serveurs Web, les journaux consignés par les serveurs proxy et les traces de navigation coté client (Cooley, 2000).
Les applications du WUM sont nombreuses, elles se divisent entre l’apprentissage de profil utilisateur en vue d’une modélisation de l’usager dans les interfaces adaptatives, et l’apprentissage de modèles de navigation (Kosala et al., 2000). Plus concrètement, il 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 la recherche d’information, et dans plusieurs autres applications basées sur le Web. .
