Les techniques d’ECD : le formatage et la segmentation

By 4 May 2013

4.4.3 Formatage

En dépits de la suite des traitements effectués dans les procédures précédentes, les données obtenues ne sont pas prêtes à une application directe de la technique d’ECD. Le formatage a pour but, en prenant en considération les objectifs de l’analyse et la technique d’ECD projetée, d’adapter d’avantage ces collections de données, en vue de la production de fichier des surfs selon le format reconnu par l’outil de fouille qui sera exploité.

4.4.3.1 Calcul des durées de visite

Dans la majorité des travaux en WUM, l’importance d’une page dans un surf est fonction de la durée de visites que prend un utilisateur sur cette page et/ou de la fréquence de ces visites. Une fois la procédure de sessionisation achevée, nous pouvons calculer les durées pour les surfs effectués, les fenêtres ouvertes, et pages visitées. D’une manière simple, ces laps de temps sont déterminés alors en mesurant l’écarts entres les instants de fins et de débuts des évènements caractérisants les commencements et les fermetures des surfs, fenêtres, ou pages, calculés dans la procédure de sessionisation.

Procedure calculer_durée
Entrée : date et heure de l’évènement de debut (J1,H1,M1,S1,MS1)
date et heure de l’évènement de fin (J2,H2,M2,S2,MS2)
Sortie : durée en secondes des surfs, fenetres, ou de visites de pages
// la fin et le debut sont enregistrés dans le même jour
Si J2-J1=0 alors Durée=(H2-H1)*60*60+(M2-M1)*60+S2-S1+(MS2-MS1)/1000;  Sinon
Si J2-J1=1 alors // cas des surfs s’étalant après minuit Durée=(24+H2-H1)*60*60+(M2-M1)*60+S2-S1+(MS2-MS1)/1000; Sinon Vérifier cet item //
Fsi.

19. Calcul des durées

4.4.3.2 Post filtrage des items insignifiants ou aberrants

La production des durées pour les différents items manipulés nous a permis de déceler certains groupes d’items dont cette durée nécessite un examen. En effet, les horloges systèmes des utilisateurs n’étant pas souvent fiables, nous avons trouvés, à titre d’exemple, des items avec des durées de visite négatives ce qui est n’est pas naturel. D’un autre côté, les requêtes provenant des serveurs de publicité et qui ne sont pas nettoyées dans la première étape, se trouvent affectées des durées de visites faibles dans le cas où elles ne sont pas explicitement suivies par l’usager.

Afin de résoudre toutes ces situations, nous avons estimé judicieux de définir un intervalle de validité pour tous les items, en fixant des valeurs seuils (un minimum d’une minute et un maximum de douze heures ont été adoptés dans notre application). Ceci permettrait de cribler à la fois les items à très faible durée de visite, et ceux plus lent considérés alors comme aberrants.

Dans cette étape, nous avons aussi éliminé, au regard à leurs titres, les pages n’ayant pas retourné les contenus escomptés des utilisateurs, mais renvoyant des messages d’erreur tel que : serveur introuvable, HTTP 500 Erreur interne au serveur…etc.

4.4.4 Traitement du contenu

Etant donné que notre étude est centrée sur l’usage et non pas sur le contenu des pages et/ou des sites, nous n’avons pas intégré suffisamment d’informations de contenu dans la phase de prétraitement et d’ECD. Toutefois, nous avons prévu, comme déjà mentionné, la récupération en temps réel des titres des pages visitées. Ce seul attribut collecté dans cette version se manifeste sous la forme de phrases, généralement en trilingues (arabe, français, ou anglais), pour lesquelles des techniques issues de la communauté TAL sont utilisées dans leur préparation. Ces méthodes, telles que l’élimination des stopwords, et le stemming, sont souvent complexes et très lourdes. elles nécessitent le recours à des connaissances puisées dans la majorité des cas de dictionnaires, thésaurus, ou des répertoires lexico-sémantiques dont WordNet (Cf. wordnet.princeton.edu/) est, pour la langue anglaise, le plus exploité. L’approche ci-après estimée plus simple a été adoptée.

4.4.4.1 Catégorisation semi-automatique de pages

