一种改进的K-Means聚类算法

刘文佳 张 骏

(武汉理工大学管理学院，湖北 武汉 430070)

0 引言

聚类分析能从海量的数据集中发现新的、有意义的数据分布模式，已经被广泛应用于图像识别、客户细分、推荐系统等诸多领域。不同于分类算法，聚类分析是一种无监督的机器学习方法，无需事先给定分类标准，根据数据的自身特征来进行自动分类，要求同一群组内的对象具有较高的相似度；不同群组间的对象具有较小的差异度。

聚类算法可大概分为基于划分的、密度的、网格的、层次的、模型的聚类算法。K-means聚类算法，是基于划分的聚类算法的一种，具有实现简单，收敛速度快等优点，适合于处理大数据的运算，Spss、Matlab、Weka等数据挖掘软件中均内置了K-means算法。而传统的K-means算法仍具有一些局限性，过度依赖于初始聚类中心的选取和聚类数目的选取，且随着数据量的不断增多，其耗费的时间较长。本文针对K-means算法的两个不足展开研究：通过最大距离原则，即取距离最大的对象作为初始聚类中心；另一方面，借用三角不等式原理——任意两边之和大于第三边，减少了一些不必要的距离计算和比较。最后通过实验比较改进的K-means聚类算法和传统的K-means聚类算法的时间复杂度。

1 K-means聚类算法

1.1 K-means聚类算法的基本思想

K-means聚类算法的核心思想是：对于数据集中的每个对象，根据计算对象与这些聚类中心的相似度或距离，来判断该对象属于哪个类。一般采用误差平方和准则函数作为目标函数，其定义如式(1)。

(1)

其中，Ci表示第i个类集合的样本数据，cj表示第j个类的聚类中心，E表示所有对象与对应的聚类中心的误差平方和，当E值收敛时，则聚类结束。

K-means聚类算法的流程描述如下：

(1)根据先验知识，给定一个K值作为划分的类的数目，随机选择K个对象作为初始聚类中心。

(2)通常依据欧式距离公式，参见式(2)，计算每个对象到K个聚类中心的距离，并选择距离最小的类作为该对象的所属类别。

(2)

其中，xi=(xi1，xi2，…，xip)和xj=(xj1,xj2，…，xjp)表示两个包含p维属性的对象。

(3)在每个类簇中，计算每个类中所有数据对象的均值，参见式(3)，得到新的聚类中心。

(3)

(4)重复步骤(2)和步骤(3)，直至聚类结果趋于稳定，目标函数收敛。

以一组数据来详细描述K-means聚类算法的详细过程，假设有10个样本对象x1,x2,x3,…,x10，每个样本对象包含两个属性xi1,xi2，如表1所示。

表1 模拟K-means聚类算法实现过程的数据集

假设聚类数目K=2，采用欧式距离公式分别计算各样本对象到聚类中心的距离，每次迭代的聚类结果依次如图(a-d)所示，当迭代次数到第4次时，聚类的结果保持不变，因此，经K-means算法计算后的聚类结果为：x1,x8,x9,x10为一类，x2,x3,x4,x5,x6,x7为另一类，共迭代了4次。

图1 迭代的聚类结果 注：以实心圆点表示每个类簇的聚类中心，空心圆点表示各样本对象，各对象以坐标的形式表示在平面坐标轴上。

1.2 K-means聚类算法的局限性分析

K-means 算法主要存在以下几方面的问题：

(1)需要根据先验知识预先设定聚类的数目K，通常K值较难确定。

(2)依赖于初始聚类中心的选取。K-means聚类算法在第一次迭代时，采取随机的方式选取初始聚类中心，因此，对于同一组数据集，进行K-means聚类分析时，得到的聚类结果不一定相同，即初始聚类中心的选取会导致最终的聚类结果不稳定。

(3)算法易陷入局部极小解。根据式(1)可知，目标函数存在多个局部最小值，但全局最小值只有一个。在K-means聚类算法中，由于初始聚类中心是随机选取的，其落入非凸函数曲面的位置，通常会偏离全局最优解的探测范围，再通过多次迭代计算，目标函数得到的结果只是达到局部最小，而非全局最优，会受到异常值或孤立点的影响。

(4)面对海量的数据集，算法的复杂度高，耗费的时间开销大。通过对K-Menas聚类算法的分析，可知其时间复杂度为O(nkt)，其中n是数据集中所有样本的数目，k是预先给定的聚类数目，t是迭代的次数。

2 K-means算法改进

2.1 K-means算法的改进思路

