Communautés dans les réseaux sémantiques pairs-à-pairs, Communities in semantic peer-to-peer networks

De
Publié par

Sous la direction de Mohamed Quafalou, Mohammad Hajjar
Thèse soutenue le 13 juillet 2010: Aix Marseille 2
La première partie de cette thèse est dédiée à l’état de l’art sur les réseaux pair-à-pair, la recherche d’information dans de tels réseaux et la problématique de la fouille des données dans le contexte pair-à-pair en se focalisant plus particulièrement sur les méthodes de regroupement (clustering) et les arbres de décision.La seconde partie traite des réseaux où les pairs disposent de leurs propres schémas de données. On y analyse plus particulièrement les fondements et le fonctionnement du système SenPeer. On propose alors une architecture supportant une organisation communautaire des réseaux pair-à-pairs sémantiques. Cela nous permet alors de construire des réseaux pair-à-pair sémantiques structurés en communautés appelés cSON (CommunitySemantic Overlay Network).Ce qui pose alors les questions concernant l’explicitation des communautés et leur exploitation pour améliorer les performances (temps de réponse, nombres de messages, précision et le rappel). Pour construire les communautés, nous étudions deux alternatives différentes : (1) Médiation sémantique : la construction des communautés se base sur les liens sémantiques entre les super-pairs et la confiance qu’ils ont les uns envers les autres et (2) Clustering : un algorithme de clustering basé sur l’analyse des requêtes traitées par les super-pairs est à la base de construction des communautés. Ensuite, nous proposons deux méthodes pour calculer des caractérisations des communautaires en se plaçant dans les deux champs de recherche suivants : (1) Data mining: on cherche à caractériser chaque communauté à l’aide d’une connaissance extraite des requêtes traitées par ses super-pairs d’une même communauté CK (Communauty Knowledge) et (2) Hypergraphes : A l’inverse de la méthode précédente, notre objectif maintenant est de caractériser collectivement les communautés. On formalise ce problème comme la recherche des MCS (minimal covering shortcuts) qui sont des raccourcis, entre les super pairs,minimaux couvrants toutes les communautés. Nous développons ensuite deux méthodes de routages de requêtes CK-rooting et MCS-rooting en utilisant respectivement la connaissance communautaire et les MCS afin d’identifier les super-pairs susceptibles de traiter une requête donnée.Dans la troisième partie, nous présentons le simulateur développé pour supporter l’approche cSON. Nous présentons alors les résultats empiriques résultant de simulations et qui montrent une amélioration significative des performances de l’approche basée uniquement sur la médiation sémantique. Cette partie se termine avec la description d’une application de recherche d’information basée sur le partage de documents scientifiques enrichis.
-Pair-à-pair
-Communautés
-Simulation
-Hypergraphes
The first part of this thesis is dedicated to the state of the art on the peer-to-peer networks, the information retrieval in such networks, and the problematic of data mining in the peer-to-peer context more particularly on clustering methods and decision trees.The second part deals with networks where peers have their own data schemas. We examine more particularlythe fundamentals and functioning of the system “SenPeer”. Then, we propose an architecture supporting acommunity organization of semantic peer-to-peer networks. This allows us to build peer-to-peer semantic structured communities called cSON (Communauty Semantic Overlay Network).This raises many questions concerning the explanation of communities and their operating to improve performances (response time, number of messages, precision and recall). To build communities, we study two different alternatives: (1) Semantic Mediation: the building of communities is based on semantic links between super-peers and the confidence that they have between them and (2) Clustering: a clustering algorithm, based onthe analysis of queries processed by the super-peers, is the base of community building. Then, we propose twomethods to calculate the characterizations of communities in the two research fields: (1) Data mining: we try to characterize each community using knowledge extracted from applications processed by his super-peers of the same community CK (Community Knowledge) and (2) Hypergraphs: Unlike the previous method, our goal nowis to characterize the communities collectively. We formalize this problem as the research of the MCS (minimalcovering shortcuts) which are shortcuts between the super-peers, minimum shortcuts covering all communities.Then, we develop two methods of queries routing CK-rooting and MCS-rooting respectively using community knowledge and MCS to identify the super-peers may process a given query.In the third section, we present the simulator developed to support the cSON approach. We present the empirical results representing the simulations and which show a significant improvement of performance of the approachonly based on semantic mediation.This part ends with a description of an application of information retrieval based on sharing enriched scientific documents.
-Peer-to-peer
-Communities
-Clustering
-Data minig
-P2p
Source: http://www.theses.fr/2010AIX22057/document
Publié le : jeudi 27 octobre 2011
Lecture(s) : 63
Nombre de pages : 162
Voir plus Voir moins

UNIVERSITÉ DE LA MEDITERRANEE AIX-MARSEILLE II
TITRE :
Communautés dans les réseaux sémantiques pairs-à-pairs
THÈSE
Pour obtenir le grade de
DOCTEUR DE L'UNIVERSITÉ DE LA MEDITERRANEE AIX-MARSEILLE II
Faculté des Sciences et Techniques
Discipline :
École Doctorale en Mathématiques et Informatique de Marseille (ED184)
Présentée par
Anis Ismail
Le 13 JUILLET 2010
JURY
M. Patrick Gallinari Pr., Université Paris 6 Rapporteur
Kokou Yetongnon Pr., Université de Bourgogne Rapporteur
Bruno Defude Pr., TELECOM SudParis Examinateur
Omar Boucelma Pr., Université Paul Cézanne Examinateur
Gilles Nachouki MC., Université de Nantes Examinateur
Mohammad Hajjar Pr., Université Libanaise Co-encadrant
Mohamed Quafafou Pr., Université de la méditerranée Directeur


ANNÉE : 2010





















2





à mes parents,
à ma Femme,
à mes amis.











3
Remerciements

Je tiens tout d’abord à exprimer ma profonde gratitude envers M. Mohamad
Quafafou et M. Mohammed Hajjar qui ont accepté de diriger cette thèse et l’ont
fait de manière constante, avec une disponibilité totale. Leur patience devant
mes difficultés à trouver « le mot juste » et leurs précieux conseils auront permis
l’achèvement de ce travail.

Je suis également reconnaissant à M. Patrick Gallinari, professeur à l’université de
Paris 6 et M. Kokou Yetongnon, professeur à l’université de Bourgogne, pour avoir
accepté d’être rapporteurs et membres de ce jury.

Je tiens à exprimer mes plus vifs remerciements à M. Gilles Nachouki qui m’a aidé à
faire cette thèse. Merci infiniment pour la disponibilité, la patience, les remarques et
suggestions pertinentes durant toute la thèse.

Merci également à M. Bruno Defude, professeur à l’université de TELECOM SudParis et
M. Omar Boucelma professeur de l’université Paul Cézanne et professeur, pour avoir
accepté d’examiner ce travail et faire partie de mon jury de thèse.

Je ne pourrais finir sans inclure dans ces remerciements les personnes les plus chères
pour leur soutien matériel et moral : mes parents, mes frères et ma femme.

4 Sommaire

LISTE DES FIGURES ......................................................................................................................................... 8
LISTE DES TABLEAUX ..................................................................................................................................... 9
LISTE DES ABREVIATIONS .......................................................................................................................... 10
CHAPITRE 1. INTRODUCTION.................................................................................................................... 13
1. MOTIVATIONS ............................................................................................................................................. 13
2. CONTRIBUTION........................................................................................................................................... 14
3. ORGANISATION DU RAPPORT ................................................................................................................ 15
PARTIE I - FONDEMENTS ET ETAT DE L’ART........................................................................................ 19
CHAPITRE 2. RECHERCHE D’INFORMATION DANS LES RESEAUX P2P ....................................... 21
1. INTRODUCTION........................................................................................................................................... 21
2. TYPES DE RESEAUX ................................................................................................................................... 22
3. RESEAUX SEMANTIQUES SUPERPOSES............................................................................................... 24
3.1. RESEAUX SUPERPOSES STRUCTURES ET NON STRUCTURES.......................................................................... 25
3.2. RESEAUX SUPERPOSES SEMANTIQUES ......................................................................................................... 27
4. SYSTEMES DE GESTION DE DONNEES P2P ......................................................................................... 28
5. RECHERCHE D’INFORMATION DANS LES COMMUNAUTES DE PAIRS ..................................... 29
5.1. RECHERCHE D’INFORMATION...................................................................................................................... 30
5.1.1. Généralités .......................................................................................................................................... 30
5.1.2. Contexte .............................................................................................................................................. 30
5.1.3. Profils.................................................................................................................................................. 31
5.1.4. Profils et filtrage ................................................................................................................................. 31
5.2. RECHERCHE D’INFORMATION DANS LES SYSTEMES P2P.............................................................................. 32
5.2.1. Recherche aveugle .............................................................................................................................. 32
5.2.2. Recherche informée............................................................................................................................. 33
5.2.3. Recherche sémantique......................................................................................................................... 35
5.3. COMMUNAUTES DANS LES P2P ................................................................................................................... 39
5.3.1. Construction de communautés ............................................................................................................ 39
5.3.2. Recherche d’information dans les communautés ................................................................................ 41
5.4. CRITERES D’EVALUATION ........................................................................................................................... 41
5.4.1. Critères qualitatifs .............................................................................................................................. 41
5.4.2. Critères quantitatifs ............................................................................................................................ 42
6. CONCLUSION................................................................................................................................................ 42
CHAPITRE 3. FOUILLE DE DONNEES DANS LES RESEAUX P2P....................................................... 44
1. INTRODUCTION.......................................................................................................................................... 44
2. FOUILLE DE DONNEES DANS LE P2P.................................................................................................... 44
3. ARBRE DE DECISION ................................................................................................................................ 46
5 4. CLASSIFICATION NON SUPERVISEE (CLUSTERING)....................................................................... 50
4.1. METHODES DE PARTITIONNEMENT ............................................................................................................. 50
4.2. METHODES HIERARCHIQUES ....................................................................................................................... 54
4.3. METHODES BASEES SUR LES MOTIFS ET LA NOTION DE FREQUENCE ............................................................ 57
4.4. CLASSIFICATION CONCEPTUELLE ................................................................................................................ 61
5. CONCLUSION................................................................................................................................................ 65
PARTIE 2 - APPROCHE COMMUNAUTAIRE POUR LA RECHERCHE D’INFORMATION DANS
LES RESEAUX P2P ........................................................................................................................................... 67
CHAPITRE 4. APPROCHE SEMANTIQUE .................................................................................................. 69
1. INTRODUCTION.......................................................................................................................................... 69
2. ARCHITECTURE GENERALE................................................................................................................... 71
2.1. MODELE COMMUN DE REPRESENTATION DES DONNEES ET DES REQUETES.................................................. 71
2.2. ARCHITECTURE D’UN PAIR.......................................................................................................................... 75
2.3. ARCHITECTURE D’UN SUPER-PAIR............................................................................................................... 76
2.4. CONFIGURATION DU RESEAU....................................................................................................................... 77
3. RECONCILIATION SEMANTIQUE ENTRE PAIRS............................................................................... 79
3.1. SIMILARITE GLOBALE.................................................................................................................................. 79
3.2 SIMILARITE LINGUISTIQUE ........................................................................................................................... 80
3.3. SIMILARITE DE VOISINAGE SEMANTIQUE..................................................................................................... 81
3.4. MATRICES DE CORRESPONDANCE ............................................................................................................... 82
4. MECANISME DE ROUTAGE SEMANTIQUE.......................................................................................... 83
4.1 SELECTION BASEE SUR L’EXPERTISE ............................................................................................................ 84
4.2 SUJET D’UNE REQUETE................................................................................................................................. 84
4.3 FONCTION DE SIMILARITE SEMANTIQUE....................................................................................................... 84
4.4 ALGORITHME DE ROUTAGE SEMANTIQUE..................................................................................................... 85
5. PROPOSITION D’UNE ARCHITECTURE COMMUNAUTAIRE ......................................................... 86
6. CONCLUSION................................................................................................................................................ 87
CHAPITRE 5. APPROCHES COMMUNAUTAIRES : CSON ..................................................................... 89
1. INTRODUCTION.......................................................................................................................................... 89
2. APPROCHE A BASE DE CONNAISSANCES............................................................................................ 91
2.1. CONSTRUCTION DES COMMUNAUTES : CONFIANCE..................................................................................... 92
2.2. ARCHITECTURE D’UNE COMMUNAUTE ........................................................................................................ 93
2.3. CONSTRUCTION DE LA CONNAISSANCE COMMUNAUTAIRE.......................................................................... 95
2.4. ROUTAGE DE REQUETES BASE SUR LA CONNAISSANCE COMMUNAUTAIRE (CK) ......................................... 97
2.5. CONCLUSION............................................................................................................................................... 98
3. APPROCHE A BASE DE COUVERTURES MINIMALES ...................................................................... 99
3.1. THEORIE DES HYPERGRAPHES ................................................................................................................... 100
3.1. 2. Algorithmes de calcul de traverses minimales ................................................................................. 102
3.2. CONSTRUCTION DES COMMUNAUTES : CLUSTERING ................................................................................. 104
2.3. ARCHITECTURE D’UN MCS-SUPER-PAIR (MCS-SP)................................................................................. 106
3.4. Calcul des MCS communautaires ........................................................................................................ 107
3.5. ROUTAGE DE REQUETE DANS L'ARCHITECTURE MCS................................................................................ 109
4. CONCLUSION.............................................................................................................................................. 112
PARTIE 3 - EXPERIMENTATIONS ET APPLICATIONS........................................................................ 113
6 CHAPITRE 6. SIMULATEUR........................................................................................................................ 115
1. INTRODUCTION......................................................................................................................................... 115
2. ARCHITECTURE GENERALE................................................................................................................. 117
3. APPROCHE SEMANTIQUE ...................................................................................................................... 118
3.1 INITIALISATION .......................................................................................................................................... 118
3.2 GENERATION DU RESEAU SON .................................................................................................................. 120
3.3 GESTION DES REQUETES............................................................................................................................. 123
4. CSON : APPROCHE COMMUNAUTAIRE ORIENTEE CONNAISSANCES .................................... 125
5. CSON : APPROCHE COMMUNAUTAIRE BASEE SUR LES MCS .................................................... 126
6. VUE D’ENSEMBLE DU SIMULATEUR CSON ...................................................................................... 129
7. CONCLUSION.............................................................................................................................................. 130
CHAPITRE 7. EVALUATION ET VALIDATION....................................................................................... 131
1. EVALUATION DU ROUTAGE DANS NOS ARCHITECTURES. ........................................................ 131
1.1 OUTILS DE SIMULATION ............................................................................................................................. 131
1.2 CONFIGURATION DU RESEAU CSON..................................................................................................... 131
1.3 MESURES ................................................................................................................................................... 132
2. RESULTATS EXPERIMENTAUX ............................................................................................................ 133
3. APPLICATION............................................................................................................................................. 139
4. MISE EN ŒUVRE DE L’APPLICATION ................................................................................................ 144
5. CONCLUSION.............................................................................................................................................. 145
CHAPITRE 8. CONCLUSION ET PERSPECTIVES .................................................................................. 146
RESUME ........................................................................................................................................................... 162
ABSTRACT....................................................................................................................................................... 162
7 Liste des Figures
Figure 1 Un réseau P2P de 50 nœuds montrant la structure ad hoc. ..................................................................... 21
Figure 2 Système P2P purs. .................................................................................................................................. 23
Figure 3 Système P2P hiérarchique. .................................................................................................................... 24
Figure 4 Réseau superposé (sous-jacent) et réseau physique.............................................................................. 25
Figure 5 Système P2P hybride. ............................................................................................................................. 27
Figure 6 Processus de classification supervisée et prédiction. .............................................................................. 47
Figure 7 Arbre de décision C4.5 (J48) pour les données weather......................................................................... 49
Figure 8 Exemple de dendogramme...................................................................................................................... 55
Figure 9 Exemple de treillis de concepts.............................................................................................................. 63
Figure 10 Réseau Super-pair sémantique organisé par Thèmes............................................................................ 70
Figure 11 Définition de la classe représentant un nœud du modèle interne sGraph [Faye, 2007]. ....................... 73
Figure 12 sGraph partiel sur les références bibliographiques ............................................................................... 73
Figure 13 Format d’échange de requêtes SQUEL [Faye, 2007]. .......................................................................... 74
Figure 14 Architecture d’un pair........................................................................................................................... 75
Figure 15 Architecture d’un super-pair................................................................................................................. 77
Figure 16 Configuration du réseau SenPeer.......................................................................................................... 78
Figure 17 Sélection basée sur l’expertise.............................................................................................................. 85
Figure 18 Architecture générale communautaire (cSON)..................................................................................... 86
Figure 19 Réseau sémantique du Super-Pair organisé par des thèmes et communautés. (Community Knowledge
CK)........................................................................................................................................................................ 92
Figure 20 Architecture d’une communauté (ensemble de domaines – KSP) ........................................................ 95
Figure 21 Un exemple d'hypergraphe. ................................................................................................................ 101
Figure 22 clusters obtenus................................................................................................................................... 106
Figure 23 Architecture d’un MCS-super-peer..................................................................................................... 107
Figure 24 clusters obtenus avec une traverse. ..................................................................................................... 108
Figure 25 Routage de requêtes en utilisant une seule stratégie ........................................................................... 111
Figure 26 Routage de requêtes en utilisant plusieurs traverses.......................................................................... 112
Figure 27 Fonctions génériques .......................................................................................................................... 115
Figure 28 Composants externes et fonctionnement général de cSON. ............................................................... 117
Figure 29 Stratégie de base : approche sémantique............................................................................................. 118
Figure 30 Approche communautaire orientée connaissance. .............................................................................. 125
Figure 31 Approche communautaire basée sur les traverses minimales. ............................................................ 127
Figure 32 Architecture globale du simulateur..................................................................................................... 130
Figure 33 Evaluation temps: Baseline – CK ....................................................................................................... 134
Figure 34 Evaluation temps : Baseline -MCS ..................................................................................................... 134
Figure 35 Nombre de Messages: Baseline - CK ................................................................................................. 136
Figure 36 Précision - Baseline - CK.................................................................................................................... 137
Figure 37 Précision - Baseline - MCS................................................................................................................. 137
Figure 38 Rappel Baseline - CK ......................................................................................................................... 138
Figure 39 Rappel Baseline - MCS....................................................................................................................... 138
Figure 40 Schémas. ............................................................................................................................................. 140
Figure 41 source de données du pair P1.............................................................................................................. 141
Figure 42 Requête Q1 ......................................................................................................................................... 142
Figure 43 Application : partages des références bibliographiques...................................................................... 143
Figure 44 Résultat de la requête Q renvoyé par l’interface de l’application...................................................... 143 1
Figure 45 Réseau P2P de 5 SP. ........................................................................................................................... 144
8 Liste des tableaux
Table 1 Bases de données exemple : weather ....................................................................................................... 49
Table 2 Exemple d'un ensemble de données D1. ................................................................................................ 105
Table 3 Exemple d'un ensemble de données D2. ................................................................................................ 105


9 Liste des abréviations

AD Arbre de Décision
AGNES AGglomerative NESting
APS Adaptive Probabilistic Search
BFS Breadth-first search
BIRCH Balanced Iterative Reducing and Clustering using Hierarchies
CACTUS CAtegorical ClusTering Using Summaries
CAN Content Adressable Network
CF-Tree Clustering Feature Tree
CK Community Knowledge
CLARA Clustering LARge Application
CLARANS Clustering Larger Applications based on RANdomized Search
CLIQUE CLustering In QUEst
COD Clustering with Obstructed Distance
cSON Community Semantic Overlay Network
CURE Clustering Using REpresentatives
DBSCAN Density Based Spatial Clustering of Applications with Noise
DHT Distributed Hash Tables
DIANA DIvisive ANAlysis
DRLP Distributed Resource Location Protocol
DTD Document Type Definition
ECCLAT Extraction of Clusters from Concepts LATtice
EM Expectation-Maximization
FTP File Transfer Protocol
GUESS Gnutella UDP Extension for Scalable Searches
INS Network structure indices
KSP Knowledge Super-Peer
LAN Local Area Network
MCS Minimum Covering Shortcut
OPTICS Ordering Points to Identifying the Clustering Structure
OWL Web Ontology Language
P2P Peer-to-Peer
P2PSL P2P Semantic Link Network
PAM Partition Around Medoids
10

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.