Authors:	Ahmadi, Zahra
Title:	Modeling Recurring Concepts in Single-label and Multi-label Streams
Online publication date:	18-Dec-2019
Year of first publication:	2019
Language:	english
Abstract:	Today, we have access to a vast amount of data in the forms of images, speech signals, structured and unstructured texts, and sensor-based signals. Our digital universe is growing quickly. Statistics indicate that 500 million tweets are posted every day. 65 billion messages are transferred on WhatsApp per day. 294 billion emails are sent daily via different platforms. Each self-driving car creates 4 terabytes of data per day. According to a study by Digital Universe, the amount of data produced by humans and machines will exceed 44 billion terabytes by 2020. This means that there will be 5,200 gigabyte of data for every person on earth. It is estimated that by 2025, the created data will increase to 463 million terabytes per day. Processing and leveraging knowledge from these sources of data requires proper infrastructure and efficient methods to analyze them in real-time. Data stream mining is the field of propounding such scalable and efficient methods, which can process data incrementally. Incremental induction from a limited set of observations of an unknown distribution has been the topic of many studies for a long time. Depending on the application, the target class can be only one or many labels among which some unknown dependencies exist. Although this problem is challenging enough, in many of the stream mining applications, the statistical properties of the input and target variable(s) may change over time in unforeseen ways. This phenomena is called concept drift. If not considered and captured properly, the trained online models quickly become obsolete over time. However, these drifts are not well-defined and could contain any change in the statistical properties of data, adding more difficulty to the prediction problem. In this thesis, our overall focus is to model one type of drifts which is called recurrent concepts. Recurrent concepts are important to be captured independently, as most of stream mining methods employ a forgetting mechanism in the learning process and forget their outdated extracted knowledge. To this end, we propose the GraphPool and multi-label GraphPool frameworks for both single-label and multi-label data streams. These frameworks keep a pool of concepts and their transitions in a first-order Markov chain to quickly recover from drifts in the streams with periodic behavior. In the course of designing such a framework for multi-label streams, we develop an efficient algorithm for classifying stationary multi-label streams. To show the effectiveness of our methods, we conduct an extensive set of experiments with both synthetic and real-world data. Heutzutage haben wir Zugang zu einer riesigen Menge an Daten in Form von Bildern, Sprachsignalen, strukturierten und unstrukturierten Texten, sowie sensorbasierten Signalen. Unser digitales Universum wächst rasant. Aus Statistiken geht hervor, dass 500 Millionen Tweets täglich hochgeladen werden. 65 Milliarden Nachrichten werden jeden Tag über Whatsapp versandt. 294 Milliarden Emails werden täglich über verschiedene Plattformen verschickt. Jedes selbstfahrende Auto erzeugt täglich 4 Terabyte an Daten. Laut einer Studie von Digital Universe wird die Menge an von Menschen und Maschinen produzierten Daten 44 Milliarden Terabytes bis 2020 übersteigen. Das bedeutet, zu jedem Menschen auf der Erde wird es 5,200 Gigabyte an Daten geben. Es gibt Schätzungen, dass sich die täglich generierte Datenmenge bis 2025 auf 463 Millionen Terabyte erhöht. Um diese Datenmengen zu verarbeiten und aus den Datenquellen Wissen herzuleiten, werden geeignete Infrastrukturen und effiziente Methoden benötigt, die in der Lage sind, die Daten zur Laufzeit zu analysieren. Data-Stream-Mining ist das Gebiet, das solche skalierbaren und effizienten Methoden bereitstellt, welche Daten inkrementell verarbeiten können. Die inkrementelle Induktion einer beschränkten Menge an Beobachtungen einer unbekannten Verteilung ist seit langer Zeit Gegenstand vieler Studien. Abhängig von der Anwendung kann die Zielklasse nur ein oder viele Label haben, zwischen denen unbekannte Abhängigkeiten existieren können. Obwohl dieses Problem bereits eine Herausforderung darstellt, können sich zusätzlich in vielen Stream-Mining-Anwendungen die statistischen Eigenschaften des Inputs und der Zielvariable(n) unvorhergesehen über die Zeit ändern. Dieses Phänomen wird als Concept Drift bezeichnet. Wenn dies nicht berücksichtigt und ordentlich gehandhabt wird, werden trainierte Online-Modelle schnell obsolet. Außerdem sind diese Drifts nicht wohldefiniert und können jegliche Änderungen in den statistischen Eigenschaften der Daten enthalten, was das Prognoseproblem noch schwieriger gestaltet. Der Hauptfokus dieser Arbeit ist die Modellierung eines Typs von Drifts, welcher als Recurrent Concepts bezeichnet wird. Es ist wichtig, dass Recurrent Concepts unabhängig voneinander abgefangen werden, da die meisten Stream-Mining-Methoden einen Vergessen-Mechanismus in den Lernprozess einbauen und ihr veraltetes extrahiertes Wissen vergessen. Wir schlagen die GraphPool und Multi-Label GraphPool-Umgebungen für Single-Label und Multi-Label-Datenströme vor. Diese Umgebungen behalten einen Pool von Konzepten und ihrer Überführung in eine Markovkette erster Ordnung, um sich schnell an periodische Drifts in den Strömen anzupassen. Im Zusammenhang mit der Konzipierung einer solchen Umgebung für Multi-Label-Ströme, entwickeln wir einen effizienten Algorithmus für die Klassifizierung von stationären Multi-Label-Strömen. Um die Effektivität unserer Methoden zu demonstrieren, führen wir eine umfangreiche Menge von Experimenten anhand von synthetischen und realen Daten durch.
DDC:	500 Naturwissenschaften 500 Natural sciences and mathematics
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-3587
URN:	urn:nbn:de:hebis:77-diss-1000032202
Version:	Original work
Publication type:	Dissertation
License:	In Copyright
Information on rights of use:	https://rightsstatements.org/vocab/InC/1.0/
Extent:	xviii, 158 Seiten
Appears in collections:	JGU-Publikationen