第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-从图 ８ 中的实验记录全过程来看，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 在读取数据集以及聚类阶段，线程池中各线程的负 载是较为均衡的，没有出现长时间的空闲状态，算法 充分利用了 ＣＰＵ 各核心的计算能力。 图 ８ ｊｖｉｓｕａｌ 监控截图 Ｆｉｇ． ８ Ｓｃｒｅｅｎｓｈｏｔ ｏｆ ｊｖｉｓｕａｌ ４．２ 真实数据集测试 使用 ＵＣＩ 上 的 真 实 数 据 集 Ｆｏｒｅｓｔ ＣｏｖｅｒＴｙｐｅ ｄａｔａｓｅｔ 对相关算法进行测试。 该数据集共有 ５８１ ０１２ 条记录，每条记录有 ５４ 个维度，聚类时簇的个 数设置为 ｋ ＝ ７。 该数据集较为庞大且聚类需多次迭代，挖掘耗 时较多。 在 Ｘｅｏｎ Ｅ５⁃２６０９ 所在平台，Ｋ⁃ｍｅａｎｓ 算法 完成聚类需要 ９８．６５ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 需要 ２６．５９ ｓ， ＰＫＭｅａｎｓ＿ＭＴ 需要 ３０． ４５ ｓ，ＰＫＭｅａｎｓ ＿ＭＲ 需耗时 ３９．１５ ｓ；而在 ｉ３⁃３２４０ 所在平台，Ｋ⁃ｍｅａｎｓ 算法完成 聚类需要 １０３． ４２ ｓ，ＭＣ⁃Ｋ⁃ｍｅａｎｓ 需要 ２８． ０２ ｓ，ＰＫ⁃ Ｍｅａｎｓ ＿ ＭＴ 需 要 ３３． １５ ｓ， ＰＫＭｅａｎｓ ＿ ＭＲ 需 耗 时 ４１．２２ ｓ。从图 ９、１０ 中可以看出，与人工生成数据集 的测试结果类似，并行优化后的各算法在 Ｘｅｏｎ Ｅ５⁃ ２６０９ 平台获得了更高的加速比，且 ＭＣ⁃Ｋ⁃ｍｅｎａｓ 算 法依靠其更多执行步骤的并行化、更为直接的底层 算法实现以及均衡的任务负载取得了最高的加 速率。 图 ９ 运行时间对比 Ｆｉｇ． ９ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｕｎ ｔｉｍｅ 实验结果再次验证了 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法可以在 ＣＰＵ 的各核心之间均衡的负载各挖掘任务，充分利 用现代 ＣＰＵ 的多核计算能力，提高对大规模数据集 的聚类效率。 图 １０ 加速率对比 Ｆｉｇ． １０ Ｃｏｍｐａｒｉｓｉｏｎ ｏｆ ｓｐｅｅｄｕｐ ｒａｔｅ ５ 结束语 本文考虑到现阶段多核 ＣＰＵ 的普及，针对经典 的 Ｋ⁃ｍｅａｎｓ 算法进行了多核并行优化，提出了一种 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法。 该算法把 Ｋ⁃ｍｅａｎｓ 聚类任务按 数据集等分为多个相互独立的挖掘子任务，并动态 分配给多个线程并行执行，充分利用现代 ＣＰＵ 的多 核计算能力。 实验结果证明了该算法可以充分利用 现在的多核 ＣＰＵ，取得了较高的加速比，提高了聚 类算法处理大规模数据集的能力。 虽然 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法有着上述优势，但是当 前版本的算法仍然存在一些问题，有待进一步改进。 例如算法可以进一步扩展到集群聚类的领域。 这些 研究内容将在以后的研究过程中进一步补充完善。 参考文献： ［１］ ＳＵＢＲＡＭＡＮＩＡＭ Ｖ． Ｐｒｏｇｒａｍｍｉｎｇ ｃｏｎｃｕｒｒｅｎｃｙ ｏｎ ｔｈｅ ＪＶＭ ｍａｓｔｅｒｉｎｇ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ， ＳＴＭ， ａｎｄ ａｃｔｏｒｓ［Ｍ］． Ｂｅｉｊｉｎｇ： Ｃｈｉｎａ Ｍａｃｈｉｎｅ Ｐｒｅｓｓ，２０１３：１⁃２７． ［２］ＡＡＲＯＮ Ｂ， ＴＡＭＩＲ Ｄ Ｅ， ＲＩＳＨＥ Ｎ Ｄ， ｅｔ ａｌ． Ｄｙｎａｍｉｃ ｉｎ⁃ ｃｒｅｍｅｎｔａｌ Ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ ｔｈｅ ２０１４ Ｉｎｔｅｒ⁃ ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｓｃｉｅｎｃｅ ａｎｄ Ｃｏｍｐｕｔａ⁃ ｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ＣＳＣＩ ２０１４． Ｌｏｓ Ａｌａｍｉｔｏｓ， ＣＡ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２０１４： ３０８⁃３１３． ［３］ＳＡＲＭＡ Ｔ Ｈ， ＶＩＳＷＡＮＡＴＨ Ｐ， ＲＥＤＤＹ Ｂ Ｅ． Ｓｉｎｇｌｅ ｐａｓｓ ｋｅｒ⁃ ｎｅｌ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ［Ｊ］． Ｓａｄｈａｎａ ⁃ Ａｃａｄｅｍｙ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｃｉｅｎｃｅｓ， ２０１３， ３８（３）： ４０７⁃４１９． ［４］ ＢＲＡＤＬＥＹ Ｐ， ＦＡＹＹＡＤ Ｕ， ＲＥＩＮＡ Ｃ． Ｓｃａｌｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｔｏ ｌａｒｇｅ ｄａｔａｂａｓｅｓ［Ｒ］． Ｒｅｄｍｏｎｄ：Ｍｉｃｒｏｓｏｆｔ Ｒｅ⁃ ｓｅａｒｃｈ Ｒｅｐｏｒｔ，１９９８：９⁃１５． ［５］陈光平，王文鹏，黄俊． 一种改进初始聚类中心选择的 Ｋ⁃ 第 ４ 期 申彦，等：ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 ·６１３·