Entity Resolution: Gedanken zur häufigsten Herausforderung der Data Science
Kurzfassung
- Eine typische Entity-Resolution-Implementierung nimmt Datensätze auf, standardisiert die relevanten Felder, bildet Kandidatenpaare per Blocking, bewertet Übereinstimmungen, setzt Entitäten zusammen, bewahrt die Verknüpfungsbelege und stellt Anwendungen den aufgelösten Kontext bereit.
- Die schwierigsten Skalierungsprobleme entstehen durch die Explosion der Paaranzahl, schwaches Blocking, wiederholte Batch-Durchläufe, fehlende transitive Verknüpfungen und die Annahme, eine Entitäts-ID sei Beleg genug.
- Tilores setzt darauf, Datensätze bereits bei der Ingestion aufzulösen und zusammenzusetzen, damit Anwendungen zur Abfragezeit den aktuellen aufgelösten Kontext abrufen können, ohne den gesamten Matching-Prozess erneut zu starten.
Inhaltsverzeichnis
- Checkliste für die Implementierung
- Kurze Antwort
- Warum entscheidet Blocking darüber, ob Entity Resolution skaliert?
- Wie sollten Teams über transitive Verknüpfungen nachdenken?
- Warum ist das Speichern von Verknüpfungsbelegen etwas anderes als das Speichern einer Entitäts-ID?
- Was ändert sich, wenn Aktualisierungen aktuell sein müssen?
- Häufig gestellte Fragen
Checkliste für die Implementierung
| Phase | Was passiert | Typischer Fehler, den es zu vermeiden gilt |
|---|---|---|
| Ingestion und Standardisierung | Quelldatensätze in den Workflow überführen, Quell-IDs bewahren, Felder normalisieren und die Ursprungswerte für die Prüfung verfügbar halten. | Die Herkunft verlieren oder unsaubere Quellwerte überschreiben, bevor das Team eine Übereinstimmung erklären kann. |
| Kandidaten blocken oder filtern | Den Vergleichsraum verkleinern, indem plausibel zusammengehörige Datensätze gruppiert werden, bevor einzelne Paare bewertet werden. | Blöcke so breit wählen, dass das ursprüngliche Paarproblem wiederentsteht, oder so eng, dass echte Übereinstimmungen verloren gehen. |
| Übereinstimmungen bewerten und entscheiden | Kandidatendatensätze mit Regeln, Ähnlichkeitsfunktionen, Machine Learning oder einer kontrollierten Kombination dieser Verfahren vergleichen. | Einen Modellwert als endgültig behandeln – ohne Schwellenwerte, Prüfpfade oder ein Verständnis von False Positives und False Negatives. |
| Entitäten und Verknüpfungen zusammensetzen | Akzeptierte Verknüpfungen zu Entitätsgruppen zusammenführen und dabei festhalten, wie Datensätze verbunden sind und wie sicher jede Verknüpfung ist. | Nur eine finale Entitäts-ID behalten und die Verknüpfungsbelege verlieren, die für Audit, Korrektur oder Erklärbarkeit nötig sind. |
| Aufgelösten Kontext bereitstellen | Anwendungen den aufgelösten Entitätskontext abfragen lassen, den sie für Betrugserkennung, KYC, Support, Analytics oder Kundenerlebnis brauchen. | Entitäten zur Abfragezeit von Grund auf neu zusammensetzen oder veraltete Batch-Ergebnisse ohne klare Aktualitätsgarantie ausliefern. |
| Aktualisierungen und Korrekturen überwachen | Neue Datensätze, Korrekturen, Löschungen, Entitätsteilungen und Drift der Match-Qualität behandeln, während sich der Datenbestand verändert. | Für jede Änderung die gesamte Pipeline neu laufen lassen oder falsche Verknüpfungen bestehen lassen, weil keine Korrektur-Workflows vorgesehen waren. |
Uns ist kürzlich ein Beitrag auf Hacker News mit dem Titel „Entity Resolution: The most common data science challenge" aufgefallen, aus dem sich eine interessante Diskussion darüber entwickelte, wie schwierig Entity Resolution im großen Maßstab ist.
Für die Kommentare im Diskussionsstrang kamen wir zu spät, hielten es aber für lohnend, einen Beitrag als Antwort auf den meistbeachteten Kommentar der Diskussion zu schreiben – von Nutzer „smeeth", der sich auf das im Ursprungsbeitrag verlinkte Entity-Resolution-Tutorial bezog:
Gefahr droht allen, die dieses Tutorial betreten und große Datenbestände haben. Das Tutorial ist unterhaltsames Marketingmaterial und schön und gut, aber es ist VIEL zu langsam, um es auf irgendetwas im großen Maßstab anzuwenden. Bitte, Ihrer geistigen Gesundheit zuliebe: Behandeln Sie es als nichts anderes als ein nettes Spielzeugbeispiel. ER will ein O(n^2)-Problem sein, und man muss sehr hart dafür kämpfen, dass es keines wird. Die meisten, die das im großen Maßstab betreiben, folgen im Grunde demselben Drehbuch: 1) Man nutzt einen sehr komplizierten, geschwindigkeitsoptimierten Nicht-ML-Algorithmus, um Gruppen von Entitäten zu finden, die mit hoher Wahrscheinlichkeit dieselben sind – meist auf Basis von String-Ähnlichkeit, Hashing oder extrem komplizierten Heuristiken. Dieser Vorgang heißt Blocking oder Filtern. 2) Man nutzt ausgefeiltes ML, um innerhalb dieser Blöcke die Übereinstimmungen zu bestimmen. Wenn Sie versuchen, 1 und 2 zu kombinieren, 1 zu überspringen oder 1 mit ML auf großen Datenbeständen zu machen, werden Sie garantiert keine Freude haben. Der Unterschied zwischen mittelmäßiger und großartiger ER liegt darin, wie gut Sie beim Blocking beziehungsweise Filtern sind. Zitat von Nutzer smeeth auf Hacker News
Nach unserer Erfahrung fehlt den meisten Lösungen, die diesem Muster folgen, Folgendes:
- 1) Sie bieten keine Möglichkeit, Daten in Echtzeit zu ändern,
- 2) ihnen fehlen transitive Verknüpfungen zwischen Übereinstimmungen, oder
- 3) die Verknüpfungen zwischen den Einträgen werden nicht dauerhaft gespeichert.
(1): Meistens laufen Blocking und Matching innerhalb von Batch-Prozessen. Jeder Eintrag Ihres Datenbestands wird mindestens einem Block zugeordnet. Anschließend wird jeder Eintrag eines Blocks mit allen anderen Einträgen desselben Blocks verglichen. Etwas, das übrigens kein „ausgefeiltes ML" erfordert, sondern sich auch mit „einfachen" Regeln erledigen lässt, die oft besser erklärbar sind.
Am Ende landen Sie dennoch bei O(n^2) innerhalb jedes Blocks. Und nur die Größe der einzelnen Blöcke entscheidet darüber, wie sehr Sie das trifft. Idealerweise enthält jeder Block nur die Einträge, die zusammengehören – aber das kommt nie vor. Kritisch wird es, sobald neue Daten hinzukommen, denn oft lässt man dann einfach denselben Prozess erneut laufen und verschwendet damit wertvolle Rechenleistung und Zeit.
Optimieren lässt sich unter anderem, das Blocking nicht für alles neu auszuführen – nur neue Daten müssen den bestehenden Blöcken hinzugefügt werden. Und dann müssen Sie nicht das gesamte Matching über alle Blöcke hinweg wiederholen, sondern nur über jene, die von den neuen Daten tatsächlich betroffen sind. Die Realität sieht allerdings so aus, dass Menschen (manchmal) bequem sind, (häufig) andere Themen lösen müssen oder dass selbst ein optimierter Prozess (fast immer) zu lange für Echtzeitaktualisierungen braucht. Wir haben oft Lösungen gesehen, die wegen ihrer Echtzeitanforderungen bei einer selbstgebauten, mäßig durchdachten rekursiven Suche landen, die mit jeder weiteren Datenmenge langsamer und langsamer wird.
(2): Wie erwähnt lässt sich jeder Eintrag Ihres Datenbestands mindestens einem Block zuordnen. Leider wird daraus oft kein „mindestens", sondern ein „genau ein". Das führt zu Szenarien, in denen A mit B übereinstimmt und C mit D, dabei aber übersehen wird, dass auch B mit C übereinstimmen könnte, C aber nicht mit A und D nicht mit B. Das würden wir Deduplizierung nennen, nicht saubere Entity Resolution. Doch selbst wenn Sie Einträge mehreren Blöcken zuordnen, stoßen Sie auf das nächste Problem: aus all diesen Verbindungen die tatsächlichen Entitäten zu identifizieren. Das lässt sich etwa mit einem Algorithmus für Zusammenhangskomponenten erledigen, ist aber ebenfalls schwer zu skalieren.
(3): Dieser Punkt hängt stark von der Implementierung ab, aber uns ist oft aufgefallen, dass Werkzeuge für Entity Resolution Ihnen lediglich eine Entitäts-ID für jeden Eintrag liefern. Jeder Eintrag mit derselben Entitäts-ID gehört zur selben Entität – ganz einfach, oder?
Doch damit haben Sie gerade eine Menge wertvoller Informationen verloren: wie alle Einträge innerhalb einer Entität tatsächlich verbunden sind und wie sicher jede Verknüpfung ist. Der Grund dafür sind Duplikate. Nehmen wir an, Sie haben drei Datensätze A1, A2 und A3, die exakt dieselben Informationen enthalten und daher eindeutig übereinstimmen. Wenn Sie nun alle Verknüpfungen zwischen ihnen anlegen, erhalten Sie die Paare A1-A2, A1-A3 und A2-A3, also drei Verknüpfungen. Bei A1..A5 sind es bereits 10. Für A1..An sind es n*(n-1)/2 Verknüpfungen. Bei n=1000 also fast eine halbe Million. Nun könnten Sie einwenden, dass all diese Duplikate keinen Wert liefern – tatsächlich arbeiten wir aber oft nicht mit echten Duplikaten, sondern mit nicht-identischen Duplikaten. Also mit Daten, die in den für das Matching relevanten Attributen exakt gleich sind, sich in anderen Attributen jedoch unterscheiden und daher nicht verworfen werden dürfen. Eine gute Lösung muss damit anders umgehen als eine mittelmäßige.
Die Diskussion zu diesem Beitrag finden Sie hier auf Hacker News.
Kurze Antwort
Eine typische Entity-Resolution-Implementierung beginnt mit Ingestion und Normalisierung und nutzt dann Blocking oder Filtern, um die Zahl der Kandidatenvergleiche zu senken. Kandidatendatensätze werden mit Regeln, Modellen oder beidem verglichen; akzeptierte Verknüpfungen werden zu Entitäten zusammengesetzt; und das System bewahrt genug Belege, um das Ergebnis zu prüfen, zu korrigieren und abzufragen.
Der entscheidende Unterschied im Produktivbetrieb: Entity Resolution ist nicht nur ein einmaliger Deduplizierungslauf. Teams brauchen auch einen Weg, neue Datensätze zu verarbeiten, transitive Verknüpfungen zu bewahren, wiederholte vollständige Durchläufe zu vermeiden und den Systemen, die ihn brauchen, den aktuellen aufgelösten Kontext bereitzustellen.
Warum entscheidet Blocking darüber, ob Entity Resolution skaliert?
Blocking beziehungsweise Filtern ist der Schritt, der verhindert, dass aus einem Matching-Problem ein Vergleich jedes Datensatzes mit jedem anderen wird. Er verkleinert die Kandidatenmenge, bevor die teurere Bewertung stattfindet.
Der Kompromiss lautet Precision gegen Recall auf der Kandidatenstufe. Zu strenge Blöcke verstecken echte Übereinstimmungen; zu lockere Blöcke schieben zu viel Arbeit in den Matcher und können Aktualisierungen verlangsamen.
Wie sollten Teams über transitive Verknüpfungen nachdenken?
Entity Resolution muss oft über Beweisketten schließen, nicht nur über direkte Paarübereinstimmungen. Wenn ein Datensatz mit einem zweiten verknüpft ist und dieser zweite mit einem dritten, braucht das System eine Regel dafür, ob diese Datensätze zur selben Entität gehören.
Diese Regel sollte erklärbar und überprüfbar sein. Andernfalls landet ein Team bei bloßen Deduplizierungsetiketten statt bei einer verlässlichen Entitätssicht, die zeigt, wie Datensätze verbunden sind.
Warum ist das Speichern von Verknüpfungsbelegen etwas anderes als das Speichern einer Entitäts-ID?
Eine finale Entitäts-ID sagt einem nachgelagerten System, welche Datensätze aktuell zusammengehören, erklärt aber nicht den Weg, der zu dieser Gruppierung geführt hat. Erst die Verknüpfungsbelege erlauben es Prüfern, eine Übereinstimmung zu untersuchen, zu korrigieren, aufzutrennen oder zu verteidigen.
Am wichtigsten wird das bei nicht-identischen Duplikaten: Sie teilen sich zwar die relevanten Matching-Felder, tragen aber weiterhin unterschiedliche Attribute, die man nicht einfach verwerfen kann.
Was ändert sich, wenn Aktualisierungen aktuell sein müssen?
Für eine historische Bereinigung kann ein einmaliger Batch-Lauf genügen, doch operative Systeme brauchen einen Plan für neue Datensätze, geänderte Attribute, Löschungen und Korrekturen. Alles bei jeder Änderung neu zu verarbeiten wird schnell teuer und langsam.
Tilores löst das, indem es Datensätze bereits bei der Ingestion auflöst und zusammensetzt. Systeme rufen zur Abfragezeit dann den aufgelösten Kontext ab, den sie für den jeweiligen Workflow brauchen.
Häufig gestellte Fragen
- Wie sieht eine typische Entity-Resolution-Implementierung von Anfang bis Ende aus?
- Sie umfasst in der Regel Ingestion, Standardisierung, Blocking oder Filtern, die Bewertung von Übereinstimmungen, das Zusammensetzen von Entitäten, das dauerhafte Speichern der Verknüpfungen, Prüf- oder Korrektur-Workflows sowie eine API- oder Abfrageschicht, die Anwendungen den aufgelösten Kontext bereitstellt.
- Warum ist Blocking in der Entity Resolution wichtig?
- Blocking reduziert die Zahl der Datensatzpaare, die im Detail verglichen werden müssen. Ohne Blocking entstehen bei großen Datenbeständen zu viele Vergleiche, um effizient zu laufen – besonders wenn laufend neue Datensätze eintreffen.
- Erfordert Entity Resolution Machine Learning?
- Nicht zwingend. Manche Workflows nutzen Regeln oder Ähnlichkeitsfunktionen, andere Machine Learning, und viele Produktivsysteme kombinieren beides. Der richtige Entwurf hängt von Datenqualität, Anforderungen an die Erklärbarkeit, dem Maßstab und den Kosten falscher Übereinstimmungen ab.
- Was sind transitive Verknüpfungen in der Entity Resolution?
- Transitive Verknüpfungen entstehen, wenn Datensatz A mit Datensatz B verknüpft ist und Datensatz B mit Datensatz C – selbst wenn A und C nicht direkt übereinstimmen. Ein Produktivsystem braucht eine Möglichkeit, über solche Verbindungen zu schließen, ohne getrennte Entitäten leichtfertig zusammenzuführen.
- Warum sollte ein Entity-Resolution-System die Verknüpfungsbelege bewahren?
- Bewahrte Verknüpfungsbelege helfen Teams zu erklären, warum Datensätze verbunden wurden, unsichere Übereinstimmungen zu prüfen, falsche Verknüpfungen zu korrigieren, mit Duplikaten umzugehen und Audit- oder Compliance-Workflows zu unterstützen. Eine finale Entitäts-ID allein reicht oft nicht.
- Wie geht Tilores mit dem Entitätskontext zur Abfragezeit um?
- Tilores löst Datensätze bereits bei der Ingestion auf und setzt sie zusammen. Zur Abfragezeit rufen Anwendungen den aktuellen aufgelösten Kontext ab, statt die Entität für jede Anfrage neu aufzubauen.
Tilores mit Ihren eigenen Daten testen
Wählen Sie den nächsten Schritt, der zu Ihrem Evaluierungsstand passt.
Sehen Sie, was aufgelöste Entitätsdaten für Ihr Unternehmen — und Ihre KI — leisten.