第 29 卷 第 9 期
Vol. 29 No. 9
控 制 与 决 策
Control and Decision
2014 年 9 月
Sep. 2014
基于密度调整的改进自适应谱聚类算法
文章编号: 1001-0920 (2014) 09-1683-05 DOI: 10.13195/j.kzyjc.2013.0660
王雅琳, 陈 斌, 王晓丽, 桂卫华
(中南大学 信息科学与工程学院，长沙 410083)
摘 要: 针对谱聚类存在构造相似度矩阵时对尺度参数敏感以及处理多重尺度数据集效果不理想的缺陷, 提出一种
基于密度调整的改进自适应谱聚类算法. 该算法将样本点所处领域的密度引入谱聚类, 利用密度差来调整样本点之
间的相似度, 使其更符合实际簇类中样本点间的内在关系, 在一定程度上解决了多尺度聚类问题; 同时, 通过样本点
的近邻距离自适应得到尺度参数, 使算法对尺度参数相对不敏感. 仿真实验验证了所提出算法的有效性和优越性.
关键词: 谱聚类；密度调整；自适应；尺度参数；多重尺度数据集
中图分类号: TP181 文献标志码: A
Improved adaptive spectral clustering algorithm based on density
adjustment
WANG Ya-lin, CHEN Bin, WANG Xiao-li, GUI Wei-hua
(School of Information Science and Engineering，Central South University，Changsha 410083，China. Correspondent:
WANG Ya-lin，E-mail：ylwang@csu.edu.cn)
Abstract: As spectral clustering is sensitive to the scaling parameter while calculating the affinity matrix and the result of
clustering multi-scale dataset is not ideal, an improved adaptive spectral clustering algorithm based on density adjustment
is proposed. The algorithm introduces local density of data into spectral clustering, using the density difference to adjust
the similarity between sample points, which makes it more consistent with the data points’ internal relations of the clusters’
actual structure. So that it solves the multi-scale clustering problem to some extent. At the same time, the algorithm is
relatively insensitive to the scaling parameter by using the distances between data points and their neighbor points to get the
scaling parameter adaptively. Simulation experiment shows the effectiveness and superiority of the proposed algorithm.
Key words: spectral clustering；density adjustment；adaptive；scaling parameter sensitivity；multi-scale dataset
0 引引引 言言言
作为数据挖掘中进行数据处理的一种重要方
法
[1]
, 聚类分析是根据一定的相似准则将数据对象划
分为由类似对象组成的多个类的过程. 由聚类得到
的同一类中的对象彼此相似, 而不同类中的对象彼
此相异. 现如今, 聚类算法已经有很多种, 如传统的
𝐾-means 算法
[2]
、FCM 算法
[3]
等. 这些经典的聚类算
法虽然在凸样本空间上有比较好的聚类效果, 但是当
样本空间不为凸时, 算法很容易陷入局部最优. 近年
来出现的谱聚类算法使得这个问题得以解决. 谱聚
类
[4-6]
是一种性能优越的聚类算法, 它不受数据集样
本点簇类形状的影响, 即使样本空间非凸, 也能得到
全局最优解, 因此, 谱聚类很快成为了关注焦点
[7-10]
.
谱聚类算法具有比其他聚类算法更优越的性能,
但其本身也存在构造相似度矩阵时对尺度参数比较
敏感以及处理多重尺度数据集时结果不理想等问
题. 为此, 广大学者对谱聚类算法进行了研究. Gong
等
[11]
通过数据点的邻近点信息来构造相似图, 以此
获得数据点间的相似度矩阵, 提出了一种基于局域信
息的谱聚类算法; Ozertem 等
[12]
利用 Mean Shift 算法
求得的权值来建立谱聚类中的相似图, 提出了一种
Mean Shift 谱聚类算法; 周林等
[13]
提出了基于谱聚类
的聚类集成算法, 首先利用谱聚类算法的内在特性
构造多样性聚类成员, 然后采用连接三元组方法和
Nystr
¨
om 采样方法计算相似度矩阵, 扩充了数据点之
间的相似性信息. 以上算法都不需要人为设定尺度
收稿日期: 2013-05-21；修回日期: 2013-08-28.
基金项目: 国家自然科学基金项目(61273187)；教育部博士点新教师类基金项目(20120162120022)；湖南省科技计划
项目(2012CK4018).
作者简介: 王雅琳(1973−), 女, 教授, 博士, 从事复杂过程建模、优化与控制等研究；陈斌(1989−), 男, 硕士生, 从事数
据挖掘与聚类分析的研究.
资源评论
