Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UNIVERSITÉ KASDI MERBAH OUARGLA Faculté des Nouvelles Technologies de l'Informa

UNIVERSITÉ KASDI MERBAH OUARGLA Faculté des Nouvelles Technologies de l'Information et de la Communication Département d'Informatique et des Technologies de l'Information Mémoire Master en Informatique Domaine : Mathématique et Informatique Filière : Informatique Spécialité : Administration et Sécurité des Réseaux Présenté par : Belhachani Fouzia et Rouas Khadîdja Soutenu le : 22/09/2020 Devant le jury composé de : Dr. Amirat Hanane Encadreur UKM Ouargla Mr. Harouz Abdelhakim Président UKM Ouargla Dr. Korichi Merieme Examinateur UKM Ouargla La recommandation des localisations : une nouvelle approche basée sur la fouille incrémentale des règles séquentielles. I Remerciement Tout d'abord, nous remercions Dieu Tout-Puissant pour le courage et la volonté qu'il nous a donnés pour mener à bien cette tâche. Nous remercions chaleureusement Mme Amirat Hanan d'avoir accepté d'être l'’encadreur de notre thèse. Nous la remercions pour le soin avec lequel elle a lu ce mémoire, ainsi que pour ses conseils et ses remarques pertinentes. Nous remercions en Particulièrement nos familles (nos parents) qui ont su nous soutenir, nous encourager, nous aider et nous supporter tout au long de l’année. Nous tenons à remercier les membres de notre jury pour avoir bien voulu consacrer une partie de leurs temps à examiner et à évaluer ce travail. Nous remercions tous nos professeurs et nos camarades qui ont veillé sur nous pendant ces cinq (05) années d’études supérieures. Rouas Khadîdja Belhachani Fouzia II Dédicace À nos chers parents pour tous leurs sacrifices, leur amour, leur tendresse, leur soutien et leurs prières tout au long de nos études. À toutes nos familles (frères et sœurs), et nos amis pour les soutenir tout au long de notre carrière universitaire. À toute personne qui nous a donné son soutien, encouragement, conseils et orientations pour la réalisation de ce travail Tables des matières I 1 Table des matières Liste des tableaux ................................................................................................................................. IV Liste des figures ..................................................................................................................................... V Résumé ................................................................................................................................................. VII Introduction générale .......................................................................................................................... 10 Chapitre 1 ............................................................................................................................................... 6 1 Introduction ................................................................................................................................... 7 2 Réseaux Sociaux Basés Sur la localisation (RSBL) .................................................................... 7 3 La recommandation des POIs ...................................................................................................... 8 4 Préliminaires .................................................................................................................................. 9 5 Les facteurs d’influence .............................................................................................................. 10 5.1 L’influence sociale ............................................................................................................... 10 5.2 L’influence géographique. .................................................................................................. 10 5.3 L’influence temporelle ........................................................................................................ 11 5.4 L’influence séquentielle....................................................................................................... 11 6 Formulation de problème de recommandation des POIs ........................................................ 12 7 Modèles de base de recommandation ........................................................................................ 12 7.1 Modèle de Markov ............................................................................................................... 12 7.2 Le filtrage collaboratif ........................................................................................................ 13 7.2.1 FC basé sur la mémoire .............................................................................................. 13 7.2.2 FC basé sur le modèle.................................................................................................. 14 7.2.3 FC hybride ................................................................................................................... 14 8 Travaux connexes ........................................................................................................................ 14 8.1 Systèmes de recommandation basés sur le filtrage collaboratif ...................................... 15 8.2 Prise en compte des facteurs d’influence ........................................................................... 16 8.2.1 Influence géographique ............................................................................................... 16 8.2.2 Influence sociale ........................................................................................................... 17 8.2.3 Influence temporelle .................................................................................................... 17 8.2.4 Indication du contenu.................................................................................................. 18 8.2.5 Influence séquentielle .................................................................................................. 18 Conclusion ............................................................................................................................................ 20 Chapitre 2 ............................................................................................................................................. 21 1. Introduction ................................................................................................................................. 22 2. Historique ......................................................................................................................................... 23 Tables des matières II 3. Définition de la fouille de donnée (Data mining) .......................................................................... 23 4. Les étapes du processus de la fouille de données ...................................................................... 24 5.1 Les tâches de fouille de données prédictives ..................................................................... 25 5.1.1 La prédiction ....................................................................................................................... 25 5.1.2 La classification ........................................................................................................... 25 5.1.3 L’estimation ................................................................................................................. 25 5.2 Tâches d'exploration de données descriptives .................................................................. 25 5.2.1 Segmentation ou clustering ......................................................................................... 25 5.2.2 La description .............................................................................................................. 26 5.2.3 L’association ................................................................................................................ 26 6 Techniques du la fouille de données ........................................................................................... 26 6.1 Les techniques supervisées.................................................................................................. 26 6.1.1 Les arbres de décision ................................................................................................. 27 6.1.2 Les réseaux de neurones ............................................................................................. 28 6.2 Les techniques non supervisées .......................................................................................... 29 6.2.1 Clustering ..................................................................................................................... 29 6.2.2 Les règles d’association ...................................................................................................... 30 6.2.2.1 Préliminaires ................................................................................................................ 30 6.2.2.2 Extraction des motifs fréquents...................................................................................... 31 6.2.2.3 La génération des motifs fréquents ................................................................................ 31 6.2.2.4 Génération des règles d’association ............................................................................... 32 7 . La fouille de données des règles séquentielles ......................................................................... 32 7.2 Exploration des motifs séquentiels (Sequential patterns mining) ................................... 32 7.2.2 Le support d’une règle séquentielle ........................................................................... 33 7.2.3 La confiance d'une règle séquentielle ........................................................................ 33 8 Conclusion .................................................................................................................................... 34 Chapitre 3 ............................................................................................................................................. 35 1. Introduction ................................................................................................................................. 36 2. Motivations................................................................................................................................... 37 3. Exploration des règles de recommandation .............................................................................. 38 3.1. Extraction des règles de recommandation partiellement ordonnées .............................. 38 4. Architecture du système STS-Rec .............................................................................................. 42 4.1. Modélisation hors ligne ....................................................................................................... 43 4.1.1 Génération des séquences d’emplacement ................................................................ 43 4.1.2 Exploration de règles de recommandation ................................................................ 43 Tables des matières III 4.1.2.1 Exploration incrémentale des règles de recommandation POSR ........................... 43 4.1.3 Recommandation en ligne ............................................................................................... 57 4.1.3.1 Préparation de la séquence d'emplacement .............................................................. 57 4.1.3.2 Correspondance des règles. ........................................................................................ 57 4.1.3.3 Recommandation de POI. ............................................................................................... 57 5. Conclusion .................................................................................................................................... 57 Chapitre 4 ............................................................................................................................................. 59 1. Introduction ................................................................................................................................. 60 2. Enivrement d’expérimentation .................................................................................................. 60 2.1 Jeux de données (Datasets) ................................................................................................. 60 2.2 Modèles évalués ................................................................................................................... 61 2.3 Les métriques d’évaluation ................................................................................................. 61 3 Expériences .................................................................................................................................. 61 3.1 Effet des paramètres ........................................................................................................... 62 4 Conclusion .................................................................................................................................... 63 Liste des tableaux IV Liste des tableaux Tableau 1. 1: Un échantillon de séquences d’emplacement. ................................................................. 10 Tableau 1. 2 : Comparaison des modèles de recommandations de POI. ............................................... 20 Tableau 2. 1: Quelque séquence de base de données. ........................................................................... 31 Tableau 2. 2: Quelques règles séquentielles. ......................................................................................... 34 Tables des figures V Liste des figures Figure 1.1 : La collecte des informations d'enregistrement dans Foursquare.......................................... 8 Figure 1.2: Le comportement séquentiel de mouvement de trois utilisateurs. ...................................... 11 Figure 1.3: Les factures d’influence sur la recommandation dans un RSBL ........................................ 15 Figure 2. 1 : Le processus de la fouille de données. .............................................................................. 24 Figure 2. 2: Les arbres de décisions. ..................................................................................................... 28 Figure 2. 3: Les réseaux de neurones. ................................................................................................... 29 Figure 3. 1: Architecture du system STS-Rec. ...................................................................................... 43 Figure 3. 2 : Architecture de l'approche incrémentale (IncrPOSR). ...................................................... 44 Figure 3. 3: L’arbre ACR après l’insertion des règles R1, R2, R3. ......................................................... 48 Figure 3. 4: l’arbre ACR après l’insertion des règles R4,R5, R6. ............................................................ 48 Figure 3. 5: L’arbre ACR après l’insertion de toutes les règles. ........................................................... 49 Figure 3. 6 :La structure SequenceIndex pour LH. ............................................................................... 50 Figure 3. 7: La structure SequenceIndex 'pour ΔLH. ............................................................................ 50 Figure 3. 8 : Règles de candidature générées à partir de S14 : E2 E3 E1 E8 E11 E7. ................................. 51 Figure 3. 9: L'ensemble des règles valides dans LH'. ............................................................................ 55 Figure 3. 10 : (a) L’état initial du ACR (b) ACR après suppression de la règle E1→ E2. ..................... 55 Figure 3. 11: (c) ACR après suppression de la règle E1→ E3, (d) ACR après suppression de ............. 55 Figure 3. 12:(g, k) nettoyage et attachement des processus et ACR après la suppression de toutes les règles invalides dans LH '. ..................................................................................................................... 56 Figure 3. 13: Mise à jour de l’arbre. ...................................................................................................... 57 Figure 4. 1 : Etude de la scalabilité. ...................................................................................................... 62 Figure 4. 2: Impact de la variation du seuil minfreq ............................................................................. 63 Figure 4. 3 : Impact de la variation de minconf. ................................................................................... 63 VI Résumé VII Résumé Ces dernières années, le développement rapide dans le domaine technologique a stimulé le développement des technologies d'acquisition de localisation et de communication mobile Ce développement a créé de nombreux services de localisation, tels que la recommandation de points d'intérêt (POI). La recommandation des localisations consiste à suggérer à un utilisateur des lieux qu'il pourrait être intéressé à visiter. L’objectif de ce service est d'aider les utilisateurs mobiles à découvrir de nouveaux lieux intéressants (par exemple, des restaurants et des magasins), en déplacement. Dans la littérature, de nombreux modèles de recommandation des POI ont été proposés. Ces modèles tiennent compte de divers facteurs tels que l'influence géographique, temporelle et sociale. Bien que ces modèles se soient avérés performants, peu d'entre eux prennent en compte le comportement séquentiel de la mobilité humaine. En outre, plusieurs modèles ont été conçus en tenant compte des données statiques, ignorant ainsi les collectes continues des données d'enregistrement dans les RSBL (Réseaux Sociaux Basés sur la Localisation). Cela a conduit à la conception des systèmes de recommandations qui doivent être construit à partir de zéro pour effectuer des prédictions actualisées, lorsque de nouvelles données d'enregistrement arrivent. La complexité temporelle et spatiale de ces systèmes de recommandation peut donc augmenter considérablement lorsqu'elle est appliquée sur des données dynamiques. Par conséquent, il est nécessaire de concevoir des systèmes de recommandeurs incrémentales capables de traiter efficacement les données dynamiques. Pour remédier ces limitations, ce mémoire propose une nouvelle approche de recommandation des points d'intérêt, appelée STS-Rec. Ce dernier, basé sur l’extraction des règles séquentielles et il prend en compte le comportement séquentiel de la mobilité humaine. STS-Rec transforme d'abord les données de mobilité en séquences de localisation. Ensuite, il extrait progressivement des règles de recommandation séquentielles à partir de ces séquences. Une évaluation expérimentale menée sur un jeu de données d'enregistrement réel à grande échelle montre que le modèle proposé surpasse la version statique (non incrémentale) de système en termes de temps d’exécution et l’espace mémoire occupé. Mots Clés : extraction incrémentale, règles séquentielles, recommandation de POI, modèle basé uploads/Geographie/ faculte-des-nouvelles-technologies-de-l-x27-information-et-de-la-communication-departement-d-x27-informatique-et-des-technologies-de-l-x27-information.pdf