Hasso-Plattner-Institut
Prof. Dr. Felix Naumann
 

Data Matching Benchmark

Das Bachelorprojekt „Data Matching Benchmark“ in Kooperation mit SAP beschäftigt sich mit dem Thema Vergleichbarkeit von Duplikaterkennungslösungen.

Sind in einem Datensatz für ein reales Objekt mehrere Einträge vorhanden, so spricht man von Duplikaten. Auch wenn es zunächst merkwürdig erscheinen mag, begegnen uns solche Duplikate im Alltag sehr häufig. Vor allem in großen Datensätzen kommt es oft vor, dass Objekte mehrfach eingespeichert werden. Solche Duplikate zu erkennen sollte deshalb automatisch erfolgen, weshalb viele Wissenschaftler und Unternehmen hierfür bereits eigene Algorithmen entwickelt haben. Gegenstand dieses Bachelorprojekts ist es, diese verschiedenen Ansätze vergleichbar zu machen und ihre individuellen Stärken und Schwächen aufzuzeigen.

Duplikate

Bei Online-Marktplätzen wie beispielsweise Amazon kommt es häufiger vor, dass ein Produkt, (z.B. ein Smartphone) mehrfach gelistet ist. Dies macht die Navigation für den Kunden komplizierter, weshalb die Anbieter solche Dubletten gerne erkennen und unter einem Eintrag zusammenfassen würden.

Die Variationen sind dabei sehr unterschiedlich: Abweichungen in der Benennung können von Tippfehlern (z.B. Smatphane) bis hin zu verschiedenen Reihenfolgen reichen (z.B. Smartphone X1 64GB vs. 64GB Smartphone X1). Unterschiedliche Geräte sollten hingegen nicht zusammengefasst werden, obwohl der Unterschied im Namen sehr gering sein kann (z.B. Smartphone X1 vs. Smartphone X2).

Auch Kunden eines Onlineshops können selbst zu Dubletten werden. Legt sich ein bestehender Kunde ein neues Konto an, so ist es im Interesse des Anbieters, dieses doppelte Konto ausfindig zu machen. Aber wann sind zwei Kunden identisch? Müssen alle Einträge im Profil gleich sein?

Auch hier sind wieder einige Variationen beispielsweise bei Straßennamen oder auch Tippfehler möglich. Nutzer könnten zwischenzeitlich umgezogen sein – ein Algorithmus zur Duplikaterkennung sollte also durchaus auch Nutzer mit verschiedenen Anschriften vergleichen, sofern z.B. Name und Geburtsdatum identisch sind.

Verschiedene Ansätze

Dieses Problem ist nicht neu – im Gegenteil: es wird bereits seit vielen Jahren an Ansätze zur automatischen Duplikaterkennung gearbeitet. Hier unterscheidet man grundsätzlich zwischen zwei Arten: Solche die konventionelle Algorithmen nutzen und solche, die maschinelles Lernen nutzen.

Bei konventionellen Algorithmen muss für jede Anwendung zunächst eine Reihe von Regeln definiert werden, nach denen Paare von Einträgen als Duplikate markiert werden. Ein möglicher Regelsatz könnte beispielsweise zwei Kunden mit sehr ähnlichen Namen und identischem Geburtsdatum als Duplikat markieren. Alle konventionellen Ansätze eint, dass die Entscheidungsgrundlage des Algorithmus vom Menschen programmiert sein muss und Wissen über den Verwendungszweck enthält.

Ansätze mit maschinellem Lernen hingegen setzen einen kleineren manuell markierten Datensatz zum Trainieren voraus. In diesem sind also bereits alle Duplikate identifiziert und stehen dem Algorithmus zur Verfügung. Mit Hilfe mehrerer Durchläufe versucht der Algorithmus dann aus den markierten Daten sinnvolle Regeln abzuleiten, mit denen er eine hohe Erkennungsrate der tatsächlichen Duplikate erreicht. Anschließend werden auf Basis dieses vom Algorithmus bestimmten Modells im Gesamtdatensatz die Duplikate bestimmt. Oftmals ist es für den Menschen bei solchen Ansätzen nicht möglich nachzuvollziehen, warum sich der Algorithmus genau für diese Regeln entschieden hat. Auch hängt der Erfolg dieser Ansätze sehr stark von der Größe und Qualität des Trainingsdatensatzes ab. In der Praxis werden solche Algorithmen deshalb oft vortrainiert ausgeliefert, so dass weniger Training und damit ein kleinerer Trainingsdatensatz beim Endanwender selbst benötigt wird.

Zusammenfassend ist also für beide Ansätze Vorarbeit nötig. Während konventionelle Algorithmen einen von Hand definierten Regelsatz verwenden, nutzen Ansätze mit maschinellem Lernen kleinere händisch markierte Beispieldatensätze, um automatisiert einen Regelsatz zu erstellen.

Evaluation

