KundenNr Name Adresse
3346 Just Vorfan Hafenstraße 12
3346 Justin Forfun Hafenstr. 12
5252 Lilo Pause Kuhweg 42
5268 Lisa Pause Kuhweg 42
Ann Joy Domplatz 2a
Anne Scheu Domplatz 28
Abbildung 4.4: Potenzielle Duplikate
4.1.2 Duplikaterkennung
Eine großer Aufwand der Datenbereinigung liegt darin, semantisch äquivalen-
te Datensätze zu identifizieren, also Datensätze, die das gleiche Realweltob-
jekt darstellen. Dieser Prozess wird in der Literatur auch als Record Linkage,
Objektidentifikation, Duplikateliminierung oder Merge/Purge bezeichnet. Der
Ablauf ist hierbei zweigeteilt. Einerseits müssen Duplikate erkannt werden,
andererseits muss eine Auswahl oder eine Zusammenführung der „besten“ Ver-
treter einer Klasse erfolgen. Abbildung 4.4 gibt ein Beispiel dreier potenzieller
Duplikate. Hierbei wird ersichtlich, dass die Auswahl oder Zusammenführung
nur mittels semi-automatischer Verfahren Erfolg versprechend ist.
Um den Entscheidungsprozess zu unterstützen, können Vergleichsregeln
genutzt werden, um Duplikate zu identifizieren. Jedoch ist es häufig notwen-
dig, dass ein Vergleich potenzieller ähnlicher Datensätze erfolgt, bei der abso-
lute Gleichheit nicht immer vorliegt. So müssen dann in einem naiven Ansatz
alle Datensätze gegen alle anderen auf Ähnlichkeit untersucht werden. Dies
bedeutet einen Aufwand von O(n
2
). Im Data Warehouse ist aufgrund der Da-
tenmenge dieser Ansatz jedoch nicht zielführend. Er erreicht eine maximale
Genauigkeit mit den eingesetzten Vergleichsfunktionen, aber gleichzeitig sind
viele Vergleiche unnötig. Somit erfordert dieser Ansatz einen sehr hohen Be-
rechnungsaufwand. Um den Suchraum geeignet einzuschränken, werden Par-
titionierungsverfahren eingesetzt. Hierzu zählen:
Blocking
Sortierte Nachbarschaft
Multi-Pass-Techniken
Pruning/Filterung
Wir werden diese Verfahren im Folgenden kurz skizzieren.
Abbildung 4.5 verdeutlicht den Prozess der Duplikaterkennung. Die Rela-
tionen R und S beinhalten Objekte, die durch die Eigenschaften r
1
, r
2
, . . . und
s
1
, s
2
, . . . beschrieben sind. Der Suchraum R × S muss partitioniert werden,
88 4 Extraktions-, Transformations- und Ladeprozess
R
r
1
, r
2
, r
3
, ...
S
s
1
, s
2
, s
3
, ...
R x S
r
1
,s
1
r
2
,s
2
r
3
,s
3
...
Matches (M)
Non Matches
(U)
Vergleichs-
funktion
Partitionierung
des
Suchraums
Abbildung 4.5: Duplikaterkennung: Prinzip
um den Vergleichsaufwand zu optimieren. Im Anschluss entscheidet eine Ver-
gleichsfunktion, ob es sich bei zwei Elementen um ein Match M handelt oder
nicht.
Blocking
Bei dieser Technik werden die Daten in einzelne Blöcke aufgeteilt. Jeder Block
stellt dabei einen disjunkten Suchbereich dar. Somit können nur Duplikate ent-
deckt werden, die sich im gleichen Block befinden.
Sortierte Nachbarschaft
Mit dem Vorschlag von Hernandez und Stolfo [HS98] wird der Vergleich von
Datensätzen hinsichtlich eines Sortierungskriteriums und innerhalb eines sor-
tierten Bereichs durchgeführt. Hierzu ist es notwendig, einen geeigneten Sor-
tierungsschlüssel zu identifizieren. So kann es sinnvoll sein, typische Fehler
durch sprachliche Kommunikation — beispielsweise im amerikanischen Raum
den Soundex oder im deutschen Raum die Kölner Phonetik in der Schlüs-
selwahl zu berücksichtigen. Aber auch benachbarte Tasten auf der Tastatur
können bei der Schlüsselbildung eine Rolle spielen. Der Schlüssel ist somit ab-
hängig von der jeweiligen Datenentstehungsdomäne. Nach der Sortierung er-
folgt der Vergleich innerhalb eines definierten Fensters. Das Verfahren erfolgt
somit in vier Schritten:
1. Berechne pro Datensatz einen Schlüssel.
Beispielsweise: die ersten drei Buchstaben einer Zeichenkette oder Soun-
dex, siehe Abschnitt 4.1.3.
2. Sortiere die Datensätze anhand des Schlüssels.
4.1 Qualitätsaspekte 89

Get Data Warehouse Technologien now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.