K-Means聚类

到目前为止，我们花了大量的笔墨在有监督算法的学习上。它们有标签、典型，也易于理解。那么下面我们将要开始介绍无监督学习算法，它们没有标签。

无监督学习主要有两大类，聚类和降维。我们先介绍几种常用的聚类的算法，这一篇先来看K-Means算法。

K-Means算法流程

假设我们有一个数据集D，即

我们的目的是什么呢？是将这个数据集分成K类，或者说分成K个簇。我们设簇的集合为C，那么C=。

下面是K-Means算法的步骤：

·        步骤1

从数据D中随机选取K个样本，作为聚类中心，我们设这K个中心分别为。

·        步骤2

计算数据D中每个样本到这K个中心的距离，即

我们一般用L2范数，也叫欧式距离来计算。在计算出距离之后，把每个样本点划分到最近的中心点。

·        步骤3

对于这K个簇，重新计算它们的中心点。

·        步骤4

重复步骤2和步骤3，直到中心点不再发生变化，或者达到我们所需的迭代次数。最后输出分类好的K个簇，即C=。

K-Means关键点

1.K值的选择

通常情况下，K值是人为设定的。因为我们事先并不知道数据能分成几个簇，因此只能靠人工来判断。

2.中心点的选择

一般我们随机来选择K个中心点，但这并不是最好的方法，后面我们会介绍优化的方法。

3.距离的度量

这里我们一般用欧式距离来度量，上文有介绍过。

4.损失函数

假设所有的样本点被分成了K个簇，那么每个簇的中心点向量为

因此，K个簇的总的均方误差就是

我们的目标就是最小化这个误差E。

算法优化

1.K个中心点的选择

前面我们介绍到，随机选取中心点并不是一个很好的方法。这里有一种改进的方法，叫做k-means++方法。这种方法的步骤是这样的：

·        步骤1

从所有样本点中随机选取1个作为中心点，我们记为m1。计算其他所有的样本点到中心点m的距离，选择距离最远的那个样本点作为第二个新的聚类中心m2。

·        步骤2

计算所有样本点到这两个中心点m1和m2的距离，将样本归类到靠近它们的中心点。

·        步骤3

把到中心点距离最远的那个样本再次作为新的中心点。

·        步骤4

重复步骤2和步骤3，直到达到K个中心点。此时，我们就可以用上文介绍过的算法流程进行运算。

2.大量数据的情况

当样本量数据非常大时，由于我们的算法要计算每个样本到中心点的距离，因此不可避免的会发生耗时长、计算量大等状况。为了解决这个问题，有人提出了Mini Batch K-Means算法。

这种算法的原理也很简单，就是对原始的大样本进行随机不放回采样，然后对每个采样进行K-Means聚类。为了提高准确性，通常要进行多次采样和多次聚类，最后选取最合适的簇来进行分类。