第 36 卷第 3 期 2018 年 5 月应用科学学报 JOURNAL OF APPLIED SCIENCES Electronics and Information Engineering Vol. 36 No. 3 May 2018 DOI: /j.issn

Size: px

Start display at page:

Download "第 36 卷第 3 期 2018 年 5 月应用科学学报 JOURNAL OF APPLIED SCIENCES Electronics and Information Engineering Vol. 36 No. 3 May 2018 DOI: /j.issn"

卖虎蒯
5 years ago
Views:

1 第 36 卷第 3 期 2018 年 5 月应用科学学报 JOURNAL OF APPLIED SCIENCES Electronics and Information Engineering Vol. 36 No. 3 May 2018 DOI: /j.issn 基于云计算平台 Hadoop 的 HKM 聚类算法设计研究张淑芬 1, 董岩岩 1, 陈学斌 1,2 1. 华北理工大学理学院, 河北唐山河北省数据科学与应用重点实验室, 河北唐山摘要 : 为有效解决传统 K-means 聚类算法在处理大规模数据集时面临的扩展性问题, 提出了一种 Hadoop K-means 聚类算法. 该算法首先根据样本密度剔除数据集中孤立点或者噪声点的影响, 再利用最大化最小距离思想选取 K 个初始中心, 使初始聚簇中心点最优化, 最后用 Hadoop 云计算平台的 MapReduce 编程模型实现算法的并行化. 实验结果表明, 该算法不仅在聚类结果上具有较高的准确率和稳定性, 而且能够很好地解决传统聚类算法在处理大规模数据时所面临的扩展性问题. 关键词 :K-means 算法 ; 样本密度 ; 最大化最小距离 ;Hadoop 平台 ; 并行化计算中图分类号 :TP391.1 文章编号 : (2016) HKM Clustering Algorithm Design and Research Based on Hadoop Platform ZHANG Shu-fen 1, DONG Yan-yan 1, Chen Xue-bin 1,2 1. College of Science, North China University of Science and Technology, Tangshan , Hebei Province, China 2. Hebei Key Laboratory of Data Science & Application, Tangshan , Hebei Province, China Abstract: In order to solve the problem of traditional K-means clustering algorithm in dealing with large-scale data set, a Hadoop K-means (HKM) clustering algorithm is proposed. Firstly, based on the of sample density, the algorithm excludes the effect of data set point or noise. Secondly the optimization of the initial cluster centers is carried out by selecting K initial centers guided by the thought of maximizing the minimum distance. In the end, the MapReduce programming model of Hadoop cloud computing platform is used to realize the parallelization of the algorithm. Experimental results show that the proposed algorithm not only has high accuracy and stability in clustering results, but also can solve the problems of scalability encountered by traditional clustering algorithms in dealing with large scale data. Keywords: K-means algorithm, sample density, maximum minimum distance, Hadoop platform, parallel computing 收稿日期 : ; 修订日期 : 作者简介 : 张淑芬, 教授, 研究方向 : 云计算大数据, hblgzhsf@qq.com

2 第 3 期张淑芬, 等 : 基于云计算平台 Hadoop 的 HKM 聚类算法设计研究 525 聚类分析是数据挖掘的一个重要分支, 是一种无指导性的机器学习方法. 该方法基于物以类聚原则, 将抽象的对象集合分为多个类簇, 使同一类簇中对象间的相似度尽可能的大, 而不同类簇中对象间的相似度尽可能的小 [1]. 常用的聚类分析算法一般包括基于划分层次密度网络和模型等 5 类 [2]. K-means 算法是基于划分类别中使用最广泛的聚类算法, 其优点是快速简单. 然而, 经典的 K-means 聚类算法存在以下 3 方面的问题 :1) 聚类结果易受孤立点或噪声点的影响. 2) 聚类结果依赖于初始点的选取. 3) 在处理大规模数据集时存在算法扩展性问题. 为了改进传统 K-means 算法存在的不足, 研究人员从不同角度提出了一系列改进方案. 文献 [3] 提出了一种基于密度的改进 K-means 算法, 该算法引入信息熵和加权距离, 从近邻密度出发, 去除孤立点对算法的影响, 同时确定初始聚类中心, 使聚类中心相对稳定. 文献 [4] 提出基于多子群粒子群伪均值 (PK-means) 聚类算法, 该算法不但可以防止空类簇的出现, 而且还具有非常好的全局收敛性和局部寻优能力, 且在孤立点问题的处理上具有很好的效果. 文献 [5] 根据数据对象的空间分布情况, 首先采用空间划分预聚类算法 (SDPCA) 对数据集实现预聚类划分, 然后采用基于邻近簇调整的优化聚类算法 (OCANC) 对预聚类成果进行优化处理, 最终获取聚类成果. 文献 [6] 针对 K-means 算法对随机选择的初始聚类中心敏感且聚类结果不稳定准确率不高的问题, 提出一种基于邻域数据距离加权的聚类中心鲁棒优化算法, 通过建立数据密度约束将聚类中心优化在数据密集区域, 有效克服 K-means 算法聚类结果稳定性差等问题. 文献 [7] 提出一种新的高效率的 K-means 最佳聚类数确定算法, 该算法通过样本数据分层得到聚类数搜索范围的上界, 并设计了一种聚类有效性指标来评价聚类后类内与类簇间的相似性程度, 从而在聚类数搜索范围内获得最佳聚类数. 文献 [8] 用拉格朗日乘数法提出了一种基于属性权重最优化的 K-means 聚类算法, 该算法在计算样本与质心的距离时为各属性赋予相应的权重以表示属性的重要程度, 并在每轮迭代中根据质心向量的变化自动计算最优的属性权重, 使所有样本与相应质心的距离和最小. 文献 [9] 提出了一种基于距离阈值及样本加权的 K-means 聚类算法, 该算法首先采用样本集的样本均值作为第一个初始族中心 ; 然后基于距离阈值的方法动态确定初始族中心及数目 ; 最后基于样本加权的方法降低离散点对聚类效果的影响, 使带权值的样本点参与整个聚类过程, 采用轮廓系数来衡量不同算法的聚类质量. 文献 [10] 提出了一种基于数据流的计算框架, 该框架建立在 MapReduce 之上, 将数据处理过程按照数据流图建模, 在该框架的基础上, 提出了一种高效的 K-means 算法, 采用基于多次采样的初始聚类中心选取方法来实现负载均衡及减少迭代次数. 针对传统 K-means 算法存在的问题, 本文从以下 3 个方面对其进行改进 :1) 以样本密度作为判定孤立点或者噪声点的衡量标准, 找出源数据集中的孤立点或者噪声点, 并将其剔除, 实现数据处理前的数据清洗过程. 2) 初始中心点的选取过程应用最大化最小距离思想, 使选取的初始中心点更具有代表性. 3) 算法实现方面, 基于 Hadoop 云计算平台, 采用 MapReduce 编程模型实现 K-means 聚类算法的并行化. 1 K-means 算法的基本思想经典 K-means 算法从源数据中随机选取 k 个数据对象作为聚类的 k 个初始中心点, 以数据对象到聚簇中心的距离作为标度, 将其划分到距离最小的类簇中, 并且采用该类簇中所有数据对象的均值坐标作为该类簇新的中心坐标, 重复执行上一步骤, 直到最小平方误差准则函数达到收敛 [11]. 其中准则函数为

3 526 应用科学学报第 36 卷 E = k d O i 2 (1) i=1 d D 式中,E 为源数据集中的数据样本到各聚簇中心距离之和. d 为数据集 D 中需要划分类簇的数据样本,O i 为类簇 i 的中心坐标. 经典 K-means 算法的具体步骤如下 : 步骤 1 从源数据集 D 中随机选取 k 个样本点作为初始的 k 个类簇中心点坐标, 分别记为 O 1, O 2, O 3,, O k. 步骤 2 对于源数据集 D 中每个数据对象 d, 分别计算出其到 k 个初始中心的距离 S(d, O i ), i = 1, 2,, k, 若满足 S(d, O i ) = min{s(d, O i ), i = 1, 2,, k, 则 d O i, 即将数据对象划分到距离最小的聚簇中. 步骤 3 调整聚簇的中心点坐标, 即将类簇中所有数据点的平均值作为类簇新的中心坐标点, 具体计算公式为 O i = 1 N N d i, i = 1, 2,, N (2) i=1 式中, 类簇 O i 中数据样本的数目为 N,d i 为类簇 O i 中的数据样本. 步骤 4 判断式 (1) 准则函数是否收敛, 如果收敛则算法结束 ; 否则重新执行步骤 2 3, 直到准则函数收敛为止. 2 K-means 算法优化 2.1 算法优化的思想聚类过程中, 将处于数据集低密度区域的数据对象称为孤立点或者噪声点 [12]. 通常为了避免噪声数据对聚类造成结果误差, 要对数据集进行数据清洗过程, 采用数据样本之间的欧氏距离作为判定孤立点或者噪声点的一个衡量标准 [13]. 因此, 首先需计算出数据集中各个样本间的欧氏距离, 然后删除数据集中的孤立点或者噪声点. 清洗后的数据都处于整个数据集的高密度区域范围之内, 能够较好地体现整个数据集中数据样本的分布情况, 从而消除了孤立点或者噪声点对于经典 K-means 算法聚类结果产生的误差, 提高了经典 K-means 聚类结果的精确度. 经典 K-means 算法在选取 k 个初始中心点时, 并未考查这 k 个中心点的有效性和代表性 [14]. 当这 k 个点恰好分别属于 k 个不同类簇时, 该算法能够很快地收敛, 并获得较优的聚类结果. 然而当这 k 个点中存在属于同一类簇的情况时, 则很容易将本属于同一类簇的数据强制性地划分到其他的类簇中, 可见经典 K-means 算法的聚类结果依赖于初始点的选取 [15]. 因此在以欧氏距离作为相似性度量的聚类算法中, 可以利用最大化最小距离思想对其进行优化, 即选取相互间距离最远的 k 个数据样本点比随机选取最初的 k 个样本点更具有代表性. 优化后的算法仍采用式 (1) 作为算法的准则函数, 该函数是一个严格的坐标下降过程. 算法的每一次迭代都会使准则函数逐步减小, 直至收敛. 2.2 定义相关参数 1) 样本密度 : 数据集 D 中的数据样本 d, 以 d 为球心, 以某一个正数 r 为半径的球形区域中所包含的样本点的数目, 称为样本密度, 记作 Dens(x) [16]. Dens(x) = {p Dist(d, p) < r, p D (3)

4 第 3 期张淑芬, 等 : 基于云计算平台 Hadoop 的 HKM 聚类算法设计研究 527 式中,Dist(d, p) 表示相邻数据对象的欧氏距离. 2) 孤立点 ( 噪声点 ): 数据集 D 中的数据样本 d, 计算 d 到其相邻点的距离的平均值 [17], 计算公式为 avg_dist = n i=1 Dist(d, x i ) n 1 (4) 将所有样本点的欧氏距离进行从大到小的排序, 当相邻的两个样本点之间的平均距离大于某一个阈值时, 则判别为孤立点并将其从源数据集 D 中删除. 2.3 优化后的算法流程输入 : 聚簇个数 k 和包含数据对象的源数据文件 ; 输出 : 使准则函数收敛的 k 个聚簇结果. 算法的具体步骤如下 : 步骤 1 分别计算出相邻两个数据样本间的欧氏距离 S(d i, d j ); 步骤 2 根据式 (4) 计算出每个数据样本到相邻点距离的平均值, 并将其中判定为孤立点的数据对象进行删除, 从而得到处于高密度全区域的数据样本集合 D; 步骤 3 从清洗后的数据集合 D 中随机选取一个对象 ( 如 x 1 ) 作为第 1 个聚簇中心 Z 1, 则有 Z 1 = x 1 ; 步骤 4 在数据集合 D 中找出距离 Z 1 最远的对象作为第 2 个聚簇中心 Z 2 ; 步骤 5 找出数据集合 D 中剩余的每个对象到已有聚簇中心最近的距离, 即对 D 中剩余的每一个对象 x i, 都分别计算到 2 个聚簇中心 Z 1 和 Z 2 的距离, 记为 d i1 和 d i2, 并令其中较小值为 min(d i1, d i2 ); 步骤 6 计算 min(d i1, d i2 ) 的最大值, 记为 max(min(d i1, d i2 )), 对应的对象记为 x j ; 步骤 7 若 max(min(d i1, d i2 )) > m Z 2 Z 1, 则取 x j 作为第 3 个聚簇中心, 其中 m 为算法中的检验参数, 一般情况下取 ( 1 2 m < 1); 步骤 8 再比较剩余的点, 重复步骤 4 6, 直至找到 k 个符合条件的聚簇中心 ; 步骤 9 读取通过上述方法确定的 k 个聚簇中心, 分别计算源数据集中每个样本到各聚簇中心的距离 ; 步骤 10 根据距离大小将每个样本分配到距离最近的聚簇中, 然后更新各聚簇的中心坐标, 即重新计算每个聚簇中所有样本坐标的平均值 ; 步骤 11 重复步骤 9 10, 直到准则函数收敛为止. 3 优化后算法的实现 3.1 Hadoop 平台介绍 Hadoop 是当前解决大规模数据问题最常用的平台, 它是由 Apache 软件基金会 (Apache software foundation, ASF) 提供的一个以 Hadoop 分布式文件系统 (Hadoop distributed file system, HDFS) 和 MapReduce 编程模型为核心的分布式计算框架 [18-19]. Hadoop 中分布式计算是以 MapReduce 编程模型实现的, 其基本思想是将整个数据文件按照一定的大小 (Hadoop2.x 默认值为 128 M) 分割成若干个 Block 块, 分别保存在 Hadoop 集群的各数据存储节点中 [20]. 在进行聚类算法计算时, 由负责整个集群资源调度的节点将整个计算任务按照数据 Block 块的个数分割成若干个 Map 子任务, 映射到集群的各计算节点上进行并行计算. Map 函数读取数据 Block 文件, 生成中间的键 / 值对, 即 <key, value> 结

