◆李 莉

（金肯职业技术学院 江苏 211156）

基于云计算平台Hadoop的并行k-means聚类算法设计研究

◆李 莉

（金肯职业技术学院 江苏 211156）

随着信息化时代的到来，也相应提升了科技的发展。现阶段网络技术的发展也不断为数据库的发展提供技术支持。在实际应用网络技术时常常会出现大量的数据需要处理，人们开始致力于探讨致聚类研究课题，但是随着不断深入的盐分分析也显现出较多的问题，例如出现了新的计算环境还有海量数据等。本文主要是探讨分析了基于云计算平台Hadoop的并行k-means聚类算法设计研究，并且在此基础之上提供了新的设计算法方式以及应对策略。根据大量的数据研究显示，并行k-means聚类算法设计的加速比较为良好，并且具有优质的数据伸缩率性能以及扩展率，有效作用于挖掘和分析海量数据。

云计算；平台Hadoop；并行k-means；聚类算法设计；研究探讨

0 前言

现阶段，数据挖掘当中比较重要的课题在于聚类算法设计，该算法的主要内容在于了集合组成抽象对象或者物理对象，并转变为与其相类似的对象簇群的算法过程。由聚类形成的簇群主要会集合一组数据对象，并且该对象之间存在较高的相似度，但是不同簇群当中的对象具有较大的差异性。当前的社会企业，科研组织，政府部门以及商业领域等都广泛应用数据库技术，并且在数据存储方面都是通过不同形式实现的。现阶段需要亟待解决的问题就是怎样加工海量数据进行处理和存储，在此基础之上如何寻找有价值的数据信息，并且可以应用在实际工作当中。针对现在产生和存在的海量数据，现有的聚类算法已经不能满足该数据的要求，尤其是在空间复杂性和时间复杂性上，这就需要聚类算法进行全面深化地研究和解决。针对以上问题的解决最重要的措施就是将并行 k-means处理方式应用在聚类算法当中，这样可以创新并行聚类算法，显著加强该算法处理数据的实效性以及功能。

云计算主要是当前比较新颖的商业计算模型，Hadoop云计算平台可以实现并行处理和开发海量数据，该平台最重要的优势在于具有较强的扩容能力以及运行效率，较低的成本，具有显著的优势性能。Hadoop云计算平台主要是由MapReduce计算模型以及HDFS两部分组成。

MapReduce属于分布式编程模型，具有较高的效率，主要是实现数据集的生成和处理，该计算模型主要是应用Hadoop云计算平台中的框架，并且需要Map函数以及Reduce函数，并且可以将运行参数的输出位置以及输入位置进行明确，加工大数据文件切割为较多数据块。其次就是该框架可以将输入当做一组键值对，在该环节，框架可以实现调用用户自行设置的函数，并且可以有效处理每一组键值对。其次就是为了确保Reduce可以实现有效输入，在Shuffle环节，MapReduce框架主要是利用Http为Reduce提供键值对。再者就是Reduce环节，该环节就可以将所涉及到的所有数据进行浏览，并且可以实现分别对应不同的Key，对用户自行设定的Reduce函数进行有效执行。最后就是输出环节，该环节主要会将Reduce输出的结果对应显示在输出目录上，这样就完后了整体MapReduce算法。

HDFS主要是应用M/S结构，每一个集群主要的组成为数据节点以及管理节点，每一个节点属于独立的PC端。在实际应用时，HDFS高度相似于单机上的文件系统，其主要功能在于可以创建文件目录，并且实现文件的复制，查看，新建以及删除等。HDFS的底层主要是可以切割文件并且将其分为若干块，之后在不同的数据节点之上将其分散储存。需要注意的是，这些块功能再次分为较多子项，并且存储在不同类型的数据节点之上，这样就可以实现容错功能。中心服务器主要是负责数据节点的管理，对其客户端访问权限以及文件的名字空间等。数据节点可以实现对节点存储的管理和控制。HDSF的核心功能在于数据节点的管理，可以有效加工某一组数据结构进行维护，还可以将每一个文件的切割情况，块的来源以及状态数据信息等进行详细记录。

