基于数据场的数据势能竞争与K-means融合的聚类算法

许家楠 张桂珠

(江南大学物联网工程学院 江苏 无锡 214122)

基于数据场的数据势能竞争与K-means融合的聚类算法

许家楠 张桂珠

(江南大学物联网工程学院 江苏 无锡 214122)

K-means算法采用欧氏距离进行数据点的划分，不能够准确地刻画数据集特征，而随机选取聚类中心点的机制，也不能获得好的聚类结果。为此，提出一种基于数据场的数据势能竞争与K-means算法融合的聚类算法。算法中定义了数据场的概念，利用局部最小距离进行数据聚合势能的竞争，然后利用势能熵提取基于数据集分布的最优截断距离，根据截断距离与斜率确定出簇中心点，实现K-means聚类。在UCI数据集上的测试结果表明，融合后的算法具有更好的聚类结果。

数据竞争 数据场 势能熵 斜率 复杂数据集

0 引 言

聚类分析又称为聚类，是数据挖掘研究的一个重要方向，是一种将数据对象划分为不同子簇的过程。每个子簇称为一类，使得同一类簇的对象差异尽可能小，而不同子簇间的差异尽可能的大[1]。聚类中的方法主要可以分为划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法。划分方法中比较典型的有K-means[2]和K-medoids[3]等聚类方法；层次方法中有CURE[4]和CHAMELEON[5]等聚类方法；基于密度的方法中有DBSCAN[6]和OPTICS[7]等聚类方法；基于网格的方法中有STING[8]和WAVECLUSTER[9]等聚类方法；以及基于模型的统计学聚类方法和神经网络聚类方法。其中K-means算法作为数据挖掘技术中基于划分方法的一个经典算法，该算法具有理论可靠、算法简单、收敛速度快而应用广泛[10]。但是K-means算法存在诸多缺陷：聚类中心点的随机选取，将导致算法陷入局部最优值；欧氏距离测度，不能够准确描述数据集的分布信息，难以处理复杂结构的数据集。鉴于以上问题，有Lu等提出一种数据竞争(DC)的聚类算法，通过数据样本点之间淘汰竞争找聚类中心点完成聚类[11]。DC算法对离群点与噪声点不是很敏感，具有简单高效的特点。

DC算法与大多数基于中心的算法一样，对于球状簇有很好的处理效果，但是难以处理非球状以及多维尺度的数据簇，例如密度分布不均匀的数据集。DC算法是在数据相似性矩阵的基础上进行聚类，而相似性矩阵采用欧氏距离测度，亦不能够有效地描述数据集数据点之间的相互关系，处理复杂结构的数据集的能力不足。故针对DC算法的缺陷，一种对密度敏感的DC算法被提出，此算法对具有密度流行结构的数据集有较好的聚类效果，但是仍无法处理密度分布不均的数据集[12]。而Zelnik-Manor等提出的基于Self-Tuning相似度的自调节谱聚类算法[13]，能够有效地处理密度分布不均匀的数据集，但Self-Tuning难以应用到类似DC以及K-means这种没有拉谱拉斯谱映射过程的聚类算法。对于上述算法存在的问题，本文提出了一种基于数据场数据势能竞争的K-means算法(K-means Algorithm For Data Potential Energy Competition),简称K-DPEC算法。该算法根据数据场中簇中心点与同簇数据集中数据点之间相互吸引作用，不同簇聚类中心点相互排斥，且数据场中的簇中心点聚合了该簇中所有点的势能量，即具有最大聚合能量的点被视为聚中心点。其次,根据数据的分布情况，采用势能熵确定数据集的最优截断距离以及结合斜率的想法选出簇中心点。最后利用K-means算法迭代划分数据点实现聚类。通过仿真实验表明，K-DPEC算法比原有的DC算法以及K-means算法具有更好的效果。

1 数据势能竞争(DPEC)聚类算法

1.1 数据场

定义1数据集中内部数据点之间存在类似引力场的作用，使得数据集被吸引力及斥力分裂成不同的簇，而这样的相互作用称为数据场。

定义2数据场模型的目的是为了实现描述数据集中簇内数据点与簇中心点之间的关系，按照数据场的概念建立起来的。

