聚类中心初始值选择方法综述

邓旭冉，超木日力格，郭 静

(1.中国科学技术大学,安徽 230000；2.中国电子科学研究院，北京 100041)

0 引 言

随着网络和多媒体的蓬勃发展，人们可以收集的数据越来越多，例如视频信息、音频信息、文本信息、图像信息等等。为了提高数据分析效率，人们更加倾向于通过机器学习的方式对海量的数据进行处理。聚类是模式识别和数据挖掘中广为使用的数据分析手段。是无监督学习领域近年来的研究热点之一[1-2]。聚类分析适用于很多不同类型的数据集合，很多研究领域，如生物、医药、工程、语言、人类学、心理学和市场学等[3]。

把单个样本对象的集合以相似程度划分为样本组成的类或簇的过程，称之为聚类[4]。聚类过程将样本空间中的数据点划分到不同的类中，使得同一类中的样本间相似程度高，不同类中的样本间相似程度低，这就是聚类的本质。经典的聚类方法有基于划分的方法、基于层次的方法、基于密度的方法，还有基于网格的方法及基于模型的方法。划分聚类算法是最常用的聚类算法之一，经典的K均值(K-means)聚类算法[5-6,8]以及模糊C均值(FCM)聚类算法[9]都属于划分聚类算法。

在划分聚类问题中，如何选择初始聚类中心一直是聚类算法研究的关键论题之一。划分聚类算法需要事先给定初始聚类中心，通过聚类中心和隶属度的迭代更新以得到对样本集合的划分。众所周知,聚类算法的结果和聚类中心初始化密切相关，合理的初始化可以使得聚类算法很快收敛，并得到较好的聚类结果。但不合理的初始聚类中心会导致算法的效率低下，甚至得到不好的聚类结果。因此，如何选择好的初始聚类中心，对聚类算法来说是非常重要的。

选取初始类中心的一种常用方法是：多次使用聚类算法，每次选择一组不同的随机初始类中心，然后从聚类结果集中选取最优聚类结果，聚类结果对应的初始类中心被认为是最佳初始类中心。这种策略简单，但计算量大且效果可能不好，这取决于数据集的大小和类的个数。

第二种有效的选择初始类中心的方法是，随机地选择一个点，或者取样本集的质心作为第一个初始类中心点。第二个初始类中心点选择离第一个点最远的点，选择后续类中心的方法是，选择离已经选取过的类中心距离和最大的点。使用这种方法，确保了选择的初始类中心不仅是随机的，而且是散开的。但是这种方法运算量较大，且容易选中离群点。

第三种，通过使用其他的聚类方法，例如山峰聚类[17]，聚类结果作为其他聚类算法的初始类中心。显然，这样的聚类中心初始化方法效果较好，因为通过使用前序聚类算法已经得到了数据集粗略的数据结构，因此使用算法的结果作为后续聚类算法的初始类中心是合理的。

本文对目前常用的几种聚类中心初始化方法进行总结。本文的章节安排如下：第一节中，重点介绍划分聚类算法的框架；第二节中，重点介绍几类聚类中心初始化方法；第三节中，分析本文介绍的几种聚类中心初始化方法，对其性能以及适用的问题进行了对比；第四节中，对本文的内容进行总结，并展望未来的工作。

1 划分聚类算法

划分聚类算法的原理，简单来说就是按照“类内间距小，类间间距大”的原则对样本集合进行划分。首先需要确定样本最后要聚成几类，然后挑选几个样本点作为初始中心点，再然后依据隶属度和聚类中心的迭代更新公式给数据点做划分，直到最后达到“类内的点都足够近，类间的点都足够远”的聚类效果[7]。

假设X={x1,x2,...,xn}是一S维数据集，X∈RS,数据集中的每个样本xk∈X,k=1,2,...,n,均由一个S维特征向量表示。聚类的目标是将这n个数据点分为c类,V={vi},i=1,2,...,c表示各个聚类中心。算法中用uik表示数据集X中的第k个样本xk对第i类的隶属程度。划分聚类算法通过使非相似性指数的价值函数达到最小，从而得到数据集中数据点的划分。

划分聚类算法的迭代过程，具体的实现框架如下：

表1 划分聚类算法框架

上述迭代更新过程，对不同的划分聚类算法来说，有不同的迭代更新公式。例如，K-means聚类算法的迭代更新过程可以总结为[5]：

(1)

(2)

对于FCM算法，聚类中心和隶属度的迭代更新公式为[9]：

(3)

(4)

选择合适的初始类中心是划分聚类算法的关键步骤。常见的方法是随机的选取初始质类中心，但是这样的聚类结果质量往往很差。下节，我们主要介绍几种划分聚类算法的初始聚类中心选取方法。

2 聚类中心初始化方法

本节主要介绍几个聚类中心初始化方法，并分析其优缺点。包括：

2.1 基于k-means++算法的聚类中心初始化

