L’implémentation de l’index avec MapReduce

L’implémentation de l’index avec MapReduce

La fusion des données

Cette étape consiste à créer dans le schéma intégré, une classe ayant pour attributs, l’ensemble des attributs des classes à intégrer et pour instances, l’union des instances [34], où les données de toutes les sources sont fusionnées pour être enregistrées par la suite dans la nouvelle base uni_ée sous une forme cohérente. L’objectif de cette étape est de trouver les valeurs consistantes pour remplacer les valeurs con_ictuelles des doublons détectés dans l’étape précédente (voir section 2.2.3.2). À cause des mises-à-jour très fréquentes et le nombre énorme des sources, la fusion des données en mode o_ine (la construction d’une base uni_ée) devient impossible, ce qui a incité les chercheurs à proposer des méthodes de fusion online [11, 35]. Cependant, cette tâche est très compliquée, car il faut retourner les réponses en temps réel. Dans [35], les auteurs ont proposé une solution qui consiste à sélectionner une réponse à partir de la première source. Cette réponse sera rafraîchie en consultant les autres sources car la qualité d’une réponse dépend de la qualité de la source qui la fournit.

En e_et, une valeur sera retournée comme réponse, si elle atteint un certain niveau de con_ance (niveau de qualité). Les auteurs n’ont pas mentionné comment estimer la qualité de la source ou comment les entités du monde réel sont identi_ées. Cette thèse ne traite pas le problème d’intégration. Nous sommes intéressés plus par les étapes de matching des enregistrements (détection des doublons) et l’étape de fusion (réconciliation des données) pour l’intégration virtuelle des données. Nous nous focalisons sur le problème de sélection d’une seule valeur consistante parmi l’ensemble de valeurs con_ictuelles correspondant à la même entité du monde réel en mode online, c’est-à- dire sans faire des modi_cations sur les sources de données, car nous considérons que la fusion se fait d’une manière virtuelle. Autrement dit, nous e_ectuons un nettoyage de réponses aux requêtes. Nous présentons dans la section suivante le concept de nettoyage de données d’une manière générale. 2.3 Dé_nition du nettoyage de données Le nettoyage de données est un processus qui consiste à détecter et à supprimer des erreurs et des incohérences de données a_n d’améliorer la qualité des données [36].

Ce problème émerge aussi bien dans des bases de données individuelles que lors de la fusion et l’intégration de plusieurs bases. En e_et, les problèmes de données sont présents dans les bases de données individuelles, comme par exemple les erreurs de saisie, les valeurs manquantes, etc. Cela nécessite un e_ort pour les nettoyer a_n de sauvegarder la cohérence de ces bases de données (BD). Cependant, la nécessité pour le nettoyage des données augmente de façon signi_cative lorsqu’il s’agit de l’intégration de plusieurs sources de données (notamment dans l’étape de fusion), comme par exemple, pour les entrepôts de données, les systèmes de bases de données fédérées, etc. En plus de la détection et la correction des données erronées, un aspect important du nettoyage des données est l’identi_cation des causes fondamentales des erreurs détectées. Cela permet d’améliorer le processus de saisie de données pour éviter la reproduction de ces erreurs [37]. En construisant une vision globale des bases de données distribuées (intégration virtuelle), beaucoup de problèmes sont posés tels que la représentation des données sous des formats di_érents et la redondance (duplication) des enregistrements. C’est dans ce genre de problèmes que nous parlons de la notion de réconciliation de données, où nous devons retourner des réponses non con_ictuelles mais sans nettoyer les sources de donn ées (sans réparation). Dans notre travail, nous nous intéressons à cette problématique. En revanche, il existe des travaux tels que [38] qui considèrent que le nettoyage et la réconciliation de données désignent le même processus.

Discussion

Les MDs visent à identi_er les tuples qui représentent la même entité du monde réel dans le cadre de réparation de données. Cependant, cette méthode ne peut pas être appliquée dans le cas des systèmes qui ne tolèrent pas les modi_cations. L’application des règles de MDs nécessite plusieurs comparaisons a_n de détecter les tuples qui ont des valeurs similaires pour les attributs de LHS. C’est pourquoi, nous ne pouvons pas les appliquer en mode online. Le problème avec ce genre de dépendances, c’est qu’elles permettent de réconcilier les données des sources deux par deux (une règle est dé_nie sur deux sources), car elles sont proposées pour réconcilier les données d’une source et les données de Master data (les données avec la con_ance=1 ), alors que dans la pratique, nous trouvons plusieurs sources sans Master data. En outre, à notre connaissance, il n’existe pas des fonctions de matching (MFs) qui permettent d’identi_er les bonnes valeurs avec lesquelles nous remplaçons les données en con_its pour les attributs de la partie RHS. Malgré le fait que les MFs [12] ont été proposées pour sélectionner les valeurs qui dominent sémantiquement l’ensemble de valeurs con_ictuelles, cette méthode ne peut pas être appliquée sur les données catégorielles ou contradictoires. Une autre solution consiste à réconcilier les données des di_érentes sources en se basant sur la con_ance pour choisir la bonne réponse. Cela peut causer d’autres erreurs, car nous ne pouvons pas nous baser sur la décision d’une seule personne (l’utilisateur qui introduit les tuples et leurs con_ances) pour modi_er les données des autres sources. De plus, dans le cas de plusieurs sources, nous devons réconcilier les données deux à deux, donc une donnée peut être modi_ée plusieurs fois.

