![](https://csdnimg.cn/release/download_crawler_static/18268884/bg1.jpg)
收稿日期:20180424;修回日期:20180611 基金项目:国家自然科学基金资助项目(61672265);七二所青年创新基金资助项目(J775)
作者简介:孙伟鹏(1990),男,江苏连云港人,硕士研究生,主要研究方向为数据挖掘、云计算(sunwp244372610@163.com);吴锡生(1959),
男,教授,硕导,博士,主要研究方向为人工智能、模式识别、云计算;孟斌(1980),男,高级工程师,硕士研究生,主要研究方向为数据挖掘.
基于 Spark并行的密度峰值聚类算法
孙伟鹏
1
,吴锡生
1
,孟 斌
2
(1.江南大学 物联网工程学院,江苏 无锡 214122;2.中船重工集团第七二研究所 软件工程中心,江苏 无
锡 214082)
摘 要:针对 FSDP聚类算法在计算数据对象的局部密度与最小距离时,由于需要遍历整个数据集而导致算法
整体时间复杂度较高的问题,提出了一种基于
Spark的并行 FSDP聚类算法 SFSDP。首先,通过空间网格划分将
待聚类数据集划分成多个数据量相对均衡的数据分区;然后,利用改进的
FSDP聚类算法并行地对各个分区内
的数据执行聚类分析;最后,通过将分区间的局部簇集合并,生成全局簇集。实验结果表明,SFSDP与 FSDP算法
相比能够有效地进行大规模数据集的聚类分析,并且算法在准确性和扩展性方面都有很好的表现。
关键词:聚类;密度峰值;空间划分;并行;Spark
中图分类号:TP301.6 文献标志码:A 文章编号:10013695(2020)01034016304
doi:10.19734/j.issn.10013695.2018.04.0377
Sparkbasedparalleldensitypeakclusteringalgorithm
SunWeipeng
1
,WuXisheng
1
,MengBin
2
(1.SchoolofIoTEngineering,JiangnanUniversity,WuxiJiangsu214122,China;2.SoftwareEngineeringCenter,ChinaShipScientific
ResearchCenter
,WuxiJiangsu214082,China)
Abstract:InviewoftheproblemthattheoveralltimecomplexityoftheFSDPclusteringalgorithmwashighbecausethealgo
rithmneededtotraversetheentiredatasetwhencalculatingthelocaldensityandminimumdistanceofdataobjects
,thispaper
presentedaSparkbasedparallelFSDPclusteringalgorithmcalledSFSDP.First,thealgorithmdividedthedatasetintomultiple
datapartitionswithrelativelyequalsizebyspatialmeshing.Then,itusedtheimprovedFSDPclusteringalgorithmtoperform
theclusteringanalysisonthedataineachpartitionparallelly.Itgeneratedtheglobalclustersbygroupingtogetherlocalclusters
betweenpartitions.ExperimentalresultsshowthatSFSDPalgorithmcaneffectivelyperformlargescaledatasetclusteringanaly
siscomparedwithFSDPalgorithm,andthealgorithmhasagoodperformanceintermsofaccuracyandscalability.
Keywords:clustering;densitypeak;spacedivision;parallel;Spark
随着互联网在全球范围内的快速普及,人们每天都会面对
来自社会、商业、医学、工程和科学以及日常生活中各个方面的
海量数据。数据的爆炸式增长、广泛可用和巨大规模把人们带
入了一个真正的数据时代。而如何快速方便地从这些杂乱无
章的大规模数据中挖掘出有用的信息,并将这些非结构化的数
据转变成知识,这种需求催生了数据挖掘的诞生
[1]
。在数据挖
掘领域中,聚类分析作为一种常用的数据分析方法,可以在对数
据对象集的相关信息一无所知的情况下,将数据对象集合划分
成多个簇,使得同一个簇中的对象彼此相似,但与其他簇中的对
象不相似
[2]
。迄今为止,国内外众多研究人员针对各类应用场
景已经提出了各式各样的聚类算法
[3]
,使得聚类分析的研究得
到了很大的发展。在现实生活中,聚类分析早已被广泛应用于
多个领域中,包括网页搜索、决策分析、图像模式识别、文档摘要
自动生成、自然语言处理、商务智能、生物学与安全等。
FSDP(clusteringbyfastsearchandfindofdensitypeaks)作
为一种新的基于密度的聚类算法
[4]
,将具有较大局部密度且
互相距离较远的数据对象作为聚类中心,然后将每一个非中心
数据对象沿着密度递增的最近邻方向迭代划分给相应的聚类
中心,实现聚类划分。该算法被提出后得到了大量研究人员的
关注
[5~8]
,虽然 FSDP算法具有算法原理简单,可以发现任意形
状、大小的聚簇等优点,但由于 FSDP算法在计算数据集中数据
对象的局部密度和最小距离的时间复杂度较高,聚类的效率相
对较低,所以该算法不能很好地适用于大规模数据的聚类。
针对
FSDP算法在进行海量、高维度数据聚类时存在效率
低、伸缩性差的问题,本文提出了一种基于 Spark的并行 FSDP
聚类算法 SFSDP。
1 相关工作
11 FSDP算法
FSDP算法认为聚类的中心应该同时具备以下两个特点:
a)聚类中心相对于包围它的数据对象密度要大,即聚类中心
被局部密度较低的邻居包围;b)聚类中心与任何具有更高局
部密度对象之间的距离较远。对于数据集中每个数据点,需要
计算数据点的局部密度
ρ
i
与具有更高局部密度数据点的最小
距离
δ
i
(下文简称为最小距离
δ
i
)两个变量。其中局部密度
ρ
i
定义为
ρ
i
=
∑
j
e
-(
d
ij
d
c
)2
(1)
其中:d
ij
表示数据点 i与 j之间的距离;d
c
表示截断距离。
最小距离
δ
i
表示的是数据点 i与任何其他具有更高局部
密度数据点之间的最小距离,其定义为
δ
i
=
min
j:
ρ
j
>
ρ
i
(d
ij
) i
≥
1
max
j
(d
ij
)
ρ
i
=max(
ρ
)
(2)
通过计算数据集中所有数据点的局部密度
ρ
i
和最小距离
第 37卷第 1期
2020年 1月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No1
Jan.2020