TU Darmstadt / ULB / tuprints

Unsupervised Duplicate Detection Using Sample Non-Duplicates

Lehti, Patrick :
Unsupervised Duplicate Detection Using Sample Non-Duplicates.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2006)

[img]
Preview
Dissertation - PDF
thesis.pdf
Available under Simple publication rights for ULB.

Download (1337Kb) | Preview
[img]
Preview
Lebenslauf - PDF
LebenslaufDiss.pdf
Available under Simple publication rights for ULB.

Download (5Kb) | Preview
Item Type: Ph.D. Thesis
Title: Unsupervised Duplicate Detection Using Sample Non-Duplicates
Language: English
Abstract:

The problem of identifying objects in databases that refer to the same real world entity, is known, among others, as duplicate detection or record linkage. Objects may be duplicates, even though they are not identical due to errors and missing data. Traditional scenarios for duplicate detection are data warehouses, which are populated from several data sources. Duplicate detection here is part of the data cleansing process to improve data quality for the data warehouse. More recently in application scenarios like web portals, that offer users unified access to several data sources, or meta search engines, that distribute a search to several other resources and finally merge the individual results, the problem of duplicate detection is also present. In such scenarios no long and expensive data cleansing process can be carried out, but good duplicate estimations must be available directly. The most common approaches to duplicate detection use either rules or a weighted aggregation of similarity measures between the individual attributes of potential duplicates. However, choosing the appropriate rules, similarity functions, weights, and thresholds requires deep understanding of the application domain or a good representative training set for supervised learning approaches. For this reason, these approaches entail significant costs. This thesis presents an unsupervised, domain independent approach to duplicate detection that starts with a broad alignment of potential duplicates, and analyses the distribution of observed similarity values among these potential duplicates and among representative sample non-duplicates to improve the initial alignment. To this end, a refinement of the classic Fellegi-Sunter model for record linkage is developed, which makes use of these distributions to iteratively remove clear non-duplicates from the set of potential duplicates. Alternatively also machine learning methods like Support Vector Machines are used and compared with the refined Fellegi-Sunter model. Additionally, the presented approach is not only able to align flat records, but makes also use of related objects, which may significantly increase the alignment accuracy, depending on the application. Evaluations show that the approach supersedes other unsupervised approaches and reaches almost the same accuracy as even fully supervised, domain dependent approaches.

Alternative Abstract:
Alternative AbstractLanguage
Das Problem zu erkennen, dass verschiedene Datenbankeinträge sich auf das selbe reale Objekt beziehen, ist in der Literatur als "duplicate detection" (Duplikaterkennung) oder "record linkage" bekannt. Solche Datenbankeinträge können auch dann Duplikate sein, wenn sie fehlerhafte oder unvollständige Informationen enthalten. Klassisch tritt dieses Problem bei der Erstellung von Datawarehouses auf, wo verschiedene unabhängige Datenquellen integriert werden sollen. Datawarehouses werden oft genutzt, um wichtige Geschäftsentscheidungen zu treffen, und müssen deshalb von hoher Qualität sein, d.h. möglichst frei von Duplikaten. Webportale sind ein weiteres Anwendungsfeld für Duplikaterkennung, denn diese ermöglichen den einheitlichen Zugriff auf unabhängige Datenquellen, und Duplikate schmälern dabei den Nutzen eines solchen Portals. Die Unabhängigkeit der Datenquellen verlangt hierbei, dass die Duplikaterkennung regelmäßig bei Aktualisierungen der Daten durchgeführt wird. Metasuchmaschinen schließlich müssen ebenfalls eine Duplikaterkennung bei der Vereinigung ihrer Ergebnisse durchführen, um den Nutzen für den Anwender zu erhöhen. Da in diesem Fall keine Kontrolle über die Datenquellen besteht, muss die Duplikaterkennung dynamisch bei jedem Zugriff erfolgen. Existierende Ansätze zur Duplikaterkennung benutzen üblicherweise Regeln oder eine gewichtete Aggregation von ähnlichkeitsmaßen. Das Bestimmen dieser Regeln oder Gewichte und die Auswahl geeigneter ähnlichkeitsmaße erfordert eine sehr gute Kenntnis der Daten oder benötigt gute repräsentative Trainingsdaten. Diese zu erhalten ist mit großem Aufwand verbunden, was sich in den hohen Kosten für typische Integrationsprojekte im Datawarehouseumfeld zeigt. Für die anderen Anwendungsfelder sind diese Ansätze gar nicht oder nur sehr bedingt geeignet. Diese Arbeit präsentiert ein Verfahren zur automatischen Duplikaterkennung für beliebige Datenquellen. Dazu werden in einem ersten Schritt eine Menge von Kandidatduplikaten und eine Menge von repräsentativen Nicht-Duplikaten bestimmt und deren ähnlichkeiten berechnet. Hierfür wird angenommen (und das Verfahren auf diesen Fall eingeschränkt), dass Duplikate zwischen verschiedenen und in sich annähernd duplikatfreien Datenquellen erkannt werden sollen. Die genannten Mengen werden dann mit Hilfe einer deutlich präziseren und effizienteren Variante des sog. Sorted-Neighborhood-Verfahrens bestimmt. Die unterschiedliche Verteilung der ähnlichkeiten bei den Kandidatduplikaten und den Nicht-Duplikate wird dann genutzt, um iterativ die Menge der Kandidatduplikate zu verfeinern. Dazu wird einerseits eine Erweiterung eines klassischen statistischen Verfahrens (das Fellegi-Sunter-Modell), als auch ein modernes Verfahren aus dem Bereich maschinelles Lernen (Support Vector Machines) evaluiert. Um nicht nur flache Datensätze auf Duplikate überprüfen zu können, wird zusätzlich erklärt wie das Verfahren für beliebige Graph-basierte Datenmodelle erweitert werden kann. Dazu werden zusätzliche ähnlichkeitsmaße für Beziehungen eingeführt, die die Qualtät der Duplikaterkennung deutlich verbessern können. Die zahlreichen Experimente zeigen, dass das vorgestellte Verfahren eine wesentlich bessere Qualität der Duplikaterkennung erreicht, als andere automatische Verfahren und sogar nah an die Qualität von Verfahren mit manuell ausgewählten Trainingsdaten heranreicht.German
Uncontrolled Keywords: Duplikaterkennung, Datenbereinigung
Alternative keywords:
Alternative keywordsLanguage
Duplikaterkennung, DatenbereinigungGerman
duplicate detection, record linkage, data cleansingEnglish
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:22
Last Modified: 07 Dec 2012 11:52
Official URL: http://elib.tu-darmstadt.de/diss/000741
URN: urn:nbn:de:tuda-tuprints-7411
License: Simple publication rights for ULB
Referees: Neuhold, Prof. Dr.- Erich and Hofmann, Prof. Dr. Thomas
Advisors: Fankhauser, Dr. Peter
Refereed: 17 May 2006
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/741
Export:

Actions (login required)

View Item View Item