基于Spark框架的CFSFDP改进算法

doi:10.16180/j.cnki.issn1007-7820.2019.05.008

电子科技 ›› 2019, Vol. 32 ›› Issue (5): 38-44.doi: 10.16180/j.cnki.issn1007-7820.2019.05.008

基于Spark框架的CFSFDP改进算法

李琪,张欣,张平康,张航

贵州大学大数据与信息工程学院,贵州贵阳 550025

收稿日期:2018-04-29 出版日期:2019-05-15 发布日期:2019-05-06
作者简介:李琪(1990-),男,硕士研究生。研究方向:云计算与大数据。|张欣(1976-),男,博士,副教授。研究方向:下一代无线通信及应用等。|张平康(1993-),男,硕士研究生。研究方向:图像处理。|张航(1991-),男,硕士研究生。研究方向:云计算与大数据。
基金资助:
国家国际科技合作专项项目(2014DFA00670);贵州省研究生教育教学改革重点(课题黔教研合JG字[2016]15);贵州省科技厅工业攻关项目(黔科合GY字[2010]3056)

Improved CFSFDP Algorithm Based on Spark Framework

LI Qi,ZHANG Xin,ZHANG Pingkang,ZHANG Hang

School of Big Data and Information Engineering,Guizhou University,Guiyang 550025,China

Received:2018-04-29 Online:2019-05-15 Published:2019-05-06
Supported by:
International Science & Technology Cooperation Program of China(2014DFA00670);Postgraduate Education Reform Project of Guizhou Province(课题黔教研合JG字[2016]15);Key Industry Project of Guizhou Science and Techonology Agency(黔科合GY字[2010]3056)

摘要/Abstract

摘要：

CFSFDP算法是一种基于密度的新型聚类算法。文中针对算法需使用决策图人工选取聚类中心点的问题,利用斜率思想找出聚类中心点与非聚类中心点间的分界点,在消除主观误差的同时实现了中心点的自动求取,并最终将算法使用Spark框架进行了并行化实现。实验结果表明,文中算法在消除人为误差的同时提升了算法效率,且并行后的算法具有良好的加速比与扩展性,适用于海量数据的聚类分析。

关键词: Spark, CFSFDP算法, 决策图, 密度峰值, 聚类, 并行化

Abstract:

CFSFDP algorithm based on density is a clustering algorithm. In order to rid dependency on artificial selection of decision graph, this paper used the idea of slope to calculate the demarcation point of clustering center points and un-clustering center points. This improvement eliminated personal equation and realized auto-calculation of center points. Parallel processing for the algorithm was conducted through the Spark framework. The experiments showed that this algorithm was applicable to clustering analysis of mass data, since it improved efficiency by eliminating personal equation and displayed great speed up ratio and extendibility after paralleling.

Key words: Spark, CFSFDP algorithm, decision diagram, density peaks, clustering, parallel

中图分类号:

TP301.6

李琪,张欣,张平康,张航. 基于Spark框架的CFSFDP改进算法[J]. 电子科技, 2019, 32(5): 38-44.

LI Qi,ZHANG Xin,ZHANG Pingkang,ZHANG Hang. Improved CFSFDP Algorithm Based on Spark Framework[J]. Electronic Science and Technology, 2019, 32(5): 38-44.

图/表 12

图1

图2

图3

图4

图5

图6

表1

图7

表2

图8

图9

图10

参考文献 16

[1]	孙吉贵, 刘杰, 赵连宇 . 聚类算法研究[J]. 软件学报, 2008,19(1):48-61.
	Sun Jigui, Liu Jie, Zhao Lianyu . Clustering algorithms research[J]. Journal of Software, 2008,19(1):48-61.
[2]	Jain A K, Dubes R C . Algorithms for clustering data[M]. New Jersy:Prentice Hall, 1988.
[3]	Zaharia M, Chowdhury M, Franklin M J, et al. Spark: cluster computing with working sets[C]. USENIX Association:Usenix Conference on Hot Topics in Cloud Computing, 2010.
[4]	Dean J, Ghemawat S . MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008,51(1):10-17.
[5]	Engle C, Lupher A, Xin R, et al. Shark:fast data analysis using coarse-grained distributed memory[C]. Scottsdale:ACM SIGMOD International Conference on Management of Data,ACM, 2012.
[6]	Rodriguez A, Laio A . Clustering by fast search and find of density peaks[J]. Science, 2014,344(6191):1492-1503.
[7]	杨洁, 王国胤, 庞紫玲 . 密度峰值聚类相关问题的研究[J]. 南京大学学报, 2017,53(4):791-801.
	Yang Jie, Wang Guoyin, Pang Ziling . Relative researches of clustering by fast search and find of density peaks[J]. Journal of Nanjing University, 2017,53(4):791-801.
[8]	蒋礼青, 张明新, 郑金龙 , 等. 快速搜索与发现密度峰值聚类算法的优化研究[J]. 计算机应用研究, 2016,33(11):3251-3254.
	Jiang Liqing, Zhang Mingxin, Zheng Jinlong , et al. Optimization of clustering by fast search and find of density peaks[J]. Application Research of Computers, 2016,33(11):3251-3254.
