1、2023 年第 10 期计算机与数字工程收稿日期：2023年4月18日，修回日期：2023年5月27日作者简介：李召鑫，男，硕士研究生，研究方向：工业大数据。孟祥印，男，副教授，硕士生导师，研究方向：智能制造与工业大数据。肖世德，男，教授，博士生导师，研究方向：智能机电一体化技术与工业大数据。胡锴沣，男，硕士研究生，研究方向：工业大数据。赖焕杰，男，硕士研究生，研究方向：图像处理及机器视觉。1引言进入到新世纪以来，伴随着科学技术的飞速发展，在各个领域每时每刻都在产生成千上万的数据，如何能高效地从这些海量数据中提取出有应用价值的信息已成为当前的研究热点。K-means是数据挖掘技术中解决海量数据
2、聚类问题的经典算法1，因其存在执行快速、易于并行化等优点故在许多领域都得到了广泛的应用。但同时存在一些不足：需指定聚类中心数；初始聚类中心的选取策基于Flink框架的K-means算法优化及并行计算策略李召鑫孟祥印肖世德胡锴沣赖焕杰（西南交通大学机械工程学院成都610031）摘要K-means算法因其原理简单和聚类效果尚佳的优点在机器学习和数据挖掘领域得到广泛使用，但其仍存在一些缺点：K-means算法需指定分类类别数K；K-means算法对于初始聚类中心的选取策略是随机选择，这可能会影响到最终聚类结果的准确率及计算速度。以上缺点都限制了K-means算法的计算效率的进一步提升。论文针对以上问
3、题，提出了一种基于Flink并行化的K-means优化算法，该算法在传统K-means算法的基础上引入Canopy算法来完成初始聚类，得到类别数K，然后采用最大距离算法来计算初始聚类中心，并利用Flink框架的并行计算能力，对多个数据集进行聚类实验。实验结果表明，论文算法可以减少聚类过程迭代次数，并且在聚类准确率方面也有一定的提高，在大规模数据集环境下同样具有良好的计算效率。关键词Flink；K-means算法；Canopy算法；并行化中图分类号TP301.6DOI：10.3969/j.issn.1672-9722.2023.10.003K-means Algorithm Optimizati
4、on and Parallel Computing StrategyBased on Flink FrameworkLI ZhaoxinMENG XiangyinXIAO ShideHU KaifengLAI Huanjie（School of Mechanical Engineering，Southwest Jiaotong University，Chengdu610031）AbstractK-means algorithm is widely used in the field of machine learning and data mining because of its simpl
5、e principleand good clustering effect，but it still has some shortcomings：K-means algorithm needs to specify the number of classification categories K.K-means algorithm selection strategy for the initial clustering center is random selection，which may affect the accuracyand calculation speed of the f
6、inal clustering results.The above shortcomings all limit the improvement of the calculation efficiency ofthe K-means algorithm.To solve the above problems，this paper proposes a K-means optimization algorithm based on Flink parallelization.This algorithm introduces the Canopy algorithm on the basis o
7、f the traditional K-means algorithm to complete the initial clustering，and obtains the number of categories K，and then uses the maximum distance algorithm to calculate the initial clustering center，and uses the parallel computing power of the Flink framework to perform clustering experiments on mult
8、iple data sets.The experimental results show that the algorithm in this paper can reduce the number of iterations of the clustering process，and also has acertain improvement in the accuracy of clustering.It also has good computational efficiency in the environment of large-scale datasets.Key WordsFl
9、ink，K-means algorithm，Canopy algorithm，parallelClass NumberTP301.6总第 408期2023 年第 10 期计算机与数字工程Computer&Digital EngineeringVol.51No.102231第 51 卷略是完全随机，这可能会影响到最终聚类结果的准确 率 及 计 算 速 度。这 两 种 缺 点 严 重 限 制 了K-means算法聚类效果和计算效率的提高。针对传统K-means算法存在的不足，许多研究人员都提出了各种改进算法，主要是对于聚类中心数的确定及聚类中心的选择策略的优化。杜佳颖等2提出了一种基于 K-mea
10、ns+算法优化初始中心点选择的改进算法，通过计算平均轮廓系数来指定K值，该算法有效提高了计算效率；李淋淋等3提出了一种基于 Spark 平台的 SBTICK-means 算法，针对传统K-means算法在大规模数据计算时存在的瓶颈，引入Canopy算法和三角形不等式定理，显著提高了聚类结果速度及准确率，并具有良好的扩展性；梁彦4提出了一种基于Spark平台的并行K-means算法和Canopy K-means算法，该算法并行化后具有较好的聚类效果，相比于Hadoop平台，具有更高的效率；许明杰等5提出一种Spark并行化的PSOK-means算法，将PSO算法与K-means算法相结合，利用改
11、进后的PSO算法提高K-means的全局搜索能力，并在Spark框架上进行了实现，通过疾病检测数据进行聚类实验来验证所提出算法的效率；王义武等6提出了一种OCC K-means算法，采用最大最小距离算法和UPGMA来筛选初始中心，并基于Spark框架进行实现，有效提高了聚类精度及和计算速度。王美琪等7提出一种 APMMD 算法，通过近邻传播算法获取候选中心点，然后利用最大最小距离算法再选取k个初始中心点，该算法有效减少了迭代次数。Apache Flink811是近年来新兴的一个大数据处理框架，与Hadoop不同，Flink是一个集批处理和流处理于一体的计算框架，具有同时支持高吞吐、低延迟、高性
12、能的优点，现在的绝大部分聚类算法并行化研究大都基于批处理框架，如 Hadoop、Spark1213等，而基于Flink实现的聚类算法研究较少。基于以上预研究，本文综合上述聚类优化算法的优点，充分利用Flink框架在计算方面的优势，提出一种基于Flink框架对K-means优化算法进行并行化加速的方案，有效提升了K-means算法的聚类速度。2相关理论和技术2.1K-means算法K-means算法14（又称为K-均值算法）是MacQueen在1967年提出的一种基于划分的聚类算法，因其算法思想简单且易于实现被广泛应用于数据挖掘领域。该算法的作用将数据集S中的n个点划分到 K个类中，具体操作步骤
13、如下：先从数据集 S中随机抽取 K 个点作为初始聚类中心 C（C1，C2，Ck），然后计算数据集中每个样本点X到每个聚类中心的距离（一般采用欧式距离15式（1）作为度量）。d()xy=()x1y12+()x2y22+()xnyn2（1）其中：d表示两个样本点间的距离，n为数据集的维度数量。以此作为分类依据，按照最近距离公式将数据集中的各个样本点X分配给距离最近的聚类中心C（C1，C2，Ck），随即更新每个聚类中心的值，设为其类别所有样本的平均值，这个过程会不断迭代直到达到迭代次数或聚类算法的误差达到设定的阈值。在聚类算法中，我们通常使用SSE（The sum ofsquares due to
14、error）即误差平方和来表示聚类的误差大小，根据此值的大小来决定迭代是否结束。其公式如下：SSE=i=1kXS|Xpi|2（2）其中：K为聚类类别数，X为数据集中的一个数据点，p为一个聚类中心。2.2Aphche FlinkFlink是Apache基金会旗下的一个开源的分布式计算框架，可同时支持流处理和批数据处理。Flink和Spark在架构上有一定的相似性，都是基于Master-Slave架构，并且支持内存计算。Flink的数据流执行图包含以下三个阶段（如图 1 所示）：Source、Transformation和Sink。其中，Source阶段的作用是用来加载数据集，Transforma
15、tion阶段的作用是利用各种算子对数据流进行相应处理，主要包括map、flatMap、keyBy、reduce等算子，Source和Transformation 的并行度可以通过 setParallelism 函数进行自定义设置。Sink阶段负责数据处理结果的输出，其并行度为1。图1Flink框架工作架构图李召鑫等：基于Flink框架的K-means算法优化及并行计算策略22322023 年第 10 期计算机与数字工程3基于 Flink 的 K-means 算法优化策略3.1聚类类别K值的确定K-means算法需要指定聚类类别数K，K的取值将直接影响到最终的聚类结果及准确率，所以预先得到合适的
16、K值显得尤为重要。Canopy算法16是McCallum在2000年提出的一种聚类算法，该算法目的是将整个数据集粗略地划分为不同的类别，优点是不用预先设定K值就可以完成粗聚类，因此可用于K-means聚类之前，将粗聚类结果的结果作为K-means的参照，避免了K值选择的盲目性，从而提高聚类速度。其流程如图2所示。图2Canopy算法确定K值流程图3.2初始聚类中心的确定初始聚类中心的理想状态是分布尽量分散，这样可以降低聚类结果陷入局部最优的概率，而且可以提高计算效率。本文关于聚类中心的指定是基于最大距离算法进行实现的，其基本思想如下，先输入数据集和类别数量K，然后随机选取一个数据点作为聚类中心
17、，在选取剩下的 K-1 个聚类中心时，通过比较数据集中的数据与已被选取的聚类中心的距离来找到最大距离dmax所对应的数据点，然后将该点加入聚类中心，最终得到所有的聚类中心。这种方法可以解决K-means算法随机选取聚类中心时聚类中心过于邻近的问题，从而减少迭代次数，有效提高算法效率。算法流程如图3所示。图3最大距离算法确定聚类中心流程图3.3基于Flink的K-means优化算法并行化实现Flink计算框架本身支持并行计算，其并行度指的是同时运行的线程的个数，通常一个Flink程序由多个任务组成，这根据用户设定的分组及并行度来确定。Flink集群中的每个 TaskManager都包括多个slo
18、t，每个TaskManager所拥有的slot数量代表了该TaskManager具有的并发执行能力，此参数可以通过 taskmanager.numberOfTaskSlots参数来进行设置，通常与该节点 CPU 可用核数成正比。Flink 在某些条件下可以减少节点之间通信的开销，是基于一种叫做任务链的技术来进行实现的，当多个算子设置了相同的并行度，而且是 one toone操作，这样相连的算子可以链接在一起形成一个task，算子之间通过本地转发（local forward）进行连接，其逻辑视图、并行化视图、优化后视图如图4所示。图4Flink任务链示意图2233第 51 卷本文算法所采取并行化
19、策略如下，首先，在JobManager节点获取到数据集之后，将其广播到每个TaskManager节点，采用最大距离算法逐次选取K个初始聚类中心，再通过withBroadcastSet函数将初始聚类中心的信息广播到各个 TaskManager 节点，在节点上迭代执行K-means算法，最后根据设置的迭代次数或者损失函数SSE来判断是否结束聚类过程。Flink程序分为 Source、Transformation、Sink三个阶段，其中Source和Transformation阶段是可以实现并行化的，通过并行化来减少数据加载及数据计算的过程，从而提高Flink程序整体的运行速度。JobManager
20、主节点的作用是获取数据集，并通过广播分发至每个 TaskManager，然后 TaskManager迭代计算聚类中心到数据集中每个点的距离，将每一个数据点都归类到一个类别，最后将计算结果返回给JobManager，完成聚类结果的输出。4实验环境与结果分析4.1实验环境与数据集本文实验平台采用开源Flink分布式框架，分别安装在5台虚拟机上，由一台JobManager和4台TaskManager组成。每一台机器的配置都是：内存2GB，硬盘 20G，操作系统均为 Centos 7.4。每一台机器的软件环境如表1所示。表1集群主要软件环境详情名称JDKHadoopFlink软件版本1.8.0_212
21、3.1.31.10.1本文实验采用的数据集是从加州大学UCI实验室提供的机器学习数据库中下载的iris、glass和wine数据集，数据集详情如表2所示。表2数据集相关信息数据集irisglasswine类别数363属性数4913样本数1502141784.2实验结果分析4.2.1准确率实验为了对比传统K-means算法和本文算法的准确率，本文通过对3个不同属性的数据集进行聚类测试（对每种算法进行20次随机实验取平均值），并统计聚类效果，聚类结果如表3和表4所示。从表 3 和表 4 可以看出，本文改进算法在求解 iris、glass和wine数据集时相比传统K-means算法的准确率都有一定的
22、提升，这表明本文基于Canopy算法和最大距离算法的K-means优化算法减少了聚类过程的迭代次数，对计算效率有一定的提升。表3K-means算法与本文改进算法准确率对比数据集irisglasswineK-means算法78.5%69.6%88.2%本文算法85.3%77.4%92.1%表4K-means算法与本文改进算法迭代次数对比数据集irisglasswineK-means算法9128本文算法7954.2.2并行效率实验加速比是衡量并行化程序性能好坏的重要指标，该指标指的是同一个计算任务在单机环境和并行环境运行消耗时间的比值，一般来说，加速比的值越大，代表算法并行加速的性能越好。为了测试
23、本文算法在Flink框架下的并行化能力，本文采用了synthetic_control数据集来进行实验验证，该数据集含有600个样本点，因为原数据集数据量较少，所以本文对原数据集进行了扩展，分别生成了含有3105、3106和3107个样本点的数据集，测试了不同节点数的加速比，实验结果如图5所示。3.532.521.510.50加速比1234节点数310531063107图5基于Flink框架的改进K-means算法的加速比由图5可以看出，当数据量比较小时，随着节点数的增加，加速比折线趋于平缓，因为当数据集的规模较小时，计算时间比较短，如果节点数增加到一定数量后，会使得节点间的数据传输和任务调度等
24、其他方面的时间开销变大，进而降低算法效率。相反，当数据集达到一定规模后，加速比与节点数近似呈线性关系，实验可以表明本文算法在处理大规模的数据时具有较高的计算效率。5结语本文针对传统K-means算法在处理海量数据的过程中在选取初始聚类中心时存在的易陷入局李召鑫等：基于Flink框架的K-means算法优化及并行计算策略22342023 年第 10 期计算机与数字工程部最优解和计算速度较慢等问题，提出一种基于Flink框架并行化的K-means优化算法。该算法采取Canopy算法来计算K-means算法输入所必需的K值，并利用最大距离算法优化初始聚类中心的选择，最后，基于Flink并行计算框架进
25、行实现。实验结果表明，相比原算法，本文算法在聚类准确率和计算效率方面都有一定程度的提升，并且验证了在大规模数据背景下并行化实现的高效性。参 考 文 献1Shengting Wu，Yuling Liu，Jingwen Wang，et al.Sentiment Analysis Method Based on K-means and OnlineTransfer Learning J.Computers，Materials&Continua，2019，60（3）：1207-1222.2杜佳颖，段隆振，段文影，等.基于Spark的改进K-means算法的并行实现 J，计算机应用研究，2020，37（
26、02）：434-436，497.DU Jiaying，DUAN Longzhen，DUAN Wenying，et al.Parallel implementation of improved K-means algorithmbased on SparkJ.Application Research of Computers，2020，37（02）：434-436，497.3李淋淋，倪建成，曹博，等.基于Spark框架的并行聚类算法 J.计算机技术与发展，2017，27（05）：97-101.LI Linlin，NI Jiancheng，CAO Bo，et al.Parallel cluster
27、ing algorithm based on Spark frameworkJ.ComputerTechnology and Development，2017，27（05）：97-101.4梁彦.基于分布式平台Spark和YARN的数据挖掘算法的并行化研究 D.广州：中山大学，2014.LIANG Yan.Research on Parallelization of Data MiningAlgorithms Based on Distributed Platform Spark andYARN D.Guangzhou：Sun Yat-sen University，2014.5许明杰，蔚承建，
28、沈航.基于Spark的并行K-means算法研究 J.微电子学与计算机，2018，35（05）：95-99.XU Mingjie，WEI Chengjian，SHEN Hang.Research onParallel K-means Algorithm Based on SparkJ.Microelectronics and Computer，2018，35（05）：95-99.6王义武，杨余旺，于天鹏，等.基于Spark平台的K-means算法的设计与优化 J.计算机技术与发展，2019，29（03）：72-76.WANG Yiwu，YANG Yuwang，YU Tianpeng，et al
29、.Design and optimization of K-means algorithm based onSpark platformJ.Computer Technology and Development，2019，29（03）：72-76.7王美琪，李建.一种改进K-means聚类的近邻传播最大最小距离算法 J.计算机应用与软件，2021，38（07）：240-245.WANG Meiqi，LI Jian.An improved K-means clusteringalgorithm for the maximum minimum distance of nearestneighbor
30、 propagation J.Computer Applications and Software，2021，38（07）：240-245.8Apache Software Foundation.Apache Flink-stateful computations over data streamsEB/OL.2018-04-10.http：/flink.apache.org/.9Verbitskiy I，Thamsen L，Kao O.When to use a distributed dataflow engine：evaluating the performance ofApacheFl
31、inkC/Proc of IEEE Conferences on Ubiquitous Intelligence&Computing，Advanced and Trusted Computing，Scalable Computing and Communications，Cloud and BigData Computing，Internet of People，and Smart WorldCongress.Piscataway，NJ：IEEE Press，2016：698-705.10Garca-Gil D，Ramrez-Gallego S，Garca S，et al.Acompariso
32、n on scalability for batch big data processingon Apache Spark and Apache FlinkJ.Big Data Analytics，2017，2（1）.11Rashmi C.Analysis of different approaches of parallelblock processing for K means clustering algorithmEB/OL.（2017-03-27）.https：/arxiv.org/abs/1703.08955.12Sakr S.Big data processing stacksJ
33、.IT Professional.2017，19（1）：34-41.13Apache Software Foundation.Apache Spark is a unifiedanalytics engine for large-scale data processingEB/OL.2019-06-09.14孙吉贵，刘杰，赵连宇.聚类算法研究 J.软件学报，2008（01）：48-61.SUN Jigui，LIU Jie，ZHAO Lianyu.Research on clustering algorithm J.Journal of Software，2008（01）：48-61.15LIB
34、ERTI L，LAVOR C，MACULAN N，et al.Euclideandistance geometry and applicationsJ.Quantity Biology，2012，56（1）：63-69.16ESTEVES K M，RONG C.Using Mahout for clusteringWikipediaslatestarticles：acomparisonbetweenK-means and fuzzy c-means in the cloud C/Proceedings of the 2011 Third IEEE International ConferenceScience Cloud Computing Technology and IEEE Computer Society.Washington，DC，USA：IEEE，2011：565-569.2235
