UNIVERSITY OF CALIFORNIA Santa Barbara Statistical Mining in Data Streams A Dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Computer Science by Ankur Jain Committee in Charge: Prof. Chang, Chair Prof. Divyakant Agrawal Prof. Yuan-Fang Wang December 2006 UMI Number: 3245961 Copyright 2006 by Jain, Ankur All rights reserved.
UMI Microform 3245961 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.
Box 1346 Ann Arbor, MI 48106-1346 The Dissertation of Ankur Jain is approved: Prof. Divyakant Agrawal Prof. Yuan-Fang Wang Prof. Chang, Committee Chairperson October 2006 Statistical Mining in Data Streams Copyright c 2006 by Ankur Jain iii Acknowledgements There are a lot of people whom I want to thank for their direct and indirect contributions in making this dissertation possible.
First of all, I would like to thank my advisor, Prof. Chang, for the guidance, support, and honest criticisms he has provided throughout the course of this work. His energy and dedication has always been a great source of inspiration for me. I would also like to thank Prof.
Yuan-Fang Wang who helped me in my research work. I am fortunate to have learned so much from his overall attitude towards problem solving, and efforts to explain things clearly. I would like to thank my friends Badri, Irfan, Kapil, Nagender, Amit, Nisheeth, Vibhore, Sumit, Sukhi, Gayatri, Shalini, Sirisha and Kavitha for supporting me over all these years especially when it was most needed. I thank my colleagues Panda, Arun, Gang, Zhihua, Zoran, Yi, Raju and Kinsghy who where always there for me whenever I needed some help or advice.
Lastly, and most importantly, I wish to thank my parents, R. Jain and Abha Jain, and sisters, Richa and Prachi, for their patience, love and support. To them I dedicate this thesis. iv Curriculum Vitæ Ankur Jain Education Bachelor of Technology in Computer Science and Engineering, Institute of Technology, Banaras Hindu University, May 2002.
Doctor of Philosophy in Computer Science, University of California, Santa Barbara, December 2006. Professional Experience Research internship in the sensor and data mining group with the Mitsubishi Electric Research Labs., Cambridge, MA, Summer 2006. Teaching assistantship at UCSB for the following courses: Computational Geometry, Computer Programming in Java, Programming Methods, Fundamentals of Database Systems, UNIX & C programming. Publications “Adaptive nonlinear clustering for data streams,” Ankur Jain, Z.
of ACM CIKM’06, Intl Conf. on Information and Knowledge Manage- ment, Arlington, VA, USA. v “Efficient diagnostic and aggregate queries on sensor networks,” Ankur Jain, Edward Y. Chang & Yuan-Fang Wang.
UCSB Technical Report, June 2006. “Using stationary-dynamic camera assemblies for wide-area video surveillance and se- lective attention,” Ankur Jain, Dan Kopell, Kyle Kakligian & Yuan-Fang Wang. of IEEE CVPR’06, Conf. on Computer Vision and Pattern Recognition, New York.
“Adaptive stream resource management using Kalman Filters,” Ankur Jain, Edward Y. Chang & Yuan-Fang Wang. of the ACM SIGMOD’04, Intl. on Manage- ment of Data, Paris, France.
“Adaptive sampling for sensor networks,” Ankur Jain & Edward Y. of DMSN’04, Intl. workshop on Data Management in Sensor Networks (in conjunction with VLDB), Toronto, Canada. “Managing and Mining Video Sensor Data,” Edward Y.
Chang, Ankur Jain, Navneet Panda, Yuan-Fang Wang, Gang Wu & Yi Wu. UCSB Technical Report, 2004. Graduate Coursework Computer Networks, Design & Analysis of Algorithms, Programming Languages and Implementation, Theory of Computation, Computational Geometry, Internet Comput- ing and Web Technology, Bioinformatics, Advanced Computer Architecture, Advanced Algorithms for Multimedia Systems. vi Abstract Statistical Mining in Data Streams Ankur Jain Recent years have seen a steady rise of a new class of data management systems called Data Stream Management Systems (DSMS).
These systems manage rapid, high- volume data-streams with transient relations instead of static data with persistent rela- tions. Data streams are common to applications such as network traffic and transac- tion monitoring systems, click-stream processors, industrial process control, and sen- sor networks. A DSMS operates on these continuous and time-varying data streams to facilitate on-the-fly query answering, and to support data acquisition, monitoring and analysis. In this dissertation, we present statistical stream mining solutions for effective on- line processing of streaming data.
We focus research issues related to adaptive stream resource conservation and online mining in a DSMS. We have developed statistical linear and non-linear filtering techniques based on the Kalman Filter to capture tem- poral correlations in the streaming data. Such correlations help in stream resource conservation. We also propose techniques that capture spatial correlations between the streaming sources that further helps improving resource conservation and facilitates answering group-queries in an efficient manner.
vii In addition to resource management and query processing, a DSMS needs to ad- dress issues related to online stream mining. Once the data stream arrives at a central server, effective mining techniques are necessary for stream analysis, before the data can be discarded. Since a stream continuously evolves with time, stream mining tech- niques need to be adaptive and should operate under a given memory constraint. We propose adaptive clustering solutions that use the kernel trick to capture non-linear re- lations in the streaming data.
We also present OCODDS, a change-detection approach that can track evolutionary changes in the stream in both linear and non-linear set- tings. Finally, we present our techniques for effective acquisition and processing of data streams common to video sensor networks. viii Contents List of Figures xii List of Tables xv 1 Introduction 1 1.1 Data Stream Mining .2 Contributions toward statistical stream mining. 8 2 Kalman Filter in Stream Resource Mangement 16 2.1 Adaptive resource management for maximizing resource conservation 18 2.1 What is the Kalman Filter? .4 The Kalman Filter .5 The Dual Kalman Filter Model .6 Why Kalman Filter? .7 Modeling Kalman Filter for Data Streaming Applications .2 Adaptive resource management for maximizing query precision.
73 3 Bayesian reasoning for sensor resource management and diagnosis 75 3.2 Architecture and Model .1 Bayesian Network Construction .2 Query Plan Generation .3 Answering Diagnostic Queries .3 Query Answer Quality-Loss. 111 4 Adaptive clustering in Data Streams 121 4.3 Adaptive Non-linear Clustering Framework .4 Kernel Methods for Stream Clustering .1 Kernel Stream Segmentation (Tier-1) .2 Data Projection in LDS (Tier-2). 163 5 OCODDS: Online change-over detection framework for tracking evolu- tionary changes in streaming data 168 5.2 The OCODDS Framework .1 Finding the changeover location in a window .2 Conducting the hypothesis test .3 OCODDS using the kernel method .1 Comparative analysis with CUSUM .2 Effect of window and padding size .3 Effect of population variance ratio .4 Effect of location uncertainty (LU) .5 Effect of Noise. 200 x 6 Video sensor data acquisition and processing 209 6.1 Background and Contribution .2 On-line selective focus-of-attention.
236 7 Conclusions and future directions 241 Bibliography 246 A Represenations of means in LDS (Chapter 4) 269 B Derivations of formulae used in Chapter 5 271 xi List of Figures 1.1 A Data Stream Management System (DSMS) .1 The DKF model .2 Architecture of DKF model .3 Moving-object dataset (Example 1) .4 Number of updates received at the central server (Example 1) .5 Average error produced by different KF models (Example 1) .6 Electric power load dataset (Example 2) .7 Number of updates received at the central server (Example 2) .8 Average error produced by different KF models (Example 2) .9 Network monitoring dataset (Example 3) .10 Comparative results for KF smoothing against moving average approach 55 2.11 Performance of DKF on smoothed data with F = 10−7 (Example 3) .12 Performance of DKF for precision width δ = 10 (Example 3) .13 m on varying # of streaming sources .14 η on varying # of streaming sources .15 ERU on varying # of streaming sources .16 ERU on varying λi .17 ERU on varying Wi .1 Correlation model for NDBC data .2 Compact representation using BN .3 Sensor Network Architecture .4 Algorithm for computing candidate attributes set, Υ.5 Supplementary procedures for the algorithm shown in Figure 3.6 Resource conservation as a function of δmin and |Q| .7 Resource conservation as a function of δmin .8 Resource conservation with δmin = 0.9 Resource conservation with δmin = 0.90 for 5 different cost sets .12 Selectivity with δmin = 0.1 Linear separation using the kernel methods.2 Well-behaved data in the feature space (Network intrusion data for “ip- sweep” attack).3 Overview of 2-tier clustering architecture .4 Adaptive non-linear clustering framework .5 Reuters stream pattern.6 Network-intrusion stream pattern .7 MNIST stream pattern .8 Cumulative Cluster Purity (u = 10).9 Fraction of elements in significant clusters (u = 10).10 Effect of dimensionality. CUSUM - Detection accuracy (LU = 1, m = 1, n = 30). CUSUM - Processing time (LU = 1, m = 1, n = 30).3 Effect of window length (LU = 1, m = 1, Nrms = 0). Accuracy with LU = 1, m = 1, Nrms = 0, n = 50.5 Effect of padding length (LU = 1, n = 50, Nrms = 0 ).6 Effect of PVR on detection bias (LU = 1, m = 1, n = 50, varying PVR).7 Effect of PVR on detection bias (LU = 1, m = 1, n = 50, varying R).8 Effect population variance on detection accuracy (LU = 1, m = 1, n = 50).9 Effect of LU (m = 1, n = 50).10 Effect of RMS noise (LU = 1, m = 1, n = 50, varying RMS noise).11 Effect of RMS noise (LU = 1, m = 1, n = 50, varying R).1 Computing the correct pan DOF (a) if optical and pan centers are col- located, and (b) if they are not.2 Error in centering assuming computational collocation of the optical center on the rotation axis.3 Selective focus-of-attention as a visual servo problem.4 Comparison of calibration accuracy as a function of experimental setup (using a CCD of 300 × 300 pixels).5 Relation between requested and realized angle of rotation for Sony PTZ camera.6 Mean projection error as a function of pan angle.7 Mean projection error as a function of depth for our model and naı̈ve models.8 Centering errors under various experimental conditions .9 Focus-of-attention experiments using real video .10 Focus-of-attention experiments using real video.
240 xiv List of Tables 1.1 Data stream applications.2 Popular Data Stream Management Systems (DSMS).1 Summary of existing solutions and advantages of using the Kalman Filter 26 2.2 Symbols and their meanings .1 Relative Costs of Sensors for Real Datasets .1 Comparison of calibration accuracy. For [50], 51% simulation runs failed to converge. If the simulation did converge, 85 iterations were needed in average. 230 xv Chapter 1 Introduction A data stream is simply a continuous sequence of data elements (x 1 , x2 , x3, · · · , xi , · · · ) that arrive in on-line fashion, where each element xi could be a scalar or a vector entity.
Babcock et al., presented the data stream model with the following salient features [18]: • The data elements arrive on-line. • The system has no control over the order in which the data elements arrive. • Once an element has been seen or processed, it cannot be easily retrieved or seen again unless it is explicitly stored in the memory. Data streams are common to a variety of data-intensive applications, some of which we have summarized in Table 1.
In all these applications, it is not feasible to operate using a traditional database management system (DBMS), since it assumes persistent data relations and predominately focuses on query optimization, data access (indexing) and privacy. On the other hand, a data stream management system (DSMS), must 1 Chapter 1. Introduction consider critical factors such as noise from the data sources, management of the system resources (both at the central and remote locations), and evolutionary changes in the data trends.