Duplikaterkennung
Transcrição
Duplikaterkennung
Informationsintegration Duplikaterkennung Ulf Leser Sebastian Wandelt Inhalt dieser Vorlesung • • • • Data Cleansing Duplikaterkennung Ähnlichkeitsmaße Sorted-Neighborhood Algorithmus Ulf Leser: Informationsintegration 2 Anfragebearbeitung in Mediator-basierten Syst. Globales Schema Korrespondenzen Lokale Exportschemata • Aufgabe der Anfragebearbeitung – Gegeben eine Anfrage q gegen das globale Schema – Gegeben eine Menge von Korrespondenzen zwischen globalem und lokalen Schemata – Finde alle Antworten auf q Ulf Leser: Informationsintegration 3 Ergebnisintegration • • • • • Schritt Schritt Schritt Schritt Schritt Ergebnisintegration 1: 2: 3: 4: 5: Anfrageplanung Anfrageübersetzung Anfrageoptimierung Anfrageausführung Ergebnisintegration Eingabe: Pro Ausführungsplan eine Menge von Ergebnistupeln Aufgabe: Die Ergebnisse der einzelnen Ausführungspläne sind oftmals redundant oder uneinheitlich. Während der Ergebnisintegration werden die einzelnen Ergebnisse zu einem Gesamtergebnis integriert, was insbesondere Duplikaterkennung und Auflösen von Widersprüchen in den Daten erfordert. Ergebnis: Das Ergebnis der Benutzeranfrage Ulf Leser: Informationsintegration 4 Datenreinigung • Jeder Plan erzeugt Ergebnistupel • Ziel: Einheitliche, nicht redundante Darstellung der integrierten Informationen • Probleme: Duplikate, fehlende Werte, Widersprüche etc. • Allgemein: Geringe Qualität der Daten • Abhilfe: Data Cleansing – Duplikaterkennung – Datenfusion Ulf Leser: Informationsintegration 5 Data Cleansing in integrierten Systemen • Föderierte Systeme – – – – Online (während Anfragebearbeitung) Passiert im Mediator Erhält Ergebnisse aller Pläne und bereitet diese auf Zugriff meist nur auf die aktuellen Anfrageergebnisse • Data Warehouses – – – – Offline (eventuell schon bei den Quellen) Passiert während des ETL-Prozesses Erzeugt persistente und qualitativ hochwertige Daten Zugriff auf gesamten Datenbestand möglich Ulf Leser: Informationsintegration 6 Beispiel bei virtueller Integration Web Service A Web Service B <pub> <Title> MAC: Merging Autonomous Content </Titel> <First> Felix </First> <Last> Naumann </Last> <Year> 2002 </Year> </pub> <pub> <Title> Merging Autonomus Content </Titel> <First> Dr. Felix</First> <Last> Naumann </Last> <Year> 2001 </Year> </pub> Title First Last Year MAC: Merging Autonomous Content Felix Naumann 2002 Merging Autonomus Content Dr. Felix Naumann 2001 Ulf Leser: Informationsintegration 7 Nachvollziehbarkeit • Data Cleansing verändert Daten • (Neue) Daten müssen erklärbar sein – Anwender eines DWH: „Da fehlt ein Produkt im Report“ – Analysewerkzeug fehlerhaft? Report falsch? Data Mart Definition falsch? Basisdatenbank unvollständig? ETL Prozeduren fehlerhaft? • Data Cleansing Aktionen müssen nachvollziehbar sein – Protokollieren der Aktionen durch alle Prozessschritte – Wiederholbarkeit aller Aktionen bei neuen Daten / Anfragen • DC programmieren, keine manuellen Änderungen Ulf Leser: Informationsintegration 8 Duplikate und Fusion • Viele Fehler findet man erst durch Vergleich – Quelle 1: Hans Meyer, Frankfurter Allee 200 – Quelle 2: Hans Meier, Frankfurter Alee 202 • Man vergleicht Duplikate miteinander • Erfordert Identifikation verschiedener Repräsentationen desselben Objekts • Fusion verschmilzt Duplikate zu einem Objekt Ulf Leser: Informationsintegration 9 Inhalt dieser Vorlesung • • • • Data Cleansing Duplikaterkennung Ähnlichkeitsmaße Sorted-Neighborhood Algorithmus Ulf Leser: Informationsintegration 10 Duplikate • Relationale Welt: Duplikat = Zwei Tupel einer Relation die identische Werte in allen Attributen besitzen • Allgemein: Duplikat = Paar von Tupeln, die demselben Realweltobjekt entsprechen – Also „synonyme“ Objekte • Typische Beispiele: Personen, Rechnungen, Lieferungen, Bestellungen, … • Viele kommerzielle Tools, vor allem im CRM • Duplicate Detection, Record Linkage, Object Identification, Deduplication, Entity Resolution, … Ulf Leser: Informationsintegration 11 Auswirkungen • Überflüssiger Verbrauch von Plattenplatz und Rechenleistung • Einfachste Auswertungen sind falsch – Anzahl Kunden != SELECT COUNT(*) FROM customer – Umsatz != SELECT SUM(revenue) FROM order • Man sieht nur noch Teile und nicht das Ganze – – – – – Überschreiten des Kreditlimits wird nicht erkannt Kein Ausnutzen von Mengenrabatten Fehleinschätzung von Kunden Mehrfachzusendung von Katalogen … Ulf Leser: Informationsintegration 12 Das formale Problem • Gegeben: Tupel T={t1,..,tm} mit Attributen A1,…,Ak – Komplexere Modelle (Bäume, Graphen) später • Tupel entsprechen Objekten O={o1,…,on} • Manche der Tupel sind Duplikate • Gesucht: eine Funktion dup: TxTbool die true zurückgibt, wenn Tupel t1 und t2 demselben Objekt o entsprechen Ulf Leser: Informationsintegration 13 Der gängige Ansatz • Man nimmt an, dass Duplikate ähnlich sind • Ähnlichkeit misst man durch eine geeignete Ähnlichkeitsfunktion sim: TxT [0,1] • Verwend. eines Schwellwerts t: dupsim(t1,t2)=true gdw. sim(t1,t2)>t • Das hat Konsequenzen Ulf Leser: Informationsintegration 14 Transitivität • Im strengen Sinne ist die Duplikateigenschaft transitiv: dup(t1,t2)=true dup(t2,t3)=true dup(t1,t3)=true • Aber: Ähnlichkeit+Schwellwert ist mitnichten transitiv – Meier, Meyer, Mayer, Bayer, Bayes, Bades, … – Meier, Meir, Mer, Er, R, … • Gut überlegen, bevor man Transitivität ausnutzt Ulf Leser: Informationsintegration 15 Äquivalenzrelation und Clustering • Annahme: Transitivität • Dann ist dup eine Äquivalenzrelation – dup partitioniert T in Cluster – Jeder Cluster entspricht einem Realweltobjekt – Jedes Tupel in einem Cluster repräsentiert sein Realweltobjekt • Duplikaterkennung ist im Grunde ein Clusteringproblem Ulf Leser: Informationsintegration 16 Genauigkeit der Duplikaterkennung • Annahme: Verwendung von sim / t • Implizite Annahme: sim(t1,t2) korreliert mit der Wahrscheinlichkeit, dass t1 und t2 Duplikate sind • Dann hängt die Genauigkeit von dupsim von t ab – Hohes t • Nahezu alle Duplikate, die man findet, sind auch welche • Aber man findet viele Duplikate nicht, weil sim nicht groß genug ist – Niedriges t • Man findet praktisch alle Duplikate • Aber man findet auch viele falsche Duplikate Ulf Leser: Informationsintegration 17 Precision und Recall Realität Duplikat Methode Duplikat Kein Duplikat Kein Duplikat true-positive false-positive false-negative true-negative • Precision = TP/(TP+FP) – Wie viele der vorhergesagten Duplikate sind wirklich welche? • Recall = TP/(TP+FN) – Wie viele der echten Duplikate haben wir gefunden? Ulf Leser: Informationsintegration 18 Beispiel • Datenbank mit 10.000 Kunden • Algorithmus findet 50 Duplikate • In Wahrheit – Im Datensatz gibt es 55 Duplikate – Davon hat der Algorithmus 42 gefunden – Die restlichen 8 sind keine Duplikate Real: Positive Alg: Positive TP = 42 Alg: Negative FN = 13 • Precision • Recall Real: Negative FP = 8 = TP/(TP+FP) = 42/50 ~ 84% = TP/(TP+FN) = 42/55 ~ 76% Ulf Leser: Informationsintegration 19 Als Kurven Precision / Recall t Precision Recall Ulf Leser: Informationsintegration 20 Prinzipielles Vorgehen • Annahme: Verwendung einer „guten“ sim • Um alle Duplikate zu finden, muss man alle Paare miteinander vergleichen • Beim Vergleich geht man attributweise vor – Schema Matching muss also schon vorher erfolgt sein • Ähnlichkeit zweier Tupel setzt sich aus der Ähnlichkeit ihrer Attributwerte zusammen, ggf mit Gewichtung der Attribute Ulf Leser: Informationsintegration 21 Probleme • Skalierbarkeit? – Der Vergleich zweier Tupel ist nicht billig – oftmals komplexe Vergleichsfunktionen (siehe gleich) – Bei 100.000 Kunden müsste man 1E10/2 Paare vergleichen – Im Unterschied zu einem Join kann man hier nicht sortieren – Wir müssen weg von der quadratischen Komplexität Ulf Leser: Informationsintegration 22 Weitere Dimension: Effizienz • Statt alle Paare zu vergleichen, nimmt man eine VorPartitionierung der Daten vor • Kleine Partitionen: Weniger Vergleiche, aber auch schlechterer Recall, wenn Duplikate in verschiedenen Partitionen liegen • Große Partitionen: Viele Vergleiche, schlechtere Effizienz, aber besserer Recall Ulf Leser: Informationsintegration 23 Trade-Offs Precision Schwellwert Recall Effizienz Ulf Leser: Informationsintegration 24 Inhalt dieser Vorlesung • Data Cleansing • Duplikaterkennung • Ähnlichkeitsmaße – LIKE und SOUNDEX – Editabstände – Weitere Maße • Sorted-Neighborhood Algorithmus Ulf Leser: Informationsintegration 25 Soundex • Entwickelt 1918 zur Volkszählung in den USA • Gleichklingende Wörter werden in gleiche Strings übersetzt – Soundex-Code: Erster Buchstabe gefolgt von Codes für die nächsten drei Konsonanten – Ähnliche Konsonanten besitzen den gleichen Code (B und P erhalten „1“, D und T erhalten „3“ etc.) – GGf. auffüllen mit „0“ – soundex („Naumann“) = N555; soundex („Neuman“) = N550 • Kritik – Sehr heuristisch (fehlende Konsonanten? Warum nur 3? Warum keine Vokale?) – Nur für (englische) Namen geeignet, Fehlermodell ist „verhören“ (und nicht vertippen) Ulf Leser: Informationsintegration 26 Editabstand • Der Editabstand zweiter Strings S, T ist die minimale Menge von Einfügungen, Löschungen oder Ersetzungen, die notwendig sind, um S in T zu überführen – – – – Offensichtlich symmetrisch Anderer Name: Levenshtein-Abstand Kann in O(|S|*|T|) berechnet werden: Schlecht Sehr populär als domänenunabhängiges Maß • Beispiele – R I MEYER MAY_R R HASEN RASEN Ulf Leser: Informationsintegration R D LEVENST_EIN LIVENSTHEIN R DR R RA_PUNZEL GARFUNKEL 27 Varianten • Normierung auf die Länge der Strings dist (a, b) simedit (a, b) 1 max(| a |, | b |) • Beachtung von Drehern: Damerau-Levensthein Abstand • Besondere Beachtung von Prefixen / Suffixen – Titel, Strassen-Enden, … • Einbeziehung der Ähnlichkeit von Buchstaben – Ersetzungen anders bestrafen je nach Buchstabenpaar – Für Hörfehler: t(y,i)~0, t(b,p)~0.2, t(i,t)~1, t(e,i)~0.3, … – Für Tippfehler: t(X,Y) hängt von der Entfernung von X und Y auf der Tastatur ab Ulf Leser: Informationsintegration 28 Token-basierte Maße: Jackard-Koeffizent • Editabstand nicht geeignet für Texte – Wortstellung in Texten ist sehr variabel – schlechter Editabstand – Beispiel: „Kunde war ungehalten; später Reklamation“ und „Der Reklamation ging ungehaltenes Verhalten vom Kunden voraus“ • Jackard-Koeffizient – Zerlege jeden Text in Menge von Token – Ähnlichkeit zweiter Texte S1, S2 | T1 T2 | simJackard ( S1 , S 2 ) 1 | T1 T2 | – Ignoriert die Reihenfolge der Wörter (Abhilfe: n-Gramme) – Div. Verfeinerungen (Stemming, TF*IDF, …): siehe Info. Retrieval Ulf Leser: Informationsintegration 29 Vom Attribut zum Tupel • Idee: Ähnlichkeit zweier Tupel ist (gewichtetes) Mittel der Ähnlichkeiten ihrer Attributwerte • In der Praxis verwendet man meist Domänenwissen, das man in Regeln kodiert Ulf Leser: Informationsintegration 30 Inhalt dieser Vorlesung • • • • Data Cleansing Duplikaterkennung Ähnlichkeitsmaße Sorted-Neighborhood Algorithmus Ulf Leser: Informationsintegration 31 Die Sorted Neighborhood Methode • Input: Tabelle mit n Tupeln, Ähnlichkeitsmaß • Output: Cluster äquivalenter Tupel • Problem: Es gibt O(n2) viele Tupelpaare – Das dauert zu lange – Außerdem: Nur sehr wenige sind tatsächlich Duplikate • Idee – Partitioniere Tabelle geschickt – Tupelpaare werden nur noch innerhalb einer Partition gebildet Ulf Leser: Informationsintegration 32 Sorted Neighborhood [HS98] • Sorted Neighborhood Algorithmus – Sortiere Tupel so, dass Duplikate (hoffentlich) nahe beieinander sind – Merge-Phase: Fenster der Größe w über sortierte Liste schieben und alle Tupel innerhalb eines Fensters miteinander vergleichen • Überlappende Partitionen – Purge-Phase: Duplikate verschmelzen • Komplexität für n Tupel (Schlüsselerzeugung sei linear) – Sortieren ist O(n*log(n)) – Anzahl Vergleiche ist O(n*w) Ulf Leser: Informationsintegration 33 Schlüsselerzeugung • Schlüsselerzeugung zentral für Effektivität des Verfahrens – Schlechte Reihenfolge: Schlechter Recall • Leider ist überhaupt nicht klar, was ein guter Schlüssel zur Duplikaterkennung ist – Implizite Priorisierung der Attribute durch Schlüsselstruktur – Wichtig: Domänenwissen Vorname Nachname Adresse ID Schlüssel Sal Stolpho 123 First St. 456780 STOSAL123FRST456 Mauricio Hernandez 321 Second Ave 123456 HERMAU321SCND123 Felix Naumann Hauptstr. 11 987654 NAUFEL11HPTSTR987 Sal Stolfo 123 First Street 456789 STOSAL123FRST456 Ulf Leser: Informationsintegration 34 Merge (Fenstergröße 2) Vorname Nachname Adresse ID Schlüssel Mauricio Hernandez 321 Second Ave 123456 HERMAU321SCND123 Felix Naumann Hauptstr. 11 987654 NAUFEL11HPTSTR987 Sal Stolpho 123 First St. 456780 STOSAL123FRST456 Sal Stolfo 123 First Street 456789 STOSAL123FRST456 • Regelbasierte Entscheidung auf Duplikat, z.B. • • IF last_name(r1) = last_name(r2) AND edit_distance(first_name(r1), firstname(r2)) < 5, AND address(r1) = address(r2) THEN dup(r1,r2)=true IF (ID(r1) = ID(r2) OR last_name(r1) = last_name(r2)) AND address(r1) = address(r2) AND city(r1) = city(r2) AND (state(r1) = state(r2) OR zip(r1) = zip(r2)) THEN dup(r1,r2)=true Ulf Leser: Informationsintegration 35 Aufwand • Bei sehr vielen Tupel dominiert der IO Aufwand • Mindestens drei Läufe notwendig – Schlüssel erzeugen und speichern – Sortieren – Fenster schieben • Praktisch sollte sich w also an der Blockgröße und der Größe des Hauptspeichers orientieren – Kleinere Blöcke erzeugen nicht weniger IO • Auch andere teure Operationen – Schlüssel erzeugen – große Schlüssel müssen viele Werte anfassen – Vergleichen – komplexe Regeln erfordern viele Einzelvergleiche Ulf Leser: Informationsintegration 36 Multipass Verfahren • Problematische Schlüsselwahl • Lösung 1: Vergrößerung des Fensters – Effizienz leidet, Effektivität steigt idR nur wenig – Die „Präfix-Verzerrung“ der Sortierung kriegt man nicht weg • Lösung 2: Multipass – – – – Merge-Purge mehrmals mit verschiedenen Schlüsseln laufen lassen Pro Lauf kleine w und einfache Schlüssel verwenden Duplikatbeziehungen aller Läufe sind gleichwertig Weniger effizientes, aber deutliches effektiveres Verfahren als Single-Pass Ulf Leser: Informationsintegration 37