Die Identity Resolution von Kevin Bacon

Six Degrees of Kevin Bacon

Vielleicht haben Sie schon von „Six Degrees of Kevin Bacon“ gehört? Das ist ein Spiel, bei dem man die kürzeste Verbindung zwischen dem amerikanischen Schauspieler Kevin Bacon und einem anderen Schauspieler finden muss – über Filme, in denen einer der beiden mitgespielt hat.

Der britische Schauspieler Simon Pegg zum Beispiel spielte in Mission Impossible gemeinsam mit Tom Cruise; Tom Cruise spielte in Eine Frage der Ehre mit Kevin Bacon. Simon Pegg hat damit eine „Bacon-Zahl“ von 2.

Die Bacon-Zahl jedes Schauspielers können Sie auf der Website The Oracle of Bacon nachschlagen.

Das Spiel beruht auf dem Konzept der „sechs Grade der Trennung“, nach dem sich je zwei Menschen auf diesem Planeten über sechs Bekannte von Bekannten verbinden lassen. Theoretisch haben wir alle also höchstens eine Bacon-Zahl von 6.

Die Six Degrees of Kevin Bacon sind tatsächlich ein ziemlich gutes Beispiel für Netzwerk- oder Graphentheorie (beziehungsweise für einen sozialen Graphen): Jeder Schauspieler ist ein „Knoten“, die Verbindungen zwischen ihnen sind „Kanten“. Es sind genau die Daten, für die eine Graphdatenbank wie Neo4j gemacht ist, in der jeder Schauspieler über einen Pfad aus Knoten und Kanten irgendwie mit jedem anderen verbunden ist.

Kevin Bacon eignet sich außerdem, um den Unterschied zwischen Graphen und Entity Resolution zu erklären. Oder besser gesagt: warum Graphdatenbanken für Entity Resolution nicht gut funktionieren.

Entity Resolution von Kevin Bacon

Entity Resolution ist der Prozess, in dem Datensätze, die sich unterscheiden mögen, aber dieselbe reale Entität betreffen (etwa eine Person oder eine Identität), miteinander verbunden werden – daher ist manchmal auch von „Record Linkage“ die Rede. Diese Datensätze sind weiterhin Knoten, und die Verbindungen zwischen ihnen sind weiterhin Kanten. Bei den Six Degrees of Kevin Bacon verbinden wir jedoch nicht zusammengehörige Entitäten – die verschiedenen Schauspieler –, das ist also keine Entity Resolution.

Trotzdem lässt sich der verehrte Herr Bacon als Beispiel für Entity bzw. Identity Resolution heranziehen.

Was verbindet Ren McCormack, Valentine McKee, Jack Swigert und Sebastian Caine?

Es sind alles Rollen, die Kevin Bacon im Lauf seiner Karriere in Filmen gespielt hat (Footloose (1984), Tremors (1990), Apollo 13 (1995) und Hollow Man (2000)).

Jeder Datensatz ist eindeutig, weil der Figurenname jeweils ein anderer ist. Gleichen wir jedoch über den echten Namen des Schauspielers ab und ergänzen zur Sicherheit vielleicht noch ein Attribut wie sein Geburtsdatum(*1), dann wissen wir jetzt, dass alle diese Figuren zur selben realen Entität gehören – in diesem Fall zu einem Schauspieler(*2).

In Wirklichkeit ist das ein recht einfaches Beispiel, sofern wir annehmen, dass Kevins Name in jedem Datensatz korrekt geschrieben und sein Geburtsdatum korrekt erfasst ist.

Fuzzy Matching von Kevin Bacon

Stellen wir uns dagegen einen Datenbestand vor, in dem die Daten nicht so sauber sind, dann müssten wir sogenannte „unscharfe Abgleichverfahren“ (Fuzzy Matching) einsetzen, um zu erkennen, dass Kevin Bacon und Kev Bakon (vielleicht ein Erfassungsfehler) dieselbe Person sind, obwohl die Datensätze unterschiedlich sind – und dass sie nicht dieselbe Person sind wie Michael Bacon (Kevins Bruder).

