Methods for frequent sequence mining with subsequence constraints


Beedkar, Kaustubh


[img]
Preview
PDF
beedkar-phd-thesis.pdf - Published

Download (1MB)

URL: https://ub-madoc.bib.uni-mannheim.de/41778
URN: urn:nbn:de:bsz:180-madoc-417787
Document Type: Doctoral dissertation
Year of publication: 2016
Place of publication: Mannheim
University: Universität Mannheim
Evaluator: Gemulla, Rainer
Date of oral examination: 10 February 2017
Publication language: English
Institution: School of Business Informatics and Mathematics > Praktische Informatik I (Gemulla 2014-)
Subject: 004 Computer science, internet
Subject headings (SWD): Data Mining
Keywords (English): 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.
Translation of the abstract: 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. (German)

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




+ Citation Example and Export

Beedkar, Kaustubh (2016) Methods for frequent sequence mining with subsequence constraints. Open Access Mannheim [Doctoral dissertation]
[img]
Preview


+ Search Authors in

+ 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