基于三支决策的谱聚类算法研究-《南京师范大学学报》（自然科学版）

文章信息/Info

Title:: Research on Spectral Clustering Algorithm Based on Three-way Decision

作者:: 施虹¹; 刘强¹; 王平心¹; 2; 杨习贝¹; (1.江苏科技大学计算机学院,江苏镇江 212003)(2.河北师范大学数学与信息科学学院,河北石家庄 050024)

Author(s):: Shi Hong¹; Liu Qiang¹; Wang Pingxin¹; 2; Yang Xibei¹; (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)

摘要:: 硬聚类要求聚类的结果必须具有清晰的边界,即每个对象要么属于一个类,要么不属于一个类. 然而,将某些不确定的对象强制分配到某个类中往往容易带来较高的决策风险. 三支聚类将确定的元素放入核心域中,将不确定的元素放入边界域中延迟决策,可以有效地降低决策风险. 本文将三支决策理论与传统的谱聚类算法相结合给出了三支谱聚类的聚类算法. 该方法通过修改谱聚类算法的聚类过程并获得任一类簇的上界. 然后通过扰动分析从该类簇的上界分离出该类簇的核心域,同时上界与核心域的差值认为是该类簇的边界域. 在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.