Authors:	Geilke, Michael
Title:	Online density estimates : a probabilistic condensed representation of data for knowledge discovery
Online publication date:	27-Nov-2017
Year of first publication:	2017
Language:	english
Abstract:	The Internet of Things (IoT) and the data that is generated from its sensors are making new demands on data mining methods. These demands stem from the desire to benefit from the knowledge contained in this data and the increasing number of devices that are equipped with these sensors. According to companies like Intel or HP, the number of sensors worldwide is likely to reach more than one trillion by 2022. All of them will produce streams of measurements and leveraging knowledge from these streams requires infrastructure to analyze them in real-time. From a data mining perspective, this involves challenging tasks such as cleaning the data, handling large amounts of data, and preserving their privacy, to name a few. The state of the art in data mining already addressed some of these challenges, but the proposed methods are typically designed for a specific task (e.g., predicting a certain variable or finding frequent patterns) and perform this task while scanning the data stream. However, at the time of collecting the data, it is often not known what kind of analysis needs to be performed or there are several -- possibly even dependent -- analysis tasks. This means that whenever storing the original data is either not feasible due to the sheer volume or impossible due to privacy concerns, the user has to wait for more data to initiate another analysis task, which impedes the use of conventional data mining algorithms. Therefore, we present a framework in this thesis, called MiDEO (Mining Density Estimates inferred Online), which decouples the process of collecting the data from the actual analysis. It uses density estimates to maintain a compact representation of the data stream and provides inference capabilities to perform queries on them. The queries can be combined to complex data mining tasks and allow to adapt the estimates to the current needs of the user or the algorithm. Compared to current methods that typically focus on one task at a time, this enables a more interactive analysis of the data stream, where the task selection is part of the analysis. In the course of designing such a framework, we develop several methods to improve the state of the art. This includes online density estimators for conditional joint densities with mixed types of variables, an online density estimator for high-dimensional data, algorithms to perform pattern mining on online density estimates, an online density estimator that is able to represent recurrences in the data stream, and algorithms that enforce well-known privacy-preserving properties to protect the entities described by the data. To show the effectiveness of these methods, we prove some of their theoretical properties and perform an extensive set of experiments. Das Internet of Things (IoT) und die aus dessen Sensoren generierten Daten stellen neue Anforderungen an Data Mining Methoden. Diese Anforderungen gehen aus dem Wunsch hervor, von dem den Daten inhärenten Wissen zu profitieren sowie der wachsenden Anzahl von mit Sensoren ausgestatteten Geräten gerecht zu werden. Firmen wie Intel oder HP zufolge kann im Jahr 2022 mit über einer Trillion Sensoren weltweit gerechnet werden. All diese Sensoren werden Ströme von Messdaten produzieren, deren Echtzeit-Analyse eine angemessene Infrastruktur voraussetzt. Im Data Mining stellen sich damit primär neue Herausforderungen wie unter anderem das Bereinigen der Daten, der Umgang mit sehr großen Datenmengen sowie die Berücksichtigung der Privatsphäre. Führende Data Mining Methoden haben sich bereits mit einigen dieser Herausforderungen befasst, allerdings sind sie typischerweise auf eine bestimmte Data Mining Aufgabe zugeschnitten (z.B. das Vorhersagen einer Variablen oder das Finden von häufigen Mustern), die darüberhinaus beim Scannen des Datenstroms ausgeführt wird. Jedoch steht während des Sammelns der Daten üblicherweise nicht fest, welche Art von Analyse benötigt wird oder es sind mehrere -- gegebenenfalls voneinander abhängige -- Analysen erforderlich. Können Daten wegen ihres Volumens oder aus Gründen der Privatsphäre nicht gespeichert werden, ist der Nutzer gezwungen, auf neu eintreffende Daten zu warten, bevor er eine neue Analyse durchführen kann. Um diesem Problem entgegen zu gehen, präsentieren wir in dieser Arbeit das MiDEO (Mining Density Estimates inferred Online) Framework. Dieses entkoppelt den Prozess der Datensammlung von der Datenanalyse. Mittels Online-Dichteschätzern verfügt es über eine jederzeit aktuelle sowie kompakte Version des Datenstroms und stellt Inferenzalgorithmen zur Verfügung um Anfragen auf die Daten zu erlauben. Diese Anfragen können zu komplexen Data Mining Aufgaben kombiniert werden und erlauben dem Benutzer eine Anpassung gemäß den aktuellen Anforderungen. Verglichen mit herkömmlichen Methoden wird so eine interaktivere Analyse der Datenströme ermöglicht, wobei die Wahl der zu lösenden Data Mining Aufgabe Teil der Analyse ist. Im Zuge der Entwicklung dieses Frameworks haben wir mehrere kompetitive Methoden entwickelt. Dies beinhaltet Online-Dichteschätzer für bedingte Verbundwahrscheinlichkeiten mit gemischten Variablentypen, einen Online-Dichteschätzer für hochdimensionale Daten, auf Online-Dichteschätzern arbeitende Pattern Mining Algorithmen, einen Rekurrenzen darstellenden Online-Dichteschätzer sowie Algorithmen, welche die Privatsphäre, der in den Daten beschriebenen Individuen schützen. Die Effektivität dieser Methoden wird durch den Beweis einiger theoretischer Eigenschaften und umfangreiche Experimente belegt.
DDC:	004 Informatik 004 Data processing
Institution:	Johannes Gutenberg-Universität Mainz
Department:	FB 08 Physik, Mathematik u. Informatik
Place:	Mainz
ROR:	https://ror.org/023b0x485
DOI:	http://doi.org/10.25358/openscience-1375
URN:	urn:nbn:de:hebis:77-diss-1000016649
Version:	Original work
Publication type:	Dissertation
License:	In Copyright
Information on rights of use:	https://rightsstatements.org/vocab/InC/1.0/
Extent:	x, 193 Seiten
Appears in collections:	JGU-Publikationen