基于密度优化初始聚类中心的K-means算法

王艳娥，安 健，梁 艳，康晶晶

(1.西安思源学院 理工学院，陕西 西安 710038；2.西安交通大学深圳研究院，广东 深圳 518057；3.山西农业大学 信息学院，山西 晋中 030800)

0 引 言

聚类是数据挖掘中一种无监督学习分析数据的方法，基于“物以类聚”的思想，根据相似性原则将相似性较高数据划归同一类，相似性较低数据划分为不同类[1]。聚类分析的无监督特性，使聚类在医疗诊断、交通检测、图像处理、环境检测和大数据等方面得到广泛的应用。聚类分析方法可分为：基于划分式、基于网格、基于密度、基于层次和基于模型等五种类型[2-3]。

1 K-means算法和研究现状

1.1 K-means算法

K-means算法[4]核心思想是随机选取k个样本作为初始聚类中心，以欧氏距离作为相似度指标，两个样本之间距离越远相似性越低，距离越近相似性越高，通过不断迭代聚类中心，将相似性高的样本划分为同一类，相似性低的样本划分为不同类。K-means具有明显的缺陷：(1)需随机选择初始聚类中心；(2)对噪声数据和异常点比较敏感；(3)需提前指定划分类数，使得聚类结果常陷于局部最优。因此关于K-means算法的优化，现有文献和相关学者主要是从这三方面展开。文中算法主要研究的是初始聚类中心的选择和噪声数据。

1.2 K-means算法研究现状

为了解决K-means算法的缺陷，众多学者提出了基于密度优化的解决方案。文献[5]通过准则函数确定样本集的最佳聚类数，基于密度选择初始聚类中心，在一定程度克服了K-means算法需要预先输入类数和随机选择初始聚类中心的缺陷，聚类结果稳定，但在选择初始聚类中心时需根据经验输入样本邻域半径和最小样本密度两个参数使得算法的聚类结果缺少客观性；文献[6]算法划分出样本空间的高密度区域，在高密度区域选择距离最远的高密度样本作为初始聚类中心，但高密度区域仍需要人为输入样本邻域半径和最小样本密度，也使聚类结果受人为作用干扰大；文献[7]以最大最小距离法为基础，提出离积法的优化K-means，该算法克服最大最小距离法易导致聚类中心稠密问题，但最大最小距离法将样本空间划分为高密度区域和低密度区域需要人为输入两个参数，这缺点文献[7]并没有克服；文献[8]提出噪声点优化K-means算法，在剔除噪声点需要根据经验设定两个参数：样本集最佳噪声样本数和判断样本是否为噪声样本的距离调节系数；文献[5-8]手动输入参数需要历史经验，聚类结果受人为干扰较大，使算法的普适性受到限制。文献[9-10]提出将方差作为选择初始聚类中心的指标，选择数据集中方差最小且处于不同区域的数据对象作为初始聚类中心，该算法的聚类结果稳定，且对噪声数据具有一定的免疫性，但选择的初始聚类中心与数据集实际类中心存在差异，且没有考虑噪声样本在聚类过程中的影响；文献[11]使用平均距离作为计算样本密度的指标，在一定程度避免将噪声点作为初始聚类中心，但选择的初始聚类中心同样与样本集实际中心分布相差较大。

该文在研究上述算法的基础上，提出基于样本规模的最优超球体计算样本密度，使样本密度的计算具有一定的客观性，克服文献[5-8]根据经验输入参数的缺陷；文献[9-11]虽然确保初始聚类中心不会落在噪声样本，但导致密度最大的样本往往位于多个类的相交处，而不是数据集实际类中心。

2 基于密度去噪的K-means算法

2.1 DDK-means算法相关概念

设RP为待聚类的样本空间，含有n个样本的样本集D={xi∈Dp,|i=1,2,…,n}，样本空间可划分为k类，设k个聚类中心为数据集C={ci∈C|i=1,2,…,k}。文中算法采用欧氏距离来衡量样本相似度。距离越远相似度越低，反之相似性越高。

(1)样本xi距离均值dm(xi)如下：

(1)

其中，j=1,2,…,n，且i≠j，dist(xi,xj)为样本xi和xj的距离。

(2)样本集的均方差msd如下：

(2)

(3)样本集的超球体v的函数表示如下：

v=πR3

(3)

其中，R=μ*msd，μ为调节系数，初始值等于1。v的大小应该与样本集n的大小和类簇数k相关。假设样本集中所有样本被均匀分配给k个类，那么每个类中应包含样本的个数n/k，考虑到噪声数据，规定每类样本的个数必须小于n/k，实际上不管样本集中的样本是否均匀分配给k类，通过规定超球体内样本个数不超过n/k都能计算出每个样本的最佳μ和最佳局部密度。

(4)样本xi的密度函数density(xi)如下：

(4)

从式(4)可以看出，density(xi)值与ρ(xi)密切相关，当ρ(xi)的值越大说明落入以xi为中心的超球体的样本越多，样本xi越接近类中心。当ρ(xi)相同时，超球内样本与xi距离越近，距离均值越小，该类样本密集度越高，则xi越接近高密集区域的类中心。作为样本xi的密度density(xi)的值越大，xi成为初始聚类中心的权重越大。

(5)样本集的密度值meanD表示如下：

(5)

(6)样本集聚类误差平方和SSE表示如下：

(6)

2.2 DDK-means算法原理

均方差在概率统计中用于测量样本集的分布程度，对于数据集可以通过均方差测量数据集的整个离散程度，当均方差的值越大说明数据集越分散，均方差越小数据集越集中。文中以均方差作为计算最优超球体的基础，将整个聚类分为两个阶段：第一阶段计算每个样本的局部密度。在大小相同的超球体内，某个样本的超球体内样本个数越多，则说明该样本处于高密度区域，作为初始聚类中心的权重就越大。根据式(3)计算所有样本的局部密度，当多个样本的超球体内的样本数相同时，则某个样本的超球体内样本紧密度起作用，越紧密，样本的密度越大，样本作为初始聚类中心的权重越大。当各个样本的超球体内的样本数不同时，则超球体内的样本数起作用，样本的超球体内样本数越多，样本密度越大，该样本作为初始聚类中心的权重越大。

第二阶段根据密度选取最佳的聚类中心，完成整个样本集的划分。选择大于样本集平均密度的样本作为初始聚类中心的候选集，同时在非初始聚类中心候选集中选取样本密度较低的样本作为噪声样本，将整个样本集划分为非噪声样本集和噪声样本集；接着在候选样本集中同样以均方差作为基础，通过可控的伸缩尺度调节样本的距离，选出k个密度较大且处于不同密度区域的样本作为初始聚类中心，然后对非噪声样本集进行聚类，完成非噪声样本的划分；最后对噪声样本集中的样本，根据它们与k个中心的相似度，将噪声样本划分给对应的类。

2.3 DDK-means算法实现

根据DDK-means算法原理，算法实现步骤分如下两步：

第一步，算法1：根据新定义的样本密度，将初始样本集划分为初始聚类中心候选样本集、非初始聚类中心候选集、噪声样本集和非噪声样本集。求解样本密度的算法描述如下:

输入：xi，{xi∈D|i=1,2,…,n}，D为样本集；k；密度调节系数μ=1；初始聚类中心候选集D1=φ；非初始聚类中心候选集D2=φ；非噪声数据集D3=φ；噪声数据集D4=φ。

输出：n个样本的密度、D1,D2,D3和D4，其中D1∪D2=D,D1∩D2=Ø，D3∪D4=D,D3∩D4=Ø。

第1步：根据式(1)、式(2)计算样本集的均方差msd。

第2步：根据式(3)计算样本集的超球体。

第3步：根据式(4)计算每个样本的密度。如果样本的最大密度远远小于n/k，转到第2步，增大式(3)中的μ的值，重新计算超球体，使得超球体内样本个数增大，增大到刚好小于或等于n/k，转到第4步。如果样本最大密度远远大于n/k，转到第2步，减少式(3)中μ的值，重新计算超球体，使得超球体内样本个数减少，减少到刚好小于或等于n/k，转到第4步。

第4步：计算样本集的密度meanD。

第5步：构造初始聚类中心候选集D1，{xi∈D1|density(xi)>meanD,i=1,2,…,n}，非初始聚类中心候选集D2=D-D1。

第6步：构造噪声数据集D4和非噪声数据集D3。其中D4=ρ*D2，0≤ρ≤1，即在D2中选择样本密度最小的前ρ*|D2|样本作为噪声样本；构造非噪声样本集D3，D3=D-D4。

第7步：算法1结束。

第二步，算法2根据算法1的结果，通过不断调节不同聚类中心之间的距离，在初始聚类中心候选集中选择密度最高且处于不同区域的样本作为初始聚类中心。再根据选择的最优初始聚类中心，先针对非噪声数据完成聚类，再将非噪声数据划分到不同的类簇中，从而剔除噪声数据对聚类过程产生的影响。

算法2:具体实现的步骤如下：

输入：构造k空集合S1,S2,…,Sk，初始化为c1∈S1,c2∈S2,…,ck∈Sk；n个样本的密度、D1,D2,D3和D4。

输出：样本集的k个划分。

第1步：在D1中选择密度最大的样本作为第一个初始聚类中心c1。

