一种局部概率引导的优化K-means++算法

王海燕,崔文超,许佩迪,李 闯

(1.长春大学 计算机科学技术学院,长春 130022；2.吉林大学 理论化学研究所,长春 130021;3.吉林师范大学 计算机学院,吉林 四平 136000)

1 引言与预备知识

聚类分析(cluster analysis)[1]又称群分析,是研究分类问题的一种统计分析方法,是数据挖掘领域中重要的无监督机器学习方法.聚类算法用途广泛,如区分消费群体、获取消费趋势、舆情分析及帮助市政规划等.常见的聚类算法有划分法、层次法、密度法、图论法、网格法和模型法等,其中划分法应用广泛.K-means聚类是经典的划分聚类算法,具有方法简单、效率高的特点.

随着K-means算法的广泛应用,其缺陷逐渐凸显[2]：1) 聚类中心数目K需要在聚类分析前确定,而这在实际应用中很难估计；2) 初始聚类中心需要人为选取,而不同的初始聚类可能导致不同的聚类结果.针对K-means算法的不足,目前已有许多改进算法：成卫青等[3]基于数据实例间的最大最小距离选取初始聚类中心,基于误差平方和(SSE)选择相对最稀疏的簇分裂,并根据SSE变化趋势停止簇分裂从而自动确定簇数；蒋丽等[4]提出了一种改进的K-means聚类算法,先根据类簇指标确定需要聚类的个数K,再采用基于密度的思想,实验证明改进后的算法比原K-means聚类算法准确性更高；针对第二项不足,周爱武等[5]通过基于评价距离确定初始聚类中心,优化后的算法针对存在孤立点的数据效果明显；Gu[6]采用减法聚类的算法确定初始聚类中心；鲍雷[7]针对传统K-means聚类算法在数据聚类分析时受初始聚类中心的影响,提出了将遗传算法嵌入到K-means算法中的混合式聚类算法.

K-means++是一种针对K-means算法第二类不足提出的优化算法[8].在K-means算法中,初始中心是以随机方式产生的,而K-means++算法则是在选取初始中心前对所有的数据进行一次计算,使选择的初始聚类中心间的相互距离尽可能远,以减少计算的过程量.如果随机产生的中心点过于相似,则会导致需要多次迭代才能将聚类划分开.而如果选择的初始中心点距离较大,则其属于同一个聚簇的可能性极小,使得聚类在最开始时就能很好地分开,因此计算量也会相应减少.假设数据集合X={x1,x2,…,xn},聚类数目为K,D(x)表示从数据点到已选取的最近聚类中心的最短距离.K-means++算法工作流程如下：

步骤1) 从数据集合X中随机取一点作为第一个聚类中心c1；

步骤2) 通过某种特定方式,在数据集合X中选取x作为下一个聚类中心ci；

步骤3) 重复步骤2),直到选取K个聚类中心；

步骤4) 继续使用标准K-means算法进行下一步计算.

在对K-means++算法研究的过程中,工作流程中步骤2)选取初始聚类中心点的特定方式有很多种,最经典的主要有以下几种：

2) 计算每个数据样本的密度,并按密度大小排序,将密度最大的数据样本点与其最接近样本点的中点作为初始聚类中心,最后使用圆域进行划分[10]；

3) 先选取一个种子点,再计算检测节点与最近种子节点间的距离D(xi,yi),求取sum(D(xi,yi)),再取可以落在sum(D(xi,yi))中的随机值random,计算random-=D(xi,yi),直至random<0,此时的点即为新的簇中心点,重复操作直到全部选取出K个种子节点[11].

但K-means++算法初始聚类中心选取方式计算出的误差平方和值上下波动明显,会出现误差平方和过大或过小的情形.为了改善该不足,本文提出一种局部概率引导的PK-means++算法,借助局部概率对选取初始聚类中心点的方式进行改进.为说明PK-means++算法的优势,本文将改进算法应用在具有代表性的分散数据集上,在针对同一K值的情形下聚类时,聚类后的误差平方和较原K-means++算法更稳定,保证了随机实验取值的稳定性.

2 K-means++算法优化

2.1 问题描述

图1 西瓜数据集4.0误差平方和曲线Fig.1 Curve of sum squared error on watermelon data set 4.0

