云计算环境中k-mean大数据聚类方法应用研究_李英杰.pdf

云计算环境中k m e a n大数据聚类方法应用研究李英杰,王 芮,尚 影(阜阳幼儿师范高等专科学校,安徽 阜阳 2 3 6 0 1 5)摘 要:传统k m e a n算法解决数据聚类问题时容易陷入局部最优,且单位时间内聚类数据的效率不高等问题,本文针对这些缺点对k m e a n算法进行改进。在M a p R e d u c e框架下并行化布局k m e a n聚类算法,基于分治策略将大数据集分为数据块,同时削减s p i l l文件的合并以降低M a p节点计算量输出;基于密度参数选取k m e a n聚类算法的中心点,使用误差平方和确定算法聚类个数,避免数据聚类陷入局部最优。实验结果显示,该方法在聚类精度与效率方面均展现其优势,具有较强的数据聚类实际应用价值。关键词:云计算;M a p R e d u c e框架;k m e a n算法;大数据聚类中图分类号:T P3 1 1.1 3 文献标志码:A 文章编号:2 0 9 5 9 6 9 9(2 0 2 2)0 6 0 0 2 8 0 30 引言大数据信息的存在造就了云计算环境的高速发展,此背景下有效信息提取大多是根据数据特征进行合理分类,明晰数据信息结构1。云计算环境中M a p R e d u c e框架在实际应用中脱颖而出,为海量数据聚类创造了行之有效的计算方法,实现数据的分布式并行化运算。布局于M a p R e d u c e框架下的聚类算法多种多样,其中k m e a n聚类算法应用广泛且取得了良好的聚类效果,属于无监督的学习算法,适用于当前的人工智能、数据挖掘领域的相关研究2;但其缺点是初始中心与K值确定的随机性较强,容易使聚类结果陷入局部最优解。针对这一问题本文对传统K值聚类算法进行改进与优化,提供了一种新的云计算大数据聚类方法。1 基于k m e a n算法的云计算大数据聚类方法1.1 数据聚类的云计算环境构建策略为了加快k m e a n算法处理数据聚类的速度、适应大数据时代数据整合的需求,将k m e a n算法实施M a p R e d u c e并行化处理并基于H a d o o p集群环境运行,在特定时间内实现更多数据的并行化计算与聚类。为提高k m e a n算法在M a p R e d u c e框架中运行的加速比、拓展性,对经典的M a p R e d u c e框架进行改进与优化:使用分治策略管理大数据集。将待聚类的数据集分为多个较小的“块”,在各个机器主存储器中保存,分割数据块的机器也可以聚集这些小的数据块3;执行k m e a n算法时在这些数据块范围内各自提取中心得到比数据块还小的数据集,在这些数据集中确定聚类中心,极大缩小k m e a n算法中心点确定的范围。削减s p i l l文件的合并以降低M a p节点计算量输出,减少缓存。在M a p任务执行期间,仅仅读取内存缓存区域中的s p i l l文件将其读入磁盘,而非对全部s p i l l文件实施合并操作4;同时在M a p内设置新的线程供其余s p i l l文件进行合并,这样减少M a p节点阶段计算结果的输出,降低算法的缓存与负载负担。1.2 基于密度参数的k m e a n聚类中心选取第3 7卷 第6期2 0 2 2年1 2月 景德镇学院学报J o u r n a l o f J i n g D e Z h e nU n i v e r s i t y V o l.3 7N o.6D c e.2 0 2 2收稿日期:2 0 2 2 0 7 2 4基金项目:安徽省高等学校省级质量工程教学团队项目(2 0 2 0 j x t d 1 9 4);安徽高校自然科学重点研究项目(K J 2 0 2 1 A 1 5 7 3);安徽省高等学校省级质量工程线下课程项目(2 0 2 0 k f k c 3 8 7)作者简介:李英杰(1 9 8 1),男,安徽阜阳人。副教授,硕士,从事大数据应用、应用数学、教育技术研究。k m e a n算法聚类过程中,如果数据样本的欧氏距离较小,对应的相似度越好,换言之,特定区域中数据聚集的程度越高,在这一区域中选择原始中心点更为科学合理,可以获得更优的聚类结果5。根据这一描述,此次研究在云计算M a p R e d u c e框架的M a p阶段基于密度参数概念优化选取聚类中心,避免数据聚类的随机性6。首先,定义xx1,x2,xn表示数据聚类的样本集合,将其分配至k个集合内,令其误差平方和最小化同时保持不变。在数据样本中,xp、xq均表示数据对象,协方差矩阵用U表示,此时可基于公式表示其距离:dp q=xp-xq()TU-1xp-xq()()12 其次,定义密度参数变量。设置xp的邻域,将空间内随机点xp作为中心、将r作为半径长度得到一个圆形区域,即为xp的邻域。那么此区域中点的数量则是基于距离r的密度参数,使用g(xp,r)描述7。基于密度参数概念进行k m e a n算法初始中心点选取,过程描述为:将数据集作为输入,聚类的数量设置为k,将聚类得到的k个簇作为结果输出,同时输出算法的聚类误差值。基于公式求取数据对象xp、xq的距离,即d(xp,xq)。求取各个数据对象的密度参数,以从低到高的顺序进行排列生成集合I;此时聚类的首个中心点即为集合I中密度参数最大值对应的数据对象,标记为A;接下来选取数据对象A,即与A距离最大、密度值最大的对象。生成第二个聚类中心点,方法如下:求取A与A的距离标记为R1,求取O1为两点的中心点,将R1的一般作为半径值、以O1为圆心,从点A或者点A出发做顺时针旋转操作获取崭新的点标记为A0,第二个聚类中心点即为相距A0最近的点。当聚类中心数量与k值一致时进行下一聚类步骤,反之则将A0作为参照点重复步骤。1.3 基于误差平方和的聚类个数值确定本次研究基于误差平方和原则获取k m e a n算法的k值,即对特定范围数据进行遍历得到该区域内聚类数的误差平方和,进行k值选取,过程如下:定义一个数据集包含n个对象,描述为x1,x2,xc,xn。聚类过程中k值一般不少于2,不大于2,此时需要计算当k值最大和最小及其区间内的误差平方和,方法见公式:FB=kk=1xBkx-2k 公式中,样本同聚类中心的函数表示为F,即样本与所属类别中心距离的平方和;n个数据划分至K个类别中,此时不同类采用B1、B2、BK 等形式描述;BK均值采用K表示。当误差平方和逐渐降低时对应的k值为最优,此时需要进一步基于公式求取两个邻近k值的误差平方和的差:z=m a xFB-FB-1()误差平方和最大差对应的G值即为所要求取得新的k值8。2 实验与分析为了验证本次研究改进的k m e a n聚类算法的优势,搭建如下云计算实验环境:实验计算机硬件采用W i n d o w s 1 0系 统,处 理 器 为i 5 7 0 0 0,在H a-d o o p 2.7.4环境下布局M a p R e d u c e框架,包括1个主节点和6个从节点。实验选用的数据集分别为H集、B集、W集,各包含样本大小为1 G B、3 G B、5 G B。同时将基于样本密度k m e a n聚类算法、基于贝叶斯 改 进k m e a n聚 类 算 法 作 为 对 比 测 试 方法9,以突出本文方法的性能与优势。在H数据集上三种方法的数据聚类测试结果如表1所示。表1 三种方法的数据聚类测试结果测试内容本文方法基于样本密度k m e a n聚类算法基于贝叶斯改进k m e a n聚类算法k值2迭代4次,准 确率9 7.2%迭代8次,准 确率8 7.6%迭代9次,准 确率8 0.4%3迭代5次,准 确率9 6.4%迭代1 3次,准 确率8 4.6%迭代1 5次,准 确率7 6.6%4迭代6次,准 确率9 6.8%迭代1 6次,准 确率8 2.6%迭代1 8次,准 确率7 5.9%表1数据显示,随着k值的增加,三种方法的迭代次数有所提升,准确率有一定的浮动迹象。具体而言,当k值由2增加至4时,本文方法迭代次数由4次增加到6次,最终聚类准确率为9 6.8%,在云计算环境下的数据聚类效果较优。而k值为4时,基于样本密度k m e a n聚类算法已经迭代了1 6次,准确率为8 2.6%;此时基于贝叶斯改进k m e a n聚类算法迭代1 8次,准确率却仅为7 5.9%,二者聚类效果与性能均不太理想。922 0 2 2年第6期 李英杰,王 芮,等:云计算环境中k-m e a n大数据聚类方法应用研究 基于三种方法对三个不同规模的数据集进行聚类测试,图1描述三种方法聚类测试过程中的时间开销情况,随着数据规模的变化,各方法的时间开销有所差别。图1 三种方法进行大数据聚类的时间开销统计图1中,三种方法聚类的时间开销均随着数据规模的增加有所增长,其中本文方法增幅最低,处理1 G B文件约耗时7.1 m i n,处理5 G B文件的耗时约为1 7 m i n,增幅较小,效率较高。而基于样本密度k m e a n聚类算法、基于贝叶斯改进k m e a n聚类算法聚类耗时一路攀升,处理3 G B、5 G B文件的耗时均在5 0 m i n以上,远落后于本文方法的聚类效率。综合上述实验结果看出,在聚类准确度与效率方面,本文方法在三种聚类算法中脱颖而出,具有一定的大数据聚类应用价值。3 结论本文对传统k m e a n聚类算法进行改进,取得了良好的测试效果,优势在于以下两点:首先,在H a d o o p集群环境中对k m e a n聚类算法进行M a p R e d u c e并行化处理,分布式完成聚类任务,大量节约算法聚类的时间开销;其次,对传统k m e a n聚类算法中心点与k值确定方法进行改进,降低算法的随机性与不确定性,避免陷入局部最优解,更容易得到准确的聚类结果,由此提升算法聚类精度。在以后的研究中,可尝试在s p a r k等计算框架中进行算法优化,进一步加强算法的大数据聚类能力。参考文献:1 孙倩,陈昊,李超.基于改进人工蜂群算法与M a p R e d u c e的大数据聚类算法J.计算机应用研究,2 0 2 0,3 7(0 6):1 1 3 1 1 6+1 7 0.2 何婕,赖敏.云计算平台中分布式H a d o o p数据挖掘关键技术研究J.机床与液压,2 0 1 8,4 6(2 4):1 5 0 1 5 5.3 宋阳,石鸿雁.基于M a p R e d u c e框架下的K m e a n s聚类算法的改进J.计算机与现代化,2 0 1 9(8):2 8 3 2+4 3.4 全海金,何映思.基于大数据的改进模糊K m e a n s算法J.重庆理工大学学报(自然科学版),2 0 1 8,3 2(1 2):1 4 5 1 4 8.5 陈洲,陆南.基于K M e a n s算法的W e b日志用户聚类研究J.计算机与数字工程,2 0 2 0,4 8(0 3):1 4 0 1 4 4.6 李爽,陈瑞瑞,林楠.面向大数据挖掘的H a d o o p框架K均值聚类算法J.计算机工程与设计,2 0 1 8,0 3 9(0 1 2):3 7 3 4 3 7 3 8.7 夏永泉,孙静茹,WU X i n w e n,等.基于改进K均值聚类算法的星点聚类研究J.图学学报,2 0 1 9,4 0(2):1 4 8 1 5 3.8 孙艺,赵瑛珲,王天棋,等.一种K 均值优化算法的研究与改进J.自动化技术与应用,2 0 2 1,4 0(0 9):1 5+1 1.9 杨博宁.基于k m e a n聚类算法的加密云数据排序搜索仿真J.计算机仿真,2 0 2 0,3 7(9):4 5 1 4 5 5.A p p l i c a t i o no fK m e a nB i gD a t aC l u s t e r i n gM e t h o d i nC l o u dC o m p u t i n gE n v i r o n m e n tL IY i n g j i e,WA N GR u i,S H A N GY i n g(F u y a n gP r e s c h o o lT e a c h e r sC o l l e g e,F u y a n g2 3 6 0 1 5,A n h u iP r o v i n c e,C h i n a)A b s r t a c t:T h e t r a d i t i o n a lk m e a na l g o r i t h mi se a s yt of a l l i n t ot h el o c a lo p t i m u m w h e ns o l v i n gt h ed a t ac l u s t e r i n gp r o b l e m,a n d t h e e f f i c i e n c yo f c l u s t e r i n gd a t ap e ru n i t t i m e i sn o t h i g h,s o t h i sp a p e r i m p r o v e s t h ek m e a na l g o r i t h mi nv i e wo f t h e s es h o r t c o m i n g s.U n d e rt h eM a p R e d u c ef r a m e w o r k,t h ep a r a l l e l l a y o u tk m e a nc l u s t e r i n ga l g o r i t h md i v i d e s t h e l a r g ed a t a s e t i n t od a t ab l o c k sb a s e do n t h ed i v i d e a n dc o n q u e r s t r a t e-g y,a n dr e d u c e s t h em e r g eo f s p i k e f i l e s t o r e d u c e t h e c o m p u t a t i o no u t p u t o f t h em a pn o d e.T h e c e n t e rp o i n to fk m e a nc l u s t e r i n ga l g o r i t h mi s s e l e c t e db a s e do nd e n s i t yp a r a m e t e r s,a n dt h en u m b e ro f c l u s t e r i n ga l g o-r i t h m s i sd e t e r m i n e db yu s i n g t h e s u mo f s q u a r e s o f e r r o r s t oa v o i dd a t a c l u s t e r i n g f a l l i n g i n t o l o c a l o p t i m i-z a t i o n.F i n a l l y,t h ee x p e r i m e n t a l r e s u l t ss h o wt h a t t h i sm e t h o ds h o w s i t sa d v a n t a g e s i nc l u s t e r i n ga c c u r a c ya n de f f i c i e n c y,a n dh a ss t r o n gp r a c t i c a l a p p l i c a t i o nv a l u e i nd a t ac l u s t e r i n g.K e yw o r d s:c l o u dc o m p u t i n g;M a p R e d u c e f r a m e w o r k;K m e a na l g o r i t h m;b i gd a t ac l u s t e r i n g03 景德镇学院学报 2 0 2 2年第6期