K 均值是典型的基于距离的排他的划分方法：给定一个 n 个对象的数据集，它可以构建数据的 k 个划分，每个划分就是一个聚类，并且 k<=n，同时还需要满足两个要求：
每个组至少包含一个对象
每个对象必须属于且仅属于一个组。
K 均值的基本原理是这样的，给定 k，即要构建的划分的数目，
首先创建一个初始划分，随机地选择 k 个对象，每个对象初始地代表了一个簇中心。对于其他的对象，根据其与各个簇中心的距离，将它们赋给最近的簇。
然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。所谓重定位技术，就是当有新的对象加入簇或者已有对象离开簇的时候，重新计算簇的平均值，然后对对象进行重新分配。这个过程不断重复，直到没有簇中对象的变化。
当结果簇是密集的，而且簇和簇之间的区别比较明显时，K 均值的效果比较好。对于处理大数据集，这个算法是相对可伸缩的和高效的，它的复杂度是 O(nkt)，n 是对象的个数，k 是簇的数目，t 是迭代的次数，通常 k<<n，且 t<<n，所以算法经常以局部最优结束。
K 均值的最大问题是要求用户必须事先给出 k 的个数，k 的选择一般都基于一些经验值和多次实验结果，对于不同的数据集，k 的取值没有可借鉴性。另外，K 均值对“噪音”和孤立点数据是敏感的，少量这类的数据就能对平均值造成极大的影响。
说了这么多理论的原理，下面我们基于 Mahout 实现一个简单的 K 均值算法的例子。如前面介绍的，Mahout 提供了基本的基于内存的实现和基于 Hadoop 的 Map/Reduce 的实现，分别是 KMeansClusterer 和 KMeansDriver，下面给出一个简单的例子，就基于我们在清单 1 里定义的二维点集数据。
// 基于内存的 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 部分: 深入推荐引擎相关算法 - 聚类（二）
原文：http://my.oschina.net/dfsj66011/blog/343969