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
1700535323
图5.4 K均值算法中K值的选取：Gap Statistic方法
1700535324
1700535325
（3）采用核函数。
1700535326
1700535327
采用核函数是另一种可以尝试的改进方向。传统的欧式距离度量方式，使得K均值算法本质上假设了各个数据簇的数据具有一样的先验概率，并呈现球形或者高维球形分布，这种分布在实际生活中并不常见。面对非凸的数据分布形状时，可能需要引入核函数来优化，这时算法又称为核K均值算法，是核聚类方法的一种[6]。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。
1700535328
1700535329
问题3 针对K均值算法的缺点，有哪些改进的模型？
1700535330
1700535331
难度：★★★☆☆
1700535332
1700535333
分析与解答
1700535334
1700535335
K均值算法的主要缺点如下。
1700535336
1700535337
（1）需要人工预先确定初始K值，且该值和真实的数据分布未必吻合。
1700535338
1700535339
（2）K均值只能收敛到局部最优，效果受到初始值很大。
1700535340
1700535341
（3）易受到噪点的影响。
1700535342
1700535343
（4）样本点只能被划分到单一的类中。
1700535344
1700535345
■ K-means++算法
1700535346
1700535347
K均值的改进算法中，对初始值选择的改进是很重要的一部分。而这类算法中，最具影响力的当属K-means++算法。原始K均值算法最开始随机选取数据集中K个点作为聚类中心，而K-means++按照如下的思想选取K个聚类中心。假设已经选取了n个初始聚类中心（0
1700535348
1700535349
■ ISODATA算法
1700535350
1700535351
当K值的大小不确定时，可以使用ISODATA算法。ISODATA的全称是迭代自组织数据分析法。在K均值算法中，聚类个数K的值需要预先人为地确定，并且在整个算法过程中无法更改。而当遇到高维度、海量的数据集时，人们往往很难准确地估计出K的大小。ISODATA算法就是针对这个问题进行了改进，它的思想也很直观。当属于某个类别的样本数过少时，把该类别去除；当属于某个类别的样本数过多、分散程度较大时，把该类别分为两个子类别。ISODATA算法在K均值算法的基础之上增加了两个操作，一是分裂操作，对应着增加聚类中心数；二是合并操作，对应着减少聚类中心数。ISODATA算法是一个比较常见的算法，其缺点是需要指定的参数比较多，不仅仅需要一个参考的聚类数量Ko，还需要制定3个阈值。下面介绍ISODATA算法的各个输入参数。
1700535352
1700535353
（1）预期的聚类中心数目Ko。在ISODATA运行过程中聚类中心数可以变化，Ko是一个用户指定的参考值，该算法的聚类中心数目变动范围也由其决定。具体地，最终输出的聚类中心数目常见范围是从Ko的一半，到两倍Ko。
1700535354
1700535355
（2）每个类所要求的最少样本数目Nmin。如果分裂后会导致某个子类别所包含样本数目小于该阈值，就不会对该类别进行分裂操作。
1700535356
1700535357
（3）最大方差Sigma。用于控制某个类别中样本的分散程度。当样本的分散程度超过这个阈值时，且分裂后满足（1），进行分裂操作。
1700535358
1700535359
（4）两个聚类中心之间所允许最小距离Dmin。如果两个类靠得非常近（即这两个类别对应聚类中心之间的距离非常小），小于该阈值时，则对这两个类进行合并操作。
1700535360
1700535361
如果希望样本不划分到单一的类中，可以使用模糊C均值或者高斯混合模型，高斯混合模型会在下一节中详细讲述。
1700535362
1700535363
问题4 证明K均值算法的收敛性。
1700535364
1700535365
难度：★★★★☆
1700535366