Stand der Technik bei der Deduplizierung

Was sind die neuesten Methoden bei der Deduplizierung von Datensätzen? Die Deduplizierung wird manchmal auch als Datensatzverknüpfung, Entitätsauflösung, Identitätsauflösung, Zusammenführen / Löschen bezeichnet. Ich kenne zum Beispiel CBLOCK [1].

Ich würde mich freuen, wenn die Antworten auch Verweise auf vorhandene Software enthalten würden, die die Methoden implementiert. Ich weiß zum Beispiel, dass Mahout ein Baldachin-Clustering implementiert . Es gibt auch Herzog , der Lucene benutzt.

Es gibt viele kommerzielle Systeme zur Deduplizierung. Es wäre wertvoll zu wissen, wie sie funktionieren und wie effizient sie sind.

Ich interessiere mich sowohl für die Deduplizierung innerhalb eines einzelnen Datensatzes als auch für die Verknüpfung mehrerer Datensätze aus verschiedenen Quellen. Effizienz und Fähigkeit, große Datenmengen zu verarbeiten, sind ebenfalls wichtig.

[1] CBLOCK: Ein automatischer Blockierungsmechanismus für umfangreiche Deduplizierungsaufgaben

Tamr (vormals Data Tamer) führt die Datenbank-Deduplizierung im Maßstab durch. Naive Bayes und Graph Clustering sind beteiligt.

Ich glaube, die Algorithmen sind größtenteils in SQL implementiert, was etwas seltsam ist, aber der Hauptautor ihres Whitepapers ist Michael Stonebraker, der an der Entwicklung von PostgreSQL mitgewirkt hat.

Lesen Sie hier das Whitepaper .

Bearbeiten: Ich habe die Schritte zusammengefasst, die ihr Artikel unten ausführt. Einige meiner Worte sind fast die gleichen wie in ihrer Zeitung.

Das Deduplizierungssystem von Tamr umfasst zwei Hauptschritte für den Umgang mit einer neuen Datenquelle: (1) Attributidentifikation und (2) Entitätskonsolidierung. Dies entspricht in etwa der Deduplizierung von Spalten und Zeilen.

1) Beim Vergleich einer neuen Datenquelle mit einer vorhandenen ist der erste Schritt die Attributidentifizierung.

Die Attribute (Spalten) der neuen Quelle werden mit vier Algorithmen auf die Attribute der vorhandenen Quelle abgebildet:

• Attributnamen mit Fuzzy-String-Vergleich vergleichen (Trigramm-Cosinus-Ähnlichkeit)
• Betrachten Sie eine ganze Spalte als Dokument, markieren Sie sie, messen Sie die Cosinus-Ähnlichkeit zwischen dieser und anderen Spalten (TF-IDF = Total Frequency / Inverse Document Frequency).
• Minimale beschreibende Länge: Vergleichen Sie zwei Spalten basierend auf der Größe ihrer Schnittmenge und Vereinigung mit exakter Übereinstimmung.
• Führen Sie bei numerischen Spalten einen T-Test zwischen der neuen Spalte und den vorhandenen numerischen Spalten durch, um festzustellen, ob sie aus derselben Verteilung stammen.

2) Entitätskonsolidierung (Zeilendeduplizierung)

Sobald die Attributidentifizierung durchgeführt wurde, möchten wir die Zeilen (Datensätze) deduplizieren.

Kategorisierung mit Clustering

Datensätze werden zunächst auf der Grundlage der Ähnlichkeit in Kategorien gruppiert , und dann werden Deduplizierungsregeln auf Kategorieebene gelernt. Das Beispiel für eine Kategorisierung ist eine Datenbank mit Skigebieten, in denen westliche Skigebiete eine andere Kategorie als östliche Skigebiete darstellen sollten, da Merkmale wie die Grundhöhe stark davon abhängen, ob das Skigebiet östlich oder westlich liegt. Die Kategorisierung erfolgt mit einem Clustering-Algorithmus am Beispiel von k-means.

Deduplizieren mit Naive Bayes

Sobald Attribute identifiziert und Datensätze in Kategorien gruppiert wurden, lernen wir die Deduplizierungsregeln für jede Kategorie basierend auf einem Trainingssatz von Dupes und Nicht-Dupes.

Es gibt zwei Arten von Deduplizierungsregeln:

1. Schwellenwerte für Attributähnlichkeiten in Bezug auf eine Abstandsfunktion, die für das Attribut sinnvoll ist. (Das Papier ist nicht klar, wie diese Schwellenwerte gelernt werden.)
2. Wahrscheinlichkeitsverteilungen für Duplikate und Nicht-Duplikate in jedem Attribut. zB P("Title" values similar | duplicate) ~ 1und Pr("State" values are different | duplicate) ~ 0

Für jedes Datensatzpaar berechnen wir die Ähnlichkeit der einzelnen Attribute mit einer geeigneten Abstandsmetrik. Wenn ein Attribut eine Ähnlichkeit oberhalb seines Schwellenwerts aufweist, wird das Datensatzpaar durch einen Naive Bayes-Klassifizierer geleitet, um als Dupe oder Nicht-Dupe klassifiziert zu werden.

Meine Annahme ist , dass für die Datensätze X1 = (a1,b1,c1,d1), X2 = (a2,b2,c2,d2)sie einen Ähnlichkeitsvektor zu berechnen , S = (s_a, s_b, s_c, s_d)wo s_iÄhnlichkeit für das Attribut WRT auf die korrekte Distanzmetrik ist.

Ich nehme an, ihr Naive Bayes-Klassifikator hat diese Struktur:

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

Entitätsauflösung mit Diagrammclustering

Nach dem Klassifizierungsschritt haben wir eine Untermenge von Datensätzen aus einer bestimmten Kategorie, die als paarweise Duplikate gelten. Diese müssen nun in verschiedene Einheiten aufgelöst werden . Dies löst ein Transitivitätsproblem: Wenn Datensatz t1 ein Duplikat von t2 und t2 ein Duplikat von t3 ist, dann muss t1 auch ein Duplikat von t3 sein. Dies bedeutet, dass t1, t2 und t3 dieselbe Entität darstellen .

Für diesen Schritt wird eine Diagrammstruktur verwendet. Innerhalb der Kategorie ist jeder Datensatz, der eine Dupe sein kann, ein Knoten. Knoten, bei denen der Verdacht besteht, dass sie Dupes voneinander sind, haben Kanten zwischen sich. Cluster werden dann im Diagramm erkannt und anhand von Schwellenwerten zusammengeführt, die angeben, wie stark ein Cluster mit einem anderen verbunden ist. Hier sind drei Beispiele für Clusterpaare, die aufgrund ihrer Verbundenheit zusammengeführt werden können oder nicht:

  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

Wenn der Algorithmus endet, sollte jeder Cluster eine eigene Entität innerhalb der Kategorie darstellen . Um den Vorgang abzuschließen, müssen die Attribute dieser Entität aus den Attributen der darin enthaltenen Datensätze ermittelt werden . Zuerst werden Nullen verworfen, dann werden Methoden wie Häufigkeit, Durchschnitt, Median und Längste verwendet.

In dem Artikel werden auch einige Methoden für die Verwendung von Domänenexperten entwickelt, um zu helfen, wenn die Algorithmen unsicher sind, und wie mehrere Experten mit unterschiedlichem Fachwissen verwendet werden.