Anytime algorithms for stream data mining

Kranen, Philipp; Seidl, Thomas

doi:3850

Anytime algorithms for stream data mining = Anytime-Algorythmen zur Mustererkennung in Datenströmen

Kranen, Philipp (Author)

2011

Verantwortlichkeitsangabevorgelegt von Philipp Kranen

ImpressumAachen : Publikationsserver der RWTH Aachen University 2011

UmfangIII, 270, XLVI S. : Ill., graph. Darst.

Aachen, Techn. Hochsch., Diss., 2011

Zsfassung in dt. und engl. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Seidl, Thomas (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2011-09-14

Online
URN: urn:nbn:de:hbz:82-opus-38501
URL: https://publications.rwth-aachen.de/record/63005/files/3850.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Data Mining (Genormte SW) ; Automatische Klassifikation (Genormte SW) ; Cluster-Analyse (Genormte SW) ; Datenstrom (Genormte SW) ; Algorithmus (Genormte SW) ; Informatik (frei) ; Anytime-Algorithmen (frei) ; dynamische Daten (frei) ; anytime algorithms (frei) ; evolving data (frei) ; stream data mining (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die rasante Entwicklung der Informationstechnologie hat zur Folge, dass in allen Bereichen der Gesellschaft und des täglichen Lebens große Mengen an Daten erzeugt und gespeichert werden. Beispiele reichen von Multimedia-Daten auf privaten Computern bis hin zu Messdaten in wissenschaftlichen Experimenten. Data Mining beschreibt die Aufgabe, in solchen Daten neue und interessante Muster zu finden. Diese können beispielsweise zur automatischen Empfehlung von Filmen genutzt werden oder helfen neue Zusammenhänge aufzudecken und Prozesse zu verstehen. Seit Beginn der Data Mining Forschung wächst die Größe der zu verarbeitenden Datensätze. Während Datensätze zunächst als statisch und vollständig gegeben angenommen wurden, generieren viele Anwendungen heute kontinuierliche und teilweise unendliche Datenströme. Anytime-Algorithmen stellen eine Klasse von Algorithmen dar, welche sich besonders gut zum Einsatz auf Datenströmen eignet. Ihr Name rührt von ihrer Eigenschaft her, zu jeder Zeit ein Ergebnis liefern zu können. Die zur Verfügung stehende Zeit ist dem Algorithmus dabei nicht bekannt: er berechnet ein initiales Ergebnis und verbessert dieses solange zusätzliche Rechenzeit vorhanden ist. Wird der Algorithmus unterbrochen, so liefert er das beste Ergebnis zurück, welches bis zu diesem Zeitpunkt erzielt wurde. In dieser Dissertation werden neue Anytime-Verfahren für die Bayes Klassifikation entwickelt, intensiv untersucht und evaluiert. Der erste Anytime-Algorithmus zum Clustern von Datenströmen wird vorgestellt und eine Anwendung für die Erkennung von Ausreißern wird diskutiert. Neben neuen Algorithmen werden zwei übergeordnete Verfahren entwickelt, die den Anwendungsbereich für Anytime-Algorithmen signifikant erweitern. Die in dieser Dissertation vorgestellten Ansätze und Resultate tragen zum Stand der Forschung im Bereich Anytime-Algorithmen und Data Mining auf Datenströmen bei.

Data is collected and stored everywhere, be it images or audio files on private computers, customer data in traditional or electronic businesses, performance or control data in production sites, web traffic and click streams at internet providers, statistical data at government agencies, sensor measurements in scientific experimentation, surveillance data, etc. There are countless examples, and the amount of data is tremendous. Data mining is the process of finding useful and previously unknown patterns in data. In the examples listed above, data mining can be used for automated recommendation of audio files, business analysis and target marketing, or performance optimization and hazard warnings. While early mining algorithms only considered static data sets, research and practice in data mining must nowadays deal with continuous, possible infinite streams of data, which are prevalent in most real world applications and scenarios. Anytime algorithms constitute a special type of algorithm that is well suited to work on data streams. They inherit their name from their ability to provide a result after any amount of processing time. The amount of time available is not known to the algorithm in advance: anytime algorithms quickly compute an initial result and strive to improve it as long as time remains. When interrupted they deliver the best result obtained until that point in time. In this thesis anytime classification is studied in depth for the Bayesian approach. New algorithmic solutions for anytime classification are developed and evaluated in extensive experimentation. The first anytime stream clustering algorithm is proposed, and an application to anytime outlier detection is presented. In addition to the algorithmic contributions, new meta-approaches are described that significantly widen the area of applications for anytime algorithms. The solutions and results of this thesis contribute to the state of the art in anytime algorithms and stream data mining research.

Fulltext:
PDF