David等人于2007年提出的k-means++算法[10]，就属于这类聚类中心初始化方法。k-means++算法随机地选择第一个类中心，然后，选择离最远的点作为第二个类中心。以此类推，直至获得c个类中心，则初始化结束。

图1 k-means++算法聚类中心选择流程

选择后续聚类中心时需要计算该聚类中心与前面几个聚类中心间的距离，计算方法如下[10]：

(5)

表2 k-means++算法

该方法主要考虑聚类中心初始化时需要覆盖整个数据集，使得聚类中心在数据集中均匀的分布，从而保证初始的类中心具有良好的代表性。通过该种聚类中心的初始化方法，可能可能选中离群点。

2.2 基于子空间的k-means++算法

为了克服k-means++算法的缺点，Murat等人于2011年提出了一种改进的聚类中心初始化方法[11]。该方法与k-means++算法的聚类中心初始化方法类似，都是通过选择分布于整个数据集的样本点作为初始类中心，从而提高类中心对样本的代表程度。

从样本的s个维度中选择两个具有代表性的维度，建立选择初始聚类中心的子空间。首先，选择样本的主维度，也就是对样本的区分程度最高的维度。计算方法如下[11]：

(6)

然后，通过计算主维度与其他维度间的相关系数，选择第二个特征维度。计算方法如下[11]：

(7)

选择CCll′最小的特征维度作为第二个维度，构建样本的子空间。在子空间中计算各个维度的均值[11]：

(8)

表3 基于子空间的k-means++算法

上述方法虽然在k-means++算法的基础上进行了改进，从而使得聚类中心初始化方法对异常点更鲁棒，但对噪声敏感。

2.3 基于mean-shift算法的聚类中心初始化

为了使得聚类中心初始化方法可以对抗噪声点的影响，Jiangang Qiao等人[12]于2013年提出了一种基于mean-shift算法的聚类中心初始化方法。

mean-shif算法[18,20]是一种无参数密度估计算法。该算法最先是以一种概率密度梯度函数的估计算法提出的。后引入了核函数和权重系数，慢慢发展为现今的迭代算法。mean-shift算法的核心思想为：先计算出当前像素点的偏移均值，将该点移动到其偏移均值，并以此为起点继续移动直至满足一定条件后停止迭代。计算聚类中心候选点和候选区域样本间的相似性，用相似性函数的最大值求目标的Mean Shift向量，将聚类中心候选点移动到偏移均值，一直迭代运算直至聚类中心候选点不发生偏移[19]。

首先，该方法的第一步与基于子空间的k-means++算法相同，需要通过计算得到样本的两个具有代表性的维度，建立只有这两个维度的样本集X′。

其次，选择任意一点，最为初始类中心候选。对该样本使用以R为半径的mean-shift算法，以使得初始类中心在样本密度较高的区域，这样就可以避免噪声点的影响。mean-shift算法半径R的计算方法为：

(1)从X′随机选取100个样本点；

(2)计算这100个样本点与其最近邻样本间的距离；

(3)mean-shift算法半径R等于最大距离的4倍。

最后，与基于子空间的k-means++算法相似，根据样本点与已有类中心间的距离选择初始类中心。但每次选择类中心时均通过mean-shift算法对其进行修正。

图2 基于mean-shift算法的聚类中心初始化方法流程

该方法对噪声点不敏感，通过使用mean-shift算法，使得得到的初始类中心在样本点密度较高的区域，因此初始聚类中心对样本点的代表程度较高。

2.4 基于山峰聚类的聚类中心初始化

一些聚类算法的聚类结果，也可以用于其他聚类算法的初始化。例如，山峰聚类算法因为其效率高、聚类结果可靠等性能，一般可用于其他复杂聚类算法的聚类中心初始化。

Yager和Filev在1994年提出的一种聚类方法，可以有效快速的估计聚类中心[17]。它的基本思想是通过构造密度函数，寻找样本密度较高的点作为聚类中心，再通过计算样本与聚类中心间的距离，实现样本的聚类。

第一步：在数据空间上构造网格，如图3所示，网格的交叉部分构成了聚类中心的候选集，记为V。一般情况下，取网格间隔均匀，也可以根据数据分布的先验信息使用非均匀的网格。网格的密度与聚类的精度以及聚类的速率有着密切的关系。网格划分越细，聚类中心候选集越大，增大了所需的计算量，聚类就越慢。

图3 网格示意图

第二步：构造山峰函数(密度函数)，该步是山峰聚类算法的核心。通过山峰函数，计算数据空间中密度较大的点。一般，使用高斯密度函数作为山峰函数。点vi山峰函数的高度为[17]：

(9)

其中，δ是一个固定常数。式(9)表明，点vi处的山峰高度由数据集中的所有样本点进行计算。显然，数据点与vi间的距离越大，对山峰函数的贡献越小。因此，当聚类候选中心vi周围的数据增加时，该点的山峰高度更高，该点被选取为聚类中心的概率越大。通过计算山峰函数，可以得到山峰函数分布图。

