|Table of Contents|

Research on Spectral Clustering Algorithm Based on Three-way Decision(PDF)

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

Issue:
2018年03期
Page:
6-
Research Field:
·人工智能算法与应用专栏·
Publishing date:

Info

Title:
Research on Spectral Clustering Algorithm Based on Three-way Decision
Author(s):
Shi Hong1; Liu Qiang1; Wang Pingxin1; 2; Yang 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 clustering; three-way decision; three-way clustering; three-way spectral clustering
PACS:
TP391
DOI:
10.3969/j.issn.1001-4616.2018.03.002
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.

Memo

Memo:
-
Last Update: 2018-11-19