1 基于云计算平台Hadoop的并行k-means聚类算法设计

由前面的分析我们能够得出，基于云计算平台Hadoop的并行k-means聚类算法设计，用户最主要的工作就是将Reduce函数以及Map函数进行设计和实现，还附带输出键值对以及输入键值对，以及包括Reduce函数以及Map函数的具体逻辑算法等。

针对串行的k-means聚类算法设计主要的算法流程为：第一步，先随意选择K个样本，并将其作为聚簇创始的中心点，第二步，迭代，首先主要按照不同聚簇的中心点坐标，并且将上述选择的样本下发到较近距离的聚簇，其次就是将不同聚簇中包含的样本的平均值进行计算。第三步，收敛。

从上述k-means聚类算法设计的主要流程能够得出，其中最重要的算法工作在于将选择的样本下发到较近距离的聚簇，这样就可以实现相互独立选择的样本，这时就可以将以上两个步骤进行并行处理和执行。在进行迭代时，将相同的操作方式下发给实际的算法当中，k-means聚类算法设计主要是在迭代期间实现Map与Reduce操作的统一执行。

在选择样本时主要是随机选择若干样本，并将其作为中心点，之后将以上形成的中心点共同储存在HDFS文件，将其当做全局变量。以上操作所涉及的迭代主要是由 Map函数，Reduce函数以及Combine函数组成的。

1.1 设计Map函数

Map函数所以输入的键值对主要是所处框架之内预设的格式，其中键值对当中的key就是当前样本主要是针对输入数据文件起始点偏移量，value主要是样本的各项坐标值数所形成的字符串。第一步，在value当中将样本各个坐标值数进行解析，之后计算value与中心点之间的距离，并且寻找出最近距离中心点聚簇的下标，之后将再次生成的键值对输出，其中所包含的key*是距离聚簇最近的下标，value*主要是样本在各个坐标产生的字符串。

为了降低在算法迭代期间产生的数据传输以及通讯代价，在结束Map操作之后，在k-means聚类算法之外设计Combine操作，之后本地合并处理结束的Map函数的数据输出。由于每一个Map函数出现的数据传输可以有线在本地节点里面进行储存，这就说明所有的Combine操作就是在本地进行执行，这样就会产生较小的通信代价。

1.2 设计Combine函数

Combine函数产生的输入键值对中的key主要是聚簇中的下标，包含的v主要是聚簇分配给key聚簇的样本之间的各个坐标产生的字符串联表。第一步，在字符串联表当中将各个样本显示在不同坐标指数进行解析，再将分别相加每一个坐标轴上产生的坐标值数，之后将字符串联表当中产生的样本总数进行详细记录。之后产生的键值对当中的key*是距离聚簇最近的下标，value*主要是样本在各个坐标的总数以及累加其在各个坐标轴产生的坐标值数。

1.3 设计Reduce函数

Reduce函数产生的输入键值对中的 key主要是聚簇中的下标，包含的v主要是由Combine函数在进行数据传输时产生的中间结果。在Reduce函数当中可以将Combine函数中处理的样本个数以及相对应数据节点在各个坐标轴上的坐标值数累加进行优先解析，之后在对应相间Reduce函数在各个坐标轴值数的累加值数，之后在除以总的样本数量，这样就可以产生新的中心点坐标。

按照Reduce函数所输出的结果可以产生新的中心点坐标，并且可以将HDSF当中的文件进行实时更新，之后在进行新的迭代，直至算法收敛。

2 实验和分析结果

2.1 实验环境，实验数据以及实验评价指标

此次研究所涉及的所有实验都是通过云计算平台Hadoop实现和运行的。该云计算平台Hadoop主要是由32核，10台设备组成的。其中双核2.8G，内存4GB的设备有4台，四核2.33G，内存为8G的设备有6台。云计算平台Hadoop的版本为0.16.0，java的版本为1.4.0-13.不同设备之间的连接都是采用交换机实现的，并且都是应用传输速率为1000MPa的以太网卡。

