Publikationsserver der Universitätsbibliothek Marburg

Titel:Density Estimation over Data Streams
Autor:Heinz, Christoph
Weitere Beteiligte: Seeger, Bernhard (Prof. Dr.)
Veröffentlicht:2007
URI:https://archiv.ub.uni-marburg.de/diss/z2007/0139
URN: urn:nbn:de:hebis:04-z2007-01399
DOI: https://doi.org/10.17192/z2007.0139
DDC: Informatik
Titel(trans.):Density Estimation over Data Streams
Publikationsdatum:2007-05-22
Lizenz:https://rightsstatements.org/vocab/InC-NC/1.0/

Dokument

Schlagwörter:
Data Mining, Nichtparametrische Statistik, Data Mining, Dichteschätzung, Density Estimation, Datenstrom, Stream Mining, Nonparametric Statistics

Zusammenfassung:
A growing number of real-world applications share the property that they have to deal with transient data arriving in massive volumes, so-called data streams. The characteristics of these data streams render their analysis by means of conventional techniques extremely difficult, in the majority of cases even impossible. In fact, to be applicable to data streams, a technique has to meet rigid processing requirements such as a single pass over the stream and strict limitations on the available memory. With respect to these requirements, an adequate real-time mining and analysis of a data stream has turned out to be a highly demanding task, which can only be tackled by developing tailored techniques. In this work, we delve more deeply into an important building block of many data mining and analysis approaches, namely density estimation, with the objective to adapt it to the data stream scenario. Density estimation, a vital research topic in mathematical statistics, aims to capture the unknown distribution of a real-valued data set by estimating its underlying probability density function. A suitable density estimate can be exploited to gain insight into the main features of the data; it can also prepare the ground for a variety of further analysis tasks. Due to the importance of density estimation, various methods have been developed in recent decades. Among the most promising methods are the nonparametric ones. They stand out from the parametric approaches as they only make very weak assumptions on the data; they let the data speak for themselves. Two important members of the class of nonparametric methods are based on kernels and wavelets. Kernel as well as wavelet density estimators are theoretically founded and practically approved, but their computational burden severely impedes their applicability. In particular, neither kernel nor wavelet density estimators can be computed over real-valued data streams because their computational complexity collides with the processing requirements for streams. However, as density estimation can be a crucial component of data stream analysis, we devoted ourselves to the adaptation of kernel and wavelet density estimators to data streams in compliance with the processing requirements for streams. Our solution for wavelet density estimators, termed compressed-cumulative WDEs, relies on processing blocks of data of the stream, where each data block is associated with a separate estimator. While processing the stream, the block estimators are successively merged into one estimator. Our solution for kernel density estimators utilizes specific building blocks, termed Cluster Kernels, to derive an estimator for the stream on demand. These Cluster Kernels summarize already processed elements in terms of local statistics, which are used for an approximate resampling of elements. Both solutions exhibit a generic design to facilitate the integration of new strategies for their main processing steps. In order to assess them, we conducted an extensive experimental study, including a thorough comparison with competitive techniques. As the results of this study reveal, our techniques outperform all competitors. Overall, they succeed in estimating the unknown density of a data stream.

Summary:
Eine stetig wachsende Zahl von Anwendungen sieht sich mit der Verarbeitung flüchtiger, in hohen Volumina eintreffender Daten konfrontiert. Aufgrund der Charakteristika dieser sogenannten Datenströme stellt sich deren Analyse mittels konventioneller Techniken als schwierig, wenn nicht gar unmöglich, heraus. Um Datenströme analysieren zu können, muss eine entsprechende Technik rigiden Verarbeitungsanforderungen gerecht werden, zu denen etwa der nur einmalig mögliche Zugriff auf jedes Element als auch die strikte Beschränkung des verfügbaren Speichers zählen. Aufgrund dieser Anforderungen ist die adäquate Verarbeitung und Analyse eines Datenstroms eine äußerst anspruchsvolle Aufgabe, welche die Entwicklung neuer Techniken erforderlich macht. Das Ziel dieser Arbeit ist die Adaption eines Bausteins vieler Mining- und Analyse-Ansätze, nämlich der Dichteschätzung, für den Datenstromkontext. Dichteschätzung selbst ist eine Fragestellung der mathematischen Statistik, die sich der Schätzung der Wahrscheinlichkeitsdichte eines reellwertigen Datensatzes widmet, um dessen unbekannte Verteilung und Charakteristika zu erfassen. Ein geeigneter Dichteschätzer kann überdies als Grundlage für weiterführende Analysen dienen. Der Wichtigkeit der Dichteschätzung wurde in den vergangenen Jahrzehnten mit der Entwicklung entsprechender Schätzverfahren Rechnung getragen. Insbesondere nichtparametrische Verfahren haben sich dabei als von besonderer Bedeutung herausgestellt, da sie, im Vergleich zu parametrischen Verfahren, nahezu keine Annahmen bezüglich der Daten machen. Kernel- und Wavelet-Dichteschätzer zählen zu den nichtparametrischen Verfahren. Beide sind sowohl theoretisch fundiert als auch praktisch bestätigt. Aufgrund ihrer Komplexität sind sie jedoch nicht ohne weiteres auf Datenströmen berechenbar. Da die Dichteschätzung aber eine wichtige Komponente bei der Analyse eines Datenstroms darstellt, widmet sich diese Arbeit speziell der Adaption von Kernel- und Wavelet-Dichteschätzern auf Datenströme unter Berücksichtigung der strikten Verarbeitungsanforderungen von Strömen. Die für Wavelet-Dichteschätzer entwickelte Lösung, genannt compressed-cumulative WDEs, basiert auf einer blockweisen Verarbeitung des Datenstroms, wobei jeder Datenblock mit einem separaten Schätzer assoziiert ist. Diese werden während der Verarbeitung des Datenstroms sukzessive vereinigt. Die für Kernel-Dichteschätzer entwickelte Lösung verwendet spezielle Bausteine, sogenannte Cluster Kernels, um einen Schätzer bei Bedarf zu konstruieren. Cluster Kernels fassen bereits verarbeitete Elemente mittels lokaler Statistiken zusammen, welche wiederum ein approximatives Resampling der Elemente ermöglichen. Beide Techniken sind generisch aufgebaut, um eine einfache Integration neuer Strategien für die wesentlichen Verarbeitungsschritte zu ermöglichen. Im Rahmen einer umfassenden experimentellen Studie wurden beide eingehend untersucht und insbesondere auch mit ähnlichen Techniken verglichen, welche jedoch allesamt unterlegen waren. In der Summe belegen die Ergebnisse dieser Studie die Fähigkeit der vorgestellten Techniken, die unbekannte Dichte eines Datenstroms adäquat zu schätzen.


* Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten