No Access

DETECTION AND CLASSIFICATION OF CHANGES IN EVOLVING DATA STREAMS

MOHAMED MEDHAT GABER

School of Information Technologies, University of Sydney, NSW 2006, Australia

Search for more papers by this author

and

PHILIP S. YU

IBM Thomas J. Watson Research Center, 19, Skyline Drive, Hawthorne, NY 10532, USA

Search for more papers by this author

https://doi.org/10.1142/S0219622006002179Cited by:28 (Source: Crossref)

Abstract

Data stream mining has attracted considerable attention over the past few years owing to the significance of its applications. Streaming data is often evolving over time. Capturing changes could be used for detecting an event or a phenomenon in various applications. Weather conditions, economical changes, astronomical, and scientific phenomena are among a wide range of applications. Because of the high volume and speed of data streams, it is computationally hard to capture these changes from raw data in real-time. In this paper, we propose a novel algorithm that we term as STREAM-DETECT to capture these changes in data stream distribution and/or domain using clustering result deviation. STREAM-DETECT is followed by a process of offline classification CHANGE-CLASS. This classification is concerned with the association of the history of change characteristics with the observed event or phenomenon. Experimental results show the efficiency of the proposed framework in both detecting the changes and classification accuracy.

Keywords:

References

S. Muthukrishnan , Data streams: Algorithms and applications , Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms ( 2003 ) . Google Scholar
H. Wang , J. Pei and P. S. Yu , Online mining of data Streams: Problems, applications and progress (tutorial) , 21st Int. Conf. Data Engineering (ICDE) . Google Scholar
M. M. Gaber, A. Zaslavsky and S. Krishnaswamy, ACM SIGMOD Record 34(1), (2005), DOI: 10.1145/1083784.1083789. Google Scholar
S. Ben-David , J. Gehrke and D. Kifer , Detecting change in data streams , Proceedings of VLDB ( 2004 ) . Google Scholar
M. Tubaishat and S. Madria, IEEE Potentials 22(2), 20 (2003), DOI: 10.1109/MP.2003.1197877. Crossref, Web of Science, Google Scholar
R. Bhargava , H. Kargupta and M. Powers , Energy consumption in data analysis for on-board and distributed applications , ICML'03 Workshop on Machine Learning Technologies for Autonomous Space Applications ( 2003 ) . Google Scholar
C. Aggarwal , An intuitive framework for understanding changes in evolving data streams , Proceedings of the ICDE Conference ( 2002 ) . Google Scholar
C. Aggarwal , A framework for diagnosing changes in evolving data streams , Proceedings of the ACM SIGMOD Conference ( 2003 ) , DOI: 10.1145/872757.872826 . Google Scholar
O. Nasraouiet al., TECNO-STREAMS: Tracking evolving clusters in noisy data streams with a scalable immune system learning model, Proc. Third IEEE Int. Conf. Data Mining (ICDM'03) (2003) pp. 235–242. Google Scholar
W. Fan , StreamMiner: A Classifier Ensemble-based Engine to Mine Concept Drifting Data Streams , VLDB'2004 . Google Scholar
W. Fan, Systematic data selection to mine concept-drifting data streams, KDD (2004) pp. 128–137, DOI: 10.1145/1014052.1014069. Google Scholar
W. Fan, Y. Huang and P. S. Yu, Decision tree evolution using limited number of labeled data items from drifting data streams, ICDM (2004) pp. 379–382, DOI: 10.1109/ICDM.2004.10026. Google Scholar
G. Hulten , L. Spencer and P. Domingos , Mining time-changing data streams , Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ( 2001 ) , DOI: 10.1145/502512.502529 . Google Scholar
R. Klinkenberg, Incremental Learning Systems Capable of Dealing with Concept Drift 8(3), 281 (2004). Google Scholar
H. Wang et al. , Mining Concept-Drifting Data Streams using Ensemble Classifiers , 9th ACM Int. Conf. Knowledge Discovery and Data Mining (SIGKDD) , DOI: 10.1145/956750.956778 . Google Scholar
M. M. Gaber , S. Krishnaswamy and A. Zaslavsky , Advanced Methods of Knowledge Discovery from Complex Data , eds. S. Badhyopadhyay et al. ( Springer Verlag , 2005 ) . Google Scholar