JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (1): 59-66.doi: 10.6040/j.issn.1671-9352.0.2021.671

Previous Articles    

Density-sensitive spectral clustering based on three-way decision

FAN Jia-chen1, WANG Ping-xin2*, YANG Xi-bei1   

  1. 1. School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212003, Jiangsu, China;
    2. School of Science, Jiangsu University of Science and Technology, Zhenjiang 212003, Jiangsu, China
  • Published:2023-02-12

PDF (PC)

177

Abstract: This paper integrates density sensitive spectral clustering with three-way decision and presents a density sensitive spectral clustering algorithm based on three-way decision. In the proposed algorithm, the upper bound of each cluster is obtained by introducing tolerance parameters in the process of density-sensitive spectral clustering, and the core is separated from the upper bound by the perturbation analysis algorithm. The difference between the upper bound and the core region is regarded as the fringe region of the specific cluster. The clustering result uses the core region and the fringe region to represent each cluster, which can more comprehensively display the data structure. Compared with the experimental results of the traditional hard clustering algorithm on the UCI data set, the proposed algorithm is effective in improving the value of AS and ACC and reducing the value of DBI by using the core region to calculate the evaluation indicators of clustering, which indicates that the proposed algorithm can be used to solve the problem of clustering uncertain objects.

Key words: three-way decision, three-way clustering, density-sensitive, similarity measure

CLC Number: 

  • TP301.6
