![](https://csdnimg.cn/release/download_crawler_static/18270995/bg1.jpg)
收稿日期:20190830;修回日期:20190921 基金项目:国家自然科学基金资助项目(61966035,61562086);新疆维吾尔自治区教育
厅创新团队项目(
XJEDU2016S035)
作者简介:赵鑫(1994),男,河南新乡人,硕士研究生,主要研究方向为数据挖掘;汪丽娟(1994),女,甘肃定西人,硕士研究生,主要研究方向
为流式数据处理;行艳妮(1994),女,陕西渭南人,硕士研究生,主要研究方向为数据挖掘;赵邁(1993),女,新疆克拉玛依人,硕士研究生,主要研
究方向为时空数据索引、遥感图像处理;赵京霞(1995),女(满族),内蒙古锡林浩特人,硕士研究生,主要研究方向为图像处理;钱育蓉(1980),女
(通信作者)(满族),山东德州人,教授,博士,主要研究方向为网络计算和遥感图像处理(qyr@xju.edu.cn).
改进的 CKmeans优化及并行策略
赵 鑫
1
,汪丽娟
1
,行艳妮
1
,赵 邁
2
,赵京霞
1
,钱育蓉
1
(1.新疆大学 软件学院,乌鲁木齐 830091;2.新疆大学 信息科学与工程学院,乌鲁木齐 830046)
摘 要:针对大数据背景下 Kmeans存在选取质心导致的局部最优解、聚类速度慢的问题,提出一种 Flink平台
下的 CKmeans聚类优化及并行策略。从算法优化层面,采用 Canopy算法确定聚类数目 k并选取初始质心;从
并行化加速层面,基于
Flink平台设计了一种面向 CKmeans的并行加速策略,并分析不同并行度对计算耗时的
影响。经实验,相较于
Kmeans算法,CKmeans算法的准确率与迭代次数间的比值更高,算法性能更优,在 iris
数据集中性能比提升 44.79%,在 wine数据集中性能比提升 32.03%;同时证明了不同并行度下 CKmeans算法
的聚类耗时呈现先下降后上升的趋势,其聚类耗时的最小值与数据集的大小相关。
关键词:大数据;加速策略;内存计算;并行化;聚类算法
中图分类号:TP391 文献标志码:A 文章编号:10013695(2020)11017328705
doi:10.19734/j.issn.10013695.2019.08.0284
OptimizationandparallelstrategyofimprovedCKmeans
ZhaoXin
1
,WangLijuan
1
,XingYanni
1
,ZhaoYi
2
,ZhaoJingxia
1
,QianYurong
1
(1.CollegeofSoftware,XinjiangUniversity,Urumqi830091,China;2.CollegeofInformationScience&Engineering,XinjiangUniversity,
Urumqi830046,China)
Abstract:Underthebackgroundofbigdata,Kmeanshaslocaloptimumsolutionandslowclusteringspeedcausedbychoo
singcentroid.ThepaperdevelopedanewclusteringoptimizationandparallelalgorithmCKmeansbasedonKmeans.Foralgo
rithmoptimization
,Canopyalgorithmcoulddeterminethenumberofclusterskandselecttheinitialcentroid.Forparallelization
acceleration,FlinkplatformcouldhelptodesignaparallelaccelerationstrategyforCKmeans.Italsocouldanalyzetheimpact
ofdifferentparallelismdegreesoncomputingtimeconsuming.ExperimentsshowthatCKmeansalgorithmhashigheraccuracy
andbetterperformance.Theperformanceratiointheirisdatasetisincreasedby44.79%,andtheperformanceratiointhe
winedatasetisimprovedby32.03%.TheclusteringtimeofCKmeansalgorithmunderdifferentparallelismdegreesdecreases
firstandthenrises
,andtheminimumclusteringtimeisrelatedtothesizeofthedataset.
Keywords:bigdata;accelerationstrategy;memorycomputing;parallelization;clusteringalgorithms
随着数据量的增长,对存储一体性能的大数据处理框架的
需求也随之增长,如 Hadoop、Spark
[1,2]
等典型的大数据批处理
框架虽然吞吐量大,但数据处理实时性较低。因此,近年来涌
现出 了 一 大 批 实 时 计 算 系 统
[3~5]
,如 ApacheFlink
[6~10]
、
ApacheStorm、JStorm、Heron、SparkStreaming等。其中,Apache
Flink是一个集流处理与批处理于一体的开源大数据计算框架,
它具有低延迟、高容错的特性。目前,机器学习算法在大数据领
域的应用越来越多,而
Kmeans算法作为典型的机器学习算法,
在大数据领域的应用更是十分广泛,但当前的 Kmeans结合大
数据的研究大多数基于批量计算框架下进行
[11~13]
,在流计算
框架下的研究较少。而当前部分流计算框架也支持机器学习算
法,如流计算框架
Flink支持机器学习库 FlinkML。因此,针对流
计算环境下 Kmeans算法存在迭代次数多、计算耗时长等问题,
结合大数据处理框架 Flink实时性的优势,提出一种基于 Flink
平台对 Canopy算法改进的 Kmeans算法作并行化加速,提高 K
means
算法的聚类速度。本文所做的工作如下:
a)为避免聚类结果陷入局部最优解,本文基于 Canopy算
法选择聚类初始质心及聚类数目 k。用 Canopy算法将原始数
据集聚成多个类,即生成多个 Canopy,每一个 Canopy代表一个
类,生成的
Canopy数量即为聚类算法的 k值,并在每个 Canopy
中选择一个质心或距中心值最近的点作为初始质心。
b)基于 Flink平台对改进后的 Kmeans算法作并行计算。
首先,用 HDFS将大规模数据集划分成多个小的数据集;其次,
对每一个数据子集作聚类计算,从而降低数据获取阶段及聚类
计算阶段的耗时;最后,分析随着并行度增加对任务各阶段计
算耗时的影响。
1 相关技术
11 ApacheFlink
ApacheFlink是一个由两类节点构成的开源分布式流式
处理框架,分别是:
a)主控节点,它是运行 FlinkjobManager的
后台服务节点,
jobManager是 Flink计算集群的核心,负责任务
调度(schedulingtasks)、管理检查点(managingcheckpoints)以
及错 误 恢 复 (failurerecovery)等,在 Flink中 的 地 位 相 当 于
storm中的 nimbus;b)计算节点,它是运行 FlinktaskManager后
台服务的节点,taskManager负责监听 jobManager分配的任务,
并在一个 JVM进程内用一个或者多个线程,在 Flink中的地位
相当于 storm中的 supervisor。Flink的计算框架可抽象为一种
第 37卷第 11期
2020年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No11
Nov.2020