1700535273
对于每一个类簇k，重新计算该类簇的中心 ．
1700535274
1700535275
（5.3）
1700535276
1700535277
K均值算法在迭代时，假设当前 J 没有达到最小值，那么首先固定簇中心{μk}，调整每个样例xi所属的类别ci来让J函数减少；然后固定{ci}，调整簇中心{μk}使J减小。这两个过程交替循环，J单调递减：当J递减到最小值时，{μk}和{ci}也同时收敛。
1700535278
1700535279
图5.2是K-means算法的一个迭代过程示意图。首先，给定二维空间上的一些样本点（见图5.2（a）），直观上这些点可以被分成两类；接下来，初始化两个中心点（图5.2（b）的棕色和黄色叉子代表中心点），并根据中心点的位置计算每个样本所属的簇（图5.2（c）用不同颜色表示）；然后根据每个簇中的所有点的平均值计算新的中心点位置（见图5.2（d））；图5.2（e）和图5.2（f）展示了新一轮的迭代结果；在经过两轮的迭代之后，算法基本收敛。
1700535280
1700535281
1700535282
1700535283
1700535284
图5.2 K均值聚类算法的迭代过程示意图
1700535285
1700535286
问题2 K均值算法的优缺点是什么？如何对其进行调优？
1700535287
1700535288
难度：★★★☆☆
1700535289
1700535290
分析与解答
1700535291
1700535292
K均值算法有一些缺点，例如受初值和离群点的影响每次的结果不稳定、结果通常不是全局最优而是局部最优解、无法很好地解决数据簇分布差别比较大的情况（比如一类是另一类样本数量的100倍）、不太适用于离散分类等。但是瑕不掩瑜，K均值聚类的优点也是很明显和突出的，主要体现在：对于大数据集，K均值聚类算法相对是可伸缩和高效的，它的计算复杂度是O(NKt)接近于线性，其中N是数据对象的数目，K是聚类的簇数，t是迭代的轮数。尽管算法经常以局部最优结束，但一般情况下达到的局部最优已经可以满足聚类的需求。
1700535293
1700535294
K均值算法的调优一般可以从以下几个角度出发。
1700535295
1700535296
（1）数据归一化和离群点处理。
1700535297
1700535298
K均值聚类本质上是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性的影响，所以未做归一化处理和统一单位的数据是无法直接参与运算和比较的。同时，离群点或者少量的噪声数据就会对均值产生较大的影响，导致中心偏移，因此使用K均值聚类算法之前通常需要对数据做预处理。
1700535299
1700535300
（2）合理选择K值。
1700535301
1700535302
K值的选择是K均值聚类最大的问题之一，这也是K均值聚类算法的主要缺点。实际上，我们希望能够找到一些可行的办法来弥补这一缺点，或者说找到K值的合理估计方法。但是，K值的选择一般基于经验和多次实验结果。例如采用手肘法，我们可以尝试不同的K值，并将不同K值所对应的损失函数画成折线，横轴为K的取值，纵轴为误差平方和所定义的损失函数，如图5.3所示。
1700535303
1700535304
1700535305
1700535306
1700535307
图5.3 K均值算法中K值的选取：手肘法
1700535308
1700535309
1700535310
由图可见，K值越大，距离和越小；并且，当K=3时，存在一个拐点，就像人的肘部一样；当K(1,3)时，曲线急速下降；当K>3时，曲线趋于平稳。手肘法认为拐点就是K的最佳值。
1700535311
1700535312
手肘法是一个经验方法，缺点就是不够自动化，因此研究员们又提出了一些更先进的方法，其中包括比较有名的Gap Statistic方法[5]。Gap Statistic方法的优点是，不再需要肉眼判断，而只需要找到最大的Gap statistic所对应的K即可，因此该方法也适用于批量化作业。在这里我们继续使用上面的损失函数，当分为K簇时，对应的损失函数记为Dk。Gap Statistic定义为
1700535313
1700535314
Gap(K)=E(logDk)−logDk ，
1700535315
1700535316
（5.4）
1700535317
1700535318
其中E(logDk)是logDk的期望，一般通过蒙特卡洛模拟产生。我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做K均值，得到一个Dk；重复多次就可以计算出E(logDk)的近似值。那么Gap(K)有什么物理含义呢？它可以视为随机样本的损失与实际样本的损失之差。试想实际样本对应的最佳簇数为K，那么实际样本的损失应该相对较小，随机样本损失与实际样本损失之差也相应地达到最小值，从而Gap(K)取得最大值所对应的K值就是最佳的簇数。根据式（5.4）计算K =1,2,…,9所对应的Gap Statistic，如图5.4所示。由图可见，当K=3时，Gap(K)取值最大，所以最佳的簇数是K=3。
1700535319
1700535320
1700535321
1700535322