基于网格密度的K—均值算法簇中心点识别的研究

刘利康

摘 要：传统的K-均值聚类算法只能通过人工参数设定K值和初始簇中心点，而人工方式选择的K值和初始簇中心点往往有较大偏差，直接导致错误的分簇结果.基于上述问题，本文提出了一种基于网格和密度的K值与最佳初始簇类中心自动识别的方法。经理论和实验证明，该方法在很大程度提高了聚类结果的质量和算法的效率。

关键词：K-均值 网格聚类 簇中心点 密度峰值

一、引言

K-均值算法是目前聚类分析算法中应用历史较久、范围较广泛的一种。传统的K-均值以平方误差准则较好的实现了空间聚类，对处理大规模数据集有较大优势。但K-均值太依赖于K值、初始簇中心点的设定。由于大多数情况下，聚类数K和簇的大致中心位置无法事先确定，因此需要通过优化算法对聚类数K和最佳初始簇中心点进行估计。但对于如何确定K和各个簇中心的位置范围，目前尚无明确的理论指导，本文则针对此问题展开讨论。

本文结合K-均值算法和网格、密度算法的优点，提出一种新的K-均值算法中K值和最优初始簇中心点自动识别的方法。经过理论和实验分析验证了该方法可以通过计算分析自动给出K值和较佳的初始簇中心点，很大程度改善了K-均值需要人工设置参数的问题，有效提高了聚类精度和效率。

二、典型基于划分方法—K-均值算法

k-均值算法由J.B.MacQueen于1967年提出[4]，是经典聚类算法之一。近几十年来被广泛应用于生物统计、图像处理、信息检索、客户分类等各领域。针对该算法的完善、改进和扩展，人们做了大量的长时间研究工作。

设待分析数据集合D的属性数为d，数据对象数量为N，以欧式距离作为数据对象的差异程度的度量，则D可看作d维欧式空间Rd中的数据点集。设每个数据点为Xi，则D= {Xi，i=1，2，...，N}。

k-均值算法以k为参数，其核心思想是将N个数据点分为k个簇，使得每个簇中的数据点到该簇中心点的平方和最小，算法的流程如下：

1.从N个数据点中任意选取k个作为初始的簇类中心点；

2.分别计算每个数据点到各簇中心点的距离，以最近邻原则，将该数据点分配到距离最近的簇中；

3.所有数据点分配完毕后，重新计算k个聚类的中心位置；

4.与前一次计算所得的k个聚类中心点的位置比较，若中心点位置变化的程度小于某阀值（即准则函数收敛），那么算法结束；否则转步骤2继续执行。

k-均值算法的优点包括：执行效率高、伸缩性强、设计思路简单明了等。但同样k-均值算法也存在着一定缺点，主要有：

1.算法擅长处理球状簇的数据集，对于任意形状的数据往往效果较差；

2.算法的k值需要人工指定，而这个k值是很难估计的。很多情况下，我们事先并不知道数据集应该分为几类；

3.算法的初始簇中心点是随机选取的，选取点不同，结果也可能不同，这种依赖性导致聚类结果的不稳定。且k-均值算法常采用误差平方和准则函数作为聚类准则函数，导致结果容易陷入局部最优，难以获取全局最优解；

4.算法需要不断计算调整后的新的簇中心位置，然后不断对数据点的分簇进行调整，因此在数据量大时，时间开销非常大；

5.对噪声点和孤立点敏感。

本文针对k-均值的k值和初始簇中心点的依赖性问题，提出一种通过网格化方法自动确定k值和选取最佳初始簇中心点的新思路，在此基础上给出了改进的K-均值算法。

三、利用网格的贡献值进行网格划分

为便于空间定位和网格统计量的计算，改进的算法先对数据作归一化，然后采用均匀划分方法。设每一维上划分长度相同的P个区间，则划分产生Pd个网格。那么P值该取多大呢？这里引入网格贡献值的概念来获取最佳的网格划分。

我们将网格看做盒子，网格中的数据点看作盒子中的小球，则最均匀的状态是一个盒子装一个球，这时数据集没有簇产生，聚类没有意义。但该状态是小概率事件，现实中几乎不可能出现。实际上数据分布往往是不均的，一个盒子可能装好几个球，也可能是空的。

我们在盒子和球的数量一一对应的条件下考察二者的关系。一个盒子是空的意味着另一个盒子多一个球，空盒子越多说明另外有盒子装得越满，分布越不均匀，聚类越容易，因此对聚类的贡献越大。另外换个角度看，盒子装得越满，说明空盒子变的更多，有球的盒子之间的空盒子越多，空隙越大，聚类变容易，对聚类的贡献也越大。

自然的引入單元网格贡献值的概念，用C表示。容易想到将包含数据点数为1（基数为1）的单元网格贡献值设0。因为均匀状态的单元网格基数全部为1，对形成密度差没有任何贡献。直观上看，一个盒子一个球是常态，正常情况应该就是这样，谈不上贡献。把球从一个盒子拿到另一个盒子的运动为改变常态做了“功”，这里称为“贡献”。使状态偏离常态越远，“贡献”就越大。

描述贡献值最简单的方式将贡献值函数设置为线性函数C=|n-1|，将空盒子的贡献值设为1，基数为1的盒子设为0，基数大于1的盒子设为n-1。为更符合贡献值的变化曲线，一般采用Sigmoid核函数的变化形式进行描述：

称基数为n的网格为n-网格，则n-网格的贡献值为S（|n-1|）。这里将1-网格称为临界网格，易知当网格划分和临界网格确定后，全部网格的贡献值总和越大，簇之间的空隙越大，类别特征越明显。

我们称基数大于临界网格的网格为稠密网格，基数小于或等于临界网格则称为稀疏网格。临界网格也可选择基数为2，3，…，n的网格担当，实践证明，在数据量较大的时候，基数在1到4之间选择常得到聚类效果佳的划分。文中我们设临界网格为1-网格，即网格数尽量与数据点数一致。令hd=N，则每一维划分数P=[h]，这里为提高聚类效率，让P向下取整。

确定P值之后，将每维划分成P个小区间，由于数据已归一化，于是每维的取值范围为[0，1]，为保证每个数据点落到唯一的网格中，设第1个划分区间为闭区间，其他情况下为左开右闭区间，…，。然后遍历数据点集，将数据点依次放入所属的网格中，并统计网格基数。遍历完成后，将稠密网格按基数降序排序生成稠密网格降序列表G。