Wang等提出数据场来描述数据空间中对象之间的相互作用[14]。在数据场中，数据集内簇中点与属于该簇的数据点之间存在相互吸引作用，而不同的簇中心点之间存在排斥，并且相同簇内的数据点只会与簇中心点产生作用而不会与簇外数据点发生作用。在物理场中，每个数据对象都被视为一个粒子，势能被证明存在，且广泛应用于数据挖掘的任务中[15]。数据对象的势能可以反应数据空间中数据点的分布，若使用相同的参数，在高密度区域的数据点具有高的势能，而稀疏区域则具有较低的势能[16]。许多基于数据场的算法被开发出来，运用在各个领域。为了计算势能，一定要用到势能函数。计算势能的函数有很多，例如：高斯核、指数核、截断核以及重力核，这里采用高斯核函数。在数据场中，数据簇中心点聚合了数据簇中所有势能，具有势能最大值。

数据点xi与数据点xj之间的作用力，使用势能函数：

(1)

式中：σ是影响因子，对最终的势能分布有影响，根据此公式，可以计算出势能矩阵P。

定义3距离数据点xi的最近的r个数据点称为其邻近点，则xi的聚合能量Ei为邻近点与它的势能总和。1

(2)

原DC算法采用欧氏距离计算两点间相似度，并定义相似度矩阵，数据点的聚合能量则是其近邻点的相似度总和。

1.2 基于数据场的聚类

从数据场的概念中可以看出，具有低势能的数据点相比于高势能的数据点更有成为簇成员的可能性。在数据场模型中，如果想要成为簇中心点的数据，则这些数据点必须具有足够远的距离。若存在数据点之间离得很近的情况，则会有两种情况，其中一个数据点成为簇成员点，或者两者都成为簇成员点。在这些数据点中，必须通过淘汰选择的方式竞争出更有可能称为簇成员的那个点，从数据集中决出非簇中心点。这种淘汰竞争的方式称为数据竞争。

存在数据集X={x1,x2,…,xn}，其中含有K个簇，n个数据点，dij为数据点之间的距离，D为数据集的距离矩阵。通过局部最小距离(LMD)选出参与数据竞争的数据点对。通过对距离矩阵D进行升序排序，得到首列为0的矩阵D′,如下所示：

(3)

若xz是数据集X中存在的唯一离群点，且第一轮的数据竞争次数为n,所以第一轮第n次竞争势必要为xz与其他某个非离群点的竞争，同时定会将xz标为数据簇的成员点，这也是采用局部最小距离方法的优点之一。采用局部最小距离，可以有效地阻止离群点成为数据簇的中心点，即对离群点不敏感。

当数据簇中的成员点的数目到达n-K时，到达数据竞争的结束条件。而剩下的K个数据点，则为聚类中心点。

2 DPEC算法的缺陷

聚类是一种无监督的学习，而不同的数据集分布、数据集的结构以及数据集的维度都是不同。基于数据集的这些特点，可以提取其携带的先验信息，利用这些信息可以提高聚类的效果。

DPEC算法通过数据势能竞争选出具有最大聚合能量的K个点，这些点只能作为最有可能的簇中心点。而算法存在一些问题，对密度分布不均匀的数据结构很难识别。密度分布不均匀的数据结构指的是数据结构中存在一些簇，这些簇的密度与其他簇具有明显的差别。数据结构密度不均匀分布将导致数据场势能分布不均匀，因此数据场中则会出现多个具有高势能的峰值点，这些点也就是具有高聚合能量的点。数据结构中密度的分布不均匀，将导致数据场中同一个区域出现多个峰值势能点，即可能出现如下情况：

(1) 除了明显的高势能点，一些具有较低势能但是具有相对较远的距离的点都有可能是簇中心点，这些点很容易被忽略。采用数据势能竞争只考虑到了聚合能量最大的点，将导致簇中心点的错误选取。

(2) 若数据场中的同一区域中出现多个势能峰值点，即具有最大聚合能量的K个点中，有多个出现在同一簇中，则将导致一个簇被错误划分为多个簇的情况。

当数据结构中存在较多簇，或者需要选取多个聚类中心点时，比较容易出现上述错选的情况。由此可以看出，DPEC算法同样存在缺陷，虽对离群点不是很敏感，但是对聚类中心点比较敏感，容易出现错选的情况。针对不同的数据集，尤其是复杂的数据集。因此有必要描述数据集自身携带的信息，考虑数据集的分布特点，也就是从全局特征来考虑。针对数据集存在的这些问题，可以设置一个最优截断距离，同时不同的数据集对应着不同的截断距离，将在下面说明如何选取。

3 优化DPEC算法

3.1 最优截断距离

为了克服DPEC算法对密度分布不均匀的复杂数据集难以识别的缺陷以及簇中心点错选的情况，可以设置一个截断距离。为了能够适应更多更复杂的数据结构，截断距离的设置有必要具有灵活性，也就是不同的数据结构对应着不同的截断距离。

对于不同的数据结构，仅仅凭人为经验来选取是不可取的，截断距离的选取对最终的聚类结果影响很大。相同的数据集，如果由不同的用户根据经验估计，聚类结果可能是不同的。对于不同的数据集，相同的用户可以评估出不同的截断距离。为了能够客观地选取出最优的截断距离，通过使用数据场的势能熵从原始数据集中自动提取截断距离的最优值的方法。数据集中密度的分布可以用势能分布来表示，同样通过密度计算截断距离方式可以转为使用数据场中势能函数的影响因子σ来确定。

在高密度的区域存在高势能，低密度的区域存在低势能。根据数据场的原理，若势能分布不均匀，则不确定性最小[15]。而数据的不确定性通常可以用熵来表示，因此，本文使用熵来优化影响因子σ。

对于数据集X={x1,x2,…,xn}，计算每个点的势能{p1,p2,…,pn}，这里使用式(1)计算可以得到，即势能矩阵中已计算。熵的计算公式为：

(4)

式中：Z=∑pi为归一化因子。

当σ从0增长到∞的时候，熵的值首先迅速下降，然后缓慢增加，最后保持稳定。当熵达到最小时，此时的σ为最优值，如图1所示。

图1 最优截断距离的选取

3.2 簇中心点的优化

由于复杂结构的数据集的密度分布不均匀，导致DPEC算法选出具有最大聚合能量的K个簇中心点可能不具有代表性，有必要对选出的簇中心点进行再次优化以及重新选择。

通过进行数据势能的竞争，将数据点根据势能大小将高能量点放在前面形成降序队列，会发现竞争后的势能点会出现两级分化，具有高势能的点与绝大多数低势能点之间存在一个临界点。将临界点前的势能点视为潜在簇中心点，而这些潜在簇中心点的数量势必大于K，所以有必要确定临界点。临界点的定义如下：

g=max{i|||ki|-|ki+1||≥λ,i=1,2,…,n-2}

(5)

λ=α(j)/n-2

(6)

(7)

式中：ki表示第i个数据点与第i+1个数据点之间的斜率；α(j)表示P′中相邻两点间斜率差的总和；λ表示P′中相邻点的斜率差的平均值，当数据点间的斜率大于等于λ的所有点中，p值最小的点为临界点。潜在簇中心点定义如下：

定义6潜在簇中心

pc={i|p′≥p′g,i=1,2,…,g}

(8)

将临界点前的潜在簇中心点进行筛选，将具有最大聚合能量的潜在簇中心点视为默认实际簇中心点。将默认的实际簇中心点，找出与实际簇中心点i最近距离的潜在聚类中心点j,计算两个点的距离MinDist(i,j)。若MinDist(i,j)>dc，则将点j视为新的实际簇中心点；若MinDist(i,j)

定义7准则函数

(9)

4 K-DPEC算法

4.1 K-means算法

K-means算法是属于划分方法中基于数据相似性度量的间接聚类算法，又称K-均值算法。该算法将数据集X中的数据划分为k个簇，划分的同时采用准则函数来评估聚类的质量，目的是使得簇内数据对象具有高相似度，簇间数据对象具有低相似度。算法步骤如下：

输入:

•k:簇的数目

•X:包含n个对象的数据集

输出:k个簇

步骤:

(1) 从X中随机选择k个数据对象作为初始簇中心点；

(2) Repeat；

(3) 根据簇中对象的均值，将每个数据对分配到最相似的簇；

(4) 更新簇均值，即重新计算每个簇中对象的均值；

(5) Until不再发生变化。

4.2 K-DPEC算法思想

为了增强K-means算法准确选取聚类中心点以及处理复杂数据集的能力，提出了一种数据势能竞争的K-means(K-DPEC)聚类算法。算法是这样考虑的：将数据竞争(DC)算法进行了改进与优化，引入了数据场的概念，利用数据点的势能竞争出簇中心点，提出了一种DPEC算法。同时，DPEC仍然存在缺陷，为了进一步准确选取簇中心点以及处理复杂数据集，采用势能熵提取了数据集的截断距离。因截断距离的选取是从数据集的全局考虑，利用了数据集的先验信息，同时结合临界点的定义准确地选取出了簇中心点。最后将簇中心点作为K-means算法的初始簇中心点，将剩余的数据成员进行了数据划分，直到准则函数的值不再发生变化，结束聚类。

算法步骤如下：

输入：数据集X={x1,x2,…,xn}，簇的数目k

输出：k个簇C={c1,c2,…,ck}

步骤1利用势能熵确定影响因子σ并计算截断距离dc。

步骤2计算数据集的欧氏距离矩阵，根据式(1)计算数据点任意两点之间的作用力，得到势能矩阵。

步骤3根据势能矩阵利用式(2)计算出各数据点的聚合势能。

步骤4依次选取两个数据点，利用局部最小距离法进行竞争，将聚合能量最大的点放在队列队首，形成降序队列。

步骤5根据队列数据点的势能分布特征，利用式(5)计算斜率并确定临界点，临界点前的点视为潜在簇中心点。

步骤6根据截断距离，筛选出实际簇中心点。

步骤7使用K-means算法将步骤6得到的簇中心点设为初始簇中心点，将其余非簇中心点迭代划分，并重新计算各类簇的簇中心点以及聚类误差平方和。

步骤8利用新的簇中心点重新聚类，计算聚类误差平方和。

步骤9当准则函数的值不再发生变化，结束聚类。否则，重复进行。

5 实验结果与分析

为了验证K-DPEC算法的性能，实验数据集使用人工数据集与UCI数据集分别进行仿真实验。实验环境：Matlab R2013a开发，处理器Intel(R) Core(TM) i7-4710MQ，主频2.50 GHz，内存8 GB，操作系统为Windows8 64位。

5.1 人工数据集

K-DPEC算法利用势能熵进行最优截断距离的选取，实验中使用Flame、Spiral、Jain、Compound以及Pathbase人工数据集进行展示，数据集描述如表1所示。

表1 人工数据集描述

K-DPEC算法通过对人工数据集提取最优影响因子σ，如图2-图6所示，参数设置如表2所示。

图2 Flame数据集最优σ选取

图3 Spiral数据集最优σ选取

图4 Jain数据集最优σ选取

图5 Compound数据集最优σ选取

图6 Pathbased数据集最优σ选取

数据集影响因子σ熵值H截断距离dcFlame1．499012．227851．9294Spiral2．998902．287802．5971Jain1．001402．259500．8672Compound2．497802．287102．1632Pathbased1．389972．275111．2037

为了直观地显示算法在人工数据集上的效果，给出了在Flame数据集上的聚类效果。

从图7至图9，展示了DC算法、K-means算法以及K-DPEC算法在数据集Flame上的聚类效果。从图7可以看出DC算法的聚类效果要好于图8中K-means算法的聚类效果，而图9中K-DPEC算法又优于DC算法的聚类效果，主要表现在两簇交界处，这取决于截断距离选取的优劣。K-DPEC算法通过对数据集的分布情况，利用势能熵提取出最优截断距离，对处理非球状簇等复杂数据集具有很好的效果。

图7 DC算法在Flame数据集的聚类效果

图8 K-means算法在Flame数据集的聚类效果

图9 K-DPEC算法在Flame数据集的聚类效果

5.2 UCI数据集

UCI数据库为加州大学欧文分校提出的用于机器学习的数据库，数据库中的数据集被用来测试机器学习以及数据挖掘算法，且数据库中的数据集都有确切的分类。UCI数据集描述如表3所示。

表3 UCI数据集描述

为了对聚类结果进行评价，实验采用常见的F-measure指标评价方法。

F-measure指标是通过算法的准确率(Precision)与召回率(Recall)得到。类i与簇Ck的准确率与召回率如下：

式中：Nik代表类簇k中类别为i的数量；Nk代表类簇k中的样本的数量；Ni代表类别为i的样本数量。

F-measure计算公式如下：

式中：α为参数，此公式为准确率(Precision)与召回率(Recall)的加权调和平均。

当α=1时，则为评价聚类结果最常用的F1，公式如下：

数据集整体聚类划分的F-measure的值则为：

式中：T为数据集真实的类簇集合，N为数据集中样本数据的总数，C为算法聚类后得到的类簇集合，F-measure指标数值越大，则表示算法聚类越准确。

图10给了DC算法、K-means算法以及K-DPEC算法的三种聚类算法在UCI机器学习数据集上聚类结果的F-measure指标。

图 10

图10展示了3种算法在6个UCI数据集上的F-measure指标的对比。从图中可以看出K-DEPC算法在UCI数据集上的F-measure指标均好于DC算法与K-means算法，特别是在ionosphere数据集与ecoli数据集上的F-measure指标，得到了大幅的提升。

6 结 语

本文算法针对K-means算法随机选取簇中心点及难以处理复杂数据结构等弊端，提出了一种基于数据场的数据势能竞争与K-means算法融合的K-DPEC聚类算法。在K-means算法的基础上引入改进后的DC算法，利用势能代替原DC算法的相似度计算，并且引入势能熵的概念以及斜率的思想，在处理复杂结构数据集和确定聚类中心点上具有较强的能力。通过仿真实验，在人工数据集以及UCI数据集上的实验结果，证明了本文算法的可行性。

[1] Xu R,Wunsch D.Survey of clustering algorithms[J].Neural Networks,IEEE Transactionson,2005,16(3):645-678.

[2] Jain A K.Data clustering:50 years beyond K-means[J].Pattern recognition letters,2010,31(8):651-666.

[3] Park H S,Jun C H.A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications,2009,36(2):3336-3341.

[4] Zhou Y J,Xu C,Li J G.Unsupervised anomaly detection method based on improved CURE clustering algorithm[J].Journal on Communications,2010,31:18-23.

[5] Karypis G,Han E H,Kumar V.Chameleon:Hierarchical clustering using dynamic modeling[J].Computer,1999,32(8):68-75.

[6] Jing Yang,Gao Jiawei,Liang Jiye.An Improved DBSCAN Clustering Algorithm Based on Data Field[J].Journal of Frontiers of Computer Science and Technology,2012,6(10):903-911.

[7] Kalita H K,Bhattacharya D K,Kar A.A New Algorithm for Ordering of Points to Identify Clustering Structure Based on Perimeter of Triangle:OPTICS(BOPT)[C]//International Conference on Advanced Computing and Communications.IEEE,2007:523-528.

[8] Ansari S,Chetlur S,Prabhu S.An Overview of Clustering Analysis Techniques used in Data Miniing[J].International Journal of Emerging Technology and Advanced Engineering,2013,3(12):284-286.

[9] Amini A,Wah T Y,Saybani M R.A study of density-gridbased clustering algorithms on data streams[C]//Fuzzy Systems and Knowledge Discovery(FSKD),2011 Eighth International Conference on.IEEE,2011,3:1652-1656.

[10] 施培蓓.数据挖掘技术中聚类算法的研究[D].江南大学,2008.

[11] Lu Zhimao,Zhang Qi.Clustering by data competition[J].Science China Information Sciences,2013,56(1):1-13.

[12] 苏辉,葛洪伟,张欢庆.密度敏感的数据竞争聚类算法[J].计算机应用,2015,35(2):444-447.

[13] Zelnik-Manor L,Perona P.Self-tuning spectral clustering[J].Advances in Neural Information Processing Systems,2004,17:1601-1608.

[14] Li D,Wang S,Gan W,et al.Data Field for Hierarchical Clustering[J].International Journal of Data Warehousing & Mining,2011,7(4):43-63.

[15] Wang S,Wang D,Caoyuan L I,et al.Clustering by Fast Search and Find of Density Peaks with Data Field[J].Chinese Journal of Electronics,2016,25(3):397-402.

[16] Wang S,Fan J,Fang M,et al.HGCUDF:Hierarchical Grid Clustering Using Data Field[J].Chinese Journal of Electronics,2014,23(1):37-42.

[17] Barany I,Vu V H.Central limit theorems for Gaussian polytopes[J].Annals of Probability,2006,35(4):1593-1621.

CLUSTERINGALGORITHMFORCOMPETITIONOFDATAPOTENTIALENERGYANDK-MEANSBASEDONDATAFIELD

Xu Jia’nan Zhang Guizhu

(SchoolofIOTEngineering,JiangnanUniversity,Wuxi214122,Jiangsu,China)

The K-means algorithm uses the Euclidean distance to divide the data points, cannot accurately characterize the data set, and randomly select the clustering center point mechanism, and cannot get good clustering results. In this paper, a clustering algorithm based on data field-based data potential competition and K-means algorithm is proposed. In this algorithm, the concept of data field is defined, and the local minimum distance is used to compete the potential of data aggregation. The optimal truncation distance based on the distribution of data set is extracted by using potential energy entropy. The cluster center point is determined according to the truncation distance and slope, and the K-means clustering is realized. The results of the UCI dataset show that the fusion algorithm has better clustering results.

Data competition Data field Potential entropy Slope Complex dataset

2017-03-21。江苏省自然科学基金项目(BK20140165)。许家楠，硕士生，主研领域：数据挖掘。张桂珠，副教授。

TP18

A

10.3969/j.issn.1000-386x.2017.12.051