Il nous a paru très difficile de réaliser un regroupement (Cf. section suivante) des surfs des utilisateurs en se basant uniquement sur les données décrites jusqu’ici. Les identifiant des pages, comme les durées de visites, et les autres attributs sont purement numériques. De plus, la fonction de distance (euclidienne) utilisée dans ce regroupement ne reflète pas généralement les proximités souhaitées. Afin de simplifier la démarche, et obtenir des résultats plus au moins palpables, nous avons opté pour une catégorisation des pages visitées en prenant en compte leurs contenus. Pour ce faire nous avons implémenté un algorithme semi-automatique consistant à attribuer manuellement à une page une catégorie (prises parmi une liste préétablie) durant son premier examen, et d’attribuer cette même catégorie automatiquement à toutes les autres pages du log traité ayant soit le même url, ou un titre proche. Ce processus est répété jusqu’à épuisement du log. Les catégories élaborées suite à un examen manuel des logs sont listées ci-dessous (RI : signifie recherche d’information).

Thèmes de la catégorie Code
RI google 1
RI google en arabe et arab web 2
RI google images, videos et livres 3
RI yahoo France 4
RI msn 5
RI autres portails ou dictionnaires 6
yahoo mail 10
Messenger 11
Hotmail 12
Gmail 13
Download, software, book, tools… 20
Forum, échange et groupes 21
Développement, exploitation d’environnements 25
jeux 30
TV, videos, photos et music 32
Journaux, magazines, news, emploi shopping et sports 35
Sites algériens 40
Recherches, conférences … 50
Religion 60
Autres non classées (erreurs, pages perso…) 70

Figure 15. Catégories construites pour les contenus des pages

4.5 Segmentation

A l’issue de la phase de prétraitement des logs bruts, l’ensemble des surfs effectués par les utilisateurs ont été identifiés et reconstitués à partir des requêtes vers les pages visitées, en conservant à la fois l’ordre de consultation et le temps passé sur chacune des pages. A ce stade, nous pouvons entamer la phase d’extraction de connaissances, où nous nous intéressons à la segmentation (clustering) de ces surfs, en opérant un regroupement homogène de ceux-ci au vu de certaines propriétés les caractérisant.

Rappelons que la segmentation, comme une technique d’ECD, a été choisie car, outre qu’elle n’exige aucune autre connaissance que les données à fouiller, elle reste souvent une tâche réalisée comme étape préliminaire dans les projets d’ECD. Elle permet aussi d’une part de réduire la dimension des données initiales, et d’autre de produire des informations (les clusters) pouvant ultérieurement alimentés en amont plusieurs autres techniques d’ECD.

Dans les points suivants, nous introduisons les mesures de similarités entre items, ainsi que la modélisation des données que nous avons adoptées. Nous rappelons également l’algorithme de segmentation choisi, et présentons les outils d’ECD que nous avons utilisés dans nos expérimentations.

4.5.1 Mesures de similarité

Les données que nous nous disposons sont les pages (ou les catégories de pages) visitées, matérialisées par leurs urls (ou les ids des catégories), et les surfs effectués qui sont rien d’autre que les listes ordonnées de pages (catégories de pages) consultées auxquelles sont associées les durées de visite correspondantes. Il nous faut donc, pour fins de segmentation, définir une mesure de similarité afin d’exprimer la similitude entre les pages web, et une deuxième pour comparer les surfs des utilisateurs.

4.5.1.1 Similarité entre pages web

En ce qui concerne les pages web, les urls avec les durées constituent les seules données d’usage que nous pouvons exploité dans le cadre de WUM. Bien que, la chaîne de caractères représentant l’url est un élément purement syntaxique dépourvu en général de sens, nous avons pourtant tenté de revoir la codification numérique des urls, que nous avons défini lors de la phase de prétraitement. Les identifiants attribués jusqu’alors aux urls n’obéissent à aucune logique, et nous ont servi seulement durant l’opération de chargement. Notre objectif est plutôt de pouvoir attribuer des identifiants numériques proches à des urls de pages semblables.

Pour ce faire, l’approche que nous avons adoptée est basée sur les algorithmes de comparaison de chaînes de caractères (string matching), dont l’objectif est d’évaluer le degré de ressemblance des chaînes en rapprochant élément par élément les caractères qui les composent. Pour des raison de simplicité, nous avons retenu la distance de Levenshtein1, dite aussi distance d’édition, qui demeure la plus basique et utilisée (Runkler et al., 2003). Cette distance est définie comme étant le nombre minimal d’opérations d’édition (insertion, suppression, substitution) nécessaire pour passer d’une chaîne source à une seconde chaîne cible.

