文档章节

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

东方神剑
 东方神剑
发布于 2014/11/13 14:48
字数 2276
阅读 291
收藏 4
点赞 0
评论 0

狄利克雷聚类算法

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

首先我们先简要介绍一下基于概率分布模型的聚类算法(后面简称基于模型的聚类算法)的原理:首先需要定义一个分布模型,简单的例如:圆形,三角形等,复杂的例如正则分布,泊松分布等;然后按照模型对数据进行分类,将不同的对象加入一个模型,模型会增长或者收缩;每一轮过后需要对模型的各个参数进行重新计算,同时估计对象属于这个模型的概率。所以说,基于模型的聚类算法的核心是定义模型,对于一个聚类问题,模型定义的优劣直接影响了聚类的结果,下面给出一个简单的例子,假设我们的问题是将一些二维的点分成三组,在图中用不同的颜色表示,图 A 是采用圆形模型的聚类结果,图 B 是采用三角形模型的聚类结果。可以看出,圆形模型是一个正确的选择,而三角形模型的结果既有遗漏又有误判,是一个错误的选择。

图 3 采用不同模型的聚类结果

图 3 采用不同模型的聚类结果

Mahout 实现的狄利克雷聚类算法是按照如下过程工作的:首先,我们有一组待聚类的对象和一个分布模型。在 Mahout 中使用 ModelDistribution 生成各种模型。初始状态,我们有一个空的模型,然后尝试将对象加入模型中,然后一步一步计算各个对象属于各个模型的概率。下面清单给出了基于内存实现的狄利克雷聚类算法。

清单 6. 狄利克雷聚类算法示例
 public static void DirichletProcessesClusterInMemory() { 
 // 指定狄利克雷算法的 alpha 参数,它是一个过渡参数,使得对象分布在不同模型前后能进行光滑的过渡
	 double alphaValue = 1.0; 
 // 指定聚类模型的个数
	 int numModels = 3; 
 // 指定 thin 和 burn 间隔参数,它们是用于降低聚类过程中的内存使用量的
	 int thinIntervals = 2; 
	 int burnIntervals = 2; 
 // 指定最大迭代次数
	 int maxIter = 3; 
	 List<VectorWritable> pointVectors = 
	 SimpleDataSet.getPoints(SimpleDataSet.points); 
 // 初始阶段生成空分布模型,这里用的是 NormalModelDistribution 
	 ModelDistribution<VectorWritable> model = 
 new NormalModelDistribution(new VectorWritable(new DenseVector(2))); 
 // 执行聚类
	 DirichletClusterer dc = new DirichletClusterer(pointVectors, model, alphaValue, 
 numModels, thinIntervals, burnIntervals); 
	 List<Cluster[]> result = dc.cluster(maxIter); 
 // 打印聚类结果
	 for(Cluster cluster : result.get(result.size() -1)){ 
		 System.out.println("Cluster id: " + cluster.getId() + " center: " + 
 cluster.getCenter().asFormatString()); 
		 System.out.println("       Points: " + cluster.getNumPoints()); 	
	 } 
 } 

执行结果
 Dirichlet Processes Clustering In Memory Result 
 Cluster id: 0 
 center:{"class":"org.apache.mahout.math.DenseVector",
 "vector":"{\"values\":[5.2727272727272725,5.2727272727272725],
 \"size\":2,\"lengthSquared\":-1.0}"} 
       Points: 11 
 Cluster id: 1 
 center:{"class":"org.apache.mahout.math.DenseVector",
 "vector":"{\"values\":[1.0,2.0],\"size\":2,\"lengthSquared\":-1.0}"} 
       Points: 1 
 Cluster id: 2 
 center:{"class":"org.apache.mahout.math.DenseVector",
 "vector":"{\"values\":[9.0,8.0],\"size\":2,\"lengthSquared\":-1.0}"} 
       Points: 0

Mahout 中提供多种概率分布模型的实现,他们都继承 ModelDistribution,如图 4 所示,用户可以根据自己的数据集的特征选择合适的模型,详细的介绍请参考 Mahout 的官方文档。

图 4 Mahout 中的概率分布模型层次结构

图 4 Mahout 中的概率分布模型层次结构

Mahout 聚类算法总结

前面详细介绍了 Mahout 提供的四种聚类算法,这里做一个简要的总结,分析各个算法优缺点,其实,除了这四种以外,Mahout 还提供了一些比较复杂的聚类算法,这里就不一一详细介绍了,详细信息请参考 Mahout Wiki 上给出的聚类算法详细介绍。

表 1 Mahout 聚类算法总结
算法 内存实现 Map/Reduce 实现 簇个数是确定的 簇是否允许重叠
K 均值 KMeansClusterer KMeansDriver Y N
Canopy CanopyClusterer CanopyDriver N N
模糊 K 均值 FuzzyKMeansClusterer FuzzyKMeansDriver Y Y
狄利克雷 DirichletClusterer DirichletDriver N Y

回页首

总结

聚类算法被广泛的运用于信息智能处理系统。本文首先简述了聚类概念与聚类算法思想,使得读者整体上了解聚类这一重要的技术。然后从实际构建应用的角度出发,深入的介绍了开源软件 Apache Mahout 中关于聚类的实现框架,包括了其中的数学模型,各种聚类算法以及在不同基础架构上的实现。通过代码示例,读者可以知道针对他的特定的数据问题,怎么样向量化数据,怎么样选择各种不同的聚类算法。

本系列的下一篇将继续深入了解推荐引擎的相关算法 -- 分类。与聚类一样,分类也是一个数据挖掘的经典问题,主要用于提取描述重要数据类的模型,随后我们可以根据这个模型进行预测,推荐就是一种预测的行为。同时聚类和分类往往也是相辅相成的,他们都为在海量数据上进行高效的推荐提供辅助。所以本系列的下一篇文章将详细介绍各类分类算法,它们的原理,优缺点和实用场景,并给出基于 Apache Mahout 的分类算法的高效实现。

最后,感谢大家对本系列的关注和支持。

参考资料

学习

  • 聚类分析:Wikipedia 上关于聚类分析的介绍

  • 数据挖掘:概念与技术(韩家伟):关于数据挖掘的经典著作,详细介绍了数据挖掘领域的各种问题和应用,其中对聚类分析的经典算法也有详尽的讲解。

  • 数据挖掘:实用机器学习技术:同样是数据挖掘的经典著作,对领域内的算法,算法的发展进行了详细的介绍。

  • Apache Mahout简介” (Grant Ingersoll,developerWorks,2009 年 10 月):Mahout 的创始者 Grant Ingersoll 介绍了机器学习的基本概念,并演示了如何使用 Mahout 来实现文档集群、提出建议和组织内容。

  • Apache Mahout:Apache Mahout 项目的主页,搜索关于 Mahout 的所有内容。

  • Apache Mahout算法总结:Apache Mahout 的 Wiki 上关于实现算法的详细介绍。

  • Mahout In Action:Sean Owen 详细介绍了 Mahout 项目,其中有很大篇幅介绍了 Mahout 提供的聚类算法,并给出一些简单的例子。

  • TF-IDF:Wikipedia 上关于 TF-IDF 的详细介绍,包括它的计算方法,优缺点,应用场景等。

  • 路透数据集:路透提供了大量的新闻数据集,可以作为聚类分析的数据源,本文中对文本聚类分析的部分采用了路透“Reuters-21578”数据集

  • Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching,发表于 2000 的 Canopy 算法的论文。

  • 狄利克雷分布:Wikipedia 上关于狄利克雷分布的介绍,它是本文介绍的狄利克雷聚类算法的基础

  • 基于Apache Mahout构建社会化推荐引擎:笔者 09 年发布的一篇关于基于 Mahout 实现推荐引擎的 developerWorks 文章,其中详细介绍了 Mahout 的安装步骤,并给出一个简单的电影推荐引擎的例子。

  • 机器学习:机器学习的 Wikipedia 页面,可帮助您了解关于机器学习的更多信息。

  • developerWorks Java技术专区:数百篇关于 Java 编程各个方面的文章。

  • developerWorks Web development 专区:通过专门关于 Web 技术的文章和教程,扩展您在网站开发方面的技能。

  • developerWorks Ajax 资源中心:这是有关 Ajax 编程模型信息的一站式中心,包括很多文档、教程、论坛、blog、wiki 和新闻。任何 Ajax 的新信息都能在这里找到。

  • developerWorks Web 2.0 资源中心,这是有关 Web 2.0 相关信息的一站式中心,包括大量 Web 2.0 技术文章、教程、下载和相关技术资源。您还可以通过 Web 2.0 新手入门 栏目,迅速了解 Web 2.0 的相关概念。

  • 查看 HTML5 专题,了解更多和 HTML5 相关的知识和动向。

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

