Duplikaterkennung

Unter Duplikaterkennung oder Objektidentifizierung (auch englisch Record Linkage) versteht man verschiedene automatische Verfahren, mit denen sich in Datensätzen Fälle identifizieren lassen, die dasselbe Objekt in der realen Welt repräsentieren. Dies ist beispielsweise beim Zusammenführen mehrerer Datenquellen (Deduplikation) oder bei der Datenbereinigung notwendig.

Duplikate können beispielsweise durch Eingabe- und Übertragungsfehler, wegen verschiedener Schreibweisen und Abkürzungen oder aufgrund unterschiedlicher Datenschemata entstehen. Beispielsweise können in eine Adressdatenbank aus unterschiedlichen Quellen Anschriften aufgenommen werden, wobei ein und dieselbe Adresse einer Person mit Variationen mehrfach aufgenommen werden kann. Mittels Duplikaterkennung sollen nun diese Duplikate herausgefunden und die eigentlichen Adressaten als Objekte identifiziert werden.

Es sind zwei Arten von Duplikaten zu unterscheiden: identische Duplikate, bei denen alle Werte identisch sind, und nichtidentische Duplikate, bei denen sich ein bis mehrere Werte unterscheiden. Die Erkennung und Bereinigung ist im ersten Fall trivial, die überzähligen Duplikate können ohne Informationsverlust einfach gelöscht werden. Schwieriger und komplexer kann der zweite Fall sein, da die Duplikate nicht über einen einfachen Ist-Gleich-Vergleich wie im ersten Fall identifiziert werden können. Aus diesem Grund müssen Heuristiken angewandt werden. Im zweiten Fall können die überzähligen Datensätze nicht einfach gelöscht werden, sie müssen vorher konsolidiert und die Werte zusammengefasst werden.

Der Prozess zur Erkennung und Konsolidierung von Duplikaten

Der Prozess zur Erkennung und Konsolidierung von Duplikaten kann in folgenden vier Schritten erfolgen:

1. Vorverarbeitung der Daten
2. Partitionierung der Daten
3. Erkennung von Duplikaten und
4. Konsolidierung zu einem Datensatz.

Zur Erkennung von Duplikaten werden verschiedene Ähnlichkeitsmaße angewandt, beispielsweise die Levenshtein-Distanz oder die Schreibmaschinendistanz. Die Tupel werden meist in drei Klassen kategorisiert: Den Duplikaten, den Nicht-Duplikaten und den potentiellen Duplikaten; Also Duplikate, dessen Klassifikation nicht eindeutig ist und deswegen nochmals manuell eingestuft werden müssen.

Man unterscheidet bei der Duplikaterkennung zwischen zwei generellen Ansätzen:

1. Regelbasierter Ansatz: Hier werden Tupel ab einer bestimmten Ähnlichkeit, als Duplikat klassifiziert. Dafür werden basierend auf den paarweisen Ähnlichkeiten Regeln definiert, die darauf schließen lassen, ob ein Tupel ein Duplikat ist oder nicht. Die Regeln basieren meist auf Domänenwissen.
2. Maschinelles Lernen: Notwendig sind hierfür meist schon vorher klassifizierte Tupel als Trainingsdaten. Diese Daten werden dann genutzt, um Regeln maschinell zu lernen und deren Genauigkeit zu testen. Im Gegensatz zum regelbasierten Ansatz ist hier kein Domänenwissen (außer zum Klassifizieren der Trainingsdaten) notwendig.

Da in der Regel aus Kostengründen nicht jeder Datensatz mit jedem anderen verglichen werden kann, gibt es Verfahren wie die sortierte Nachbarschaft (englisch Sorted Neighborhood), bei der nur potenziell ähnliche Datensätze daraufhin überprüft werden, ob sie Duplikate sind.

Es gibt phonetische Algorithmen, die Wörtern nach ihrem Sprachklang eine Zeichenfolge zuordnen, den phonetischen Code, um eine Ähnlichkeitssuche zu implementieren, zum Beispiel Soundex und Kölner Phonetik.

Beispiele

Bei den folgenden Einträgen aus einer Liste von Namen kann es sich möglicherweise um Duplikate handeln:

Max Müller

Max Mueller

M. Müller

Max Muller

Offensichtliche Duplikate sind dagegen „Straße“ und „Strasse“.

Bei einer Bibliothek können Dubletten auftreten, wenn mehrere Bibliothekskataloge zusammengeführt werden.

Siehe auch

• Mustererkennung
• Datenlinkage

Literatur

• Detlef Apel, Wolfgang Behme, Rüdiger Eberlein, Christian Merighi: Datenqualität erfolgreich steuern – Praxislösungen für BI-Projekte. 2009, Hanser Fachbuch, ISBN 978-3-446-42056-4.
• Felix Naumann (Hasso-Plattner-Institut, HPI), Melanie Herschel (Universität Tübingen): An Introduction to Duplicate Detection – Synthesis Lectures on Data Management. 2010, Morgan & Claypool Publishers. doi:10.2200/S00262ED1V01Y201003DTM003.
• Felix Naumann (HPI): Data Profiling and Data Cleansing – Similarity measures (PDF). Vortragsunterlagen vom 11. Juni 2013.
• Jürgen Nemitz: Datenvernetzung in einem historischen Forschungsprojekt, in: EDV-Tage Theuern, Theuern 2000
• Peter Christen: Data Matching – Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection. 2012, Springer, ISBN 978-3-642-31163-5