基于三支决策的密度敏感谱聚类

doi:10.6040/j.issn.1671-9352.0.2021.671

摘要/Abstract

摘要： 将三支决策与密度敏感谱聚类结合,提出了一种基于三支决策的密度敏感谱聚类算法。该算法通过在密度敏感谱聚类的聚类过程引入容差参数得到每个类的上界,然后通过扰动分析算法从上界中分离出核心域,上界和核心域的差值被认定为该类的边界域。聚类结果用核心域和边界域来表示每个类簇,可以更全面地展示数据的结构信息。与传统的硬聚类算法在UCI数据集的实验结果相比较,本文使用核心域计算聚类的评价指标DBI、AS和ACC都有所提升,较好地解决了不确定性对象的聚类问题。

关键词: 三支决策, 三支聚类, 密度敏感, 相似性度量

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

中图分类号:

TP301.6

凡嘉琛,王平心,杨习贝. 基于三支决策的密度敏感谱聚类[J]. 《山东大学学报(理学版)》, 2023, 58(1): 59-66.

FAN Jia-chen, WANG Ping-xin, YANG Xi-bei. Density-sensitive spectral clustering based on three-way decision[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(1): 59-66.

参考文献

[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.

相关文章 13

[1]	钱进,汤大伟,洪承鑫. 多粒度层次序贯三支决策模型研究[J]. 《山东大学学报(理学版)》, 2022, 57(9): 33-45.
[2]	巩增泰,他广朋. 直觉模糊集所诱导的软集语义及其三支决策[J]. 《山东大学学报(理学版)》, 2022, 57(8): 68-76.
[3]	施极,索中英. 基于区间数层次分析法的损失函数确定方法[J]. 《山东大学学报(理学版)》, 2022, 57(5): 28-37.
[4]	杨洁,罗天,李阳军. 基于TOPSIS的无标签序贯三支决策模型[J]. 《山东大学学报(理学版)》, 2022, 57(3): 41-48.
[5]	李敏,杨亚锋,雷宇,李丽红. 基于可拓域变化代价最小的最优粒度选择[J]. 《山东大学学报(理学版)》, 2021, 56(2): 17-27.
[6]	余鹰,吴新念,王乐为,张应龙. 基于标记相关性的多标记三支分类算法[J]. 《山东大学学报(理学版)》, 2020, 55(3): 81-88.
[7]	姬儒雅,魏玲,任睿思,赵思雨. 毕达哥拉斯模糊三支概念格[J]. 《山东大学学报(理学版)》, 2020, 55(11): 58-65.
[8]	刘国涛,张燕平,徐晨初. 一种优化覆盖中心的三支决策模型[J]. 山东大学学报（理学版）, 2017, 52(3): 105-110.
[9]	张聪, 于洪. 一种三支决策软增量聚类算法[J]. 山东大学学报（理学版）, 2014, 49(08): 40-47.
[10]	田海龙, 朱艳辉, 梁韬, 马进, 刘璟. 基于三支决策的中文微博观点句识别研究[J]. 山东大学学报（理学版）, 2014, 49(08): 58-65.
[11]	张里博, 李华雄, 周献中, 黄兵. 人脸识别中的多粒度代价敏感三支决策[J]. 山东大学学报（理学版）, 2014, 49(08): 48-57.
[12]	杜丽娜, 徐久成, 刘洋洋, 孙林. 基于三支决策风险最小化的风险投资评估应用研究[J]. 山东大学学报（理学版）, 2014, 49(08): 66-72.
[13]	李成栋,魏　荣 . 双枝模糊集的内、外积及相似性度量[J]. J4, 2007, 13(2): 72-76 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed