Reconstruction des surfs : Algorithme de sessionisation

By 4 May 2013

4.4.2 Reconstruction des surfs

A l’opposé des approches centrées serveur, qui se basent sur des heuristiques pour la reconstruction de sessions, notre travail permet, en fonctionnement normal, de connaître avec exactitude les moments de démarrage de navigations et leurs instants de fermeture.

Dans ce point, nous introduisons la notion de surf, qui correspond à une séance de navigation. Un surf commence donc à la détection du lancement d’une ou de plusieurs instances d’IE (évènements de type 01). Il est déclaré terminé, lorsque toutes ses instances sont achevées (évènements de type 03), sans aucune condition sur sa durée, ou les laps de temps le séparant des autres.

Etant donné que la reconstruction est effectuée seulement à posteriori, il a été constaté, en présence de certaines situations d’erreurs, que cette reconstruction n’est pas aisée. Par exemple, il impossible, en l’absence de suivi en ligne et en temps réel, de détecter la destruction anormale ou prématurée d’une instance d’IE active pour laquelle aucun évènement de fermeture n’est enregistré dans le log. Si non résolu, ce type de situation engendrera des navigations à longueur (durée) étrange voire infini, et rend la procédure de sessionisation quasi-impossible. Cette question est traitée dans le point suivant.

4.4.2.1 Détection et résolution des fenêtres non terminées

Durant un surf, les fenêtres non terminées sont celles démarrées mais n’ayant pas émis normalement un évènement de fermeture (code 03). Ce genre de situation se produit dans les cas de fermetures inopinées de l’instance du navigateur, suite entre autres, à un arrêt brutal du système, ou à la destruction de la fenêtre active par un outil de type filtre de contenu, ou pop-up blocker (outils bloquant les fenêtres publicitaires, ou autres indésirées).

Afin de résoudre de pareils cas, un balayage préalable et complet du log est la seule solution. Durant ce scan, nous détectons et séparons les fenêtres sans terminaisons. Nous devons, en suite, induire des instants de terminaisons pour chacune d’entre elles. A cet effet, trois solutions sont proposées fixant les instants de fins pour ces fenêtres :

1. ignorer la suite des évènements qu’aurait eu déclenchés la fenêtre, et la déclarer terminée au dernier évènement enregistré.
2. dans le même surf, assigner à la fin de la fenêtre, l’instant de l’évènement suivant immédiatement dans le log (il correspond obligatoirement à une autre fenêtre).
3. ajouter un évènement de terminaison fictif, après une durée égale à la moyenne du rythme de déclenchement des évènements pour la fenêtre concernée. L’algorithme de résolution des fenêtres non terminées est le suivant.

Procedure fenetres_sans_fin
Entrée m : dans 1,2,3 pour approche à utiliser.
Sortie : table des fenêtres non terminées, avec des instants de fin.
debut
Ouvrir la table LOG ;
Créer une table F_NON_Terminée et l’initialiser ; Pour chaque utilisateur Ui(Maci,Logini) faire Appliquer un filtre à LOG pour les entrées de Ui ; Tant que non LOG.EOF faire Lire (Item) ;
f Id_Fenetre(Item);
e Evènement (Item);
_debut Date_Heure(Item);
si ealors iserer f dans F_NON_Terminée avec le numéro d’entrée du log;
sinon debut
le numéro d’entrée du log pour f N° entrée en cours du log ;
f.fin _debut ;
fin de si (* 2 * )
sinon // evènement de fermeture d’IE
si f trouvé dans F_NON_Terminée alors la supprimer fin de si (* 1 *) LOG.suivant;
Fin tant que ;
Annuler le filter pour LOG ;
Réouvrir F_NON_Terminée depuis le debut ; Tant que non F_NON_Terminée.eof faire Selon la méthode (m) faire :
1 :dans LOG, aller_au_dernier_évènement de la fenetre et récupérer son début dans _debut ;
2 : dans LOG, aller_au_premier_évènement_suivant_immediatement le dernier de la fenetre et récupérer son début dans _debut ;
3 : à partir de LOG, calculer la moyenne dans _debut
Modifier l’entrée de F_NON_Terminée en mettant Fin _debut ; F_NON_Terminée.suivant ;
Fin tant que ;
Fin de fenetres_sans_fin