[1] SONG Lihua, ZHANG Xiaofeng. Improved pixel relevance based on Mahalanobis distance for image segmentation[J]. International Journal of Information and Computer Security, 2018, 10(2/3):237-247.
[2] ZHENG Liang, YANG Yi, TIAN Qi. SIFT meets CNN: a decade survey of instanceretrieval[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 40(5):1224-1244.
[3] LU D, TRIPODIS Y, GERSTENFELD L C, et al. Clustering of temporal gene expression data with mixtures of mixed effects models with a penalizedlikelihood[J]. Bioinformatics, 2019, 35(5):778-786.
[4] 雷小锋,谢昆青,林帆,等. 一种基于k-Means局部最优性的高效聚类算法[J]. 软件学报, 2008, 19(7):1683-1692. LEI Xiaofeng, XIE Kunqing, LIN Fan, et al. An efficient clustering algorithm based on local optimality of k-means[J]. Journal of Software, 2008, 19(7):1683-1692.
[5] LUXBURG U V. A tutorial on spectralclustering[J]. Statistics and Computing, 2007, 17(4):395-416.
[6] XU Danhua, LI Chuan, CHEN Teng, et al. A novel low rank spectral clustering method for faceidentification[J]. Recent Patents on Engineering, 2019, 13(4):387-394.
[7] XIA Kaijian, GU Xiaoqing, ZHANG Yudong. Oriented grouping-constrained spectral clustering for medical imaging segmentation[J]. Multimedia Systems, 2020, 26(1):27-36.
[8] ZELNIK-MANOR L, PERONA P. Self-tuning spectral clustering[C] //Advances in Neural Information Processing System(NIPS17). [S.l.] : MIT Press, 2005: 1601-1608.
[9] YAO Yiyu. The superiority of three-way decisions in probabilistic rough set models[J]. Information Science, 2011, 181(6):1080-1096.
[10] YAO Yiyu. An outline of a theory of three-way decisions[C] // 8th International Conference on Rough Sets and Current Trends in Computing. Chengdu: Springer, 2012: 1-17.
[11] 李金海,邓硕. 概念格与三支决策及其研究展望[J]. 西北大学学报(自然科学版), 2017, 47(3):321-329. LI Jinhai, DENG Shuo. Concept lattice, three-way decisions and their research outlooks[J]. Journal of Northwest University(Natural Science Edition), 2017, 47(3):321-329.
[12] CHENG Yusheng, RUI Kai. Text classification of minimal risk with three-waydecisions[J]. Journal of Information and Optimization Sciences, 2018, 39(4):973-987.
[13] LIU Fang, LIU Yi, ABDULLAH S. Three-way decisions with decision-theoretic rough sets based on covering-based q-rung orthopair fuzzy rough set model[J]. Journal of Intelligent and Fuzzy Systems, 2021, 40(5):9765-9785.
[14] WANG Pingxin, YAO Yiyu. CE3: a three-way clustering method based on mathematicalmorphology[J]. Knowledge-based Systems, 2018, 155:54-65.
[15] YU Hong, ZHANG Cong, WANG Guoyin. A tree-based incremental overlapping clustering method using the three-way decision theory[J]. Knowledge-based Systems, 2016, 91(C):189-203.
[16] YU Hong. A framework of three-way cluster analysis[C] // International Joint Conference on Rough Sets. Olsztyn: Springer, 2017: 300-312.
[17] 王玲,薄列峰,焦李成. 密度敏感的谱聚类[J]. 电子学报, 2007, 35(8):1577-1581. WANG Ling, BO Liefeng, JIAO Licheng. Density-sensitive spectral clustering[J]. Acta Electronics Sinica, 2007, 35(8):1577-1581.
[18] NG A Y, JORDAN M I, WEISS Y. On spectral clustering:analysis and an algorithm[C] //Proceedings of the 14th International Conference on Neural Information Processing Systems:Natural and Synthetic. Cambridge: MIT Press, 2001: 849-856.
[19] 陶新民,王若彤,常瑞,等. 基于低密度分割密度敏感距离的谱聚类算法[J]. 自动化学报, 2020, 46(7):1479-1495. TAO Xinmin, WANG Ruotong, CHANG Rui, et al. Low density separation density sensitive distance-based spectral clustering algorithm[J]. Acta Automatic Sinica, 2020, 46(7):1479-1495.
[20] WANG Pingxin, SHI Hong, YANG Xibei, et al. Three-way k-means: integrating k-means and three-way decision[J]. International Journal of Machine Learning and Cybernetics, 2019, 10(10):2767-2777.
[21] MAULIK U, BANDYOPADHYAY S. Performance evaluation of some clustering algorithms and validity indices[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(12):1650-1654.
[22] BEZDEK J C, PAL N R. Some new indexes of clustervalidity[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1998, 28(3):301-315.
[23] ROUSSEEUW P. Silhouettes: a graphical aid to the interpretation and validation ofcluster analysis[J]. Journal of Computational and Applied Mathematics, 1987, 20(20):53-65.
[1] QIAN Jin, TANG Da-wei, HONG Cheng-xin. Research on multi-granularity hierarchical sequential three-way decision model [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(9): 33-45.
[2] GONG Zeng-tai, TA Guang-peng. Semantics of the soft set induced by intuitionistic fuzzy set and its three-way decision [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(8): 68-76.
[3] SHI Ji, SUO Zhong-ying. Loss function determination method based on interval number analytic hierarchy process [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(5): 28-37.
[4] YANG Jie, LUO Tian, LI Yang-jun. Unlabeled sequential three-way decisions model based on TOPSIS [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(3): 41-48.
[5] LI Min, YANG Ya-feng, LEI Yu, LI Li-hong. Optimal granularity selection based on minimum cost of extension domain change [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(2): 17-27.
[6] Ying YU,Xin-nian WU,Le-wei WANG,Ying-long ZHANG. A multi-label three-way classification algorithm based on label correlation [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(3): 81-88.
[7] JI Ru-ya, WEI Ling, REN Rui-si, ZHAO Si-yu. Pythagorean fuzzy three-way concept lattice [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(11): 58-65.
[8] 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.
[9] ZHANG Cong, YU Hong. An incremental three-way decisions soft clustering algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 40-47.
[10] 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.
[11] ZHANG Li-bo, LI Hua-xiong, ZHOU Xian-zhong, HUANG Bing. Multi-granularity cost-sensitive three-way decision for face recognition [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 48-57.
[12] DU Li-na, XU Jiu-cheng, LIU Yang-yang, SUN Lin. Research on the evaluation of venture investment based on the risk minimization of three-way decision [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 66-72.
[13] LI Cheng-dong and WEI Rong . The interior and exterior product and similarity measurement of both-branch fuzzy sets [J]. J4, 2007, 13(2): 72-76 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd