Fuzzy Search Teil 1 – Doppelte Datensätze suchen, finden und nicht finden (wollen)

Doppelte Datensätze treten nicht nur beim Zusammenführen mehrerer Quellsysteme auf, häufig bestehen doppelte Datensätze bereits in einem einzigen Quellsystem. Ziel von Datenqualitätsmaßnahmen ist es, diese doppelte Datensätze zu finden und zusammenzuführen, so dass ein einziger sogenannter “golden record” entsteht, oder ggf. auch die Dubletten zu löschen. Dieser Verarbeitungsschritt erfordert vor der Suche nach doppelten Datensätze eine genaue Definition darüber, was ein “doppelter Datensatz” überhaupt ist. Fehlerhaft zugeordnete Daten haben in den meisten Fällen eine wesentlich negativere Auswirkungen, als doppelt vorhandene Daten. Dieser Artikel soll ein paar Anregungen zur Definition von Duplikaten geben.

Grundlagen

Bevor es an die eigentliche Definition der Duplikate geht, müssen die möglichen Ergebnisse einer Duplikatssuche näher betrachtet werden. Im Allgemeinen wird festgelegt, dass der Ähnlichkeitswert eines Vergleiches true ist, wenn die zu vergleichenden Daten übereinstimmen und false wenn sie es nicht tun. Sind die gefundenen Datensätze echte Duplikate, spricht man von positiv, andernfalls von negativ. Daraus ergibt sich eine Klassifizierung eines Ergebnisses in vier mögliche Kategorien.

Zur Bewertung der Ergebnisse werden häufig die beiden Kennwerte Recall und Precision verwendet, einfach ausgedrückt die Menge an Treffern und die Genauigkeit der Treffer.

Aus diesen Grundlagen leitet sich auch die erste Überlegung für die Definition der Duplikatssuche ab: Ist das Ziel ein möglichst hoher Recall oder eine möglichst hohe Precision. Je nach Anwendungsfall sollte die Gewichtung der Kennwerte unterschiedlich gesetzt werden.

Bei einer Duplikatssuche gegen die Robinsonliste des DDV ist wahrscheinlich ein hoher Recall gewünscht, bei einer Duplikatssuche in einem eigenen internen Datenbestand eher eine hohe Precision.

Wichtig: Die Ergebnisgruppe False Negative – Datensätze die laut Definition Duplikate sind, aber nicht als solche gefunden wurden – sind sehr schwer zu analysieren, besonders bei sehr großen Datenbeständen, ist es kaum bis gar nicht möglich, da diese Datensätze nicht entsprechend gekennzeichnet sind.

Das Duplikat

In einem ersten Schritt lässt man sich vielleicht auf folgende recht einfach Definition festlegen:

“Stimmen alle für den Vergleich relevanten Daten zu 100% überein, so wurde ein Duplikat gefunden.”

Dies beschreibt den typischen 1:1 zu Vergleich von Daten. Die wichtige Frage an dieser Stelle ist jedoch: Was sind relevanten Daten?

Um ein Duplikat zu definieren, muss sehr genau festgelegt werden, welche Daten für die Prüfung herangezogen werden. Sind folgende Datensätze Duplikate?

Max Mustermann, Mustergasse 1

Oder werden diese Datensätze erst zu Duplikaten wenn der Ort mit einbezogen wird? Müssen ggf. auch noch andere Kriterien wie z.B. ein Titel, ein Namenszusatz oder ein Adresszusatz mit einbezogen werden? Was ist wenn der Datensatz wie folgt aussieht:

M. Mustermann jun., Mustergasse 1b, 12345 Musterstadt

Max Mustermann, Mustergasse 1, 12345 Musterstadt

Eine allgemeine Definition kann hier nicht festgelegt werden. Hier zu definieren was ein Duplikat ist und was nicht, sind Business Regeln, die in jedem Unternehmen definiert werden müssen. Es gibt Prozesse in denen die Suche nach doppelten Datensätzen auf Gebäudeebene oder auf auf Haushaltseben stattfindet, andere wiederum versuchen die Duplikate auf Personenebene zu definieren. Bei diesen Definitionen ändert sich natürlich auch das Verhältnis von Precision zu Recall.

Weiterführende Informationen/Überlegungen

Je nach verwendetem Algorithmus müssen die Suchparameter für unterschiedliche Länder/Sprachräume ggf. stark angepasst werden. Aber auch die Definition der relevanten Daten/Felder kann sich je nach Herkunftsland der Daten – insbesondere bei Adressdaten – ändern. Eine deutsche Adresse besteht normalerweise aus den Daten Empfänger, Strasse, Hausnummer, Postleitzahl und Ort, bei Adressen aus Österreich werden sehr häufig noch Hausnummernergänzungen (Stiegennummer) mit angegeben, in den UK kann zusätzlich noch das Gebäude Bestandteil einer Adresse sein. Weitere allgemeine Informationen zu Adressformaten sind bei AddressDoctor zu finden.

In einigen Fällen kann es auch sinnvoll sein, die Einstellungen für die Duplikatsprüfung je nach Quellsystem anzupassen. Durch den Einsatz verschiedener Systeme oder auch durch die Datenerfassung durch verschiedene Unternehmen (Call Center), kann die Qualität der Daten variieren, was sich auf die Kennzahlen Precision und Recall auswirkt.

Für die Duplikatssuche werden in den meisten Produkten Schwellenwerte, Kennzahlen zur Messung der Übereinstimmung eines Vergleichs – für die Definition von Duplikaten verwendet. In der Microsoft SSIS Fuzzy Grouping Transformation ist dies der Wert Minimum Similarity. Schwellenwerte können dabei pro Spalte wie auch durch einen Gesamtschwellenwert definiert werden.

Durch die Definition verschiedener Schwellenwerte für die einzelnen zu prüfenden Spalten, ist es möglich unterschiedliche Arten von Duplikaten zu erkennen, z.B. gekürzte Vornamen, verschiedene Schreibweisen bei Straßennamen usw. Der Einsatz verschiedener Kombinationen von Schwellenwerten kann die Precision erhöht und der Recall verringert werden. Da die Fuzzy Grouping Transformation keine Verwendung mehrerer Schwellenwerte unterstützt, verwendet Microsoft in den Beispielen häufig nur den kumulierten Schwellenwert über alle Spaltenwerte, wodurch keine genaue Differenzierung der Dubletten ermöglicht wird.

Bei Fragen zu den einzelnen Punkten freue ich mich über Kommentare. Im zweiten Teil dieses Blogeintrages werde ich unsere Komponente zur Dublettensuche datenfabrik.dedupe näher vorstellen.