第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的主频几乎每两年提高一倍，与第 １０ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．４ ２０１５ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４１１０３６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０６３０．１５５５．００３．ｈｔｍｌ ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 申彦１，２ ，朱玉全２ （１．江苏大学 信息管理与信息系统系，江苏 镇江 ２１２０１３；２．江苏大学 计算机科学与通信工程学院，江苏 镇江 ２１２０１３） 摘 要：虽然现在多核 ＣＰＵ 非常普及，但传统 Ｋ⁃ｍｅａｎｓ 聚类算法由于没有专门进行并行化设计，不能充分利用现代 ＣＰＵ 的多核计算能力，算法针对大规模数据集的聚类效率有待进一步提高。 因此，对 Ｋ⁃ｍｅａｎｓ 算法进行 ＣＭＰ 并行化 改进，提出了一种 Ｍｕｌｔｉ⁃ｃｏｒｅ Ｋ⁃ｍｅａｎｓ（ＭＣ⁃Ｋ⁃ｍｅａｎｓ）算法。 该算法对 Ｋ⁃ｍｅａｎｓ 的聚类任务进行了分解，设计了独立且 均衡的聚类子任务并分配给各线程并行执行，以此利用现代 ＣＰＵ 的多核计算能力。 实验结果表明，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 相 比 Ｋ⁃ｍｅａｎｓ 获得了较高的多核加速比，提高了针对大规模数据集的聚类能力。 关键词：Ｋ 均值算法；聚类算法；单片多核；大规模数据集；数据挖掘；无监督学习；大数据 中图分类号： ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０４⁃０６０７⁃０８ 中文引用格式：申彦，朱玉全． ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法［Ｊ］． 智能系统学报， ２０１５， １０（４）： ６０７⁃６１４． 英文引用格式：ＳＨＥＮ Ｙａｎ， ＺＨＵ Ｙｕｑｕａｎ． Ａｎ ｏｐｔｉｍｉｚｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ Ｋ⁃ｍｅａｎｓ ｂａｓｅｄ ｏｎ ｄａｔａ ｓｅｔ ｐａｒｔｉｔｉｏｎ ｏｎ ＣＭＰ ｓｙｓｔｅｍｓ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（４）： ６０７⁃６１４． Ａｎ ｏｐｔｉｍｉｚｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ Ｋ⁃ｍｅａｎｓ ｂａｓｅｄ ｏｎ ｄａｔａ ｓｅｔ ｐａｒｔｉｔｉｏｎ ｏｎ ＣＭＰ ｓｙｓｔｅｍｓ ＳＨＥＮ Ｙａｎ １，２ ， ＺＨＵ Ｙｕｑｕａｎ ２ （１． Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｍａｎａｇｅｍｅｎｔ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ， Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ， Ｚｈｅｎｊｉａｎｇ ２１２０１３， Ｃｈｉｎａ；２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ， Ｚｈｅｎｊｉａｎｇ ２１２０１３， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ Ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｎｏｔ ｄｅｓｉｇｎｅｄ ｔｏ ｆｏｃｕｓ ｏｎ ｐａｒａｌｌｅｌｉｚａｔｉｏｎ， ｗｈｉｃｈ ｃａｎ ｎｏｔ ｍａｋｅ ｕｓｅ ｏｆ ｔｈｅ ｍｕｌｔｉ⁃ｃｏｒｅ ｃｏｍｐｕｔｉｎｇ ｃａｐａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｍｏｄｅｒｎ ＣＰＵ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｔｒａ⁃ ｄｉｔｉｏｎａｌ Ｋ⁃ｍｅａｎｓ ｆｏｒ ｍａｓｓｉｖｅ ｄａｔａ ｓｅｔ ｓｈｏｕｌｄ ｂｅ ｆｕｒｔｈｅｒ ｉｍｐｒｏｖｅｄ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ａ ｎｏｖｅｌ ａｌｇｏｒｉｔｈｍ ｎａｍｅｄ Ｍｕｌｔｉ⁃ｃｏｒｅ Ｋ⁃ｍｅａｎｓ （ＭＣ⁃Ｋ⁃ｍｅａｎｓ） ａｆｔｅｒ ｒｅｄｅｓｉｇｎｉｎｇ ｔｈｅ ｏｒｉｇｉｎａｌ Ｋ⁃ｍｅａｎｓ ｔｈａｔ ｆｏｃｕｓｅｓ ｏｎ ｐａｒａｌｌｅｌｉｚａｔｉｏｎ ｉｎ ａ ｃｈｉｐ ｍｕｌｔｉ⁃ｐｒｏ⁃ ｃｅｓｓｏｒ ＣＭＰ ｅｎｖｉｒｏｎｍｅｎｔ ｉｓ ｐｒｏｐｏｓｅｄ． Ｉｎ ｏｒｄｅｒ ｔｏ ｕｔｉｌｉｚｅ ｔｈｅ ｍｕｌｔｉ⁃ｃｏｒｅ ｃｏｍｐｕｔｉｎｇ ｃａｐａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｍｏｄｅｒｎ ＣＰＵ， ＭＣ⁃Ｋ⁃ｍｅａｎｓ ｐａｒｔｉｔｉｏｎｓ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｔａｓｋｓ ｉｎｔｏ ｓｏｍｅ ｉｎｄｅｐｅｎｄｅｎｔ ａｎｄ ｂａｌａｎｃｅｄ ｓｕｂｔａｓｋｓ ａｎｄ ｄｉｓｔｒｉｂｕｔｅｓ ｔｈｅｓｅ ｓｕｂ⁃ ｔａｓｋｓ ｔｏ ｔｈｅ ｔｈｒｅａｄｓ ｔｏ ｅｘｅｃｕｔｅ ｐａｒａｌｌｅｌ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗｅｄ ｔｈａｔ ｔｈｅ ＭＣ⁃Ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｒｅｃｅｉｖｅｄ ｔｈｅ ｒｅｌａｔｉｖｅｌｙ ｈｉｇｈｅｒ ｓｐｅｅｄｕｐ ｒａｔｅ ｃｏｍｐａｒｅｄ ｔｏ ｔｈｅ Ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ， ｗｈｉｃｈ ｉｍｐｒｏｖｅｓ ｔｈｅ ｈａｎｄｌｉｎｇ ｃａｐａｃｉｔｙ ｆｏｒ ｍａｓｓｉｖｅ ｄａｔａ ｓｅｔ． Ｋｅｙｗｏｒｄｓ：ｋ⁃ｍｅａｎｓ； ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ＣＭＰ； ｍａｓｓｉｖｅ ｄａｔａ ｓｅｔ； ｄａｔａ ｍｉｎｉｎｇ； ｕｎｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ； ｂｉｇ ｄａｔａ 收稿日期：２０１４⁃１１⁃２８． 网络出版日期：２０１５⁃０６⁃３０． 基金项目：国家自然科学基金资助项目（７１２７１１１７）；国家科技支撑计划 基金资助项目（２０１０ＢＡＩ８８Ｂ００）；江苏省自然科学基础研究计 划基金资助项目（ＢＫ２０１０３３１）；江苏省博士研究生创新计划 基金资助项目（ＣＸ１０Ｂ＿０１６Ｘ）；江苏省博士后科研资助计划 项目 （ １４０１０５６Ｃ ） 通信作者：申彦． Ｅ⁃ｍａｉｌ：１０４１８６１７９＠ ｑｑ．ｃｏｍ． 聚类是一项重要的研究工作，已经成为数据挖 掘、统计分析以及压缩算法等领域的研究重点。 聚 类研究领域有大量经典的算法涌现，如 Ｋ⁃ｍｅａｎｓ， ＰＡＭ，ＷａｖｅＣｌｕｓｔｅｒ 等。 其中 Ｋ⁃ｍｅａｎｓ 算法因其简 单、易于实现，获得了广泛的应用。 现代数据挖掘技 术的一个突出特点是需要处理大规模数据集。 经典 的 Ｋ⁃ｍｅａｎｓ 算法在处理大规模数据集时，无法一次 性把数据集全部装载入内存，需要多次扫描硬盘上 的数据，整个聚类过程相当耗时。 因其应用的广泛 性，很多研究人员选择对其进行优化，使其适应大规 模数据集聚类的应用需求。 值得注意的是，在过去 的几十年中，ＣＰＵ 的主频几乎每两年提高一倍，与 ．