一种基于数据流的软子空间聚类算法
作者:
基金项目:

国家自然科学基金(61273258,61272437,61073189);上海市自然科学基金(13ZR1417500);上海市教育委员会科研创新项目(14YZ131)


Soft Subspace Clustering Algorithm for Streaming Data
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [40]
  • |
  • 相似文献
  • | | |
  • 文章评论
    摘要:

    针对高维数据的聚类研究表明,样本在不同数据簇往往与某些特定的数据特征子集相对应.因此,子空间聚类技术越来越受到关注.然而,现有的软子空间聚类算法都是基于批处理技术的聚类算法,不能很好地应用于高维数据流或大规模数据的聚类研究中.为此,利用模糊可扩展聚类框架,与熵加权软子空间聚类算法相结合,提出了一种有效的熵加权流数据软子空间聚类算法——EWSSC(entropy-weighting streaming subspace clustering).该算法不仅保留了传统软子空间聚类算法的特性,而且利用了模糊可扩展聚类策略,将软子空间聚类算法应用于流数据的聚类分析中.实验结果表明,EWSSC 算法对于高维数据流可以得到与批处理软子空间聚类方法近似一致的实验结果.

    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.

    参考文献
    [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
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2013-03-18
  • 最后修改日期:2013-08-02
  • 在线发布日期: 2013-11-01
文章二维码
您是第19728283位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号