[1]施 虹,刘 强,王平心,等.基于三支决策的谱聚类算法研究[J].南京师范大学学报(自然科学版),2018,41(03):6.[doi:10.3969/j.issn.1001-4616.2018.03.002]
 Shi Hong,Liu Qiang,Wang Pingxin,et al.Research on Spectral Clustering Algorithm Based on Three-way Decision[J].Journal of Nanjing Normal University(Natural Science Edition),2018,41(03):6.[doi:10.3969/j.issn.1001-4616.2018.03.002]
点击复制

基于三支决策的谱聚类算法研究()
分享到:

《南京师范大学学报》(自然科学版)[ISSN:1001-4616/CN:32-1239/N]

卷:
第41卷
期数:
2018年03期
页码:
6
栏目:
·人工智能算法与应用专栏·
出版日期:
2018-09-30

文章信息/Info

Title:
Research on Spectral Clustering Algorithm Based on Three-way Decision
文章编号:
1001-4616(2018)03-0006-08
作者:
施 虹1刘 强1王平心12杨习贝1
(1.江苏科技大学计算机学院,江苏 镇江 212003)(2.河北师范大学数学与信息科学学院,河北 石家庄 050024)
Author(s):
Shi Hong1Liu Qiang1Wang Pingxin12Yang Xibei1
(1.School of Computer,Jiangsu University of Science and Technology,Zhenjiang 212003,China)(2.College of Mathematics and Information Science,Hebei Normal University,Shijiazhuang 050024,China)
关键词:
谱聚类三支决策三支聚类三支谱聚类
Keywords:
spectral clusteringthree-way decisionthree-way clusteringthree-way spectral clustering
分类号:
TP391
DOI:
10.3969/j.issn.1001-4616.2018.03.002
文献标志码:
A
摘要:
硬聚类要求聚类的结果必须具有清晰的边界,即每个对象要么属于一个类,要么不属于一个类. 然而,将某些不确定的对象强制分配到某个类中往往容易带来较高的决策风险. 三支聚类将确定的元素放入核心域中,将不确定的元素放入边界域中延迟决策,可以有效地降低决策风险. 本文将三支决策理论与传统的谱聚类算法相结合给出了三支谱聚类的聚类算法. 该方法通过修改谱聚类算法的聚类过程并获得任一类簇的上界. 然后通过扰动分析从该类簇的上界分离出该类簇的核心域,同时上界与核心域的差值认为是该类簇的边界域. 在UCI数据集上的实验结果显示,该方法能有效提高聚类结果的ACC、AS、ARI值,并且降低DBI值.
Abstract:
Hard clustering based on the assumption that a cluster must be represented by a set with crisp boundary. However,assigning uncertain points into a cluster will increase decision risk. Three-way clustering assigns the identified elements into the core region and the uncertain elements into the fringe region to reduce decision risk. In this paper,we present a new three-way spectral clustering by combining three-way decision and spectral clustering. In the proposed algorithm,we revise the process of spectral clustering and obtain an upper bound of each cluster. Perturbation analysis is applied to separate the core region from upper bound and the differences between upper bound and core region are regarded as the fringe region of specific cluster. The results on UCI data sets show that such strategy is effective in reducing the value of DBI and improving the values of ACC and AS.

参考文献/References:

