基于最大期望的初始聚类中心选择算法

廉文娟，史丹丹，安其立，贾 斌

（山东科技大学计算机科学与工程学院，山东 青岛 266590）

0 引言

聚类是机器学习中重要的组成部分，是一种研究分类问题的统计分析方法，广泛应用于文本[1]，图像[2]，音频等领域。K-means算法为聚类算法中的硬聚类算法，是典型的基于原型的目标函数聚类方法的代表。它的基本思想是，通过迭代方式寻找 K个簇的一种划分方案，使得聚类结果对应的代价函数最小。算法中采用欧式距离作为相似度测量，代价函数为各个样本距离所属簇中心点的误差平方和（Sum of Squared Error, SSE）。但是K-Means方法有几个缺点，包括确定初始的聚类中心初始值是随机的，以及距离模型用于确定数据之间的相似性，而传统距离模型对每个数据属性的影响相同。K-means++在此基础上，利用初始样本点到整体样本的距离，基于概率化的选择计算出下一个初始聚类中心，对于同样问题的解决方法国内外有利用密度[3]、区域密度[4]以及排序划分[7]的优化计算方法；文献[7]-[11]分别采用不同的方法计算初始样本中心，其中文献[7]和文献[11]分别采用了加权局部方差和自确定簇数和聚类中心的方法；文献[9]采用余弦距离作为度量标准确定最优簇中心，针对计算过程中迭代次数，计算耗时以及整体聚类效果；文献[12]研究了一种基于改进 k-均值和距离最小二乘法的稳健苹果检测与重构方法；文献[13]结合主成分分析（PCA）和快速质心分析来尝试提高 K-Means的性能估计（RCE）。本文针对样本初始中心利用最大期望一次估算全部初始聚类中心位置，在后续迭代求解过程中有效减少迭代次数，降低时间开销，提高了整体聚类效果。不同的是，文献[15]中是根据目标预测状态选择初始聚类中心点。文中首先介绍了传统K-Means++算法的原理和流程，然后针对K-Means++算法的缺点，提出了基于最大期望估算初始聚类中心聚类算法。最后，根据当前研究的热点问题，提出对K-Means算法未来研究方向的展望。

1 K-means++算法

1.1 K-means++

在判断初始聚类中心时，K-means++参照K-means算法在其基础上给出了在整体样本中利用概率化选择初始的聚类中心之间的相互距离尽可能地远的方法，很大程度解决了原始K-means极易陷入局部最优的困境以及由于 k-means算法需要随机地确定初始聚类中心的原因，导致不同的聚类中心可能导致完全不同的聚类结果的缺陷。

k-means++算法的核心思想是：假设已经选取了n个初始聚类中心（0＜ n＜k），则在选取第n+1个聚类中心时，聚类当前n个聚类中心越远的点会有更高的概率被选为第 n +1个聚类中心。在选取第一个聚类中心（n = 1 ）时同样通过随机的方法。

k-means++算法的实现步骤，如下：

Step 1：从数据集中随机选取一个样本点作为初始聚类中心 c1;

Step 2：首先计算每个样本与当前已有聚类中心之间的最短距离（即最近的聚类中心的距离），用D（ x）表示；接着计算每个样本点被选为下一个聚类出下一个聚类中心；

Step 3：重复第2步知道选择出K个聚类中心；

Step 4：针对数据集中的每个样本ix，计算它到K个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；

Step 5：针对每个类别ic，重新计算它到聚类中Step 6：重复第4步和第5步直到聚类中心的位置不再变化；

在 k-means++算法中，并不是直接选择距离最远的点作为新的簇中心，只是让这样的点被选做簇中心的概率更大而已。

1.2 K-means++损失计算

对于具有相同方差的高斯分布，簇 C = ｛ c1, c2,… ,ci｝,样本 X = ｛ x1, x2,… , xn｝，均值为 μ，标准差用σ表示，方差为 σ2。高斯混合分布下整体样本似然函数：

ln L（θ）是 L （θ）的增函数， ln L（θ）与 L （θ）在同一点处达到最大值，对似然函数 L （θ）取对数，转为求解对数似然方程，定义为：

对于计算簇内一点到各样本间距离总和最小，式（2）的即为整个迭代过程中的损失函数的核心表示。

（2）为关于μ的偏导，对于本高斯混合分布下簇内样本中心的计算方法，即为每次新簇样本中心。

1.3 初始样本中心选择

概率化选择是 K-means++算法计算初始样本中心的核心算法，设 D = ｛ d1, d2,… dn｝为全部样本到现有聚类中心的距离，定义下一个初始样本中心为

其中分布下，根据概率能够被正确选择为临近真正聚类中心点的概率并不是很高，这不仅要以后来的迭代计算来不停校正中心点的位置，而且容易陷入局部最优，从而影响计算效率和最终效果。

1.4 EM算法

EM 算法是一类很好的优化算法，核心算法是一组迭代计算。迭代分为两部分，即E步和M步，两互为输入输交替计算。由于EM算法的收敛性并不能保证全局最优，因此常对EM算法进行随机初始化并多次运行，选择对数似然最大的迭代输出结果[8]。

EM算法的迭代过程如下：

首先，初始随机选择各参数的值。然后，重复下述俩步，直到收敛。