共有 人打赏支持
东方神剑

东方神剑

粉丝 64
博文 126
码字总数 93166
作品 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
Apache Mahout中推荐算法Slope one源码分析

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

Breath_L
2012/02/11
0
6
探索推荐引擎内部的秘密,第 1 部分: 推荐引擎初探

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

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

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

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

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

东方神剑
2014/11/13
0
0
机器学习(Machine Learning)&深入学习(Deep Learning)资料

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

JDquant
2017/08/03
0
0
推荐机制 协同过滤和基于内容推荐的区别

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

liaomin416100569
04/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

about git flow

  昨天元芳做了git分支管理规范的分享,为了拓展大家关于git分支的认知,这里我特意再分享这两个关于git flow的链接,大家可以看一下。 Git 工作流程 Git分支管理策略   git flow本质上是...

qwfys
今天
1
0
Linux系统日志文件

/var/log/messages linux系统总日志 /etc/logrotate.conf 日志切割配置文件 参考https://my.oschina.net/u/2000675/blog/908189 dmesg命令 dmesg’命令显示linux内核的环形缓冲区信息,我们可...

chencheng-linux
今天
1
0
MacOS下给树莓派安装Raspbian系统

下载镜像 前往 树莓派官网 下载镜像。 点击 最新版Raspbian 下载最新版镜像。 下载后请,通过 访达 双击解压,或通过 unzip 命令解压。 检查下载的文件 ls -lh -rw-r--r-- 1 dingdayu s...

dingdayu
今天
0
0
spring boot使用通用mapper(tk.mapper) ,id自增和回显等问题

最近项目使用到tk.mapper设置id自增,数据库是mysql。在使用通用mapper主键生成过程中有一些问题,在总结一下。 1、UUID生成方式-字符串主键 在主键上增加注解 @Id @GeneratedValue...

北岩
今天
2
0
告警系统邮件引擎、运行告警系统

告警系统邮件引擎 cd mail vim mail.py #!/usr/bin/env python#-*- coding: UTF-8 -*-import os,sysreload(sys)sys.setdefaultencoding('utf8')import getoptimport smtplibfr......

Zhouliang6
今天
0
0
Java工具类—随机数

Java中常用的生成随机数有Math.random()方法及java.util.Random类.但他们生成的随机数都是伪随机的. Math.radom()方法 在jdk1.8的Math类中可以看到,Math.random()方法实际上就是调用Random类...

PrivateO2
今天
1
0
关于java内存模型、并发编程的好文

Java并发编程:volatile关键字解析    volatile这个关键字可能很多朋友都听说过,或许也都用过。在Java 5之前,它是一个备受争议的关键字,因为在程序中使用它往往会导致出人意料的结果。在...

DannyCoder
昨天
0
0
dubbo @Reference retries 重试次数 一个坑

在代码一中设置 成retries=0,也就是调用超时不用重试,结果DEBUG的时候总是重试,不是0吗,0就不用重试啊。为什么还是调用了多次呢? 结果在网上看到 这篇文章才明白 https://www.cnblogs....

奋斗的小牛
昨天
2
0
数据结构与算法3

要抓紧喽~~~~~~~放羊的孩纸回来喽 LowArray类和LowArrayApp类 程序将一个普通的Java数组封装在LowArray类中。类中的数组隐藏了起来,它是私有的,所以只有类自己的方法才能访问他。 LowArray...

沉迷于编程的小菜菜
昨天
0
0
spring boot应用测试框架介绍

一、spring boot应用测试存在的问题 官方提供的测试框架spring-boot-test-starter,虽然提供了很多功能(junit、spring test、assertj、hamcrest、mockito、jsonassert、jsonpath),但是在数...

yangjianzhou
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部