基于加权密度的自适应谱聚类算法

计算机工程与科学

基于加权密度的自适应谱聚类算法

万月，陈秀宏，何佳佳

（江南大学数字媒体学院,江苏无锡 214122）

收稿日期:2017-12-27 修回日期:2018-03-12 出版日期:2018-10-25 发布日期:2018-10-25
基金资助:
国家自然科学基金（61373055）;江苏省2015年度普通高校研究生科研创新计划（KYLX_1191）

An adaptive spectral clustering algorithm

based on weighted density

WAN Yue，CHEN Xiuhong，HE Jiajia

（School of Digital Media,Jiangnan University,Wuxi 214122,China）

Received:2017-12-27 Revised:2018-03-12 Online:2018-10-25 Published:2018-10-25

摘要/Abstract

摘要：

谱聚类算法中如何定义一个合适的尺度参数仍待学习。针对谱聚类算法中由高斯核函数建立的相似度矩阵对尺度参数敏感的问题，提出了一个新的基于加权密度的自适应谱聚类算法——WDSC。该算法将数据点的加权K近邻距离作为尺度参数，尺度参数的倒数作为数据点所在邻域的密度，引入新的密度差调整相似度矩阵；考虑了每个数据点的邻域分布，故对噪声有一定的鲁棒性，且对参数也不再敏感。在不同数据集上的实验以及对比实验均验证了该算法的有效性与鲁棒性。

关键词: 谱聚类, 尺度参数, 加权K近邻, 密度差

Abstract:

How to decide a proper scale parameter is still an issue to deal with. In this paper, we propose an adaptive spectral clustering algorithm based on weighted density
(WDSC), which solves the sensitivity of the scale parameter in the similarity matrix made from Gaussian kernels. It takes weighted K nearest neighbor distance of each data as the scale parameter, and the reciprocal of the scale parameter as its density. It also brings in a new density contrast to adjust the similarity matrix. It takes the neighbor distribution of each data into consideration, so it is robust to outliers and insensitive to scale parameters. Experiments on different datasets and comparative experiments demonstrate the effectiveness and robustness of the proposed algorithm.

Key words: spectral clustering, scale parameter, weighted K nearest neighbor, density contrast

万月，陈秀宏，何佳佳. 基于加权密度的自适应谱聚类算法[J]. 计算机工程与科学.

WAN Yue，CHEN Xiuhong，HE Jiajia.

An adaptive spectral clustering algorithm

based on weighted density

[J]. Computer Engineering & Science.

[1]	袁泉, 晏飞扬, 文志云, 张振康, . 基于谱聚类的社交网络差分隐私保护算法研究[J]. 计算机工程与科学, 2022, 44(02): 251-256.
[2]	毛伊敏，刘银萍. 基于复合物参与度和密度的关键蛋白质预测[J]. 计算机工程与科学, 2019, 41(10): 1738-1748.
[3]	周伟，肖杨 . 基于Canopy聚类的谱聚类算法[J]. 计算机工程与科学, 2019, 41(06): 1095-1100.
[4]	刘汉强，张青. 区间模糊谱聚类图像分割方法[J]. 计算机工程与科学, 2018, 40(09): 1611-1616.
[5]	李瑞琳1,2，赵永华1，黄小磊2,3. 一种基于MPI的稀疏化局部尺度并行谱聚类算法的研究与实现[J]. J4, 2016, 38(05): 839-847.
[6]	张振宇,张珍,杨文忠,吴晓红. 复杂网络中重叠社区检测[J]. J4, 2013, 35(12): 76-83.