Cluster：K-means Algorithm

Cluster:K-means Algorithm

 

K-means算法算是Clustering算法中最为简单的算法了，我们从最简单的算法开始学习。

K-means的算法思路很简单，根据算法名字所描述的那样，K是系统的输入参数，表明我们想分簇的数量；首先随机选择K个初始点作为中心点(Centroid)，再将每个数据点赋给离其最近的簇，然后更新簇的中心点；直到中心点不再变化为止。

 

K-means的正式描述见下图：

1：选择K个数据点作为初始化的中心点(Centroid)

2、3、4：数据迭代，将数据赋给最近的中心点，重新计算簇的中心点

5：直到簇中心点不再变化；也可以说簇内的数据不再更新。

 

上面提到的算法结果是比较强的收敛条件，即簇内数据不再转移；对于类似算法(Proximity Algorithm)或者收敛条件比较弱的话，可以将收敛条件弱化：如只有少量(1%)的数据点转移等即可认为收敛。对于Proximity Algorithm我记得有本书专门论述这个情况，大家可以自行查找下。

 

我们来深入的学习一下K-means算法的步骤，首先先看下初始化数据点的选择：

在初始化数据点时，我们会首先选择K个数据点作为Centroid中心点。这一步是basic K-means算法的关键步骤，初始化中心点得选择会最终影响到Clustering结果的好坏。

1：随机选择：算计选择初始化中心点对于大多数正常的数据都是个简单的方法，但是这个方法有很大的问题，就是得到的误差值SSE比较大，结果不是令人满意。

2：多次运行数据集合，选择最小的SSE的分簇结果作为最终结果。该方法依赖于数据集合和簇数量，对分簇结果有比较大影响，所以在某些场景下效果也不是很好。

3：抽取数据集合样本，对样本进行Hierarchical Clustering技术，从中抽取K个Clustering作为初始中心点。该方法工作良好，知识有两点限制条件：抽样数据不能太大，因为Hierarchical Clustering比较耗时间；K值相对于抽样数据比较小才行。

4：随机选择收个中心点或者选择所有数据的中心点，然后在每次中心点迭代过程中，选择距离已经选择的中心点最远的点作为新添的中心点。该方法能够既能保证距离又能保证分布，不过该方法有可能会选择到离散值(Outliar)，计算最远的点也比较耗费时间，通常的做法是将该过程应用于数据集合的采样样本上。样本数据采集到离散值的概率比较小，另外计算最远距离的点得计算量也小许多。

 

看完数据初始化后，我们来看下将数据点赋给最近的簇中心点(Centroid)过程：

有最近的概念，就得有衡量最近的概念。关于距离的定义，可以参考这里http://isilic.iteye.com/blog/1816986，一般来说，我们使用Euclidean Distance(L2)来衡量Euclidean空间的数据，使用Cosine Similarity来衡量Document数据；对于给定类型的数据还有其他的衡量方法，如Manhattan Distance(L1)衡量Euclidean空间的数据，或者Jaccard Similarity作用于文档数据等。

定义了距离的概念之后，在Euclidean空间中，我们使用定义(Sum of the Square Error)来作为Clustering结果的误差度量，看下这个度量的公式：

其中涉及到的参数概念如下：

 如果是对文档数据求相似性的话，就可以使用cosine similarity：

 解决完数据初始值和数据赋予簇中心点过程问题后，我们来看下额外需要关注的几个问题：

1：处理空簇数据，即簇中没有数据的情况。

对于出现这种情况，可以使用随机选取任意簇(非空)中最远的点作为当前空簇的中心点；或者在当前具有最大SSE的簇中选择最远距离值作为当前空簇的中心点。这两种做法都是减小了总体的SSE，如果有多个空簇的话，针对每一个空簇执行上面的两种方法之一，重复多次，消除空簇。

 

2：Outliar值

当使用SSE误差作为衡量标准是，Outliar(离散值)能够在很大程度上影响最终的分簇结果；尤其是在Outliar被偶然选中作为clustering中心点的时候。所以在这种聚类过程中，离散值希望能够在与处理中就能找出来并且排除掉。但是在某些应用中，离散值是必须存在的，如数据压缩；在某些应用中，离散值是人们感兴趣的数据，如金融分析等。

离散值识别就是很明显的一个问题了，有大量的技术来用来识别离散值。很明显，这是另外一个话题了，大家可以自行学习下。

 

3：PostProcessing

我们对K-means的期望是使用固定的K来对数据进行分簇，使得分簇结果的SSE尽可能的小，也就是分簇尽可能的准确，前面提到的多次跑数据来避免局部最小值，但实际上还是有可能多次跑数据的结果还是局部最优值，这就需要使用额外的技术来在单词数据运行中就能尽可能的跳出局部最优，而不是通过对此运行数据来解决问题。在单次数据运行中我们引入PostProcessing(后置处理)迭代功能来期望解决问题。