E步骤。计算当前的参数，计算每个点由某个分模型生成的概率。

M步骤。使用E步骤估计出的概率，来改进每个分模型的均值，方差和权重。

2 基于期望最大值的初始中心估算方法

通过计算得到合适瞭望样本，以瞭望样本的角度获得全部样本与瞭望样本间距离，根据距离估算可能的初始聚类中心，一次获得全部聚类中心并作为迭代计算的开始，逐步获得更精确的聚类中心。其过程为，根据样本 X = ｛ x1, x2,… , xn｝，簇数k，瞭望长度ξ，丢弃因子c。首先计算瞭望样本，瞭望值结合瞭望长度ξ给出实际瞭望样本值o；然后基于瞭望样本计算整体样本下的距离值D，根据距离分布调整瞭望长度ξ，再计算并更新丢弃因子c下新的距离D。利用最大期望算法估计高斯混合分布下距离数据中参数μ的取值，计算μ在D中的最邻近位置，返回对应位置的样本编号更新初始聚类中心。最后以现有初始聚类中心开始聚类，首先计算样本归属再计算样本归属关心下新的聚类中心，重复计算直到收敛或达到某一次数。

算法如下：

算法

输入：样本集 X = ｛ x1, x2,… , xn｝，簇数k，瞭望长度ξ，丢弃因子c。

输出：簇划分 C = ｛c1, c2,… ,ck｝

过程：

1. 从D中随机选择k个样本作为初始均值向量 ｛μ1, μ2,… ,μk｝

2. repeat

3. 随机选择瞭望样本o

4. for j = 1,2,… ,mdo

5. 计算其余样本到瞭望样本的距离，根据距离估算初始聚类中心 c1；

6. 结合瞭望长度ξ给出实际瞭望样本值o;

7. 计算整体样本下的距离值D，根据距离分布调整瞭望长度，再计算并更新丢弃因子c下新的距离D；

8. 计算μ在D中的最邻近位置，返回对应位置的样本编号更新初始聚类中心；

2.1 均值计算过程

设簇1,2,…,k服从均值不同，方差相同的高斯分布，基于欧式距离计算得到全部样本点到现有聚类中心的距离 D = ｛ d1, d2,… dn｝，可知距离D服从高斯混合分布，如图1。

图1 簇为4时初始中心与样本的距离分布Fig.1 The distance between the initial center and the sample when the cluster is 4

在方差一定得情况下各簇内均值不同，设总样本 为 N = ｛ x1, x2,… ,xn｝， xi表 示 为 一 个 k +1元 组＜xi, zi1, zi2,… ,zik＞，元组元素只有一个取 1，其余的为0。且此处 zi1到 zik为隐藏变量，为未知，对任意 zij被选择的概率相等，即：

由高斯混合分布的一般定义，似然函数及其参数：

σ2, … ,σ2,}，随之定义与观测数据有关的隐变量：2k Z→X，令隐变量的后验分布q（ Z）表示服从高斯混合分布聚类中每个数据来源于第 c ∈ ｛ 1, 2, … ,k ｝个分布的概率，π为高斯分布的混合比例，k为参与混合的分布总数则因变量有离散取值 Z = ｛ z1, z2,… ,zk｝。

E步：使用假设和观测数据估计概率分布

M步：对E步输出的隐变量后验分布计算模型参数，得到优化问题的计算框架

重复以上两步直至收敛，得参数 μ1, μ2,… ,μk的估计值。

2.2 定义瞭望样本

瞭望样本作为观测整体样本的哨兵为整体样本距离计算提供较好的计算角度，减少距离重叠提高距离分布清晰度，瞭望样本定义为：

其中n为样本维度， m ax （ Xk）为k维时样本中最大的值，ξ为瞭望长度。

2.3 局部降噪

对于部分不规则样本带来的噪声干扰，可选择的引入丢弃因子c,（ c ∈ ［ 0,1）），将距离过近和距离太远的数据以适当比例置零，降低离群点对整体聚类的影响，同时提高正常样本中聚类中心被正确选择的概率，定义：

其中c为丢弃因子，1cd-为去噪后的样本距离。

3 结果分析

为了验证算法有效性，实验采用高斯混合分布下2000个方差0.3的样本数据，参考均一性和完整，利用v-measure作为衡量指标：

其中h为均一性，表示一个簇中只包含一个类别的样本；c为完整性，表示同类样本被归类到同一簇中。多次聚类效果对比如下，图2图3分别为K-means++和EMK-means++。

通过实验可知，多次聚类达到 v-measure指标1.0的成功次数比K-means++为0.78，EMK-means++为 0.89，后者明显降低了陷入局部最优概率，提升了整体聚类效果。

图2 K-means++Fig.2 K-means++

图3 EMK-means++Fig.3 EMK-means++

4 结束语

本文提出了一种基于最大期望估算初始样本中心的聚类算法，结合瞭望值估算高斯混合分布下距离数据的初始样本中心，为后续迭代计算提供了较可靠的样本中心位置，降低了迭代次数和时间开销，提高计算效率，提升了整体聚类效果。本文的局限性主要在方法对于数据的分布，瞭望样本的选取以及部分参数初值的设定较为敏感，这也是下一步的主要研究内容。