Extraction de connaissances en WUM et applications

By 4 May 2013

3.6 Extraction de connaissances et applications

Une fois les données brutes d’usage préparées et formatées dans la phase précédente, elles seront prêtes à l’application des techniques de fouille de données en vue d’en extraire des motifs de navigation intéressants. Cette phase de découverte de connaissances est la plus favorite et préférée par les acteurs de la fouille de données, car elle en permet d’explorer et d’évaluer leur différentes méthodes et algorithmes (Markov et al., 2007).

Il est reporté dans la littérature qu’un nombre illimité de techniques peut être appliqué en WUM, qui varient en complexité entre celles relativement simples reposant par exemple sur l’analyse exploratoire statistique à celles plus laborieuses basées sur des modèles formels et/ou probabilistiques (Srivastava et al.,2000).

Dans cette section, nous passons en revue quelques travaux dédiés à la phase d’extraction de connaissances en WUM. La présentation ne prétend pas ni l’exhaustivité ni l’approfondissement, et nous ne s’étalons donc pas sur les détails de chaque méthode, mais nous nous contentons notamment sur l’étude des principaux paradigmes explorés dans cette phase à savoir : l’analyse statistique et OLAP, les règles d’association, la segmentation/classification, et en fin les motifs séquentiels. Afin d’alléger ce mémoire, les différentes applications du WUM sont aussi parallèlement évoquées de façon sommaire.

3.6.1 L’analyse statistique

La majorité des applications commerciales en WUM exploitent des techniques issues de l’analyse statistique descriptive (Facca et al., 2005), qui reste l’approche la plus commune pour l’extraction de connaissances sur l’utilisation des sites par les internautes (Srivastava et al., 2000).

Cette famille d’outils1 d’analyse de logs permet de calculer, présenter sous différentes formes, et éditer certaines grandeurs afférentes à la description des données telles que la fréquence, la moyenne, la médiane, … etc. sur des variables comme la longueur de la session, la durée de visite, le nombre et la fréquence d’accès aux pages, le temps par page…etc., dérivées à partir des fichiers logs après prétraitement (Cooley, 2000), (Markov et al., 2007). La figure suivante montre, à titre d’illustration, quelques résultats d’une analyse descriptive du site web www.awstat.net, que nous avons tirée de (Benabdeslem, 2003).

Résumé de statistiques appliquées sur le fichier log du site : www.awstat.net
Figure 7. Résumé de statistiques appliquées sur le fichier log du site : www.awstat.net

Même avec le foisonnement de ce genre d’outils, (Zaîane et al., 1998) constate, suite à une évaluation d’une vingtaine de produits d’analyse statistique de logs, qu’ils restent rigides et limités dans les résultats qu’ils fournissent. Néanmoins, la superficialité de leurs analyses ne les rend pas totalement inutiles. En effet, ces outils outre qu’ils ont été exploités premièrement dans la mesure de trafic dans les réseaux, puis dans l’examen de certaines classes d’erreurs de bas niveau comme la détection de points d’entrée non autorisés et l’identification des URI invalides, ils peuvent servir et supporter plusieurs autres précieuses tâches telles que pour améliorer la performance d’un système, renforcer la sécurité d’un site, ou aider à sa refonte ou encore pour élaborer des décision de marketing (Cooley, 2000).

1 Plusieurs sites Internet maintiennent des listes de ces outils. Visité par exemple le site de l’université de UPPSALA, à l’url suivant : http://www.uu.se/software/analyzers/access-analyzers.html

3.6.2 OLAP

OnLine Analytical Processing dont la source de données est toujours un entrepôt de données (un cube multidimensionnel) est une autre forme d’exploration de données d’usage du web offrant un cadre d’analyse plus intégré et flexible. Dans la majorité des cas, les entrepôts de données en WUM intègrent en plus des données d’usage des données de contenu pour chaque dimension. Les outils OLAP offrent l’avantage de permettre le changement dans le niveau d’agrégation le long de chaque dimension pendant l’analyse. De plus, les résultats de leurs requêtes peuvent constitués l’entrée à une variété d’outils de fouille ou de visualisation de données (Mobasher, 2006).

WebLogMiner présenté dans (Zaiane et al., 1998 ) est un système de cette famille d’outil. Il permet l’analyse, par les opérations drilldown, rollup, slide et dice, sur plusieurs dimensions telles que : l’url, l’utilisateur, le type de ressource, la taille de ressource, le temps de requête, la durée de consultation, le logiciel client, l’état du serveur, définies dans des hiérarchies de concepts afin de faciliter la spécialisation et la généralisation. Bien que, dans ce papier, les auteurs se focalisent sur l’analyse des séries temporelles, les données d’usage collectées et fouillées par WebLogMiner ont servi à contrôler la charge et les performance d’un système de e-learning, et d’examiner comment il est exploité par un groupe d’apprenants.

3.6.3 Les règles associatives

