大数据k-Means聚类挖掘优化算法
2015-04-20宋旭东朱文辉邱占芝
宋旭东，朱文辉，邱占芝
(大连交通大学 软件学院，辽宁 大连 116028)
大数据k-Means聚类挖掘优化算法
宋旭东，朱文辉，邱占芝
(大连交通大学 软件学院，辽宁 大连 116028)
基于数据规模导致难以应对的存储量、数据规模导致传统算法失效、大数据复杂的数据关联性导致高复杂度的计算等问题,对大数据下的k-means聚类优化算法进行研究，给出了适用于大数据任务处理的MapReduce软件架构的模型机制，通过改进k-means初始聚类中心的选取，提出了一种基于MapReduce模型的k-means聚类优化算法.最后将改进的算法应用于煤炭煤质的分析中，结果显示较传统算法，改进算法的效率有明显提高.
大数据；数据挖掘；k-means算法；MapReduce模型
0 引言
云计算、物联网、社交网络等新兴服务促使人类社会的数据种类和规模正以前所未有的速度增长，大数据时代已到来.大数据量可显著提高机器学习算法的准确性；训练数据集越大,数据分类精度越高；大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果，因此数据量足够大时有可能使用代价很小的简单算法来达到很好的学习精度.
然而，基于大数据的数据挖掘的研究面临新的挑战，主要表现在：数据规模导致难以应对的存储量；数据规模导致传统算法失效；大数据复杂的数据关联性导致高复杂度的计算.
本文主要研究大数据下的聚类优化算法，主要是根据实体的特征对其进行聚类，按一定的距离或相似测度在大型多维空间数据集中标识出聚类或稠密分布的区域，将数据分成一系列相互区分的组，以期从中发现数据集的整个空间分布规律和典型模式.k-means聚类算法是数据挖掘技术中基于分裂法的一个经典的聚类算法，因为该算法的理论可靠、算法简单、收敛迅速而被广泛应用[1].
选择合理的一组初始聚类中心，可以得到较高的聚类准确率.文献[2]利用贪心算法参照数据样本的分布特征将数据划分为k个集合，选取各集合中数据的平均值作为初始聚类中心.文献[3]提出了一种基于关联图划分的k-means算法.该算法能够有效地根据数据的分布特性选取初始聚类中心.文献[4]结合密度法和最大化最小距离的思想，首先选取相互间距离最大的k对高密度点，并以这k对高密度点的均值作为聚类的初始中心，然后再进行k-Means聚类.文献[5]针对数据对象的分布密度以及计算最近两点的垂直中点方法来确定k个初始聚类中心 ,以获得最优聚类.然而这些传统的聚类挖掘优化算法在面对海量大数据时算法的时间复杂度都比较高.本文研究大数据下的k-means聚类算法，在进行改进初始聚类中心选取的基础上，提出了一种基于MapReduce模型的k-means聚类优化算法.
1 大数据MapReduce软件架构模型机制
Google提出的软件架构MapReduce是一种用于大规模数据集的并行运算编程模型，在处理T级别以上巨量数据的业务上有着明显优势[6].
MapReduce运行机制的基本思路是将数据集分解为成百上千的小数据集split，若干个数据集交由集群的一个节点并行执行Map计算并产生中间结果，之后这些中间结果又交由大量的节点执行Reduce计算产生最终结果.
MapReduce运行机制的核心是Map和Reduce函数.Map函数功能是按照一定的规则将输入的键值
MapReduce运行机制如图1所示.
图1 MapReduce软件架构模型机制
2 基于MapReduce软件架构的聚类挖掘优化算法
2.1 算法框架结构
用MapReduce处理的数据集应具备这样的特点：它可以被分解为许多小的数据集，且每一个小的数据集可以完全并行的进行处理[7-8].基于Hadoop的k-means算法的处理过程主要有两部分，第一部分是初始聚类中心，并把数据集样本分为一定大小的数据块，以便并行处理.第二部分及时启动Map和Reduce任务进行算法的并行化处理，直至产生聚类结果.
其算法流程如图2所示.
图2 基于MapReduce的并行化k-means算法流程
除去对初始聚类中心选取的优化，假设每个节点处理p个任务，共有h个节点，那么优化后的算法时间复杂度为n*k*l*t/(p*h).从理论上基于MapReduce的k-means算法时间效率提高了很多.
2.2 k-means算法初始聚类中心的优化
传统的算法初始聚类中心的选取是随机的，这就造成聚类结果的不稳定性[9].本文采取一种初始聚类中心选取的方法，提高结果的稳定性.优化的k-means聚类算法首先根据一定的算法规则选择k个样本作为初始化聚类中心点，然后将k个聚类中心存放在HDFS上的一个文件中，作为全局变量[10].
设聚类样本数据集：D={di|di∈R,i=1,2,3,…,n},k个聚类中心用c1,c2,c3,…,ck表示.具体有如下定义：
初始聚类中心算法描述如下：
输入：终止条件ε以及聚类个数k,样本数据的数据集D，存储两两样本点间距离dist(di,dj)的矩阵D1，集合A及聚类中心集合C.
输出：满足终止条件，得出k个初始聚类中心.
处理：
(1)计算数据集D中两两样本点之间的距离dist(di,dj)并存入矩阵D1中.
(2)初始化集合A及聚类中心集合C，最小距离样本点放入集合A中，并将其中心O1作为第一个初始的聚类中心存入C中.
(3)求出矩阵D1次小距离的样本点中心，然后求出此中心与O1的距离，与averg比较；如果小于averg，则将此样本点加入A中，再求第三距离小的样本点，重复步骤(3)；如果大于averg，则将此中心存入C.
(4)直到集合C中个数为k.
3 算法实验
将基于MapReduce的k-means算法应用于某大型煤炭企业.我们将一台机器作为NameNode和JobTracter节点，其他五台机器作为DataNode和TaskTracker节点.每台节点硬件配置如下：CPU型号为英特尔Corei5M480 @ 2.67GHz双核、内存为1G.硬盘容量为250G，7 200r/m，构建了基于MapReduce的k-means优化算法应用平台，实现对煤炭特征数据的聚类分析.
应用中选取18038个煤炭数据样本点，采用k-means传统算法和优化算法进行试验，设置生成4个聚类.传统算法的聚类结果由于对初始聚类中心的依赖性导致聚类结果不稳定，不同的的试验其产生的聚类结果也在不断变化，而经过优化算法结果始终保持不变.本文选取了两个传统算法的聚类结果，及其优化算法的聚类结果如图3所示.
从结果可以看出优化算法与传统算法相比有更高的准确性和稳定性.
图3 传统算法及优化算法聚类结果
4 结论
针对大数据k-means聚类数据挖掘问题，本文给出了基于MapReduce软件架构模型机制，完成了k-means聚类算法的初始聚类中心的选取优化，实现了基于MapReduce模型机制的k-means聚类优化算法.实验表明，优化改进后的算法与传统算法相比拥有较好的有效性和更高的计算效率，并且数据量越大优势就越明显.本文实验表明在处理大数据时，应用MapReduce软件架构平台对实现包含k-means算法在内的数据挖掘算法具有现实意义.
[1]苏锦旗,薛惠锋,詹海亮.基于划分的K-均值初始聚类中心优化算法[J].微电子学与计算机，2009(1):14-17.
[2]仝雪姣,孟凡荣,王志晓.对k-means初始聚类中心的优化[J].计算机工程与设计，2011(8):165-167.
[3]李正兵，罗斌，翟素兰，等. 基于关联图划分的 Kmeans 算法[EB/OL]. 计算机工程与应，2012. http://www.cnki.net/kcms/detail/11.2127.TP.20120615.1726.025.html.
[4]邓海，覃华，孙欣. 一种优化初始中心的K-Means聚类算法[EB/OL].计算机技术与发展，2013. http://www.cnki.net/kcms/detail/61.1450.TP.20130724.0945.012.html.
[5]周炜奔,石跃祥.基于密度的K-means聚类中心选取的优化算法[J].计算机应用研究,2012(5):132-134.
[6]LAMMEL R. Google′s MapReduce Programming Model-Revisited[J]. Science of Computer Programming,2008,70(1):1-30.
[7]SATISH NARAYANA SRIRAMA, PELLE JAKOVITS, EERO VAINIKKO.Adapting scientific computing problems to clouds using MapReduce[J].Future generations computer systems,2012,28(1):184-192.
[8]刘鹏.实战Hadoop—开启通向云计算的捷径[M].北京：电子工业出版社，2011：60-74.
[9]JIAWEI HAN，MICHELINE KAMBER. 数据挖掘概念与技术[M].北京：机械工业出版社，2007：2-3.
[10]周爱武，崔丹丹，潘勇.一种优化初始聚类中心的k-means聚类算法[J].微机型与应用，2011(13):1-3.
Big Data K-Means Clustering Mining Optimization Algorithm
SONG Xudong, ZHU Wenhui, QIU Zhangzhi
(Software Institute,Dalian Jiaotong University,Dalian 116028,China)
For the difficulty of storage capacity dealing with big data,failure of traditional algorithms for big scale data and high complexity computation,k-means clustering mining optimization algorithm is studied based on big data,and a MapReduce software architecture is proposed.It is suitable for large data processing mechanism, provides an improved method for selecting initial clustering centers and puts forward a k-means algorithm optimization based on MapReduce model.The improved algorithm is applied to coal quality analysis,and the result shows that compared with traditional algorithms,the optimization algorithm improves the efficiency obviously,and the accuracy is also enhanced.
big data;data mining;k-means algorithm;MapReduce model
1673-9590(2015)03-0091-04
2014-01-22
国家自然科学基金资助项目( 61074029)；大连市科技计划资助项目(2014A11GX006)
宋旭东(1969-)，男，教授，博士，从事大数据分析、数据挖掘与决策支持的研究E-mail:xudongsong@126.com.
A
