Duplikaterkennung - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 14

2.4 Ähnlichkeitsmessung

In den vorherigen Kapiteln wurde bereits beschrieben, dass bei der Duplikater-
kennung die Ähnlichkeit zweier Tupel mit Hilfe einer Ähnlichkeitsfunktion sim
gemessen wird. Das einfachste Ähnlichkeitsmaß ist die Identität, bei der alle At-
tribute zweier Tupel miteinander verglichen werden. Die Vergleichsfunktion sim
liefert den Wert 1, wenn alle Attribute identisch sind bzw. 0 bei nicht identischen
Attributen 22 . Bei der Identität führen kleinste Abweichungen (z.B. zwei vertausch-
te Buchstaben beim Namen) zwischen zwei Attributwerten direkt zu einer Ähn-
lichkeit von 0.
Für eine Ähnlichkeitsfunktion zweier Tupel sind die verschiedenen Attribute der
Tupel zu berücksichtigen. Dies kann beispielsweise durch die Konkatenation der
einzelnen Attributwerte erfolgen, woraufhin anschließend der Abstand der beiden
entstandenen Zeichenketten gemessen wird. Hierbei fallen fehlende Werte jedoch
übermäßig stark ins Gewicht und unterschiedliche Attributtypen werden nicht be-
rücksichtigt 23 . Daher werden die Attribute eines Tupel-Paares meistens einzeln be-
trachtet. Für jedes Attribut wird separat die Distanz berechnet, wobei die Distanz
normalerweise imWertebereich von 0 bis 1 liegt 24 . Verykios et al. 25 fassen das Er-
gebnis der einzelnen Attributvergleiche in einem Vergleichsvektor zusammen. Die
einzelnen Elemente des Vergleichsvektors können zusätzlich verschieden gewich-
tet werden, um den unterschiedlichen Informationsgehalt der Attribute und Attri-
butwerte zu berücksichtigen 26 . So hat ein Nachname beispielsweise einen höheren
Informationsgehalt als das Geschlecht einer Person. Die gewichteten Abstände der
einzelnen Attribute können dann für eine Klassifikation der Tupel-Paare als Dupli-
kat oder Nicht-Duplikat verwendet werden. Dies kann mit einer Regelmenge bzw.
einem Entscheidungsbaum erfolgen.

Gegeben sind zwei Datensätze r1 und r2 .
IF r1 . Nachname = r2 . Nachname
AND sim ( r1 . Vorname , r2 . Vorname ) => θ

AND r1 . Adresse = r2 . Adresse
THEN r1 = r2

22 vgl. [19]
23 vgl. [19], S. 338
24 vgl. [14], S. 387. Abweichend kann der Wertebereich auch von -1 bis 1 definiert sein.
25 vgl. [34], S. 90
26 vgl. [17], S. 415