基于云计算的并行k-means算法研究


第 30 卷第 5 期 齐 齐 哈 尔 大 学 学 报 Vol.30,No.5 2014 年 9 月 Journal of Qiqihar University Sep.,2014 基于云计算的并行 k-means 算法研究 林长方,黄仲开,曾少俊 (漳州卫生职业学院信息技术部,福建 漳州 363000) 摘要:针对传统 k-means 聚类算法面对海量数据存在时间复杂度急剧增加的问题,结合云计算的优势,提出基于 MapReduce 编程框架来实现 k-means 聚类算法的并行化处理。Map 函数完成每个样本记录到聚类中心的距离计算 并标记其所属聚类类别,Reduce 函数汇总中间结果并计算出新的聚类中心,供下一轮迭代使用。通过实验表明: 基于 MapReduce 的并行化 k-means 聚类算法具有较好的加速比和良好的扩展性。 关键词:云计算;数据挖掘;并行 k-means;MapReduce 中图分类号:TP301.6 文献标志码:A 文章编号:1007-984X(2014)05-0005-05 聚类分析是运用数学的方法将物理或抽象数据对象的集合分成相似的对象类的过程,它是数据挖掘中 非常活跃的研究领域之一[1]。基于划分的聚类算法(如:k-means、k-medoids)以其简单、准确的特性被广 泛应用于统计学、生物学、机器学习、人工智能及市场营销等领域。随着信息技术的进步,数据采集与存 储技术飞速发展,聚类分析的对象集合规模越来越庞大,从而对聚类分析算法的并行性和分布化提出了新 的挑战。 MapReduce编程框架是Google实验室提出的一种用于并行处理海量数据集(TB级别以上)的分布式计 算架构,能够屏蔽底层实现细节,有效降低并行编程难度,成为当今云计算平台主流的并行数据处理模 型[2-4]。Apache基金会开发的Hadoop是一种开源的分布式系统平台,用户能轻松地构建一个高效的分布系 统[5-6]。本文 以Hadoop云计算平台为基础,研究了基于MapReduce编程模型的并行k-means算法,并进行了相 关实验。 1 Hadoop 平台 Apache Software Foundation公司受到Jeffrey Dean和Sanjay Ghemawat提出的MapReduce的启发,在 2005 年 秋天把Hadoop作为Lucene子项目Nutch的一部分正式引入。Hadoop是并行处理技术、分布式技术和网格计算 技术发展的产物[5],它不仅可高效地存储海量数据,而且可编写、运行分布式应用程序处理海量数据。Hadoop 由HDFS、MapReduce和HBase三个核心子项目组成,具有扩容能力强、效率与可靠性高、成本低、免费开 源及良好移植性的特点[5,6]。 HDFS(Hadoop Distributed File System)是一个分布式文件系统,由一个NameNode和多个DataNodes组 成,NameNode作为HDFS的中心服务器,负责管理文件系统的命名空间(NameSpace)及客户端对文件的访 问操作,同时负责数据块到DataNodes节点的映射。集群中的DataNodes负责各自节点的数据存储管理及文件 读写请求,并在NameNode的统一调度下完成数据块的创建、复制与删除等工作[7] MapReduce 是在 HDFS 基础上实现的一种并行编程模型,由一个 Master 和多个 Slave 节点组成,整个 工作流程包括 Map 和 Reduce 两个阶段。主服务器 Master 从用户处获取数据后,将数据分割为固定大小的 多个分片 Split 后以任务的形式分配给多个较近的节点服务器。在 Map 阶段,各个节点服务器以分配到的 Split 作为输入,对分片中的每条记录执行 map 函数,产生一系列的中间键值对,汇集于缓存中 的键值对集合会按 key 进行排序,最后按一定的时间间隔把数据结果写入节点服务器的硬盘,同时将相关 位置信息传送给 Master 节点。在 Reduce 阶段,Reduce 节点利用 Master 节点传送过来的位置信息远程读取 。 收稿日期:2014-04-29 基金项目:福建省教育厅基金项目(JB12312) 作者简介:林长方(1978-),男,福建华安人,讲师,硕士,主要从事数据挖掘、数据管理方面的研究,lincfhuang@126.com。 ·6· 齐 齐 哈 尔 大 学 学 报 2014 年 中间结果,当各个 Reduce 节点读取到全部的中间结果后,先对结果集按 key 重新排序,并对有序的 键值对集合进行处理,合并相同的 key 结果,最后执行 reduce 函数,并把最终处理结果写入 HDFS 中。 2 k-means 算法的 MapReduce 实现 2.1 k-means 算法 k-means聚类算法是一种基于划分的聚类分析方法,用于发现无类标号数据中的簇和簇中心。该算法 的核心思想是将n个数据划分为k个聚类,使每类中的数据点到聚类中心的平方和最小[8] (1)设定划分簇的 k 值,随机选取 k 个数据对象作为初始聚类中心。 。具体思路为: (2)分别计算剩余对象到各个聚类中心的距离(相似性度量),按距离最近的原则把对象分配到聚类 中。 (3)调整新类且重新计算出新类的中心。 (4)比较前后两次计算所得的聚类中心,若中心不同则转步骤(2),否则转步骤(5)。 (5)算法结束,输出聚类结果。 根据上述可知 k-means 采用迭代更新(串行)的方法处理聚类中心,整个算法的时间复杂度为 O(nkt), n、k、t 分别代表对象个数、聚类个数、迭代次数。在大数据量下,步骤(2)所耗时就急剧增加。然而计 算每个剩余对象到聚类中心的距离都是独立完成的,相互间没有联系,因此,可利用 MapReduce 模型进行 并行化处理。 2.2 k-means 的 MapReduce 并行化实现 基于 MapReduce 编程框架的并行化 k-means 聚类算法的基本思想:在串行算法执行过程中的每一次迭 代启动相应的一次 MapReduce 计算(含 Map 函数、Combine 函数和 Reduce 函数),完成数据对象到聚类中 心的距离及新的聚类中心的计算,算法流程如图 1。 从数据对象中随机选取 k 个数据样本作为初始中心点,并存储在 HDFS 上的一个文件中,作为全局变 量,每次迭代执行完进行更新。根据 MapReduce 计算模型处理数据的模式,对待处理数据对象进行预处理, 按行分片,且分片间无相关性。 2.2.1 Map 函数设计 Map 函数的任务是从 HDFS 的文件中逐行读取数据样本,以 key/value 键值对表示,计算每个样本到各 中心点的距离,并按照距离最小的规则将样本数据归属类别及标记其所属的聚类类别。Map 函数的输入为 待聚类全部数据样本及上一轮迭代计算获得的聚类中心(或初始聚类中心),数据记录的键值 对以每条记录的<行号,记录行>组成;输出中间结果键值对以<聚类类别 ID,记录属性向量> 组成。 Map 函数伪代码: void map() { min_distance=Math.max( ); //定义最短距离变量 min_distance,初始化最大值 ID=-1; for(i=0;i<=k-1;i++) {distance=distance(array,cluster[i]); //定义数组 array,记录样本各维数值,分别计算样本与第 i 个聚类中心各维的距 图 1 算法流程图 第 5 期 基于云计算的并行 k-means 算法研究 ·7· 离 if distance; //中间结果 } 2.2.2 Combine 函数设计 Combine 函数的任务是对 Map 函数输出的大量中间结果进行本地规约,减少键值对数据 在节点间的传输时耗和带宽占用。输入的键值对对应<聚类类别 ID,记录属性向量>,针对相 同的 ID,解析出每条记录的各维坐标值,分别累加各维坐标值得到局部聚类的累加和,并统计相同 ID 样 本记录的个数和;输出的键值对,key 为 ID,value 为样本记录总数与局部聚类的各维累加和。 Combine 函数的伪代码: void combine() { num=0; //定义变量 num,统计样本个数和 while(value.hasNext( )) { num++; //统计相同聚类(ID)的样本个数 for (i=1;i<=dimension;i++) //dimension 代表每个记录样本的维数 {sum[i]+=point[i];} //定义数组 sum[i],初始化各分量为 0,分别记录各维坐标值累加值 } value=num+sum; //构造存储记录总个数和各维累加值的字符串 Output; } 2.2.3 Reduce 函数设计 Reduce 函数的任务是汇总 Combine 函数产生的局部聚类结果,计算出新的聚类中心,供下一轮 Map-Reduce 函数使用。Reduce 函数根据输入(输入:)统计样本 的全局总个数及各维坐标值的累加值,然后用累加值除以总个数获得均值向量(新聚类中心坐标);输出为 <聚类类别 ID,均值向量>。 Reduce 函数的伪代码: void Reduce() { NUM=0; //定义 NUM 变量,初始值为 0,统计相同 ID 的样本总个数 while(value.hasNext( )) { NUM=NUM+num; //统计局部样本个数(num)的总数量 for (i=1;i<=dimension;i++) //dimension 代表每个记录样本的维数 {SUM[i]+=point[i];} //定义数组 SUM[i],初始化各分量为 0,分别记录局部各维坐标值累加值的总和 } for (i=1;i<=dimension;i++) //dimension 代表每个记录样本的维数 mean[i]=SUM[i]/NUM; //定义数组 mean[i],初始化各分量为 0,记录各维坐标的均值 value=mean[i]; //构造一个字符串,包含新的中心点各维坐标值(向量均值)的信息,将字符串赋予 value Output; } ·8· 齐 齐 哈 尔 大 学 学 报 2014 年 根据 Reduce 函数的输出结果,获取新的聚类中心的坐标,并更新 HDFS 相关文件。计算连续两轮结 果的误差平方和准则函数,若差值小于给定阈值,则表明聚类准则函数收敛,算法结束;否则,新的聚类 中心替换上轮的中心文件,进入新一轮的 Map-Reduec 计算。 3 实验结果与分析 3.1 实验环境与实验数据 实验环境采用云计算平台Hadoop,共 6 个节点,每个节点的配置:Pentium(R) Dual-Core E5800 @3.20GHz ×2,2 GB RAM,500 随机选取两台硬件配置相同的计算机,一台来自集群中的某 个节点,另一台为安装了数据挖掘工具Weka软件的普通计算机, 分别采用并行化的 k-means聚类算法和传统的串行 k-means聚类 算法处理相同规模的测试数据集,比较从数据输入到完成聚类划 分所花费的时间,T1 表示运行于普通计算机的串行 k-means 所 花费的时间均值,T2 表示运行于集群某节点的并行化的 k-means 所花费的时间均值,实验结果见表 1。 GB硬盘,千兆网卡。操作系统均采用Ubuntn 10.10,JDK采用Sun JDK1.6.0_23 版本, Hadoop平台采用Hadoop-0.20.2 版本。 实验数据利用 UCI 的 Synthetic Control Chart Time Series 数据集(包含 600 个样本,每个样本有 60 个属 性)为基础,随机生成样本数分别为 50000,20000,100000,500000,800000 的 5 个测试数据集,分别称 为 data01、data02、data03、data04、data05。 3.2 实验与分析 在实验过程中,为了避免随机性选择的初始聚类中心 k 可能带来的误差,对每组测试数据集各自进行 20 次的重复操作,取其平均值作为最终的实验结果。实验分别以单机处理速度、并行处理加速比和扩展性 作为评判指标。 3.2.1 单机处理比较实验 由表 1 可以发现,在测试数据集规模较小的情况下串行算法 的执行效率高于并行化的 k-means 算法。这是因为,Hadoop 集 群上的 Job 的启动与交互需要消耗资源,且占总消耗资源的比例较大。随着数据规模的增大,实际计算消 耗的时间就增多,Job 所消耗的比例下降,并行化算法的执行效率就提高。 随着测试数据集的增大,两种算法的执行时间都在增长。然而串行算法的增长速度远远大于并行化算 法,表明资源消耗越来越严重,最终将导致系统资源承受不了串行计算的开销而使算法终止运行。 3.2.2 扩展率性能实验 本实验是为了测试基于不同的硬件资源条件,并行化算法 处理相同规模数据的执行效率。实验数据为 data02、data03、 data04,要求生成 10 个聚类类别,分别选取 1、2、3、4、5、 6 个节点参与计算,实验结果如图 2。 从图 2 中可看出三组测试数据随着节点的增加各自的运行 时间都在降低,表明节点的增加可提高系统对相同规模数据的 处理能力,体现出了较好的扩展性,但执行时间却没有按照节 点的增加数目出现倍数的降低,这是因为节点数的增加伴随着 节点间的通信开销也增大。 3.2.3 集群加速比性能实验 加速比(Speedup)是用来衡量并行系统执行性能和效率的一个指标,是同一任务在单台计算机上的 执行时间与 m 台计算机执行时间的比例。在实验中测试了并行算法处理 data03、data04、data05 的加速比, 实验结果如图 3。 表 1 单机实验结果 序号 测试数据集 样本数 T1/s T2/s 1 2 3 4 5 data02 data01 data03 data04 Data05 20000 50000 100000 500000 800000 11 27 54 173 436 65 78 104 145 168 时 间 / s 图 2 扩展率性能试验结果 集群节点数 第 5 期 基于云计算的并行 k-means 算法研究 ·9· 从图 3 可看出,加速比随着集群节点的增加保持一个接近线性 的增长,表明节点的增加能够较有效地节省算法的执行时间,且数 据集越大,加速比的性能越高。这主要是 Map 与 Reduce 函数设计 较合理,特别是 Combine 函数的加入,使中间结果键值 对在节点间的通信对带宽的消耗大大降低,所以数据集越大,算法 的加速比性能越好。 4 结束语 在云计算平台上,基于 MapReduce 编程框架对 k-means 聚类算法进行并行化处理,以期实现 k-means 聚类算法处理海量数据的能力及提高执行效率,实验结果表明,在大数据量下,基于 MapReduce 框架的并 行化 k-means 聚类算法不仅能够提高计算效率,而且具有良好的加速比和扩展性。 参考文献 [1] 陈爱平.基于 Hadoop 的聚类算法并行化分析及应用研究[D].成都:电子科技大学,2012 [2] Dean J,Ghemawat S.MapReduce:simplied data processing on large clusters:Communications of the ACM[J].January,2008,51, (1):107-113 [3] Anchalia P P,Koundinya A K,Srinath N K.MapReduce Design of K-Means Clustering Algorithm[C]//Information Science and Applications(ICISA),2013 International Conference on,Suwon,2013:1-5 [4] Yunhua [5] Lam C.Hadoop in Action[M].Manning Publication Co,2011 Qian,Liye Liang,Feng Wang.a New Method for Measuring the Uncertainty in Incomplete Information Systems[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2009,17(6):855-880 [6] Hadoop:Open source implementation of MapReduce,Available[EB/OL].[2010-07-24]:http://hadoop.apache.org [7] 邓自力.云计算中的网络拓扑设计和 hadoop 平台研究[D].合肥:中国科学技术大学,2009 [8] 崔丹丹.K-Means 聚类算法的研究与改进[D].合肥:安徽大学,2012 Research on parallel k-means algorithm based on cloud computing LIN Chang-fang,HUANG Zhong-kai,ZENG Shao-jun (Department of Information Technology,Zhangzhou Health Vocation College,Zhang zhou 363000,China) Abstract:For the problem of high time complexity in dealing with huge data of k-means algorithm,propose a parallel method using MapReduce programming model and cloud computing to reduce the time complexity of k-means. The distance between each record and each cluster was calculated and new category was marked to each record in the Map function.All the records of the same key value were sent to a single reducer and get the new cluster centroids for the next MapReduce Job.Experimental results show that the parallel k-means algorithm based on MapReduce has basically linear speedup with an increasing number of node computers and good scalability. Key words:cloud computing;data mining;parallel k-means;MapReduce 集群节点数 图 3 加速比实验结果 加 速 比 基于云计算的并行k-means算法研究 作者: 林长方, 黄仲开, 曾少俊, LIN Chang-fang, HUANG Zhong-kai, ZENG Shao-jun 作者单位: 漳州卫生职业学院信息技术部,福建 漳州,363000 刊名: 齐齐哈尔大学学报(自然科学版) 英文刊名: Journal of Qiqihar University (Natural Science Edition) 年,卷(期): 2014(5) 本文链接:http://d.wanfangdata.com.cn/Periodical_qqhrdxxb201405002.aspx
还剩5页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

8nb5

贡献于2014-12-18

下载需要 5 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf