Methods for frequent sequence mining with subsequence constraints

Beedkar, Kaustubh

Vorschau

PDF
beedkar-phd-thesis.pdf - Veröffentlichte Version
Download (1MB)

URL:	https://madoc.bib.uni-mannheim.de/41778
URN:	urn:nbn:de:bsz:180-madoc-417787
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2016
Ort der Veröffentlichung:	Mannheim
Hochschule:	Universität Mannheim
Gutachter:	Gemulla, Rainer
Datum der mündl. Prüfung:	10 Februar 2017
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science I: Data Analytics (Gemulla 2014-)
Fachgebiet:	004 Informatik
Normierte Schlagwörter (SWD):	Data Mining
Freie Schlagwörter (Englisch):	Large-scale Frequent Sequence Mining, Declarative Frequent Sequence Mining
Abstract:	In this thesis, we study scalable and general purpose methods for mining frequent sequences that satisfy a given subsequence constraint. Frequent sequence mining is a fundamental task in data mining and has many real-life applications like information extraction, market-basket analysis, web usage mining, or session analysis. Depending on the underlying application, we are generally interested in discovering certain frequent sequences, which are described using subsequence constraints. There exists many tools and algorithms for this task, however, they are not sufficiently scalable to deal with large amounts of data that may arise in applications and are generally not extensible across range of applications. We propose scalable, distributed sequence mining algorithms that target MapReduce. Our work builds on MG-FSM, which is a distributed framework for frequent sequence mining. We propose novel algorithms that improve and extend the basic MG-FSM framework to efficiently support traditional subsequence constraints that arise in applications. Additionally, we show that many subsequence constraints---including and beyond the traditional ones considered in literature---can be unified in a single framework. A unified treatment allows researchers to study jointly many types of subsequence constraints (instead of each one individually) and helps to improve usability of pattern mining systems for practitioners. To this end, we propose a general purpose framework that provides a set of simple and intuitive ``pattern expressions'', which allows to describe any subsequence constraint of interest and explore algorithms for efficiently mining frequent subsequences under such general constraints. Our experimental study on real-world datasets indicates that our proposed algorithms are scalable and effective across wide range of applications.
Übersetzung des Abstracts:	In dieser Arbeit untersuchen wir skalierbare und universale Methoden zum Mining von häufigen Sequenzen, die eine vorgegebene Teilsequenzbeschränkung erfüllen. Das Mining von häufigen Sequenzen ist eine wesentliche Aufgabe in Data Mining und hat viele Anwendungen in der echten Welt wie Informationsextraktion, Warenkorbanalyse, Mining von Webnutzung oder Websitzungsanalyse. Abhängig von der zugrunde liegenden Anwendung sind wir allgemein daran interessiert, bestimmte häufige Sequenzen zu entdecken, die mithilfe von Teilsequenzbeschränkungen beschrieben werden. Viele Werkzeuge und Algorithmen existieren bereits für diese Aufgabe, allerdings sind diese nicht in der Lage, mit großen Mengen von Daten umzugehen, welche im Anwendungsfall auftreten können und sich im Allgemeinen nicht über eine Reihe von Anwendungen erweitern lassen. Wir stellen skalierbare, verteilte Sequenz Mining-Algorithmen vor, die auf MapReduce abzielen. Unsere Arbeit baut auf MG-FSM auf, ein verteiltes Framework für das Mining von häufigen Sequenzen. Wir stellen neuartige Algorithmen vor, die das grundlegende MG-FSM-Framework verbessern und erweitern, um traditionelle in Anwendungen auftretende Subsequenzbeschränkungen effizient zu unterstützen, Zusätzlich zeigen wir, dass viele Subsequenzbeschränkungen -- einschließlich der traditionell in der Literatur berücksichtigten Beschränkungen und darüber hinaus -- in einem einzigen Framework vereinheitlicht werden können. Eine einheitliche Behandlung erlaubt Forschern, gleichzeitig viele Arten von Subsequenzbeschränkungen zu untersuchen (anstatt jede einzeln) und hilft dabei, die Nutzbarkeit von Pattern Mining-Systemen für Anwender zu verbessern. Zu diesem Zweck stellen wir ein universales Framework vor, das eine Menge von einfachen und intuitiven "Pattern Expressions" bereitstellt. Diese erlauben, jede beliebige Beschränkung zu beschreiben und Algorithmen zum effizienten Mining von häufigen Subsequenzen unter solch allgemeinen Bedingungen zu untersuchen. Unsere Teststudie zu echten Datensätzen zeigt, dass unsere vorgeschlagenen Algorithmen skalierbar und effizient über eine große Breite an Anwendungen hinweg sind. (Deutsch)