基于密度的K-means初始聚类中心点选取算法

李 波 管彦允 龚维印 韦旭勤 薛 端

（六盘水师范学院数学与计算机科学学院 贵州六盘水 553000）

聚类算法在目前数据挖掘领域使用非常广泛的算法，其中基于划分的聚类算法是聚类算法中非常重要的一个分支[1]，其算法核心思想是计算每个目标数据与聚类中心点的距离，把该数据点划分到离其最近的聚类。K-means算法是由J.B.MacQueen[2]提出的一种基于划分的聚类算法，由于该算法简单、有效，能快速把大量数据集划分到正确的聚类中[3],因此K-means聚类算法目前依然在数据挖掘领域占用非常重要的地位[4]。虽然经典K-means算法高效简单，但也存在一定的局限性：如果数据存在分布不均匀或存在离群点的情况，经典K-means算法会因为算法初始化时随机选择K个聚类中心导致出现聚类效果不佳和聚类差异性很大的情况[5]。

近几年国内外很多学者针对K-means算法的不足提出了大量的优化和改进策略。Elad M等人[6]提出基于距离和密度的方式查找聚类初始中心点。X Liu等人[7]提出通过计算每个点的距离，选择距离最大的点作为聚类初始中心点。Huang等人[8]提出了一种特征值加权的K-means算法，通过不同的权重在迭代过程中选择中心点。周本金等人[9]提出了通过方差方式选择初始聚类中心，解决聚类结果的不稳定问题优化K-means聚类。左进等人[10]提出了通过密度剔除离散点,选择密度均匀点作为聚类中心，该方法解决初始点的选择随机性导致聚类不稳定。ZHU E Z等人[11]提出选择高密度数据点作为聚类初始中心点，但是数据集中有离群点的情况下算法效果不佳。郭永坤等人[12]提出高密度优先聚类算法，针对密度差异大的数据集效果理想，同时增加聚类稳定性,但未考虑离群点。Aharon M等人[13]提出了自动获取最佳K值的算法，该方法在K值变化范围很大时效果表现不佳。Chen Z等人[14]提出一种基于数据点最大距离算法，该方法通过聚类自动计算最优K值，但聚类初始点的随机性导致算法的不稳定性。

针对K-means算法存在的聚类初始点的随机性和不稳定性，本文认为数据点密度大的点才应该是真实的聚类中心，根据这一思路提出了一种改进算法，算法首先分析数据密度分布，定位数据密度最大的K个点作为聚类初始中心点，从而可以解决分布不均匀数据和离群点导致的聚类不稳定性问题增加聚类稳定性，同时使算法快速收敛减少迭代次数。实验结果表明，针对分布不均匀或存在离群点的数据集，本算法也能快速收敛，算法稳定性和正确性也比较高，从而充分说明了本算法的高效性和合理性。

一、改进K-means算法

（一）经典K-means算法。经典K-means算法基本思想：第一步，人工确定聚类个数，算法根据聚类个数随机选择K个聚类初始中心点。第二步，计算每个数据点到K个聚类中心点的距离，根据距离把每个数据点划分到离该数据点最近的一个聚类中去。第三步计算出新生成的K个聚类中心点。重复执行上述的第二步和第三步，直到算法满足结束条件，生成K个最终聚类，算法结束。

（二）基于密度改进的K-means初始中心点聚类算法。通过λi定义可以看出，Ai越小表示数据点Xi以MeanDist(D)为半径的聚类平均距离越小,反映出Xi点附近的数据点比较密集,ρ(i)越大同时也反映出Xi点附近的数据点比较密集,因此λi可以很好的展现出数据集D的密度分布特征。

第一步，初始数据集U={}，选择λi最大的点Xi（即选择密度最大的点）作为第一个初始中心点,把以Xi点为中心以MeanDist(D)为半径包含点作为第一个聚类U1,这样就能选出密度最大的聚类，把U1加入U。从数据D中删除包含U的数据点，重新计算λi，按照上述规则直到计算出k个集合或者max（ρ(i)）＜K/4n，生成U2…UK（K表示聚类个数）。

第二步，计算数据集合Ui中每个数据点的簇内误差平方Ei，选择Ei最小的点作为该聚类的初始中心点Ki，通过该方法选出来的初始聚类中心有效的减少迭代次数,可以避免孤立点、噪点的影响。

（三）算法流程。基于以上思想，可以准确的确定K个密度最大的真实中心点，屏蔽离群点对算法稳定性的影响，改进后K-means算法流程如下所示：

