聚类分析: k-means算法

k-means算法

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

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

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

1. 假设数据集在一个 m 维的欧式空间中，我们初始时，可随机选择 k 个数据项作为这 k 个簇的形心 Ci,i∈{1,2,…k} ，每个簇心代表的其实是一个簇，也就是一组数据项构成的集合。然后对所有的 n 个数据项，计算这些数据项与 Ci 的距离（一般情况下，在欧式空间中，数据项之间的距离用欧式距离表示）。比如对于数据项 Dj,j∈{1,…n} ，它与其中的一个簇心 Ci 最近，则将 Dj 归类为簇 Ci .
2. 通过上面这一步，我们就初步将 D 划分为 k 个类了。现在重新计算这 k 个类的形心。方法是计算类中所有数据项的各个维度的均值。这样，构成一个新的形心，并且更新这个类的形心。每个类都这样计算一次，更新形心。
3. 对上一步计算得到的新的形心，重复进行第（1），（2）步的工作，直到各个类的形心不再变化为止。

下面，通过一个例子，展示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算法作简要分析：

1. 时间复杂度： O(nkt) ，其中， n 为数据项个数， k 为要聚类成的簇数， t 为迭代次数。而通常， k<<n ，所以，对于大数据集，k-means算法相对可伸缩，且有效。
2. 局限性：k-means算法有其相应的局限性，我们必须明白这些缺点，才能避免不正确的使用：
   
   • 只能应用于可计算均值的数据，比如对于一些标称属性的数据，就不能使用k-means。所以，后来人们设计了k-众数算法，来解决对于标称属性数据的聚类;
   • 必须事先给出要生成的簇数 k ，而实际上我们大多时候并不知道这些数据应该生成的簇数，后来ISODATA算法通过类的自动合并和分裂，得到较为合理的类型数目k;
   • 前面已经说过，k-means对于初始点的选择很重要，不同初始点，会导致不同效果的聚类。为了解决这个问题，k-means++算法应运而生。

k-means算法的在线模式

上面介绍的k-means算法是最常见的一种，我们又叫它“批处理模式”，因为每次为数据点分配簇的时候，我们都是将所有的数据点按照当前固定的簇中心分配，最后再统一更新簇中心。

现在我简单介绍一种效果更好的k-means算法，也被称为“k-means算法的在线模式”。它比“批处理”模式更适用于一般的文本数据聚类。

在线模式的基本思路与原始的批处理方法非常相近。唯一不同的一点是在对于每个数据点分配簇之后，立即更新簇中心，然后调整分配结果，直到簇中心不改变为止。在处理下一个数据点。工作原理可以分为以下三步：

• 随机选择 k 个数据点作为簇中心；
• 依次遍历每个数据点，每一次遍历（设当前遍历到的数据点为 Di ）执行下面两步操作：
  
  1. 计算得到距离 Di 最近的簇心，将 Di 分配给这个簇；
  2. 立即更新簇心（其实，全部的 k 个簇中，只有这一个簇需要更新簇心）
  3. 循环执行前两步，直到簇心不再改变位置（此时，这个数据点属于哪个簇其实固定了）
• 遍历完所有的数据点，也就完成了聚类；

k-means++算法

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

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

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

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

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

1. 对已经选出作为簇心的 r 个点（ r<k ），计算数据集中每个数据项应该归类的簇，以及距离
2. 将这 n 个距离求和，得到sum(Dis_i)，然后随机选取一个小于sum(Dis_i)的值Random
3. 令Random依次减去 Disi ，Random -= Disi ，直到Random <= 0为止，此时，Random减去的 Disi 所对应的数据项就是新的簇心。

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

1. 随机选择一个数据项，作为第一个簇心
2. 根据选择下一个簇心的操作方法（上面列出的3步），选择下一簇心
3. 重复步骤2，直到得到全部的 k 个簇心

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

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