文档章节

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

东方神剑
 东方神剑
发布于 2014/11/13 14:38
字数 2050
阅读 78
收藏 1
点赞 0
评论 0

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

© 著作权归作者所有

共有 人打赏支持
东方神剑

东方神剑

粉丝 63
博文 126
码字总数 93166
作品 0
朝阳
程序员
协同过滤和推荐引擎简介

推荐系统在个性化领域有着广泛的应用,从技术上讲涉及概率、抽样、最优化、机器学习、数据挖掘、搜索引擎、自然语言处理等多个领域。东西太多,我也不准备写连载,今天仅从基本算法这个很小的...

xrzs ⋅ 2013/06/18 ⋅ 0

探索推荐引擎内部的秘密,第 2 部分: 深入推荐引擎相关算法 - 协同过滤(二)

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

东方神剑 ⋅ 2014/11/13 ⋅ 0

Apache Mahout中推荐算法Slope one源码分析

关于推荐引擎 如今的互联网中,无论是电子商务还是社交网络,对数据挖掘的需求都越来越大了,而推荐引擎正是数据挖掘完美体现;通过分析用户历史行为,将他可能喜欢内容推送给他,能产生相当...

Breath_L ⋅ 2012/02/11 ⋅ 6

探索推荐引擎内部的秘密,第 1 部分: 推荐引擎初探

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

东方神剑 ⋅ 2014/11/13 ⋅ 0

机器学习(Machine Learning)&深入学习(Deep Learning)资料

《Brief History of Machine Learning》 介绍:这是一篇介绍机器学习历史的文章,介绍很全面,从感知机、神经网络、决策树、SVM、Adaboost到随机森林、Deep Learning. 《Deep Learning in Ne...

JDquant ⋅ 2017/08/03 ⋅ 0

推荐机制 协同过滤和基于内容推荐的区别

参考ibm文章 https://www.ibm.com/developerworks/cn/web/1103zhaoctrecommstudy1/index.html 该系列分为三部分 第 2 部分: 深入推荐引擎相关算法 - 协同过滤 第 3 部分: 深入推荐引擎相关算...

liaomin416100569 ⋅ 04/13 ⋅ 0

机器学习在热门微博推荐中的应用

近年来,机器学习在搜索、广告、推荐等领域取得了非常突出的成果,成为最引人注目的技术热点之一。微博也在机器学习方面做了广泛的探索,其中在推荐领域,将机器学习技术应用于微博最主要的产...

技术小能手 ⋅ 02/08 ⋅ 0

探索推荐引擎内部的秘密,第 2 部分: 深入推荐引擎相关算法 - 协同过滤

集体智慧和协同过滤 什么是集体智慧 集体智慧 (Collective Intelligence) 并不是 Web2.0 时代特有的,只是在 Web2.0 时代,大家在 Web 应用中利用集体智慧构建更加有趣的应用或者得到更好的用...

Endeavour ⋅ 2015/08/12 ⋅ 0

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

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

东方神剑 ⋅ 2014/11/13 ⋅ 0

0到1再到100 蘑菇街搜索与推荐架构的探索之路

丁小明,花名小宝,蘑菇街搜索技术团队负责人。2011年底加入蘑菇街,2013年开始负责搜索团队,见证了蘑菇街一路蓬勃发展的历程,也和团队一起从零起步摸爬滚打,打造了蘑菇街的搜索推荐体系,...

雪夜凋零 ⋅ 2017/07/28 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周三乱弹 —— 这样的女人私生活太混乱了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 胖达panda :你经历过体验到人生的大起大落吗?我一朋友在10秒内体验了,哈哈。@小小编辑 请点一首《almost lover》送给他。 《almost love...

小小编辑 ⋅ 28分钟前 ⋅ 5

自己动手写一个单链表

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号:好好学java,获取优质学习资源。 一、概述 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对...

公众号_好好学java ⋅ 33分钟前 ⋅ 0

Centos7重置Mysql 8.0.1 root 密码

问题产生背景: 安装完 最新版的 mysql8.0.1后忘记了密码,向重置root密码;找了网上好多资料都不尽相同,根据自己的问题总结如下: 第一步:修改配置文件免密码登录mysql vim /etc/my.cnf 1...

豆花饭烧土豆 ⋅ 今天 ⋅ 0

熊掌号收录比例对于网站原创数据排名的影响[图]

从去年下半年开始,我在写博客了,因为我觉得业余写写博客也还是很不错的,但是从2017年下半年开始,百度已经推出了原创保护功能和熊掌号平台,为此,我也提交了不少以前的老数据,而这些历史...

原创小博客 ⋅ 今天 ⋅ 0

LVM讲解、磁盘故障小案例

LVM LVM就是动态卷管理,可以将多个硬盘和硬盘分区做成一个逻辑卷,并把这个逻辑卷作为一个整体来统一管理,动态对分区进行扩缩空间大小,安全快捷方便管理。 1.新建分区,更改类型为8e 即L...

蛋黄Yolks ⋅ 今天 ⋅ 0

Hadoop Yarn调度器的选择和使用

一、引言 Yarn在Hadoop的生态系统中担任了资源管理和任务调度的角色。在讨论其构造器之前先简单了解一下Yarn的架构。 上图是Yarn的基本架构,其中ResourceManager是整个架构的核心组件,它负...

p柯西 ⋅ 今天 ⋅ 0

uWSGI + Django @ Ubuntu

创建 Django App Project 创建后, 可以看到路径下有一个wsgi.py的问题 uWSGI运行 直接命令行运行 利用如下命令, 可直接访问 uwsgi --http :8080 --wsgi-file dj/wsgi.py 配置文件 & 运行 [u...

袁祾 ⋅ 今天 ⋅ 0

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

推荐:并发情况下:Java HashMap 形成死循环的原因

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历...

码代码的小司机 ⋅ 昨天 ⋅ 2

聊聊spring cloud gateway的RetryGatewayFilter

序 本文主要研究一下spring cloud gateway的RetryGatewayFilter GatewayAutoConfiguration spring-cloud-gateway-core-2.0.0.RC2-sources.jar!/org/springframework/cloud/gateway/config/G......

go4it ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部