第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使得生成的结果 则函数的计算阶段，这些阶段均可进行并行化改进，与 ＤＭＰ、ＳＭＰ 环境下的 Ｋ⁃ｍｅａｎｓ 聚类过程可以有效 的结合，作为 ＤＭＰ、ＳＭＰ 环境下 Ｋ⁃ｍｅａｎｓ 聚类算法 的有效补充。 也有研究人员开始着手研究 ＣＭＰ 环 境下 Ｋ⁃ｍｅｎａｓ 算法的并行化，但是相关研究尚处于 起步 阶 段， 算 法 实 现 仍 存 在 进 一 步 改 进 的 空 间［１５⁃１６］ 。 １．３ 多核处理器的出现 ２００５ 年，当主频接近 ４ ＧＨｚ 时，ＣＰＵ 的主要制 造厂商英特尔和 ＡＭＤ 公司发现单纯的主频提升已 经无法明显提升系统整体性能。 由于 ＣＰＵ 片内流 水线过长，使得单位频率效能低下，加上由于缓存的 增加和对漏电流控制的不利，造成 ＣＰＵ 功耗大幅度 增加。 随着功耗的增大，散热问题也越来越成为一 个无法逾越的障碍。 于是，出现了多核心 ＣＰＵ 的解 决方案。 其实较早以前已经有研究人员提出了利用单芯 片多核心处理器（ＣＭＰ）技术来代替复杂度越来越 高的单核心 ＣＰＵ。 ＩＢＭ、ＩＰ、ＳＵＮ 等企业也在服务器 领域投入了一定的多核 ＣＰＵ 进行商用。 然而由于 当时的服务器多核 ＣＰＵ 价格过于昂贵、应用面窄、 并没有真正发展起来。 ２００６ 年，多核 ＣＰＵ 进入了迅猛的发展时期，Ｉｎ⁃ ｔｅｌ 的 Ｃｏｒｅ， Ｘｅｏｎ 以及 ＡＭＤ 的 Ａｔｈｌｏｎ，Ｂａｒｃｅｌｏｎａ 等 受到了广泛的欢迎。 这些 ＣＰＵ 在性能得到极大提 升的同时，功耗反而得到了降低。 值得注意的是 ＯＳ 并不能自动的让某个应用程 序直接利用 ＣＰＵ 的多核，而是需要进行有关算法的 ＣＭＰ 并行化改进。 对于数据挖掘中的聚类、关联规 则挖掘等计算密集型、Ｉ／ Ｏ 密集型应用而言，对原有 算法进行并行化改进，提高算法的执行效率，尽快给 出挖掘结果成为了当务之急。 研究具有较强的现实 意义［１］ 。 ２ Ｋ⁃ｍｅａｎｓ 算法详细描述 Ｋ⁃ｍｅａｎｓ 算法，也被称为 Ｋ⁃平均或 Ｋ⁃均值算 法，是目前得到广泛应用的一种聚类算法［１７］ 。 其相 似度的计算根据一个簇中对象的平均值来进行。 Ｋ⁃ ｍｅａｎｓ 算法以 ｋ 为参数，把 ｎ 个数据点分为 ｋ 个簇， 使得簇内具有较高的相似度，而簇间的相似度较低。 算法首先随机地选择 ｋ 个对象，每个对象初始 地代表了一个簇的平均值或中心。 对剩余的每个对 象根据其与各个簇中心的距离，将它赋予最近的簇， 然后重新计算每个簇的平均值。 这个过程不断重 复，直到准则函数收敛。 准则函数定义为： Ｅ ＝ ∑ ｋ ｉ ＝ １ ∑ｘ∈Ｃｉ ｘ － ｘｉ ２ 。 这里的准则函数 Ｅ 是数据集中所 有数据点的平方误差总和，ｘ 是数据集空间中的点， ｘｉ 是簇 Ｃｉ的平均值。 准则函数 Ｅ 使得生成的结果 簇尽可能的紧凑和独立。 算法 １ Ｋ⁃ｍｅａｎｓ （Ｄａｔａｓｅｔ Ｄ， ＣｌｕｓｔｅｒＮｕｍｂｅｒ Ｋ） 输入：事务数据库 Ｄ，聚类簇的数量 Ｋ 输出：Ｋ 个聚类，使得平方误差准则 Ｅ 最小 １） ａｓｓｉｇｎ ｉｎｉｔｉａｌ ｖａｌｕｅ ｆｏｒ ｍｅａｎｓ； ／ ／ 任意选择 ｋ 个对象作为初始的簇中心 ２） ＲＥＰＥＡＴ； ３）ＦＯＲ ｊ ＝ １ ｔｏ ｎ ＤＯ ａｓｓｉｇｎ ｅａｃｈ ｘｊ ｔｏ ｔｈｅ ｃｌｏｓｅｓｔ ｃｌｕｓｔｅｒｓ ｍｅａｎ； ／ ／ 根据簇中对象的平均值将每个对象分配给最 近的簇 ４）ＦＯＲ ｉ ＝ １ ｔｏ ｋ ＤＯ ｘｉ ＝ １ Ｃｉ ∑ｘ∈Ｃｉ ｘ ； ／ ／ 更新簇的平均值，即计算每个簇中对象的平 均值 ５）Ｃｏｍｐｕｔｅ Ｅ ＝ ∑ ｋ ｉ ＝ １ ∑ｘ∈Ｃｉ ｘ － ｘｉ ２ ； ／ ／ 计算准则函数 Ｅ ６） Ｕｎｔｉｌ Ｅｎｅｗ － Ｅｌａｓｔ ＜ ε ， ε 为预先设定的一个 较小的值； ／ ／ 表示 Ｅ 不再产生明显的变化 Ｋ⁃ｍｅａｎｓ 是解决聚类问题的一种经典算法，该 算法实现起来较为简单且有非常好的可扩展性。 因 此，很多科研人员在研究针对大规模数据集的高效 聚类算法时，往往会以 Ｋ⁃ｍｅａｎｓ 算法作为首选进行 改进和优化。 分析 Ｋ⁃ｍｅａｎｓ 算法的时间复杂度，其运行时间 主要消耗在：１）数据集读取所产生的 Ｉ／ Ｏ；２）判断每 一个数据点（数据记录）的所属类别；３）计算每一个 类别（簇）的中心；４）计算准则函数 Ｅ。 而这 ４ 个阶 段均可以很好地并行化，以此利用现代 ＣＰＵ 的多核 特性，最大化的发挥 ＣＰＵ 的性能，提高聚类效率。 为此，本文提出了一种 Ｍｕｌｔｉ⁃ｃｏｒｅ Ｋ⁃ｍｅａｎｓ 算法 （ＭＣ⁃Ｋ⁃ｍｅａｎｓ），该算法对上述 ４ 个过程分别进行并 行化，充分利用 ＣＰＵ 的多核特性，进一步提高 Ｋ⁃ ｍｅａｎｓ 算法的聚类效率。 新算法可作为 ＳＭＰ、ＤＭＰ 分布式环境下聚类算法以及增量 ＯｎｅＳｃａｎ 聚类算法 的有效补充，提高单节点的聚类效率，从而提高整体 的聚类效率。 ３ ＣＭＰ 上基于数据集划分的大规模 数据集 Ｋ⁃ｍｅａｎｓ 多核优化算法 ３．１ ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法详细描述 在 ＣＭＰ 环境下对 Ｋ⁃ｍｅａｎｓ 聚类算法进行改进 以适应大规模数据集，关键是要改进原有算法的串 行执行部分为并行执行。 分析 Ｋ⁃ｍｅａｎｓ 算法可以发 现，在较为消耗资源的数据集读取阶段、数据点所属 类别判断阶段、每个新簇的簇中心计算阶段以及准 则函数的计算阶段，这些阶段均可进行并行化改进， 第 ４ 期 申彦，等：ＣＭＰ 上基于数据集划分的 Ｋ⁃ｍｅａｎｓ 多核优化算法 ·６０９·