第2步：在D1选择样本xi作为第二个初始聚类中心c2，xi满足dist(xi,c1)>msd。

第3步：在D1选择样本xr作为第r+1个聚类中心，xr满足条件dist(xr,c1)>msd/(r-1)&& dist(xr,c2)>msd/(r-1)&&…&& dist(xr,cr-1)>msd/(r-1)，其中2≤r≤k。直到选择出第k个初始聚类中心。

第4步：根据每个样本与聚类中心的距离将非噪声数据划分到K个类中，重新计算K个类的聚类中心。

第5步：根据式(6)，计算SSE，如果SSE发生变化转到第3步，否则转到第6步。

第6步：根据噪声数据与聚类中心的聚类，将噪声数据划分到K个类中，完成聚类。

3 DDK-means算法仿真实验

为验证文中算法的有效性，分别在乳腺癌数据集、UCI[12]数据库中常用的几个数据集以及人工数据集中进行测试，并与传统的K-means方法、文献[9,11]中的算法进行比较。所有算法的实验环境为：Win7操作系统、COREi5处理器、2G内存、Matlab R2012a处理软件。

3.1 实验数据集

3.1.1 乳腺癌数据集

用于测试的乳腺癌数据集为wdbc和breast-cancer-wisconsin。breast-cancer-wisconsin数据集包含699个样本(实际的病例数据)，其中16个样本有缺失属性，文中算法对缺失属性的样本采用丢弃的方法，最终数据集包含683个样本，其中444个样本为良性肿瘤，239个样本为恶性肿瘤。

3.1.2 UCI数据集和人工模拟数据集

为验证文中算法的普适性，在UCI数据库中选取机器学习用来进行测试的数据集进行验证，包括Iris、Wine、Ionosphere、Soybean-small和Seed数据集。

为进一步验证文中算法的合理性，生成包含不同噪声比的人工模拟数据集。关于人工模拟数据集高斯分布的相关参数如表1所示。

表1 人工模拟数据集各项参数

用于进行算法测试的人工模拟数据集包含6组数据集，6数据集各包含1 800个样本，类别数为3，每类簇包含600个样本，每类数据集按照不同的高斯分布生成。按照表1所示的各项参数生成含有不同噪声比的数据集，噪声比分别为0%，10%，20%，30%，40%，50%，其中噪声产生在第3类，噪声数据的标准差为4。

3.2 实验结果与分析

文中算法在乳腺癌数据集、UCI数据集和人工模拟数据集的测试结果分析，通过常用的聚类效果评价指标：聚类误差平方和、聚类时间、聚类准确率[13]、Rand index[14]、Jaccard coefficient[15]、Adjusted rand index[16]进行比较。传统K-means算法，随机选择初始聚类中心，聚类结果不稳定，

为加强K-means算法评价指标的稳定性，采取在测试数据集上重复执行K-means算法100次，K-means算法的各项评价指标是执行100次后的平均值。

为验证文中算法能够很好地克服以上算法存在的缺陷，将文中算法与传统K-means算法、文献[9,11]提出的算法进行对比。

3.2.1 乳腺癌数据集与UCI数据集聚类结果分析

K-means算法、文献[9]、文献[11]和文中算法在乳腺癌数据集和UCI数据集上的聚类误差平方和、运行时间如表2和表3所示。

表2 四种算法在UCI数据集上的聚类误差平方和比较

表2中加粗数据表示该算法的聚类误差平方和评价指标最佳。从表2中的实验结果数据可以看出，文献[9]、文献[11]在Iris和Ionosphere数据集的聚类误差平方和明显优于K-means算法，在其他数据集中与K-means算法相同；文中算法在乳腺癌数据集以及几个常用的UCI数据集中的聚类误差平方和均明显低于K-means算法、文献[9]和文献[11]；结果说明，文中算法能够将相似性高的样本划分为同一类，相似性低的样本划分为不同类，聚类的结果更符合数据集的原始分布。

表3是四种算法在样本集上运行时间比较。从表3可以看出K-means算法在聚类时间上明显优于文献[9]、文献[11]和文中算法，结果产生的原因是其他三种算法在选择最优的初始聚类中心时有一定的时间开销；但文中算法在运行时间上明显优于文献[9]和文献[11]，文中算法在对样本进行聚类时，减少反复聚类时的样本集规模，噪声样本并没有参与反复聚类的过程，当对非噪声样本完成聚类后，噪声样本一次性直接划分给相似性高的类；同时由于文中算法选择的初始聚类中心更接近样本集实际中心的分布，使得反复聚类的迭代次数减少，进一步降低了时间开销。

表3 UCI数据集四种算法聚类时间比较

