Learning Expressive Linkage Rules for Entity Matching using Genetic Programming


Isele, Robert


[img]
Preview
PDF
Isele_Dissertation.pdf - Published

Download (8MB)

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.




Metadata export


Citation


+ Search Authors in

BASE: Isele, Robert

Google Scholar: Isele, Robert

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item