Sammle Daten aus mehr als einer Quelle, oder aus einer Quelle mehr als einmal, und Duplikate folgen zwangsläufig. Dasselbe Produkt taucht auf drei Marktplätzen mit drei leicht unterschiedlichen Namen auf. Dieselbe Firma heißt in einem Register “Acme Widgets Ltd” und in einem anderen “ACME WIDGETS LIMITED”. Derselbe Eintrag erscheint zweimal, weil sich die Paginierung während des Crawlens verschoben hat, oder weil ein Link einen Tracking-Parameter trug und der andere nicht.
Bleiben Duplikate unbeachtet, blähen sie Zählungen auf, teilen den Verlauf über mehrere Datensätze und verfälschen still jede darauf aufbauende Kennzahl. Dieser Leitfaden behandelt, wie man sie auflöst: Normalisierung von Identifikatoren, Abgleich auf starke Schlüssel zuerst, sicheres Fuzzy-Matching in großem Maßstab, Clustering und die Entscheidung, welche Version eines Datensatzes erhalten bleibt.
Wichtigste Erkenntnisse
- Die meisten Duplikate werden durch Normalisierung der Identifikatoren erkannt, bevor überhaupt ein Fuzzy-Matching stattfindet: kanonische URLs, validierte Produktcodes und bereinigte Firmennamen.
- Zuerst auf starke Identifikatoren abgleichen. Eine gültige Barcode-Nummer oder eine Registernummer schlägt jede noch so hohe Namensähnlichkeit.
- Niemals jeden Datensatz mit jedem anderen vergleichen. Eine Million Datensätze ergeben etwa 500 Milliarden Paare; Blocking reduziert das auf ein handhabbares Maß.
- Entscheide, welcher Fehler schwerer wiegt. Für manche Aufgaben ist ein falscher Merge schlimmer als ein übersehenes Duplikat; für andere ist es umgekehrt.
- Herkunft bewahren. Der zusammengeführte Datensatz sollte weiterhin jede Quelle kennen, aus der er stammt.
Drei Arten von Duplikaten
| Art | Beispiel | Wie es erkannt wird |
|---|---|---|
| Wiederholte Erfassung | Dieselbe URL wird zweimal abgerufen, oder sich überschneidende Ergebnisseiten | Kanonische URL oder Quellenkennung |
| Dieselbe Entität, andere Quelle | Ein Produkt auf drei Marktplätzen gelistet | Gemeinsame Identifikatoren, dann Fuzzy-Matching |
| Nahezu identischer Inhalt | Derselbe Artikel mit kleinen Änderungen weiterverbreitet | Inhaltsähnlichkeit, wie in Änderungserkennung im großen Maßstab behandelt |
Dieser Leitfaden konzentriert sich auf die ersten beiden, bei denen das Ziel ein Datensatz pro realem Produkt, Unternehmen oder Eintrag ist.
Schritt 1: Identifikatoren normalisieren
Normalisierung ist billig und erkennt mehr Duplikate als jedes noch so ausgeklügelte Matching.
URLs. Dieselbe Seite kommt unter vielen URLs an. Host kleinschreiben, www. entfernen, Tracking-Parameter wie utm_*, gclid und fbclid entfernen, die verbleibenden Query-Parameter sortieren und abschließende Schrägstriche entfernen. http://www.Shop.com/p/123/?utm_source=x&b=2&a=1 und https://shop.com/p/123?a=1&b=2 werden zu demselben Schlüssel.
Produktcodes. Global Trade Item Numbers (die Nummern hinter UPC- und EAN-Barcodes) tragen eine Prüfziffer, mit der sich falsch getippte oder falsch gescrapte Codes ablehnen lassen, bevor man ihnen vertraut. Die Methode von GS1 gewichtet die Ziffern mit 3, 1, 3, 1 und so weiter, beginnend bei der Ziffer neben der Prüfziffer, summiert sie und nimmt den Betrag, der nötig ist, um auf das nächste Vielfache von zehn aufzurunden. In GS1s eigenem durchgerechneten Beispiel erhält der 11-stellige Rumpf 61414121022 die Prüfziffer 0. Gültige Codes auf 14 Stellen auffüllen, damit eine 13-stellige und eine 14-stellige Version desselben Codes als gleich verglichen werden.
Firmennamen. Groß-/Kleinschreibung und Akzente vereinheitlichen, Satzzeichen entfernen und Rechtsformzusätze wie Ltd, Limited, Inc, GmbH und SA entfernen, bevor verglichen wird. “Acme Widgets Ltd.” und “ACME WIDGETS LIMITED” werden beide zu acme widgets. Wenn ein Unternehmen eine Registernummer oder eine Legal Entity Identifier hat, diese statt des Namens verwenden; die Auflösung von Unternehmen zu Identifikatoren wird in Überwachung der öffentlichen Präsenz Ihrer Lieferanten behandelt.
Schritt 2: Zuerst auf starke Schlüssel abgleichen
Sobald Identifikatoren normalisiert sind, sind exakte Übereinstimmungen darauf sowohl schnell als auch zuverlässig. Zwei Datensätze mit demselben gültigen Barcode sind dasselbe Produkt. Zwei Datensätze mit derselben kanonischen URL sind dieselbe Seite. Zwei Unternehmen mit derselben Registernummer sind dasselbe Unternehmen, wie auch immer sie genannt werden.
Strukturierte Daten helfen hier ebenfalls. Viele Produktseiten veröffentlichen Barcodes und SKUs in JSON-LD, was weit zuverlässiger ist, als sie von der sichtbaren Seite zu scrapen; siehe hört auf, HTML zu parsen.
Schritt 3: Fuzzy-Matching, aber nur innerhalb von Blocks
Datensätze ohne gemeinsame Identifikatoren benötigen Fuzzy-Matching auf Namen, Adressen oder Beschreibungen. Die Falle ist die Skalierung. Jeden Datensatz mit jedem anderen zu vergleichen wächst mit dem Quadrat der Datensatzgröße: eine Million Datensätze ergeben etwa 500 Milliarden Paare.
Blocking löst das. Gruppiere Datensätze nach einem billigen Schlüssel, den echte Übereinstimmungen fast immer teilen, etwa Land plus erstes Wort des normalisierten Namens, oder Marke plus Produktkategorie, und vergleiche nur innerhalb jeder Gruppe. Ein guter Blocking-Schlüssel reduziert die Vergleiche um Größenordnungen, während nur wenige echte Übereinstimmungen verloren gehen. Prüfe von Zeit zu Zeit durch Stichproben von Paaren über Blocks hinweg, was dabei verloren geht.
Innerhalb eines Blocks entscheiden ein String-Ähnlichkeitswert und ein Schwellenwert über Übereinstimmungen. Beginne streng, bei etwa 0,9, und lockere erst, nachdem du geprüft hast, was die lockerere Einstellung zusammenführen würde.
Schritt 4: Sorgfältig clustern
Übereinstimmungen sind paarweise; Entitäten sind Gruppen. Eine Union-Find-Struktur wandelt Paare effizient in Cluster um. Sie birgt aber auch ein Risiko: Transitivität. Wenn A mit B übereinstimmt und B mit C, landen A und C zusammen, selbst wenn sie nichts gemeinsam haben. Lange Ketten schwacher Übereinstimmungen sind der Grund, warum zwei verschiedene Unternehmen zusammengeführt werden. Achte auf ungewöhnlich große Cluster und prüfe sie, bevor du sie akzeptierst.
Die gesamte Pipeline passt in ein kleines Modul:
import re
import unicodedata
from collections import defaultdict
from difflib import SequenceMatcher
from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode
LEGAL_SUFFIXES = {"ltd", "limited", "inc", "incorporated", "llc", "gmbh", "ag", "sa", "sas",
"srl", "bv", "nv", "plc", "co", "corp", "corporation", "company", "oy", "ab"}
TRACKING = re.compile(r"^(utm_|gclid$|fbclid$|mc_|ref$|ref_)")
def gtin_valid(code):
"""GS1 check digit: weights 3,1,3,... from the digit next to the check digit."""
digits = re.sub(r"\D", "", str(code or ""))
if len(digits) not in (8, 12, 13, 14):
return False
body, check = digits[:-1], int(digits[-1])
total = sum(int(d) * (3 if i % 2 == 0 else 1) for i, d in enumerate(reversed(body)))
return (10 - total % 10) % 10 == check
def norm_name(name):
text = unicodedata.normalize("NFKD", name or "").encode("ascii", "ignore").decode().lower()
tokens = [t for t in re.findall(r"[a-z0-9]+", text) if t not in LEGAL_SUFFIXES]
return " ".join(tokens)
def norm_url(url):
parts = urlsplit((url or "").strip())
query = urlencode(sorted((k, v) for k, v in parse_qsl(parts.query) if not TRACKING.match(k.lower())))
host = parts.netloc.lower().removeprefix("www.")
return urlunsplit(("https", host, parts.path.rstrip("/") or "/", query, ""))
def similar(a, b):
return SequenceMatcher(None, a, b).ratio()
def cluster(records, threshold=0.9):
"""Group records that refer to the same entity. Returns lists of record indexes."""
parent = list(range(len(records)))
def find(i):
while parent[i] != i:
parent[i] = parent[parent[i]]
i = parent[i]
return i
def union(i, j):
parent[find(i)] = find(j)
# 1. Exact matches on strong identifiers.
by_key = defaultdict(list)
for i, r in enumerate(records):
if gtin_valid(r.get("gtin")):
by_key["gtin:" + re.sub(r"\D", "", r["gtin"]).zfill(14)].append(i)
if r.get("url"):
by_key["url:" + norm_url(r["url"])].append(i)
for ids in by_key.values():
for j in ids[1:]:
union(ids[0], j)
# 2. Fuzzy name match, only within a cheap blocking key.
blocks = defaultdict(list)
for i, r in enumerate(records):
name = norm_name(r.get("name"))
if name:
blocks[(r.get("country") or "", name.split()[0])].append((i, name))
for members in blocks.values():
for a in range(len(members)):
for b in range(a + 1, len(members)):
if similar(members[a][1], members[b][1]) >= threshold:
union(members[a][0], members[b][0])
groups = defaultdict(list)
for i in range(len(records)):
groups[find(i)].append(i)
return list(groups.values())An einem kleinen Testdatensatz führt es “Acme Widgets Ltd”, “ACME WIDGETS LIMITED” und einen dritten Datensatz, der die kanonische URL des Unternehmens teilt, zusammen, führt zwei Schuh-Einträge zusammen, deren Barcodes sich nur durch eine führende Null unterscheiden, und lässt “Acme Widget Co” in den Vereinigten Staaten bewusst als separate Entität stehen, weil der Blocking-Schlüssel das Land enthält. Ob diese letzte Entscheidung richtig ist, hängt von deinen Daten ab, was genau der Punkt des nächsten Schritts ist.
Schritt 5: Entscheiden, welcher Datensatz erhalten bleibt
Ein Cluster ist mehrere Versionen einer Entität, und man braucht genau eine. Übliche Survivorship-Regeln:
- Der vollständigste gewinnt, Feld für Feld: für jedes Feld den nicht leeren Wert aus der besten Quelle nehmen, statt einen ganzen Datensatz.
- Der aktuellste gewinnt bei Werten, die sich ändern, etwa Preis und Verfügbarkeit.
- Die vertrauenswürdigste Quelle gewinnt bei Werten wie offiziellen Namen und Adressen, zum Beispiel ein Register gegenüber einem Verzeichnis.
Was auch immer du wählst, behalte jeden Quellen-Identifikator und jede URL im zusammengeführten Datensatz, zusammen mit dem Zeitpunkt, zu dem jeder beobachtet wurde. Stellt sich ein Merge als falsch heraus, ist Herkunft das, was es erlaubt, ihn wieder aufzuteilen.
Präzision und Recall messen
Entity Resolution hat zwei Fehlertypen, und welcher davon wichtiger ist, hängt von der Aufgabe ab.
| Fehler | Was passiert | Am schlimmsten für |
|---|---|---|
| Falscher Merge | Zwei reale Entitäten werden eine | Firmen- und personennahe Daten, Compliance, alles Rechtliche |
| Übersehenes Duplikat | Eine Entität bleibt als mehrere Datensätze bestehen | Zählungen, Marktgrößenbestimmung, Preisvergleich |
Beschrifte per Hand ein paar Hundert Kandidatenpaare, miss beide Raten und stimme Schwellenwerte und Blocking-Schlüssel auf den Fehler ab, der dir wichtig ist. Eine B2B-Lead-Datenbank, wie die in Aufbau einer B2B-Lead-Datenbank, verträgt ein übersehenes Duplikat in der Regel weit besser als zwei fälschlich verschmolzene Unternehmen. Ein Preisvergleich-Feed, wie ein Echtzeit-Wettbewerbspreisfeed, ist umgekehrt: Ein übersehenes Duplikat bedeutet, dass ein Produkt zweimal mit zwei Preisen erscheint.
Früh und an der Quelle deduplizieren
Duplikate kosten Geld, bevor sie Genauigkeit kosten. Jeder wiederholte Abruf derselben kanonischen URL ist Bandbreite oder Guthaben, das umsonst ausgegeben wird, weshalb die Kanonisierung von URLs in die Crawling-Warteschlange gehört, nicht nur ins Data Warehouse. Die Auswirkung auf die Stückkosten wird in Kosten pro bereinigtem Datensatz behandelt.
Fazit
Deduplizierung ist größtenteils Normalisierung. Kanonische URLs, validierte Produktcodes und bereinigte Firmennamen fangen den Großteil der Duplikate ab, bevor überhaupt ein Fuzzy-Matching läuft. Danach auf starke Schlüssel abgleichen, nur innerhalb von Blocks fuzzy matchen, mit einem Auge auf lange Ketten clustern, Herkunft bei jedem zusammengeführten Datensatz bewahren und die Fehler messen, die für deinen Anwendungsfall wichtig sind.
Gut gemacht wird aus einem realen Ding ein Datensatz, mit seiner vollständigen Historie daran. Schlecht gemacht wirkt der Datensatz gleichzeitig größer und weniger vertrauenswürdig.
Quellen und Referenzen
- GS1 US, How to calculate a check digit manually.
- GLEIF, Open LEI data.