文档章节

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

东方神剑
 东方神剑
发布于 2014/11/13 14:38
字数 2050
阅读 81
收藏 2

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 聚类算法。

本文转载自:http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy3/index.html

共有 人打赏支持
东方神剑

东方神剑

粉丝 64
博文 126
码字总数 93166
作品 0
朝阳
程序员
探索推荐引擎内部的秘密,第 3 部分: 深入推荐引擎相关算法 - 聚类(四)

狄利克雷聚类算法 前面介绍的三种聚类算法都是基于划分的,下面我们简要介绍一个基于概率分布模型的聚类算法,狄利克雷聚类(Dirichlet Processes Clustering)。 首先我们先简要介绍一下基于...

东方神剑
2014/11/13
0
0
探索推荐引擎内部的秘密,第 2 部分: 深入推荐引擎相关算法 - 协同过滤(二)

基于 Apache Mahout 实现高效的协同过滤推荐 Apache Mahout 是 Apache Software Foundation (ASF) 旗下的一个开源项目,提供一些可扩展的机器学习领域经典算法的实现,旨在帮助开发人员更加方...

东方神剑
2014/11/13
0
0
探索推荐引擎内部的秘密,第 3 部分: 深入推荐引擎相关算法 - 聚类

聚类分析 什么是聚类分析? 聚类 (Clustering) 就是将数据对象分组成为多个类或者簇 (Cluster),它的目标是:在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。所以,在很...

Endeavour
2015/08/12
0
0
探索推荐引擎内部的秘密,第 3 部分: 深入推荐引擎相关算法 - 聚类(一)

聚类分析 什么是聚类分析? 聚类 (Clustering) 就是将数据对象分组成为多个类或者簇 (Cluster),它的目标是:在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。所以,在很...

东方神剑
2014/11/13
0
0
探索推荐引擎内部的秘密,第 3 部分: 深入推荐引擎相关算法 - 聚类 (三)

Canopy 聚类算法 Canopy 聚类算法的基本原则是:首先应用成本低的近似的距离计算方法高效的将数据分为多个组,这里称为一个 Canopy,我们姑且将它翻译为“华盖”,Canopy 之间可以有重叠的部...

东方神剑
2014/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Shell编程(expect同步文件、指定host和同步文件、构建文件分发系统、批量执行命令)

expect脚本同步文件 需求:自动同步文件 实验准备: A机器:192.168.248.130 B机器:192.168.248.129 实现: 1.A机器编写4.expect脚本文件,内容如下所示: #!/usr/bin/expectset passwd "...

蛋黄_Yolks
18分钟前
1
0
ppwjs之bootstrap颜色:背景颜色

<!DOCTYPT html><html><head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>ppwjs欢迎您</title><link rel="icon" href="/favicon.ico" ......

ppwjs
18分钟前
0
0
Ubuntu与 Fedora之对比

大家好。今天我将重点介绍两个流行的Linux发行版之间的一些特性和差异; Ubuntu 18.04和Fedora 28。它们都有自己的包管理; Ubuntu使用DEB,而Fedora使用RPM,但它们都具有相同的桌面环境(GNO...

linuxprobe16
22分钟前
1
0
线性代数入门

线性代数的概念对于理解机器学习背后的原理非常重要,尤其是在深度学习领域中。它可以帮助我们更好地理解算法内部到底是怎么运行的,借此,我们就能够更好的做出决策。所以,如果你真的希望了...

牛奋Debug
昨天
3
0
开发5分钟,调试2小时 - 该如何debug?

几年来我在答疑群、论坛、公众号、知乎回答的各种问题,没有一万也有八千。其中有三分之二以上都是在帮人看报错,帮人 debug(调试代码)。 可以说,会不会 debug,有没有 debug 的意识,懂不...

crossin
昨天
4
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部