1 Son nom provient de Vladimir Levenshtein qui l’a définie en 1965.

L’application de ce nouveau mapping nous a permis d’améliorer la représentation numérique des urls, comme le montrent les exemples de la figure suivante. Toutefois, cette codification reste bien entendu encore limitée, et certes source de perte d’information. Seul la prise en compte de données de contenu permettrait de résoudre de façon satisfaisante cette question.

url nouveau identifiant ancien identif.
ftp://ftp-developpez.com/heureuxoli
www.developpez.com/delphi
www.developpez.net/forum
www.google.com
www.google.co.uk
www.google.com.sa
www.google.com/mb
www.google.fr/mb
www.google.fr/ig
www.google.fr
maps.google.fr
images.google.fr
images.google.com
mail.google.com
mail.google.com/mail
mail.live.com/mail
mail.yahoo.com
games.yahoo.com
groups.yahoo.com
sports.yahoo.com
fr.sports.yahoo.com
fr.docs.yahoo.com
fr.search.yahoo.com
search.yahoo.com
www.pdfchm.com/search
www.pdfchm.com/auth
www.pdfchm.com/book
www.pdfchm.com/link
www.pdfchm.com
elabweb.free.fr
elabweb.free.fr/inc
elabweb.free.fr/admin
elabweb.free.fr/annuaire
avunet.info.free.fr/annuaire
avunet.info.free.fr/inc
avunet.info.free.fr/cfp
avunet.info.free.fr
avunet.free.fr/
sunmat.free.fr
1
9
14
255
259
262
265
268
270
273
276
279
282
285
288
291
366
369
372
375
378
381
384
387
1573
1576
1579
1582
1585
2539
2542
2545
2549
2555
2560
2563
2566
2570
2573
106
1323
115
2
1831
149
150
1145
483
128
539
380
317
454
396
1713
14
1279
1464
1173
214
1243
639
1131
563
832
550
556
555
147
127
126
177
123
2005
165
164
1277
1940

Figure 16. Exemples d’urls avec nouveau et ancien code numérique

4.5.1.2 Similarité entre surfs web

La comparaison de surfs quant à elle peut être mesurée selon plusieurs métriques. Les plus courants sont la distance euclidienne, le cosinus de l’angle entre vecteurs représentant ces surfs, ou le coefficient de Jaccard (intersection des pages divisée par leur union) (Wang et al., 2002). L’utilisation du coefficient de Dice (Rijsbergen, 1979), défini premièrement dans les SRI comme mesure de distance entre surfs est aussi envisageable. Il nous permet de regrouper les surfs proches selon une fenêtre paramétrée de pages :

Sim (S1,S2)= 2*(nPS1 nPS2)/ | nPS1 | |nPS2|
Où nPSi : est les n items prises à partir des pages du surf i

Notons que, pour des raisons de compatibilités de versions, nous avons utilisés dans nos expérimentations les implémentations des outils d’ECD sans les modifier. La distance euclidienne est alors adoptée dans le regroupement des sessions.

4.5.2 Modélisation

Les surfs des utilisateurs sont représentés par des vecteurs contenants les couples (pagei, duréei) des pages visitées : pagei dénote soit l’identifiant de la page, ou le code de sa catégorie, et duréei la durée de visite. De plus, et afin de prendre en compte les aspects liés à la linéarité et la temporalité des surfs, et des modalités d’usage du navigateur, ces vecteurs sont enrichis par d’autres attributs : tels que : le début de surf codé sur trois période de la journée de 8 heures chacune (matin (0.33), soir (0.66), et nuit (1)), sa longueur (durée totale), le nombre de fenêtres ouvertes, et pages consultées. Notons enfin, qu’étant donné l’approche que nous utilisons, les valeurs de tous les attributs ont été normalisées, comme c’est illustré dans la figure ci-après.

Exemple de surfs sous formes de vecteurs numériques normalisés
Figure 17. Exemple de surfs sous formes de vecteurs numériques normalisés.

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