État de l'art en matière de déduplication

Quelles sont les méthodes de pointe en matière de déduplication des enregistrements? La déduplication est aussi parfois appelée: couplage d'enregistrements, résolution d'entité, résolution d'identité, fusion / purge. Je connais par exemple CBLOCK [1].

J'apprécierais que les réponses incluent également des références aux logiciels existants mettant en œuvre les méthodes. Je sais par exemple que Mahout implémente le clustering de la canopée . Il y a aussi Duke qui utilise Lucene.

Il existe de nombreux systèmes commerciaux de déduplication. Il serait utile de savoir comment ils fonctionnent et leur efficacité.

Je m'intéresse à la fois à la déduplication au sein d'un même ensemble de données et à la liaison entre plusieurs ensembles de données provenant de différentes sources. L'efficacité et la capacité de traiter de grandes quantités de données sont également importantes.

[1] CBLOCK: un mécanisme de blocage automatique pour les tâches de déduplication à grande échelle

Tamr (anciennement Data Tamer) effectue la déduplication de la base de données à grande échelle. Naive Bayes et le regroupement de graphes sont impliqués.

Je crois que les algorithmes sont largement implémentés en SQL, ce qui est quelque peu étrange, mais l'auteur principal de leur livre blanc est Michael Stonebraker, qui a aidé à diriger la création de PostgreSQL.

Consultez le livre blanc ici .

Edit: J'ai résumé les étapes de leur article ci-dessous. Certains de mes mots sont presque les mêmes que dans leur article.

Le système de déduplication de Tamr comporte deux étapes principales pour gérer une nouvelle source de données: (1) l'identification d'attribut et (2) la consolidation d'entité. Celles-ci sont à peu près équivalentes à la déduplication des colonnes et à la déduplication des lignes.

1) En comparant une nouvelle source de données à une source existante, la première étape est l'identification des attributs.

Les attributs (colonnes) de la nouvelle source sont mappés aux attributs de la source existante avec quatre algorithmes:

• Comparer les noms d'attributs avec une comparaison de chaînes floues (similitude de cosinus trigramme)
• Considérez une colonne entière comme un document, jetez un jeton, mesurez la similitude de cosinus de fréquence totale / fréquence de document inverse (TF-IDF) entre celle-ci et d'autres colonnes.
• Longueur descriptive minimale: comparez deux colonnes en fonction des tailles de leur intersection et de leur union avec une correspondance exacte.
• Pour les colonnes numériques, effectuez un test t entre la nouvelle colonne et les colonnes numériques existantes pour déterminer si elles proviennent de la même distribution.

2) Consolidation d'entités (déduplication de lignes)

Une fois l'identification des attributs effectuée, nous voulons dédupliquer les lignes (enregistrements).

Catégorisation avec clustering

Les enregistrements sont d'abord regroupés en catégories en fonction de la similitude, puis les règles de déduplication sont apprises au niveau de la catégorie. L'exemple qu'ils donnent de la catégorisation est pour une base de données de stations de ski, où les stations de ski occidentales devraient être une catégorie différente des stations de ski orientales, car les caractéristiques telles que l'élévation de la base sont fortement séparées selon que la station est à l'est ou à l'ouest. La catégorisation se fait avec un algorithme de clustering, avec k-means donné à titre d'exemple.

Déduplication avec Naive Bayes

Une fois les attributs identifiés et les enregistrements regroupés en catégories, nous apprenons les règles de déduplication pour chaque catégorie en fonction d'un ensemble d'apprentissage de dupes et de non-dupes.

Il existe deux types de règles de déduplication:

1. Seuils pour les similitudes d'attributs par rapport à une fonction de distance qui a du sens pour l'attribut. (Le document n'est pas clair sur la façon dont ces seuils sont appris.)
2. Distributions de probabilité pour dupe et non-dupes dans chaque attribut. par exemple P("Title" values similar | duplicate) ~ 1et Pr("State" values are different | duplicate) ~ 0

Pour chaque paire d'enregistrements, nous calculons la similitude de chacun de leurs attributs avec une métrique de distance appropriée. Si un attribut a une similitude au-dessus de son seuil, la paire d'enregistrements est alimentée via un classificateur Naive Bayes pour être classée comme dupe ou non dupe.

Mon hypothèse est que pour les enregistrements X1 = (a1,b1,c1,d1), X2 = (a2,b2,c2,d2)ils calculent un vecteur de similitude S = (s_a, s_b, s_c, s_d)où s_iest la similitude de cet attribut par rapport à la métrique de distance correcte.

Je suppose que leur classificateur Naive Bayes a cette structure:

P(dupe|S) = P(dupe)P(s_a|dupe)(s_b|dupe)(s_c|dupe)P(s_d|dupe) / P(S)

Résolution d'entité avec regroupement de graphes

Après l'étape de classification, nous avons un sous-ensemble d'enregistrements d'une catégorie donnée qui sont censés être des doublons par paire. Ces problèmes doivent maintenant être résolus en entités distinctes . Cela résout un problème de transitivité: si l'enregistrement t1 est une dupe de t2 et t2 est une dupe de t3, alors t1 doit également être une dupe de t3. C'est-à-dire que t1, t2 et t3 représentent la même entité .

Une structure graphique est utilisée pour cette étape. Dans la catégorie, chaque enregistrement qui peut être une dupe est un nœud. Les nœuds soupçonnés d'être dupes les uns des autres ont des bords entre eux. Les clusters sont ensuite découverts dans le graphique puis fusionnés en fonction de seuils concernant la force de connexion d'un cluster à un autre. Voici trois exemples de paires de clusters pouvant ou non être fusionnées en fonction de leur connectivité:

  c1        c2    

x-x-x-----y-y-y
|\|/|     |\|/|
x-x-x-----y-y-y  Meets similiarity threshold
|/|\|     |/|\|
x-x-x-----y-y-y    

x-x-x     y-y-y
|\|/|     |\|/|
x-x-x-----y-y-y  Does not meet similarity threshold
|/|\|     |/|\|
x-x-x     y-y-y    

    x     y
    |     |
    x-----y      Meets similarity threshold
    |     |
    x     y

Lorsque l'algorithme se termine, chaque cluster doit représenter une entité distincte au sein de la catégorie . Pour terminer le processus, les attributs de cette entité doivent être déterminés à partir des attributs des enregistrements qu'elle contient . Les valeurs nulles sont d'abord éliminées, puis des méthodes comprenant la fréquence, la moyenne, la médiane et la plus longue sont utilisées.

Le document développe également quelques méthodes d'utilisation d'experts du domaine pour aider lorsque les algorithmes ne sont pas sûrs, et comment utiliser plusieurs experts avec différents niveaux d'expertise.