聚类分析: k-means算法

k-means算法

聚类分析是数据分析中，非常重要的一类课题。他的作用是将大量的无标签数据通过计算，自动为其标注标签。众所周知，这一点是区别于数据分类技术的。而现实的场景中，无标签的数据显然多于有标签数据，因此，我在这里也是先说聚类，后面的博文，再说分类。

聚类的目的，是要将数据归为不同的类，基本原则是要相近的数据尽量归为一类，而不同类之间的数据则要尽量有比较大的差别。

说到聚类，当然最先想到的就是k-means算法。它不仅是最简单的聚类算法，也是最普及且最常用的。k-means算法是一种基于形心的划分数据的方法。我们给定一个数据集D$D$，以及要划分的簇数k$k$，就能通过该算法将数据集划分为k$k$个簇。一般来说，每个数据项只能属于其中一个簇。具体方法可以这样描述：

下面，通过一个例子，展示k-means的细节。

我们来处理一个简单的二维平面上的聚类问题。数据集为：A1(2, 10), A2(2, 5), A3(8, 4), B1(5, 8), B2(7, 5), B3(6, 4), C1(1, 2), C2(4,9)，如图Fig.1:

现在，我们选择：A1, B1, C1三个点作为初始的簇心，将这个数据集分成三类。

第一步，令所有数据点选择距离他们最近的簇心，并且执行归类：归类的结果如图Fig.1中虚线所圈出来的那样：

第二步，更新簇心，重新计算距离，再次执行归类，结果如图Fig.2所示，图中,我用红色*号表示簇心：

第三步，重复进行前两步，直到簇心不在变更为止，最终，得到Fig.3中所示的聚类结果，图中,我用红色*号表示簇心：

可见，整个算法就是一个迭代的过程。需要注意的是，初始簇心的选择有时候会影响最终的聚类结果，所以，实际操作中，我们一般会选用不同的数据作为初始簇心，多次执行k-means算法。

由于篇幅限制，详细的实现代码我在我的github主页中给出：kmeans，这里省略。

最后，我们对k-means算法作简要分析：

k-means++算法

k-means++是k-means的变形，通过小心选择初始簇心，来获得较快的收敛速度以及聚类结果的质量，本文中，我们将简单介绍k-means++. 首先，一定要先理解k-means++的原理。

它是这样去做的：先随机选择一个数据项作为第一个初始的簇心（当然，最终我们要选择k$k$个），根据这1个簇心，我们通过一系列计算，获得第2个簇心，再根据这2个簇心，通过计算获得第3个簇心。。。以此类推，最终，获得全部的k$k$个簇心，然后，再按照上面k-means的做法，做聚类分析。其中，至于下一个簇心的选择需要经过怎样的计算，我们放到后面再说。现在需要明白的是，通过增加合理计算的方式，我们不再是随机选取k$k$个簇心作为初始值，而是通过一种迭代算法，合理选择簇心。

那么究竟怎样的选择就是合理的选择呢？在此我们有这样一个原则：假设现在已经选择了r$r$个簇心，要接着选取第r+1$r+1$个簇心。那么当然是应该选择距离其簇心较远的数据点当新的簇心。可以脑补这样一个场景：r$r$个簇心，每个数据点都对应着且只对应着一个簇心，这个簇心当然是相对于其他r−1$r-1$个簇心来说，是距离这个数据点最近的。于是每个点，都与其簇心有条连线，连线的长度就是这个数据点到簇心的距离，我们现在要做的，就是选择距离其簇心距离较大的那个数据点。

你可能会说，这个道理很简单，但是应该是选择距离“最大”的才对，为什么选择距离“较大”的呢？那是因为这里面可能会存在数据噪声的问题，也可能由于我们至少第一个簇心的选择还是随机的缘故，导致如果这样每次都“精确”选择，反而最终的聚类效果不佳。所以，一种比较合理的做法是选择“较大”，而非“最大”。当然，从这一点，我们也能看出，k-means++即使比传统的k-means更好，却依然是一种启发式的算法，不能说这种做法最终的结果就一定是最优的。

现在的问题就全部集中在如何选择离簇心距离“较大”的数据点了。假设，现在将所有的数据点与其对应簇心连接，那么会构成n$n$条连线（n$n$是数据项的个数，自己与自己连接的情况，可以看做是构成了一条长度为0的线），我们记这n$n$条连线的长度为Dis1,Dis2,…Disn$Dis_1, Dis_2, /dots Dis_n$，然后把这n$n$条连线按随机的顺序，首尾相连，构成一条长度为∑Disi$/sum{Dis_i}$的连线，然后现在随机抛出一点，落在这条“总线”上，那么显然，落在距离较长的线上的概率更高一些，如Fig.4所示，假设D1,D2,D3$D_1, D_2, D_3$距离其对应簇心的长度分别是1, 2, 3，那当然是落在Dis3$Dis_3$上的概率最高了。选择下一簇心的具体方法操作如下：

综上，k-means++算法步骤如下：

k-means++虽然在初始簇心的选择上比k-means更优，但是依然也有缺陷，比如，下一个簇心的选择总是依赖于已有的簇心，后来k-means||算法，改进了这一缺点，这里就不再做过多介绍了。

k-means++算法和前面k-means算法的全部代码以及测试数据我都放在了github上：kmeans，欢迎参考指正。