Auf dem Markt existieren viele verschiedene Ansätze, die alle mehr oder weniger ähnlich arbeiten. Angenommen, ein Webshop-Anbieter möchte nun wissen, für welchen Ansatz er sich entscheiden soll - ihm liegen Angebote von zwei Anbietern vor. Anbieter A nutzt den konventionellen Ansatz, benötigt also Zeit um den Regelsatz zu definieren. Hingegen kommt der maschinelle Ansatz bei Anbieter B zur Anwendung, so dass hier zeitliche Ressourcen zur händischen Markierung einiger Beispieldaten benötigt werden. Für welchen Ansatz soll er sich nun entscheiden? Gibt es Maße um die Leistung beider Optionen zu messen und vergleichbar zu machen?

Ob ein Algorithmus gut oder schlecht arbeitet kann mit verschiedenen Metriken untersucht werden. Ein Beispiel hierfür ist die Präzisions-Metrik, welche angibt, wie viele der erkannten Duplikate tatsächlich echte Duplikate sind. Auf jeden Fall wird aber ein vollständig markierter Datensatz benötigt, um Fehler des Algorithmus identifizieren zu können. Neben diesen harten Metriken sind aber auch weichere Aspekte für Kunden interessant – nämlich die oben angesprochene benötigte Anpassungszeit und die damit verbundenen Kosten.

Auf Basis dieser verschiedenen Kennzahlen kann der Webshop-Betreiber dann entscheiden, welcher Algorithmus sich für seine Verwendung besser eignet und die höchste Leistung bietet.

Wirtschaftspartner SAP

Als Hersteller von Unternehmenssoftware bietet SAP Lösungen für die Deduplikation von Unternehmensdaten an. Im Laufe der Jahre wurden mehrere Algorithmen mit verschiedenen Ansätzen entwickelt, die jeweils für unterschiedliche Problemstellungen optimiert wurden. Um nun zu entscheiden, welcher dieser Algorithmen sich für welche Verwendungszwecke besser eignet, wird neben einem Beispieldatensatz mit markierten Duplikaten auch ein Auswertungswerkzeug benötigt, welches zahlreiche Informationen bezüglich der Effektivität des Algorithmus liefert. So können Erkenntnisse über Stärken eines Ansatzes und Möglichkeiten zur Verbesserung wieder in die Entwicklung oder das Tuning einfließen und somit Produkte von SAP weiter verbessern oder Ideen für neue Ansätze liefern.

Data Matching Benchmark

Auch in der Wissenschaft ist das Problem der automatischen Duplikaterkennung weitreichend bekannt. In zahlreichen Publikationen wurden bereits verschiedenste Algorithmen entwickelt und an Beispieldatensätzen evaluiert, jedoch mangelt es bisher deutlich an Vergleichbarkeit der Ergebnisse und präzisen Angaben zu Stärken und Schwächen. Hier soll das Projekt zukünftig Abhilfe schaffen und diesen Forschungsbereich voranbringen.

Anders als vorherige Ansätze wird sich dieses Tool auf den Vergleich von Algorithmen für relationale Daten fokussieren. Diese Datensätze sind wie Tabellen aufgebaut, definieren also eine Reihe von Spalten, zu denen jeder Eintrag als Zeile der Tabelle je eine Information liefert. Da Unternehmensdaten häufig in dieser tabellarischen Form vorliegen, können Algorithmen für solche mit diesem neuen Benchmark besonders einfach analysiert werden.

Zu verschiedenen markierten Datensätzen können Wissenschaftler und Entwickler Resultate ihrer Algorithmen in das Programm hochladen. Anschließend können dann Resultate entweder gegen den markierten Datensatz als Musterlösung oder gegen andere Algorithmen verglichen werden. Auch können dabei verschiedene Konfigurationen eines einzigen Algorithmus analysiert werden, um konkrete Verbesserungsansätze abzuleiten. Hierfür berechnet die Software verschiedenste gängige Metriken und erlaubt es, die Abweichungen von der Musterlösung genauer zu untersuchen. Besonders hilfreich sind dabei Hinweise des Tools wie gut Duplikate einer bestimmten Sorte (z.B. Tippfehler) erkannt wurden. Somit können sehr einfach konkrete Stärken und Schwächen der verglichenen Algorithmen untersucht werden.

Die Projektteilnehmer ermöglichen damit dem Wirtschaftspartner SAP und der Wissenschaft verschiedenste Ansätze nachvollziehbar zu vergleichen und damit schneller und einfacher in der Entwicklung von verbesserten Ansätzen voranzukommen. Als Open Source Software steht das Benchmark anschließend allen interessierten Personen zur freien Verfügung und kann sowohl von Forschern als auch Unternehmen weltweit verwendet und stetig weiterentwickelt werden.

Team bei SAP & HPI

Studenten Team

Martin Graf, Florian Papsdorf, Lukas Laskowski, Florian Sold

SAP Partner

Dr. Andreas Doehrn, Roland Gremmelspacher, Gary Bahl, Hartmut Vogler, Michael Veth

Project Lead

Prof. Dr. Felix Naumann