在PostProcessing过程中，引入切割(Splitting)和合并(Merging)阶段来降低最终分簇结果的SSE：

Splitting：该阶段是添加新簇，通过增加新簇来降低总SSE误差。方法一拆分最大SSE或者最大标准偏差的簇；方法二引入新簇，新簇的中心点设定为任意簇中的最远距离，或者是从最高SSE的点集合中随机选择点作为新簇的中心点。

Merging：合并过程，在该阶段合并簇数据。方法一是重新分布Cluster中的数据，将该簇数据打散分散至其它簇中；方法二是合并两个簇中的数据，簇选择可以使簇中心点最为接近的两个簇进行合并，更好的选择选择使得总SSE有最小增加的簇进行合并

 

4：增量更新中心点

基本K-means做法是在迭代过程中，所有数据点赋予簇之后全量更新簇的中心点。其实说如果数据点没有更新的话，是不用重新计算簇中心点的。如果数据点的归属簇有更新的话，需要同时更新两个簇(源簇和目标簇)的中心点。这种操作的话会有更好的精度和更快的收敛速度。不过这种增量更新的最大问题是数据点的更新顺序，数据点的处理顺序有可能决定了最终的分簇结果。

 

时间和空间复杂度分析：

基础K-Means算法的空间和时间分析都比较简单，因为只有数据点和簇中心点需要保存，再加上数据点与簇的对应关系。空间需求为O((m+K)n)，其中：

m为数据点

K为分簇点

n为数据的空间数

时间需求为O(I*K*m*n),其中I为数据迭代次数；一般来说，迭代次数I都比较小。

 

优点分析：

1：简单，算法直观，一目了然，学习难度不大。

2：适用于各种数据集合

3：有效，运行效率高，能很快就得到记过，是数据集合数目的线性增长。

这三个优点足够支持K-Means算法的使用范围了。

 

缺点：

1：不能处理非球形数据、数据大小和密度不同的分簇也无能为力，需要其它算法完善，这个也是K-Means的硬伤。

2：不能处理包含离散值(Outliers)的数据集合，需要Outlier Detection配合。

3：K-Means要求数据集合需要有Center(Centroid)的概念，如果数据集合没有中心点的概念，K-Means也无能为力，不过K-Memoid算法没有这个限制，只是效率比K-Means低。

 

 

K-Means算法的最直接扩展就是Bisecting K-Means算法。Bisecting K-Means算法的思路很简单，先将数据集合分成两个簇，然后选择其中的一个簇进行拆分，重复进行直到产生K个簇为止。

算法细节如下：

 算法的关键点在待拆分的簇的选择上：选择簇内数据量最大的簇去拆分；选择最大的SSE误差；或者两者兼而有之。

Bisecting K-Means算法的思路比较简单，不在赘述。

 

上面了解了很多K-Means算法的优劣、时间和空间分析、算法考虑的问题等，下面我们直接给出来K-Means算法的实现，大家可以参考下；你也可以直接在上面修改算法实现细节，进而实现自己的算法：

 

function kmeans(points, k, distance, snapshotPeriod, snapshotCb) {
   distance = distance || "euclidean";
   if (typeof distance == "string") {
      distance = distances[distance];
   }
   
   var centroids = randomCentroids(points, k);
   var assignment = new Array(points.length);
   var clusters = new Array(k);

   var iterations = 0;   
   var movement = true;
   while (movement) {
      // update point-to-centroid assignments
      for (var i = 0; i < points.length; i++) {
         assignment[i] = closestCentroid(points[i], centroids, distance);
      }

      // update location of each centroid
      movement = false;
      for (var j = 0; j < k; j++) {
         var assigned = [];
         assignment.forEach(function(centroid, index) {
            if (centroid == j) {
               assigned.push(points[index]);
            }
         });

         if (!assigned.length) {
            continue;
         }
         var centroid = centroids[j];
         var newCentroid = new Array(centroid.length);

         for (var g = 0; g < centroid.length; g++) {
            var sum = 0;
            for (var i = 0; i < assigned.length; i++) {
               sum += assigned[i][g];
            }
            newCentroid[g] = sum / assigned.length;
            
            if (newCentroid[g] != centroid[g]) {
               movement = true;
            }
         }
         centroids[j] = newCentroid;
         clusters[j] = assigned;
      }
   }
   return clusters;
}

 

算法实现来自这里：http://harthur.github.com/clusterfck/demos/colors/

 

本文牵扯到的理论不多，大部分是结论，所以信息量比较大。如果有人对K-Means算法的基础感兴趣，如为什么要使用最小SSE误差来衡量分簇效果，为什么要使用Euclidean(L2)距离来衡量距离，为什么也能使用Manhattan(L1)距离来衡量点之间的距离。如果有这些疑问的话，可以参考Introduction to Data Mining这本书的第八章节，里面最后又单独部分来解决这些疑问；如果你对这些不感兴趣的话，可以直接略过这些内容。