14. Détection et résolution des fenêtres sans fin

Une fois les fenêtres non terminées identifiées et résolues, nous pouvons entamer la phase de sessionisation. La description de l’algorithme correspondant à cette phase est ci-dessous donnée.

4.4.2.2 Algorithme de sessionisation

L’objectif de la procédure de sessionisation est de reconstruire les différents surfs comme ils ont été parcourus par un utilisateur, en se basant sur les données stockées dans son fichier log. En prenant donc en entrée le fichier log nettoyé, nous devons produire d’une part un fichier de surfs délimités par leurs instants de début et de fin, et d’autre un deuxième fichier de pages visitées avec, pour chacune, des bornes temporelles.

Dans une situation sans erreur, la visite d’une seule page web triviale engendrera précisément par ordre chronologique trois lignes dans le fichier log. Une première de début de navigation (évènement 01), une seconde de fin de téléchargement de la page (évènement 02), et une dernière de fermeture du browser (évènement 03). Si c’est le cas, la sessionisation est alors très simple et intuitive. Toutefois, la situation se complique lors des visites effectuées sur les pages et les sites plus élaborés. En effet, avec les développements constants de la technologie de construction des pages web (frames, dynamisme, redirection…etc.), et le pullulement des publicités sur le net, nous avons constaté, que pour une requête vers une page de cette catégorie le schéma décrit plus haut n’est plus conservé, et que souvent le log consigne de multiple évènements de début de navigation, et de fin de téléchargement.

Mentionnons que dans la phase de nettoyage, nous n’avons considéré que les problèmes des items inutiles au regard à leurs urls, et des frames. Des questions comme les pages publicitaires, et les formes complexes d’équivalence d’urls ne sont pas prise en considération. Ce genre de problèmes nécessite la connaissance d’autres données à l’échelle du web, qui ne sont pas néanmoins à notre portée.

La succession des lignes du fichier log, réduites aux types évènements déclenchés, dans une situation sans erreur, peut être exprimée en fonction d’expressions régulières de la façon suivante :

visite d’une seule page web simple : (01)(02)(03)
visite d’une seule page plus complexe, i>0, et 0<=j<=i : (01)i(02)j(03)

15. Suites d’évènements pour une page simple ou complexe

L’algorithme de sessionisation démarre, pour les entrées de chaque utilisateur, depuis le début. En parcourant le log, il fait associer des évènements de début de navigation à d’autres de fin de téléchargements correspondants. Les débuts des évènements étant connus, l’algorithme ci-dessous détermine, en s’appuyant sur les identifiants de fenêtres du navigateur, les instant de fin pour chaque surf effectué, fenêtre ouverte et page consultée.

Procedure reconstruire_surfs
Entrée : log nettoyé, liste des utilisateurs couples (@Mac,Login) , table des fenêtres non terminées résolues.
Sortie : tables des surfs,pages, et fenêtres
Inititialisation : Liste_Fenetre nil ; Liste_Page nil ;
Appliquer un filtre sur le log,et la table F_Non_Terminées avec @mac et le login en entrée
Tant que non log.eof faire
{ Item entrée courante ;
// Récupérer l’id de la fenêtre, l’évènement, l’url, le titre, et le time f Id_Fenetre(Item) ;
e Evènement(Item);
u Url(Item) ;
t Titre(Item) ;
tps Time(Item) ;
Si f inexistante dans Liste_Fenetres alors // nouvelle navigation
Si e=1 alors // debut de navigation ok
Si pas de surf ouvert alors ouvrir un surf ; fin si Nouvelle_Fenetre(f,tps) ; // creation dans Liste_fenetres Nouvelle_Page (u,tps,t) ; // Creation dans Liste_Pages de f Verifier s’il n’ya pas une entrée à terminer dans F_Non_Terminée ;
Sinon item orphelin l’ignorer ; // 1 nouvelle fenetre doit
fin si //commencer par un debut de navigation
Sinon // la fenetre existe
{Verifier s’il n’ya pas une entrée à terminer dans F_Non_Terminée ;
Si f n’est pas terminée alors // permet d’ignorer les items orphelins
Selon e faire
1 : { // debut de navigation
Si la page inexistante dans Liste_Pages
alors // visite d’1 nouvelle page Terminer la page proche ; Nouvelle_Page(u,tps,t) ;
Sinon // revisite
Si telechargement terminée de la page alors //revisite Terminer la page ; Nouvelle_Page(u,tps,t) ;
Sinon réinitialiser la page ;// page non completement visualisée
//réinitialiser son debut}
2 : { // fin de téléchargement
Si la page existe dans Liste_Pages alors la terminer ; Sinon terminer celle la plus proche dans la fenetre ; }
3 : Terminer la fenetre f ; // fin d’IE Fin selon
Item Log.suivant ;
} // Fin tant que ;
Fin reconstruire_surfs ;

16. Reconstruction de surfs

Cet algorithme utilise la procédure, ci-dessous décrite, pour la terminaison d’une fenêtre.

Procedure Terminer_fenetre
Entree : l’id de la fenêtre f, et time l’instant de fin
Sortie : la fenêtre et les pages qu’elle a ouvert avec instant de fin
Si la fenetre active est la dernière alors terminaison du surf en cours.
Debut
Accéder dans la liste des fenetre à f ;
f.fin time ;
Nbre de fenetres ouvertes– ;
Pour chaque page de f faire terminer les pages non encore terminées ; Ecrire les résultats ; // le surf, les fenêtres et les pages ouvertes Si Nbre de fenetres ouvertes nul alors terminer le surf ; fin
si ;
Fin terminer_fenetre

17. Procédure de terminaison d’une fenêtre

4.4.2.3 Des surfs aux sessions

Les tests que nous avons menés en se basant sur les fichiers des surfs comme nous l’avons définis dans les points ci-dessus, nous ont montrés une très grande disparité entre les navigations des utilisateurs. En effet, nous avons trouvé des surfs d’une durée insignifiante, et d’autre de longueur de l’ordre de quelques heures. De plus les surfs de certains utilisateurs ne sont séparés que parfois de très courts laps de temps. Afin de produire des fichiers de navigations plus significatives, nous avons estimé utiles de générer en plus un fichier de sessions telles qu’elles sont définies par les travaux centrés serveur (Cf. chapitre 3). Pour rappel, dans ces travaux une session est définie par l’ensemble des requêtes effectuées par un utilisateur en respectant un seuil d’inactivité de 30 minutes. Nous avons donc ajouté un module permettant de compacter les surfs générés par l’algorithme précédent, en produisant une table de sessions. Cette dernière et celle des surfs vont constituer nos données d’entrée dans l’étape de segmentation.

Procedure Compacter_surfs_en_sessions ; Entree : la table des surfs
Sortie : la table des sessions (compactage de surfs) NumSession 1
Pour chaque user Ui dans la tables des utilisateurs faire
Fusionner_Surfs(Ui) ;
Recodifier_Pages(Ui) ( positionner l’id_session) NumSession++
Fin_Compacter_surfs_en_sessions ;
//————————————————————–
Fusioner_Sufs(u)
// D1 et D2 deux variables Date
Appliquer un filtre avec code_user=u sur la table des Surfs ; Si Nombre de records de Surfs positif alors
Inserer_nouvelle_session ; Session.debut Surf.debut; D1 surf.fin ;
_duree 0 ; _nbfenetres 0 ; _nbpages 0 ; Tant que non fin de Surf faire
D2 Surf.debut ; Delta D2-D1 ;
Si Delta>= 30 mn alors
fermer la session en cours avec :
Fin=D1 ; nbfenetres=_nbfenetres ; nbpages=_nbpages ; duree=_duree ; Reinitialiser _duree, nb_fenetres,nb_pages à 0 ;
Inserer une nouvelle session avec
Debut=D2, nbfenetres=surf.nbfenetres; nbpages=surf.nbpages; Fin de si ;
_duree _duree+surf.duree ;
_nbfenetres _nbfenetres+surf.nbfenetres;
_nbpages _nbpages+surf.nbpages; D1 Surf.fin;
Sessions.fin D1
Surf.suivant
Fin tant que
Annuler le filtre à Surf
Fin fusionner_surfs ;

18. Compactage de surfs en sessions.

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