5 528 应用科学学报第 36 卷果, 并将其输出写入到本地磁盘持久化存储. 完成所有 Map 阶段任务之后, 各计算节点启动 Reduce 任务读取 Map 阶段的输出结果, 经过 Reduce 阶段的归约处理输出最终的结果 [21-24], 其执行过程如图 1 所示. 3.2 HKM 算法的实现图 1 MapReduce 执行过程 Figure 1 Process of MapReduce 将 2.1 节提出的优化后 K-means 算法结合 Hadoop 平台 MapReduce 编程模型实现, 即 Hadoop K-means 算法, 简称 HKM 算法. HKM 算法的具体实现包含两个 MapReduce 过程 :1)MapReduce 任务进行数据清洗和确定 k 个初始点的坐标 ;2)MapReduce 任务将源数据集分割成 k 个类簇数据清洗和确定 k 个初始点第 1 个 MapReduce 任务用于进行数据清洗和确定 k 个初始点的坐标, 具体分为 Map 和 Reduce 两个阶段. Map 阶段流程 : 步骤 1 读取输入文件, 转化成 <key, value> 键值对的形式, 其中 key 为当前数据对象相对于输入数据文件起始点的偏移量,value 为当前数据对象各维度坐标所组成的字符串. 初始化一个 List 集合, 用于存储当前已确定的中心坐标. 步骤 2 从 value 中解析出当前数据对象各维度的值, 并计算出每个数据样本到相邻点距离的平均值, 并将其中判定为孤立点的数据对象进行删除. for i = 0 to N { distance 第 i 与第 i + 1 个中心点的距离 ; if distance > Dist{//Dist 为规定的距离阈值常量 i = 0; // 将确定的孤立点各维度坐标置为 0, 即从源数据集中删除掉步骤 3 找出数据样本点与已确定中心的最大距离. for i=0 to list1.size(){ distance sample 与第 i 个中心点的距离 ; if (distance < mindistance){ mindistance=distance;//mindistance 为数据对象与已知中心的最小距离 ;

6 第 3 期张淑芬, 等 : 基于云计算平台 Hadoop 的 HKM 聚类算法设计研究 529 步骤 4 数据结果也是以 <key1, value1> 键值对形式 :key1 为输入的键值,value1 为最小距离 mindistance 和该数据对象各维度坐标所构成的字符串. Reduce 阶段流程 : 步骤 1 读取 Map 阶段的输出结果. 步骤 2 找出最大化最小距离 max(min(distance)). While (Value-list.hasNext()){ 从 Value-list.next() 中解析出一个对象的各维度坐标 sample 和它与已知中心坐标的最小距离 mindistance; if (mindistance > maxdistance){ maxdistance=mindistance; // 寻找出最大化的最小距离, 即距离已知中心点欧氏距离最大的数据样本对象步骤 3 坐标. sample 当前对象的各维度坐标 ; 输出结果中 key2 为输入的键值,value2 为新确定的中心对象 sample 各维度的步骤 4 若当前已确定的中心坐标个数小于 k, 则继续执行以上的 MapReduce 任务 ; 大于 k, 则停止循环进入到下一个 MapReduce 任务聚合为 k 个类簇第 2 个 MapReduce 任务用于将源数据集聚合成 k 个类簇, 同样分为 Map 和 Reduce 两个阶段. Map 阶段流程 : 步骤 1 数据文件. 步骤 2 读取 k 个中心点的坐标保存到变量中, 并以 <key, value> 键值对的形式读取源确定每个数据对象与 k 个中心的最小距离 mindist: for i=0 to k-1 do { distance 数据对象 sample 与第 i 个中心点的距离 ; if (distance < mindist){ mindist= distance; index=i; //index 为 k 个中心的序列号步骤 3 输出结果中 key3 为数据中心的序列号,value3 为对应数据对象的各维度坐标. Reduce 阶段流程 : 步骤 1 读取 Map 阶段的输出结果. 步骤 2 从 value 中解析出 Map 结果中的数据对象数目及相应节点各维的坐标累加值 : While(value-list.hasNext()){ 从 value-list.next() 中解析出一个对象的各维坐标值, 将各维坐标值累加到数组相应的分量中 ; num+=1;

7 530 应用科学学报第 36 卷步骤 3 num. 算出各个聚簇的中心坐标, 即用各维度坐标的累加值除以聚簇中对象的总数步骤 4 输出结果中 key4 为输入的键值,value4 为重新计算得到的各个聚簇中心坐标构造成的字符串. 步骤 5 将 Reduce 产生的最新各个聚簇中心坐标, 重新带入 Map 函数, 进行第 2 次迭代计算, 直到 HKM 聚类算法的准则函数收敛为止. 4 数据实验与分析 4.1 实验环境与数据集本次实验在 7 个节点上配置 Hadoop 集群, 在编号为 01 和 02 的机器上配置 Name-Node 服务, 在编号为 03 的机器上配置 Resource -Manager 服务. 在剩余的 4 台机器上配置 Data- Node Node-Manager 服务, 作为 HDFS 的存储节点以及 MapReduce 的计算节点. 每台机器的配置情况如下 :CPU 型号为 Inter(R) Core(TM) i5-3470, 内存为 4GB,Hadoop 版本为 2.4.1,Linux 系统版本为 CentOS-6.6. 实验中所使用的源数据集是根据程序随机生成的数据. 为了测试 HKM 算法的高效性, 使用程序分别生成 4 个不同大小的数据集, 分别为 200MB 400MB 600MB 800MB. 4.2 实验结果及分析第 1 组实验, 为验证 HKM 聚类算法初始值选取的有效性, 选取 200MB 数据作为源数据集, 分别用经典 K-means 算法和文中提出的 HKM 算法对源数据集进行 5 次聚类测试. 实验结果如表 1 所示. 表 1 两种算法测试的聚类结果 Table 1 Results of two clustering algorithms 序号经典 K-means 算法 HKM 算法初始中心准确率 /% 初始中心准确率 /% 1 (106, 37) (57, 136) (128, 46) (57, 136) (34, 185) (57, 136) (167, 84) (57, 136) (62, 141) (57, 136) 均值实验结果表明, 经典的 K-means 算法运算结果不稳定, 在准确率上也没能超过改进后的算法,HKM 聚类算法在聚类结果的准确率和稳定上都具有相对的优势. 第 2 组实验, 为了测试 HKM 聚类算法的性能, 实验分别采用数据伸缩率 (sizeup) 加速比 (speedup) 和扩展率 (scaleup) 作为评价标准 [25]. 伸缩率测评方法是保持计算节点的个数不变, 不断地增加数据规模. 图 2 给出了不同数目计算节点的 Hadoop 平台下 HKM 算法的数据伸缩率性能.

8 第 3 期张淑芬, 等 : 基于云计算平台 Hadoop 的 HKM 聚类算法设计研究 531 图 2 HKM 算法伸缩率性能的测试结果 Figure 2 Test results of HKM algorithm sizeup performance 从实验结果可以看出, 随着数据规模不断增大, 伸缩率也逐渐增大, 表明 HKM 聚类算法处理大规模数据的效率越来越高, 充分说明基于 Hadoop 的 HKM 聚类算法能够较好地解决传统聚类算法在处理大规模数据时所面临的算法扩展性问题. 加速比是同一个任务在单处理器系统和并行处理器系统中运行消耗的时间的比率 [26], 用以衡量并行程序或者系统并行化的性能和效果. 加速比评价方法是保持数据规模不变, 不断地增加计算节点的数目. m 台计算节点的加速比为 speedup(m) = T 1 T m (5) 式中,T 1 为在 1 台计算节点上使用的时间,T 2 为在 m 台计算节点上使用的时间. 加速比评价实验采用 200 MB 400 MB 600 MB 800 MB 4 组不同规模的数据集作为实验数据, 计算节点从 1 逐渐增加到 6, 分别记录 HKM 聚类算法在不同节点大小的集群上产生聚类结果所需要的时间, 然后计算出 HKM 聚类算法的加速比, 结果如图 3 所示. 图 3 HKM 算法加速比性能的测试结果 Figure 3 Test results of HKM algorithm speedup performance 实验结果表明,HKM 聚类算法的加速比与计算节点数量保持一定的线性比例, 随着计算

9 532 应用科学学报第 36 卷节点不断增加, 算法的加速比性能也不断提高, 并且随着数据集规模增大, 算法的加速比性能也越来越好. 说明多节点的计算集群能够较好地缩短计算所需要的时间, 这是因为随着计算节点的增加, 可利用的计算资源也在增多, 使算法的运行时间相应地减少. 扩展率评测方法是在扩大数据的同时, 增加计算机的数目. m 台计算节点的扩展率计算方法为 scaleup(d s, m) = T 1 T m (6) 式中,d s 为数据的规模, 单位为 MB;m 为计算节点的数量 ;T 1 为 1MB 的数据在 1 台计算节点上运行的时间 ;T m 为 d s MB 的数据在 m 台计算节点上运行的时间. 扩展率评价实验采用 200 MB 400 MB 600 MB 800 MB 4 组不同规模的数据集作为实验数据, 在 1 6 个计算节点上测试 HKM 聚类算法, 分别记录产生聚类结果所需要的时间, 然后计算出 HKM 聚类算法的扩展率, 实验结果如图 4 所示. 图 4 HKM 算法扩展率性能的测试结果 Figure 4 Test results of HKM algorithm scaleup performance 实验结果表明,HKM 聚类算法的扩展率值随计算节点数目的增加而不断减小, 并且一直小于 1, 表示 HKM 聚类算法对数据集的大小有良好的稳定性和扩展性. 5 结语本文首先分析了经典 K-means 聚类算法存在的问题, 针对这些问题提出 HKM 聚类算法, 即应用样本密度法剔除数据集中孤立点或者噪声点, 根据最大化最小距离思想选取初始中心点, 并使用 Hadoop 集群进行实现. 最后结合多组实验数据表明, 所设计的 HKM 算法不仅能够很好地提高聚类结果的精度, 并且能有效地应用到大规模数据的数据挖掘和分析中. 参考文献 : [1] 张杰, 卓灵, 朱韵攸. 一种 K-means 聚类算法的改进与应用 [J]. 电子技术应用,2015,41(1): Zhang J, Zhou L, Zhu Y X. Improvement and application of K-means clustering algorithm [J]. Application of Electronic Technique, 2015, 41(1): (in Chinese) [2] 陈兴蜀, 吴小松, 王文贤. 基于特征关联度的 K-means 初始聚类中心优化算法 [J]. 四川大学学报 ( 工程科学版 ),2015, 47(1):

10 第 3 期张淑芬, 等 : 基于云计算平台 Hadoop 的 HKM 聚类算法设计研究 533 Chen X S, Wu X S, Wang W X. A K-means initial clustering center optimization algorithm based on feature relevance [J]. Journal of Sichuan University (Engineering Science Edition), 2015, 47(1): (in Chinese) [3] 罗军锋, 锁志海. 一种基于密度的 K-means 聚类算法 [J]. 微电子学与计算机,2014(10): Luo J F, Suo Z H. A clustering algorithm based on density for K-means [J]. Microelectronics and Computer Science, 2014(10): (in Chinese) [4] 沈艳, 余冬华, 王昊雷. 粒子群 K-means 聚类算法的改进 [J]. 计算机工程与应用,2014, 50(21): Shen Y, Yu D H, Wang H L. An improved K-means clustering algorithm for particle swarm optimization [J]. Computer Engineering and Applications, 2014, 50(21): (in Chinese) [5] 张洁玲, 白清源. 一种高效的 K-means 聚类改进算法 [J]. 福州大学学报 ( 自然科学版 ),2014, 42(4): Zhang J L, Bai Q Y. An efficient K-means clustering algorithm [J]. Journal of Fuzhou University (Natural Science Edition), 2014, 42(4): (in Chinese) [6] 罗倩. K-means 聚类中心的鲁棒优化算法 [J]. 计算机工程与设计,2015, 36(9): Luo Q. Robust Optimization algorithm for K-means clustering centers [J]. Computer Engineering and Design, 2015, 36(9): (in Chinese) [7] 王勇, 唐靖, 饶勤菲. 高效率的 K-means 最佳聚类数确定算法 [J]. 计算机应用,2014, 34(5): Wang Y, Tang J, Rao Q F. A K-means optimal clustering algorithm for high efficiency [J]. Computer Application, 2014, 34(5): (in Chinese) [8] 熊平, 顾霄. 基于属性权重最优化的 K-means 聚类算法 [J]. 微电子学与计算机,2014, 31(4): Xiong P, Gu X. K-means clustering algorithm based on attribute weight optimization [J]. Microelectronics and Computer Science, 2014, 31(4): (in Chinese) [9] 安计勇, 闫子骥, 翟靖轩. 基于距离阈值及样本加权的 K-means 聚类算法 [J]. 微电子学与计算机,2015(8): An J Y, Yan Z J, Zhai J X. K-means clustering algorithm based on distance threshold and sample weighting [J]. Microelectronics and Computer Science, 2015(8): (in Chinese) [10] 王飞, 秦小麟, 刘亮. 云环境下基于数据流的 K-means 聚类算法 [J]. 计算机科学,2015, 42(11): Wang F, Qin X L, Liu L. K-means clustering algorithm based on data flow in cloud environment [J]. Computer Science, 2015, 42(11): (in Chinese) [11] 朱烨行, 李艳玲, 崔梦天. 一种改进 K-means 算法的聚类算法 CARDBK [J]. 计算机科学,2015, 42(3): Zhu Y X, Li Y L, Cun M T. CARDBK clustering algorithm with improved K-means algorithm [J]. Computer Science, 2015, 42(3): (in Chinese) [12] 张玉芳, 毛嘉莉, 熊忠阳. 一种改进的 K-means 算法 [J]. 计算机应用,2003, 23(8): Zhang Y F, Mao J L, Xiong Z Y. An improved K-means algorithm [J]. Computer Application, 2003, 23(8): (in Chinese) [13] 邢长征, 谷浩. 基于平均密度优化初始聚类中心的 K-means 算法 [J]. 计算机工程与应用,2014, 50(20): Xing C Z, Gu H. A K-means algorithm for initial clustering center optimization based on average density [J]. Computer Engineering and Applications, 2014, 50(20): (in Chinese) [14] 杨志, 罗可. 一种改进的基于粒子群的聚类算法 [J]. 计算机应用研究,2014, 31(9): Yang Z, Luo K. An improved clustering algorithm based on particle swarm optimization [J]. Journal of Computer Applications, 2014, 31(9): (in Chinese) [15] 柳静, 郭红山. 云计算中 K-means 聚类中心优化求解方法 [J]. 科技通报,2015, 31(10): Liu J, Guo H S. Optimization method of K-means clustering center in cloud computing [J]. Bulletin of Science and Technology, 2015, 31(10): (in Chinese) [16] 周炜奔, 石跃祥. 基于密度的 K-means 聚类中心选取的优化算法 [J]. 计算机应用研究,2012, 29(5): Zhou W B, Shi Y X. An optimization algorithm of K-means clustering center selection based on density [J]. Computer application research, 2012, 29(5): (in Chinese)

11 534 应用科学学报第 36 卷 [17] 符保龙, 张爱科. 基于均值密度中心估计的 K-means 聚类文本挖掘方法 [J]. 重庆邮电大学学报 ( 自然科学版 ),2014, 26(1): Fu B L, Zhang A K. A K-means clustering text mining method based on mean density center estimation [J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2014, 26(1): (in Chinese) [18] Rao B T, Reddy L S. Survey on improved scheduling in Hadoop MapReduce in cloud environments [J]. Computer Science, 2012, 34(9): [19] Dittrich J, Quiane-Ruiz J A. Efficient big data processing in Hadoop MapReduce [J]. Proceedings of the Vldb Endowment, 2015, 5(12): [20] Lin X, Meng Z, Xu C. A practical performance model for Hadoop MapReduce [C]//IEEE International Conference on CLUSTER Computing Workshops. IEEE, 2015: [21] Han W, Zhang X, Chen Y. MapReduce based image classification approach [J]. Journal of Computer Applications, 2014, 34(6): [22] 周润物, 李智勇, 陈少淼. 面向大数据处理的并行优化抽样聚类 K-means 算法 [J]. 计算机应用,2016, 36(2): Zhou R W, Li Z Y, Chen S M. Parallel optimal sampling clustering K-means algorithm for large data [J]. Computer Application, 2016, 36(2): (in Chinese) [23] Rao B T, Reddy L S S. Survey on improved scheduling in Hadoop MapReduce in cloud environments[j]. Computer Science, 2015, 34(9): [24] 马汉达, 郝晓宇, 马仁庆. 基于 Hadoop 的并行 PSO-K-means 算法实现 Web 日志挖掘 [J]. 计算机科学,2015, 42(s1): Ma H D, Hao X Y, Ma R Q. Implementation of Web log mining based on Hadoop s parallel PSO-K-means algorithm [J]. Computer Science, 2015, 42(s1): (in Chinese) [25] 周婷, 张君瑛, 罗成. 基于 Hadoop 的 K-means 聚类算法的实现 [J]. 计算机技术与发展,2013, 23(7): Zhou T, Zhang J Y, Luo C. Implementation of K-means clustering algorithm based on Hadoop [J]. Computer Technology and Development, 2013, 23(7): (in Chinese) [26] 赵卫中, 马慧芳, 傅燕翔. 基于云计算平台 Hadoop 的并行 K-means 聚类算法设计研究 [J]. 计算机科学,2011, 38(10): Zhao W Z, Ma H F, Fu Y X. Research on parallel K-means clustering algorithm based on cloud computing platform Hadoop [J]. Computer Science, 2011, 38(10): (in Chinese) ( 编辑 : 管玉娟 )

<D2BDC1C6BDA1BFB5CDB6C8DAD7CAB8DFB7E5C2DBCCB3B2CEBBE1C3FBB5A52E786C7378>

<D2BDC1C6BDA1BFB5CDB6C8DAD7CAB8DFB7E5C2DBCCB3B2CEBBE1C3FBB5A52E786C7378> 参会人员名单 Last Name 姓名公司 Tel Fax Bai 柏煜康复之家 8610 8761 4189 8610 8761 4189 Bai 白威久禧道和股权投资管理 ( 天津 ) 有限公司 8610 6506 7108 8610 6506 7108 Bao 包景明通用技术集团投资管理有限公司 8610

第 36 卷第 3 期 2018 年 5 月 应用科学学报 JOURNAL OF APPLIED SCIENCES Electronics and Information Engineering Vol. 36 No. 3 May 2018 DOI: /j.issn

第 36 卷第 3 期 2018 年 5 月应用科学学报 JOURNAL OF APPLIED SCIENCES Electronics and Information Engineering Vol. 36 No. 3 May 2018 DOI: /j.issn