图1是K-means、文献[9]、文献[11]和文中算法在乳腺癌数据集和UCI数据集上在聚类准确率、Rand index、Jaccard coefficient和Adjusted rand index参数指标的比较折线图。图1(a)中，文中算法在这几个数据集上的聚类准确率最优，K-means算法的聚类结果最差；图1(b)中，文中算法的Rand index明显优于其他三种算法，K-means算法的聚类效果最差；图1(c)中，文中算法的Jaccard coefficient均优于其他三种算法，而且在wdbc、Iris和Seeds样本集的优势明显；图1(d)中，文中算法的Adjusted rand index在wdbc、Iris、Wine、Seeds数据上明显优于其他三中算法，在breast-cancer-wisconsin和Ionoshpere数据上也具有一定的优势。

图1 四种算法在UCI数据集上的结果比较

通过在乳腺癌数据集和常用的UCI数据集进行聚类结果的比较，证明文中提出的优化DDK-means算法的聚类效果明显优于其他三种聚类方法，其中K-means算法的聚类效果最差，文献[9]和文献[11]的聚类结果相似，文中算法有效地克服了优化后初始聚类中心与样本实际类中心差异较大的缺陷。

3.2.2 人工数据集结果分析

在人工模拟数据集上对K-means算法、文献[9]、文献[11]和文中算法进行测试。除了在六种聚类效果评价指标进行对比外，对四种算法选择的初始聚类中心进行了比较，四种算法选择的初始聚类中心如图2所示。图2中黑白相间的圆表示不同算法在不同噪声比数据集中选择的初始聚类中心。

K-means算法的初始聚类中心是随机产生，初始聚类中心不稳定，图2中的K-means初始聚类中心是随机选取其中一次的结果；文献[9]、文献[11]和文中算法选择的初始聚类中心稳定。图2选取具有代表性的无噪声数据集、20%噪声数据集、50%噪声数据集，在这三个数据集上运行K-means算法、文献[9]、文献[11]和文中算法；图2(a)～(d)分别是K-means算法、文献[9]、文献[11]和文中算法在三个数据集中选择的初始聚类中心。图2(a)是K-means算法选择的初始聚类中心，随机选择的初始聚类使得初始的中心往往不够理想，不同类簇的初始聚类中心可能位于在同一类中，甚至可能为噪声数据，这样极大概率导致K-means聚类结果不稳定且趋于局部最优；图2(b)是文献[9]选择的初始聚类中心，文献[9]基于方差优化后选择的初始聚类中心稳定，能够保证聚类中心分布在不同区域，且初始聚类中心稳定，但从图中可以看出文献[9]选择的初始聚类中心偏离数据集真实的聚类中心；图2(c)是文献[11]选择的初始聚类中心，图2(c)能够保证初始聚类中心选择稳定，且处于不同的区域，但初始聚类中仍然偏离数据集真实中心；图2(d)是文中算法的结果，可以看出文中算法选择的初始聚类中心分别位于三类样本密集区域，初始聚类中心更接近样本集实际类中心。

图2 四种算法选择的初始聚类中心

表4和表5是四种算法在不同噪声比的6组人工模拟数据集上的聚类误差平方和比较和算法运行时间比较。

表4 人工模拟数据集聚类误差平方和比较

表4中用加粗数据表示该算法的聚类评价指标最佳。从表4中提供的数据可以看出，文中算法在不同噪声比的人工模拟数据集上的聚类误差平方和均明显优于K-means算法、文献[9]和文献[11]；文献[9]和文献[11]在人工模拟数据集中的聚类误差平方和与K-means相同。

表5中K-means算法在不同噪声比人工模拟数据集的运行时间明显均优于其他三种算法，但文中算法的运行时间均优于文献[9]和文献[11]。

表5 人工模拟数据集运行时间比较

图3(a)～(d)分别是K-means、文献[9]、文献[11]和文中算法在不同噪声比的人工模拟数据集上在聚类准确率、Rand index、Jaccard coefficient和Adjusted rand index四种评价指标的比较折线图，可以看出文中算法在四种聚类评价指标上均明显优于其他三种算法。

图3 四种算法在不同噪声比人工数据集上的运行结果

人工模拟数据集上的聚类结果进一步说明，文中算法能够克服选择的初始聚类中心与数据集实际中心分布差异较大的问题。

4 结束语

针对现有基于密度优化K-means算法存在的问题，提出密度去噪的DDK-means算法，通过样本集的规模和样本类簇数对样本密度的最大值进行限定，同时根据样本集的密度均值剔除样本集中的噪声样本，克服需要手动输入参数以及噪声样本参与整个聚类的缺陷。与同类文献对比，实验结果证明文中算法不仅在乳腺癌数据集的聚类结果稳定、聚类准确率提高明显、对噪声数据不敏感，且在其他UCI数据集上也具有较优的聚类效果。