摘要: 现在进入了大数据的时代, 以前的那种聚类算法根本没法高效地搞定大量的数据, 云计算平台靠的是负载均衡、网络存储还有虚拟化这些技术, 把这些既费时间又费力的瓶颈给打破了, 这样就给处理海量数据提供了一个不错的解决办法。本研究重点剖析了平台环境之下的编程模型, 同时也对传统K-means算法进行了探讨, 进而提出了一套基于该平台的并行化K-means算法的设计方案, 这套方案里面涵盖了对Map函数的设计以及函数的设计环节, 后续通过展开相关实验工作, 证实了这种经过并行化处理的K-means算法, 在面对大规模数据集的时候, 是非常适合于进行数据分析和挖掘操作的。0 引言随着信息化社会的发展, 在各个行业中产生的数据都在以爆炸式的速度增长。典型的聚类算法——K-means算法是基于划分的聚类算法。因为它具有快速、简单的特性。因此它被广泛应用。但是在面对海量数据时, 传统的K-means算法无论是在时间复杂度还是空间复杂度上都遇到了瓶颈。云计算技术出现了, 这个技术的出现, 为海量数据的处理提供了良好的解决方案。云计算是一种建立在互联网基础之上的计算手段。它是云计算技术的一个开源版本, 具备能够容忍部分错误、并且可以在多种不同的平台环境中运行的突出优点。这个系统主要包括了两个组成部分, 一个是分布式文件系统, 另一个是编程模型。在这篇文章当中, 我们依托于已经搭建好的云计算平台, 借助了该编程模型的功能, 针对传统的K-means聚类算法进行了并行化方面的设计工作, 并且还开展了一系列实验, 对这些设计的有效性进行了相关证明。第一部分是关于编程模型的内容。所谓的编程模型, 从字面上去理解的话, 它是由两个特定的阶段所组成的, 一个是映射阶段, 另一个则是规约阶段, 这两个阶段分别是通过两个特定的函数来进行表示的, 也就是我们所熟知的Map函数以及函数。作业的流程, 就像我们在图1里面所看到的那样。在执行Map阶段的时候, Map任务是在集群的从节点上进行运行的。多个Map任务之间是相互独立运行的, 没有任何牵连。当原始数据进入Map函数之前, 系统会对那个原始的、巨大的数据集进行划分处理。处理完之后, 再将其格式化为键值对的那个形式。接着, 让这些数据经过Map函数的运算和一系列处理操作。经过这些步骤以后, 最后就会产生出一个或者多个中间的键值对。这个阶段, 它是由数据分割和操作还有数据合并这两部分给组成的。简单来说, 它就是把Map任务输出的那个中间结果, 里面那些有着相同key2的项, 全部给它合并成一对。然后呢, 则是采用那种默认的hash函数, 把中间的这些结果, 按照key2值的范围划分成R份, 发送出去并且要保证某一个范围内的key2一定都是由同一个任务来处理这件事儿的。在这个阶段, 每一个任务都需要从多个Map任务的节点上面, 去拿到它所负责的那个key2的区间里面的中间结果。这个函数接收了形式那样的输入, 在对输入做了处理之后, 会产生键值对作为最终的结果, 并且会把结果输出到HDFS上面去。为了方便大家进行理解, 在上述过程当中数据格式的变化情况展示在了图2之中。2 基于的并行K-means算法的设计2.1 K-means聚类算法的基本思路现在人们在用聚类算法的时候, 最广泛使用的基于划分的算法就是K-means算法了, 它的基本思想是这样的, 把空间里面的n个对象集合拿出来, 然后以K个点作为中心去进行簇的划分, 把这些对象归类到离他们最近的那个中点那里。通过反复迭代这种工作方式, 一步步地去更新那些聚类中心的具体数值, 然后再次把数据点进行簇的重新划分, 直到那个规定的目标函数能够达到收敛的状态。关于K-means这个算法, 它是采用了距离指标来作为评判物体之间相似程度的依据。它内部所使用的那个目标函数, 在形式上是可以表达成如下这样的样子:其中, Xi表示数据集X等于{x1, x2…, xN}当中的第i个样本, 这里边的N为样本总数, Cj表示第j个簇, K为簇的总个数, 而zj则对应的是第j个簇的中心。现在假设一共有n个数据对象, 计划要把它们划分成K个簇, t表示迭代的次数, O表示在每一次迭代中, 计算某一个数据对象到各个聚类的中心距离时所需要的耗时情况, 那么, 如果使用串行的方式来实现K-means算法, 它的时间复杂度就是n乘以K再乘以t最后乘以O。可以看到, 当面对大数据的时候, 算法的时间复杂度会变得翻倍地增加。2.这里讲的是, 关于2这个K-均值聚类算法的, 那个化设计的问题。在K-means算法里, 计算数据对象和聚类中心之间的那段距离, 是被反复拿去用的一个操作, 而且每一个数据对象去算那个到聚类中心距离的时候, 彼此之间是相互独立的, 互不耽误。图3描述了基于的并行K-means算法的设计方法, 具体是怎么回事呢, 其中数据的分片这件事是由环境自己来完成的, 不需要人工干预, 程序员只需要去编写Map函数和函数的实现代码就够了。2.在第2.1部分中, 我们对Map函数进行了具体的设计。第一步呢, 就是Map函数要对数据段进行逐行的扫描, 这一步里, 每一行会作为数据对象被处理, 然后记录成键值对, 接着就是运算步骤, 这一步需要拿出保存在全局变量中的聚类中心, 把数据对象和这些聚类中心拿来进行运算, 从而得出数据对象跟每一个聚类中心之间的距离是多少了, 最后一步是分配操作, 也就是要把数据对象分配到距离它最近的那个类里面去, 这个过程完成之后, 就会产生新的键值对, 这些新的键值对就作为这个函数的输出了, 关于Map函数的具体写法, 其伪代码如下。定义映射函数, 括号里面的参数是大写字母开始的键名称和点, 后面还有一个空着的参数。等于零, 这一操作的作用是初始化数据对象所在的类。开始对数据对象进行初始化操作, 同时也针对聚类中心的最小距离这一内容展开相关的设定工作。forint i0iDispoint为了得到数据对象和聚类中心之间的距离, 需要执行计算操作。if把那个数据对象给它安排到, 跟它离得最近的那个类里面去。i调用写点的方法, 并将参数一和一以及点对象作为输入传递进去。//输出键值对2.2.2 函数的设计开始行动之前, 先把那些聚类ID一模一样的人或者物, 统一交给一个任务去处理, 接下来, 让那个记数的函数, 好好记录下一共来了多少样本数据, 并且还要在暗中默默地把每个数据对象的每一个维度的坐标数值, 一个一个全都加起来累死个够才行, 到最后一步, 干脆把各个维度上累加起来的总和, 直接除以之前记下来的那个总样本个数, 这么一算出来的玩意儿, 就是这一类新的、更新换代后的聚集中心点, 至于这个函数的具体步骤是怎么安排的, 就请看下面这段像是乱码一样但能猜出意思的伪代码吧。函数 void 接收两个参数, 其中第一个是 key, 第二个为空。把数值从集合中取出来, 然后拿到第一个元素的个数, 把这个整数存进变量里面, 这里的数值代表的是数据对象里的属性数量。forint i0isum0int 等于 value.size//获取数据对象的个数。forint j0j将变量value在索引j和索引i处对应的数值累加到变量sum里面, 也就是把通过调用方法get获取到的值进行相加操作。avg sum/执行write方法, 传入参数key以及avg的值。//输出键值对把本轮函数输出的聚类中心拿去跟上一轮的聚类中心做相互比较。如果目标函数已经达到了收敛的状态, 那么算法就会停止执行。如果没有收敛。那就要把本轮的聚类中心写入到中心文件里面去。这样它就可以被当成新的聚类中心来使用。3 实验与分析本实验旨在比较同一硬件配置下, 集群中的单个运算节点与普通计算机在分别运用并行K-means算法与串行传统K-means算法处理等量数据时的效能差异。鉴于K-means算法对初始聚类中心具有显著的敏感特征, 故在一致的数据集设定内, 执行十轮反复测试, 并计算均值以作为最终呈现的实验结果, 具体数据见表1所示。在表1里面, t1的意思是, 用那种传统的、一个一个接着算的串行办法去处理数据集, 一共花了多少时间。t2的意思是, 用了能让多个部分一起算的并行办法来处理同样的数据集, 总共花的时间是多少。通过实验数据可以发现, 串行K-means算法的执行效率优于并行化K-means算法的执行效率。这种情况发生在数据集的规模较小的时候。这是因为当数据量小时, 计算任务所消耗的资源较少。但是, 在平台上启动, 分配任务以及进行作业间的交互, 却需要耗费固定的资源。可是伴随着数据集的规模不断变大, 计算任务所占用资源的比例也会随之不断提高。这样一来, 并行化算法的优势就能充分地显现出来。它运行时间增长的速度远远小于串行算法的增长速度。另外一边, 串行算法所消耗的资源在快速地增加。这种情况下, 系统会提示内存不够用。4 结论在这篇文章里, 咱们探讨了编程模型还有K-means这种聚类算法。然后把基于它的并行版K-means算法的设计方案给弄出来了, 也做了实验去验证它行不行。实验的结论是, 这种并行的K-means算法, 在处理那种数据量特别大的数据挖掘任务时是可以用的, 而且算得也比较快, 效率还不错。
