文档章节

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

东方神剑
 东方神剑
发布于 2014/11/13 14:38
字数 2050
阅读 83
收藏 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

共有 人打赏支持
东方神剑

东方神剑

粉丝 65
博文 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 部分: 深入推荐引擎相关算法 - 聚类 (三)

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

东方神剑
2014/11/13
0
0
探索推荐引擎内部的秘密,第 1 部分: 推荐引擎初探

信息发现 如今已经进入了一个数据爆炸的时代,随着 Web 2.0 的发展, Web 已经变成数据分享的平台,那么,如何让人们在海量的数据中想要找到他们需要的信息将变得越来越难。 在这样的情形下,...

东方神剑
2014/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

微服务分布式事务实现

https://www.processon.com/view/link/5b2144d7e4b001a14d3d2d30

WALK_MAN
今天
2
0
《大漠烟尘》读书笔记及读后感文章3700字

《大漠烟尘》读书笔记及读后感文章3700字: 在这个浮躁的社会里,你有多久没有好好读完一本书了? 我们总觉得自己和别人不一样,所以当看到别人身上的问题时,很少有“反求诸己”,反思自己。...

原创小博客
今天
3
0
大数据教程(9.5)用MR实现sql中的jion逻辑

上一篇博客讲解了使用jar -jar的方式来运行提交MR程序,以及通过修改YarnRunner的源码来实现MR的windows开发环境提交到集群的方式。本篇博主将分享sql中常见的join操作。 一、需求 订单数据表...

em_aaron
今天
3
0
十万个为什么之什么是resultful规范

起源 越来越多的人开始意识到,网站即软件,而且是一种新型的软件。这种"互联网软件"采用客户端/服务器模式,建立在分布式体系上,通过互联网通信,具有高延时(high latency)、高并发等特点...

尾生
今天
3
0
Terraform配置文件(Terraform configuration)

Terraform配置文件 翻译自Terraform Configuration Terraform用文本文件来描述设备、设置变量。这些文件被称为Terraform配置文件,以.tf结尾。这一部分将讲述Terraform配置文件的加载与格式。...

buddie
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部