在K-means++算法3种选取初始聚类中心方式中,最常见的是最后一种.但在使用第三种方式进行多次聚类实验时,误差平方和间有明显波动.即常用的K-means++算法得到的误差平方和受实验随机性的影响较大.

本文以西瓜数据集4.0为例进行聚类.首先,将数据集的聚类个数设为4,然后使用常见的选取初始聚类中心的方式将西瓜数据集4.0的30个二维数据向量进行K-means++聚类.图1为西瓜数据集4.0误差平方和曲线.由图1可见,误差平方和的取值不稳定,上下波动较明显,最大值超过0.45,最小值接近0.25,这种波动会严重影响聚类的精度和速度.

2.2 PK-means++算法

为进一步缩小误差、减少工作量,本文针对K-means++算法在误差平方和取值时遇到的问题进行优化.主要思想是通过K-means++算法计算每个点所占的概率区间,距离越远的点在(0,1)中占有概率段比例越大,随机取到该区间的概率就越大.

假设将输入设置为：一个包含n个对象的集合D；聚类个数K；距离数组D[n],D[i]表示第i个点到最近簇中心的距离；概率数组P[n]； 概率点数组PK[n].

将输出设置为K个聚类中心点集合.则PK-means++算法步骤如下：

1) 在数组中,随机取一点,作为第一个簇中心点；

2) 迭代集合D中所有的点,计算所有点到最近簇中心点的距离,并将数据记录到距离数组中,记为D[1],D[2],…,D[n]；

3) 将所有的D[i](i=1,2,…,n)叠加,得到距离和Sum(D[n]),并分别计算D[i]在Sum(D[n])中的概率,记为P[i];将概率P[i]通过概率段的形式在(0,1)中表示,将概率段的起始点存入数组PK中；

4) 取随机数rP(0

5) 重复步骤2)～步骤4),直至K个聚类初始中心全部选出；

6) 继续使用标准的K-means算法进行下一步计算.

图2 数据组P和数据组PKFig.2 Data group P and data group PK

以第一个初始聚类中心下标为4的聚类为例,将各数据点到第一个聚类中心的距离概率表示在(0,1)区间上,结果如图2所示.其中,数据组P存储的各数据表示各点到第一个初始聚类中心距离的概率段,其中P[4]=0.数据组PK存储的是概率段在(0,1)内的实际点数据,若随机取的rP值在区间(PK[n-1],PK[n]]内,则把第n个数据点作为下一个聚类中心.

3 实 验

3.1 数据集

图3 20个(1,5)区间的随机点Fig.3 Twenty random points of zone (1,5)

为了验证算法PK-means++在误差平方和方面的优势,本文将数据集合锁定在分散数据集上,为保证是相对分散的数据集,随机取5×5正方形(横坐标x∈(0,5),纵坐标y∈(0,5))内的20个二维数据点作为数据集Ⅰ,数据点可视化效果如图3所示.随机取10×10正方形内的20个二维数据点作为数据集Ⅱ,数据点可视化效果如图4所示；随机取10×10正方形内的50个二维数据点作为数据集Ⅲ,数据点可视化效果如图5所示.由图3～图5可见,研究选取的数据非常分散.

图4 20个(1,10)区间的随机点Fig.4 Twenty random points of zone (1,10)

图5 50个(1,10)区间的随机点Fig.5 Fifty random points of zone (1,10)

3.2 实验结果分析

在上述选取分散数据的基础上,为充分说明PK-means++算法的优越性,下面分别对K-means++算法和PK-means++算法进行多次对比聚类实验.参考文献[12],实验环境为：Intel(R) CoreTMi5-7200处理器,主频为2.50 GHz,内存为8.00 GB.分别做10次实验,记录10次实验的误差平方和,并针对不同的数据集给出两种算法的对比曲线.

