# Datenlinkage

Datenlinkage bezeichnet die Verknüpfung verschiedener Datenquellen. Der Begriff Record Linkage wird oft synonym verwendet, oft aber auch im engeren Sinne zur Bezeichnung der technischen (algorithmischen) Verfahren zur Erkennung, ob zwei Datensätze zum selben Fall gehören, und gegebenenfalls zu deren Zusammenführung in einem einzelnen Datensatz. Datenlinkage ist Teil des Datenmanagements, dient zur Verbesserung der Datenqualität und stellt ein wichtiges Teilgebiet der Data Science dar.

## Szenarien

Datenlinkage ist immer dann relevant, wenn Daten in einer Datenbank korrigiert oder aus einer anderen Datenquelle ergänzt werden sollen. Beispiel: Die Daten eines Krebsregisters werden durch die Daten eines Melderegisters ergänzt, die Informationen zu Todesfällen enthalten. Bei Krebsregistern ist das Datenlinkage ein Routine-Vorgang und durch das Bundeskrebsregisterdatengesetz geregelt.
Typische Szenarien sind:
* Duplikaterkennung und Deduplikation; hier werden in einer Datenbank mehrfach vorhandene Datensätze aufgespürt und das mehrfache Vorkommen bereinigt.
* Zusammenführung zweier, sich teilweise überlappender, Datenbanken, das Record Linkage im eigentlichen Sinn; hier sollen ergänzende Daten in der jeweils anderen Datenbank gefunden werden, z. B. im Sinne eines Follow-up oder einer Datenfusion.
* iterative Dateneingabe; hier sollen einer Datenbank laufend neue Datensätze hinzugefügt oder bereits vorhandene ergänzt werden. Dabei ist zu prüfen, ob ein einzugebender Datensatz früher schon ganz oder teilweise erfasst wurde.
Wenn die Datensätze (oder die zum Vergleich verwendeten Datenfelder) völlig identisch sind, ist die Aufgabe in allen diesen Szenarien trivial. Die eigentlichen Verfahren des Record Linkage betreffen Fälle, in denen die Datensätze möglicherweise fehlerbehaftet oder lückenhaft sind. Für die Zuordenbarkeit zweier Datensätze werden bei den meisten Verfahren Maßzahlen (Scores) für die Ähnlichkeit verwendet und ein oder zwei Schwellenwerte definiert. Wird der obere Schwellenwert erreicht oder überschritten, werden die Datensätze als zusammengehörig angesehen, wird der untere Schwellenwert unterschritten, gelten sie als nicht zusammengehörig; das kann algorithmisch entschieden werden. Im Fall, dass sich oberer und unterer Schwellenwert unterscheiden, verbleibt dazwischen ein Bereich, in dem das algorithmische Verfahren die Entscheidung offen lässt. Dann trifft oft ein menschlicher Bearbeiter die abschließende Entscheidung (Clerical Review), eventuell unter Hinzuziehung weiterer Informationen.
Beispiel: Ein Adress-Datensatz, in dem das Datenfeld „Familienname“ einmal mit dem Wert „Mueller“ und einmal mit dem Wert „Müller“ oder das Feld „Vorname“ einmal mit dem Wert „Karl“ und einmal mit dem Wert „Karl Josef“ besetzt ist. Schon dieses einfache Beispiel weist darauf hin, dass sich das Problem, identische Fälle zu erkennen, algorithmisch nicht immer vollständig lösen lässt: Es könnte sich bei den vermeintlichen Duplikaten ja auch um Familienmitglieder im gleichen Haushalt handeln.
Die Verfahren des Datenlinkage werden meist im Kontext von personenbezogenen oder personenbeziehbaren Daten eingesetzt und müssen dann die Vorgaben des Datenschutzrechts beachten; sie sind aber auch für andere Arten von Daten anwendbar. Bei personenbezogenen Daten steht die Verknüpfbarkeit im Konflikt mit dem Gewährleistungsziel der Nicht-Verkettbarkeit, wie sie etwa im Standard-Datenschutzmodell definiert wird. Die Entwicklung datenschutzfreundlicher Verfahren zum Datenlinkage (Privacy-Preserving Record Linkage, PPRL, siehe unten) zielt auf eine Minimierung dieses Konflikts ab. Zu beachten ist, dass auch pseudonymisierte Daten in der Regel als personenbeziehbar gelten, so dass für das Datenlinkage ein rechtlicher Erlaubnistatbestand vorhanden sein muss, z. B. eine informierte Einwilligung der betroffenen Personen.
Für die Durchführung des Record Linkage existieren einige Software-Werkzeuge.

## Fehler beim Linkage

Bei den Verfahren zum Record Linkage können zwei Arten von Fehlern vorkommen:
* Ein Synonymfehler tritt auf, wenn zwei zusammengehörige Datensätze versehentlich als nicht zusammengehörig deklariert werden, mit der Folge, dass ein Individuum durch zwei verschiedene Datensätze repräsentiert wird.
* Ein Homonymfehler tritt auf, wenn zwei nicht zusammengehörige Datensätze versehentlich als zusammengehörig deklariert werden.
Wird das Linkage algorithmisch durch einen Score unterstützt, so wird durch Erhöhung der Schwellenwerte tendenziell die Rate von Homonymfehlern verringert, die von Synonymfehlern erhöht, und umgekehrt bei Absenkung der Schwellenwerte.
Beispiele für mögliche Fehlerquellen in den einzelnen Datensätzen sind:
* falsche oder unvollständige Eingaben,
* abweichende Schreibweisen, z. B. bei ausländischen Namen,
* Zahlendreher oder Buchstabendreher,
* Namens- oder Adressänderungen.
Um diese Arten von Fehlern von vornherein zu minimieren, werden als Vorbereitung des Linkage oft einzelne Datenfelder standardisiert. Entsprechende Maßnahmen können sein die einheitliche Behandlung von
* diakritischen Zeichen, z. B. Auflösung von Umlauten,
* Doppelnamen, z. B. Auftrennung in zwei Datenfelder,
* Namenszusätzen wie Titel oder Adelsprädikaten,
* Adressangaben,
* Abkürzungen.
Darüber hinaus werden oft auch phonetische Versionen von Namen verwendet. Übliche Verfahren zu deren Bildung sind
* Soundex,
* Kölner Phonetik,
* Hannoversche Phonetik.
Für die Beschreibung der Verfahren des Record Linkage geht man in der Regel davon aus, dass definierte Teile der Datensätze zum Vergleich herangezogen werden. Die Datenfelder dieser Teildatensätze werden als Identifikatoren oder Schlüsselvariablen bezeichnet; darüber hinaus können die Datensätze weitere, auch unterschiedliche Datenfelder enthalten, die oft als Nutzdaten bezeichnet und nicht zum Linkage herangezogen werden.
Beispiel: Bei der Zusammenführung zweier Kunden-Datenbanken von zwei Tochtergesellschaften könnten die Felder „Name“, „Vorname“, „Geburtsdatum“, „Wohnort“ und „Adresse“ zusammen als Identifikatoren verwendet werden, während die Bestell-Historien als Nutzdaten behandelt werden.
Das Record-Linkage-Problem wird durch die Vergabe eindeutiger Identifikatoren vereinfacht, Beispiel: Steuernummer. Das Problem der Datensatz-Zusammenführung ist dann trivial; die Schwierigkeit, die mit der Erkennung einer Übereinstimmung verbunden ist, ist in den Prozess der Zuteilung der Identifikatoren ausgelagert.

## Verfahren des Record Linkage