第三步：得到聚类中心。首先，在聚类中心候选集V中选取山峰函数最大的点作为第一个聚类中心，而后通过顺序地削去山峰函数大的点及该点周围的点，寻找下个聚类中心。

从山峰聚类的过程可以看出，山峰聚类结果中的聚类中心分布在样本密度较高的区域，并且聚类的个数是不需要事先指定的。

2.5 基于高密度区域快速搜索聚类算法

有的聚类算法将聚类中心的选择与聚类过程结合起来，避免对聚类中心的初始化。山峰聚类算法在寻找聚类中心时是通过顺序的削去山峰来实现的，而在实际中，当类个数非常大时，通过山峰聚类算法进行聚类中心的发现其时空代价过大。Alex Rodriguez和 Alessandro Laio[21]于2014年在《自然》杂志上提出了一种很简洁优美的聚类算法, 可以识别各种形状的类簇, 并且其参数很容易确定。

该算法的假设是, 类簇的中心由一些局部密度比较低的点围绕, 并且这些点距离其他高局部密度点的距离都比较大。首先定义两个值: 局部密度ρi以及到高局部密度点的距离δi[21]:

(10)

(11)

其中：如果x<0，χ(x)=1，否则χ(x)=0。dc是一个截断距离, 是一个超参数。所以ρi相当于距离点i的距离小于dc的点的个数。由于该算法只对ρi的相对值敏感, 所以对dc的选择比较鲁棒, 一种推荐做法是选择dc使得平均每个点的近邻数为所有点的1%～2%。对于密度最大的点，设置δi=maxj(dij)。

那些有着比较大的局部密度ρi和很大的δi的点被认为是类簇的中心。局部密度较小但是δi较大的点是异常点.在确定了类簇中心之后, 所有其他点属于距离其最近的类簇中心所代表的类簇。

图4(A)中为样本点，图4(B)中通过式(10)和式(11)计算局部密度ρi和δi后构建的决策图。从图4可以看出，可以看到, 点1和点10两个点的ρi和δi都比较大, 可以作为聚类中心点，而 点26、点 27和点 28的δi也比较大, 但是ρi较小, 所以属于异常点。

图4 基于高密度区域快速搜索聚类算法

通过该聚类方法，可以避免对聚类中心的初始化，也可以得到较好的聚类结果。显然，该聚类方法也可用于寻找聚类中心，并作为其他聚类算法的类中心初始值。

3 聚类中心初始化方法分析

本文介绍的几种聚类方法，存在优缺点，且适用的聚类场景也不一样。本节中，主要对这几种聚类方法进行分析比对。

基于k-means++算法的聚类中心初始化算法和基于子空间的k-means++算法都是需要制定类中心个数的聚类中心初始化方法。显然，在对数据集的结构不了解的情况下指定聚类个数是比较困难的。同时，这两类方法都是在得到第一个聚类中心后，通过一定的方式寻找后续的聚类中心，因此该方法对噪声敏感，如果第一个聚类中心偏离较大时，得到的聚类中心初始化结果也会较差。

虽然基于mean-shift的聚类中心初始化算法也是通过获得第一个聚类中心，然后根据一定规律寻找后续的聚类中心的方法，但是因为mean-shift方法的性质，使得得到的初始类中心在样本点密度较高的区域，对样本点的代表程度较高，因此该方法对噪声鲁棒。上述三种方法都是对聚类中心的初始化方法，后续对数据的聚类需要使用其他的聚类算法，例如k-means聚类算法等，对数据集进行划分。

山峰聚类是一种常用聚类中心初始化方法，该方法与基于mean-shift的聚类中心初始化算法一样，都是基于类中心应选在数据点密度较高的区域的假设。根据山峰函数计算数据点的密度，不断选择山峰作为聚类中心候选点，从而得到数据的类中心。显然，该方法也存在需要指定类中心个数的问题，但该方法计算简单，且得到聚类中心的同时，也可以得到数据的划分。

基于高密度区域快速搜索聚类算法，在山峰聚类的基础上，通过引入新的函数，可以一次性得到数据的聚类中心以及数据的划分，因此该算法提出后得到了广泛的应用。

综上所述，这几类聚类算法各有其优缺点，也有其适用的聚类场景。

4 结 语

聚类算法在许多科学领域均得到了非常广泛的应用，同时，怎样提升聚类结果的精确度，也成为了机器学习研究的热点。聚类算法初始化的好坏决定着聚类算法结果的优劣，近年来，专家学者们对如何合理的对聚类中心进行初始化做了大量的研究，为得到更好地聚类结果做出了显著地贡献。本文旨在介绍近年来提出的聚类中心初始化方法，分析其优劣性质，为选择聚类中心初始化方法提供参考。当然，本文短短的篇幅不足以概括所有的聚类中心初始化方法，作者只是将最新的成果罗列出来，因此收集更多地聚类中心初始化方法并分析其优缺点也是下一步工作的重点。