Mit dem Fuzzy-Matching-Algorithmus nach Jaro-Winkler sehen wir in diesem Fall, dass Kevin und Kev eine Ähnlichkeit von 90,70 % haben, während Bacon und Bakon auf 89,3 % kommen. Michael und Kevin/Kev passen eindeutig nicht zusammen.

Deduplizierung von Kevin Bacon

Tauchen wir tiefer in Kevin Bacon ein …

Unser erstes Beispiel der Entität Kevin Bacon ist tatsächlich eine zu stark vereinfachte Darstellung. Würden wir über Name und Geburtsdatum abgleichen, sähen Sie, dass in Wahrheit alle Datensätze miteinander verbunden wären. In diesem Fall hätten wir also 6 „Kanten“ statt 3.

Da mehr Kanten mehr Komplexität bedeuten, würden wir diese vier Datensätze in Tilores mit hoher Wahrscheinlichkeit „deduplizieren“, sodass ein Kevin Bacon zum Masterdatensatz wird und die Duplikate nur noch mit diesem Master-Kevin-Bacon verbunden sind. Weitere, nicht identische Kevin Bacons würden ebenfalls nur mit dem Master-Datensatz verknüpft, was die Zahl der Kanten verringert. Alle doppelten Kevin-Bacon-Datensätze und ihre Metadaten bleiben über den Master-Kevin-Bacon verfügbar, aber die Kanten sind nun reduziert – die Entität ist damit einfacher und schneller abrufbar.

Welche von Kevin Bacons Rollen seine „Master“-Rolle ist, überlasse ich Ihnen. Im Fall von Tilores ist der Masterdatensatz üblicherweise der zuerst eingelesene Datensatz. Wird der Masterdatensatz gelöscht, reorganisiert sich die Entität unmittelbar, sodass der als Zweites eingelesene Datensatz zum neuen Master wird – die Datenintegrität der Entität bleibt so erhalten.

Warum also keine Graphdatenbanken für Entity Resolution?

Würden wir für unsere Kevin-Bacon-Übung zur Entity Resolution eine Graphdatenbank verwenden, lägen all unsere Kevin-Bacon-Figurendatensätze zusammen mit sämtlichen Figuren aller anderen Schauspieler darin, und jeder wäre über Kanten mit jedem verbunden. Man könnte zwar alle Kevin-Bacon-Figuren finden, aber die Komplexität der schieren Kantenmenge würde den Abruf der Entität Kevin Bacon unglaublich langsam machen.

In einem Entity-Resolution-System liegen ebenfalls alle Figurendatensätze vor, aber nur die zusammengehörigen Datensätze sind miteinander verknüpft. Das System nutzt weiterhin Graphentheorie (jedenfalls bei Tilores), aber nur auf Ebene der Entität. Dadurch ist das gesamte System deutlich schneller und wesentlich besser für Echtzeit-Anwendungsfälle geeignet, etwa Betrugserkennung, KYC und Kundenbindung im E-Commerce.

Wollen SIE Kevin-Bacon-Daten bereinigen?

Wenn Sie Entity Resolution auf Tausenden oder Millionen von Kevin-Bacon-Datensätzen durchführen müssen, sprechen Sie gern mit uns, ob wir Ihnen mit Tilores helfen können. Wir urteilen nicht. Im Gegenteil – wir applaudieren Ihrem Einsatz für die Bereinigung Kevin-Bacon-bezogener Daten.

Fußnoten

(1) Ein universell anerkanntes Schauspielergesetz hilft uns hier, denn zwei Schauspieler dürfen nicht denselben Namen tragen. Kuriose Randnotiz: Der irische Schauspieler Killian Scott heißt in Wirklichkeit Cillian Murphy und musste seinen Namen ändern, weil der unnatürlich attraktive Schauspieler Cillian Murphy (ebenfalls Ire) diesen Namen in der Schauspielwelt zuerst für sich beanspruchte.

(2) Ich behaupte nicht, dass Schauspieler keine Menschen wären. Sind sie. Und sie haben auch Gefühle. Vor allem Kevin Bacon.