Duplikaterkennung


aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 Adressen aufgenommen werden, wobei ein und dieselbe Adresse mit Variationen mehrfach aufgenommen werden kann. Mittels Duplikaterkennung sollen nun diese Duplikate herausgefunden und die eigentlichen Adressen 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 ist der zweite Fall, 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 (Apel, 2009, S. 164):

  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. 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

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

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

Siehe auch