JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2014, Vol. 49 ›› Issue (08): 40-47.doi: 10.6040/j.issn.1671-9352.1.2014.114

Previous Articles     Next Articles

An incremental three-way decisions soft clustering algorithm

ZHANG Cong, YU Hong   

  1. Chongqing Key Lab of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
  • Received:2009-06-20 Revised:2014-07-01 Published:2014-09-24

Abstract: Most of the clustering algorithms reported assume a data set always does not change. However, it is often observed that the analyzed data set changes over time in many applications. To combat changes, we introduce a new incremental soft clustering approach based on three-way decisions theory. Firstly, the interval sets are used to represent a cluster, wherein the upper bound, the border, the lower bound of interval sets corresponding to positive region, boundary region, negative region generated by the three-way decisions respectively, and an initial clustering algorithm is proposed by using representative points. Secondly, to eliminate the influence of the processing order on final incremental clustering results, the incremental data is pre-clustered used the same way. To quickly search similar areas for incremental data, a searching tree based on the representative points is constructed, and the strategies of searching and updating are presented. Finally, the three-way decisions strategy is used to incremental clustering. The results of the experiments show the approach is effective to incremental clustering.

Key words: incremental clustering, soft clustering, searching tree, three-way decisions

CLC Number: 

  • TP181
[1] PHAM D T, DIMOV S S, NGUYEN C D. An incremental K-means algorithm[J]. Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, 2004, 218(7):783-795.
[2] ESTER M, KRIEGEL H P, SANDER J, et al. Incremental clustering for mining in a data warehousing environment[C]//Proceedings of the 24th VLDB Conference. Washington: IEEE Computer Society, 1998: 323-333.
[3] GOYAL N, GOYAL P, Venkatramaiah K, et al. An efficient density based incremental clustering algorithm in data warehousing environment[C]//2009 International Conference on Computer Engineering and Applications. Singapore: IACSIT Press, 2009: 482-486.
[4] 陈宁, 陈安, 周龙骧. 基于密度的增量式网格聚类算[J]. 软件学报, 2002, 13(1):1-7. CHENG Ning, CHENG An, ZHOU Longxiang. An incremental grid density-based clustering algorithm[J]. Journal of Software, 2002, 13(1):1-7.
[5] PATRA B K, VILLE O, LAUNONEN R, et al. Distance based incremental clustering for mining clusters of arbitrary shapes[C]//Pattern Recognition and Machine Intelligence. Berlin Heidelberg: Springer, 2013: 229-236.
[6] IBRAHIM R, AHMED N, YOUSRI N A, et al. Incremental mitosis: discovering clusters of arbitrary shapes and densities in dynamic data[C]//2012 11th International Conference on Machine Learning and Applications. Washington: IEEE Computer Society, 2012: 102-107.
[7] NING Huazhong, XU Wei, CHI Yun, et al. Incremental spectralclustering by efficiently updating the eigen-system[J]. Pattern Recognition, 2010, 43(1):113-127.
[8] GAD W K, KAMEL M S. Incremental clustering algorithm based on phrase-semantic similarity histogram[C]//2010 International Conference on Machine Learning and Cybernetics. Washington: IEEE Computer Society, 2010:2088-2093.
[9] GIL-GARCIA R, PONS-PORRATE A. Dynamic hierarchical algorithms for document clustering[J]. Pattern Recognition Letters, 2010, 31(6):469-477.
[10] PREZ-SUREA A, MARTINEZ-TRINIDAD J F, CARRASCO-OCHOA J A, et al. An algorithm based on density and compactness for dynamic overlapping Clustering[J]. Pattern Recognition, 2013, 46(11):3040-3055.
[11] YAO Yiyu. An outline of a theory of three-way decisions[C]//Rough Sets and Current Trends in Computing. Berlin Heidelberg: Springer, 2012: 1-17.
[12] ZHOU Bing, YAO Yiyu, LUO Jigang. Cost-sensitive three-way email spam filtering[J]. Journal of Intelligent Information Systems, 2013: 1-27.
[13] AZAM N, YAO Jingtao. Analyzing uncertainties of probabilistic rough set regions with game-theoretic rough sets[J]. International Journal of Approximate Reasoning, 2014, 55(1):142-155.
[14] LI Liudun, TIAN Rui, LIANG Decui. Three-way Decisions in Dynamic Decision-theoretic Rough Sets[C]//RoughSets and Knowledge Technology. Berlin Heidelberg: Springer, 2013: 291-301.
[15] YAO Yiyu, LINGRAS P, WANG Ruizhi, et al. Interval set cluster analysis: a re-formulation[C]//Rough Sets, FuzzySets, Data Mining and Granular Computing. BerlinHeidelberg: Springer, 2009: 398-405.
[16] YU Hong, WANG Ying. Three-way decisions method for overlapping clustering [C]//Rough Sets and Current Trends in Computing. Berlin Heidelberg: Springer, 2012: 277-286.
[17] 王爱平, 万国伟, 程志权,等. 支持在线学习的增量式极端随机森林分类器[J]. 软件学报, 2011, 22(9):2059-2074. WANG Aiping, WAN Guowei, CHENG Zhiquan, et al. Incremental learning extremely random forest classifier for online learning[J]. Journal of Software, 2011, 22(9):2059-2074.
[1] LIU Guo-tao, ZHANG Yan-ping, XU Chen-chu. Three-way decisions model based on the optimal center covering algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(3): 105-110.
[2] TIAN Hai-long, ZHU Yan-hui, LIANG Tao, MA Jin, LIU Jing. Research on identificating Chinese micro-blog opinion sentence based on three-way decisions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 58-65.
Full text



No Suggested Reading articles found!