推荐星级：
- 1
- 2
- 3
- 4
- 5
基于z值的分布式密度峰值聚类算法
资料介绍
密度峰值聚类算法由于在发现任意形状簇且不需指定聚类个数等方面具有一定的优势而被广泛关注.但是该算法需要计算数据集中所有点的密度和点对之间的距离,因此不适合处理大规模高维数据集.为此,本文提出了一种基于z值的分布式密度峰值聚类算法,DP-z.本方法利用空间z填充曲线将高维数据集映射到一维空间上,根据数据点的z值信息对数据集分组.为了能够得到正确的结果,需要对分组间数据进行交互,然后并行计算每个点密度和斥群值.DP-z算法在分组间数据交互时采用过滤策略,减少大量无效距离计算和数据传输开销,有效提高算法的执行效率.最后,本文在云计算平台上对DP-z算法进行了验证,实验表明在保证DP-z算法与原始密度峰值聚类算法聚类结果相同的情况下有效的提高了算法执行效率.
部分文件列表
| 文件名 | 大小 |
| 基于z值的分布式密度峰值聚类算法.pdf | 1012K |
部分页面预览
（完整内容请下载后查看）3
Vol． 46 No． 3
Mar． 2018
第
期
电
子
学
报
2018
3
ACTA ELECTRONICA SINICA
年
月
z
基于 值的分布式密度峰值聚类算法
1
1
2
，
，
卢 晶 段 勇 刘海波
( 1．
，
110870;
沈阳工业大学信息科学与工程学院 辽宁沈阳
2．
，
071002)
河北大学计算机科学与技术学院 河北保定
:
．
摘
要
密度峰值聚类算法由于在发现任意形状簇且不需指定聚类个数等方面具有一定的优势而被广泛关注
，
．
，
但是该算法需要计算数据集中所有点的密度和点对之间的距离 因此不适合处理大规模高维数据集 为此 本文提出
z
了一种基于 值的分布式密度峰值聚类算法
，DP-z．
z
本方法利用空间 填充曲线将高维数据集映射到一维空间上 根
，
z
．
，
据数据点的 值信息对数据集分组 为了能够得到正确的结果 需要对分组间数据进行交互 然后并行计算每个点密
，
． DP-z
，
，
算法在分组间数据交互时采用过滤策略 减少大量无效距离计算和数据传输开销 有效提高算法的
度和斥群值
．
执行效率 最后 本文在云计算平台上对
，
DP-z ， DP-z
算法进行了验证 实验表明在保证
算法与原始密度峰值聚类算法
．
聚类结果相同的情况下有效的提高了算法执行效率
:
;
;
聚类 分布式计算 云计算
; z ;
填充曲线 密度峰值
关键词
:
TP301. 6
:
A
:
0372-2112 ( 2018) 03-0730-09
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 03． 031
中图分类号
文献标识码
文章编号
URL: http: / /www． ejournal． org． cn
电子学报
Distributed Density Peaks Clustering Based on z-Value
1
1
2
LU Jing ，DUAN Yong ，LIU Hai-bo
( 1． School of Information Science and Engineering，Shenyang University of Technology，Shenyang，Liaoning 110870，China;
2． School of Computer Science and Technology，Hebei University，Baoding，Hebei 071002，China)
Abstract: Density peak clustering is an effective and novel clustering algorithm，it is concerned as its superiority of
finding arbitrary shape of clusters and number of clusters． However，this algorithm is required to measure the density and dis-
tance between any pair of objects． This limits the practicability of this algorithm when clustering high-volume and high-di-
mensional data set． In order to improve efficiency and scalability，we propose a distributed density peak clustering algorithm
based on z-value，and DP-z． It utilizes z-values to map points in multidimensional space into one dimension，and then splits
the data set into several partitions according to the z-values of points． In order to get the correct result，we make use of the
character of points' z-values to filter the data object while exchanging data among groups，which reduces a huge amount of
useless distance measurement cost and data shuffle cost． Then we compute the density and distance value in parallel． Finally，
we test the DP-z algorithm based on the cloud computing platform，the experiments show that DP-z can achieve higher per-
formance at speed without reducing the accuracy．
Key words: clustering; distributed computing; cloud computing; z-order curve; density peaks
．
域得到广泛应用
1
引言
《Science》
发表于
学术期刊的密度峰值聚类算法
( Density Peaks Clustering，DPC) ［4］
聚类分析是数据挖掘和模式识别等领域广为研究
一个新型的基于密度
．
的问题之一 它将数据库中的数据分割成不同的族
． ，
的聚类算法 由于该算法能够发现任意形状的聚类 也
(
) ，
类
并使族内数据之间的相似性比族间数据之间的
［1 ～ 3］
;
不依赖于数据集的维度 算法的实现过程只需要计算
．
相似性大 大量聚类分析算法
、
在社会网络分析 统
(
)
出每个点密度值 ρ 由某一范围内点的个数来刻画 和
、
、
、Web
计数据分析 智能商务 图像模式识别
搜索等领
: 2016-10-31;
: 2017-05 － 31;
:
收稿日期
修回日期
责任编辑 梅志强
:
( No． 2015020010) ;
( No． LR2015045) ;
河北省自然科学基金青年基金
基金项目 辽宁省自然科学基金
辽宁省高等学校优秀科技人才支持计划
( No． F2015201140)
731
3
:
z
第
期
卢
晶 基于 值的分布式密度峰值聚类算法
(
DPC
EDDPC
，
做简要介绍 并对其中存在
斥群值 δ 与密度值比自己大的点的距离的最小值刻
本节对
和
) ， ．
不需要多次迭代 重要的是该算法不必事先指定
、
的复杂度高 计算量大等问题进行简要分析
．
画
，
．
聚类个数 而是用户根据每个点的两个属性值而决定
2． 1
密度峰值聚类算法简介
S = { x }
N
．
密度峰值聚类算法拥有以上优点而被广泛关注
，
S
考虑待聚类的数据集
对于 中的任何
i
i = 1
由于该算法需要计算数据集中所有点对之间距
x ，
密度峰值聚类算法要计算其局部密度 ρ 和
数据点
i
i
，
、
，
离 导致算法执行效率低 降低适用性 尤其高维海量数
．
斥群值 δ 两个属性
i
．
，
据 随着云计算技术的发展 很多算法可以在多台机器
［5］ MapReduce
:
局部密度 ρ
i
，
的分布式环境下执行 文献 基于
计算模
: ED-
=
( d － d )
( 1)
ρ
χ
i
∑
ij
c
j
型提出了一种高效的分布式密度中心聚类算法
1，x ＜ 0
0，x ＞ 0
DPC．
由于其粗略的数据复制方案导致其仍然存在大量
( x) =
其中 χ
{
．
的冗余数据复制和计算开销
d ＞ 0
c
，d
可以根据如下参数估计
参数
为截断距离
c
，
本文在深入分析密度峰值聚类算法的基础上 提
方法［4］来确定 将所有点对的距离从小到大排序的
，
1%
［6］
值
z
( Distrib-
的分布式密度峰值聚类算法
出一种基于
～ 2%
．
处 例如
100
，
个点 共有
4950
，
种组合 将这些组合
uted Density Peaks Clustering based on z-value，DP-z) ，
并
， 50 ～ 100
d
．
值 由式
距离排序 在
处选取某一距离为
c
Hadoop
，
DP-z
在
集群上进行了实验测试 验证
算法在处
( 1)
，
S
x
d
可知 ρ 表示的是 中与 之间的距离小于
的
i
i
c
．
理大规模高维数据上的高效性
DP-z
(
x
) ．
点的个数 不考虑 本身
i
z
算法利用空间 填充曲线将高维数据映射成
i
点 的斥群值 δ 定义为
:
i
Z
，
z
一维空间 轴上的点 根据数据点 值的分布将数据集
= min( d )
( 2)
斥群值 δ 代表与密度值比自己大的点的距离的最
， j ，
小值 假设密度比 ρ 大的点中 点 与点 的距离最近
δ
ij
i
j: ＞
ρj ρi
． ，
分组 将各组数据分给不同的机器进行运算 在组内计
． z
算每个点的密度值 ρ 和斥群值 δ 由于采用 填充曲线
．
i
i
，
对高维数据点进行了降维处理 可能会导致原始数据
= d ( d
i
j
) ，
j
i
那么 δ
代表点 到点 的距离 而点 就是点
i
ij
ij
，
．
的近邻性受损 导致相邻的数据被分到不同的组中 在
［5］， = arg min ( d ) ．
i
说明点 可以
的斥群值依附点 σ
σ
计算分组中每个点密度值 ρ 和斥群值 δ 时可能会用到
i
i
ij
j
S， ＞
ρj ρi
∈
．
，
z
其它组中的数据 对此 本文基于数据点 值携带高维
j
．
，
归属于点 所属聚类 斥群值 δ 越小 这种依附可能性
i
z
空间位置信息的性质提出一种基于 值上下限的数据
，
i
j
越大 说明点 越有可能归属于点 所属的聚类 斥群值
;
，
复制模型和数据分发模型 将其他组内的少量数据复
， i
j
，
，
i
δ 越大 点 距离点 越远 依附关系就越弱 点 越有
i
．
制到本组中 各机器根据分组数据和复制数据进行并
j
，
．
可能与点 不属于同一个聚类 或者是离群点 当某个
，
行计算各点的密度值 ρ 和斥群值 δ 并从理论上保证其
m
，
m
点
的密度值 ρ 是所有点中密度最大值 那么点
m
的
．
正确性
斥群值 δ 则为
m
:
本文的主要贡献如下
DPC
= max ( d )
( 3)
δ
m
j
mj
，
算法进行了分布式扩展 基于
Ma-
① 对原始
，
根据密度值 ρ 和斥群值 δ 可绘制二维决策图 横轴
1( b)
pReduce
z
模型提出基于 值的分布式密度峰值聚类算
，DP-z， Hadoop
，
．
1
，
为密度值 纵轴为斥群值 如图 所示 图
1
为图
．
法
并在开源云计算平台
上实现
( a)
．
，
数据集的决策图 根据图中决策点的分布情况 可
以看出密度值 ρ 和斥群值 δ 都非常大的点分布在决策
，
② 为正确计算 ρ 值 设计基于
d
z
范围内 值最小
c
;
下限和最大上限的复制策略 为正确计算分组内密度
，
，
图中的右上角 将这些点圈出作为聚类中心点 然后根
，
'
最大值点外其他点的全局斥群值 δ 设计基于 δ 范围内
，
据数据集中每个点的 δ 值的依附关系 反推出每个点所
z
;
值最小下限和最大上限的复制策略 为正确计算组内
．
属聚类
，
密度值最大点的全局斥群值 δ 设计基于各组最大密度
” z
值点的 δ 范围内 值下限和上限分发策略
．
③ 在多个数据集上对分布式密度峰值聚类算法进
．
行了多方面 实验评估
2
密度峰值聚类算法及其分布式
Alex Rodriguez
2014
《Science》
年在 上发
由
等人于
． ［5］ ，
表 文献 在此基础上针对算法复杂度高等问题 提
: EDDPC．
出了分布式密度中心聚类算法
全部评论(0)