L’ECD : la classification et les motifs séquentiels

By 4 May 2013

3.6.5 La classification

Dans cette tâche d’ECD, on se focalise sur le regroupement des données en ensembles de classes prédéfinies. Dans le cadre du WUM et généralement dans le web, on s’intéresse notamment à la construction de profils utilisateurs appartenant à des catégories particulières selon leurs motifs d’usage, ce qui nécessite évidemment la sélection et l’extraction préalable des caractéristiques de chaque catégorie ou classe.

L’application type reste le filtrage collaboratif, un champ de recherche en relation avec le profiling des utilisateurs, la personnalisation et la recommandation dans le web, dont l’idée est de prédire les préférences d’un nouvel utilisateur inconnu en se référant à d’autres plus proches (Markov et al., 2007).

Pour la classification, plusieurs algorithmes d’apprentissage supervisé sont utilisés, tels que : les arbres de décision, le kPPV, les SVM, et les classificateurs de Bayes (Cooley, 2000). Il est aussi de coutume d’exploiter, pour fins de classification, les résultats d’un algorithme de segmentation ou d’extraction de RA (Mobasher, 2006).

(Fu et al., 2001) présente un algorithme de classification des pages d’un site web, en vue de sa réorganisation, basé sur les informations d’usage. Dans ce travail, deux catégories de pages ont été définies : les pages d’index et celles de contenu, dont les propriétés : type de fichier, nombre de liens, un compteur de fin de session et la longueur de référence1 ont été retenues comme traits caractéristiques permettant la catégorisation.

Une approche basée sur les SVM est développée dans (Joachims, 2002) pour l’apprentissage, dans le cadre des SRI, de fonctions de recherche. Ce système, contrairement aux travaux d’apprentissage par l’exemple précédents, qui nécessite des informations sur la pertinences des documents, obtenues à partir des jugements d’experts souvent difficiles et coûteuses à mettre en œuvre, repose sur les données d’usage2 et de son exploitation dans l’optimisation automatique de la qualité des réponses des moteurs de recherches.

3.6.6 Les motifs séquentiels

La problématique de l’extraction des motifs séquentiels est semblable à celle des RA, mais en introduisant des contraintes temporelles et d’ordre entre les événements. Il s’agit donc de trouver des motifs intersessions, comme la présence d’un ensemble d’items X est suivi d’un autre ensemble Y dans le fichier des sessions ordonnées dans le temps.

1 Le compteur de fin de session exprime le nombre de fois qu’une page termine une session, alors que la longueur de référence est la durée moyenne que prend un utilisateur sur une page.
2 .Un ensemble de triplets (q, r, c) : une requête (Query), le classement affiché (Ranking), et la listes des liens (Links) choisis par l’utilisateur.

Ce genre d’informations est utile pour prédire des formes de visites futures, et aider dans le placement d’annonces publicitaires recherchées par certaines catégories d’utilisateurs. Il sert aussi dans l’analyse de tendance, le prefetching de documents web, et pour la détection des points de changement dans les données (Cooley, 2000).

Plus formellement, étant donné une transaction T de m pages notée T= <p1,…,pm>, S est dit séquence de longueur n<=m dans T , qu’on note S=(s1,…,sn), s’ils existent un n entiers positifs 1<=a1<a2…<an<=m tel que pour tout i : si=pai. S est dit séquence contiguë dans T, noté S= (sc1,…,scn) s’il existe un entier b ( 0<=b<=m-n) tel que pour tout i de 1 à n : sci=pb+i. un motif séquentiel non contiguë est dit tout simplement motif séquentiel (Mobasher, 2006).

Les traces d’usage vues comme des séquences de pages ont permis l’application de plusieurs modèles solides dans l’analyse et la découverte de connaissances. Par exemple, les chaînes de Markov ont été adoptées dans de multiples travaux dans la modélisation des activités de navigation des internautes (Kammenhuber et al., 2006), où chaque page est représentée par un état et les transitions entres les pages par les probabilités de passage entre ces pages. La figure suivante modélise une trace comportant un ensemble de transactions (50 ici) impliquant les pages A, B, C, D, E et F, avec les fréquences indiquées.

En procédant ainsi, on peut, à titre d’exemple en e-commerce, estimer la probabilité qu’un utilisateur achète un produit, en sachant qu’il a précédemment exploré un catalogue en ligne (Mobasher, 2006).

Exemple de modélisation par chaîne de Markov d’une trace de navigation
Figure 9. Exemple de modélisation par chaîne de Markov d’une trace de navigation

Web Utilization Miner (Spiliopoulou et al., 1999) est un outil de spécification, de découverte et de visualisation de motifs séquentiels d’usage intéressants d’un point vue statistique ou structurel, reposant sur le modèle formel de (Spiliopoulou, 1999). Le log est stocké, après transformation, dans un arbre agrégé afin d’améliorer le temps de réponse du système, qui implémente MINT un langage de requête de type SQL, afin de découvrir les motifs séquentiels. L’utilisateur spécifiera, comme illustré dans l’exemple de la requête suivante, le format des motifs selon des templates, peuvent inclure des jokers (wildcards), et éventuellement autres contraintes statistiques.

Select T
From node as XY, template X*Y* as T
Where X.url !=”/balk.html” and X.support>40 and Y.url=”/kontakt.html”

8. Requête d’extraction de motifs par MINT dans WUM

Une modélisation des parcours de navigation sur un site par un langage généré par une Grammaire Probabiliste Hypertextuelle (GPH)1 est présentée par (Borges et al., 1999). Cet article utilise un modèle de N-Gram, où il est supposé que seulement les N dernières pages visitées affectent la probabilité d’identification de la page suivante. En outre, les propriétés statistiques du langage sont estimées en utilisant l’entropie de la GPH.

(Pei et al., 2000) proposent une solution efficace aux difficultés de la fouille des motifs séquentiels très longs qu’éprouvent les algorithmes de types Apriori, ou GSP (Generalized Sequential Pattern mining algorithm, de Agrawal & Srikant, une extension de l’algorithme Apriori pour la fouille de séquences), en introduisant WAP-Tree une structure d’arbre très concis pour la représentation des séquences et un algorithme efficace de fouille de cette structure appelé WAP-Mine. Les résultats d’évaluations ont montrés des améliorations en terme de performances par rapport à GSP. .

Lire le mémoire complet ==> (Prétraitement & Extraction de Connaissances en Web Usage Mining)
S2WC2 : un WUM Framework Centré Utilisateur
Mémoire En vue de l’obtention du diplôme de Magister – Option : Informatique et Communication Electronique
Département des Mathématiques et d’Informatique – Spécialité : Informatique
Université Kasdi Merbah de Ouargla – Faculté des Sciences et Sciences de l’Ingénieur