Statistical and Probabilistic Methods for Data Stream Mining
The aim of this work is not only to highlight and summarize issues and challenges which arose during the mining of data streams, but also to find possible solutions to illustrated problems. Due to the streaming nature of the data, it is impossible to hold the whole data set in the main memory, i.e. efficient on-line computations are needed. For instance incremental calculations could be used in order to avoid to start the computation process from scratch each time new data arrive and to save memory. Another important aspect in data stream analysis is that the data generating process does not remain static, i.e.\ the underlying probabilistic model cannot be assumed to be stationary. The changes in the data structure may occur over time. Dealing with non-stationary data requires change detection and on-line adaptation. Furthermore real data is often contaminated with noise, this causes a specific problem for approaches dealing with the data streams. They must be able to distinguish between changes according to noise and changes of the underlying data generating process or its parameters. In this work we propose a variety of different methods, which fulfil specific requirements of data stream mining. Furthermore we carry out theoretical analysis of effects of noise and changes in data stream for sliding window based evolving system in order to illustrate the problem of suboptimal window size. In order to do the validation of an evolving system significant, we propose some simple benchmark tests that can give an idea of how much an evolving system might be misled by noise.
Das Hauptziel dieser Arbeit ist es, zentrale Probleme und wichtige Aspekte im Datastream-Mining zu veranschaulichen und mögliche Lösungen zu diskutierten Problemen vorzustellen. Da die Anzahl der Daten bei Datastreams potenziell unendlich ist und die statistischen Eigenschaften der Daten sich mit der Zeit ändern können, lassen sich klassische Data-Mining- und Statistikmethoden nicht auf Data Streams direkt anwenden. Aus diesem Grund werden im Rahmen dieser Arbeit bereits existierende Ansätze an die Datastream-Problematik angepasst und neue Methoden entwickelt. Zum Beispiel werden inkrementelle oder rekursive Berechnungen statistischer Parameter und statistischer Tests vorgestellt, die nötig sind, um Berechnungen online und auf Hardware wie Steuergeräten mit teilweise recht begrenzter Rechen und Speicherkapazität ausführen zu können. Ein wesentliches Problem stellt die Unterscheidung zwischen zufälligen Schwankungen im Sinne von Rauschen und echten Änderungen in Datastreams dar. Es bietet sich an, Hypothesentests mit inkrementeller Berechnung für dieses Problem der Change Detection einzusetzen. In dieser Arbeit werden inkrementelle und auf Fenstertechnik basierende statistische Tests für Change Detection vorgestellt. Die Mehrzahl der existierenden Algorithmen zum Datastream-Mining verwenden keine expliziten Methoden zur Change Detection, sondern benutzen für die Vorhersage gleitende Fenster fester Breite. Nur wenige dieser Methoden beschäftigen sich mit der Frage wie die Fenstergröße ausgewählt werden soll und welche Effekte Veränderungen in den Daten auf die Vorhersagequalität haben. Hierzu wird eine theoretische Analyse für die optimale Fensterbreite für zwei Datenmodelle durchgeführt und gezeigt, dass eine suboptimale Fenstergröße zur drastischen Senkung der Vorhersagequalität führen kann. Außerdem können die vorgestellten Datenmodelle als Benchmark Tests für fensterbasierte Ansätze verwendet werden. Dies kann einen Eindruck vermitteln, wie stark ein sich an Datastreams automatisch anpassendes "Evolving System" durch Rauschen in den Daten negativ beeinflusst wird.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved