算法数据论文,基于Spark平台的K means聚类算法改进并行化实现有...
罗军锋+洪丹丹
摘 要： 为了解决传统k⁃means算法需要输入k值和在超大规模数据集进行聚类的问题，这里在前人研究基础上，首先在计算距离时引入信息熵，在超大规模数据集采用数据抽样，抽取最优样本数个样本进行聚类，在抽样数据聚类的基础上进行有效性指标的验证，并且获得算法所需要的k值，然后利用引入信息熵的距离公式再在超大数据集上进行聚类。实验表明，该算法解决了传统k⁃means算法输入k值的缺陷，通过数据抽样在不影响数据聚类质量的前题下自动获取超大数据集聚类的k值。
关键词： k⁃means算法； 信息熵； 最优样本抽取； 有效性指标
中图分类号： TN911⁃34； TP311文献标识码： A 文章编号： 1004⁃373X（2014）08⁃0019⁃03
Automatic k⁃means clustering algorithm based on data sampling
LUO Jun⁃feng， HONG Dan⁃dan
（Information center， Xian Jiaotong University， Xian 710049， China）
Abstract： In order to solve the problems of the traditional k⁃means algorithm in which k values needs to be input and the the ultra⁃large⁃scale data set needs to be clustered， on the basis of previous studies， the information entropy is brought in when distance is calculated， and data sampling method is adopted， that is， the optimal samples are extracted from the ultra⁃large⁃scale data set to conduct sample clustering. Based on the sample data clustering， the validity indexes are verified and k value required by the algorithm is obtained. The distance formula for information entropy is brought in to carry out clustering on the ultra⁃large data set. Experiments show that the algorithm can overcome the defects of traditional k⁃means algorithm for k value input， and can automatically obtain k values of ultra⁃large data clustering under the premise of not affecting the quality of the early data clustering.
Keywords： k⁃means algorithm； information entropy； optimal sample extraction； validity index
0引言
聚类是数据挖掘中重要的三个领域（关联规则，聚类和分类）之一。它按照特定要求，对待分类的对象进行分类，要求类内相似度尽可能最大，同时类间相似度尽可能最小。k⁃means[1]算法因其简单实用而成为应用和研究最广泛的算法之一。但是该算法需要事先确定k值，而确定最佳k值一直也是聚类有效性研究的重要课题。一般情况下，确定最佳k值的基本思想为：在k值取值范围内运行k⁃means算法，得到不同的结果，选择合适的有效性评估指标对结果进行评估，最终确定最佳k值。近年来，许多研究人员对于如何确定最佳k值进行了深入的研究。包括聚类有效性指的研究，如XB（Xie⁃Beni）[2]，KL（Krzanowski⁃Lai）[3]，Sil（Silhouette）[4]，DB（Davies⁃Bouldin）[5]，IGP（In⁃Group Proportion）[6]，BWP（Between⁃Within Proportion）[7]。同时文献[8]研究了k值最优解[kopt]及其上限[kmax]的条件，证明了[kmax≤n]。但是这些研究没有基于海量数据之上，当数据量急剧扩大时，以上方法进行确定k值的效率由于数据的急剧扩大而得不偿失。因此，本文借鉴前人的研究成果，首先通过引入信息熵对前人的有效性指标进行了改进，针对海量数据集的数据挖掘，提出了基于数据抽样的k⁃means自动挖掘算法。该算法采用分段抽样策略，以新指标为有效性验证标准，通过引入统计最优数据抽样数，得到抽样数据的k值，然后将该k值应用到海量数据集上进行聚类，取得了良好的效果。
1相关概念和原理
1.1最优抽样数和抽样策略
衡量抽样效果的两个重要指标分别为样本容量和样本质量[9]。所谓样本容量是指所抽取的样本数，所谓样本质量是抽样样本的代表性，是抽样中的一个重要指标。在抽样过程中，如果样本集的容量越大，其与原数据集的相似程度也就越好，因而挖掘出来的结果与从原数据集挖掘结果的一致性也就越好。但是，抽样后挖掘结果的准确性和效率是一对矛盾体，样本量大，准确性高，效率低；样本量小，准确性低，效率高。
另外，当样本量增加超过一定规模后，准确性不会有足够的提升，将在保证结果准确性的情况下，抽取的最小样本量为最优样本数（Optimal Sample Size，OSS），准确寻找最优样本数非常麻烦，为此，本文引入文献[9]中的统计最优样本数来代替OSS。
1.2基于熵权重的距离度量
为提高算法的性能，对数据集中计算数据对象距离时采用加权距离，权重值的计算使用信息熵来确定。数据集中的各维属性对聚类结果的影响程度不同，并且不同的邻居对该数据的归类也有不同的影响。于是，本文借鉴文献[10]，引入信息熵的概念度量属性权重的大小，并进一步求得相邻对相之间的权重系数，最终求出基于熵权重的距离计算公式。
具体步骤如下：
（1） 设有如下属性值矩阵，其具有n个对象，m维属性：
[X=x11…x1m⋮⋱⋮xn1…xnm]
（2） 构造属性值属性比重矩阵。为了方便不同的量纲属性值进行比较，对属性值进行了标准化处理。处理方法为：
[rij=max(xij)-xijmax(xij)-min(xij)]
式中：[rij]为对象[xi]的第 j 维属性的属性值比重。
（3） 分别计算第 j 维属性的熵值，权值：
熵值：[Hj=-i=1nrijlnrijlnn]
权值：[wj=1-Hjj=1m（1-Hj）]， [0≤wj≤1，j=1mwj=1]
（4） 计算相邻对象间的权重系数。设对象[xj]是数据对象[xi]的某个邻居，则二者间的权重系数的计算公式如下：
[wij=p=1mwp×xjpxop] （1）
式中：[xop]表示对象[xi]的第 p 维属性值，对象[xo]是对象[xi]的邻居，[wp]是第p维属性的权值。
从式（1）中可以看出，相邻对象的权重系数是由对象的所有属性，其所有邻居共同决定，这样在随后计算距离时就最大限度地考虑了相邻对象之间的相互影响及其所有属性的影响。
那么基于信息熵的距离计算公式为：
[d(xi,xj)=wij×k=1m(xik-xjk)2]（2）
利用改进的距离计算公式可以更为准确地计算出各个数据对象之间的差距程度，在一定程度上提高了聚类的精确度。
1.3聚类有效性指标
好的聚类划分应使类内尽可能相似，类间尽可能不相似。目前，评价聚类结果优劣的指标很多，前面都提到过，本文选择BWP指标进行了局部改变，修改后的指标能更好地评价聚类划分的结果。
设k={X，R}为聚类空间，其中 [X=x1,x2,...,xn]，需要将样本聚类为c类则修改前的评价有效性指标BWP为：
[BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)-1nj-1q=1,q≠injxq(j),xi(j)2min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)+1nj-1q=1,q≠injxq(j),xi(j)2] （3）
由于修改前的BWP指标在计算距离时只是使用简单距离公式计算距离，没有考虑到各属性的权重，因此，本文在计算距离时引入信息熵，使用加权的距离公式，修改后的指标公式为：
[N_BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))-1nj-1q=1,q≠injd(xq(j),xi(j))min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))+1nj-1q=1,q≠injd(xq(j),xi(j))] （4）
2基于数据抽样的自动k⁃means聚类算法
结合以上分析，提出的具体算法归纳如下：
（1） 确定最优抽样数OSS；
（2） 在全部数据集中采用简单随机抽样策略抽取OSS个数据进行抽样样本数据聚类；
（3） 选择聚类数的搜索范围[[kmin，kmax]]，并且从[kmin]循环至[kmax]：
①调用k⁃means算法，距离公式采用式（2）对应的距离公式；
②利用式（4）计算单个样本的BWP指标值；
③计算在该聚类数的平均BWP指标值，即求所有单个样本BWP的简单算术平均。
（4） 求得平均BWP指标中最大时对应的k为最佳聚类数
（5） 在全部数据集中采用式（2）的距离公式，以上一步求的最佳聚类数k进行聚类。
3仿真实验与分析
本文实验采用Matlab 2012b开发环境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB内存，Windows XP操作系统上运行。本实验选取UCI机器学习数据库中的Mushroom Database作为实验数据。该数据库包含8 124个实例，23个属性。在实验前，需要将stalk⁃root属性上的空缺值补齐，然后进行实验。描绘该测试数据集的样本容量和样本质量关系曲线如图1所示。
图1 Mushroom数据集的学习曲线
设切线斜率阈值为0.2，计算出本数据集的OSS为604。为了实验，本文先后抽取了403，1 005，1 501和604这4种样本进行抽样聚类，结果下面会详细分析。针对上述6组样本进行了本算法的仿真实验，考虑到k⁃means算法本身由于初始聚类中心的不确定性，因此，本实验进行了10次实验，实验结果如表1所示。从表中可以看出，第一，随着样本数的增加，聚类精度也是提高的，但是，精度的提高速度越来越慢，说明本文引入的抽样方法是最优确定抽样样本数的方法；第二，从传统的k⁃means算法和本文算法比较来看，不论样本数的多寡，本文的聚类精度都比传统k⁃means算法精度高。
4结语
本文通过在传统距离公式中引入信息熵，并进行加权处理，并将此改进引入到有效性指标中，针对大规模数据集的数据挖掘，提出了基于数据抽样的k⁃means自动挖掘算法，该算法采用随机抽样策略，以新指标为有效性验证标准，通过引入统计最优数据抽样数，得到抽样数据的k值，然后将该k值应用到大规模数据集上进行聚类，取得了良好的效果。
表1 两种算法抽样样本的精度比较
参考文献
[1] MACQUEEN James. Some methods for classification and analysis of multivariate observations [C]// Proceedings of 5⁃th Berkeley Symposium on Mathematical Statistics and Probability. California， USA： [s.n.]，1967： 281⁃297.
[2] GAO Xiao⁃shan， LI Jing， TAO Da⁃cheng. Fuzziness measurement of fuzzy sets and its application in cluster validity analysis [J]. International Journal of Fuzzy Systems， 2007， 9 （4）： 188⁃191.
[3] DUDOIT Sandrine， FRIDLYAND Jane. A prediction⁃based resampling method for estimating the number of clusters in a dataset [J]. Genome biology， 2002， 3（7）： 1⁃22.
[4] ROUSSEEUW P J. Silhouettes： a graphical aid to the interpretation and validation of cluster analysis [J]. Journal of computational and applied mathematics， 1987， 20： 53⁃65.
[5] 周世兵，徐振源，唐旭清.基于近邻传播算法的最佳聚类数确定方法比较研究[J].计算机科学，2011，38（2）：225⁃228.
[6] KAPP A V， TIBSHIRANI R. Are clusters found in one dataset present in another dataset? [J]. Biostatistics， 2007， 8（1）： 9⁃31.
[7] 周世兵，徐振源，唐旭清.k⁃means算法最佳聚类数确定方法[J].计算机应用，2010（8）：1995⁃1998.
[8] 杨善林，李永森，胡笑旋，等.k⁃means算法中的k值优化问题研究[J].系统工程理论与实践，2006，26（2）：97⁃101.
[9] 于海涛.抽样技术在数据挖掘中的应用研究[D].合肥：合肥工业大学，2006.
[10] 唐波.改进的k⁃means聚类算法及应用[J].软件，2012（3）：36⁃40.
（4） 计算相邻对象间的权重系数。设对象[xj]是数据对象[xi]的某个邻居，则二者间的权重系数的计算公式如下：
[wij=p=1mwp×xjpxop] （1）
式中：[xop]表示对象[xi]的第 p 维属性值，对象[xo]是对象[xi]的邻居，[wp]是第p维属性的权值。
从式（1）中可以看出，相邻对象的权重系数是由对象的所有属性，其所有邻居共同决定，这样在随后计算距离时就最大限度地考虑了相邻对象之间的相互影响及其所有属性的影响。
那么基于信息熵的距离计算公式为：
[d(xi,xj)=wij×k=1m(xik-xjk)2]（2）
利用改进的距离计算公式可以更为准确地计算出各个数据对象之间的差距程度，在一定程度上提高了聚类的精确度。
1.3聚类有效性指标
好的聚类划分应使类内尽可能相似，类间尽可能不相似。目前，评价聚类结果优劣的指标很多，前面都提到过，本文选择BWP指标进行了局部改变，修改后的指标能更好地评价聚类划分的结果。
设k={X，R}为聚类空间，其中 [X=x1,x2,...,xn]，需要将样本聚类为c类则修改前的评价有效性指标BWP为：
[BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)-1nj-1q=1,q≠injxq(j),xi(j)2min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)+1nj-1q=1,q≠injxq(j),xi(j)2] （3）
由于修改前的BWP指标在计算距离时只是使用简单距离公式计算距离，没有考虑到各属性的权重，因此，本文在计算距离时引入信息熵，使用加权的距离公式，修改后的指标公式为：
[N_BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))-1nj-1q=1,q≠injd(xq(j),xi(j))min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))+1nj-1q=1,q≠injd(xq(j),xi(j))] （4）
2基于数据抽样的自动k⁃means聚类算法
结合以上分析，提出的具体算法归纳如下：
（1） 确定最优抽样数OSS；
（2） 在全部数据集中采用简单随机抽样策略抽取OSS个数据进行抽样样本数据聚类；
（3） 选择聚类数的搜索范围[[kmin，kmax]]，并且从[kmin]循环至[kmax]：
①调用k⁃means算法，距离公式采用式（2）对应的距离公式；
②利用式（4）计算单个样本的BWP指标值；
③计算在该聚类数的平均BWP指标值，即求所有单个样本BWP的简单算术平均。
（4） 求得平均BWP指标中最大时对应的k为最佳聚类数
（5） 在全部数据集中采用式（2）的距离公式，以上一步求的最佳聚类数k进行聚类。
3仿真实验与分析
本文实验采用Matlab 2012b开发环境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB内存，Windows XP操作系统上运行。本实验选取UCI机器学习数据库中的Mushroom Database作为实验数据。该数据库包含8 124个实例，23个属性。在实验前，需要将stalk⁃root属性上的空缺值补齐，然后进行实验。描绘该测试数据集的样本容量和样本质量关系曲线如图1所示。
图1 Mushroom数据集的学习曲线
设切线斜率阈值为0.2，计算出本数据集的OSS为604。为了实验，本文先后抽取了403，1 005，1 501和604这4种样本进行抽样聚类，结果下面会详细分析。针对上述6组样本进行了本算法的仿真实验，考虑到k⁃means算法本身由于初始聚类中心的不确定性，因此，本实验进行了10次实验，实验结果如表1所示。从表中可以看出，第一，随着样本数的增加，聚类精度也是提高的，但是，精度的提高速度越来越慢，说明本文引入的抽样方法是最优确定抽样样本数的方法；第二，从传统的k⁃means算法和本文算法比较来看，不论样本数的多寡，本文的聚类精度都比传统k⁃means算法精度高。
4结语
本文通过在传统距离公式中引入信息熵，并进行加权处理，并将此改进引入到有效性指标中，针对大规模数据集的数据挖掘，提出了基于数据抽样的k⁃means自动挖掘算法，该算法采用随机抽样策略，以新指标为有效性验证标准，通过引入统计最优数据抽样数，得到抽样数据的k值，然后将该k值应用到大规模数据集上进行聚类，取得了良好的效果。
表1 两种算法抽样样本的精度比较
参考文献
[1] MACQUEEN James. Some methods for classification and analysis of multivariate observations [C]// Proceedings of 5⁃th Berkeley Symposium on Mathematical Statistics and Probability. California， USA： [s.n.]，1967： 281⁃297.
[2] GAO Xiao⁃shan， LI Jing， TAO Da⁃cheng. Fuzziness measurement of fuzzy sets and its application in cluster validity analysis [J]. International Journal of Fuzzy Systems， 2007， 9 （4）： 188⁃191.
[3] DUDOIT Sandrine， FRIDLYAND Jane. A prediction⁃based resampling method for estimating the number of clusters in a dataset [J]. Genome biology， 2002， 3（7）： 1⁃22.
[4] ROUSSEEUW P J. Silhouettes： a graphical aid to the interpretation and validation of cluster analysis [J]. Journal of computational and applied mathematics， 1987， 20： 53⁃65.
[5] 周世兵，徐振源，唐旭清.基于近邻传播算法的最佳聚类数确定方法比较研究[J].计算机科学，2011，38（2）：225⁃228.
[6] KAPP A V， TIBSHIRANI R. Are clusters found in one dataset present in another dataset? [J]. Biostatistics， 2007， 8（1）： 9⁃31.
[7] 周世兵，徐振源，唐旭清.k⁃means算法最佳聚类数确定方法[J].计算机应用，2010（8）：1995⁃1998.
[8] 杨善林，李永森，胡笑旋，等.k⁃means算法中的k值优化问题研究[J].系统工程理论与实践，2006，26（2）：97⁃101.
[9] 于海涛.抽样技术在数据挖掘中的应用研究[D].合肥：合肥工业大学，2006.
[10] 唐波.改进的k⁃means聚类算法及应用[J].软件，2012（3）：36⁃40.
（4） 计算相邻对象间的权重系数。设对象[xj]是数据对象[xi]的某个邻居，则二者间的权重系数的计算公式如下：
[wij=p=1mwp×xjpxop] （1）
式中：[xop]表示对象[xi]的第 p 维属性值，对象[xo]是对象[xi]的邻居，[wp]是第p维属性的权值。
从式（1）中可以看出，相邻对象的权重系数是由对象的所有属性，其所有邻居共同决定，这样在随后计算距离时就最大限度地考虑了相邻对象之间的相互影响及其所有属性的影响。
那么基于信息熵的距离计算公式为：
[d(xi,xj)=wij×k=1m(xik-xjk)2]（2）
利用改进的距离计算公式可以更为准确地计算出各个数据对象之间的差距程度，在一定程度上提高了聚类的精确度。
1.3聚类有效性指标
好的聚类划分应使类内尽可能相似，类间尽可能不相似。目前，评价聚类结果优劣的指标很多，前面都提到过，本文选择BWP指标进行了局部改变，修改后的指标能更好地评价聚类划分的结果。
设k={X，R}为聚类空间，其中 [X=x1,x2,...,xn]，需要将样本聚类为c类则修改前的评价有效性指标BWP为：
[BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)-1nj-1q=1,q≠injxq(j),xi(j)2min1≤k≤c,k≠j(1nkp=1nkxp(k),xi(j)2)+1nj-1q=1,q≠injxq(j),xi(j)2] （3）
由于修改前的BWP指标在计算距离时只是使用简单距离公式计算距离，没有考虑到各属性的权重，因此，本文在计算距离时引入信息熵，使用加权的距离公式，修改后的指标公式为：
[N_BWP(j,i)=min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))-1nj-1q=1,q≠injd(xq(j),xi(j))min1≤k≤c,k≠j(1nkp=1nkd(xp(k),xi(j)))+1nj-1q=1,q≠injd(xq(j),xi(j))] （4）
2基于数据抽样的自动k⁃means聚类算法
结合以上分析，提出的具体算法归纳如下：
（1） 确定最优抽样数OSS；
（2） 在全部数据集中采用简单随机抽样策略抽取OSS个数据进行抽样样本数据聚类；
（3） 选择聚类数的搜索范围[[kmin，kmax]]，并且从[kmin]循环至[kmax]：
①调用k⁃means算法，距离公式采用式（2）对应的距离公式；
②利用式（4）计算单个样本的BWP指标值；
③计算在该聚类数的平均BWP指标值，即求所有单个样本BWP的简单算术平均。
（4） 求得平均BWP指标中最大时对应的k为最佳聚类数
（5） 在全部数据集中采用式（2）的距离公式，以上一步求的最佳聚类数k进行聚类。
3仿真实验与分析
本文实验采用Matlab 2012b开发环境，在Intel（R） Core（TM） i5CPU 3.4 GHz，4 GB内存，Windows XP操作系统上运行。本实验选取UCI机器学习数据库中的Mushroom Database作为实验数据。该数据库包含8 124个实例，23个属性。在实验前，需要将stalk⁃root属性上的空缺值补齐，然后进行实验。描绘该测试数据集的样本容量和样本质量关系曲线如图1所示。
图1 Mushroom数据集的学习曲线
设切线斜率阈值为0.2，计算出本数据集的OSS为604。为了实验，本文先后抽取了403，1 005，1 501和604这4种样本进行抽样聚类，结果下面会详细分析。针对上述6组样本进行了本算法的仿真实验，考虑到k⁃means算法本身由于初始聚类中心的不确定性，因此，本实验进行了10次实验，实验结果如表1所示。从表中可以看出，第一，随着样本数的增加，聚类精度也是提高的，但是，精度的提高速度越来越慢，说明本文引入的抽样方法是最优确定抽样样本数的方法；第二，从传统的k⁃means算法和本文算法比较来看，不论样本数的多寡，本文的聚类精度都比传统k⁃means算法精度高。
4结语
本文通过在传统距离公式中引入信息熵，并进行加权处理，并将此改进引入到有效性指标中，针对大规模数据集的数据挖掘，提出了基于数据抽样的k⁃means自动挖掘算法，该算法采用随机抽样策略，以新指标为有效性验证标准，通过引入统计最优数据抽样数，得到抽样数据的k值，然后将该k值应用到大规模数据集上进行聚类，取得了良好的效果。
表1 两种算法抽样样本的精度比较
参考文献
[1] MACQUEEN James. Some methods for classification and analysis of multivariate observations [C]// Proceedings of 5⁃th Berkeley Symposium on Mathematical Statistics and Probability. California， USA： [s.n.]，1967： 281⁃297.
[2] GAO Xiao⁃shan， LI Jing， TAO Da⁃cheng. Fuzziness measurement of fuzzy sets and its application in cluster validity analysis [J]. International Journal of Fuzzy Systems， 2007， 9 （4）： 188⁃191.
[3] DUDOIT Sandrine， FRIDLYAND Jane. A prediction⁃based resampling method for estimating the number of clusters in a dataset [J]. Genome biology， 2002， 3（7）： 1⁃22.
[4] ROUSSEEUW P J. Silhouettes： a graphical aid to the interpretation and validation of cluster analysis [J]. Journal of computational and applied mathematics， 1987， 20： 53⁃65.
[5] 周世兵，徐振源，唐旭清.基于近邻传播算法的最佳聚类数确定方法比较研究[J].计算机科学，2011，38（2）：225⁃228.
[6] KAPP A V， TIBSHIRANI R. Are clusters found in one dataset present in another dataset? [J]. Biostatistics， 2007， 8（1）： 9⁃31.
[7] 周世兵，徐振源，唐旭清.k⁃means算法最佳聚类数确定方法[J].计算机应用，2010（8）：1995⁃1998.
[8] 杨善林，李永森，胡笑旋，等.k⁃means算法中的k值优化问题研究[J].系统工程理论与实践，2006，26（2）：97⁃101.
[9] 于海涛.抽样技术在数据挖掘中的应用研究[D].合肥：合肥工业大学，2006.
[10] 唐波.改进的k⁃means聚类算法及应用[J].软件，2012（3）：36⁃40.
