打字猴:1.700535351e+09

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

1700535367 分析与解答

1700535368

1700535369 首先，我们需要知道K均值聚类的迭代算法实际上是一种最大期望算法（Expectation-Maximization algorithm），简称EM算法。EM算法解决的是在概率模型中含有无法观测的隐含变量情况下的参数估计问题。假设有m个观察样本，模型的参数为θ，最大化对数似然函数可以写成如下形式

1700535370

1700535371