选取数据集Ⅰ,对比K-means++和PK-means++算法聚类计算得出的误差平方和,结果如图6所示.由图6可见,PK-means++算法计算得出的误差平方和变化较平稳,而原始K-means++算法计算的误差平方和上下浮动相对较大.这是因为K-means++算法先随机选取一个小于距离和的数,然后将随机数作为被减数依次做减距离操作,最后取差小于0时的点作为下一个初始聚类点,而PK-means++算法是在距离概率(0,1)内取点.在聚类较明显的数据集中这两种算法对误差平方和都无太大影响.说明PK-means++算法对聚类效果较明显的数据集聚类后不会产生太大影响.而对较分散的数据集,数据点之间的距离较平均,距离差异较小,PK-means++算法随机取数的范围较K-means++取数的范围小,取数的波动性较小导致取点的波动性较小,每次实验取点的结果较接近,从而保证了误差平方和的上下波动较小,进而呈现一种稳定的状态.

为进一步证明PK-means++算法的优势,本文将实验规模扩大到数据集Ⅱ和数据集Ⅲ上,K-means++算法和PK-means++算法计算得出的误差平方和曲线分别如图7和图8所示.由图7和图8可见,PK-means++算法在平稳程度上仍有绝对优势,而K-means++算法波动幅度仍较大,随机取值得到的不一定是最佳实际数据.

图6 两种算法对数据集Ⅰ误差平方和的对比Fig.6 Comparison of two algorithms for sum squared error on data set Ⅰ

图7 两种算法对数据集Ⅱ误差平方和的对比 Fig.7 Comparison of two algorithms for sum squared error on data set Ⅱ

为证明PK-means++算法的优越性,本文选择在西瓜数据集上进行实验,并将实验基数设为10次.图9为西瓜数据集使用K-means++算法和PK-means++算法实验10次得到的误差平方和对比曲线.由图9可见,PK-means++算法计算得出的误差平方和较K-means++算法上下浮动较小,结果较平均,表明PK-means++c有优势.

图8 两种算法对数据集Ⅲ误平方和的对比Fig.8 Comparison of two algorithms for sum squared error on data set Ⅲ

图9 两种算法对西瓜数据集4.0误差平方和的对比Fig.9 Comparison of two algorithms for sum squared error on watermelon data set 4.0

4 PK-means++算法应用

本文将PK-means++算法应用到Seeds数据集上,计算Seeds数据集组内的误差平方和(SSE).由于已经验证了PK-means++算法在计算误差平方和方面的稳定性,因此,在对Seeds数据集的实验过程中,本文针对每个K仅进行单次实验即可,即通过误差平方的方式确定聚类数K的最佳数值.利用PK-means++算法分别计算K=2,3,4,5时的误差平方和,结果列于表1.

表1 PK-means++算法计算不同K值的SSE

手肘法[13]的核心指标是误差平方和,该方法可获得较准确的聚类数,最终图形为手肘的形状.随着聚类数K的增大,样本划分更精细,每个簇的聚合程度逐渐提高,则SSE会逐渐变小,整个过程的SSE可归结为下列3个阶段[14]：

1) 当K小于真实聚类数时,K的增大会大幅度增加每个簇的聚合程度,故SSE的下降幅度会很大；

2) 当K到达真实聚类数时,此时是一个过渡期,若继续增加K,则所得到的聚合程度回报会迅速变小,故SSE的下降幅度会骤减；

3) 当K值大于真实聚类数时,SSE会随K的增大而趋于平缓.

最终的误差平方和SSE和K的关系图是一个手肘形状,而肘部对应的K值即为数据的真实聚类数,如图10所示.由图10可见,聚类数K=3是Seeds的最佳聚类个数.利用PK-means++算法聚类后的效果如图11所示.由图11可见,PK-means++算法将Seeds数据集成功聚类为3个类别.

图10 Seeds数据集手肘图Fig.10 Elbow diagram of Seeds data set

图11 Seeds使用PK-means++算法的聚类效果Fig.11 Clustering effect of PK-means++ algorithm on Seeds

综上所述,针对K-means++算法在使用常见的选取初始聚类中心方式对较分散数据集进行误差平方和计算时,聚类结果的误差平方和影响波动较大的问题,本文提出了一种PK-means++算法,该算法在进行较分散数据集聚类时,借助局部概率引导聚类中心的选取,选取初始聚类中心的方式在同一K值的情形下对较分散的数据集可取到较稳定的误差平方和,即PK-means++算法提高了误差平方和的准确度,聚类后的误差平方和比K-means++算法更稳定,从而更好地保证了随机实验取值的稳定性.