·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算法的聚类效率具有重要的现实意义，并且此相对应的内存频率却没有相对应的提高。 内存与 ＣＰＵ 之间处理数据的能力差距越来越大，极大地影 响了应用程序的性能。 同时，工程师们开始认识到， 仅仅提高单核芯片的频率会产生过多热量且无法带 来希望的性能改善。 于是，ＣＭＰ （ ｃｈｉｐ ｍｕｌｔｉ⁃ｐｒｏｃｅｓ⁃ ｓｏｒ）成为了先进处理器的发展趋势。 ＣＭＰ 可以在大 幅提高处理性能的同时降低 ＣＰＵ 主频，减少能源消 耗。 然而仅简单提供 ＣＭＰ 环境并不能直接带来应 用程序性能的提高，需要研发人员针对 ＣＭＰ 环境对 有关算法进行优化，才能使得应用程序更好的利用 ＣＰＵ 的多核计算能力，提高程序的运行效率［１］ 。 本文针对提高大规模数据集聚类效率的问题， 着重研究单机多核环境下（ＣＭＰ）Ｋ⁃ｍｅａｎｓ 算法的并 行化改进，提出了一种 Ｍｕｌｔｉ⁃ｃｏｒｅ Ｋ⁃ｍｅａｎｓ （ＭＣ⁃Ｋ⁃ ｍｅａｎｓ）算法。 该算法对原 Ｋ⁃ｍｅａｎｓ 算法的聚类任务 进行了分解，设计了相互独立且均衡的聚类子任务 交由各线程并行执行，能够充分利用现代 ＣＰＵ 的多 核计算能力，提高大规模数据集的聚类效率。 １ 研究背景 １．１ 确定性聚类的基本概念 金属橡胶隔振器在飞机液压管道上的应用如图 １ 所示，从图 １ 看出，金属橡胶放置在外围卡箍的凹 槽内，传统管道固定一般直接与外围卡箍接触或之 间有薄的橡胶垫作为隔振装 。 图 １ ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法示意 Ｆｉｇ． １ Ｉｌｌｕｓｔｒａｔｉｏｎ ｏｆ ＭＣ⁃Ｋ⁃ｍｅａｎｓ 定义 １ 确定性聚类的输入可以用一组有序对 （Ｘ， ｓ）或（Ｘ， ｄ）来表示，这里 Ｘ 表示一组样本，ｓ 和 ｄ 分别是度量样本间相似度或相异度（距离） 的标 准。 确定性聚类系统的输出是一个个分区，例如Ｃ ＝ ｛Ｃ１ ， Ｃ２ ，…， Ｃｋ｝，其中 Ｃｉ（ ｉ ＝ １，２…，Ｋ） 是 Ｘ 的子 集，且满足： Ｃ１ ∪ Ｃ２ ∪，… ， ∪ Ｃｋ ＝ Ｘ；Ｃｉ ∩ Ｃｊ ＝ ⌀， ｉ ¹ｊ 。 Ｃ 中的成员 Ｃ１ ， Ｃ２ ，…， Ｃｋ 叫做类或簇（Ｃｌｕｓ⁃ ｔｅｒ），每一个类或簇都是通过一些特征描述的，通常 有如下几种表示方式： １） 通过它们的中心或类的边界点表示空间的 一类点。 ２） 使用聚类树中的结点，图形化地表示一个类。 ３） 使用样本属性的逻辑表达式表示类。 １．２ 相关的研究工作 为了解决 Ｋ⁃ｍｅａｎｓ 算法对大规模数据集聚类效 率较低的问题，有研究者提出了只需要扫描一遍原 始数据集即产生聚类结果的算法。 这些算法只需读 入大规模数据集中的一部分进入主存或者分批读入 数据集进行聚类，扫描数据集一遍即完成聚类。 相 应的算法有 ｒａｎｄｏｍ⁃ｋｍｅａｎｓ， Ｄｙｎａｍｉｃ ｉｎｃｒｅｍｅｎｔａｌ Ｋ⁃ ｍｅａｎｓ ［２］ ， Ｓｉｎｇｌｅ ｐａｓｓ ｋｅｒｎｅｌ Ｋ⁃ｍｅａｎｓ ［３］ ， ｓｃａｌａｂｌｅ⁃ ｋｍｅａｎｓ ［４］ ，等。 其中，由 Ｍｉｃｒｏｓｏｆｔ Ｒｅｓｅａｒｃｈ 的 Ｒｅｄ⁃ ｍｏｎｄ 等提出的 ｓｃａｌａｂｌｅ⁃ｋｍｅａｎｓ 算法性能优越，受到 了广泛的重视，并被集成到 ＳＱＬ ＳＥＲＶＥＲ ２００８ 中。 类似研究的主要目的是优化 Ｋ⁃ｍｅａｎｓ 算法，减少数 据集的读取次数。 有研究者从优化 Ｋ⁃ｍｅａｎｓ 聚类初 始条件设置的角度，利用自适应技术、启发式算法以 及半监督技术等实现 Ｋ⁃ｍｅａｎｓ 初始聚类中心或者聚 类个数的优化选择，加速 Ｋ⁃ｍｅａｎｓ 聚类的收敛过程， 提高聚类的效率以及结果的质量［５⁃７］ 。 有研究人员 从减少大规模数据集数据维度的角度，降低聚类迭 代过 程 的 计 算 量， 提 高 Ｋ⁃ｍｅａｎｓ 聚 类 算 法 的 效 率［８⁃９］ 。 以上相关的研究工作切实提高了 Ｋ⁃ｍｅａｎｓ 聚类的效率，然而这些新算法并没有利用分布式环 境提高聚类的效率。 最近有研究人员进行了 ＳＭＰ、 ＤＭＰ 环境下的集群多处理器 Ｋ⁃ｍｅａｎｓ 聚类的研究 工作，提高了大规模数据集的聚类效率［１０⁃１１］ 。 直接 针对共享内存多处理器系统以及分布式内存多处理 器环境进行 Ｋ⁃ｍｅａｎｓ 的并行化，需要考虑复杂的数 据划分、节点容错等并行化的基本问题且需要消耗 大量的节点间同步以及数据网络传输的时间。 随着 类似 Ｇｏｏｇｌｅ ＭａｐＲｅｄｕｃｅ 以及 Ａｐａｃｈｅ 的 Ｈａｄｏｏｐ 的出 现和广泛使用，在这些编程模型的基础之上进行分 布式开发变得相对容易，分布式的基本问题可以依 靠基础编程模型来解决。 很多研究人员利用 Ｍａ⁃ ｐＲｅｄｕｃｅ 的算法模型，针对 Ｋ⁃ｍｅａｎｓ 聚类过程的并 行化进行了大量深入的研究工作，取得了很多重要 的研究成果，使得 Ｋ⁃ｍｅａｎｓ 算法可用于大规模数据 集聚类的应用场合。 然而这些算法更多考虑的是多 处理器分布式场景下的 Ｋ⁃ｍｅａｎｓ 并行化，较少考虑 到单机 ＣＰＵ 的多核利用。 除此之外，并不是所有的 聚类算法都适合以 ＭａｐＲｅｄｕｃｅ 的形式进行并行化 的，且为了适应 ＭａｐＲｅｄｕｃｅ 的编程架构，有时反而 会增加额外的计算量与通信量［１２⁃１４］ 。 现代 ＣＰＵ 技术的发展，使得单机的运行环境也 发生了极大的变化。 多核处理器的出现提高了 ＣＰＵ 的计算性能，降低了 ＣＰＵ 的功耗。 尽管如此， 传统的算法并不能直接从多核 ＣＰＵ 中获益，需要针 对多核 ＣＰＵ 的特点进行并行化改进与优化，才能充 分利用多核 ＣＰＵ 的计算能力。 因此，研究单机 ＣＭＰ 环境下 Ｋ⁃ｍｅａｎｓ 算法的并行化方法对提高单机 Ｋ⁃ ｍｅａｎｓ 算法的聚类效率具有重要的现实意义，并且 ·６０８· 智 能 系 统 学 报 第 １０ 卷