Stream data clustering based on grid density and attraction

ABSTRACT

Clustering real-time stream data is an important and challenging problem. Existing algorithms such as CluStream are based on the k-means algorithm. These clustering algorithms have difficulties finding clusters of arbitrary shapes and handling outliers. Further, they require the knowledge of k and user-specified time window. To address these issues, this article proposes D-Stream, a framework for clustering stream data using a density-based approach.

Our algorithm uses an online component that maps each input data record into a grid and an offline component that 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 and a attraction-based mechanism to accurately generate cluster boundaries.

Exploiting the intricate relationships among the decay factor, attraction, 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 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: Bandyopadhyay, S., Giannella, C., Maulik, U., Kargupta, H., Liu, K., and Datta, S. 2006. Clustering distributed data streams in peer-to-peer environments. Inform. Sci. 176, 14, 1952--1985.
• 3: Daniel Barbará, Requirements for clustering data streams, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507519]
• 4: 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]
• 5: Chen, Y., Dong, G., Han, J., Pei, J., Wah, B. W., and Wang, J. 2002. OLAPing stream data: Is it feasible? In Proceedings of the Workshop on Research Issues in Data Mining and Knowledge Discovery, ACM SIGMOD. 53--58.
• 6: Yixin Chen , Li Tu, Density-based clustering for real-time stream data, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281210]
• 7: 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]
• 8: Giannella, C., Han, J., Pei, J., Yan, X., and Yu, P. S. 2003. Mining frequent patterns in data streams at multiple-time granularities. Next Gen. Data Min., 191--212.
• 9: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
• 10: 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]
• 11: 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]
• 12: 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
• 13: Daesu Lee , Wonsuk Lee, Finding Maximal Frequent Itemsets over Online Data Streams Adaptively, Proceedings of the Fifth IEEE International Conference on Data Mining, p.266-273, November 27-30, 2005 [doi>10.1109/ICDM.2005.68]
• 14: 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]
• 15: Streaming-Data Algorithms for High-Quality Clustering, Proceedings of the 18th International Conference on Data Engineering, p.685, February 26-March 01, 2002
• 16: 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
• 17: 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]
• 18: 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
• 19: 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]
• 20: Haixun Wang , Jian Yin , Jian Pei , Philip S. Yu , Jeffrey Xu Yu, Suppressing model overfitting in mining concept-drifting data streams, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150496]
• 21: Wang, Z., Wang, B., Zhou, C., and Xu, X. 2004. Clustering data streams on the two-tier structure. Advanced Web Technologies and Applications, 416--425.
• 22: Shi Zhong, Efficient streaming text clustering, Neural Networks, v.18 n.5-6, p.790-798, June 2005 [doi>10.1016/j.neunet.2005.06.008]

INDEX TERMS

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

General Terms:
Algorithms, Management

Keywords:
Stream data, clustering, data mining, density-based algorithms