Réconciliation de données

En intégrant les données provenant de plusieurs sources, beaucoup de problèmes sont posés tels que la représentation des données sous des formats di_érents ce qui conduit à la création des doublons. Ces derniers représentent des con_its de données au moment de l’interrogation d’une base de données, ce qui a_aiblit la qualité des réponses retournées. Ainsi, la détection des doublons est devenue une étape cruciale pour la résolution des contradictions. Alors que la littérature regorge des approches de détection des doublons correspondant à la même entité du monde réel [2_10] et des méthodes d’intégration de données de plusieurs sources [11_13, 19, 66], la plupart de ces approches tendent à éliminer les informations erronées provenant des sources, ce qui conduit à ce qu’on appelle la réparation de données (nettoyage de données), et cela tout en supprimant les inconsistances. Cependant, dans les applications du monde réel, le nettoyage des données incohérentes peut être très coûteux, et peut conduire à une perte de données potentiellement utiles. Cela a motivé les chercheurs pour proposer de nouvelles méthodes pour assurer des ré- ponses cohérentes aux requêtes [35, 67], malgré la présence de ces données incohérentes. Le principe de ce genre de méthodes est de détecter automatiquement les données inconsistantes à partir des réponses, et retourner des réponses nettoyées sans modi_er les données dans les sources [68]. Ces approches se basent sur les contraintes d’intégrité traditionnelles comme les dépendances fonctionnelles (FDs). Cependant, les FDs sont insu_santes pour capturer les incohérences à cause de leur expressivité limitée. Dans ce chapitre, nous abordons le problème de déduplication des réponses aux requêtes en mode en ligne (online), appelé réconciliation des données, et cela par l’application des règles de réconciliation de données (DRRs) [17] dérivées des MDs [8, 13, 14].

Notre solution [17] permet de détecter automatiquement les doublons lors de l’arrivée de la requête, et permet d’identi_er e_cacement la version cohérente des données fournies à l’utilisateur en guise de réponse à sa requête, tout en conservant les données incohérentes dans les sources. Pour atteindre cet objectif, nous complétons les MDs par une fonction de réconciliation qui retourne parmi un ensemble de valeurs en con_its, représentant la même entité du monde réel, les valeurs les plus consistantes. En d’autres termes, cette fonction permet d’estimer la qualité de toutes ces valeurs a_n de retourner la valeur de meilleure qualité, et cela en tirant pro_t des règles de qualité nommées CFDs [4, 9, 15, 16]. Nous proposons une méthode qui se base sur les DRRs pour construire en o_ine un index (DRI Data Reconciliation Index) contenant tous les doublons des sources de données et leurs valeurs réconciliées. Cet index est utilisé pour accélérer la réconciliation des doublons des réponses aux requêtes. Le DRI met en ÷uvre une stratégie basée sur des pivots a_n d’éliminer les doublons non pertinents dans les réponses aux requêtes. Les autres parties de ce chapitre sont organisées comme suit : dans la section 3.2, nous rappelons la dé_nition du problème de réconciliation. Dans la section 3.3, nous illustrons ce problème par un exemple de motivation. Nous introduisons les règles que nous avons proposées pour la réconciliation dans la section 3.4 et nous détaillons le cadre de l’approche proposée dans la section 3.5. Dans la section 3.6, nous présentons l’algorithme, que nous avons élaboré pour la réconciliation des données en ligne ODRA (Online Data Reconciliation Algorithm). En_n, nous montrons comment utiliser les retours d’expé- rience des utilisateurs pour améliorer la qualité des réponses fournies, dans la section 3.7, et nous concluons dans la section 3.8.

Table des matières

