没有合适的资源?快使用搜索试试~ 我知道了~
相对邻域与剪枝策略优化的密度峰值聚类算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 157 浏览量
2023-02-23
20:15:25
上传
评论
收藏 2.49MB DOCX 举报
温馨提示
试读
24页
相对邻域与剪枝策略优化的密度峰值聚类算法.docx
资源推荐
资源详情
资源评论
聚类分析简称聚类, 是根据样本间的相似性将样本集划分成合理类簇的过程, 聚类结
果使得同一类簇中的样本具有较高的相似性, 而不同类簇之间的样本相似性较低
[1-3]
. 聚类
是数据挖掘中的基本技术, 能够从数据中发现潜藏的知识和模式, 已广泛应用于社会网络分
析、图像模式识别、智能商务等众多领域.大数据背景下, 数据的海量、多样和复杂使得具
有自动理解、处理和概括数据的高效聚类算法研究迫在眉睫
[4]
.
聚类算法大致可以分为划分式聚类方法
[5-6]
、层次聚类方法
[7]
、基于网格的聚类方法
[8]
和基于密度的聚类方法
[9]
等. 其中, 基于密度的聚类方法可以发现任意形状的类簇, 对噪音
数据不敏感, 且聚类时不需要事先知道类簇的个数, 是数据挖掘技术中广泛使用的一类方
法.
快速搜索和发现样本密度峰值聚类(Density peaks clustering, DPC)算法是 Rodriguez 等
[10]
近年在 Science 发表的一种新型聚类算法. 与其他聚类算法不同, DPC 算法能自动确定类
簇数和类簇中心点, 并进行高效的非中心点样本分配和离群点剔除, 因而吸引了众多学者对
它进行深入研究. Wang 等
[11]
针对 DPC 算法对输入参数 dc (密度计算的截断距离)敏感, 并且
没有有效的设定准则的问题, 在采用核函数计算密度的情况下, 结合数据域的概念提出了一
种自动计算 dc 的方法. 同时, 强调在大数据量情况下算法效率是 DPC 算法亟待研究的关键
问题. Zhang 等
[12]
针对 DPC 算法不能解决一个类簇中多密度峰值或者无密度峰值的情况, 提
出一种扩展的 E_CFSFDP (Extended clustering by fast search and find of density peaks)算法,
在 DPC 算法聚类完成之后, 多执行一个子类的合并步骤. 该扩展方法在无密度峰值的数据
集上取得了更好的实验效果, 但是时间开销巨大, 作者也将降低时间消耗作为下一步研究的
重点. 谢娟英等
[13]
针对 DPC 算法中截断距离 dc 对聚类结果影响较大和样本分配策略可能
会导致的“多米诺骨牌”效应的问题, 分别提出了 K 近邻优化和模糊加权 K 近邻优化的密度
聚类方法 KNN-DPC (K-nearest neighbors optimized density peaks clustering)和 FKNN-DPC
(Fussy weighted KNN-DPC)
[14]
, 并通过实验证明了改进方法的有效性. 但是并未给出关于引
入参数 K 的有效设定方法, 同时由于额外 K 近邻的查找和复杂的类簇分配策略的引入, 使
得 KNN-DPC 和 FKNN-DPC 算法的时间复杂性都要远高于 DPC, 极大地影响了算法的实用
性. 因为 DPC 算法首先需要计算数据集中任意两个样本间的欧氏距离, 其时间复杂度为
O(m×n2)O(m×n2)(m 为样本特征个数, n 为数据集样本个数), 当处理海量高维数据时,大量
的高维欧氏距离计算会带来高额的时间开销, 严重影响了算法的实用性, 所以对 DPC 算法
的效率改进展开研究具有重要的应用价值. 巩树凤等
[15]
考虑了 DPC 算法效率不高的问题,
给出了分布式环境下的密度中心聚类算法 SDDPC (Simple distributed density peaks
clustering), 并且结合 Voronoi 图提出了优化的 EDDPC (Efficient distributed density peaks
clustering)算法, 提高了分布式环境下 DPC 算法的效率, 但并没有涉及 DPC 算法本身的研
究与改进.
针对 DPC 算法和现有改进算法在效率方面的不足, 本文提出一种基于相对邻域和剪枝
策略的密度峰值快速搜索聚类(Relative neighborhood and pruning strategy optimized density
peaks clustering, RP-DPC)算法. RP-DPC 的主要贡献包括: 1)改变原 DPC 算法的流程, 不再
预先计算样本两两之间的距离, 改为在聚类过程中计算必要的样本间距离, 从而避免了大量
冗余距离的计算; 2)借助双基准点映射的相对邻域来大致衡量样本之间的亲疏关系, 从而只
需要对相对“亲密”的样本进行距离计算和密度统计; 3)在计算样本的斥群值(与更高密度样
本之间距离的最小值
[15]
)时加入剪枝策略, 极大地缩小被剪枝样本的斥群值查找范围, 从而
加快了算法的效率; 4) 理论分析和在多个数据集上的对比实验均表明, RP-DPC 算法具有和
DPC 算法同样的聚类效果, 时间性能却大大优于已有的 DPC 算法及其改进算法.
1. DPC 算法
快速搜索和发现样本密度峰值的聚类算法 DPC
[10]
能够自动发现数据集样本的类簇中
心, 实现任意形状数据集样本的聚类. 该算法的设计基于以下假设: 1)聚类中心点的密度较
大, 被密度不超过它的样本点包围; 2)聚类中心点与其他密度更大的点(另一个类簇的中心
点)的距离相对较远. 为了找到同时满足上述条件的类簇中心, DPC 算法引入了样本 xixi 的
密度 ρiρi 和斥群值 δiδi, 其定义如式(1)和式(2)所示:
ρi=∑jχ(d(xi,xj)−dc)ρi=∑jχ(d(xi,xj)−dc)
(1)
其中, χ(x)χ(x)是一个函数, 当 x<0x<0 时,χ(x)=1χ(x)=1, 否则
χ(x)=0χ(x)=0; d(xi,xj)d(xi,xj)为样本 xixi 和 xjxj 间的欧氏距离, dcdc 为截断距离,即样本 xixi
的密度 ρiρi 是与样本 xixi 的距离小于 dcdc 的点的个数.
δi=min(d(xi,xj)|ρi>ρj)δi=min(d(xi,xj)|ρi>ρj)
(2)
斥群值 δiδi 代表密度比样本 xixi 大且距离样本 xixi 最近的点的距离. 当某个点 xixi 的
密度是样本集中最大的, 那么设定点 xixi 的 δi=dmaxδi=dmax(dmaxdmax 为已有样本间距离
的最大值).
DPC 算法将每个数据点的 ρρ 值和 δδ 值表示在一个 2 维决策图(Decision graph)上. 用
户根据决策图的分布情况, 选定聚类中心点, 接下来再将所有剩下的点分配到比其密度更高
且最近的样本点所属的类簇中. DPC 算法构造样本距离相对于样本密度的 2 维决策图, 能够
展示任意维度数据集的类簇中心点, 实现对任意维度数据的可视化聚类分析.
文献[10]使用大量实验证明了 DPC 算法在聚类质量上的优良性能,但是该算法也存在
一些不足, 包括质量和效率两个方面, 本文主要关注其效率方面. 对样本规模为 nn, 属性个
数为 mm 的数据集, DPC 算法中时间复杂度主要来自 3 部分: 1) 计算两两样本间的距离,
其时间复杂度为 O(m×n2)O(m×n2); 2) 计算每个样本的密度 ρρ, 其时间复杂度为
O(n2)O(n2); 3) 计算每个样本的 δδ 值, 其时间复杂度也是 O(n2)O(n2). 所以 DPC 算法总的
时间度杂度为 O(m×n2)O(m×n2). 当处理海量高维数据时, 算法的实用性受到了严重的影
响.
进一步分析 DPC 算法的时间复杂度, 其最高复杂度来自于样本间距离矩阵的计算, 后
续的样本 ρρ 值和 δδ 值都是在此距离矩阵上展开. 但仔细分析算法中 ρρ 值和 δδ 值的含义,
可以发现每个样本的 ρρ 值和 δδ 值计算并不需要全部用到该样本与其他 n−1n−1 个样本的
距离, 因此 DPC 算法预先计算的距离矩阵存在大量冗余距离. 本文提出的改进方法是将样
本间距离的计算过程后移, 与样本的 ρρ 值和 δδ 值计算过程结合在一起. 对在 ρρ 值和 δδ
值计算中明确需要用到的样本间距离才进行计算, 从而避免大量冗余距离的计算, 提高算法
的时间效率.
2. RP-DPC 算法及其分析
本文从缩减 ρρ 值计算时样本间距离计算量和 δδ 值计算时距离比较范围两个方面对原
DPC 算法进行改进, 提出了一种基于相对邻域和剪枝策略优化的密度峰值聚类算法: RP-
DPC 算法. 算法主要思想是: 首先, 去掉 DPC 算法中复杂度最高的距离矩阵预计算步骤;
其次, 在 ρρ 值计算中, 将相对距离的思想引入到 DPC 算法, 通过相对邻域来刻画对象之间
的相对位置关系, 以此缩小样本 ρρ 值计算所需要的距离计算量; 然后, 在计算各样本的 δδ
值时, 加入剪枝策略, 将被剪枝样本点的 δδ 值计算范围从样本集缩小到其自身邻域以内,
因此剪枝策略可以进一步提高算法的时间性能. 本节内容安排如下: 第 2.1 节对 RP-DPC 算
法做一个整体描述, 第 2.2 节和第 2.3 节将分别给出 RP-DPC 算法对样本 ρρ 值和 δδ 值的改
进计算方法, 最后, 第 2.4 节给出 RP-DPC 算法复杂度分析.
2.1 RP-DPC 算法描述
DPC 算法与 RP-DPC 算法的流程图如图 1 所示, 两个算法的不同之处已用虚线框标出.
由图 1 可以清楚地看出, 与 DPC 算法相比, RP-DPC 算法去掉了距离矩阵的计算步骤, 但在
样本的 ρρ 值和 δδ 值计算过程中增加了相对邻域映射模型和剪枝策略. RP-DPC 算法的具体
描述见算法 1.
下载: 全尺寸图片 幻灯片
算法 1. RP-DPC 算法
输入. 数据集 S={xi}ni=1S={xi}i=1n, 截断距离 dcdc.
输出. 聚类结果 CC.
步骤 1. 数据预处理: 数据归一化;
步骤 2. 采用相对邻域映射模型计算每个样本的密度 ρiρi;
步骤 3. 采用剪枝策略计算样本的斥群值 δiδi;
步骤 4. 按照 DPC 中的操作从由 ρρ 和 δδ 构成的决策图中选出类簇中心点集合 CICI;
步骤 5. 按照 DPC 的方法对非类簇中心点的样本进行类簇分配.
2.2 相对邻域映射模型
在密度 ρρ 值计算中, 原 DPC 算法首先需要计算每个样本与其他 n−1n−1 个样本的距
离, 找到该样本的邻域, 然后再统计其邻域内的样本数量得到密度, 这一步骤的时间复杂度
为 O(n2)O(n2). 对于任意样本 xixi 来说, 计算其密度需要知道 xixi 与其他 n−1n−1 个样本的
精确距离, 但若是将某个样本从 xixi 邻域中排除则只需要大致的距离范围就可以了. 基于上
述分析, 本文采用排除法. 通过样本间相对位置获取样本间大致的距离范围来排除大部分不
可能属于彼此邻域的样本, 从而大大降低密度计算的复杂度. 为了实现这一目标, 受文献
[16]的启发, 本文将相对距离的思想引入到 RP-DPC 算法.
文献[16]在计算样本邻域时, 根据各样本到基准点的距离将每一个样本映射到不同的
桶中, 然后在计算每个样本的邻域时最多只要从相邻 3 个桶的样本中寻找, 而不是从整个样
本集, 从而提高算法效率. 具体做法如下:
设给定样本集 S={xi}ni=1S={xi}i=1n, 每个样本有 mm 维特征, 第 ii 个样本的第 jj 个特
征的值记为 vijvij, 截断距离记为 dcdc.
文献[16]中对基准点和映射函数的定义如式(3)和(4)所示.
x0=(v0j)mj=1x0=(v0j)j=1m
(3)
其中, v0j=min((vij)ni=1)v0j=min((vij)i=1n). 基准点 x0x0 由 SS 中所有样本在 mm 个特
征上的最小值所构成.
剩余23页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3651
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功