Soft Subspace Clustering Algorithm for Streaming Data
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [40]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    A key challenge to most conventional clustering algorithms in handling many real life problems is that data points in different clusters are often correlated with different subsets of features. To address this problem, subspace clustering has attracted increasing attention in recent years. However, the existing subspace clustering methods cannot be effectively applied to large-scale high dimensional data and data streams. In this study, the scalable clustering technique to subspace clustering is extend to form soft subspace clustering for streaming data. An entropy-weighting streaming subspace clustering algorithm, EWSSC is proposed. This method leverages on the effectiveness of fuzzy scalable clustering method for streaming data by revealing the important local subspace characteristics of high dimensional data. Substantial experimental results on both artificial and real-world datasets demonstrate that EWSSC is generally effective in clustering high dimensional streaming data.

    Reference
    [1] Jain AK. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 2010,31(8):651-666.[doi: 10.1016/j.patrec.2009. 09.011]
    [2] Sun JG, Liu J, Zhao LY. Clustering algorithms research. Run Jian Xue Bao/Journal of Software, 2008,19(1):48-61 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/19/48.htm[doi: 10.3724/SP.J.1001.2008.00048]
    [3] Zhu L, Chung FL, Wang S. Generalized fuzzy C-means clustering algorithm with improved fuzzy partitions. IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009,39(3):578-591.[doi: 10.1109/TSMCB.2008.2004818]
    [4] Zhang M, Yu J. Fuzzy partitional clustering algorithms. Run Jian Xue Bao/Journal of Software, 2004,15(6):858-868 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/15/858.htm
    [5] Muller E, Gunnemann S, Assent I, Seidl T. Evaluating clustering in subspace projections of high dimensional data. In: Proc. of the VLDB Endowment. 2009. 1270-1281.
    [6] Kriegel HP, Kröger P, Zimek A. Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering. ACM Trans. on Knowledge Discovery from Data, 2009,3(1):1-58.[doi: 10.1145/1497577.1497578]
    [7] Parsons L, Haque E, Liu H. Subspace clustering for high dimensional data: A review. ACM SIGKDD Explorations Newsletter, 2004,6(1):90-105.[doi: 10.1145/1007730.1007731]
    [8] Wang J, Wang ST, Deng ZH. A novel text clustering algorithm based on feature weighting distance and soft subspace learning. Chinese Journal of Computers, 2012,35(8):1655-1665 (in Chinese with English abstract).
    [9] Deng ZH, Choi KS, Chung FL, Wang S. Enhanced soft subspace clustering integrating within-cluster and between-cluster information. Pattern Recognition, 2010,43(3):767-781.[doi: 10.1016/j.patcog.2009.09.010]
    [10] Chen LF, Guo GD, Jiang QS. Adaptive algorithm for soft subspace clustering. Run Jian Xue Bao/Journal of Software, 2010,21(10): 2513-2523 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3763.htm[doi: 10.3724/SP.J.1001.2010.03763]
    [11] Gan G, Wu J. A convergence theorem for the fuzzy subspace clustering (FSC) algorithm. Pattern Recognition, 2008,41(6): 1939-1947.[doi: 10.1016/j.patcog.2007.11.011]
    [12] Jing L, Ng MK, Huang JZ. An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data. IEEE Trans. on Knowledge and Data Engineering, 2007,19(8):1026-1041.[doi: 10.1109/TKDE.2007.1048]
    [13] Jing L, Ng MK, Xu J, Huang JZ. Subspace clustering of text documents with feature weighting k-means algorithm. Advances in Knowledge Discovery and Data Mining, 2005,1(1):802-812.[doi: 10.1007/11430919_94]
    [14] Gan G, Wu J, Yang Z. A fuzzy subspace algorithm for clustering high dimensional data. Advanced Data Mining and Applications, 2006,1(1):271-278.[doi: 10.1007/11811305_30]
    [15] Guha S, Meyerson A, Mishra N, Motwani R, O''callaghan L. Clustering data streams: Theory and practice. IEEE Trans. on Knowledge and Data Engineering, 2003,15(3):515-528.[doi: 10.1109/TKDE.2003.1198387]
    [16] Zhong S. Efficient streaming text clustering. Neural Networks, 2005,18(5-6):790-798.[doi: 10.1016/j.neunet.2005.06.008]
    [17] Hall LO, Goldgof DB. Convergence of the single-pass and online fuzzy C-means algorithms. IEEE Trans. on Fuzzy Systems, 2011, 19(4):792-794.[doi: 10.1109/TFUZZ.2011.2143418]
    [18] Hore P, Hall LO, Goldgof DB. Creating streaming iterative soft clustering algorithms. In: Proc. of the Annual Meeting of the North American Fuzzy Information. 2007. 484-488.[doi: 10.1109/NAFIPS.2007.383888]
    [19] Hore P, Hall LO, Goldgof DB. Single pass fuzzy C-means. In: Proc. of the IEEE Int''l Fuzzy Systems Conf. 2007. 1-7.[doi: 10.1109/FUZZY.2007.4295372]
    [20] Bradley PS, Fayyad U, Reina C. Scaling clustering algorithms to large databases. In: Proc. of the Knowledge Discovery and Data Mining. 1998. 9-15.
    [21] Farnstrom F, Lewis J, Elkan C. Scalability for clustering algorithms revisited. ACM SIGKDD Explorations Newsletter, 2000,2(1): 51-57.[doi: 10.1145/360402.360419]
    [22] Domeniconi C, Gunopulos D, Ma S, Yan B, Al-Razgan M, Papadopoulos D. Locally adaptive metrics for clustering high dimensional data. Data Mining and Knowledge Discovery, 2007,14(1):63-97.[doi: 10.1007/s10618-006-0060-8]
    [23] Chan EY, Ching WK, Ng MK, Huang JZ. An optimization algorithm for clustering using weighted dissimilarity measures. Pattern Recognition, 2004,37(5):943-952.[doi: 10.1016/j.patcog.2003.11.003]
    [24] Zhong S. Efficient online spherical k-means clustering. In: Proc. of the IEEE Int''l Joint Conf. on Neural Networks. 2005. 3180-3185.[doi: 10.1109/IJCNN.2005.1556436]
    [25] Banerjee A, Ghosh J. Frequency-Sensitive competitive learning for scalable balanced clustering on high-dimensional hyperspheres. IEEE Trans. on Neural Networks, 2004,15(3):702-719.[doi: 10.1109/TNN.2004.824416]
    [26] Aggarwal CC, Han J, Wang J, Yu PS. A framework for clustering evolving data streams. In: Proc. of the Int''l Conf. on Very Large Data Bases. 2003. 81-92.[doi: 10.1016/B978-012722442-8/50016-1]
    [27] Zhang YJ, Liu ZQ. Self-Splitting competitive learning: A new on-line clustering paradigm. IEEE Trans. on Neural Networks, 2002, 13(2):369-380.[doi: 10.1109/72.991422]
    [28] Xu L, Krzyzak A, Oja E. Rival penalized competitive learning for clustering analysis, RBF net, and curve detection. IEEE Trans. on Neural Networks, 1993,4(4):636-649.[doi: 10.1109/72.238318]
    [29] Wei L M, Xie WX. Rival checked fuzzy C-means algorithm. Acta Electronica Sinica, 2000,28(7):63-66 (in Chinese with English abstract).
    [30] Arthur D, Vassilvitskii S. K-Means : The advantages of careful seeding. In: Proc. of the 18th Annual ACM-SIAM Symp. on Discrete Algorithms. 2007. 1027-1035.
    [31] Cheng TW, Goldgof DB, Hall LO. Fast fuzzy clustering. Fuzzy Sets and Systems, 1998,93(1):49-56.[doi: 10.1016/S0165-0114(96) 00232-1]
    [32] Zhong S, Ghosh J. A unified framework for model-based clustering. Journal of Machine Learning Research, 2003,4(1):1001-1037.
    [33] Dhillon IS, Modha DS. Concept decompositions for large sparse text data using clustering. Machine Learning, 2001,42(1):143-175.[doi: 10.1023/A:1007612920971]
    [34] Bezdek JC. Pattern Recognition with Fuzzy Objective Function Algorithms. New York: Plenum Press, 1981.
    [35] Nguyen N, Caruana R. Consensus clusterings. In: Proc. of the Int''l Conf. on Data Mining. 2007. 607-612.[doi: 10.1109/ICDM. 2007.73]
    [36] Strehl A, Ghosh J. Cluster ensembles—A knowledge reuse framework for combining multiple partitions. Journal of Machine Learning Research, 2003,3(1):583-617.
    [37] Rand WM. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 1971,66(1): 846-850.[doi: 10.2307/2284239]
    [38] Iam-On N, Boongoen T, Garrett S, Price C. A link-based approach to the cluster ensemble problem. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2011,33(9):2396-2409.[doi: 10.1109/TPAMI.2011.84]
    [39] 20-Newsgroups corpus. 1999. http://kdd.ics.uci.edu/databases/20newsgroups/20newsgroups.html
    [40] Mccallum AK. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. 1996. http://www.cs. cmu.edu/mccallum/bow
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

朱林,雷景生,毕忠勤,杨杰.一种基于数据流的软子空间聚类算法.软件学报,2013,24(11):2610-2627

Copy
Share
Article Metrics
  • Abstract:6050
  • PDF: 7781
  • HTML: 0
  • Cited by: 0
History
  • Received:March 18,2013
  • Revised:August 02,2013
  • Online: November 01,2013
You are the first2043738Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063