本文针对 K-means算法的不足，本文从两个方面进行了改进，一方面针对 K-means 算法采取随机方式选取初始聚类中心，可能导致聚类结果不稳定，且各类簇间的差异度不显著等不足，本文采取最大距离原则，即在选取聚类中心时，将距离相差最大的对象作为聚类中心，可有效避免传统的K-means算法采取随机方法选择聚类中心，使得部分聚类中心相隔较近，从而出现局部最小值的情况。

另一方面，K-means聚类算法的复杂度为O(nkt)，主要体现在对数据集中样本点距离的计算和比较上。本文借鉴平面几何中的三角不等式原理：“三角形任意两边之和大于第三边”。其形式化定义如下：令xi∈X，d(ck,cr)为两个聚类中心间的距离，d(ck,cr)、d(xi,ck)和d(xi,cr)构成了一个三角形的三边。根据三角不等式原理，有d(ck,cr)d(xi,ck)+d(xi,cr)。若d(ck,cr)≥2d(xi,ck)，则可推导出d(xi,ck)

d(ck,cr)d(xi,ck)+d(xi,cr)d(ck,cr)>d(xi,ck)+d(xi,ck)⟹d(xi,ck)

(4)

2.2 改进的K-means算法的流程描述

为便于研究说明，本文只考虑了二维数据的聚类分析。在处理多维数据时，可利用降维技术将实现多维数据到二维数据的转换，通俗地讲，即按照某种换算方法将一组高维数据转化到低维数据的表现形式，并保证变化后的数据依旧保持或近似保持高维数据的相似度关系。通常，有两种方法——极点轴投影换算法和非线性判据换算法，来进行数据的降维。极点轴投影换算法的核心思想是通过不断地做轴线，使得数据集中的全部元素投影在轴线上。非线性判据换算法的基本思想是：使用了非线性换算判据k，k是使原空间点间的距离与对应新空间点间的距离的平方差达到极小值时，得到新空间点的几何构形。

本文以二维数据为研究对象，基于上述的改进思路，将改进的K-means聚类算法的基本思想可概括为三点：①根据距离最大值原则，迭代K次，找到个初始聚类中心；②计算各样本点到聚类中心的距离，采取欧式距离公式来计算两个样本点的距离，并根据最小距离原则将样本点划分到对应的类中；③重复步骤②，当目标函数收敛时，则聚类结束。改进的K-means聚类算法的流程描述如下：

(1)假设数据集中有n个样本点，记作Sn=x1,x2,…,xn，选取距离最大的两点p、q，满足dqp=maxdij;i,j∈1,2,…,n，记 第一个初始聚类中心x1*=xp，第二个聚类中心x2*=xq。

(2)以x1*和x2*为中心对数据集中剩余的n-2个样本点进行归类，若xi-x1*

(3)计算S21*集合中的各个样本点到聚类中心x1*的欧式距离，得到最大距离时对应的样本点，满足d21=maxxi-x1*,xi∈S21*；同理，计算S22*中的各样本点到聚类中心x2*的欧式距离，得到满足d22=maxxi-x2*,xi∈S22*时对应的样本点。记d2=maxd21,d22，满足该条件的样本点记作x3*，作为第3个初始聚类中心。

(4)重复执行步骤(2)和步骤(3)，直至找到K个初始聚类中心为止。

(5)计算每两个初始聚类中心间的欧式距离，记作dci,cj。

(6)计算各个样本点到聚类中心的距离，根据最小距离原则，将样本点划分到相应的类中。任选一个聚类中心ck，计算样本点xi到聚类中心的距离d(xi,ck)，并将满足d(ck,cr)<2d(xi,ck)条件的聚类中心cr，记录在集合CM中。对于CM中未处理的中心cr，计算d(xi,ck)，找到满足d(ck,cy)≥2d(xi,cr)的中心cy，并将cy从CM中删除，减少了样本点与所有聚类中心的距离的计算。最后计算样本点xi到聚类中心的最小欧式距离，即mind(xi,CM)=min{d(xi,ck),d(xi,CM)}，并将样本点xi划分到对应类簇中。

(7)以误差平方和准则函数作为目标函数，重复步骤(5)和步骤(6)，迭代多次，直至目标函数的值收敛，则聚类算法结束。

2.3 改进的K-means聚类算法的复杂度分析

以一个样本点为例，传统的K-means聚类算法在计算样本点到各聚类中心的距离时，需进行k次计算，其时间复杂度为O(nkd)；而改进的K-means算法，在最好的情况下只需计算1次，最坏情况下需计算k次。假设经过一次迭代，某样本点到聚类中心的平均计算次数为α次，则时间复杂度为O(nαd)。显然有αk，则O(nkd)≥O(nαd)，可说明改进的K-means聚类算法具有更低的时间复杂度，需要运算的时间更短，运行效率更高效。尤其当数据集较多时，即n较大时，改进的K-means聚类算法在运算时间上的优越性越发明显。

