Vergleich Blocking- und Sorted-Neighborhood-Methode - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 55

Precision und Recall
Precision und Recall sind in Abbildung 5.7 graphisch dargestellt. Die Precisi-
on entspricht für Blocking dem Niveau der Sorted-Neighborhood-Methode. Beim
Blocking sind jedoch die Ausschläge nach oben und unten stärker, was auf die
strikte Trennung der Blöcke zurückzuführen ist. Durch die Vergrößerung der Blö-
cke ist es möglich, dass Duplikate, die bei kleinen Blöcken in einem Block lagen
durch die Block-Vergrößerung auf verschiedene Blöcke aufgeteilt und somit nicht
mehr erkannt werden.
Zusätzlich zu den beiden Partitionierungsverfahren enthält die Abbildung auch
die Precision des vollständigen Tupelvergleichs 7 . Diese ist deutlich geringer als
die Precision von Blocking und Sorted-Neighborhood. Dies liegt daran, dass auch
in der Sortierreihenfolge weit entfernete Tupel miteinander verglichen werden und
durch die Toleranz der Ähnlichkeitsfunktion ggf. falsch klassifiziert werden. Wie
bereits angesprochen, verstärkt sich der Effekt noch, wenn zusätzlich die transitive
Hülle gebildet wird.
Bei der Betrachtung der Vollständigkeit der Duplikaterkennung anhand des Re-
calls, kann der Wert des vollständigen Vergleichs als obere Schranke betrachtet
werden. Eine Unterscheidung, ob die transitive Hülle gebildet wurde oder nicht,
ist nicht notwendig, da keine zusätzlichen echte Duplikate erkannt wurden und
fehlerhaft klassifizierte Duplikate den Recall nicht beeinflussen. Der Recall für die
Sorted-Neighborhood-Methode liegt durchgehend auf einem hohen Niveau. Dies
liegt daran, dass in den Testdaten bei dem beschriebenen Sortierschlüssel bei 70%
der echten Duplikate die Tupel direkt nebeneinander liegen und zwischen wei-
teren 10% der echten Duplikate die Tupel nur durch ein einziges Tupel getrennt
sind. Daher fallen auch bei kleinen Fenstergrößen über 80% der Duplikaten-Paare
in ein gemeinsames Fenster. Der Anstieg der Kurve bei der Sorted-Neighborhood-
Methode nimmt mit zunehmender Fenstergröße jedoch ab, da eine Sättigung er-
reicht wurde.
Deutlicher fällt der Effekt beim Blocking aus. Hier ist der Recall bei wenigen
Tupelvergleichen relativ niedrig und steigt zunächst stark an. Mit zunehmender
Anzahl von Vergleichen flacht der Anstieg der Kurve jedoch ebenfalls ab. Die
Sprünge innerhalb der Kurve sind wie bei der Precision durch eine Verschiebung
von Duplikaten in unterschiedliche Blöcke zu erklären.
7 Der vollständige Vergleich beinhaltet ca. 47,6 Mio Tupel-Vergleiche. In den Abbildungen 5.7 und
5.8 sind die Kennzahlen des vollständigen Vergleichs jeweils als Hilfslinie dargestellt.