A Single Pass Trellis-Based Algorithm for Clustering Evolving Data Streams

详细信息    查看全文

• 作者：Simon Malinowski (18)
  Ricardo Morla (18)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7448
• 期：1
• 页码：327-339
• 全文大小：259KB
• 参考文献：1. O鈥機allaghan, L., Mishra, N., Meyerson, A., Guha, S., Motwani, R.: Streaming-data algorithms for high-quality clustering. In: Proc. of Intl. Conf. on Data Engineering, pp. 685鈥?94 (2002)
  2. Aggarwal, C.C., Han, J., Wang, J., Yu, P.S.: A framework for clustering evolving data streams. In: VLDB, pp. 81鈥?2 (2003)
  3. Guha, S., Meyerson, A., Mishra, N., Motwani, R., O鈥機allaghan, L.: Clustering data streams: Theory and practice. IEEE Transactions on Knowledge and Data Engineering聽15(3), 515鈥?28 (2003) ss="external" href="http://dx.doi.org/10.1109/TKDE.2003.1198387">CrossRef
  4. Aggarwal, C.C., Han, J., Wang, J., Yu, P.S.: A framework for projected clustering of high dimensional data streams. In: Proc. of the Intl. Conf. on Very Large Data Bases, pp. 852鈥?63 (2004)
  5. Cao, F., Ester, M., Qian, W., Zhou, A.: Density-based clustering over an evolving data stream with noise. In: 2006 SIAM Conference on Data Mining, pp. 328鈥?39 (2006)
  6. Chen, Y., Tu, L.: Density-based clustering for real-time stream data. In: Proc. of ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, pp. 133鈥?42 (2007)
  7. Kranen, P., Assent, I., Baldauf, C., Seidl, T.: The ClusTree: indexing micro-clusters for anytime stream mining. In: Knowledge and Information Systems, pp. 1鈥?4 (2010)
  8. Forestiero, A., Pizzuti, C., Spezzano, G.: A single pass algorithm for clustering evolving data streams based on swarm intelligence. In: Data Mining and Knowledge Discovery, pp. 1鈥?6 (2011)
  9. Hassani, M., Kranen, P., Seidl, T.: Precise anytime clustering of noisy sensor data with logarithmic complexity. In: Proc. of International Workshop on Knowledge Discovery from Sensor Data, pp. 52鈥?0 (2011)
  10. Gu, G., Perdisci, R., Zhang, J., Lee, W.: Botminer: clustering analysis of network traffic for protocol- and structure-independent botnet detection. In: Proceedings of the 17th Conference on Security Symposium, pp. 139鈥?54 (2008)
  11. Bifet, A., Holmes, G., Pfahringer, B., Kranen, P., Kremer, H., Jansen, T., Seidl, T.: MOA: Massive Online Analysis, a Framework for Stream Classification and Clustering. Journal of Machine Learning Research, 3鈥?6 (2011)
  12. Ester, M., Kriegel, H.-P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proc. of ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, pp. 226鈥?31 (1996)
  13. Davies, D.L., Bouldin, D.W.: A cluster separation measure. IEEE Trans. on Pattern Analysis and Machine Intelligence聽PAMI-1(2), 224鈥?27 (1979) ss="external" href="http://dx.doi.org/10.1109/TPAMI.1979.4766909">CrossRef
  14. Viterbi, A.: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. on Information Theory聽13(2), 260鈥?69 (1967) ss="external" href="http://dx.doi.org/10.1109/TIT.1967.1054010">CrossRef
  15. Frank, A., Asuncion, A.: UCI machine learning repository (2010), ss="a-plus-plus" href="http://archive.ics.uci.edu/ml"> <span class="a-plus-plus emphasis fontcategory-non-proportional">http://archive.ics.uci.edu/ml
  
• 作者单位：Simon Malinowski (18)
  Ricardo Morla (18)
  
  18. INESC-TEC, Faculty of Engineering, University of Porto, Portugal
  

文摘

The main paradigm for clustering evolving data streams in the last 10 years has been to divide the clustering process into an online phase that computes and stores detailed statistics about the data in micro-clusters and an offline phase that queries micro-cluster statistics and returns desired clustering structures. The argument for two-phase algorithms is that they support evolving data streams and temporal multi-scale analysis, which single pass algorithms do not. In this paper, we describe a single pass fully online trellis-based algorithm, named ClusTrel, designed for centroid-based clustering that supports evolving data streams and generates clustering structures right after a new point is processed. The performance of ClusTrel is assessed and compared to state of the art algorithms for clustering of data streams showing similar performance with smaller memory footprint.