Density Estimation over Data Streams

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.