【机器学习】CMP上基于数据集划分的K-means多核优化算法编辑部

第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算法在读取数据集、判断每

验，所以需要针对不同实验平台中不同类型的 ＣＰＵ 进行测试。 ＨＰ ＰＲＯ ３３８０ ＭＴ 平台采用的 ＣＰＵ 是 Ｉｎｔｅｌ ｉ３⁃３２４０＠ ３．４０ ＧＨｚ，核心类型为 Ｉｖｙ Ｂｒｉｄｇｅ，６４ 位 ＣＰＵ，双核，四线程，支持超线程技术，３ ＭＢ 三级 缓存，双通道。 ＨＰ ＰｒｏＬｉａｎｔ ＤＬ３８８ｐ Ｇｅｎ８ 平台采用 的 ＣＰＵ 是 Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５⁃２６０９＠ ２．４０ ＧＨｚ，核心类型 为 Ｓａｎｄｙ Ｂｒｉｄｇｅ，６４ 位 ＣＰＵ，四核，四线程，１０ ＭＢ 三 级缓存，四通道。 对比算法为文献［１５］ 描述的基于 ＭａｐＲｅｄｕｃｅ 的并行 Ｋ⁃ｍｅａｎｓ 算法（ＰＫＭｅａｎｓ＿ＭＲ）以及文献［１６］ 描述的 ＰＫＭｅａｎｓ＿ＭＴ 算法。 在实验中根据上述文 献描述的算法思想分别实现了各算法进行对比实 验。 因为相同初始化条件下各算法最终聚类的结果 是一样的，所以实验主要对比分析相关算法的执行 时间以及加速率情况。 ４．１ 人工生成数据集测试 人工生成数据集由数据生成程序根据 Ｋ 个高 斯分布随机产生，每个高斯分布设置一个随机权重 来确定是否产生数据。 每一个高斯分布的中心是随 机产生的，区间为［－５，５］。 数据点每个维度值的产 生区间为［０．７，１．５］。 产生的人工数据集包含 １００ 维，１８０ ０００ 个数据点，数据集使用二进制 ｂｉｎ 文件 保存。 本次实验因为数据集以及聚类测试算法是在 同一台计算机上的，所以读取数据集时的阻塞系数 ｂｌｏｃｋＣｏｅｆｆｉｃｉｅｎｔ 设置为 ０。 聚类簇数量设置为 ｋ ＝ ５。 整个实验随机产生 ５ 个不同的人工生成数据 集，针对每个数据集，分别执行 ＭＣ⁃Ｋ⁃ｍｅａｎｓ、 ＰＫ⁃ Ｍｅａｎｓ＿ＭＲ、ＰＫＭｅａｎｓ＿ＭＴ 以及 Ｋ⁃ｍｅａｎｓ 算法各 １０ 次，各自共运行 ５０ 次，最后以聚类时间的平均值作 为算法聚类效率的评价。 实验结果如图 ２、３ 所示。 该数据集较为规整，算法运行收敛较快。 从实 验结果可以看出：针对服务器领域的 Ｘｅｏｎ Ｅ５⁃２６０９， 虽然主频较低，但依靠较大的 Ｌ３ 缓存以及四通道 的内存控制器，使得各算法取得了较高的执行效率。 Ｋ⁃ｍｅａｎｓ 算法在该平台环境下执行消耗了 ２５．２８ ｓ， ＰＫＭｅａｎｓ＿ＭＲ 消耗了 １０．０１ ｓ，ＰＫＭｅａｎｓ＿ＭＴ 消耗了 ８．１５ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 则需要 ７．０２ ｓ。 而在 ｉ３⁃３２４０ 所 在平台环境下，Ｋ⁃ｍｅａｎｓ 算法消耗了 ２８． ２４ ｓ，ＰＫ⁃ Ｍｅａｎｓ＿ＭＲ 消耗了 １１． ４７ ｓ， ＰＫＭｅａｎｓ ＿ＭＴ 消耗了 ９．３５ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 在该平台则需要 ９．０２ ｓ。 从并 行化改造后各算法的执行结果来看，在 Ｘｅｏｎ Ｅ５⁃ ２６０９ 所在平台，算法获得了更高的加速比。 这主要 是由于 Ｘｅｏｎ Ｅ５⁃２６０９ 是四核四线程的，拥有真实的 四核心，可以更好地并行完成各并行化算法划分的 多任务聚类工作。 而 ｉ３⁃３２４０ 是双核心的，依靠超 线程技术实现的四线程并行，但是 ＣＰＵ 的双物理核 心需要频繁的进行线程上下文的切换，消耗了一部 分的运行时间，获得了较低的加速比。 其中，ＭＣ⁃Ｋｍｅａｎｓ 算法在读取数据集、判断每 个数据点的所属类别、计算簇中心以及计算准则函 数 Ｅ 这 ４ 个阶段均进行了并行化改进。 且在这 ４ 个 阶段中，每个数据点的任务量是相当的，因此 ＭＣ⁃Ｋ⁃ ｍｅａｎｓ 算法所采取的等分数据集的方法可以取得较 好的负载均衡性，算法取得了对比算法中最高的加 速率。 ＰＫＭｅａｎｓ＿ＭＴ 算法取得了较低的加速率。 分析 算法可知，该算法仅在读取数据集以及迭代计算每 个数据点的归属时利用 ｐａｒｆｏｒ 函数进行了并行化。 对新分类中心点的计算及准则函数的计算均没有并 行化，且算法需要依托 ＭＡＴＬＡＢ 平台，故取得了较 低的加速率。 ＰＫＭｅａｎｓ＿ＭＲ 算法在对比算法中取得了最低的 加速率。 分析算法可知，ＰＫＭｅａｎｓ＿ＭＲ 算法改进原 Ｋ⁃ｍｅａｎｓ 算法，使其以 ＭａｐＲｅｄｕｃｅ 方式运行，节点之 间在迭代时需要多次通信、多次同步，且算法需适应 ＭａｐＲｅｄｕｃｅ 固有模式，降低了算法的运行效率，因此 取得了最低的加速率。 但对比原 Ｋ⁃ｍｅａｎｓ 算法仍提 高了一倍多的运行效率。 可以看出，对 Ｋ⁃ｍｅａｎｓ 进行并行化改进，适应了 多核 ＣＰＵ 的发展趋势，可以极大程度提高算法的运 行效率，满足处理大规模数据集的需要。 图 ２ 运行时间对比 Ｆｉｇ． ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｕｎ ｔｉｍｅ 图 ３ 加速率对比 Ｆｉｇ． ３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｓｐｅｅｄｕｐ ｒａｔｅ 逐步增大生成数据集的规模，生成的人工数据 集为 １００ 维，分别包含 １８０ ０００ 个数据点，３６０ ０００ 个数据点，５４０ ０００ 个数据点，７２０ ０００ 个数据点， ９００ ０００个数据点。 在 Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５⁃２６０９ 平台测试 每个算法的加速率。 实验每次随机产生 ２ 个相同大 第 ４ 期 申彦，等：ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 ·６１１·