Les règles d’association (RA) sont une technique élémentaire en ECD. Elles cherchent à trouver des corrélations et des dépendances entres items (produits, pages, utilisateurs etc.). En WUM, elles sont utilisées pour rapporter et identifier les pages web communément référencées ensemble dans les sessions des utilisateurs. Cette technique, basée souvent sur des algorithmes de type Apriori, est effectuée en deux phases : premièrement les ensembles de pages apparaissant ensemble et vérifiant un seuil de support sont d’abord sélectionnées. À partir de ces ensembles dits itemsets fréquents ou larges les règles satisfaisant un autre seuil de confiance sont ensuite générées (Cooley, 2000).

Rappelons qu’une règle d’association prend la forme d’une implication (si antécédent alors conséquence [Support, Confiance]), par exemple une règle du genre A.html, B.html  C.html, exprime que si l’utilisateur a visité les pages A et B, alors il est très probable (selon la confiance de la règle) qu’il a visité aussi la page C dans la même session.

L’un des problèmes cruciaux dans cette tâche est de garantir une certaine efficacité dans les algorithmes d’extraction. En effet, le nombre d’items impliqués et les règles à découvrir peut être très élevé, ce qui affectera de manière significative les performances. C’est ainsi que le recours à des techniques de réduction de dimensionnalité a été adopté dans plusieurs travaux. Dans le même ordre d’idées, de multiple projets en WUM ont choisi la structuration des données sous forme d’arbres compacts, pour la représentation et le stockage des itemsets fréquents, afin d’accroître l’efficacité dans le processus de découverte (Mobasher, 2006).

Par ailleurs, un support minimum global pour l’ensemble de données est toujours fixé au départ dans les algorithmes standard d’extraction de RA. Ceci ne permet de découvrir que les items les plus importants, et ne peut en aucune façon déceler les éléments rares. Pour résoudre ce problème, une approche de découverte de RA reposant sur l’utilisation de multiples supports minimums a été introduite dan (Liu et al., 1999). Elle prend en considération la nature et la fréquence des éléments dans l’ensemble de données, qui sont souvent différents dans beaucoup d’applications réelles.

(Spilioupoulou, 1999) propose un modèle formel pour la représentation des motifs de navigation, il utilise GSM (G-Sequence Miner) une extension de l’algorithme Apriori au séquences généralisées définies dans ce modèle. Cet algorithme prend en entrée non pas le log original mais une version résumée de celui-ci appelée arbre de log agrégé, où les séquences ayant le même préfixe sont fusionnés.

Un log sous forme d’un arbre agrégé
Figure 8. Un log sous forme d’un arbre agrégé

WebSIFT (Web Site Information Filter) est un système de WUM, qui implémente en utilisant l’algorithme célèbre Apriori, entre autres tâches, la découverte de règles associatives (Cooley, 2000).

La connaissance de RA permet de les exploiter dans plusieurs applications (Cooley, 2000). Elles peuvent servir pour restructurer un site, en insérant par exemple de nouveau liens entres des pages découvertes comme associées mais qui ne sont pas directement connectées, et dans la construction de systèmes de recommandation en e- commerce (Schafer et al., 1999), (Lin et al., 2002), ou encore dans l’implémentation d’heuristiques de prérécupération de ressources (prefetching), par l’amélioration de schémas de cache, afin de réduire les latences (Cunha et al., 1997),(Nanopoulos et al., 2002).

3.6.4 La segmentation

Comme nous l’avons introduit dans le premier chapitre, la segmentation est une technique d’ECD qui consiste à rassembler dans des groupes homogènes, appelés clusters ou segments, des éléments ayant des caractéristiques similaires. Elle est habituellement effectuée comme étape préliminaire dans les processus de fouille, car elle permet de réduire l’espace d’exploration des données. En outre, les clusters produits par cette technique peuvent servir comme données d’entrées pour d’autres algorithmes d’ECD (Markov et al., 2007). Dans le cadre du WUM, deux principaux types de clusters sont généralement à découvrir : les clusters d’utilisateurs et les clusters de pages (Srivastava et al., 2000).

La segmentation des utilisateurs a été l’une des techniques les plus investies en WUM. Elle a fait l’objet de multiples travaux qui s’intéressent à former des groupes d’utilisateurs exhibant des comportements de navigation semblables (Shahabi et al., 1997),(Fu et al., 1999),(Paliouras et al., 2000),(Wang et al., 2002),(Abraham et al., 2003),(Rangarajan et al., 2004).

D’une manière générale, les traces de navigations qu’on assimile à des transactions utilisateurs sont associées à un espace multidimensionnel de vecteurs de vues de pages auquel on applique les algorithmes de segmentation connus (tel que K-means). Ces algorithmes tentent de partitionner cet espace à un ensemble de groupes de transactions qui soient proches les unes des autres en fonction d’une mesure de distance ou de similitude entre vecteurs. Les clusters obtenus représentent des segments d’internautes basés sur leurs motifs de navigation, et éventuellement sur d’autres attributs capturés dans le fichier log.

Etant donné que l’objectif dans cette tâche est principalement de permettre d’analyser chaque cluster afin d’en dériver des connaissances exploitables dans les différentes applications (e-commerce, personnalisation, prefetching…etc.), et du fait que les clusters obtenus ne constituent pas en eux même un moyen efficace pour capturer une vue agrégée du comportement des utilisateurs, car ils peuvent inclure des milliers d’utilisateurs et impliquer des centaines de pages. On cherche plutôt, après la production des segments, une vue résumée de chaque segment en calculant par exemple son vecteur centroide (ou vecteur moyen) (Mobasher, 2006).

(Shahabi et al., 1997) présentent un profiler coté client réalisé par un agent java distant pour la collecte de traces de navigation. Les auteurs, après avoir défini un espace de caractérisation des parcours de navigation, introduisent une méthode de segmentation adoptant le cosinus de l’angle définie entres les chemins comme fonction de distance. L’algorithme k-means est appliqué ensuite dans la production des clusters.

Une segmentation hiérarchique des utilisateurs, en se basant sur leurs motifs de navigation, est proposée dans (Fu et al., 1999). Après une phase de prétraitement, les sessions des utilisateurs sont généralisées en utilisant une induction basée sur les attributs, dans le but de réduire la dimension des données. En premier lieu, une hiérarchie de pages, dérivée de la syntaxe des urls, est construite où chaque page terminale (simple page) est remplacée par une autre plus générale dans la hiérarchie. Les sessions ainsi généralisées sont ensuite segmentées en utilisant l’algorithme BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)1.

(Paliouras et al., 2000) discutent et analysent trois méthodes de segmentation2, en vue de construire des modèles de communautés d’utilisateurs, en identifiant ses traits caractéristiques dans une phase de post-traitement. L’évaluation des méthodes étudiées a portée sur la comparaison de quatre critères : le nombre, la taille, la séparation et la couverture des clusters générés.

Contrairement aux travaux précédents (Wang et al., 2002) introduit une nouvelle mesure de similarité entre les sessions web, qui prend en compte la séquence d’événements dans le log. L’idée est de considérer une session comme un ensemble de séquences, et d’appliquer ensuite l’approche de l’alignement des séquences emprunté de la biologie moléculaire (étude des séquences d’ADN). Pour ce faire, les urls sont d’abord représentés en adoptant une codification sous la forme de chaînes de digits, la similarité revient donc à comparer les chaînes représentant chaque page (définie par son url). Cette notion de similarité est étendue aux sessions en les considérant comme une séquence de visites de pages. La programmation dynamique est utilisée pour trouver les bonnes correspondances entre ces séquences.

Plusieurs autres travaux ont étudié l’application des techniques de softcomputing dans la segmentation en WUM. Dans (Ragarajan et al., 2004) un réseau de neurones

compétitif de type ART1 (Adaptive Resonance Theory) à deux couches (à trois couche dans (Tanasa et al., 2004a), et de type SOM dans (El Golli et al. 2004)) est utilisé pour segmenter les utilisateurs. Cette architecture a été exploitée dans l’implémentation d’un système de prefetching, dont les résultats d’évaluation comparés à k-means ont montré une nette avancée en terme de distance intra-clusters. De plus, la précision de la prédiction des requêtes futures a atteint 97.78%. Une solution hybride, combinant un algorithme d’optimisation par les fourmis artificiels et un modèle de programmation génétique, est présentée dans (Abraham et al., 2003).

1 Proposé par Zhang T. et al., en 1996, dans un article intitulé : BIRCH an efficient data clustering method for very large databases, diponible sur : http://citeseer.ist.psu.edu/zhang96birch.html
2 Il s’agit de AUTOCLASS, les cartes de Kohonen et un algorithme proposé par les auteurs basé sur la segmentation des graphes.

Motionnons enfin, que de nombreuses méthodes stochastiques ont été récemment proposées pour la segmentation des motifs de navigation des utilisateurs, telles que les mélanges de modèles (mixtures models) et l’analyse sémantique latente probabilistique. Ces modèles sont capables de capturer un comportement utilisateur plus complexe et dynamique (Mobasher, 2006),(Zhang et al., 2006).

La segmentation de pages quant à elle est réalisée soit en se basant sur les données d’usage (données du log), soit sur celles de contenu (mots-clé, attributs…). Dans la première catégorie les pages référencées souvent ensemble sont organisées automatiquement en groupes, dans la deuxième classe les résultats donnent les pages ayant un contenu lié.

Les clusters d’utilisateurs sont beaucoup plus utilisés dans les tâches de personnalisation (Perkowitz et al., 1997),(Mobasher et al., 2000) afin de livrer un contenu adapté aux utilisateurs du même cluster, ou dans la segmentation de marchés en e-commerce. D’un autre coté, les moteurs de recherche (Joachims, 2002), (Kammenhuber et al., 2006) et les assistants à la navigation (Joachims et al., 1997) se servent des segments de pages pour proposer des liens similaires fondés sur les requêtes ou l’historique des besoins des utilisateurs (Cooley, 2000). .

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