此次研究实验都是采用人工数据作为主要的数据研究，应用48维度。针对算法性能的测试，在此次研究实验当中涉及到的数据群主要是32G，16G，8G，4G，2G，1G等。

2.2 分析实验结果

因为 k-means聚类算法的操作运行当中包含随机初始化中心点，所以在进行数据计算时需要进行20次的重复执行，每一组数据的最终实验结果取自于此次计算重复执行时间的平均值。

在此次研究实验当中，主要对k-means聚类算法在进行不同数据大小处理的加速比，其实验结果可以详见图1：

图1 测试结果

在上图能够得出，k-means聚类算法的加速比无限接近于线性。随着不断增大的数据集规模，就会相应提升k-means聚类算法的加速比性能。造成以上结果的原因在于k-means聚类算法的Map与Reduce中键值对的对比比较科学，这样可以提升算法的速率以及实效性，使其可以在较短时间内执行和实现。其次就是在并行k-means聚类算法都当中，新添加了Combine函数的操作，这样就会在加大程度上降低数据节点与对应节点之间的通讯代价，加强了数据集的规模，提升了通讯量的减少比例。所以，在增加数据集的规模时，就会相应提升k-means聚类算法的性能。

在此次研究分析当中，还进行了k-means聚类算法的扩展率测试。首先就是测试在不同大小数据集1G，2G，4G，在数据节点1，数据节点2，数据节点4上的上的运行效率，其次就是计算在不同大小2G，4G，8G，以及16G在数据节点2，数据节点4，数据节点8上以及数据节点16上的运行效率，最后就是测试在不同大小数据集4G，8G，16G以及32G，在数据节点4，数据节点8，数据节点16以及数据节点32上的运行效率，所得出的实验结果详情见图2。

图2 测试不同数据节点扩展性的实验结果

从上图能够得出，针对相同数据集，如果计算平台上的数据节点的数量以及测试数据集大小呈现同比例上升时，就会相应降低k-means聚类算法的扩展率。造成以上原因的主要因素在于，当增加数据节点的数量时，就会相应增加各个数据节点之间的通讯代价。如果数据集的规模也在不断扩大，就会相应提升算法执行的时间。然而，从此次研究实验结果可以看出，随着不断增加的数据集国模，就会相应提升k-means聚类算法的扩展率性能。造成以上原因的主要因素在于，，如果提升数据集规模，就可以将每一个数据节点的计算能力进行提升。在分析对比k-means聚类算法的加速比可以看住，在 k-means聚类算法当中添加Combine时，随着不断提升的数据集规模，就会相应提升各个数据节点之间的通信代价减少比例。

3 结束语

现阶段，各个行业领域都开始普遍使用云计算方式，并且借助于其所具有的数据挖掘优势以及聚类算法优势等实现企业的生产经营。以上两个方面也已经成为现阶段国际上热门课题研究。从云计算平台Hadoop的并行k-means聚类算法设计研究现状可以看出，其未来的主要研究方向在于：探讨分析聚类算法并行化的一般规律，并且可以寻找出数据集大小，数据节点数量以及算法复杂性三者之间的关系。

[1]华志洁．基于 Hadoop云计算平台仿百度智能输入提示算法的研究与实现[J]．天津科技，2015．

[2]陈静．基于 Hadoop云计算平台的文本处理算法的研究与改进[J]．天津科技，2016．

[3]张玉峰，曾奕棠．基于云聚类挖掘的物流信息智能分析方法研究[J]．情报资料工作，2016．

[4]王凤领．基于 Hadoop高校教育资源云存储平台构建研究[J]．计算机技术与发展，2016．

[5]谢雪莲，李兰友．基于云计算的并行K-means聚类算法研究[J]．计算机测量与控制，2015．

[6]段庆伟，铁木巴干．基于 Hadoop云计算平台的新浪微博数据聚类分析算法研究[J]．辽宁科技学院学报，2017．

[7]武森，冯小东，张晓楠．基于MapReduce的大规模文本聚类并行化[J]．北京科技大学学报，2015．

[8]赵卫中，马慧芳，傅燕翔．基于云计算平台 Hadoop的并行k-means聚类算法设计研究[J]．计算机科学，2016．