第10卷第4期 智能系统学报 Vol.10 No.4 2015年8月 CAAI Transactions on Intelligent Systems Aug.2015 D0:10.3969/j.issn.1673-4785.201411036 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150630.1555.003.html CMP上基于数据集划分的K-means多核优化算法 申彦12，朱玉全2 (1.江苏大学信息管理与信息系统系，江苏镇江212013：2.江苏大学计算机科学与通信工程学院，江苏镇江212013) 摘要：虽然现在多核CPU非常普及，但传统K-meas聚类算法由于没有专门进行并行化设计，不能充分利用现代 CPU的多核计算能力，算法针对大规模数据集的聚类效率有待进一步提高。因此，对K-meas算法进行CMP并行化 改进，提出了一种Muli-core K-means(MC-K-means)算法。该算法对K-means的聚类任务进行了分解，设计了独立且 均衡的聚类子任务并分配给各线程并行执行，以此利用现代CPU的多核计算能力。实验结果表明，MC-K-meas相 比K-means获得了较高的多核加速比，提高了针对大规模数据集的聚类能力。 关键词：K均值算法：聚类算法：单片多核：大规模数据集：数据挖掘：无监督学习：大数据 中图分类号：TP181文献标志码：A文章编号：1673-4785(2015)04-0607-08 中文引用格式：申彦，朱玉全.CMP上基于数据集划分的K-means多核优化算法[J].智能系统学报，2015,10(4)：607-614. 英文引用格式：SHEN Yan,ZHU Yuquan..An optimized algorithm of K-means based on data set partition on CMP systems[J], CAAI Transactions on Intelligent Systems,2015,10(4):607-614. An optimized algorithm of K-means based on data set partition on CMP systems SHEN Yan'2,ZHU Yuquan2 (1.Department of Information Management and Information System,Jiangsu University,Zhenjiang 212013,China;2.School of Computer Science and Communication Engineering,Jiangsu University,Zhenjiang 212013,China) Abstract:The traditional K-means clustering algorithm is not designed to focus on parallelization,which can not make use of the multi-core computing capability of the modern CPU.Therefore,the clustering efficiency of the tra- ditional K-means for massive data set should be further improved.In this paper,a novel algorithm named Multi-core K-means (MC-K-means)after redesigning the original K-means that focuses on parallelization in a chip multi-pro- cessor CMP environment is proposed.In order to utilize the multi-core computing capability of the modern CPU, MC-K-means partitions the clustering tasks into some independent and balanced subtasks and distributes these sub- tasks to the threads to execute parallel.The experimental results showed that the MC-K-means algorithm received the relatively higher speedup rate compared to the K-means algorithm,which improves the handling capacity for massive data set. Keywords:k-means;clustering algorithm;CMP;massive data set;data mining;unsupervised learning;big data 聚类是一项重要的研究工作，已经成为数据挖PAM,WaveCluster等。其中K-means算法因其简 掘、统计分析以及压缩算法等领域的研究重点。聚 单、易于实现，获得了广泛的应用。现代数据挖掘技 类研究领域有大量经典的算法涌现，如K-means,. 术的一个突出特点是需要处理大规模数据集。经典 的K-means算法在处理大规模数据集时，无法一次 收稿日期：2014-11-28.网络出版日期：2015-06-30. 性把数据集全部装载人内存，需要多次扫描硬盘上 基金项目：国家自然科学基金资助项目(71271117)：国家科技支撑计划 基金资助项目(2010BA88B00):江苏省自然科学基础研究计 的数据，整个聚类过程相当耗时。因其应用的广泛 划基金资助项目(BK2010331):江苏省博士研究生创新计划 性，很多研究人员选择对其进行优化，使其适应大规 基金资助项目(CXI10B_016X):江苏省博土后科研资助计划 项目(1401056C). 模数据集聚类的应用需求。值得注意的是，在过去 通信作者：申彦.E-mail:104186179@q4.com. 的几十年中，CPU的主频几乎每两年提高一倍，与
第 １０ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．４ ２０１５ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４１１０３６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０６３０．１５５５．００３．ｈｔｍｌ ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 申彦１，２ ，朱玉全２ （１．江苏大学 信息管理与信息系统系，江苏 镇江 ２１２０１３；２．江苏大学 计算机科学与通信工程学院，江苏 镇江 ２１２０１３） 摘 要：虽然现在多核 ＣＰＵ 非常普及，但传统 Ｋ⁃ｍｅａｎｓ 聚类算法由于没有专门进行并行化设计，不能充分利用现代 ＣＰＵ 的多核计算能力，算法针对大规模数据集的聚类效率有待进一步提高。 因此，对 Ｋ⁃ｍｅａｎｓ 算法进行 ＣＭＰ 并行化 改进，提出了一种 Ｍｕｌｔｉ⁃ｃｏｒｅ Ｋ⁃ｍｅａｎｓ（ＭＣ⁃Ｋ⁃ｍｅａｎｓ）算法。 该算法对 Ｋ⁃ｍｅａｎｓ 的聚类任务进行了分解，设计了独立且 均衡的聚类子任务并分配给各线程并行执行，以此利用现代 ＣＰＵ 的多核计算能力。 实验结果表明，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 相 比 Ｋ⁃ｍｅａｎｓ 获得了较高的多核加速比，提高了针对大规模数据集的聚类能力。 关键词：Ｋ 均值算法；聚类算法；单片多核；大规模数据集；数据挖掘；无监督学习；大数据 中图分类号： ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０４⁃０６０７⁃０８ 中文引用格式：申彦，朱玉全． ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法［Ｊ］． 智能系统学报， ２０１５， １０（４）： ６０７⁃６１４． 英文引用格式：ＳＨＥＮ Ｙａｎ， ＺＨＵ Ｙｕｑｕａｎ． Ａｎ ｏｐｔｉｍｉｚｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ Ｋ⁃ｍｅａｎｓ ｂａｓｅｄ ｏｎ ｄａｔａ ｓｅｔ ｐａｒｔｉｔｉｏｎ ｏｎ ＣＭＰ ｓｙｓｔｅｍｓ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（４）： ６０７⁃６１４． Ａｎ ｏｐｔｉｍｉｚｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ Ｋ⁃ｍｅａｎｓ ｂａｓｅｄ ｏｎ ｄａｔａ ｓｅｔ ｐａｒｔｉｔｉｏｎ ｏｎ ＣＭＰ ｓｙｓｔｅｍｓ ＳＨＥＮ Ｙａｎ １，２ ， ＺＨＵ Ｙｕｑｕａｎ ２ （１． Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｍａｎａｇｅｍｅｎｔ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ， Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ， Ｚｈｅｎｊｉａｎｇ ２１２０１３， Ｃｈｉｎａ；２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ， Ｚｈｅｎｊｉａｎｇ ２１２０１３， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ Ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｎｏｔ ｄｅｓｉｇｎｅｄ ｔｏ ｆｏｃｕｓ ｏｎ ｐａｒａｌｌｅｌｉｚａｔｉｏｎ， ｗｈｉｃｈ ｃａｎ ｎｏｔ ｍａｋｅ ｕｓｅ ｏｆ ｔｈｅ ｍｕｌｔｉ⁃ｃｏｒｅ ｃｏｍｐｕｔｉｎｇ ｃａｐａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｍｏｄｅｒｎ ＣＰＵ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｔｒａ⁃ ｄｉｔｉｏｎａｌ Ｋ⁃ｍｅａｎｓ ｆｏｒ ｍａｓｓｉｖｅ ｄａｔａ ｓｅｔ ｓｈｏｕｌｄ ｂｅ ｆｕｒｔｈｅｒ ｉｍｐｒｏｖｅｄ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ａ ｎｏｖｅｌ ａｌｇｏｒｉｔｈｍ ｎａｍｅｄ Ｍｕｌｔｉ⁃ｃｏｒｅ Ｋ⁃ｍｅａｎｓ （ＭＣ⁃Ｋ⁃ｍｅａｎｓ） ａｆｔｅｒ ｒｅｄｅｓｉｇｎｉｎｇ ｔｈｅ ｏｒｉｇｉｎａｌ Ｋ⁃ｍｅａｎｓ ｔｈａｔ ｆｏｃｕｓｅｓ ｏｎ ｐａｒａｌｌｅｌｉｚａｔｉｏｎ ｉｎ ａ ｃｈｉｐ ｍｕｌｔｉ⁃ｐｒｏ⁃ ｃｅｓｓｏｒ ＣＭＰ ｅｎｖｉｒｏｎｍｅｎｔ ｉｓ ｐｒｏｐｏｓｅｄ． Ｉｎ ｏｒｄｅｒ ｔｏ ｕｔｉｌｉｚｅ ｔｈｅ ｍｕｌｔｉ⁃ｃｏｒｅ ｃｏｍｐｕｔｉｎｇ ｃａｐａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｍｏｄｅｒｎ ＣＰＵ， ＭＣ⁃Ｋ⁃ｍｅａｎｓ ｐａｒｔｉｔｉｏｎｓ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｔａｓｋｓ ｉｎｔｏ ｓｏｍｅ ｉｎｄｅｐｅｎｄｅｎｔ ａｎｄ ｂａｌａｎｃｅｄ ｓｕｂｔａｓｋｓ ａｎｄ ｄｉｓｔｒｉｂｕｔｅｓ ｔｈｅｓｅ ｓｕｂ⁃ ｔａｓｋｓ ｔｏ ｔｈｅ ｔｈｒｅａｄｓ ｔｏ ｅｘｅｃｕｔｅ ｐａｒａｌｌｅｌ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗｅｄ ｔｈａｔ ｔｈｅ ＭＣ⁃Ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｒｅｃｅｉｖｅｄ ｔｈｅ ｒｅｌａｔｉｖｅｌｙ ｈｉｇｈｅｒ ｓｐｅｅｄｕｐ ｒａｔｅ ｃｏｍｐａｒｅｄ ｔｏ ｔｈｅ Ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ， ｗｈｉｃｈ ｉｍｐｒｏｖｅｓ ｔｈｅ ｈａｎｄｌｉｎｇ ｃａｐａｃｉｔｙ ｆｏｒ ｍａｓｓｉｖｅ ｄａｔａ ｓｅｔ． Ｋｅｙｗｏｒｄｓ：ｋ⁃ｍｅａｎｓ； ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ＣＭＰ； ｍａｓｓｉｖｅ ｄａｔａ ｓｅｔ； ｄａｔａ ｍｉｎｉｎｇ； ｕｎｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ； ｂｉｇ ｄａｔａ 收稿日期：２０１４⁃１１⁃２８． 网络出版日期：２０１５⁃０６⁃３０． 基金项目：国家自然科学基金资助项目（７１２７１１１７）；国家科技支撑计划 基金资助项目（２０１０ＢＡＩ８８Ｂ００）；江苏省自然科学基础研究计 划基金资助项目（ＢＫ２０１０３３１）；江苏省博士研究生创新计划 基金资助项目（ＣＸ１０Ｂ＿０１６Ｘ）；江苏省博士后科研资助计划 项目 （ １４０１０５６Ｃ ） 通信作者：申彦． Ｅ⁃ｍａｉｌ：１０４１８６１７９＠ ｑｑ．ｃｏｍ． 聚类是一项重要的研究工作，已经成为数据挖 掘、统计分析以及压缩算法等领域的研究重点。 聚 类研究领域有大量经典的算法涌现，如 Ｋ⁃ｍｅａｎｓ， ＰＡＭ，ＷａｖｅＣｌｕｓｔｅｒ 等。 其中 Ｋ⁃ｍｅａｎｓ 算法因其简 单、易于实现，获得了广泛的应用。 现代数据挖掘技 术的一个突出特点是需要处理大规模数据集。 经典 的 Ｋ⁃ｍｅａｎｓ 算法在处理大规模数据集时，无法一次 性把数据集全部装载入内存，需要多次扫描硬盘上 的数据，整个聚类过程相当耗时。 因其应用的广泛 性，很多研究人员选择对其进行优化，使其适应大规 模数据集聚类的应用需求。 值得注意的是，在过去 的几十年中，ＣＰＵ 的主频几乎每两年提高一倍，与 ．
·608. 智能系统学报 第10卷 此相对应的内存频率却没有相对应的提高。内存与 1.2相关的研究工作 CPU之间处理数据的能力差距越来越大，极大地影 为了解决K-means算法对大规模数据集聚类效 响了应用程序的性能。同时，工程师们开始认识到， 率较低的问题，有研究者提出了只需要扫描一遍原 仅仅提高单核芯片的频率会产生过多热量且无法带 始数据集即产生聚类结果的算法。这些算法只需读 来希望的性能改善。于是，CMP(chip multi-proces- 入大规模数据集中的一部分进入主存或者分批读入 sor)成为了先进处理器的发展趋势。CMP可以在大 数据集进行聚类，扫描数据集一遍即完成聚类。相 幅提高处理性能的同时降低CPU主频，减少能源消 应的算法有random-kmeans,Dynamic incremental K- 耗。然而仅简单提供CMP环境并不能直接带来应 meanst2),Single pass kernel K-meanst3,scalable- 用程序性能的提高，需要研发人员针对CMP环境对 kmeanst),等。其中，由Microsoft Research的Red- 有关算法进行优化，才能使得应用程序更好的利用 mond等提出的scalable-kmeans算法性能优越，受到 CPU的多核计算能力，提高程序的运行效率[)。 了广泛的重视，并被集成到SQL SERVER2008中。 本文针对提高大规模数据集聚类效率的问题， 类似研究的主要目的是优化K-means算法，减少数 着重研究单机多核环境下(CMP)K-means算法的并 据集的读取次数。有研究者从优化K-means聚类初 行化改进，提出了一种Multi-core K-means(MC-K- 始条件设置的角度，利用自适应技术、启发式算法以 means)算法。该算法对原K-means算法的聚类任务 及半监督技术等实现K-means初始聚类中心或者聚 进行了分解，设计了相互独立且均衡的聚类子任务 类个数的优化选择，加速K-means聚类的收敛过程， 交由各线程并行执行，能够充分利用现代CPU的多 提高聚类的效率以及结果的质量5。有研究人员 核计算能力，提高大规模数据集的聚类效率。 从减少大规模数据集数据维度的角度，降低聚类迭 代过程的计算量，提高K-means聚类算法的效 1 研究背景 率[8]。以上相关的研究工作切实提高了K-means 1.1确定性聚类的基本概念 聚类的效率，然而这些新算法并没有利用分布式环 金属橡胶隔振器在飞机液压管道上的应用如图 境提高聚类的效率。最近有研究人员进行了SMP 1所示，从图1看出，金属橡胶放置在外围卡箍的凹 DMP环境下的集群多处理器K-means聚类的研究 槽内，传统管道固定一般直接与外围卡箍接触或之 工作，提高了大规模数据集的聚类效率101。直接 间有薄的橡胶垫作为隔振装。 针对共享内存多处理器系统以及分布式内存多处理 器环境进行K-means的并行化，需要考虑复杂的数 Cluster1 Thread2 据划分、节点容错等并行化的基本问题且需要消耗 事 Data Set I hread 大量的节点间同步以及数据网络传输的时间。随着 类似Google MapReduce以及Apache的Hadoop的出 Cluster2 Threadl 现和广泛使用，在这些编程模型的基础之上进行分 ·Thread2 布式开发变得相对容易，分布式的基本问题可以依 o Threadl 靠基础编程模型来解决。很多研究人员利用Ma ●Thread2 pReduce的算法模型，针对K-means聚类过程的并 图1MC-K-means算法示意 行化进行了大量深入的研究工作，取得了很多重要 Fig.1 Illustration of MC-K-means 的研究成果，使得K-means算法可用于大规模数据 定义1确定性聚类的输入可以用一组有序对 集聚类的应用场合。然而这些算法更多考虑的是多 (X,s)或(X,d)来表示，这里X表示一组样本，s和 处理器分布式场景下的K-means并行化，较少考虑 d分别是度量样本间相似度或相异度（距离）的标 到单机CPU的多核利用。除此之外，并不是所有的 准。确定性聚类系统的输出是一个个分区，例如C= 聚类算法都适合以MapReduce的形式进行并行化 {C,C2,…,C},其中C,(i=1,2…,K)是X的子 的，且为了适应MapReduce的编程架构，有时反而 集，且满足：C1UC2U,…,UCk=X;C:∩C= 会增加额外的计算量与通信量[214。 ☑，i为。 现代CPU技术的发展，使得单机的运行环境也 C中的成员C,C2,…,C.叫做类或簇(Cus- 发生了极大的变化。多核处理器的出现提高了 ter),每一个类或簇都是通过一些特征描述的，通常 CPU的计算性能，降低了CPU的功耗。尽管如此， 有如下几种表示方式： 传统的算法并不能直接从多核CPU中获益，需要针 1)通过它们的中心或类的边界点表示空间的 对多核CPU的特点进行并行化改进与优化，才能充 类点。 分利用多核CPU的计算能力。因此，研究单机CMP 2)使用聚类树中的结点，图形化地表示一个类。 环境下K-means算法的并行化方法对提高单机K 3)使用样本属性的逻辑表达式表示类。 means算法的聚类效率具有重要的现实意义，并且
此相对应的内存频率却没有相对应的提高。 内存与 ＣＰＵ 之间处理数据的能力差距越来越大，极大地影 响了应用程序的性能。 同时，工程师们开始认识到， 仅仅提高单核芯片的频率会产生过多热量且无法带 来希望的性能改善。 于是，ＣＭＰ （ ｃｈｉｐ ｍｕｌｔｉ⁃ｐｒｏｃｅｓ⁃ ｓｏｒ）成为了先进处理器的发展趋势。 ＣＭＰ 可以在大 幅提高处理性能的同时降低 ＣＰＵ 主频，减少能源消 耗。 然而仅简单提供 ＣＭＰ 环境并不能直接带来应 用程序性能的提高，需要研发人员针对 ＣＭＰ 环境对 有关算法进行优化，才能使得应用程序更好的利用 ＣＰＵ 的多核计算能力，提高程序的运行效率［１］ 。 本文针对提高大规模数据集聚类效率的问题， 着重研究单机多核环境下（ＣＭＰ）Ｋ⁃ｍｅａｎｓ 算法的并 行化改进，提出了一种 Ｍｕｌｔｉ⁃ｃｏｒｅ Ｋ⁃ｍｅａｎｓ （ＭＣ⁃Ｋ⁃ ｍｅａｎｓ）算法。 该算法对原 Ｋ⁃ｍｅａｎｓ 算法的聚类任务 进行了分解，设计了相互独立且均衡的聚类子任务 交由各线程并行执行，能够充分利用现代 ＣＰＵ 的多 核计算能力，提高大规模数据集的聚类效率。 １ 研究背景 １．１ 确定性聚类的基本概念 金属橡胶隔振器在飞机液压管道上的应用如图 １ 所示，从图 １ 看出，金属橡胶放置在外围卡箍的凹 槽内，传统管道固定一般直接与外围卡箍接触或之 间有薄的橡胶垫作为隔振装 。 图 １ ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法示意 Ｆｉｇ． １ Ｉｌｌｕｓｔｒａｔｉｏｎ ｏｆ ＭＣ⁃Ｋ⁃ｍｅａｎｓ 定义 １ 确定性聚类的输入可以用一组有序对 （Ｘ， ｓ）或（Ｘ， ｄ）来表示，这里 Ｘ 表示一组样本，ｓ 和 ｄ 分别是度量样本间相似度或相异度（距离） 的标 准。 确定性聚类系统的输出是一个个分区，例如Ｃ ＝ ｛Ｃ１ ， Ｃ２ ，…， Ｃｋ｝，其中 Ｃｉ（ ｉ ＝ １，２…，Ｋ） 是 Ｘ 的子 集，且满足： Ｃ１ ∪ Ｃ２ ∪，… ， ∪ Ｃｋ ＝ Ｘ；Ｃｉ ∩ Ｃｊ ＝ ⌀， ｉ ¹ｊ 。 Ｃ 中的成员 Ｃ１ ， Ｃ２ ，…， Ｃｋ 叫做类或簇（Ｃｌｕｓ⁃ ｔｅｒ），每一个类或簇都是通过一些特征描述的，通常 有如下几种表示方式： １） 通过它们的中心或类的边界点表示空间的 一类点。 ２） 使用聚类树中的结点，图形化地表示一个类。 ３） 使用样本属性的逻辑表达式表示类。 １．２ 相关的研究工作 为了解决 Ｋ⁃ｍｅａｎｓ 算法对大规模数据集聚类效 率较低的问题，有研究者提出了只需要扫描一遍原 始数据集即产生聚类结果的算法。 这些算法只需读 入大规模数据集中的一部分进入主存或者分批读入 数据集进行聚类，扫描数据集一遍即完成聚类。 相 应的算法有 ｒａｎｄｏｍ⁃ｋｍｅａｎｓ， Ｄｙｎａｍｉｃ ｉｎｃｒｅｍｅｎｔａｌ Ｋ⁃ ｍｅａｎｓ ［２］ ， Ｓｉｎｇｌｅ ｐａｓｓ ｋｅｒｎｅｌ Ｋ⁃ｍｅａｎｓ ［３］ ， ｓｃａｌａｂｌｅ⁃ ｋｍｅａｎｓ ［４］ ，等。 其中，由 Ｍｉｃｒｏｓｏｆｔ Ｒｅｓｅａｒｃｈ 的 Ｒｅｄ⁃ ｍｏｎｄ 等提出的 ｓｃａｌａｂｌｅ⁃ｋｍｅａｎｓ 算法性能优越，受到 了广泛的重视，并被集成到 ＳＱＬ ＳＥＲＶＥＲ ２００８ 中。 类似研究的主要目的是优化 Ｋ⁃ｍｅａｎｓ 算法，减少数 据集的读取次数。 有研究者从优化 Ｋ⁃ｍｅａｎｓ 聚类初 始条件设置的角度，利用自适应技术、启发式算法以 及半监督技术等实现 Ｋ⁃ｍｅａｎｓ 初始聚类中心或者聚 类个数的优化选择，加速 Ｋ⁃ｍｅａｎｓ 聚类的收敛过程， 提高聚类的效率以及结果的质量［５⁃７］ 。 有研究人员 从减少大规模数据集数据维度的角度，降低聚类迭 代过 程 的 计 算 量， 提 高 Ｋ⁃ｍｅａｎｓ 聚 类 算 法 的 效 率［８⁃９］ 。 以上相关的研究工作切实提高了 Ｋ⁃ｍｅａｎｓ 聚类的效率，然而这些新算法并没有利用分布式环 境提高聚类的效率。 最近有研究人员进行了 ＳＭＰ、 ＤＭＰ 环境下的集群多处理器 Ｋ⁃ｍｅａｎｓ 聚类的研究 工作，提高了大规模数据集的聚类效率［１０⁃１１］ 。 直接 针对共享内存多处理器系统以及分布式内存多处理 器环境进行 Ｋ⁃ｍｅａｎｓ 的并行化，需要考虑复杂的数 据划分、节点容错等并行化的基本问题且需要消耗 大量的节点间同步以及数据网络传输的时间。 随着 类似 Ｇｏｏｇｌｅ ＭａｐＲｅｄｕｃｅ 以及 Ａｐａｃｈｅ 的 Ｈａｄｏｏｐ 的出 现和广泛使用，在这些编程模型的基础之上进行分 布式开发变得相对容易，分布式的基本问题可以依 靠基础编程模型来解决。 很多研究人员利用 Ｍａ⁃ ｐＲｅｄｕｃｅ 的算法模型，针对 Ｋ⁃ｍｅａｎｓ 聚类过程的并 行化进行了大量深入的研究工作，取得了很多重要 的研究成果，使得 Ｋ⁃ｍｅａｎｓ 算法可用于大规模数据 集聚类的应用场合。 然而这些算法更多考虑的是多 处理器分布式场景下的 Ｋ⁃ｍｅａｎｓ 并行化，较少考虑 到单机 ＣＰＵ 的多核利用。 除此之外，并不是所有的 聚类算法都适合以 ＭａｐＲｅｄｕｃｅ 的形式进行并行化 的，且为了适应 ＭａｐＲｅｄｕｃｅ 的编程架构，有时反而 会增加额外的计算量与通信量［１２⁃１４］ 。 现代 ＣＰＵ 技术的发展，使得单机的运行环境也 发生了极大的变化。 多核处理器的出现提高了 ＣＰＵ 的计算性能，降低了 ＣＰＵ 的功耗。 尽管如此， 传统的算法并不能直接从多核 ＣＰＵ 中获益，需要针 对多核 ＣＰＵ 的特点进行并行化改进与优化，才能充 分利用多核 ＣＰＵ 的计算能力。 因此，研究单机 ＣＭＰ 环境下 Ｋ⁃ｍｅａｎｓ 算法的并行化方法对提高单机 Ｋ⁃ ｍｅａｎｓ 算法的聚类效率具有重要的现实意义，并且 ·６０８· 智 能 系 统 学 报 第 １０ 卷
第4期 申彦，等：CMP上基于数据集划分的K-means多核优化算法 ·609· 与DMP、SMP环境下的K-means聚类过程可以有效 簇尽可能的紧凑和独立。 的结合，作为DMP、SMP环境下K-means聚类算法 算法lK-means(Dataset D,ClusterNumber K) 的有效补充。也有研究人员开始着手研究CMP环 输入：事务数据库D,聚类簇的数量K 境下K-menas算法的并行化，但是相关研究尚处于 输出：K个聚类，使得平方误差准则E最小 起步阶段，算法实现仍存在进一步改进的空 1)assign initial value for means; 间15.16 /任意选择k个对象作为初始的簇中心 1.3多核处理器的出现 2)REPEAT: 2005年，当主频接近4GHz时，CPU的主要制 3)FORj =1 to n DO assign each x;to the closest 造厂商英特尔和AMD公司发现单纯的主频提升已 clusters mean; 经无法明显提升系统整体性能。由于CPU片内流 /根据簇中对象的平均值将每个对象分配给最 水线过长，使得单位频率效能低下，加上由于缓存的 近的簇 增加和对漏电流控制的不利，造成CPU功耗大幅度 增加。随着功耗的增大，散热问题也越来越成为一 4))FOR=1okD0G∑6： 个无法逾越的障碍。于是，出现了多核心CPU的解 //更新簇的平均值，即计算每个簇中对象的平 决方案。 均值 其实较早以前已经有研究人员提出了利用单芯 片多核心处理器(CMP)技术来代替复杂度越来越 5)ComputeE=∑∑lx-x； i=i xeC 高的单核心CPU。BM、P、SUN等企业也在服务器 /计算准则函数E 领域投入了一定的多核CPU进行商用。然而由于 6)Until E.-E=<E,e为预先设定的一个 当时的服务器多核CPU价格过于昂贵、应用面窄、 较小的值： 并没有真正发展起来。 //表示E不再产生明显的变化 2006年，多核CPU进入了迅猛的发展时期，In- K-means是解决聚类问题的一种经典算法，该 tel的Core,Xeon以及AMD的Athlon,Barcelona等 算法实现起来较为简单且有非常好的可扩展性。因 受到了广泛的欢迎。这些CPU在性能得到极大提 此，很多科研人员在研究针对大规模数据集的高效 升的同时，功耗反而得到了降低。 聚类算法时，往往会以K-means算法作为首选进行 值得注意的是OS并不能自动的让某个应用程 改进和优化。 序直接利用CPU的多核，而是需要进行有关算法的 分析K-means算法的时间复杂度，其运行时间 CMP并行化改进。对于数据挖掘中的聚类、关联规 主要消耗在：1)数据集读取所产生的/0：2)判断每 则挖掘等计算密集型、/0密集型应用而言，对原有 一个数据点（数据记录）的所属类别；3)计算每一个 算法进行并行化改进，提高算法的执行效率，尽快给 类别（簇）的中心；4)计算准则函数E。而这4个阶 出挖掘结果成为了当务之急。研究具有较强的现实 段均可以很好地并行化，以此利用现代CPU的多核 意义山 特性，最大化的发挥CPU的性能，提高聚类效率。 2K-means算法详细描述 为此，本文提出了一种Muli-core K-means算法 (MC-K-means),该算法对上述4个过程分别进行并 K-means算法，也被称为K-平均或K-均值算 行化，充分利用CPU的多核特性，进一步提高K 法，是目前得到广泛应用的一种聚类算法)。其相 means算法的聚类效率。新算法可作为SMP、DMP 似度的计算根据一个簇中对象的平均值来进行。K 分布式环境下聚类算法以及增量OneScan聚类算法 means算法以k为参数，把n个数据点分为k个簇， 的有效补充，提高单节点的聚类效率，从而提高整体 使得簇内具有较高的相似度，而簇间的相似度较低。 的聚类效率。 算法首先随机地选择k个对象，每个对象初始 3 CMP上基于数据集划分的大规模 地代表了一个簇的平均值或中心。对剩余的每个对 数据集K-means多核优化算法 象根据其与各个簇中心的距离，将它赋予最近的簇， 3.1MC-K-means算法详细描述 然后重新计算每个簇的平均值。这个过程不断重 在CMP环境下对K-means聚类算法进行改进 复，直到准则函数收敛。准则函数定义为：E= 以适应大规模数据集，关键是要改进原有算法的串 三三：-。这里的准测西数E是数据集中所 行执行部分为并行执行。分析K-means算法可以发 现，在较为消耗资源的数据集读取阶段、数据点所属 有数据点的平方误差总和，x是数据集空间中的点， 类别判断阶段、每个新簇的簇中心计算阶段以及准 x:是簇C:的平均值。准则函数E使得生成的结果 则函数的计算阶段，这些阶段均可进行并行化改进
与 ＤＭＰ、ＳＭＰ 环境下的 Ｋ⁃ｍｅａｎｓ 聚类过程可以有效 的结合，作为 ＤＭＰ、ＳＭＰ 环境下 Ｋ⁃ｍｅａｎｓ 聚类算法 的有效补充。 也有研究人员开始着手研究 ＣＭＰ 环 境下 Ｋ⁃ｍｅｎａｓ 算法的并行化，但是相关研究尚处于 起步 阶 段， 算 法 实 现 仍 存 在 进 一 步 改 进 的 空 间［１５⁃１６］ 。 １．３ 多核处理器的出现 ２００５ 年，当主频接近 ４ ＧＨｚ 时，ＣＰＵ 的主要制 造厂商英特尔和 ＡＭＤ 公司发现单纯的主频提升已 经无法明显提升系统整体性能。 由于 ＣＰＵ 片内流 水线过长，使得单位频率效能低下，加上由于缓存的 增加和对漏电流控制的不利，造成 ＣＰＵ 功耗大幅度 增加。 随着功耗的增大，散热问题也越来越成为一 个无法逾越的障碍。 于是，出现了多核心 ＣＰＵ 的解 决方案。 其实较早以前已经有研究人员提出了利用单芯 片多核心处理器（ＣＭＰ）技术来代替复杂度越来越 高的单核心 ＣＰＵ。 ＩＢＭ、ＩＰ、ＳＵＮ 等企业也在服务器 领域投入了一定的多核 ＣＰＵ 进行商用。 然而由于 当时的服务器多核 ＣＰＵ 价格过于昂贵、应用面窄、 并没有真正发展起来。 ２００６ 年，多核 ＣＰＵ 进入了迅猛的发展时期，Ｉｎ⁃ ｔｅｌ 的 Ｃｏｒｅ， Ｘｅｏｎ 以及 ＡＭＤ 的 Ａｔｈｌｏｎ，Ｂａｒｃｅｌｏｎａ 等 受到了广泛的欢迎。 这些 ＣＰＵ 在性能得到极大提 升的同时，功耗反而得到了降低。 值得注意的是 ＯＳ 并不能自动的让某个应用程 序直接利用 ＣＰＵ 的多核，而是需要进行有关算法的 ＣＭＰ 并行化改进。 对于数据挖掘中的聚类、关联规 则挖掘等计算密集型、Ｉ／ Ｏ 密集型应用而言，对原有 算法进行并行化改进，提高算法的执行效率，尽快给 出挖掘结果成为了当务之急。 研究具有较强的现实 意义［１］ 。 ２ Ｋ⁃ｍｅａｎｓ 算法详细描述 Ｋ⁃ｍｅａｎｓ 算法，也被称为 Ｋ⁃平均或 Ｋ⁃均值算 法，是目前得到广泛应用的一种聚类算法［１７］ 。 其相 似度的计算根据一个簇中对象的平均值来进行。 Ｋ⁃ ｍｅａｎｓ 算法以 ｋ 为参数，把 ｎ 个数据点分为 ｋ 个簇， 使得簇内具有较高的相似度，而簇间的相似度较低。 算法首先随机地选择 ｋ 个对象，每个对象初始 地代表了一个簇的平均值或中心。 对剩余的每个对 象根据其与各个簇中心的距离，将它赋予最近的簇， 然后重新计算每个簇的平均值。 这个过程不断重 复，直到准则函数收敛。 准则函数定义为： Ｅ ＝ ∑ ｋ ｉ ＝ １ ∑ｘ∈Ｃｉ ｘ － ｘｉ ２ 。 这里的准则函数 Ｅ 是数据集中所 有数据点的平方误差总和，ｘ 是数据集空间中的点， ｘｉ 是簇 Ｃｉ的平均值。 准则函数 Ｅ 使得生成的结果 簇尽可能的紧凑和独立。 算法 １ Ｋ⁃ｍｅａｎｓ （Ｄａｔａｓｅｔ Ｄ， ＣｌｕｓｔｅｒＮｕｍｂｅｒ Ｋ） 输入：事务数据库 Ｄ，聚类簇的数量 Ｋ 输出：Ｋ 个聚类，使得平方误差准则 Ｅ 最小 １） ａｓｓｉｇｎ ｉｎｉｔｉａｌ ｖａｌｕｅ ｆｏｒ ｍｅａｎｓ； ／ ／ 任意选择 ｋ 个对象作为初始的簇中心 ２） ＲＥＰＥＡＴ； ３）ＦＯＲ ｊ ＝ １ ｔｏ ｎ ＤＯ ａｓｓｉｇｎ ｅａｃｈ ｘｊ ｔｏ ｔｈｅ ｃｌｏｓｅｓｔ ｃｌｕｓｔｅｒｓ ｍｅａｎ； ／ ／ 根据簇中对象的平均值将每个对象分配给最 近的簇 ４）ＦＯＲ ｉ ＝ １ ｔｏ ｋ ＤＯ ｘｉ ＝ １ Ｃｉ ∑ｘ∈Ｃｉ ｘ ； ／ ／ 更新簇的平均值，即计算每个簇中对象的平 均值 ５）Ｃｏｍｐｕｔｅ Ｅ ＝ ∑ ｋ ｉ ＝ １ ∑ｘ∈Ｃｉ ｘ － ｘｉ ２ ； ／ ／ 计算准则函数 Ｅ ６） Ｕｎｔｉｌ Ｅｎｅｗ － Ｅｌａｓｔ ＜ ε ， ε 为预先设定的一个 较小的值； ／ ／ 表示 Ｅ 不再产生明显的变化 Ｋ⁃ｍｅａｎｓ 是解决聚类问题的一种经典算法，该 算法实现起来较为简单且有非常好的可扩展性。 因 此，很多科研人员在研究针对大规模数据集的高效 聚类算法时，往往会以 Ｋ⁃ｍｅａｎｓ 算法作为首选进行 改进和优化。 分析 Ｋ⁃ｍｅａｎｓ 算法的时间复杂度，其运行时间 主要消耗在：１）数据集读取所产生的 Ｉ／ Ｏ；２）判断每 一个数据点（数据记录）的所属类别；３）计算每一个 类别（簇）的中心；４）计算准则函数 Ｅ。 而这 ４ 个阶 段均可以很好地并行化，以此利用现代 ＣＰＵ 的多核 特性，最大化的发挥 ＣＰＵ 的性能，提高聚类效率。 为此，本文提出了一种 Ｍｕｌｔｉ⁃ｃｏｒｅ Ｋ⁃ｍｅａｎｓ 算法 （ＭＣ⁃Ｋ⁃ｍｅａｎｓ），该算法对上述 ４ 个过程分别进行并 行化，充分利用 ＣＰＵ 的多核特性，进一步提高 Ｋ⁃ ｍｅａｎｓ 算法的聚类效率。 新算法可作为 ＳＭＰ、ＤＭＰ 分布式环境下聚类算法以及增量 ＯｎｅＳｃａｎ 聚类算法 的有效补充，提高单节点的聚类效率，从而提高整体 的聚类效率。 ３ ＣＭＰ 上基于数据集划分的大规模 数据集 Ｋ⁃ｍｅａｎｓ 多核优化算法 ３．１ ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法详细描述 在 ＣＭＰ 环境下对 Ｋ⁃ｍｅａｎｓ 聚类算法进行改进 以适应大规模数据集，关键是要改进原有算法的串 行执行部分为并行执行。 分析 Ｋ⁃ｍｅａｎｓ 算法可以发 现，在较为消耗资源的数据集读取阶段、数据点所属 类别判断阶段、每个新簇的簇中心计算阶段以及准 则函数的计算阶段，这些阶段均可进行并行化改进， 第 ４ 期 申彦，等：ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 ·６０９·
·610 智能系统学报 第10卷 且由于其所需计算的性质，都可以较好的做到多核 partly,ji=1,2,…,n,i=1,2,…,k; 之间的负载均衡。 19)until every equally data_set,is finished; 改进后的MC-K-means算法详细描述如下。其 20)join the results of every task to get total_E;= 中关键步骤如图1所示，为了方便描述，图中以2线 程为例进行说明，可推广到n线程的情形。 (,)i=1,2 算法2MC-K-means(Dataset D,ClusterNumber K) 输入：事务数据库D,聚类的簇的数量K 2DE=芝alE: i=1 输出：K个聚类，使得平方误差准则E最小 22)until Ee-Ei<s,s is a preset very small 1)random assign initial value for means; threshold /任意选择k个对象作为初始的簇中心 在读入外存数据时，考虑到数据源可能存在于 2)thread_count=Runtime.getRunTime().avail- 网络数据库中，在读取时会有一定的延时，多开线程 abkleProcessors/(1-blockCoefficient);0<=blockCoef- 可有效利用CPU的多核，因此考虑设置Runtime.ge ficient<1; tRunTime ()availabkleProcessors/(1-blockCoeffi- /计算线程数 cient)大小的线程池，其中blockCoeff伍cient=数据记 3)executeService service Excute.new- 录/0阻塞时间/数据记录处理时间，在运行时可根 FixedThreadPool(thread_count); 据数据源的延时动态凋整。 1/创建线程池 在装载数据之后，判断每一数据点的所属类别 4)divide the data set into n parts equally and cre- 时采用的是欧几里得距离的平方d(x,y)2= ate n tasks to read every data set,where n=thread [∑1x,一，P门。该计算对于每个数据点的计算 count; /装载数据 量均是相同的，等分数据即可做到负载平衡。除此 5)thread_count Runtime.getRunTime().avail- 之外，该过程是计算密集型的，多开线程对提高效率 abkleProcessors; 无益，反而会因为CPU频繁的线程切换而降低运行 6)threadPool Excute.newFixedThreadPool 效率。因此开设线程个数与CPU核心数avail-. (thread_count); abkleProcessors相同的线程池：又因为距离计算任务 /创建线程池，计算准则函数E 的计算量对每个数据点是一样的，所以MC-K-means 7)divide the data set into n parts equally and cre- 算法等分数据，创建availabkleProcessors个任务进 ate n tasks to compute the category,where n thread_ 行数据点类别判断的计算，并交由线程池调度执行。 count; 计算每一个聚类簇的簇中心，仍然是一个计算 8)repeat 密集型的任务，因此在此阶段开设线程数与CPU核 9)for every data_seti 心数相同的线程池。MC-K-means算法针对之前等 10)let one task;to assign each data point of the 分的数据集，每个线程广计算被分配的数据集归属 data_set,to the closest clusters center and record the 于每个分类i的sum,以及num:,并汇总j个线程的 category; 结果得到total_sum与以及total_num与，最终得到 11)until every data_set,is finished; cluster_center:,。采用针对等分数据集的方法使得 12)for every equally data_.set//计算每个簇的簇 簇中心计算的各任务相对均衡。在准则函数E的 中心； 计算过程中也采用了同样的负载均衡的方法。 13)let one task;to compute the sum;and num of CMP系统是共享内存的，上述MC-K-means算 data_set,partly,j=1,2,…n,i=1,2,…k; 法仅在访问共享变量及每部分数据处理完毕时需要 14)until every equally data_set,is finished; 进行同步，避免了数据集通过网络在节点之间传输 15)join the results of every task,to get total_sum= 造成的时间消耗，算法具有较高的执行效率。 (um）,almm=(um,）,i=1,2: 4实验结果以及分析 j=1 j=1 16)cluster_center;total_sum,/total_num;,i= 为了验证算法的有效性，依据前述MC-K-means 1,2,…,k; 算法的主要思想，使用Java语言实现了MC-K //每个线程均可访问中心值，以便再次划分数据 means以及K-means算法1-i9。实验平台为HP 17)for every equally data_set,//计算每个簇部分 PR03380MT,Window XP_SP3,4GB内存，jdk7u51 准则函数 以及HP ProLiant DL388pGen8,RedHat9.0,32GB 18)let one task,to compute the E of data_set 内存，jdk7u51。因为是做CPU多核加速的有关实
且由于其所需计算的性质，都可以较好的做到多核 之间的负载均衡。 改进后的 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法详细描述如下。 其 中关键步骤如图 １ 所示，为了方便描述，图中以 ２ 线 程为例进行说明，可推广到 ｎ 线程的情形。 算法２ ＭＣ⁃Ｋ⁃ｍｅａｎｓ （Ｄａｔａｓｅｔ Ｄ， ＣｌｕｓｔｅｒＮｕｍｂｅｒ Ｋ） 输入：事务数据库 Ｄ，聚类的簇的数量 Ｋ 输出：Ｋ 个聚类，使得平方误差准则 Ｅ 最小 １） ｒａｎｄｏｍ ａｓｓｉｇｎ ｉｎｉｔｉａｌ ｖａｌｕｅ ｆｏｒ ｍｅａｎｓ； ／ ／ 任意选择 ｋ 个对象作为初始的簇中心 ２）ｔｈｒｅａｄ ＿ｃｏｕｎｔ ＝ Ｒｕｎｔｉｍｅ． ｇｅｔＲｕｎＴｉｍｅ （ ）． ａｖａｉｌ⁃ ａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ／ （１－ｂｌｏｃｋＣｏｅｆｆｉｃｉｅｎｔ）；０＜ ＝ ｂｌｏｃｋＣｏｅｆ⁃ ｆｉｃｉｅｎｔ＜１； ／ ／ 计算线程数 ３ ） ｅｘｅｃｕｔｅＳｅｒｖｉｃｅ ｓｅｒｖｉｃｅ ＝ Ｅｘｃｕｔｅ． ｎｅｗ⁃ ＦｉｘｅｄＴｈｒｅａｄＰｏｏｌ（ｔｈｒｅａｄ＿ｃｏｕｎｔ）； ／ ／ 创建线程池 ４） ｄｉｖｉｄｅ ｔｈｅ ｄａｔａ ｓｅｔ ｉｎｔｏ ｎ ｐａｒｔｓ ｅｑｕａｌｌｙ ａｎｄ ｃｒｅ⁃ ａｔｅ ｎ ｔａｓｋｓ ｔｏ ｒｅａｄ ｅｖｅｒｙ ｄａｔａ ｓｅｔ， ｗｈｅｒｅ ｎ ＝ ｔｈｒｅａｄ＿ ｃｏｕｎｔ； ／ ／ 装载数据 ５）ｔｈｒｅａｄ ＿ｃｏｕｎｔ ＝ Ｒｕｎｔｉｍｅ． ｇｅｔＲｕｎＴｉｍｅ （ ）． ａｖａｉｌ⁃ ａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ； ６ ） ｔｈｒｅａｄＰｏｏｌ ＝ Ｅｘｃｕｔｅ． ｎｅｗＦｉｘｅｄＴｈｒｅａｄＰｏｏｌ （ｔｈｒｅａｄ＿ｃｏｕｎｔ）； ／ ／ 创建线程池，计算准则函数 Ｅ ７） ｄｉｖｉｄｅ ｔｈｅ ｄａｔａ ｓｅｔ ｉｎｔｏ ｎ ｐａｒｔｓ ｅｑｕａｌｌｙ ａｎｄ ｃｒｅ⁃ ａｔｅ ｎ ｔａｓｋｓ ｔｏ ｃｏｍｐｕｔｅ ｔｈｅ ｃａｔｅｇｏｒｙ， ｗｈｅｒｅ ｎ ＝ ｔｈｒｅａｄ＿ ｃｏｕｎｔ； ８） ｒｅｐｅａｔ ９） ｆｏｒ ｅｖｅｒｙ ｄａｔａ＿ｓｅｔｊ １０） ｌｅｔ ｏｎｅ ｔａｓｋｊ ｔｏ ａｓｓｉｇｎ ｅａｃｈ ｄａｔａ ｐｏｉｎｔ ｏｆ ｔｈｅ ｄａｔａ＿ｓｅｔ ｊ ｔｏ ｔｈｅ ｃｌｏｓｅｓｔ ｃｌｕｓｔｅｒｓ ｃｅｎｔｅｒ ａｎｄ ｒｅｃｏｒｄ ｔｈｅ ｃａｔｅｇｏｒｙ； １１）ｕｎｔｉｌ ｅｖｅｒｙ ｄａｔａ＿ｓｅｔ ｊ ｉｓ ｆｉｎｉｓｈｅｄ； １２）ｆｏｒ ｅｖｅｒｙ ｅｑｕａｌｌｙ ｄａｔａ＿ｓｅｔ ｊ ／ ／ 计算每个簇的簇 中心； １３）ｌｅｔ ｏｎｅ ｔａｓｋｊ ｔｏ ｃｏｍｐｕｔｅ ｔｈｅ ｓｕｍｉｊ ａｎｄ ｎｕｍｉｊ ｏｆ ｄａｔａ＿ｓｅｔ ｊｐａｒｔｌｙ， ｊ ＝ １，２，…ｎ， ｉ ＝ １，２，…ｋ ； １４）ｕｎｔｉｌ ｅｖｅｒｙ ｅｑｕａｌｌｙ ｄａｔａ＿ｓｅｔ ｊ ｉｓ ｆｉｎｉｓｈｅｄ； １５）ｊｏｉｎ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｅｖｅｒｙ ｔａｓｋｊ ｔｏ ｇｅｔ ｔｏｔａｌ＿ｓｕｍ ｉ ＝ （∑ ｊ ＝ ｎ ｊ ＝ １ ｓｕｍｉｊ） ， ｔｏｔａｌ＿ｎｕｍｉ ＝ （∑ ｊ ＝ ｎ ｊ ＝ １ ｎｕｍｉｊ） ， ｉ ＝１，２，…，ｋ； １６） ｃｌｕｓｔｅｒ ＿ ｃｅｎｔｅｒｉ ＝ ｔｏｔａｌ＿ｓｕｍｉ ／ ｔｏｔａｌ＿ｎｕｍｉ，ｉ ＝ １，２，…，ｋ； ／ ／ 每个线程均可访问中心值，以便再次划分数据 １７）ｆｏｒ ｅｖｅｒｙ ｅｑｕａｌｌｙ ｄａｔａ＿ｓｅｔ ｊ ／ ／ 计算每个簇部分 准则函数 １８）ｌｅｔ ｏｎｅ ｔａｓｋｊ ｔｏ ｃｏｍｐｕｔｅ ｔｈｅ Ｅｉｊ ｏｆ ｄａｔａ ＿ ｓｅｔ ｊ ｐａｒｔｌｙ， ｊ ＝ １，２，…，ｎ， ｉ ＝ １，２，…，ｋ； １９）ｕｎｔｉｌ ｅｖｅｒｙ ｅｑｕａｌｌｙ ｄａｔａ＿ｓｅｔ ｊ ｉｓ ｆｉｎｉｓｈｅｄ； ２０）ｊｏｉｎ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｅｖｅｒｙ ｔａｓｋｊ ｔｏ ｇｅｔ ｔｏｔａｌ＿Ｅｉ ＝ （∑ ｊ ＝ ｎ ｊ ＝ １ Ｅｉｊ） ， ｉ ＝ １，２，…，ｋ； ２１） Ｅ ＝ ∑ ｉ ＝ ｋ ｉ ＝ １ ｔｏｔａｌ＿Ｅｉ ； ２２）ｕｎｔｉｌ Ｅｎｅｗ － Ｅｌａｓｔ ＜ ε ， ε ｉｓ ａ ｐｒｅｓｅｔ ｖｅｒｙ ｓｍａｌｌ ｔｈｒｅｓｈｏｌｄ 在读入外存数据时，考虑到数据源可能存在于 网络数据库中，在读取时会有一定的延时，多开线程 可有效利用 ＣＰＵ 的多核，因此考虑设置 Ｒｕｎｔｉｍｅ．ｇｅ⁃ ｔＲｕｎＴｉｍｅ （ ）． ａｖａｉｌａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ／ （ １⁃ｂｌｏｃｋＣｏｅｆｆｉ⁃ ｃｉｅｎｔ）大小的线程池，其中 ｂｌｏｃｋＣｏｅｆｆｉｃｉｅｎｔ ＝ 数据记 录 Ｉ／ Ｏ 阻塞时间／ 数据记录处理时间，在运行时可根 据数据源的延时动态调整。 在装载数据之后，判断每一数据点的所属类别 时采 用 的 是 欧 几 里 得 距 离 的 平 方 ｄ （ｘ，ｙ） ２ ＝ ∑ ｎ ｉ ＝ １ ｘｉ － ｙｉ ２ [ ] 。 该计算对于每个数据点的计算 量均是相同的，等分数据即可做到负载平衡。 除此 之外，该过程是计算密集型的，多开线程对提高效率 无益，反而会因为 ＣＰＵ 频繁的线程切换而降低运行 效率。 因此开设线程个 数 与 ＣＰＵ 核 心 数 ａｖａｉｌ⁃ ａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ 相同的线程池；又因为距离计算任务 的计算量对每个数据点是一样的，所以 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法等分数据，创建 ａｖａｉｌａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ 个任务进 行数据点类别判断的计算，并交由线程池调度执行。 计算每一个聚类簇的簇中心，仍然是一个计算 密集型的任务，因此在此阶段开设线程数与 ＣＰＵ 核 心数相同的线程池。 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法针对之前等 分的数据集，每个线程 ｊ 计算被分配的数据集归属 于每个分类 ｉ 的 ｓｕｍｉｊ 以及 ｎｕｍｉｊ ，并汇总 ｊ 个线程的 结果得到 ｔｏｔａｌ＿ｓｕｍｉｊ 以及 ｔｏｔａｌ＿ｎｕｍｉｊ ， 最终 得 到 ｃｌｕｓｔｅｒ＿ｃｅｎｔｅｒｉ 。 采用针对等分数据集的方法使得 簇中心计算的各任务相对均衡。 在准则函数 Ｅ 的 计算过程中也采用了同样的负载均衡的方法。 ＣＭＰ 系统是共享内存的，上述 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算 法仅在访问共享变量及每部分数据处理完毕时需要 进行同步，避免了数据集通过网络在节点之间传输 造成的时间消耗，算法具有较高的执行效率。 ４ 实验结果以及分析 为了验证算法的有效性，依据前述 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法 的 主 要 思 想， 使 用 Ｊａｖａ 语 言 实 现 了 ＭＣ⁃Ｋ⁃ ｍｅａｎｓ 以 及 Ｋ⁃ｍｅａｎｓ 算 法［１８⁃１９］ 。 实 验 平 台 为 ＨＰ ＰＲＯ ３３８０ ＭＴ，Ｗｉｎｄｏｗ ＸＰ＿ＳＰ３，４ ＧＢ 内存，ｊｄｋ７ｕ５１ 以及 ＨＰ ＰｒｏＬｉａｎｔ ＤＬ３８８ｐ Ｇｅｎ８， ＲｅｄＨａｔ ９．０，３２ ＧＢ 内存，ｊｄｋ７ｕ５１。 因为是做 ＣＰＵ 多核加速的有关实 ·６１０· 智 能 系 统 学 报 第 １０ 卷
第4期 申彦，等：CMP上基于数据集划分的K-means多核优化算法 ·611- 验，所以需要针对不同实验平台中不同类型的CPU 个数据点的所属类别、计算簇中心以及计算准则函 进行测试。HPPR03380MT平台采用的CPU是 数E这4个阶段均进行了并行化改进。且在这4个 Intel i3-3240@3.40GHz,核心类型为Ivy Bridge,64 阶段中，每个数据点的任务量是相当的，因此MC-K- 位CPU,双核，四线程，支持超线程技术，3MB三级 means算法所采取的等分数据集的方法可以取得较 缓存，双通道。HP ProLiant DL388pGen8平台采用 好的负载均衡性，算法取得了对比算法中最高的加 的CPU是Intel Xeon E5-2609@2.40GHz,核心类型 速率。 为Sandy Bridge,64位CPU,四核，四线程，10MB三 PKMeans_.MT算法取得了较低的加速率。分析 级缓存，四通道。 算法可知，该算法仅在读取数据集以及迭代计算每 对比算法为文献[l5]描述的基于MapReduce 个数据点的归属时利用parfor函数进行了并行化。 的并行K-means算法(PKMeans_MR)以及文献[l6] 对新分类中心点的计算及准则函数的计算均没有并 描述的PKMeans_.MT算法。在实验中根据上述文 行化，且算法需要依托MATLAB平台，故取得了较 献描述的算法思想分别实现了各算法进行对比实 低的加速率。 验。因为相同初始化条件下各算法最终聚类的结果 PKMeans_.MR算法在对比算法中取得了最低的 是一样的，所以实验主要对比分析相关算法的执行 加速率。分析算法可知，PKMeans_.MR算法改进原 时间以及加速率情况。 K-means算法，使其以MapReduce方式运行，节点之 4.1人工生成数据集测试 间在迭代时需要多次通信、多次同步，且算法需适应 人工生成数据集由数据生成程序根据K个高 MapReduce固有模式，降低了算法的运行效率，因此 斯分布随机产生，每个高斯分布设置一个随机权重 取得了最低的加速率。但对比原K-means算法仍提 来确定是否产生数据。每一个高斯分布的中心是随 高了一倍多的运行效率。 机产生的，区间为[-5,5]。数据点每个维度值的产 可以看出，对K-means进行并行化改进，适应了 生区间为[0.7,1.5]。产生的人工数据集包含100 多核CPU的发展趋势，可以极大程度提高算法的运 维，180000个数据点，数据集使用二进制bin文件 行效率，满足处理大规模数据集的需要。 保存。本次实验因为数据集以及聚类测试算法是在 同一台计算机上的，所以读取数据集时的阻塞系数 30 28.24 25.28 blockCoefficient设置为0。聚类簇数量设置为k=5。 整个实验随机产生5个不同的人工生成数据 20 =5 集，针对每个数据集，分别执行MC-K-means、PK- 15 11.47 :水 PKMeans MR 10 1001 9.029.35 Means_.MR、PKMeans_MT以及K-means算法各I0 7.028 oK-means 次，各自共运行50次，最后以聚类时间的平均值作 5 为算法聚类效率的评价。实验结果如图2、3所示。 Intel Xeon E5-2609Intel i3-3240 该数据集较为规整，算法运行收敛较快。从实 操作平台 验结果可以看出：针对服务器领域的Xeon E5-2609, 图2运行时间对比 虽然主频较低，但依靠较大的L3缓存以及四通道 Fig.2 Comparison of run time 的内存控制器，使得各算法取得了较高的执行效率。 4.00r 3.60 K-means算法在该平台环境下执行消耗了25.28s, 3.50 3.10 PKMeans_.MR消耗了10.01s,PKMeans_MT消耗了 3.00 3.133.02 2.53 2.16 =5 2.50 8.15s,MC-K-means则需要7.02s。而在i3-3240所 2.00 MC-K-means 在平台环境下，K-means算法消耗了28.24s,PK- 翼 PKMeans MT 1.50 PKMeans MR 1.00 Means_MR消耗了11.47s,PKMeans_MT消耗了 0.50 9.35s,MC-K-means在该平台则需要9.02s。从并 0 Intel Xeon E5-2609 Intel i3-3240 行化改造后各算法的执行结果来看，在Xeon E5- 操作平台 2609所在平台，算法获得了更高的加速比。这主要 图3加速率对比 是由于Xeon E5-2609是四核四线程的，拥有真实的 Fig.3 Comparison of speedup rate 四核心，可以更好地并行完成各并行化算法划分的 逐步增大生成数据集的规模，生成的人工数据 多任务聚类工作。而3-3240是双核心的，依靠超 集为100维，分别包含180000个数据点，360000 线程技术实现的四线程并行，但是CPU的双物理核 个数据点，540000个数据点，720000个数据点， 心需要频繁的进行线程上下文的切换，消耗了一部 900000个数据点。在Intel Xeon E5-2609平台测试 分的运行时间，获得了较低的加速比。 每个算法的加速率。实验每次随机产生2个相同大 其中，MC-Kmeans算法在读取数据集、判断每
验，所以需要针对不同实验平台中不同类型的 ＣＰＵ 进行测试。 ＨＰ ＰＲＯ ３３８０ ＭＴ 平台采用的 ＣＰＵ 是 Ｉｎｔｅｌ ｉ３⁃３２４０＠ ３．４０ ＧＨｚ，核心类型为 Ｉｖｙ Ｂｒｉｄｇｅ，６４ 位 ＣＰＵ，双核，四线程，支持超线程技术，３ ＭＢ 三级 缓存，双通道。 ＨＰ ＰｒｏＬｉａｎｔ ＤＬ３８８ｐ Ｇｅｎ８ 平台采用 的 ＣＰＵ 是 Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５⁃２６０９＠ ２．４０ ＧＨｚ，核心类型 为 Ｓａｎｄｙ Ｂｒｉｄｇｅ，６４ 位 ＣＰＵ，四核，四线程，１０ ＭＢ 三 级缓存，四通道。 对比算法为文献［１５］ 描述的基于 ＭａｐＲｅｄｕｃｅ 的并行 Ｋ⁃ｍｅａｎｓ 算法（ＰＫＭｅａｎｓ＿ＭＲ）以及文献［１６］ 描述的 ＰＫＭｅａｎｓ＿ＭＴ 算法。 在实验中根据上述文 献描述的算法思想分别实现了各算法进行对比实 验。 因为相同初始化条件下各算法最终聚类的结果 是一样的，所以实验主要对比分析相关算法的执行 时间以及加速率情况。 ４．１ 人工生成数据集测试 人工生成数据集由数据生成程序根据 Ｋ 个高 斯分布随机产生，每个高斯分布设置一个随机权重 来确定是否产生数据。 每一个高斯分布的中心是随 机产生的，区间为［－５，５］。 数据点每个维度值的产 生区间为［０．７，１．５］。 产生的人工数据集包含 １００ 维，１８０ ０００ 个数据点，数据集使用二进制 ｂｉｎ 文件 保存。 本次实验因为数据集以及聚类测试算法是在 同一台计算机上的，所以读取数据集时的阻塞系数 ｂｌｏｃｋＣｏｅｆｆｉｃｉｅｎｔ 设置为 ０。 聚类簇数量设置为 ｋ ＝ ５。 整个实验随机产生 ５ 个不同的人工生成数据 集，针对每个数据集，分别执行 ＭＣ⁃Ｋ⁃ｍｅａｎｓ、 ＰＫ⁃ Ｍｅａｎｓ＿ＭＲ、ＰＫＭｅａｎｓ＿ＭＴ 以及 Ｋ⁃ｍｅａｎｓ 算法各 １０ 次，各自共运行 ５０ 次，最后以聚类时间的平均值作 为算法聚类效率的评价。 实验结果如图 ２、３ 所示。 该数据集较为规整，算法运行收敛较快。 从实 验结果可以看出：针对服务器领域的 Ｘｅｏｎ Ｅ５⁃２６０９， 虽然主频较低，但依靠较大的 Ｌ３ 缓存以及四通道 的内存控制器，使得各算法取得了较高的执行效率。 Ｋ⁃ｍｅａｎｓ 算法在该平台环境下执行消耗了 ２５．２８ ｓ， ＰＫＭｅａｎｓ＿ＭＲ 消耗了 １０．０１ ｓ，ＰＫＭｅａｎｓ＿ＭＴ 消耗了 ８．１５ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 则需要 ７．０２ ｓ。 而在 ｉ３⁃３２４０ 所 在平台环境下，Ｋ⁃ｍｅａｎｓ 算法消耗了 ２８． ２４ ｓ，ＰＫ⁃ Ｍｅａｎｓ＿ＭＲ 消耗了 １１． ４７ ｓ， ＰＫＭｅａｎｓ ＿ＭＴ 消耗了 ９．３５ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 在该平台则需要 ９．０２ ｓ。 从并 行化改造后各算法的执行结果来看，在 Ｘｅｏｎ Ｅ５⁃ ２６０９ 所在平台，算法获得了更高的加速比。 这主要 是由于 Ｘｅｏｎ Ｅ５⁃２６０９ 是四核四线程的，拥有真实的 四核心，可以更好地并行完成各并行化算法划分的 多任务聚类工作。 而 ｉ３⁃３２４０ 是双核心的，依靠超 线程技术实现的四线程并行，但是 ＣＰＵ 的双物理核 心需要频繁的进行线程上下文的切换，消耗了一部 分的运行时间，获得了较低的加速比。 其中，ＭＣ⁃Ｋｍｅａｎｓ 算法在读取数据集、判断每 个数据点的所属类别、计算簇中心以及计算准则函 数 Ｅ 这 ４ 个阶段均进行了并行化改进。 且在这 ４ 个 阶段中，每个数据点的任务量是相当的，因此 ＭＣ⁃Ｋ⁃ ｍｅａｎｓ 算法所采取的等分数据集的方法可以取得较 好的负载均衡性，算法取得了对比算法中最高的加 速率。 ＰＫＭｅａｎｓ＿ＭＴ 算法取得了较低的加速率。 分析 算法可知，该算法仅在读取数据集以及迭代计算每 个数据点的归属时利用 ｐａｒｆｏｒ 函数进行了并行化。 对新分类中心点的计算及准则函数的计算均没有并 行化，且算法需要依托 ＭＡＴＬＡＢ 平台，故取得了较 低的加速率。 ＰＫＭｅａｎｓ＿ＭＲ 算法在对比算法中取得了最低的 加速率。 分析算法可知，ＰＫＭｅａｎｓ＿ＭＲ 算法改进原 Ｋ⁃ｍｅａｎｓ 算法，使其以 ＭａｐＲｅｄｕｃｅ 方式运行，节点之 间在迭代时需要多次通信、多次同步，且算法需适应 ＭａｐＲｅｄｕｃｅ 固有模式，降低了算法的运行效率，因此 取得了最低的加速率。 但对比原 Ｋ⁃ｍｅａｎｓ 算法仍提 高了一倍多的运行效率。 可以看出，对 Ｋ⁃ｍｅａｎｓ 进行并行化改进，适应了 多核 ＣＰＵ 的发展趋势，可以极大程度提高算法的运 行效率，满足处理大规模数据集的需要。 图 ２ 运行时间对比 Ｆｉｇ． ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｕｎ ｔｉｍｅ 图 ３ 加速率对比 Ｆｉｇ． ３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｓｐｅｅｄｕｐ ｒａｔｅ 逐步增大生成数据集的规模，生成的人工数据 集为 １００ 维，分别包含 １８０ ０００ 个数据点，３６０ ０００ 个数据点，５４０ ０００ 个数据点，７２０ ０００ 个数据点， ９００ ０００个数据点。 在 Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５⁃２６０９ 平台测试 每个算法的加速率。 实验每次随机产生 ２ 个相同大 第 ４ 期 申彦，等：ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 ·６１１·
.612. 智能系统学报 第10卷 小的人工数据集，针对每个数据集，分别执行MC-K- k的取值对多核加速效率的影响。设置k为10，再 means、PKMeans_.MR、PKMeans_MT、K-means算法各 次变换数据集大小从180K至900K,重复上述实验 10次，各算法每阶段各自共运行20次，最后分别记 过程，记录实验结果如图6所示，各算法加速率如图 录下针对每个大小的数据集各算法聚类的平均时 7及表2所示。 间。k的取值为5。实验结果如图4所示，各算法加 表2不同数据集大小下的加速率详情 速率如图5及表1所示。 Table 2 Speedup rate details of different data size 140「 Data Set MC-K- k=5 PKMeans_ PKMeans_ ◆+-MC-K-neans 120 Size/x103 means MT MR -PKMeans_MT 100 PKMcans MR 180 3.71 3.16 2.52 80 ◆-K means 360 3.73 3.23 2.53 60 540 3.75 3.27 2.54 40 720 3.76 3.29 2.53 20 900 3.75 3.29 2.54 0 180 360540720900×10 250r 数据集大小 k=10 200 ◆MC-K-means 图4算法线性测试 -PKMeans MT Fig.4 Scalability test of different algorithms PKMcans MR 150 T◆K means 4.0f 100 3.5 50 3.0 哥 2.5 0 ,×10 2.0 k=5 180360540720900 1.5 ◆MC-K-means 数据集大小 1.0 -PKMeans_MT PKMcans MR 图6算法线性测试 0.5 Fig.6 Scalability test of different algorithms 0 →×10 180360540720900 4.0「 数据集大小 3.5 图5不同数据集大小下的加速率 3.0 Fig.5 Speedup rate of different data sizes 2.5 表1不同数据集大小下的加速率详情 2.0 1.5 k=10 Table 1 Speedup rate details of different data sizes -◆MC-K-means 1.0 -PKMeans MT Data Set MC-K- PKMeans PKMeans_ 0.5 PKMcans_MR Size/×103 means MT MR ×10 180 3.6 3.1 2.52 180 360540720900 360 3.62 3.11 2.51 数据集大小 540 3.64 3.14 2.53 图7不同数据集大小下的加速率 720 3.68 3.15 2.54 Fig.7 Speedup rate of different data size 900 3.68 3.15 2.53 从实验结果可以看出，除PKMeans_.MR算法因 从实验结果可以看出，随着数据集规模的不断 节点数不变，加速率保持相对稳定外，k取值的提 增长，各算法的运行时间均较为线性的增加。其中 高，有利于各并行化算法子任务的并行执行，减少同 PKMeans_.MR算法因为节点数并没有增加，所以加 步，故提高了相应算法的加速率。 速率基本保持不变。MC-K-means以及PKMeans_ 为了验证MC-K-means算法在执行过程中各并 T的加速率均随着数据集规模的增加呈现提高的 行化挖掘任务的负载是均衡的，在3-3240所在平 趋势，但都在接近各自极限后不再提高，保持一个相 台，修改聚类的过程为K-means读取数据集→MC 对稳定的加速率。这是因为随着数据集规模的增 K-means读取数据集→K-means聚类→MC-K-means 大，线程之间切换的资源消耗所占比重逐步降低，多 聚类。利用JDK7平台的jvisualvm20]工具对生成的 核优势逐渐显现。 180K数据集的聚类全过程进行了监控，并记录如图 验证不同数据集大小情况下，不同的聚类数目 8所示
小的人工数据集，针对每个数据集，分别执行 ＭＣ⁃Ｋ⁃ ｍｅａｎｓ、ＰＫＭｅａｎｓ＿ＭＲ、ＰＫＭｅａｎｓ＿ＭＴ、Ｋ⁃ｍｅａｎｓ 算法各 １０ 次，各算法每阶段各自共运行 ２０ 次，最后分别记 录下针对每个大小的数据集各算法聚类的平均时 间。 ｋ 的取值为 ５。 实验结果如图 ４ 所示，各算法加 速率如图 ５ 及表 １ 所示。 图 ４ 算法线性测试 Ｆｉｇ． ４ Ｓｃａｌａｂｉｌｉｔｙ ｔｅｓｔ ｏｆ ｄｉｆｆｅｒｅｎｔ ａｌｇｏｒｉｔｈｍｓ 图 ５ 不同数据集大小下的加速率 Ｆｉｇ． ５ Ｓｐｅｅｄｕｐ ｒａｔｅ ｏｆ ｄｉｆｆｅｒｅｎｔ ｄａｔａ ｓｉｚｅｓ 表 １ 不同数据集大小下的加速率详情 Ｔａｂｌｅ １ Ｓｐｅｅｄｕｐ ｒａｔｅ ｄｅｔａｉｌｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｄａｔａ ｓｉｚｅｓ Ｄａｔａ Ｓｅｔ Ｓｉｚｅ ／ ×１０ ３ ＭＣ⁃Ｋ⁃ ｍｅａｎｓ ＰＫＭｅａｎｓ＿ ＭＴ ＰＫＭｅａｎｓ＿ ＭＲ １８０ ３．６ ３．１ ２．５２ ３６０ ３．６２ ３．１１ ２．５１ ５４０ ３．６４ ３．１４ ２．５３ ７２０ ３．６８ ３．１５ ２．５４ ９００ ３．６８ ３．１５ ２．５３ 从实验结果可以看出，随着数据集规模的不断 增长，各算法的运行时间均较为线性的增加。 其中 ＰＫＭｅａｎｓ＿ＭＲ 算法因为节点数并没有增加，所以加 速率基本保持不变。 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 以及 ＰＫＭｅａｎｓ ＿ ＭＴ 的加速率均随着数据集规模的增加呈现提高的 趋势，但都在接近各自极限后不再提高，保持一个相 对稳定的加速率。 这是因为随着数据集规模的增 大，线程之间切换的资源消耗所占比重逐步降低，多 核优势逐渐显现。 验证不同数据集大小情况下，不同的聚类数目 ｋ 的取值对多核加速效率的影响。 设置 ｋ 为 １０，再 次变换数据集大小从 １８０Ｋ 至 ９００Ｋ，重复上述实验 过程，记录实验结果如图 ６ 所示，各算法加速率如图 ７ 及表 ２ 所示。 表 ２ 不同数据集大小下的加速率详情 Ｔａｂｌｅ ２ Ｓｐｅｅｄｕｐ ｒａｔｅ ｄｅｔａｉｌｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｄａｔａ ｓｉｚｅ Ｄａｔａ Ｓｅｔ Ｓｉｚｅ ／ ×１０ ３ ＭＣ⁃Ｋ⁃ ｍｅａｎｓ ＰＫＭｅａｎｓ＿ ＭＴ ＰＫＭｅａｎｓ＿ ＭＲ １８０ ３．７１ ３．１６ ２．５２ ３６０ ３．７３ ３．２３ ２．５３ ５４０ ３．７５ ３．２７ ２．５４ ７２０ ３．７６ ３．２９ ２．５３ ９００ ３．７５ ３．２９ ２．５４ 图 ６ 算法线性测试 Ｆｉｇ． ６ Ｓｃａｌａｂｉｌｉｔｙ ｔｅｓｔ ｏｆ ｄｉｆｆｅｒｅｎｔ ａｌｇｏｒｉｔｈｍｓ 图 ７ 不同数据集大小下的加速率 Ｆｉｇ． ７ Ｓｐｅｅｄｕｐ ｒａｔｅ ｏｆ ｄｉｆｆｅｒｅｎｔ ｄａｔａ ｓｉｚｅ 从实验结果可以看出，除 ＰＫＭｅａｎｓ＿ＭＲ 算法因 节点数不变，加速率保持相对稳定外，ｋ 取值的提 高，有利于各并行化算法子任务的并行执行，减少同 步，故提高了相应算法的加速率。 为了验证 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法在执行过程中各并 行化挖掘任务的负载是均衡的，在 ｉ３⁃３２４０ 所在平 台，修改聚类的过程为 Ｋ⁃ｍｅａｎｓ 读取数据集→ＭＣ⁃ Ｋ⁃ｍｅａｎｓ 读取数据集→Ｋ⁃ｍｅａｎｓ 聚类→ＭＣ⁃Ｋ⁃ｍｅａｎｓ 聚类。 利用 ＪＤＫ７ 平台的 ｊｖｉｓｕａｌｖｍ ［２０］工具对生成的 １８０Ｋ 数据集的聚类全过程进行了监控，并记录如图 ８ 所示。 ·６１２· 智 能 系 统 学 报 第 １０ 卷
第4期 申彦，等：CMP上基于数据集划分的K-means多核优化算法 .613. 从图8中的实验记录全过程来看，MC-K-means 实验结果再次验证了MC-K-means算法可以在 在读取数据集以及聚类阶段，线程池中各线程的负 CPU的各核心之间均衡的负载各挖掘任务，充分利 载是较为均衡的，没有出现长时间的空闲状态，算法 用现代CPU的多核计算能力，提高对大规模数据集 充分利用了CPU各核心的计算能力。 的聚类效率。 k=7 ,合色星数：有 MC-K-means ■PKMeans_MT PKMeans MR 4.0 3.71 3.69 3.5 3.24 3.12 3.0 2.5 2.52 2.5 2.0 1.5 1.0 0.5 图8 jvisual监控截图 0 Fig.8 Screenshot of jvisual Intel Xeon E5-2609 Intel i3-3240 操作平台 4.2真实数据集测试 使用UCI上的真实数据集Forest CoverType 图10加速率对比 dataset对相关算法进行测试。该数据集共有581 Fig.10 Comparision of speedup rate 012条记录，每条记录有54个维度，聚类时簇的个 5 结束语 数设置为k=7。 该数据集较为庞大且聚类需多次迭代，挖掘耗 本文考虑到现阶段多核CPU的普及，针对经典 时较多。在Xeon E5-2609所在平台，K-means算法 的K-means算法进行了多核并行优化，提出了一种 完成聚类需要98.65s,MC-K-means需要26.59s, MC-K-means算法。该算法把K-means聚类任务按 PKMeans_.MT需要30.45s,PKMeans_.MR需耗时 数据集等分为多个相互独立的挖掘子任务，并动态 39.15s;而在i3-3240所在平台，K-means算法完成 分配给多个线程并行执行，充分利用现代CPU的多 聚类需要103.42s,MC-K-means需要28.02s,PK 核计算能力。实验结果证明了该算法可以充分利用 Means_MT需要33.l5s,PKMeans_MR需耗时 现在的多核CPU,取得了较高的加速比，提高了聚 41.22s。从图9、10中可以看出，与人工生成数据集 类算法处理大规模数据集的能力。 的测试结果类似，并行优化后的各算法在Xeon E5- 虽然MC-K-means算法有着上述优势，但是当 2609平台获得了更高的加速比，且MC-K-menas算 前版本的算法仍然存在一些问题，有待进一步改进。 法依靠其更多执行步骤的并行化、更为直接的底层 例如算法可以进一步扩展到集群聚类的领域。这些 算法实现以及均衡的任务负载取得了最高的加 研究内容将在以后的研究过程中进一步补充完善。 速率。 参考文献： k=7 ☐MC-K-means [1]SUBRAMANIAM V.Programming concurrency on the JVM ■PKMeans MT mastering synchronization,STM,and actors[M].Beijing: PKMeans_MR China Machine Press,2013:1-27. ☐K-means [2]AARON B,TAMIR D E,RISHE N D,et al.Dynamic in- 120 103.42 cremental K-means clustering[C]//Proc of the 2014 Inter- 100 98.65 national Conference on Computational Science and Computa- 80 tional Intelligence,CSCI 2014.Los Alamitos,CA:IEEE 60 Computer Society,2014:308-313. 40 39.15 [3]SARMA T H,VISWANATH P.REDDY B E.Single pass ker- 2684 nel k-means clustering method[J].Sadhana-Academy Pro- 20 ceedings in Engineering Sciences,2013,38(3):407-419. [4]BRADLEY P,FAYYAD U,REINA C.Scaling clustering Intel Xeon E5-2609 Intel i3-3240 algorithms to large databases[R].Redmond:Microsoft Re- 操作平台 search Report,1998:9-15. 图9运行时间对比 [5]陈光平，王文鹏，黄俊.一种改进初始聚类中心选择的K-
从图 ８ 中的实验记录全过程来看，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 在读取数据集以及聚类阶段，线程池中各线程的负 载是较为均衡的，没有出现长时间的空闲状态，算法 充分利用了 ＣＰＵ 各核心的计算能力。 图 ８ ｊｖｉｓｕａｌ 监控截图 Ｆｉｇ． ８ Ｓｃｒｅｅｎｓｈｏｔ ｏｆ ｊｖｉｓｕａｌ ４．２ 真实数据集测试 使用 ＵＣＩ 上 的 真 实 数 据 集 Ｆｏｒｅｓｔ ＣｏｖｅｒＴｙｐｅ ｄａｔａｓｅｔ 对相关算法进行测试。 该数据集共有 ５８１ ０１２ 条记录，每条记录有 ５４ 个维度，聚类时簇的个 数设置为 ｋ ＝ ７。 该数据集较为庞大且聚类需多次迭代，挖掘耗 时较多。 在 Ｘｅｏｎ Ｅ５⁃２６０９ 所在平台，Ｋ⁃ｍｅａｎｓ 算法 完成聚类需要 ９８．６５ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 需要 ２６．５９ ｓ， ＰＫＭｅａｎｓ＿ＭＴ 需要 ３０． ４５ ｓ，ＰＫＭｅａｎｓ ＿ＭＲ 需耗时 ３９．１５ ｓ；而在 ｉ３⁃３２４０ 所在平台，Ｋ⁃ｍｅａｎｓ 算法完成 聚类需要 １０３． ４２ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 需要 ２８． ０２ ｓ，ＰＫ⁃ Ｍｅａｎｓ ＿ ＭＴ 需 要 ３３． １５ ｓ， ＰＫＭｅａｎｓ ＿ ＭＲ 需 耗 时 ４１．２２ ｓ。从图 ９、１０ 中可以看出，与人工生成数据集 的测试结果类似，并行优化后的各算法在 Ｘｅｏｎ Ｅ５⁃ ２６０９ 平台获得了更高的加速比，且 ＭＣ⁃Ｋ⁃ｍｅｎａｓ 算 法依靠其更多执行步骤的并行化、更为直接的底层 算法实现以及均衡的任务负载取得了最高的加 速率。 图 ９ 运行时间对比 Ｆｉｇ． ９ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｕｎ ｔｉｍｅ 实验结果再次验证了 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法可以在 ＣＰＵ 的各核心之间均衡的负载各挖掘任务，充分利 用现代 ＣＰＵ 的多核计算能力，提高对大规模数据集 的聚类效率。 图 １０ 加速率对比 Ｆｉｇ． １０ Ｃｏｍｐａｒｉｓｉｏｎ ｏｆ ｓｐｅｅｄｕｐ ｒａｔｅ ５ 结束语 本文考虑到现阶段多核 ＣＰＵ 的普及，针对经典 的 Ｋ⁃ｍｅａｎｓ 算法进行了多核并行优化，提出了一种 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法。 该算法把 Ｋ⁃ｍｅａｎｓ 聚类任务按 数据集等分为多个相互独立的挖掘子任务，并动态 分配给多个线程并行执行，充分利用现代 ＣＰＵ 的多 核计算能力。 实验结果证明了该算法可以充分利用 现在的多核 ＣＰＵ，取得了较高的加速比，提高了聚 类算法处理大规模数据集的能力。 虽然 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法有着上述优势，但是当 前版本的算法仍然存在一些问题，有待进一步改进。 例如算法可以进一步扩展到集群聚类的领域。 这些 研究内容将在以后的研究过程中进一步补充完善。 参考文献： ［１］ ＳＵＢＲＡＭＡＮＩＡＭ Ｖ． Ｐｒｏｇｒａｍｍｉｎｇ ｃｏｎｃｕｒｒｅｎｃｙ ｏｎ ｔｈｅ ＪＶＭ ｍａｓｔｅｒｉｎｇ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ， ＳＴＭ， ａｎｄ ａｃｔｏｒｓ［Ｍ］． Ｂｅｉｊｉｎｇ： Ｃｈｉｎａ Ｍａｃｈｉｎｅ Ｐｒｅｓｓ，２０１３：１⁃２７． ［２］ＡＡＲＯＮ Ｂ， ＴＡＭＩＲ Ｄ Ｅ， ＲＩＳＨＥ Ｎ Ｄ， ｅｔ ａｌ． Ｄｙｎａｍｉｃ ｉｎ⁃ ｃｒｅｍｅｎｔａｌ Ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ ２０１４ Ｉｎｔｅｒ⁃ ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｓｃｉｅｎｃｅ ａｎｄ Ｃｏｍｐｕｔａ⁃ ｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ＣＳＣＩ ２０１４． Ｌｏｓ Ａｌａｍｉｔｏｓ， ＣＡ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２０１４： ３０８⁃３１３． ［３］ＳＡＲＭＡ Ｔ Ｈ， ＶＩＳＷＡＮＡＴＨ Ｐ， ＲＥＤＤＹ Ｂ Ｅ． Ｓｉｎｇｌｅ ｐａｓｓ ｋｅｒ⁃ ｎｅｌ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ［Ｊ］． Ｓａｄｈａｎａ ⁃ Ａｃａｄｅｍｙ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｃｉｅｎｃｅｓ， ２０１３， ３８（３）： ４０７⁃４１９． ［４］ ＢＲＡＤＬＥＹ Ｐ， ＦＡＹＹＡＤ Ｕ， ＲＥＩＮＡ Ｃ． Ｓｃａｌｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｔｏ ｌａｒｇｅ ｄａｔａｂａｓｅｓ［Ｒ］． Ｒｅｄｍｏｎｄ：Ｍｉｃｒｏｓｏｆｔ Ｒｅ⁃ ｓｅａｒｃｈ Ｒｅｐｏｒｔ，１９９８：９⁃１５． ［５］陈光平，王文鹏，黄俊． 一种改进初始聚类中心选择的 Ｋ⁃ 第 ４ 期 申彦，等：ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 ·６１３·
·614. 智能系统学报 第10卷 means算法[J].小型微型计算机系统，2012,33(6)： [13]王晓华.MapReduce2.0源码分析与编程实战[M].北 1320-1323. 京：人民邮电出版社，2014：1-55. CHEN Guangping,WANG Wenpeng,HUANG Jun.Im- [14]MARTHA,V,ZHAO Weizhong,XV Xiaowei.H-MapRe- proved initial clustering center selection method for k-means duce:A framework for workload balancing in MapReduce algorith[J].Journal of Chinese Computer Systems,2012, [C]//Proc of the International Conference on Advanced 33(6):1320-1323. Information Networking and Applications,AINA.Piscat- [6]MAHMUD M S,RAHMAN MM,AKHTAR M N.Improve- away,:EEE,2013:637-644. ment of k-means clustering algorithm with better initial cen- [15 ZHAO Weizhong,MA Huifang,HE Qing.Parallel k- troids based on weighted average[C]//Proc of the 7th In- means clustering based on mapreduce[C]//Proc of the ternational Conference on Electrical and Computer Engineer- 1st International Conference on Cloud Computing,Cloud- ing,ICECE 2012.Los Alamitos,CA:IEEE Computer Soci- Com 2009.Germany:Springer Verlag,2009:674-679. ey,2012:647-650. [16]FAHIM A M.Parallel implementation of k-means on multi- [7]PATIL R,JONDHALE K C.Edge based technique to esti- core processors[J].Computer Science and Telecommuni- mate number of clusters in k-means color image segmentation cations,2014,1(41):53-61. [C]//Proc of the 3rd IEEE International Conference on [17]ZALIK K R.An efficient k-means clustering algorithm[J]. Computer Science and Information Technology,ICCSIT 2010. Pattern Recognition Letters,2008,29(9):1385-1391. Piscataway,NJ:IEEE Computer Society,2010:117-121. [18 HERBERT S,DALE S.A comprehansive introduction [8 ]JING Liping,NG M K,HUANG zhexue.An entropy weigh- [M].Beijing:China Machine Press,2013 ting k-means algorithm for subspace clustering of high-di- [19]JAVIER F G.Java 7 concurrency cookbook M].Beijing: mensional sparse data[]IEEE Transactions on Knowledge Posts Telecom Press,2014. and Data Engineering,2007,19(8):1026-1041. [20]Monitoring and managing java se 6 platform applications [9]BISHNU P S,BHATTACHERJEE V.A dimension reduc- [EB/OL].[2005-12-18 ].http://java.sun.com/develop- tion technique for k-means clustering algorithm[C]//Proc er/technicalArticles/J2SE/monitoring. of the Ist International Conference on Recent Advances in 作者简介： Information Technology,RAIT-2012.Piscataway,NJ: 申彦，男，1982年生，讲师，博士，主 IEEE Computer Society,2012:531-535. 要研究方向为数据挖掘、智能信息系 [10]DOBBELIN R,SCHUTT T,REINEFELD A.An analysis 统。获2014年度中国商业联合会科学 of SMP memory allocators:mapreduce on large shared- 技术奖三等奖。发表学术论文11篇， memory systems[C]//Proc of the 41st International Con- 其中被EI检索5篇。 ference on Parallel Processing Workshops ICPPW), 2012.Piscataway,NJ:IEEE,2012:48-54. [11]DI F G,BLASA F,CAFIERO S,et al.Fault tolerant de- 朱玉全，男，1965年生，教授，博士 centralised k-means clustering for asynchronous large-scale 生导师，主要研究方向为数据挖掘、智 networks[J].Journal of Parallel and Distributed Compu- 能信息系统、信息系统集成。获2014 ting,2013,73(3):317-329. 年度中国商业联合会科学技术奖三等 [12]赵卫中，马慧芳，傅燕翔，等.基于云计算平台Hadoop的 奖，全国多媒体课件大赛一等奖和江苏 并行k-means聚类算法设计研究[J].计算机科学， 省优秀软件产品奖（金慧奖）各1项，省 2011,38(10):166-169. 部级科技进步奖4次，申请发明专利10项，其中授权发明专 ZHAO Weizhong,MA Huifang,FU Yanxiang,et al. 利3项，获批计算机软件著作权7部。发表学术论文70余 Reasearch on parallel k-means algorithm design based on 篇，10多篇被EI检索，出版编著2部。 hadoop platform [J].Computer Science,2011,38(10): 166-169. [责任编辑：陈峰]
ｍｅａｎｓ 算法［ Ｊ］． 小型微型计算机系统， ２０１２， ３３ （ ６）： １３２０⁃１３２３． ＣＨＥＮ Ｇｕａｎｇｐｉｎｇ， ＷＡＮＧ Ｗｅｎｐｅｎｇ， ＨＵＡＮＧ Ｊｕｎ． Ｉｍ⁃ ｐｒｏｖｅｄ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｅｒ ｓｅｌｅｃｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ， ２０１２， ３３（６）： １３２０⁃１３２３． ［６］ＭＡＨＭＵＤ Ｍ Ｓ， ＲＡＨＭＡＮ Ｍ Ｍ， ＡＫＨＴＡＲ Ｍ Ｎ． Ｉｍｐｒｏｖｅ⁃ ｍｅｎｔ ｏｆ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｂｅｔｔｅｒ ｉｎｉｔｉａｌ ｃｅｎ⁃ ｔｒｏｉｄｓ ｂａｓｅｄ ｏｎ ｗｅｉｇｈｔｅｄ ａｖｅｒａｇｅ［Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ ７ｔｈ Ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒ⁃ ｉｎｇ， ＩＣＥＣＥ ２０１２． Ｌｏｓ Ａｌａｍｉｔｏｓ， ＣＡ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉ⁃ ｅｔｙ， ２０１２： ６４７⁃６５０． ［７］ ＰＡＴＩＬ Ｒ， ＪＯＮＤＨＡＬＥ Ｋ Ｃ． Ｅｄｇｅ ｂａｓｅｄ ｔｅｃｈｎｉｑｕｅ ｔｏ ｅｓｔｉ⁃ ｍａｔｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ｉｎ ｋ⁃ｍｅａｎｓ ｃｏｌｏｒ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ［Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ ３ｒｄ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， ＩＣＣＳＩＴ ２０１０． Ｐｉｓｃａｔａｗａｙ， ＮＪ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２０１０： １１７⁃１２１． ［８］ＪＩＮＧ Ｌｉｐｉｎｇ， ＮＧ Ｍ Ｋ， ＨＵＡＮＧ ｚｈｅｘｕｅ． Ａｎ ｅｎｔｒｏｐｙ ｗｅｉｇｈ⁃ ｔｉｎｇ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ ｏｆ ｈｉｇｈ⁃ｄｉ⁃ ｍｅｎｓｉｏｎａｌ ｓｐａｒｓｅ ｄａｔａ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００７， １９（８）： １０２６⁃１０４１． ［９］ ＢＩＳＨＮＵ Ｐ Ｓ， ＢＨＡＴＴＡＣＨＥＲＪＥＥ Ｖ． Ａ ｄｉｍｅｎｓｉｏｎ ｒｅｄｕｃ⁃ ｔｉｏｎ ｔｅｃｈｎｉｑｕｅ ｆｏｒ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ １ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｅｃｅｎｔ Ａｄｖａｎｃｅｓ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， ＲＡＩＴ⁃２０１２． Ｐｉｓｃａｔａｗａｙ， ＮＪ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２０１２： ５３１⁃５３５． ［１０］ＤＯＢＢＥＬＩＮ Ｒ， ＳＣＨＵＴＴ Ｔ ， ＲＥＩＮＥＦＥＬＤ Ａ． Ａｎ ａｎａｌｙｓｉｓ ｏｆ ＳＭＰ ｍｅｍｏｒｙ ａｌｌｏｃａｔｏｒｓ： ｍａｐｒｅｄｕｃｅ ｏｎ ｌａｒｇｅ ｓｈａｒｅｄ⁃ ｍｅｍｏｒｙ ｓｙｓｔｅｍｓ［Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ ４１ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ ｏｎ Ｐａｒａｌｌｅｌ Ｐｒｏｃｅｓｓｉｎｇ Ｗｏｒｋｓｈｏｐｓ （ ＩＣＰＰＷ ）， ２０１２． Ｐｉｓｃａｔａｗａｙ， ＮＪ： ＩＥＥＥ， ２０１２： ４８⁃５４． ［１１］ＤＩ Ｆ Ｇ， ＢＬＡＳＡ Ｆ， ＣＡＦＩＥＲＯ Ｓ， ｅｔ ａｌ． Ｆａｕｌｔ ｔｏｌｅｒａｎｔ ｄｅ⁃ ｃｅｎｔｒａｌｉｓｅｄ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｆｏｒ ａｓｙｎｃｈｒｏｎｏｕｓ ｌａｒｇｅ⁃ｓｃａｌｅ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕ⁃ ｔｉｎｇ， ２０１３， ７３（３）： ３１７⁃３２９． ［１２］赵卫中，马慧芳，傅燕翔，等．基于云计算平台 Ｈａｄｏｏｐ 的 并行 ｋ⁃ｍｅａｎｓ 聚类算法设计研究 ［ Ｊ］． 计算机科学， ２０１１，３８（１０）： １６６⁃１６９． ＺＨＡＯ Ｗｅｉｚｈｏｎｇ， ＭＡ Ｈｕｉｆａｎｇ， ＦＵ Ｙａｎｘｉａｎｇ， ｅｔ ａｌ． Ｒｅａｓｅａｒｃｈ ｏｎ ｐａｒａｌｌｅｌ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎ ｂａｓｅｄ ｏｎ ｈａｄｏｏｐ ｐｌａｔｆｏｒｍ ［Ｊ］ ． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２０１１，３８（１０）： １６６⁃１６９． ［１３］王晓华． ＭａｐＲｅｄｕｃｅ ２．０ 源码分析与编程实战［Ｍ］．北 京：人民邮电出版社， ２０１４：１⁃５５． ［１４］ＭＡＲＴＨＡ， Ｖ， ＺＨＡＯ Ｗｅｉｚｈｏｎｇ， ＸＶ Ｘｉａｏｗｅｉ． Ｈ⁃ＭａｐＲｅ⁃ ｄｕｃｅ： Ａ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｗｏｒｋｌｏａｄ ｂａｌａｎｃｉｎｇ ｉｎ ＭａｐＲｅｄｕｃｅ ［Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｄｖａｎｃｅｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ＡＩＮＡ． Ｐｉｓｃａｔ⁃ ａｗａｙ， ＮＪ： ＩＥＥＥ， ２０１３： ６３７⁃６４４． ［１５］ ＺＨＡＯ Ｗｅｉｚｈｏｎｇ， ＭＡ Ｈｕｉｆａｎｇ， ＨＥ Ｑｉｎｇ． Ｐａｒａｌｌｅｌ ｋ⁃ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ ｍａｐｒｅｄｕｃｅ ［ Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ １ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｌｏｕｄ Ｃｏｍｐｕｔｉｎｇ， Ｃｌｏｕｄ⁃ Ｃｏｍ ２００９． Ｇｅｒｍａｎｙ： Ｓｐｒｉｎｇｅｒ Ｖｅｒｌａｇ， ２００９： ６７４⁃６７９． ［１６］ＦＡＨＩＭ Ａ Ｍ． Ｐａｒａｌｌｅｌ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｋ⁃ｍｅａｎｓ ｏｎ ｍｕｌｔｉ⁃ ｃｏｒｅ ｐｒｏｃｅｓｓｏｒｓ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉ⁃ ｃａｔｉｏｎｓ， ２０１４， １（４１）： ５３⁃６１． ［１７］ＺＡＬＩＫ Ｋ Ｒ． Ａｎ ｅｆｆｉｃｉｅｎｔ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｌｅｔｔｅｒｓ， ２００８， ２９（９）： １３８５⁃１３９１． ［ １８ ］ ＨＥＲＢＥＲＴ Ｓ， ＤＡＬＥ Ｓ． Ａ ｃｏｍｐｒｅｈａｎｓｉｖｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ［Ｍ］． Ｂｅｉｊｉｎｇ： Ｃｈｉｎａ Ｍａｃｈｉｎｅ Ｐｒｅｓｓ， ２０１３ ［１９］ＪＡＶＩＥＲ Ｆ Ｇ． Ｊａｖａ ７ ｃｏｎｃｕｒｒｅｎｃｙ ｃｏｏｋｂｏｏｋ［Ｍ］． Ｂｅｉｊｉｎｇ： Ｐｏｓｔｓ ＆ Ｔｅｌｅｃｏｍ Ｐｒｅｓｓ， ２０１４． ［２０］ Ｍｏｎｉｔｏｒｉｎｇ ａｎｄ ｍａｎａｇｉｎｇ ｊａｖａ ｓｅ ６ ｐｌａｔｆｏｒｍ ａｐｐｌｉｃａｔｉｏｎｓ ［ＥＢ／ ＯＬ］． ［ ２００５⁃１２⁃１８］． ｈｔｔｐ： ／ ／ ｊａｖａ．ｓｕｎ． ｃｏｍ／ ｄｅｖｅｌｏｐ⁃ ｅｒ／ ｔｅｃｈｎｉｃａｌＡｒｔｉｃｌｅｓ／ Ｊ２ＳＥ／ ｍｏｎｉｔｏｒｉｎｇ． 作者简介： 申彦，男，１９８２ 年生，讲师，博士，主 要研究方向为数据挖掘、智能信息系 统。 获 ２０１４ 年度中国商业联合会科学 技术奖三等奖。 发表学术论文 １１ 篇， 其中被 ＥＩ 检索 ５ 篇。 朱玉全，男，１９６５ 年生，教授，博士 生导师，主要研究方向为数据挖掘、智 能信息系统、信息系统集成。 获 ２０１４ 年度中国商业联合会科学技术奖三等 奖，全国多媒体课件大赛一等奖和江苏 省优秀软件产品奖（金慧奖）各 １ 项，省 部级科技进步奖 ４ 次，申请发明专利 １０ 项，其中授权发明专 利 ３ 项，获批计算机软件著作权 ７ 部。 发表学术论文 ７０ 余 篇，１０ 多篇被 ＥＩ 检索，出版编著 ２ 部。 ［责任编辑：陈峰］ ·６１４· 智 能 系 统 学 报 第 １０ 卷