来源：简单、流行、机器学习

介绍：

前面介绍的最小距离分类法和最大似然分类法在分类前需要一些已知的标记样本作为训练数据，然后训练模型。 最后，该模型可用于对未知类别进行分类。 样本的分类称为监督分类。 监督分类）又称训练场法，是一种以建立统计识别函数为理论基础，基于典型样本训练方法进行分类的技术[1]。

监督分类的对应部分是无监督分类。 无监督分类是指人们事先不将任何先验知识应用到分类过程中，而仅仅依靠数据，即自然聚类的特征，来进行“盲目”分类； 分类的结果只是区分不同的类别，但无法确定类别的属性[2]。

虽然在无监督分类的结果中，我们无法知道分类后的类别属于哪个类别，但是在无监督分类完成之后，我们往往可以根据经验来判断每个类别属于哪个类别。 或者有时候，我们只需要使用这个无监督分类的结果，而不用担心这个分类的每个类别属于什么类别。

对于监督分类，前面介绍了两种基本方法。 对于无监督分类，基本方法是K-Means分类方法。

基本的：

K-Means算法以距离作为相似度的评价指标，以样本点到类别中心的误差平方和作为聚类质量的评价指标。 它采用迭代的方法来实现总体分类误差平方和最小的聚类函数。 方法[3]。

假设我们有一个数据集(x1,x2,...,xn)，每个xi都是一个d维特征向量。现在，我们需要将这个数据集分为k个不同的类别

其中，类别Si中所有元素到类别中心Ui的距离平方和为

，（前面的最小距离分类介绍了不同的距离计算方法，这里为了表达简单，用欧式距离代替一般的距离）我们最终分类的目的是让得到的k个类别的距离平方和总和值最小，有点绕。 在数值模型中，可以表示为以下表达式[4]：

有了目标函数，现在的问题就很明确了：求这k个类别中心的具体值

，最小化上述表达式的值。

这是一个求最大值的问题。 当你遇到求最大值的问题时，你是否立即想到求最大值的拉格朗日法？ 不幸的是，对于这个目标函数，我们无法通过求出目标函数的导数并使其等于0来获得这些参数（如果将公式展开，可以直观地看到即使求出导数，使其等于0 ，并且该方程的参数无法求解）。

那么如何解决这个问题呢？ 于是乎，有人提出了基于迭代思想的解决方案：先随机给出初始类别中心，然后进行聚类。 通过迭代，不断调整这些类别中心，直到得到最佳的聚类中心。 。

算法步骤如下：

1. 从集合(x1,x2,…,xn)中随机选择k个元素作为k个类别各自的中心。

2. 聚类。 计算集合中每个元素与k个类别中心的距离，并将这些元素分配给距离最小的类别。 这个过程实际上是一个重新聚类的过程。

3.更新品类中心。 根据之前的聚类结果，取出当前类别中的所有元素，然后计算这些元素在每个维度上的平均值，重新计算每个类别的中心。 每个类别中心重新计算后，得到一个新的类别中心组。

4. 重复步骤2和3，直到聚类结果不再变化。 这样得到的类别中心基本上就是我们最终想要找到的类别中心。

图例解释：

如下图，就是一个K-Means分类过程。 图中，二维空间（x，y）中有一些点。 我们可以将这些点的x，y坐标视为一些样本的二维特征，然后我们需要对这些二维特征进行K-。 无监督分类均值，假设我们要将这些点分为三类，流程描述如下：

（1）图1显示，在特征空间中，选择了三个中心作为初始类别中心，分别用红色、绿色和蓝色表示。

（2）图2是一次迭代后的结果，即最小距离分类后，然后计算每个类别的期望，以及最大化期望的过程。 哈哈，听起来有点学术。 换句话说，一次迭代会执行以下操作：

Ø对所有样本点的最小距离进行分类；

Ø分类完成后，重新计算每个类别中的特征均值，并用这个特征均值向量替代之前的样本中心。

(3) 图3是3次迭代的结果。

(4) 图4是6次迭代的结果，也是最终的分类结果。 这一步的图片和图3的差别很小，只有类别和类别中心有很小的变化。

图 1. 初始状态 图 2. 一次迭代后

图 3. 三次迭代后 图 4. 六次迭代后的最终结果

直观上来说，上面K-Means寻找最终类别中心的思路还是比较容易理解的。 那么有人可能会问：从数学公式可以推导出来吗？ 通过这样的迭代，目标函数可以为

达到最低限度？

答案是肯定的，因为K-Means迭代实际上应用了EM（期望最大化）的思想，而EM的原理可以用数学公式来证明。 但由于K-means的原理比较简单易懂，所以在介绍K-means时，一般不会解释EM算法的原理，以免把简单的问题复杂化。 以后介绍EM或者GMM的时候，可以回去对比一下K-Means的原理。

K-means的缺点：

K-Means的原理很容易理解，并且在聚类时采用最小距离分类方法，计算也比较简单。 然而，K-Means也有其固有的缺点：

K-Means的初始类别中心是随机选择的，初始类别中心对整体分类结果和计算时间有很大影响。 如果初始类别中心不好，算法可能会陷入局部极小值，得到次优的分类结果，而得不到全局最优解[4]。 另外，如果初始的类别中心不好，也会增加迭代次数。 这增加了分类所花费的时间。

针对随机设置类别中心的缺点，许多人提出了K-Means的改进方法，例如在设置初始类别中心时使用GA遗传算法进行选择[5]； 或者徐一峰等人提出的初始类别中心的选择。 方法[6]。

K-Means 算法对异常值很敏感。 因为相似度度量是基于某个样本到类别中心的距离，而类别中心也是利用属于当前类别的所有样本的均值来计算的，所以如果整体样本中存在噪声点或者孤立点设定点，那么必然会影响最终的分类结果。

参考：

[1] 百度百科-监督分类

[2] 百度百科-无监督分类

[3]百度百科-K-means

[4] 博客园

[5] 博客园

[6]徐一峰，陈春明，徐云清。 一种改进的k-means聚类算法[J]计算机应用与软件2008.3vol.25NO.3:275-277