·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多核加速的有关实且由于其所需计算的性质，都可以较好的做到多核 之间的负载均衡。 改进后的 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法详细描述如下。 其 中关键步骤如图 １ 所示，为了方便描述，图中以 ２ 线 程为例进行说明，可推广到 ｎ 线程的情形。 算法２ ＭＣ⁃Ｋ⁃ｍｅａｎｓ （Ｄａｔａｓｅｔ Ｄ， ＣｌｕｓｔｅｒＮｕｍｂｅｒ Ｋ） 输入：事务数据库 Ｄ，聚类的簇的数量 Ｋ 输出：Ｋ 个聚类，使得平方误差准则 Ｅ 最小 １） ｒａｎｄｏｍ ａｓｓｉｇｎ ｉｎｉｔｉａｌ ｖａｌｕｅ ｆｏｒ ｍｅａｎｓ； ／ ／ 任意选择 ｋ 个对象作为初始的簇中心 ２）ｔｈｒｅａｄ ＿ｃｏｕｎｔ ＝ Ｒｕｎｔｉｍｅ． ｇｅｔＲｕｎＴｉｍｅ （ ）． ａｖａｉｌ⁃ ａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ／ （１－ｂｌｏｃｋＣｏｅｆｆｉｃｉｅｎｔ）；０＜ ＝ ｂｌｏｃｋＣｏｅｆ⁃ ｆｉｃｉｅｎｔ＜１； ／ ／ 计算线程数 ３ ） ｅｘｅｃｕｔｅＳｅｒｖｉｃｅ ｓｅｒｖｉｃｅ ＝ Ｅｘｃｕｔｅ． ｎｅｗ⁃ ＦｉｘｅｄＴｈｒｅａｄＰｏｏｌ（ｔｈｒｅａｄ＿ｃｏｕｎｔ）； ／ ／ 创建线程池 ４） ｄｉｖｉｄｅ ｔｈｅ ｄａｔａ ｓｅｔ ｉｎｔｏ ｎ ｐａｒｔｓ ｅｑｕａｌｌｙ ａｎｄ ｃｒｅ⁃ ａｔｅ ｎ ｔａｓｋｓ ｔｏ ｒｅａｄ ｅｖｅｒｙ ｄａｔａ ｓｅｔ， ｗｈｅｒｅ ｎ ＝ ｔｈｒｅａｄ＿ ｃｏｕｎｔ； ／ ／ 装载数据 ５）ｔｈｒｅａｄ ＿ｃｏｕｎｔ ＝ Ｒｕｎｔｉｍｅ． ｇｅｔＲｕｎＴｉｍｅ （ ）． ａｖａｉｌ⁃ ａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ； ６ ） ｔｈｒｅａｄＰｏｏｌ ＝ Ｅｘｃｕｔｅ． ｎｅｗＦｉｘｅｄＴｈｒｅａｄＰｏｏｌ （ｔｈｒｅａｄ＿ｃｏｕｎｔ）； ／ ／ 创建线程池，计算准则函数 Ｅ ７） ｄｉｖｉｄｅ ｔｈｅ ｄａｔａ ｓｅｔ ｉｎｔｏ ｎ ｐａｒｔｓ ｅｑｕａｌｌｙ ａｎｄ ｃｒｅ⁃ ａｔｅ ｎ ｔａｓｋｓ ｔｏ ｃｏｍｐｕｔｅ ｔｈｅ ｃａｔｅｇｏｒｙ， ｗｈｅｒｅ ｎ ＝ ｔｈｒｅａｄ＿ ｃｏｕｎｔ； ８） ｒｅｐｅａｔ ９） ｆｏｒ ｅｖｅｒｙ ｄａｔａ＿ｓｅｔｊ １０） ｌｅｔ ｏｎｅ ｔａｓｋｊ ｔｏ ａｓｓｉｇｎ ｅａｃｈ ｄａｔａ ｐｏｉｎｔ ｏｆ ｔｈｅ ｄａｔａ＿ｓｅｔ ｊ ｔｏ ｔｈｅ ｃｌｏｓｅｓｔ ｃｌｕｓｔｅｒｓ ｃｅｎｔｅｒ ａｎｄ ｒｅｃｏｒｄ ｔｈｅ ｃａｔｅｇｏｒｙ； １１）ｕｎｔｉｌ ｅｖｅｒｙ ｄａｔａ＿ｓｅｔ ｊ ｉｓ ｆｉｎｉｓｈｅｄ； １２）ｆｏｒ ｅｖｅｒｙ ｅｑｕａｌｌｙ ｄａｔａ＿ｓｅｔ ｊ ／ ／ 计算每个簇的簇 中心； １３）ｌｅｔ ｏｎｅ ｔａｓｋｊ ｔｏ ｃｏｍｐｕｔｅ ｔｈｅ ｓｕｍｉｊ ａｎｄ ｎｕｍｉｊ ｏｆ ｄａｔａ＿ｓｅｔ ｊｐａｒｔｌｙ， ｊ ＝ １，２，…ｎ， ｉ ＝ １，２，…ｋ ； １４）ｕｎｔｉｌ ｅｖｅｒｙ ｅｑｕａｌｌｙ ｄａｔａ＿ｓｅｔ ｊ ｉｓ ｆｉｎｉｓｈｅｄ； １５）ｊｏｉｎ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｅｖｅｒｙ ｔａｓｋｊ ｔｏ ｇｅｔ ｔｏｔａｌ＿ｓｕｍ ｉ ＝ （∑ ｊ ＝ ｎ ｊ ＝ １ ｓｕｍｉｊ） ， ｔｏｔａｌ＿ｎｕｍｉ ＝ （∑ ｊ ＝ ｎ ｊ ＝ １ ｎｕｍｉｊ） ， ｉ ＝１，２，…，ｋ； １６） ｃｌｕｓｔｅｒ ＿ ｃｅｎｔｅｒｉ ＝ ｔｏｔａｌ＿ｓｕｍｉ ／ ｔｏｔａｌ＿ｎｕｍｉ，ｉ ＝ １，２，…，ｋ； ／ ／ 每个线程均可访问中心值，以便再次划分数据 １７）ｆｏｒ ｅｖｅｒｙ ｅｑｕａｌｌｙ ｄａｔａ＿ｓｅｔ ｊ ／ ／ 计算每个簇部分 准则函数 １８）ｌｅｔ ｏｎｅ ｔａｓｋｊ ｔｏ ｃｏｍｐｕｔｅ ｔｈｅ Ｅｉｊ ｏｆ ｄａｔａ ＿ ｓｅｔ ｊ ｐａｒｔｌｙ， ｊ ＝ １，２，…，ｎ， ｉ ＝ １，２，…，ｋ； １９）ｕｎｔｉｌ ｅｖｅｒｙ ｅｑｕａｌｌｙ ｄａｔａ＿ｓｅｔ ｊ ｉｓ ｆｉｎｉｓｈｅｄ； ２０）ｊｏｉｎ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｅｖｅｒｙ ｔａｓｋｊ ｔｏ ｇｅｔ ｔｏｔａｌ＿Ｅｉ ＝ （∑ ｊ ＝ ｎ ｊ ＝ １ Ｅｉｊ） ， ｉ ＝ １，２，…，ｋ； ２１） Ｅ ＝ ∑ ｉ ＝ ｋ ｉ ＝ １ ｔｏｔａｌ＿Ｅｉ ； ２２）ｕｎｔｉｌ Ｅｎｅｗ － Ｅｌａｓｔ ＜ ε ， ε ｉｓ ａ ｐｒｅｓｅｔ ｖｅｒｙ ｓｍａｌｌ ｔｈｒｅｓｈｏｌｄ 在读入外存数据时，考虑到数据源可能存在于 网络数据库中，在读取时会有一定的延时，多开线程 可有效利用 ＣＰＵ 的多核，因此考虑设置 Ｒｕｎｔｉｍｅ．ｇｅ⁃ ｔＲｕｎＴｉｍｅ （ ）． ａｖａｉｌａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ／ （ １⁃ｂｌｏｃｋＣｏｅｆｆｉ⁃ ｃｉｅｎｔ）大小的线程池，其中 ｂｌｏｃｋＣｏｅｆｆｉｃｉｅｎｔ ＝ 数据记 录 Ｉ／ Ｏ 阻塞时间／ 数据记录处理时间，在运行时可根 据数据源的延时动态调整。 在装载数据之后，判断每一数据点的所属类别 时采 用 的 是 欧 几 里 得 距 离 的 平 方 ｄ （ｘ，ｙ） ２ ＝ ∑ ｎ ｉ ＝ １ ｘｉ － ｙｉ ２ [ ] 。 该计算对于每个数据点的计算 量均是相同的，等分数据即可做到负载平衡。 除此 之外，该过程是计算密集型的，多开线程对提高效率 无益，反而会因为 ＣＰＵ 频繁的线程切换而降低运行 效率。 因此开设线程个 数 与 ＣＰＵ 核 心 数 ａｖａｉｌ⁃ ａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ 相同的线程池；又因为距离计算任务 的计算量对每个数据点是一样的，所以 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法等分数据，创建 ａｖａｉｌａｂｋｌｅＰｒｏｃｅｓｓｏｒｓ 个任务进 行数据点类别判断的计算，并交由线程池调度执行。 计算每一个聚类簇的簇中心，仍然是一个计算 密集型的任务，因此在此阶段开设线程数与 ＣＰＵ 核 心数相同的线程池。 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法针对之前等 分的数据集，每个线程 ｊ 计算被分配的数据集归属 于每个分类 ｉ 的 ｓｕｍｉｊ 以及 ｎｕｍｉｊ ，并汇总 ｊ 个线程的 结果得到 ｔｏｔａｌ＿ｓｕｍｉｊ 以及 ｔｏｔａｌ＿ｎｕｍｉｊ ， 最终 得 到 ｃｌｕｓｔｅｒ＿ｃｅｎｔｅｒｉ 。 采用针对等分数据集的方法使得 簇中心计算的各任务相对均衡。 在准则函数 Ｅ 的 计算过程中也采用了同样的负载均衡的方法。 ＣＭＰ 系统是共享内存的，上述 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算 法仅在访问共享变量及每部分数据处理完毕时需要 进行同步，避免了数据集通过网络在节点之间传输 造成的时间消耗，算法具有较高的执行效率。 ４ 实验结果以及分析 为了验证算法的有效性，依据前述 ＭＣ⁃Ｋ⁃ｍｅａｎｓ 算法 的 主 要 思 想， 使 用 Ｊａｖａ 语 言 实 现 了 ＭＣ⁃Ｋ⁃ ｍｅａｎｓ 以 及 Ｋ⁃ｍｅａｎｓ 算 法［１８⁃１９］ 。 实 验 平 台 为 ＨＰ ＰＲＯ ３３８０ ＭＴ，Ｗｉｎｄｏｗ ＸＰ＿ＳＰ３，４ ＧＢ 内存，ｊｄｋ７ｕ５１ 以及 ＨＰ ＰｒｏＬｉａｎｔ ＤＬ３８８ｐ Ｇｅｎ８， ＲｅｄＨａｔ ９．０，３２ ＧＢ 内存，ｊｄｋ７ｕ５１。 因为是做 ＣＰＵ 多核加速的有关实 ·６１０· 智 能 系 统 学 报 第 １０ 卷