[9]	李敏, 张桂珠 . 密度峰值优化初始中心的K-means算法[J]. 计算机应用与软件, 2017,34(3):212-217.
	Li Min, Zhang Guizhu . K-means algorithm of optimized initial center by density peaks[J]. Computer Applications and Software, 2017,34(3):212-217.
[10]	Wang S, Wang D, Li C , et al. Clustering by fast search and find of density peaks with data field[J]. Chinese Journal of Electronics, 2016,25(3):397-402. doi: 10.1049/cje.2016.05.001
[11]	孙昊, 张明新, 戴娇 , 等. 基于网格的快速搜寻密度峰值的聚类算法优化研究[J]. 计算机工程与科学, 2017,39(5):964-970.
	Sun Hao, Zhang Minxing, Dai Jiao , et al. Optimization of grid based clustering by fast search and find of density peaks[J]. Computer Engineering & Science, 2017,39(5):964-970.
[12]	戴娇, 张明新, 郑金龙 , 等. 基于密度峰值的快速聚类算法优化[J]. 计算机工程与设计, 2016,37(11):2979-2984.
	Dai Jiao, Zhang Minxing, Zheng Jinlong , et al. Optimization of fast clustering algorithm based on density peaks[J]. Computer Engineering and Design, 2016,37(11):2979-2984.
[13]	张天宇, 谌志群, 黄孝喜 , 等. 基于改进CFSFDP算法的电信投诉文本聚类方法[J]. 电子科技, 2017,30(10):93-96.
	Zhang Tianyu, Chen Zhiqun, Huang Xiaoxi , et al. Clustering method for telecom complaints text based on improved CFSFDP algorithm[J]. Electronic Science and Technology, 2017,30(10):93-96.
[14]	张文开 . 基于密度的层次聚类算法研究[D]. 合肥:中国科学技术大学, 2015.
	Zhang Wenkai . Research on density-based hierarchical clustering algorithm[D]. Hefei:University of Science and Technology of China, 2015.
[15]	马春来, 单洪, 马涛 , 等. 一种基于CFSFDP改进算法的重要地点识别方法研究[J]. 计算机应用研究, 2017, 34(1):136-140.
	Ma Chunlai, Shan Hong, Ma Tao , et al. Research on important places identification method based on improved CFSFDP algorithm[J]. Application Research of Computers, 2017,34(1):136-140.
[16]	Rong C . Using mahout for clustering wikipedia's latest articles:a comparison between K-means and fuzzy C-means in the cloud[C]. Athens:IEEE Third International Conference on Cloud Computing Technology and Science, IEEE Computer Society, 2011.

数据集	样本数	类别数	维度
Iris	150	3	4
Wine	178	3	13
R15	600	15	2
Aggregation	788	7	2

数据集	B_n值	分界点
Iris	0.57	3
Wine	0.76	3
R15	3.55	15
Aggregation	1.21	7

基于Spark框架的CFSFDP改进算法

Improved CFSFDP Algorithm Based on Spark Framework

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 16

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	金霄,吴飞,鄢松,陆雯霞,张忠艺. 基于GAWK-means的地铁车站指纹定位方法[J]. 电子科技, 2022, 35(2): 34-39.
[2]	徐航帆,刘丛,唐坚刚,彭敦陆. 改进地标点采样的加速谱聚类算法[J]. 电子科技, 2021, 34(5): 47-53.
[3]	杨珊珊,张大兴,郭家伟,王诗迢. 结合关键点和块优点的复制粘贴检测算法[J]. 电子科技, 2020, 33(3): 38-43.
[4]	缪冉,李菲菲,陈虬. 基于卷积神经网络与多尺度空间编码的场景识别方法[J]. 电子科技, 2020, 33(12): 54-58.
[5]	张长青,杨楠. 基于车联网大数据分析的实时路况检测系统[J]. 电子科技, 2019, 32(8): 66-70.
[6]	蓝机满. 基于云计算的数据挖掘系统设计[J]. 电子科技, 2019, 32(8): 70-74.
[7]	李媛. 分布式手机信令数据采集与分析技术研究[J]. 电子科技, 2019, 32(6): 78-81.
[8]	章裕润,吴飞,毛万葵. 基于WiFi-GM指纹的室内定位算法[J]. 电子科技, 2019, 32(5): 49-54.
[9]	孙悦,袁健. 基于Spark的改进随机森林算法[J]. 电子科技, 2019, 32(4): 60-64.
[10]	向志华,邵亚丽. 一种结合贪心选择和特征加权的高维数据聚类算法[J]. 电子科技, 2019, 32(11): 70-73.
[11]	于慧,王宇嘉,陈强,肖闪丽. 基于多种群动态协同的多目标粒子群算法[J]. 电子科技, 2019, 32(10): 28-33.
[12]	潘迪. 基于DBSCAN与梯度划分的Kinect障碍物轮廓检测算法[J]. 电子科技, 2019, 32(1): 86-90.
[13]	梅凯, 火久元, 常扣扣. 并行人工蜂群算法研究[J]. , 2018, 31(1): 20-.
[14]	滕泉 1，沈景凤 1，徐斌 2，王玮玮 3. 基于贪婪算法的旅游路线优化问题[J]. , 2017, 30(9): 142-.
[15]	李根，王亚刚，周小伟，张凤登. 一种基于密度均值的谱聚类算法[J]. , 2016, 29(8): 74-.