3 实验结果与分析

本文采取对比分析法，分别采用人工数据集和KDD Cup 1998 data数据集来比较传统的K-means聚类算法和改进的K-means算法的运算时间。

实验一：验证根据最大距离法选取初始聚类中心的有效性。本实验模拟了17组二维数据：{(4,8)；(4,9)；(7,8)；(4,6)；(4,10)；(4.5,5)；(7,10)；(10,6)：(9,7)；(10,8)；(9,6)；(7.5,9)；(7,9)；(3.5,5)；(4.5,6)；(3.5,8)；(4,5) }。假设聚类数目k=4，采取传统的K-means聚类算法对人工数据集进行聚类分析，在同一组数据集上依次进行5次实验，即每次实验都是采取随机原则选择每个类别的初始聚类中心，最终的聚类中心的结果如表2所示。采取最大距离法选取初始聚类中心时，最终得到的聚类结果如表2所示。

表2 两种K-means算法的最终聚类中心(以坐标的形式表示)

从表2的实验结果可知，传统的K-means算法得到三组不同的聚类结果，印证了传统的K-means算法依赖于初始聚类中心的选取，得到的聚类结果通常是不稳定的。另外，从5次聚类分析的结果可知，随机2、随机3和随机5这三组实验得到的聚类结果是完全相同的，一定程度上说明此组聚类结果是合理的。而改进的K-means算法得到与随机2、随机3和随机5等实验相同的聚类结果，说明根据最大距离的原则选取初始聚类中心的方法是可行的，能保证各类簇间的样本点的差异度较大。

实验二：比较改进的K-means算法和传统的K-means算法的时间复杂度。

本实验基于KDD Cup 1998 data公开数据集，该数据集包含95412条记录，每条记录包含481个字段，在Turbo C++开发环境下实现。根据数据集的特性，依次选取3个不同的聚类数目k，分别为3，10，50。每次固定聚类数目k，在同一数据集上分别采用传统的K-means算法和改进的K-means算法进行聚类分析，记录下每种算法的运算时间。运算时间越短，说明该聚类算法的时间复杂度越低，性能越佳。两种聚类算法的运算时间如表3所示。

表3 两种聚类算法的运算时间对比(以秒为计算单位)

从表3的实验结果可知，随着聚类数目k值的增大，改进的K-means算法较传统的K-means算法在时间效率上提升的倍数越高。因为改进的K-means算法引入了三角不等式原理，当聚类数目的值不断增加时，对于每个样本点来说，需要计算的样本点到聚类中心的距离的次数越多，改进的K-means算法恰好利用三角形中“任意两边之和大于第三边”的定律，减少了某些样本点到其他聚类中心的距离的计算和比较，因此运行时间得到大幅缩减，具有更高的运行效率。

4 结束语

面对海量的数据，K-means聚类算法通过对数据集的划分，从而在划分后的数据集上进行分析处理，不仅能提高信息系统的运算速度，一定程度上还能提升分析结果的准确度。而传统的K-means聚类算法在聚类分析时，面临着诸多挑战，本文从两个方面进行改进，一方面采取最大距离原则来选择初始聚类中心，使得最终的聚类结果中，同一类中的样本点的相似度高，不同类间的样本点的相似度低。另一方面，借鉴三角不等式原理，减少了一些样本点到聚类中心的计算和比较过程，有效减少了运算的时间，降低了时间复杂度。

[1] 郭崇慧, 赵作为. 基于客户行为的4S店客户细分及其变化挖掘[J].管理工程学报,2015,(04):18-26.

[2] 安计勇, 闫子骥, 翟靖轩. 基于距离阈值及样本加权的K-means聚类算法[J].微电子学与计算机,2015,32(8).

[3] 何云斌, 刘雪娇, 王知强, 等. 基于全局中心的高密度不唯一的K-means算法研究[J].计算机工程与应用,2016,(01):48-54.

[4] 吴夙慧, 成颖, 郑彦宁, 等. K-means算法研究综述[J].现代图书情报技术,2011,(05):28-35.

[5] 刘美玲, 黄名选, 汤卫东. 基于离散量优化初始聚类中心的K-means算法[J].计算机工程与科学,2017,39(6).

[6] 何春霞, 常晋义. 三角不等式原理对聚类算法的改进[J].常熟理工学院学报,2007,(2).