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
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
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
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
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
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
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
9
•
•
•
•
Data Cleansing
Duplikaterkennung
Ähnlichkeitsmaße
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, …
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
…
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: TxTbool die true zurückgibt,
wenn Tupel t1 und t2 demselben Objekt o entsprechen
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
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
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
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
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?
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%
19
Als Kurven
Precision /
Recall
t
Precision
Recall
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
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
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
23
Trade-Offs
Precision
Schwellwert
Recall
Effizienz
24
• Data Cleansing
• Duplikaterkennung
• Ähnlichkeitsmaße
– LIKE und SOUNDEX
– Editabstände
– Weitere Maße
• Sorted-Neighborhood Algorithmus
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)
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
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
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
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
30
•
•
•
•
Data Cleansing
Duplikaterkennung
Ähnlichkeitsmaße
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
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)
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
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
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
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
37

Duplikaterkennung

Transcrição

Documentos relacionados

März 11 Kinder

PDF Computersicherheit

Tampa Bay Sun Bowl 2005

Umrüstung Motorola V50 auf Bluetooth SA644 (Limo) - BMW E39

24h Bestelltelefon: 040-734 193 60 E

Unser Angebot für Sie... - Schloss Apotheke Ettlingen

Methoden der Dublettenerkennung - Hasso-Plattner

7 Normandie, Juli 1944 In der Ferne war das Brummen schwerer

Wochenblatt Verlag: Ulf Kowitz ist neuer lokaler Anzeigenleiter

deutsch

„Unglaubliche Geschichte(n) Thüringens“: Kabarettist

Januar 2015 - SV Funkstreife

Verteilung, Autonomie, Heterogenität und Transparenz

Verteilung, Autonomie, Heterogenität und Transparenz

f2 bloom