[1] ELALAMI M E. Supporting image retrieval framework with rule base system[J]. Knowledge-based systems,2011,24(2):331-340.
[2]MARTíN G J D,PALOMARES A,BALAGUER B E,et al. Studying the feasibility of a recommender in a citizen web portal based on user modeling and clustering algorithms[J]. Expert systems with applications,2006,30(2):299-312.
[3]KALYANI S,SWARUP K S. Particle swarm optimization based ans clustering approach for security assessment in power systems[J]. Expert systems with applications,2011,38(9):10839-10846.
[4]SHI J,LUO Z. Nonlinear dimensionality reduction of gene expression data for visualization and clustering analysis of cancer tissue samples[J]. Computers in biology & medicine,2010,40(8):723.
[5]SEBISKVERADZE D,VRABIE V,GOBINET C,et al. Automation of an algorithm based on fuzzy clustering for analyzing tumoral heterogeneity in human skin carcinoma tissue sections[J]. Technical methods and pathology,2011,91(5):799-811.
[6]XU R. Survey of clustering algorithms[J]. IEEE transactions on neural networks,2005,16(3):645-678.
[7]孙吉贵,刘杰,赵连宇. 聚类算法研究[J]. 软件学报,2008,19(1):48-61.
[8]KAUFMAN L,ROUSSEEUW P J. Finding groups in data:an introduction to cluster analysis[M]. New Jersey:John Wiley & Sons Inc,1990.
[9]MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. California:University of California Press,1967.
[10]LUXBURG U V. A tutorial on spectral clustering[J]. Statistics & computing,2007,17(4):395-416.
[11]蔡晓妍,戴冠中,杨黎斌. 谱聚类算法综述[J]. 计算机科学,2008,35(7):14-18.
[12]CAI Y,JIAO Y Y,ZHUGE W Z,et al. Partial multi-view spectral clustering[J]. Neurocomputing,2018,311:316-324.
[13]MALIK J,BELONGIE S,LEUNG T,et al. Contour and texture analysis for image segmentation[J]. International journal of computer vision,2001,43(1):7-27.
[14]WEISS Y. Segmentation using eigenvectors:a unifying view[C]//International Conference on Computer Vision. United States:IEEE Computer Society,1999.
[15]SHI J,MALIK J. Normalized cuts and image segmentation[J]. IEEE transactions on pattern analysis and machine intelligence,2000.
[16]李丽红,李言,刘保相. 三支决策中不承诺决策的转化代价与风险控制[J]. 计算机科学,2016,43(1):77-80.
[17]FAHAD A,ALSHATRI N,TARI Z,et al. A survey of clustering algorithms for big data:taxonomy and empirical analysis[J]. IEEE transactions on emerging topics in computing,2014,2(3):267-279.
[18]ROUSSEEUW P J. Silhouettes:a graphical aid to the interpretation and validation of cluster analysis[J]. Journal of computational & applied mathematics,1987,20(20):53-65.
[19]BEZDEK J C,PAL N R. Some new indexes of cluster validity[J]. IEEE transactions on systems man & cybernetics society,1998,28(3):301-315.
[20]MAULIK U,BANDYOPADHYAY S. Performance evaluation of some clustering algorithms and validity indices[J]. IEEE transactions on pattern analysis & machine intelligence,2002,24(12):1650-1654.
[21]NG A Y,JORDAN M I,WEISS Y. On spectral clustering:analysis and an algorithm[J]. Proc Nips,2001,14:849-856.
[22]YAO Y Y. The superiority of three-way decisions in probabilistic rough set models[J]. Information sciences,2011,181(6):1080-1096.
[23]YAO Y Y. An outline of a theory of three-way decisions[C]//International Conference on Rough Sets and Current Trends in Computing. Berlin,Heidelberg:Springer,2012.
[24]GAO C,YAO Y Y. Actionable strategies in three-way decisions[J]. Knowledge-based systems,2017,133:183-199.
[25]李金海,邓硕. 概念格与三支决策及其研究展望[J]. 西北大学学报(自然科学版),2017,47(03):321-329.
[26]YU H,ZHANG C,WANG G Y. A tree-based incremental overlapping clustering method using the three-way decision theory[J]. Knowledge-based systems,2016,91(C):189-203.
[27]YU H,JIAO P,YAO Y Y,et al. Detecting and refining overlapping regions in complex networks with three-way decisions[J]. Information sciences,2016,373:21-41.
[28]YU H. A framework of three-way cluster analysis[C]//International Joint Conference on Rough Sets. Cham:Springer,2017.
[29]YU H,WANG X,WANG G,et al. An active three-way clustering method via low-rank matrices for multi-view data[J/OL]. Information sciences,2018. https://doi.org/10.1016/j.ins.2018.03.009.
[30]WANG P X,YAO Y Y. CE3:A three-way clustering method based on mathematical morphology[J]. Knowledge-based systems,2018,155:54-65.
[31]王平心,刘强,杨习贝,等. 基于动态邻域的三支聚类分析[J]. 计算机科学,2018,45(1):62-66.
[32]BLAKE C L,MERZ C J. UCI machine learning repository[J/OL]. Html,2005. http://www.ics.uci.edu/mlearn/MLRepository.

相似文献/References:

[1]许小龙,王士同.基于局部和全局信息的正则化迭代聚类[J].南京师范大学学报(自然科学版),2014,37(03):21.
 Xu Xiaolong,Wang Shitong.Iterative Clustering with Local and Global Regularization[J].Journal of Nanjing Normal University(Natural Science Edition),2014,37(03):21.

备注/Memo

备注/Memo:
收稿日期:2018-04-16.
基金项目:国家自然科学基金(61503160、61572242).
通讯联系人:王平心,博士,副教授,研究方向:粗糙集、粒计算. E-mail:pingxin_wang@hotmail.com
更新日期/Last Update: 2018-11-19