论文部分内容阅读
K-Means作为机器学习算法的典型代表,在大数据背景下的应用十分广泛,但其存在随机选取初始质心导致的局部最优解、大数据规模下迭代次数多、计算耗时长、准确率低等问题。在大数据背景下,基于大数据计算框架的机器学习算法优化与应用研究已成为研究热点问题,当前很多大数据计算框架都包含机器学习库,且随着实时搜索引擎、社交软件等应用的出现,数据实时处理日益成为学者们的研究热点,传统的先存储后计算的批量计算理念已经不再适用于实时流数据的处理,因此如何构造高吞吐、低延迟的大数据流式计算框架成为亟待解决的关键问题。基于上述存在的问题,本研究从基于Flink平台的K-Means算法的优化、并行化加速以及Flink平台的任务调度策略方面进行研究。具体研究内容可概括如下:(1)为解决大数据规模下K-Means存在选取质心导致的局部最优解、聚类速度慢的问题,提出一种Flink平台下的CK-Means聚类优化及并行策略。从算法优化层面,采用Canopy算法确定聚类数目k并选取初始质心;从并行化加速层面,基于Flink平台设计了一种面向CK-Means的并行加速策略,并分析不同并行度对计算耗时的影响。经试验,相较K-Means算法,CK-Means算法的准确率与迭代次数间的比值更高,算法性能更优;不同并行度下的CKMeans算法的聚类耗时呈现先下降后上升的趋势,其聚类耗时的最小值与数据集的大小相关。(2)为提高K-Means算法的聚类速度和准确率,提出了基于k-d树分区的K-Means并行化加速策略。从算法优化层面,选择数据集中相距最远的k个点优化初始质心;从任务并行化加速层面,提出k-d树分区算法对数据集进行划分并实现任务并行化;从执行环境并行化加速层面,设置不同进程数目与CPU核数验证F-KMeans的加速效果。(3)为了提高Flink计算框架的资源利用率,提出了基于Flink流式计算环境下资源感知任务调度策略。针对Flink平台下先来先服务任务调度算法忽略了任务资源需求与节点可用资源之间的关系,导致不同节点任务负载不均,从而影响系统吞吐量的问题,提出了基于Flink流式计算环境下资源感知任务调度策略。首先,以GlobalState模块监测的资源数据为依据,考虑任务资源需求与节点可用资源间的匹配关系,提出一种任务选择算法与节点选择算法选取待执行任务与最佳调度节点;其次,通过资源感知调度策略把待执行任务调度至最佳调度节点;最后,通过设计实验验证了算法的有效性。