欢迎访问一起赢论文辅导网
机械论文
当前位置:首页 > 机械论文
加速大数据聚类K-means算法的改进
来源:一起赢论文网     日期:2015-11-04     浏览数:2666     【 字体:

加速大数据聚类K-means算法的改进韩 岩1,2,李 晓1(1.中国科学院新疆理化技术研究所,新疆乌鲁木齐830011;2.中国科学院大学计算机与控制学院,北京100049)摘 要:为有效处理大规模数据聚类的问题,提出一种先抽样再用最大最小距离进行K-means并行化聚类的方法。基于抽样的方法避免了聚类陷入局部解中,基于最大最小距离法使得初始聚类中心趋于最优化。大量实验结果表明,无论是在单机环境还是集群环境下,该方法受初始聚类中心的影响降低,提高了聚类的准确性,减少了聚类的迭代次数,降低了聚类的时间。关键词:K-均值算法;随机抽样;最大最小距离法;映射归约;并行化中图法分类号:TP311 文献标识号:A  文章编号:1000-7024 (2015)05-1317-04doi:10.16208/j.issn1000-7024.2015.05.039收稿日期:2014-05-08;修订日期:2014-07-09基金项目:中国科学院西部之光人才培养计划基金项目(RCPT201205)作者简介:韩岩(1988 ),男,河南商丘人,硕士,研究方向为数据挖掘、物联网、海量数据处理与分析;李晓(1957 ),男,新疆乌鲁木齐人,硕士,研究员,博士生导师,研究方向为多语种信息处理、信息系统研究与开发。E-mail:825358445@qq.comImproved accelerating large data K-means clustering algorithmHAN Yan1,2,LI Xiao1(1.Xinjiang Technical Institute of Physics and Chemistry,Chinese Academy of Sciences,Urumqi 830011,China;2.School of Computer and Control Engineering,University of Chinese Academy of Sciences,Beijing 100049,China)Abstract:To deal with large-scale data clustering problems,a speeding K-means parallel clustering method was presented whichrandomly sampled first and then used max-min distance means to carry out K-means parallel clustering.Sampling based methodavoids the problem of clustering in local solutions and max-min distance based method makes the initial clustering centers tend tobe optimum.Results of a large number of experiments show that the proposed method is affected less by the initial clusteringcenter and improves the precision of clustering in both stand-alone environment and cluster environment.It also reduces the number of iterations of clustering and the clustering time.Key words:K-means algorithm;random sampling;max-min distance method;MapReduce;parallelization0 引 言聚类分析是数据挖掘领域中的一个重要分支,研究者针对各个领域提出了不同的改进聚类算法:划分聚类、层次聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类等算法[1-3]。尤其K-means算法使用最为广泛,但Kmeans算法对初始的k个中心依赖性很大,初始中心选择不当,容易造成局部最优解,增加迭代次数,降低执行效率。由于数据规模越来越大,而传统的聚类算法在处理大规模数据时无论从系统资源还是从实时性效率的角度,都不能提供很好的解决方案[4]。为解决上述问题,本文提出一种先抽样再用最大最小距离方法计算聚类中心的聚类分析方法。1 相关概念(1)K-means算法思想:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到聚类中心收敛为止[1]。(2)最大最小距离法:具体详细内容参见文献[11]。(3)欧氏距离(简称距离)Euclidean[2]D = X-C =2Σ ni=1(Xi-Ci) 槡2 (1)(4)加权聚类准则函数。聚类准则函数[2]:Mj = 1NjΣX∈SjX,其中Nj =|Sj| (2) 计算机工程与设计2015年Jc =Σkj=1ΣX∈SjX-Mj2 (3)由于是对大数据进行聚类,防止孤立点对Jc值的影响,采用加权聚类准则函数Jc = Σkj=1ΣX∈SjX-Mj( 2/n)12(4)式中:X———样本类别,Mj———样本均值,n———所有样本数目。(5)MapReduce编程模型的基本思路:将大数据集分解成千上百个小数据集,每个小数据集分别由集群中的1个节点并行执行Map计算任务并生成中间结果,然后这些中间结果多节点并行执行Reduce计算任务,形成最终结果。MapReduce执行过程如图1所示。图1 MapReduce执行过程2 改进的K-means算法2.1 改进算法思想K-means算法属于划分聚类算法之一,它有算法简单,速度快等优点;它也有对初始聚类中心依赖较大、对异常偏离数据敏感、只适合处理数值的数据等缺点。下文将针对优化初始聚类中心和并行化提出解决办法。改进算法的思路如下:设数据集X= {x1,x2...xn},且xi∈Od 其中n为样本个数,d为样本维度,k为聚类个数,m为迭代次数。传统K-means算法如下[7]:(1)适当选择k个类的初始中心;(2)在第m次迭代中,对任意一个样本,求其到k个中心的距离,将该样本归到距离最短的中心所在的类;(3)利用均值等方法更新该类的中心值;(4)对于所有的k个聚类中心,如果利用式(2)、式(3)的迭代法更新后,值保持不变,则迭代结束,否则继续迭代。本文算法是首先结合随机抽样方法从样本集X中抽取一个规模较小的工作集X′,设|X′|=|X|/s,其中s为抽样因子,一般取值在5~100之间(即抽样数据是原始数据1%~20%),取值视原始数据量而定。然后,用最大最小距离法计算抽样数据的聚类中心C1,再以C1作为据的聚类中心C,由于K-means之间的计算相互独立的,所以,可以使用MapReduce框架实现计算的并行化,提高计算的效率。然后再计算新的聚类中心C′与C距离是否小于设定的阀值Y,如果小于执行结束,返回新的聚类中心与聚类结果。否则用新的聚类中心C′重新聚类,直到两个聚类中心距离小于设定阀值为止。通过个流程可以分析出整个程序的时间复杂度为:O(nk (1/s+t)/ (M*N))其中n是样本集的个数,k是聚类个数,t是全局数据的迭代次数,M 是执行作业的Map个数,N是集群中执行该任务的结点数。2.2 改进算法的执行流程2.2.1 改进算法主要有个两个主要的步骤(1)确定初始化聚类的中心。(2)实现海量数据的K-means算法并行化计算。2.2.2 执行流程设数据集为X= {x1,x2,…,xn},其中xi∈Od,抽样因子为s,聚类个数为k,阀值参数为Y。(1)从数据集X中随机抽取n/s个样本数据构成抽样样本X′= {x′1,x′2...x′m};得到|X′|=|X|/s。(2)用最大最小距离方法计算抽样数据X′的k个聚类中心:1)先从抽样数据X′随机选择一个样本x′i,作为抽样数据聚类中心C1第1个中心点c1;2)用X中样本集计算出与c1欧氏距离式(1)最远的点x′j,作为第2个中心点c2;3)用X中样本集计算出与C1中样本集之间的欧氏距离:di1= x′i-c1  i=1,2…n;di2= x′i-c2  i=1,2…n;在所有模式中选择{min(di1,di2)i=1,2…n;}中最大的作为第3个中心点c3;即min(dj1,dj2)=max {min(di1,di2)i=1,2…n;}j=1,2…n;则c3=x′j;4)如果现有聚类中心的个数r(r<k),得到了C1={x′1,x′2…x′r},即确定第r+1个中心点:min(dj1,dj2…djr)=max {min (di1,di2…dir)i=1,2…n;}j=1,2…n;则cr+1=x′j;5)重复4),直到获得k个聚类中心,即C1= {x′1,x′2…x′k}(3)用C1作为全局数据的初始聚类中心C= {x1,x2…xk},使用MapReduce框架实现K-means算法的并行运算并求出新的聚类中心C′。(4)计算出新的聚类中心C′与C的距离是否小于阀值Y,如果小于Y,则返回聚类中心C及聚类结果;否则用C′作为新的聚类中心重新聚类,直到新的聚类中心与上一次聚类中心之间的距离小于Y时,聚类结束,返回聚类的中心与聚类结果。·1318·第36卷 第5期  韩岩,李晓:加速大数据聚类K-means算法的改进 3 实验与结果分析3.1 实验环境硬件:2.5GHZ的双核CPU,硬盘500G。软件:操作系统CentOS5,hadoop1.0.4,Eclipse4.2,单机伪分布式与集群完全分布式环境。3.2 实验结果与分析实验说明:方法都是基于MapReduce的并行运算,普通K-means方法(S):代表随机选择k个聚类中心后用Kmeans方法;最大最小距离的K-means (MM):最大最小距离法计算出k个聚类中心后再用K-means方法;抽样加最大最小距离的K-means(MMS):①先采用最大最小距离方法计算出抽样数据k个初聚类中心C;②使用聚类中心C作为全局数据的初始聚类中心;③ 再使用并行化的Kmeans方法计算出聚类的结果。记录数为n,聚类个数为k,终止条件为Y,方法为M,加权准则函数为Jc,迭代次数t,执行时间T。以下的结果是运行5次的平均结果。3.2.1 实验1:验证改进的K-means算法可行性首先才用人工标注的20条测试数据进行测试,数据分布如图2所示。图2 标注数据分布实验1运行结果见表1。表1 不同方法不同聚类个数聚类结果k/Y M Jc t T/s4/10-2S 5.5104 3.0 22.11MM 3.3487 2.0 15.49MMS 3.3487 2.0 15.205/10-2S 3.4529 2.4 15.03MM 1.6228 2.0 14.93MMS 1.6228 2.4 15.066/10-2S 1.5598 2.0 15.01MM 1.0762 2.0 14.95MMS 1.0762 2.0 15.05从表1与图3的结果中得出使用最大最小距离法Kmeans聚类取得了相同优化的解,而且在5次实验中保持了稳定性,且性能明显优于随机选择聚类中心的K-means,但于海量数据的聚类用最大最小距离方法来计算聚类中心很浪费时间的,甚至造成内存不足,所以提出了这种折中的方法用抽样数据中心代替全局数据初始聚类中心的聚类方法。图3 不同聚类个数与Jc趋势3.2.2 实验2:验证改进的K-means算法有效性实验说明:用随机产生的记录数来验证方法的有效性,记录数n (单位:万)分别是1、10、100,环境:单机伪分布条件下,方法同上,聚类为100时结果见表2。表2 单机下聚类结果n Y M Jc t T/s1 10-2S 0.4192 6.0 43.81MM 0.4091 5.0 95.66MMS 0.4104 4.0 43.3710 10-2S 0.4252 8.0 108.34MM 0.4175 3.0 474.82MMS 0.4212 3.0 44.95100 10-2S 0.4238 7.4 1195.12MM 时间过长MMS 0.4192 3.2 633.703.2.3 实验3:验证改进算法可以并行执行在虚拟机下4台均是装有CentOS5操作系统,内存512M,硬盘100G,2.5Ghz双核CPU,其中一台是master,三台是Slave。数据:使用实验2中数据。聚类为100时在集群的运行结果见表3。表3 集群下运行结果n Y M Jc t T/s1 10-2S 0.4192 6.0 57.19MM 0.4121 3.0 58.06MMS 0.4001 3.0 26.3310 10-2S 0.4252 8.0 91.36MM 0.4163 3.0 402.45MMS 0.4212 3.0 40.46100 10-2S 0.4248 7.0 1049.40MM 0.4241 5.0 4151.64MMS 0.4155 4.2 603.40通过表2得出以下结论:当数据量较小时,最大最小距离法Jc的值最小且执行时间最短;随着数据量的增加,最大最小距离法计算聚类中心时间增加导致计算时间过长;·1319· 计算机工程与设计2015年继续增加数据量时,这种方法将不在适合聚类运算。大数据量时,这种改进的方法执行时间大大减少了且加权准则函数值也降低了,提高聚类的质量。表3与表2对比,在同样的条件下,执行的时间明显是降低的,但并没成比例的降低。原因如下:①实验3中4台虚拟机总内存和实验2中1台虚拟机内存是相同的;②实验中随机数据和抽样数据导致迭代次数不一样,但在平均执行一次的时间,集群运行效率要比单机时效率要高。这也说明了同样条件下,并行化操作提高了运行效率。尤其是在执行时间上提高了2~3倍。4 结束语本文主要通过Hadoop平台上的MapReduce框架实现K-means算法并行化的聚类操作。实验结果表明:这种改进的方法选取了较优的初始聚类中心,降低了对初始聚类中心的依赖性,提高了聚类的质量及运行效率,加速了聚类的收敛速度。特别是在集群环境下,数据量较大时,完全随机分布的数据有明显的效果。下一步工作主要在于抽样数据质量与优化上再进行改进;集群优化与负载均衡等。参考文献:[1]ZHOU Aiwu,CUI Dandan,PAN Yong.An optimization initial clustering center of K-means clustering algorithm [J].Microcomputer &Its Applications,2011,30 (13):1-3 (in Chinese).[周爱武,崔丹丹,潘勇.一种优化初始聚类中心的Kmeans聚类算法[J].微型机与应用,2011,30 (13):1-3.][2]WANG Jia,JIANG Mingfu,LI Youguo.A cluster analysismethod based on improved K-means algorithm [J].AgricultureNetwork Information,2009,10:120-122 (in Chinese). [汪嘉,姜明富,李友国.一种基于改进的K-Means算法的聚类分析方法[J].农业网络信息,2009,10:120-122.][3]HUANG Tao,LIU Shenghui,TAN Yanna.Research of clustering algorithm based on K-means[J].Computer Technologyand Development,2011,21 (7):54-57 (in Chinese). [黄韬,刘胜辉,谭艳娜.基于K-means聚类算法的研究[J].计算机技术与发展,2011,21 (7):54-57.][4]QIAN Yanjiang.Research and realization of large-scale dataclustering techniques [D].Chengdu:Chengdu University,2009 (in Chinese). [钱彦江.大规模数据聚类技术研究与实现[D].成都:电子科技大学,2009.][5]WANG Xiuhua.A parallel speeding K-means clustering method[J].Computer Knowledge and Technology,2013,9 (18):4299-4302 (in Chinese).[王秀华.一种并行的加速K-均值聚类方法[J].电脑知识与技术,2013,9 (18):4299-4302.][6]Srirama SN,Jakovits P,Vainikko E.Adapting scientific computing problems to clouds using MapReduce [J].Future Generations Computer Systems,2012,39 (11):184-192 (inChinese). [Srirama SN,Jakovits P,Vainikko E.使用MapReduce解决云端的科学计算问题[J].下一代计算机系统,2012,39 (11):184-192.][7]HAN Jiawei,kamber.Data mining:Concepts and techniques[M].Beijing:Mechanical Industry Press,2008:288-375 (inChinese).[韩家炜,坎伯.数据挖掘概念与技术[M].北京:机械工业出版社,2008:288-375.][8]TIAN Shenping, WU Wenliang. Algorithm of automaticgained parameter value k based on dynamic K-means[J].Computer Engineering and Design,2011,32 (1):274-276 (in Chinese).[田森平,吴文亮.自动获取K-means聚类参数k值的算法[J].计算机工程与设计,2011,32 (1):274-276.][9]ZHOU Aiwu,YU Yafei.The research about clustering algorithm of K-means [J].Computer Technology and Development,2011,21 (2):62-65 (in Chinese). [周爱武,于亚飞.K-means聚类算法的研究[J].计算机技术与发展,2011,21 (2):62-65.][10]WANG Xiuhua.A speeding K-means clustering method basedon sampling [J].Computer and Modernization,2013 (12):27-29 (in Chinese).[王秀华.基于随机抽样的加速K-均值聚类方法[J].计算机与现代化,2013 (12):27-29.][11]ZHOU Juan,XIONG Zhongyang,ZHANG Yufang.Multiseed clustering algorithm based on max-min distance means[J].Computer Applications,2006,26 (6):1425-1427 (inChinese).[周涓,熊忠阳,张玉芳,等.基于最大最小距离法的多中心聚类算法[J].计算机应用,2006,26 (6):1425-1427.]·1320·

[返回]
上一篇:环氧树脂包覆聚磷酸铵微胶囊的制备及其对聚丙烯的阻燃效果
下一篇: 改进的大数据分层建树KNN聚类算法