K 均值聚类算法

K 均值是典型的基于距离的排他的划分方法：给定一个 n 个对象的数据集，它可以构建数据的 k 个划分，每个划分就是一个聚类，并且 k<=n，同时还需要满足两个要求：

• 每个组至少包含一个对象

• 每个对象必须属于且仅属于一个组。

K 均值的基本原理是这样的，给定 k，即要构建的划分的数目，

1. 首先创建一个初始划分，随机地选择 k 个对象，每个对象初始地代表了一个簇中心。对于其他的对象，根据其与各个簇中心的距离，将它们赋给最近的簇。

2. 然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。所谓重定位技术，就是当有新的对象加入簇或者已有对象离开簇的时候，重新计算簇的平均值，然后对对象进行重新分配。这个过程不断重复，直到没有簇中对象的变化。

当结果簇是密集的，而且簇和簇之间的区别比较明显时，K 均值的效果比较好。对于处理大数据集，这个算法是相对可伸缩的和高效的，它的复杂度是 O(nkt)，n 是对象的个数，k 是簇的数目，t 是迭代的次数，通常 k<<n，且 t<<n，所以算法经常以局部最优结束。

K 均值的最大问题是要求用户必须事先给出 k 的个数，k 的选择一般都基于一些经验值和多次实验结果，对于不同的数据集，k 的取值没有可借鉴性。另外，K 均值对“噪音”和孤立点数据是敏感的，少量这类的数据就能对平均值造成极大的影响。

说了这么多理论的原理，下面我们基于 Mahout 实现一个简单的 K 均值算法的例子。如前面介绍的，Mahout 提供了基本的基于内存的实现和基于 Hadoop 的 Map/Reduce 的实现，分别是 KMeansClusterer 和 KMeansDriver，下面给出一个简单的例子，就基于我们在清单 1 里定义的二维点集数据。

清单 3. K 均值聚类算法示例

// 基于内存的 K 均值聚类算法实现
 public static void kMeansClusterInMemoryKMeans(){ 

 // 指定需要聚类的个数，这里选择 2 类
 int k = 2; 

 // 指定 K 均值聚类算法的最大迭代次数
 int maxIter = 3; 

 // 指定 K 均值聚类算法的最大距离阈值
 double distanceThreshold = 0.01; 

 // 声明一个计算距离的方法，这里选择了欧几里德距离
 DistanceMeasure measure = new EuclideanDistanceMeasure(); 

 // 这里构建向量集，使用的是清单 1 里的二维点集
 List<Vector> pointVectors = SimpleDataSet.getPointVectors(SimpleDataSet.points); 

 // 从点集向量中随机的选择 k 个作为簇的中心
 List<Vector> randomPoints = RandomSeedGenerator.chooseRandomPoints(pointVectors, k); 

 // 基于前面选中的中心构建簇
 List<Cluster> clusters = new ArrayList<Cluster>(); 

 int clusterId = 0; 

 for(Vector v : randomPoints){ 

 clusters.add(new Cluster(v, clusterId ++, measure)); 

 } 

 // 调用 KMeansClusterer.clusterPoints 方法执行 K 均值聚类
 List<List<Cluster>> finalClusters = KMeansClusterer.clusterPoints(pointVectors, 

 clusters, measure, maxIter, distanceThreshold); 

 // 打印最终的聚类结果
 for(Cluster cluster : finalClusters.get(finalClusters.size() -1)){ 

 System.out.println("Cluster id: " + cluster.getId() + 

" center: " + cluster.getCenter().asFormatString()); 

 System.out.println("       Points: " + cluster.getNumPoints());  

 } 

 } 

 // 基于 Hadoop 的 K 均值聚类算法实现
 public static void kMeansClusterUsingMapReduce () throws Exception{ 

 // 声明一个计算距离的方法，这里选择了欧几里德距离
 DistanceMeasure measure = new EuclideanDistanceMeasure(); 

 // 指定输入路径，如前面介绍的一样，基于 Hadoop 的实现就是通过指定输入输出的文件路径来指定数据源的。
 Path testpoints = new Path("testpoints"); 

 Path output = new Path("output"); 

 // 清空输入输出路径下的数据
 HadoopUtil.overwriteOutput(testpoints); 

 HadoopUtil.overwriteOutput(output); 

 RandomUtils.useTestSeed(); 

 // 在输入路径下生成点集，与内存的方法不同，这里需要把所有的向量写进文件，下面给出具体的例子
 SimpleDataSet.writePointsToFile(testpoints); 

 // 指定需要聚类的个数，这里选择 2 类
 int k = 2; 

 // 指定 K 均值聚类算法的最大迭代次数
 int maxIter = 3; 

 // 指定 K 均值聚类算法的最大距离阈值
 double distanceThreshold = 0.01; 

 // 随机的选择 k 个作为簇的中心
 Path clusters = RandomSeedGenerator.buildRandom(testpoints, 

 new Path(output, "clusters-0"), k, measure); 

 // 调用 KMeansDriver.runJob 方法执行 K 均值聚类算法
 KMeansDriver.runJob(testpoints, clusters, output, measure, 

 distanceThreshold, maxIter, 1, true, true); 

 // 调用 ClusterDumper 的 printClusters 方法将聚类结果打印出来。
 ClusterDumper clusterDumper = new ClusterDumper(new Path(output, 

"clusters-" + maxIter -1), new Path(output, "clusteredPoints")); 

 clusterDumper.printClusters(null); 

 } 

 //SimpleDataSet 的 writePointsToFile 方法，将测试点集写入文件里
 // 首先我们将测试点集包装成 VectorWritable 形式，从而将它们写入文件
 public static List<VectorWritable> getPoints(double[][] raw) { 

 List<VectorWritable> points = new ArrayList<VectorWritable>(); 

 for (int i = 0; i < raw.length; i++) { 

 double[] fr = raw[i]; 

 Vector vec = new RandomAccessSparseVector(fr.length); 

 vec.assign(fr); 

 // 只是在加入点集前，在 RandomAccessSparseVector 外加了一层 VectorWritable 的包装
 points.add(new VectorWritable(vec)); 

 } 

 return points; 

 } 

 // 将 VectorWritable 的点集写入文件，这里涉及一些基本的 Hadoop 编程元素，详细的请参阅参考资源里相关的内容
 public static void writePointsToFile(Path output) throws IOException { 

 // 调用前面的方法生成点集
 List<VectorWritable> pointVectors = getPoints(points); 

 // 设置 Hadoop 的基本配置
 Configuration conf = new Configuration(); 

 // 生成 Hadoop 文件系统对象 FileSystem 

 FileSystem fs = FileSystem.get(output.toUri(), conf); 

 // 生成一个 SequenceFile.Writer，它负责将 Vector 写入文件中
 SequenceFile.Writer writer = new SequenceFile.Writer(fs, conf, output, 

 Text.class,  VectorWritable.class); 

 // 这里将向量按照文本形式写入文件
 try { 

 for (VectorWritable vw : pointVectors) { 

 writer.append(new Text(), vw); 

 } 

 } finally { 

 writer.close(); 

 }  

 } 

