1700535358
1700535359
（4）两个聚类中心之间所允许最小距离Dmin。如果两个类靠得非常近（即这两个类别对应聚类中心之间的距离非常小），小于该阈值时，则对这两个类进行合并操作。
1700535360
1700535361
如果希望样本不划分到单一的类中，可以使用模糊C均值或者高斯混合模型，高斯混合模型会在下一节中详细讲述。
1700535362
1700535363
问题4 证明K均值算法的收敛性。
1700535364
1700535365
难度：★★★★☆
1700535366
1700535367
分析与解答
1700535368
1700535369
首先，我们需要知道K均值聚类的迭代算法实际上是一种最大期望算法（Expectation-Maximization algorithm），简称EM算法。EM算法解决的是在概率模型中含有无法观测的隐含变量情况下的参数估计问题。假设有m个观察样本，模型的参数为θ，最大化对数似然函数可以写成如下形式
1700535370
1700535371
1700535372
．
1700535373
1700535374
（5.5）
1700535375
1700535376
当概率模型中含有无法被观测的隐含变量时，参数的最大似然估计变为
1700535377
1700535378
1700535379
．
1700535380
1700535381
（5.6）
1700535382
1700535383
1700535384
1700535385
由于z(i)是未知的，无法直接通过最大似然估计求解参数，这时就需要利用EM算法来求解。假设z(i)对应的分布为，并满足。利用Jensen不等式，可以得到
1700535386
1700535387
1700535388
1700535389
1700535390
1700535391
．
1700535392
1700535393
（5.7）
1700535394
1700535395
1700535396
1700535397
1700535398
要使上式中的等号成立，需要满足，其中c为常数，且满足；因此，，不等式右侧函数记为r(x|θ)。当等式成立时，我们相当于为待优化的函数找到了一个逼近的下界，然后通过最大化这个下界可以使得待优化函数向更好的方向改进。
1700535399
1700535400
1700535401
1700535402
图5.5是一个θ为一维的例子，其中棕色的曲线代表我们待优化的函数，记为f(θ)，优化过程即为找到使得f(θ)取值最大的θ。在当前θ的取值下（即图中绿色的位置），可以计算，此时不等式右侧的函数（记为r(x|θ)）给出了优化函数的一个下界，如图中蓝色曲线所示，其中在θ处两条曲线的取值时相等的。接下来找到使得r(x|θ)最大化的参数θ′，即图中红色的位置，此时f(θ′)的取值比f(θ)（绿色的位置处）有所提升。可以证明，f(θ′)≥r(x|θ)=f(θ)，因此函数是单调的，而且从而函数是有界的。根据函数单调有界必收敛的性质，EM算法的收敛性得证。但是EM算法只保证收敛到局部最优解。当函数为非凸时，以图5.5为例，如果初始化在左边的区域时，则无法找到右侧的高点。
1700535403
1700535404
1700535405
1700535406
1700535407
图5.5 K均值算法的收敛性