|
Learning Expressive Linkage Rules for Entity Matching using Genetic Programming
Isele, Robert
|
URL:
|
https://ub-madoc.bib.uni-mannheim.de/33418
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-334182
|
|
Document Type:
|
Doctoral dissertation
|
|
Year of publication:
|
2013
|
|
Place of publication:
|
Mannheim
|
|
University:
|
Mannheim
|
|
Evaluator:
|
Bizer, Christian
|
|
Date of oral examination:
|
10 June 2013
|
|
Publication language:
|
English
|
|
Institution:
|
School of Business Informatics and Mathematics > Information Systems V: Web-based Systems (Bizer 2012-)
|
|
Subject:
|
500 Science
|
|
Subject headings (SWD):
|
Datenintegration , Datenverknüpfung , Evolutionärer Algorithmus , Genetische Programmierung
|
|
Keywords (English):
|
Entity Matching , Record Linkage , Data Integration , Linkage Rules , Genetic Programming , Active Learning
|
|
Abstract:
|
A central problem in data integration and data cleansing is to identify
pairs of entities in data sets that describe the same real-world object.
Many existing methods for matching entities rely on explicit linkage rules,
which specify how two entities are compared for equivalence. Unfortunately,
writing accurate linkage rules by hand is a non-trivial problem that
requires detailed knowledge of the involved data sets. Another important
issue is the efficient execution of linkage rules.
In this thesis, we propose a set of novel methods that cover the complete
entity matching workflow from the generation of linkage rules using genetic
programming algorithms to their efficient execution on distributed systems.
First, we propose a supervised learning algorithm that is capable of
generating linkage rules from a gold standard consisting of set of entity
pairs that have been labeled as duplicates or non-duplicates. We show that
the introduced algorithm outperforms previously proposed entity matching
approaches including the state-of-the-art genetic programming approach by
de Carvalho et al. and is capable of learning linkage rules that achieve a
similar accuracy than the human written rule for the same problem.
In order to also cover use cases for which no gold standard is available,
we propose a complementary active learning algorithm that generates a gold
standard interactively by asking the user to confirm or decline the
equivalence of a small number of entity pairs. In the experimental
evaluation, labeling at most 50 link candidates was necessary in order to
match the performance that is achieved by the supervised GenLink algorithm
on the entire gold standard.
Finally, we propose an efficient execution workflow that can be run on
cluster of multiple machines. The execution workflow employs a novel
multidimensional indexing method that allows the efficient execution of
learned linkage rules by reducing the number of required comparisons
significantly.
|
|
Translation of the abstract:
|
Ein zentrales Problem der Datenintegration und Datenbereinigung ist das
Finden von Paaren von Entitäten in Datensets, welche das gleiche
Realwelt-Objekt beschreiben. Viele bestehende Methoden für das
Identifizieren solcher Paare basieren auf domänenspezifischen
Verknüpfungsregeln, die festlegen, wie zwei Entitäten auf Äquivalenz
verglichen werden. Allerdings ist das Schreiben solcher Verknüpfungsregeln
von Hand in der Praxis aufwendig und erfordert eine detaillierte Kenntnis
der verwendeten Datensets. Ein weiteres wichtiges Problem stellt das
effiziente Ausführen der generierten Verknüpfungsregeln dar.
Die vorliegenden Arbeit führt neuartige Algorithmen ein, die den gesamten
Entity Matching Prozess abdecken, von der automatischen Erzeugung von
effektiven Verknüpfungsregeln bis zu deren effizienten Ausführung. Zuerst
wird ein genetischer Algorithmus eingeführt, der Verknüpfungsregeln aus
einem Goldstandard lernt, welcher aus einer Menge von Paaren von Entitäten
besteht, worin jedes Paar als Duplikat oder Nicht-Duplikat gekennzeichnet
ist. Die experimentelle Evaluierung zeigt, dass der eingeführte Algorithmus
eine höhere Genauigkeit als bestehende Verfahren einschließlich eines
kürzlich eingeführten genetischen Algorithmus erreicht. Außerdem erreichten
die gelernten Verknüpfungsregeln eine vergleichbare Genauigkeit als Regeln
die für das gleiche Datenset von Hand geschrieben wurden.
Um auch Anwendungsfälle abzudecken, in denen kein Goldstandard verfügbar
ist, wird anschließend ein komplementärer Active Learning Algorithmus
eingeführt, welcher Verknüpfungsregeln interaktiv lernt indem er dem Nutzer
eine kleine Anzahl von Beispielpaaren präsentiert, welcher dieser als
Duplikat oder Nicht-Duplikat kennzeichnet. In den Experimenten erreichte
der vorgestellte Algorithmus, nach dem der Nutzer maximal 50 Kandidaten
manuell gekennzeichnet hat, eine vergleichbare Genauigkeit als der
überwachte Algorithm auf dem gesamten Goldstandard.
Abschließend führt die vorliegenden Arbeit einen Algorithmus zur
Ausfuehrung der gelernten Verknüpfungsregeln auf verteilten Architekturen
ein. Der eingeführte Algorithmus nutzt ein neuartiges
Indexierungsverfahren, welches die Anzahl der notwendigen Vergleiche
signifikant reduziert.
(German)
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Search Authors in
You have found an error? Please let us know about your desired correction here: E-Mail
Actions (login required)
 |
Show item |
|
|
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)