执行结果
 KMeans Clustering In Memory Result 

 Cluster id: 0 

 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
"vector":"{\"values\":{\"table\":[0,1,0],\"values\":[1.8,1.8,0.0],\"state\":[1,1,0],
\"freeEntries\":1,\"distinct\":2,\"lowWaterMark\":0,\"highWaterMark\":1,
\"minLoadFactor\":0.2,\"maxLoadFactor\":0.5},\"size\":2,\"lengthSquared\":-1.0}"} 

       Points: 5 

 Cluster id: 1 

 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
 "vector":"{\"values\":{\"table\":[0,1,0],
 \"values\":[7.142857142857143,7.285714285714286,0.0],\"state\":[1,1,0],
 \"freeEntries\":1,\"distinct\":2,\"lowWaterMark\":0,\"highWaterMark\":1,
 \"minLoadFactor\":0.2,\"maxLoadFactor\":0.5},\"size\":2,\"lengthSquared\":-1.0}"} 

       Points: 7 

 KMeans Clustering Using Map/Reduce Result 

 Weight:  Point: 

 1.0: [1.000, 1.000] 

 1.0: [2.000, 1.000] 

 1.0: [1.000, 2.000] 

 1.0: [2.000, 2.000] 

 1.0: [3.000, 3.000] 

 Weight:  Point: 

 1.0: [8.000, 8.000] 

 1.0: [9.000, 8.000] 

 1.0: [8.000, 9.000] 

 1.0: [9.000, 9.000] 

 1.0: [5.000, 5.000] 

 1.0: [5.000, 6.000] 

 1.0: [6.000, 6.000]

介绍完 K 均值聚类算法，我们可以看出它最大的优点是：原理简单，实现起来也相对简单，同时执行效率和对于大数据量的可伸缩性还是较强的。然而缺点也是很明确的，首先它需要用户在执行聚类之前就有明确的聚类个数的设置，这一点是用户在处理大部分问题时都不太可能事先知道的，一般需要通过多次试验找出一个最优的 K 值；其次就是，由于算法在最开始采用随机选择初始聚类中心的方法，所以算法对噪音和孤立点的容忍能力较差。所谓噪音就是待聚类对象中错误的数据，而孤立点是指与其他数据距离较远，相似性较低的数据。对于 K 均值算法，一旦孤立点和噪音在最开始被选作簇中心，对后面整个聚类过程将带来很大的问题，那么我们有什么方法可以先快速找出应该选择多少个簇，同时找到簇的中心，这样可以大大优化 K 均值聚类算法的效率，下面我们就介绍另一个聚类方法：Canopy 聚类算法。

探索推荐引擎内部的秘密，第 3 部分: 深入推荐引擎相关算法 - 聚类（二）