Für ein exaktes Record Linkage werden fehlerfreie eindeutige Identifikatoren benötigt; schon eine unterschiedliche Schreibweise in einem Datenfeld führt zu einem Synonymfehler. Daher muss ein Record-Linkage-Verfahren bei möglicherweise fehlerbehafteten Daten eine mehr oder weniger ausgeprägte Fehlertoleranz aufweisen. Man spricht dann von stochastischem Record Linkage. Die Verfahren hierfür verwenden z. T. Methoden aus der Stochastik, aber auch aus der Klassifikationstheorie, der Mustererkennung und der künstlichen Intelligenz. Hauptsächliche Verfahrensklassen sind:
* regelbasierte Verfahren; diese überprüfen Minimalanforderungen an die Übereinstimmung zweier Datensätze.
* distanzbasierte Verfahren; diese verwenden String-Metriken wie die Levenshtein-Distanz oder andere Ähnlichkeitsmaße, die die Ähnlichkeiten von Zeichenketten beschreiben; sie können auf den Datensatz als Ganzes oder auf einzelne, insbesondere textuelle, Datenfelder angewendet werden.
* stochastische Verfahren; das klassische stochastische Verfahren geht auf Newcombe, Fellegi/Sunter und Jaro zurück. Hier wird ein Maß für die Ähnlichkeit zweier Datensätze auf der Basis eines Maximum-Likelihood-Ansatzes gebildet.
Als Varianten dieser Verfahren werden verwendet
* Entscheidungsbaum-Methoden, eventuell verfeinert durch Boosting und Bagging,
* Support Vector Machines,
* EM-Verfahren (expectation-maximization),
* künstliche neuronale Netze,
* Diskriminanzanalyse.
Bei vielen dieser Verfahren können lernende Algorithmen eingesetzt werden, wobei das Lernverfahren überwacht oder unüberwacht sein kann.
Da bei der Zusammenführung zweier umfangreicher Datenbestände sehr viele paarweise Vergleiche durchgeführt werden müssten, wird zur Verbesserung der Performance oft ein Blocking-Verfahren eingesetzt, das die Datensätze nach exakter Übereinstimmung in einigen Datenfeldern vorsortiert und dadurch die Anzahl der nötigen Paarvergleiche reduziert.

## Datenschutzfreundliche Verfahren (PPRL)

Das Ziel von PPRL-Verfahren des Datenlinkage ist das Record Linkage von personenbeziehbaren Daten, ohne die wahre Identität der betroffenen Personen aufzudecken. Dabei geht man von kryptographisch verschlüsselten Identifikatoren aus, oder allgemeiner von Pseudonymen, die die Identifikatoren ersetzen. Dies bedeutet für das exakte Datenlinkage keinerlei Einschränkung. Da aber schon minimal unterschiedliche Werte der Identifikatoren bei den gängigen Pseudonymisierungsverfahren zu vollkommen unterschiedlichen Pseudonymen führen, macht eine Pseudonymisierung die fehlertolerante Duplikaterkennung unmöglich. Ansätze zur Auflösung dieses Dilemmas sind:
* Einsatz eines Datentreuhänders, der besonderen rechtlichen und vertraglichen Bindungen unterliegt und den Abgleich mithilfe der Identifikatoren im Klartext vornimmt; dazu verwaltet er eindeutige Pseudonyme für die Fälle und die Zuordnungstabelle oder -regel zwischen Identifikatoren und Pseudonymen.
* Einen Schritt weiter gehen viele Krebsregister, indem aus verschiedenen Kombinationen von identifizierenden Merkmalen sogenannte Kontrollnummern erzeugt werden, von denen sich bei Datenfehlern nur einige ändern und die somit vom Datentreuhänder (hier Vertrauensstelle genannt) für einen ausreichend zuverlässigen Abgleich verwendet werden können.
* Eine weitere Verbesserung dieser Idee besteht in der Verwendung von Bloomfiltern anstelle der Kontrollnummern.
* Noch in der Erprobung befinden sich neuere Ansätze, die Methoden des sicheren verteilten Rechnens (Secure Multiparty Computation) verwenden.