Density-based clustering for real-time stream data

ABSTRACT

Existing data-stream clustering algorithms such as CluStream arebased on k-means. These clustering algorithms are incompetent tofind clusters of arbitrary shapes and cannot handle outliers. Further, they require the knowledge of k and user-specified time window. To address these issues, this paper proposes D-Stream, a framework for clustering stream data using adensity-based approach. The algorithm uses an online component which maps each input data record into a grid and an offline component which computes the grid density and clusters the grids based on the density. The algorithm adopts a density decaying technique to capture the dynamic changes of a data stream. Exploiting the intricate relationships between the decay factor, data density and cluster structure, our algorithm can efficiently and effectively generate and adjust the clusters in real time. Further, a theoretically sound technique is developed to detect and remove sporadic grids mapped to by outliers in order to dramatically improve the space and time efficiency of the system. The technique makes high-speed data stream clustering feasible without degrading the clustering quality. The experimental results show that our algorithm has superior quality and efficiency, can find clusters of arbitrary shapes, and can accurately recognize the evolving behaviors of real-time data streams.

REFERENCES

• 1: Charu C. Aggarwal , Jiawei Han , Jianyong Wang , Philip S. Yu, A framework for clustering evolving data streams, Proceedings of the 29th international conference on Very large data bases, p.81-92, September 09-12, 2003, Berlin, Germany
• 2: Brain Babcock , Mayur Datar , Rajeev Motwani , Liadan O'Callaghan, Maintaining variance and k-medians over data stream windows, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.234-243, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773176]
• 3: S. Bandyopadhyay, C. Giannella, U. Maulik, H. Kargupta, K. Liu, and S. Datta. Clustering distributed data streams in peer-to-peer environments. Information Sciences 176(14):1952--1985, 2006.
• 4: Daniel Barbará, Requirements for clustering data streams, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507519]
• 5: Jürgen Beringer , Eyke Hüllermeier, Online clustering of parallel data streams, Data & Knowledge Engineering, v.58 n.2, p.180-204, August 2006 [doi>10.1016/j.datak.2005.05.009]
• 6: Bi-Ru Dai , Jen-Wei Huang , Mi-Yen Yeh , Ming-Syan Chen, Adaptive Clustering for Multiple Evolving Streams, IEEE Transactions on Knowledge and Data Engineering, v.18 n.9, p.1166-1180, September 2006 [doi>10.1109/TKDE.2006.137]
• 7: Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Querying and mining data streams: you only get one look a tutorial, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564794]
• 8: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 9: Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003 [doi>10.1109/TKDE.2003.1198387]
• 10: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 11: Olfa Nasraoui , Carlos Rojas , Cesar Cardona, A framework for mining evolving trends in web data streams using dynamic learning and retrospective validation, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1488-1512, 14 July 2006 [doi>10.1016/j.comnet.2005.10.021]
• 12: Streaming-Data Algorithms for High-Quality Clustering, Proceedings of the 18th International Conference on Data Engineering, p.685, February 26-March 01, 2002
• 13: Sang-Hyun Oh , Jin-Suk Kang , Yung-Cheol Byun , Gyung-Leen Park , Sang-Yong Byun, Intrusion Detection based on Clustering a Data Stream, Proceedings of the Third ACIS Int'l Conference on Software Engineering Research, Management and Applications, p.220-227, August 11-13, 2005
• 14: Jörg Sander , Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications, Data Mining and Knowledge Discovery, v.2 n.2, p.169-194, June 1998 [doi>10.1023/A:1009745219419]
• 15: S. Subramaniam , T. Palpanas , D. Papadopoulos , V. Kalogeraki , D. Gunopulos, Online outlier detection in sensor data using non-parametric models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 16: Huanliang Sun , Ge Yu , Yubin Bao , Faxin Zhao , Daling Wang, CDS-Tree: An Effective Index for Clustering Arbitrary Shapes in Data Streams, Proceedings of the 15th International Workshop on Research Issues in Data Engineering: Stream Data Mining and Applications, p.81-88, April 03-04, 2005 [doi>10.1109/RIDE.2005.8]
• 17: Z. Wang, B. Wang, C. Zhou,, and X. Xu. Clustering Data streams on the Two-tier structure. Advanced Web Technologies and Applications pages 416--425, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
d-stream, density-based clustering, sporadic grids, stream data mining