输入：数据集D{x1,x2,…,xn},假设聚类个数为K

输出：K个聚类

Step1：初始数据集U=Ø，计算数据中任意两个点Xi、Xj的距离d(xi,xj),计算结果保存在矩阵Dist[n][n ]中,同时计算出数据集D的平均MeanDist(D)。

Step2：遍历Dist[n][n]求出所有样本点的密度ρ(i),同时计算出数据点xi的簇类平均距离Ai和参数λi。

Step3：选择λi最大的数据点，计算与xi距离d（xi,x）j小于等于MeanDist(D)的数据点xj加入到集合U0中。

Step4：从数据集D中删除数据点xi，xiϵU。

Step5：重复上述 Step1到 Step4，直到|U|＜=K 或者max（ρ(i)）＜K/4n。

Step6：遍历U中的每个数据集，求出每个Ui数据集中Ei最小的数据点作为簇类初始中心点。

Step7：采用经典K-means算法，输出结果。

二、实验结果及分析

（一）实验环境和数据集。本算法在处理器Intel（R）Core（TM）i5-1135G7@2.40GHz，内存为 16.00GB，Microsoft Windows10的操作系统机器运行，算法运行环境为Python3.7。本算法中采用的是UCI下载的数据集,UCI是加州大学提出的一个专门用来测试聚类效果的标准测试数据集[15]。本实验选取UCI上三个维度信息差异较大的数据集来验证算法的效果，通过改进算法和经典聚类算法对数据进行聚类,可以很好的说明本算法对在不同维度和不同数据集都可以表现非常好的性能。具有详细数据集特征见表1。

表1 数据集详细信息表

（二）实验结果。本文采用聚类算法常用的准确率和评价函数值（总的误差）作为评价聚类结果好坏的关键评价指标。评价函数值计算如公式8,大部分文献都将评价函数作为判断聚类效果的标准,其值越小效果越好。精准率是指预测分类样本个数和实际分类样本的比例，值越大表示正确分类的数据越多，表示算法效果越好。

准确率计算公式如下：

其中Ci是聚类i中数据样本个数，C’i是表示通过算法预测为聚类i中样本数据个数。

本次实验,使用UCI三个数据集Iris、Wine和Breast对K-means经典算法、K-means++和本文算法进行测试，为了排除随机性对算法的影响，取三个算法在上述数据集测试的平均值作为结果。表2为三个数据集在三种算法中准确率和评价函数值的平均值。

表2 聚类结果稳定性和准确性比较

（三）实验分析。通过实验结果可知,K-means经典算法在数据集分类类别和数据集属性数量增加的情况下,聚类的准确率下降明显。本次实验采用UCI网站3个数据集使用经典算法和本算法来进行测试，实验采用准确率和评价函数值作为聚类结果的评价标准。三种不同的聚类算法在Iris指标最好，在Breast数据集指标最差，主要原因在于Breast数据集的聚类个数和数据维度较Iris数据集有明显的增加。本算法通过改进传统的K-means算法随机产生三个聚类初始点，由于初始聚类中心的选择会决定算法的迭代次数和聚类效果，如果初始聚类点选择了离群点将会导致准确率的下降。本论文通过数据密度和距离等条件能够快速有效地找到密度最大的K个初始点作为聚类中心点。通过实验结果可以证明本算法确定的初始聚类点，能够快速让聚类算法收敛，减少迭代次数和保证聚类效果的稳定性。通过表2可以看到针对三个数据集，本算法对传统的K-means经典算法准确率都有一定的提升。综上所述，本论文的改进算法是有效和可行的，在准确率方面有了很大的提升，同时与其他算法相比评价函数值也有一定的优越性。

三、结语

传统K-means算法高效且简单，是目前聚类算法中使用非常广泛的算法，但是由于传统算法随机动态的选择聚类初始中心，特别是数据分布不均匀或数据出现离群点的情况下，这样会导致聚类的不稳定性，增加聚类迭代次数。本论文提出的算法能够快速定位真实数据分布中聚类密度大的中心点作为K-means算法初始点，解决了K-means算法的不稳定性和离群点对算法的影响。通过实验结果可知，改进后的算法确定的聚类初始中心点较接近真实聚类中心点，能够减少算法迭代次数，提升聚类准确率，从而证明本算法的真实有效。本改进算法使用UCI网站的小型数据进行测试和验证，在数据维度和数据集都比较大得情况，如何降低算法复杂度，进一步提升聚类准确性，将是下一步需要解决的问题。