基于局部密度构造相似矩阵的谱聚类算法 - 学兔兔 www.bzfxw.com .pdf

第 34 卷第 3期 通 信 学 报 Vol.34 No. 3
2013年 3月 Journal on Communications March 2013
基于局部密度构造相似矩阵的谱聚类算法
吴健,崔志明,时玉杰,盛胜利,龚声蓉
1. 苏州大学 智能信息处理及应用研究所,江苏 苏州 215006;2. 美国阿肯色中央大学 计算机科学系,阿肯色州 康威 72035-0001
摘 要:依据样本数据点分布的局部和全局致性特征,提出了种基于局部密度构造相似矩阵的谱聚类算法。
首先通过分析样本数据点的分布特性给出了局部密度定义,根据样本点的局部密度对样本点集由密到疏排序,并
按照设计的连接策略构建无向图;然后以 GN算法思想为参考,给出了种基于边介数的权值矩阵计算方法,经
过数据转换得到谱聚类相似矩阵;最后通过第个极大本征间隙出现的位置来确定类个数,并利用经典聚类方法
对特征向量空间中的数据点进行聚类。通过人工仿真数据集和 UCI数据集进行测试,实验结果表明本文谱聚类算
法具有较好的顽健性。
关键词:谱聚类;相似矩阵;局部密度;无向图构建;边介数
中图分类号:TP391 文献标识码:A 文章编号 :1000-436X201303-0014-09
局最优。与传统的聚类算法相比,它能很好地解决
1 引言
非块状和非凸形数据的聚类问题。谱聚类的这种优
传统的聚类分析方法受限于非凸形状的样 本 良特性 在图像分割 和 文档聚类 等 领域 得到了
空间,当样本空间不凸时,传统聚类算法会陷入局成功的应用。
部最优。为了克服样本空间形状的限制,研究者提 谱 聚 类 是 种 基 于 相 似 矩 阵 的 聚 类 算 法 , 它
出了谱聚类spectral clustering算法 。 该算法不仅 对 相似 矩阵 进行变 换得 到拉 普拉 斯矩 阵,然 后 对
能够在任意形状的样本空间上聚类,而且收敛于全 其特征向量进行聚类 。 所以, 相似矩阵构造
收稿日期:2012-11-07;修回日期:2013-01-27
基金项目:国家自然科学基金资助项目61003054, 61170020, 61170124
第 34 卷第 3期 通 信 学 报 Vol.34 No. 3
20第13 3期年 3月 吴健等:基于 Jou 局部 rna 密度 l on C 构造 omm 相似 unic 矩阵的 ations 谱聚类算法 Marc h 20 1513
的 好坏 是谱 聚类算 法优 劣的 重要 因素 。传统 的 谱 2.2 无向图构建
聚类 算法采用 欧式距离来表 示样本点 之间的距 2.2.1 现有构图方法分析
基于局部密度构造相似矩阵的谱聚类算法
离 ,并 通过 高斯核 变换 来计 算样 本点 之间的 相 似目前, 用来构造无向图的方法有ε阈值法、k近
度 ,其 仅考 虑到了 局部 致 性, 没有 考虑到 全 局邻法和互为 k 近邻法。ε阈值法虽然简便,但是由
致性。 王玲等 人 提 出 密 度吴健 敏 感,崔志 的 相 似明 性,时玉 度 量杰于样本点分布的多,盛胜利,龚声蓉样性,ε的选取比较困难,很难
1. 苏州大学 智能信息处理及应用研究所,江苏 苏州 215006;2. 美国阿肯色中央大学 计算机科学系,阿肯色州 康威 72035-0001
方 法, 该方 法采用 密度 敏感 的距 离测 度描述 数 据选择个合适的以得到既连通又稀疏的图。较之
的 实际 聚类 分布, 它可 以放 大不 同高 密度区 域 内更好且常用的是 k近邻方法, k 容易选取且能得到
摘 要:依据样本数据点分布的局部和全局致性特征,提出了种基于局部密度构造相似矩阵的谱聚类算法。
数 据点 间的 距离, 同时 缩短 同 高密 度区域 内 数个稀疏图。但是 k近邻法把每个数据点看成同
首先通过分析样本数据点的分布特性给出了局部密度定义,根据样本点的局部密度对样本点集由密到疏排序,并
据 点间 的距 离。相 对传 统的 相似 矩阵 计算方 法 ,等重要的点,随机对点进行 k近邻连线,不仅计算
按照设计的连接策略构建无向图;然后以 GN算法思想为参考,给出了种基于边介数的权值矩阵计算方法,经
该 方法 的定 义较复 杂且 计算 复杂 度较 高。孔 万 增量大而且可能导致不同类数据点间的互连,从而将
过数据转换得到谱聚类相似矩阵;最后通过第个极大本征间隙出现的位置来确定类个数,并利用经典聚类方法
等人 采用传统谱聚 类中 的方法构造相似矩阵 , 不同类数据点归为同类。互为 近邻方法 虽能保
对特征向量空间中的数据点进行聚类。通过人工仿真数据集和 UCI数据集进行测试,实验结果表明本文谱聚类算 k
法具有较好的顽健性。
利 用本 征间 隙自动 确定 数据 的聚 类个 数,并 利 用证数据点间互连的对称性,但其可能使同类样本之
关键词:谱聚类;相似矩阵;局部密度;无向图构建;边介数
确 定的 类数 和谱分 解的 特征 向量 之间 的余弦 值 完 间也无法得到连通图。 笔者以图 1 所示样本数据集
中图分类号:TP391 文献标识码:A 文章编号 :1000-436X201303-0014-09
成数据的聚类。文献110 中的谱聚类方法都没为例进行分析。
有 充分 利用 样本点 分布 特性 所隐 含的 先验信 息 ,
不 能构 造很 好的相 似矩 阵。 当其 面临 复杂样 本 数
据点集时,无法得到 理想 的聚类结果。
为了构建更符合样本数据点分布特性的相 似
矩阵,本文提出了种基于局部密度构造相似矩阵
的谱聚类LDSC, local density -based spectral clu s-
tering算法。通过人工仿真数据集和 UCI数据集进
行测试,实验结果表明,本文算法得到的相似矩阵
能更好地表示数据样本点之间的相似性,算法具有
较好的顽健性。
2 LDSC算法 图1 原始样本数据集
2.1 算法思想
构建无向图,即根据定的策略给样本空间中
样本数据点 集分布 具有 如下 2 个 致性特 的 数 据点 连 线, 最终 得到样 本 数据 集 对应 的无 向
征。
图。图 1为原始数据集,分为上月、下月和最下面
1 局部致性:指的是在空间位置上相邻的数
的不规则分布 3类。
据点具有较高的相似性。
ing capability. 图 2中给出了利用 3种现有方法构建无向图的
2 全局致性:指的是位于同流形上的数据
结果,从图 2中可以看出现有无向图构建方法的局
点具有较高的相似性。 限性。图 2a的ε 阈值构图法中, 阈值为 0.3,从图
局最优。与传统的聚类算法相比,它能很好地解决
本文依 据样本数据点 分布的局 部和全局
2a 中很容易发现其存在的问题:同类样本数据点
1 引言
非块状和非凸形数据的聚类问题。谱聚类的这种优
致性特 征 , 提 出了 种 基 于局部 密度 构造 相似 矩
间不连通,且存在较多孤立点。图 2b的 k近邻方
传统的聚类分析方法受限于非凸形状的样 本 良特性 在图像分割 和 文档聚类 等 领域 得到了
阵的谱 聚类 算法 。算 法首 先给出 局部 密度 定义 ,
法虽然已形成连通图,但也存在明显的缺陷:不同
空间,当样本空间不凸时,传统聚类算法会陷入局成功的应用。
对样本 数据 点由 密到 疏排 序, 按序 依次 对样 本点
类样本数据点互连,即图 2b中的下月型数据集和

展开阅读全文