Résumé
Remerciements
Liste des Figures
Liste des Tables
Glossaire
1 Introduction Générale
1.1 Contexte
1.2 Motivations et problématique
1.3 Contributions
1.4 Plan de thèse
2 Etat de l’art
2.1 Introduction
2.2 L’intégration de données
2.2.1 Dé_nition
2.2.2 Les architectures d’intégration
2.2.2.1 Intégration matérielle
2.2.2.2 Intégration virtuelle
2.2.3 Étapes d’intégration de données
2.2.3.1 L’alignement de schéma
2.2.3.2 Le matching des enregistrements
2.2.3.3 La fusion des données
2.3 Dé_nition du nettoyage de données
2.4 Problèmes de données
2.4.1 Les valeurs manquantes
2.4.2 Les données erronées (Erreurs de saisie)
2.4.3 Les données dupliquées (doublons)
2.4.4 L’hétérogénéité
2.5 Etapes du processus de nettoyage de données
2.5.1 L’analyse syntaxique
2.5.2 La transformation des données
2.5.3 La véri_cation
2.5.4 L’appariement
2.5.5 Correction des données erronées
2.6 Les di_érentes méthodes de nettoyage de données
2.6.1 Classi_cation des di_érentes méthodes de nettoyage
2.6.1.1 Méthodes statistiques
2.6.1.2 Méthodes basées sur le Clustering
2.6.1.3 Méthodes basées sur les patterns
2.6.1.4 Méthodes basées sur les règles d’association
2.6.2 Les avantages et les limites des méthodes de nettoyage
2.6.2.1 Méthodes statistiques
2.6.2.2 Méthodes basées sur les clusters
2.6.2.3 Méthodes basées sur les patterns
2.6.2.4 Méthodes basées sur les règles d’association
2.7 Détection des doublons
2.7.1 Les règles de matching : MDs
2.7.2 Discussion
2.8 Interaction entre la détection des doublons et la réparation des données
2.9 Conclusion
3 Réconciliation de données
3.1 Introduction
3.2 Problème de Réconciliation
3.3 Exemple de motivation
3.4 Règles de Réconciliation (DRRs)
3.4.1 Dé_nition
3.4.2 Syntaxe
3.4.3 Sémantique des DRRs
3.4.4 L’approche de réconciliation
3.4.4.1 Les propriétés de Reconcile
3.4.4.2 Mesure de qualité des attributs
3.5 Le cadre de notre approche
3.5.1 L’index de réconciliation (DRI)
3.5.1.1 Clusters des doublons
3.5.1.2 La liste des top-k valeurs consistantes
3.5.1.3 La stratégie basée sur le pivot
3.5.2 La construction et la maintenance du DRI
3.6 Traitement des requêtes
3.6.1 Le Matching des requêtes et DRRs
3.6.2 Détection des doublons
3.6.3 La sélection des réponses
3.7 Retour d’expérience des utilisateurs
3.8 Conclusion
4 L’utilisation du Crowdsourcing pour la réconciliation des données
4.1 Introduction
4.2 La notion de Crowdsourcing
4.2.1 Dé_nition
4.2.2 L’architecture générale du crowdsoucring
4.2.3 Le fonctionnement des systèmes de crowdsoucring
4.3 Le crowdsourcing et la qualité de données
4.4 Panorama des travaux basés sur le crowdsourcing
4.4.1 Coreleone
4.4.2 CrowdER
4.4.3 Arnold
4.5 Utilisation du Crowdsourcing pour la réconciliation
4.6 CrowdMD
4.7 Génération des MDs
4.7.1 Étiquetage d’échantillon
4.7.2 Génération de RHS
4.7.3 Table de similarité
4.7.3.1 La table
4.7.3.2 La table
4.7.4 Génération de LHS
4.8 Estimation du taux d’erreurs
4.9 Conclusion
5 Implémentation et Evaluation
5.1 Introduction
5.2 Evaluation de l’approche de réconciliation
5.2.1 Description du Data Set
5.2.1.1 Règles de qualité de données
5.2.2 Installation Expérimentale
5.2.3 Résultats des expérimentations
5.2.3.1 Construction et maintenance du DRI
5.2.3.2 L’e_cacité d’ODRA
5.2.3.3 La scalabilité
5.2.3.4 Qualités des sources
5.3 Implémentation du CrowdMD
5.3.1 Interface de Crowdsourcing
5.3.2 Les HITs
5.4 Conclusion
6 Conclusion et Perspectives
6.1 Conclusion
6.2 Perspectives
6.2.1 L’implémentation de l’index avec MapReduce
6.2.2 La génération des DRRs avec le Crowdsoucring
6.2.3 L’étude de requêtes complexes
A Les opérateurs de similarité
A.1 Les mesures de similarité basées sur les caractères
A.1.1 La distance d’édition
A.1.2 La distance de GAP a_né
A.1.3 La distance de Jaro
A.1.4 Les Q-Grammes
A.2 Les mesures de similarité basées sur les jetons
A.2.1 Les Q-Grammes avec TF-IDF
A.3 Les mesures de similarité phonétiques
Bibliographie

Télécharger le rapport complet