Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-10928
For citation please use:
Main Title: Semi-supervised data cleaning
Translated Title: Teilüberwachte Datenreinigung
Author(s): Mahdavi Lahijani, Mohammad
Advisor(s): Abedjan, Ziawasch
Referee(s): Abedjan, Ziawasch
Lehner, Wolfgang
Wu, Eugene
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: Data cleaning is one of the most important but time-consuming tasks for data scientists. The data cleaning task consists of two major steps: (1) error detection and (2) error correction. The goal of error detection is to identify wrong data values. The goal of error correction is to fix these wrong values. Data cleaning is a challenging task due to the trade-off among correctness, completeness, and automation. In fact, detecting/correcting all data errors accurately without any user involvement is not possible for every dataset. We propose a novel data cleaning approach that detects/corrects data errors with a novel two-step task formulation. The intuition is that, by collecting a set of base error detectors/correctors that can independently mark/fix data errors, we can learn to combine them into a final set of data errors/corrections using a few informative user labels. First, each base error detector/corrector generates an initial set of potential data errors/corrections. Then, the approach ensembles the output of these base error detectors/correctors into one final set of data errors/corrections in a semi-supervised manner. In fact, the approach iteratively asks the user to annotate a tuple, i.e., marking/fixing a few data errors. The approach learns to generalize the user-provided error detection/correction examples to the rest of the dataset, accordingly. Our novel two-step formulation of the error detection/correction task has four benefits. First, the approach is configuration free and does not need any user-provided rules or parameters. In fact, the approach considers the base error detectors/correctors as black-box algorithms that are not necessarily correct or complete. Second, the approach is effective in the error detection/correction task as its first and second steps maximize recall and precision, respectively. Third, the approach also minimizes human involvement as it samples the most informative tuples of the dataset for user labeling. Fourth, the task formulation of our approach allows us to leverage previous data cleaning efforts to optimize the current data cleaning task. We design an end-to-end data cleaning pipeline according to this approach that takes a dirty dataset as input and outputs a cleaned dataset. Our pipeline leverages user feedback, a set of data cleaning algorithms, and a set of previously cleaned datasets, if available. Internally, our pipeline consists of an error detection system (named Raha), an error correction system (named Baran), and a transfer learning engine. As our extensive experiments show, our data cleaning systems are effective and efficient, and involve the user minimally. Raha and Baran significantly outperform existing data cleaning approaches in terms of effectiveness and human involvement on multiple well-known datasets.
Die Datenbereinigung ist eine der wichtigsten, aber zeitraubendsten Aufgaben für Datenwissenschaftler. Die Datenbereinigungsaufgabe besteht aus zwei Hauptschritten: (1) Fehlererkennung und (2) Fehlerkorrektur. Das Ziel der Fehlererkennung ist es, falsche Datenwerte zu identifizieren. Das Ziel der Fehlerkorrektur ist es, diese falschen Werte in korrekte Werte zu korrigieren. Die Datenbereinigung ist eine anspruchsvolle Aufgabe aufgrund des Kompromisses zwischen Korrektheit, Vollständigkeit und Automatisierung. Tatsächlich ist es nicht für jeden Datensatz möglich, alle Datenfehler ohne Beteiligung des Benutzers genau zu erkennen und zu korrigieren. Wir schlagen einen neuartigen Datenbereinigungsansatz vor, der Datenfehler mit einer neuartigen zweistufigen Aufgabenformulierung entdeckt/korrigiert. Die Intuition ist, dass wir durch das Sammeln eines Menge von Basisfehler-Detektoren/Korrektoren, die Datenfehler unabhängig voneinander markieren/beheben können, lernen können, sie mit Hilfe einiger informativer Benutzerannotationen zu einem endgültigen Satz von Datenfehlern/Korrekturen zu kombinieren. Zunächst erzeugt jeder Basisfehler-Detektor/Korrektor einen ersten Satz potenzieller Datenfehler/Korrekturen. Dann fasst der Ansatz die Ausgabe dieser Basisfehler- Detektoren/Korrektoren in einer halb-überwachten Weise zu einem endgültigen Satz von Datenfehlern/Korrekturen zusammen. Tatsächlich fordert der Ansatz den Benutzer iterativ auf, ein Tupel zu annotieren, d.h. einige wenige Datenfehler zu markieren/zu korrigieren. Der Ansatz lernt, die vom Benutzer zur Verfügung gestellten Fehlererkennungs-/Korrekturbeispiele entsprechend auf den Rest des Datensatzes zu zu generalisieren. Unsere neuartige zweistufige Formulierung der Fehlererkennungs-/Fehlerkorrekturaufgabe hat vier Vorteile. Erstens ist der Ansatz konfigurationsfrei und benötigt keine vom Benutzer bereitgestellten Regeln oder Parameter. Tatsächlich betrachtet der Ansatz die Basis- Fehlerdetektoren/-korrektoren als Black-Box-Algorithmen, die nicht unbedingt korrekt oder vollständig sind. Zweitens ist der Ansatz bei der Fehlererkennungs-/Fehlerkorrekturaufgabe effektiv, da seine ersten und zweiten Schritte die Empfindlichkeit bzw. Genauigkeit maximieren. Drittens minimiert der Ansatz auch die menschliche Beteiligung, da er die informativsten Tupel des Datensatzes für die Benutzerbeschriftung auswählt. Viertens ermöglicht uns die Aufgabenformulierung unseres Ansatzes, frühere Datenbereinigungsbemühungen zur Optimierung der aktuellen Datenbereinigungsaufgabe zu nutzen. Wir entwerfen nach diesem Ansatz eine End-to-End-Datenbereinigungs-Pipeline, die einen fehlerhaften Datensatz als Eingabe nimmt und einen bereinigten Datensatz ausgibt. Unsere Pipeline nutzt das Benutzer-Feedback, einen Satz von Datenbereinigungsalgorithmen und, falls verfügbar, historische Daten. Intern besteht unsere Pipeline aus einem Fehlererkennungssystem (namens Raha), einem Fehlerkorrektursystem (namens Baran) und einer Transferlernmaschine. Wie unsere umfangreichen Experimente zeigen, sind unsere Datenbereinigungssysteme effektiv und effizient und involvieren den Benutzer nur minimal. Raha und Baran übertreffen bestehende Datenbereinigungsansätze in Bezug auf Wirksamkeit und menschliche Beteiligung bei mehreren bekannten Datensätzen erheblich.
URI: https://depositonce.tu-berlin.de/handle/11303/12054
http://dx.doi.org/10.14279/depositonce-10928
Exam Date: 6-Nov-2020
Issue Date: 2020
Date Available: 4-Dec-2020
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): data cleaning
machine learning
data science
error detection
error correction
Datenbereinigung
maschinelles Lernen
Datenwissenschaft
Fehlererkennung
Fehlerkorrektur
License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:FG Datenbanksysteme und Informationsmanagement (DIMA) » Publications

Files in This Item:
mahdavi_mohammad.pdf
Format: Adobe PDF | Size: 1.91 MB
DownloadShow Preview
Thumbnail

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons