级联二步图关系挖掘关键词推荐系统

标签: 推荐系统 机器学习 youtube 二步图 推荐 | 发表时间:2014-02-19 14:38 | 作者:semo2524
出处:http://semocean.com

youtube使用简单的共现思路, 实现视频的高效推荐。 受到该思路的启发, 我们基于百度凤巢广告主在广告库中提交的关键词, 更进一步设计出可级联的二部图关系挖掘算法框架, 实现亿量级关键词, 百万级别用户的高效推荐。 本文即对该算法的实现进行详细介绍。

youtube 推荐算法

首先还是简单介绍下youtube使用的推荐算法。 符合google系一贯的风格, 算法很简单, 数据量很大, 效果很明显。

大家都知道youtube上有N多vedio,而且各种各样档次类型。而youtube将用户的需求分为3类:

  1. 查找具体video。直接通过搜索
  2. 查找某一topic的video。基本也可以通过搜索解决
  3. 没有明确目的, 随便看看打发时间娱乐

youtube算法,主要解决第三个需求, 使用top N方式推荐video供访问者浏览。而youtube的问题是视频数量太多,且视频的兴趣点较为分散(相对的amazon和netflix的需求则较为集中),所以google没有选择高大上的svd等复杂方法,而是简单的共现计算。论文中整个数据流的处理方式, 和传统的搜索引擎, 或是搜索推荐系统还是一致的, 基本分为: 候选的选择(检索系统中叫触发逻)找到可能推荐的候选, 排序(ranking过程)给出最终排序结果,并做top N截断

  • 候选vedio选择

youtube 使用关联规则的形式, 在24小时内所有用户session内找到共同访问(co-visitation)的video vi, vj

并计算,r(vi, vj) = cij/f(vi, vj)   vi, vj的关联程度可以使用该公式计算得出,  分母f最简单的方式就是ci*cj, cij为两个item共同出现的次数。之后根据阈值过滤r(vi, vj)即得到与vi关联的vj。 定义S为用户u看过的种子video集合, 则定义Ri为使用符合条件的r(vi, vj)得到的关联电影集合。

c1

其中Ri为与vi关联的video,则C1(S)为使用种子电影S进行一次关联扩展后的电影集合,则可以定义:

cn

则Cn(S)为种子video集合S进行n次扩展后的video集合。

以上思路虽然简单,但其中包含的一个特性是可以在相关性和种子集合数量间做一个权衡: 使用降低相关性的方法, 换取更多结果。

  • ranking

上述步骤为候选电影的挖掘方法, 之后需要对挖掘出来的种子video进行ranking,例如使用pv排序, 使用, 候选电影与user profile 的相关性等进行ranking。 当然此时还需要注意给出推荐理由(例如根据哪个种子电影进行推荐)以提升采纳率。

二部图实现思路简介

受到youtube二部图的启发, 我们设计开发了级联二部图, 基本思路是使用中间节点, 建立二步节点之间的路径(关系)计算左右两节点的相关性。

  • 二步跳转关系介绍

定义unit为一个凤巢中的单元(可理解为一组相关关键词), unit1与关键词‘礼品’相关, 而‘礼品’与‘礼品快递’关联, 此时通过两次二部图的链接, 即能找到unit1和‘礼品快递’的关联关系。

二部图

该级联二部图有两个特点:

  1. 二部图可以通过中间的节点建立关系: 只要能各自建立两边的节点(例如unit和关键词)与中间节点的关系 ,级联二部图两端,可以不是相同类别的item。例如unit1包含关键词‘礼品’, 而礼品与‘礼品快递’字面相关,则即使不包含‘礼品快递’, 算法仍然能够找到unit1与‘礼品快递’的关系。
  2. 可以进行多步扩展: 和youtube电影推荐算法类似, 该算 法可以由级联二步扩展为级联多步, 当然, 实在牺牲准确性的前提下。

二步图的基本思想, 就是通过中间节点, 建立左右两特定节点之间的路径, 之后根据这些路径及权重, 算出左右两节点的相关性, 思路和random walk中价值传递的思路较为类似: 一个节点的价值, 最终流到那儿, 就说明这两个节点比较接近。

二部图-1

  • 具体挖掘步骤

步骤一:左右节点权重归一化, 可以使用L1-norm,或是L2-norm进行归一化, 之后得到每个左/右节点到中间节点的路径归一化权重。

步骤二:为了避免’哈利波特‘问题, 或我们经常说的’新华字典‘问题, 避免被多数人采用/提交的中间节点,需要对中间节点进行惩罚,降低部分中间节点的权重。

步骤三:计算左节点到右节点一条路径的权重, 路径的权重 = 左边权重 * 右边权重 * 通过惩罚值; 其中左右边权重通过步骤一计算得到, 通过惩罚值通过步骤二得到。

步骤四:根据连接某对左右节点的所有路径计算该对节点的相关性。

由上述4个步骤大家可以看出, 其实该框架和mahout中hadoop item-based 的计算item相似度的流程极为相似, 具体算法可参见mahout源码: mahout推荐算法;但该算法具有很好的扩展性, 就是前边介绍的: 灵活更换左右节点, 即可实现多步级联的推荐。

核心代码示意

具体实现即根据上文四个步骤进行划分, 四个步骤的实现代码可参见下属配置文件:

two_hop

通过conf文件,大家即可了解上述4个步骤的实现, 具体该配置可以参见conf/twohop_bipartite.job.conf

实现效果

经过多次优化, 包含基础数据的清洗, 使用该方法, 客户的覆盖率提升至75.6%, 相关性85%。 且针对一些大客户的需求, 可以放松相关性来进行扩词。

工具使用方法

级联二部图工具使用方法如下:

python ${TWOHOP_MINING_HOME}/script/twohop_mining.py                                                                        -hadoop hadoop_client_path  -inputA input_A_path                                                                                                               -inputB input_B_path                                                                                                                  -output output_path 

注: 该框架依赖于我们自行开发的hadoop任务框架, 所以可能无法完整运行, 但使用者可以将上述4个步骤的hadoop脚本单独抽取出来进行单独运行。

工具代码地址

代码可从我的云盘下载: 级联二部图框架

参考文献:

mahout推荐算法:http://mahout.apache.org/users/recommender/recommender-documentation.html

youtube video推荐算法:Davidson J, Liebald B, Liu J, et al. The YouTube video recommendation system[C]//Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010: 293-296.

百度关键词工具介绍参见:http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596

也可关注我的微博: weibo.com/dustinsea

或是直接访问: http://semocean.com

相关 [级联 关系 关键词] 推荐:

级联二步图关系挖掘关键词推荐系统

- - Dustinsea
youtube使用简单的共现思路, 实现视频的高效推荐. 受到该思路的启发, 我们基于百度凤巢广告主在广告库中提交的关键词, 更进一步设计出可级联的二部图关系挖掘算法框架, 实现亿量级关键词, 百万级别用户的高效推荐. 本文即对该算法的实现进行详细介绍. 首先还是简单介绍下youtube使用的推荐算法.

App Store Top 1000 关键词分析

- - 标点符
做这个分析的主要目的是分析用户的搜索习惯及用户的需求方向,寻找可能的机会. 以下分析是7月初进行的,数据比较老,供参考. 在Top 1000的关键词中,82% 是品牌词,足见品牌(口碑)对应App的下载量还是非常的重要. 而另外18%的非品牌词也展现了一些打造品牌的机会(用户在该品类下还没有产生思维定势,新的App还存在一定的机会),以下为另外18%的非品牌关键词:.

官方媒体谴责新浪微博过滤关键词

- ivan - Solidot
官方媒体新华社-中国网事在腾讯微博发帖谴责新浪微博,指责新浪微博过滤关键词“达芬奇”. 中国网事称,“新浪微博为何助纣为虐. 近一段时间以来,凡是在新浪微博上发布的有关“达芬奇”的帖子都无端被“封杀”:帖子只有自己能看见,而粉丝和公屏都不显示,其中包括新华社中国网事昨日发布的有关帖子. 经过有关交涉后,该微博于12日下午六时左右暂时恢复“达芬奇”这个它们设定的敏感词.

Tango 的蛛丝马迹:关键词是诺基亚,低价…

- SotongDJ - 爱范儿 · Beats of Bits
直到今天为止,关于微软 Windows Phone 演进版本的信息仍然不多,大概的关键词是这么几个:. Mango :今年秋天的重要版本,有数百项更新,已经进入 RTM 阶段. Tango:在 Mango 之后的版本. Apollo:Windows Phone 8 的开发代号. 微软这次的习惯是,开发代号皆以“o”结尾(包括之前的 NoDo).

Google开始审查BitTorrent、RapidShare等关键词

- bubble - Solidot
Google屈从于MPAA和RIAA等的压力,开始在即时搜索和自动完成功能中审查BitTorrent、torrent、utorrent、RapidShare和Megaupload等关键词. 数周前,Google宣布它将在即时搜索和自动完成功能中过滤到与盗版相关的关键词. 26日,在没有发表正式声明的情况下它开始部署这项功能,部分地区的Google用户在搜索框内输入BitTorrent、torrent、utorrent、RapidShare和Megaupload等关键词将不会显示搜索提示.

文本分析漫谈-分类器中的关键词提取

- flychen50 - UGC广播站
作者:人人网UGC团队成员 刘威 人人网UGC团队博客. 面对人人网海量的UGC,数据挖掘工作势在必行,能把用户最想要的信息推荐出来,是我们正在研究的课题之一. 在推荐系统中,分类器是个非常重要的部分. 分类器的研究重点落在两个方面,一方面是文本关键词的提取,一方面是对已有关键词或标签的文本进行训练分类.

未来互联网的六大关键词 你猜到几个?

- Googmr - cnBeta.COM
如果让你挑选六个词汇来描述互联网的未来,你会选哪几个词呢?美国《连线》杂志创办人、绰号“资深独行侠”的凯文・凯利就在年度NExTWORK技术大会上选出了他描绘互联网未来主要趋势的六大关键词,并认为互联网正在加速向视频、移动和云发展. 下面就是凯利所挑选的描述互联网未来发展趋势的六大关键词.

耶稣成Facebook万能关键词 粉丝直逼Lady Gaga

- 陆以诺 - cnBeta.COM
据国外媒体报道,知道什么是Facebook万能关键词吗. 不是明星,也不是运动员,而是――耶稣. Aaron Tabor是名医生,今年41岁. 他Facebook中“耶稣日记(Jesus Daily)”的账号专用来写耶稣语录. 他本人还有几个推销婴儿保健品的账号.

20个最贵的谷歌广告关键词

- 国铸 - 译言-每日精品译文推荐
译者 chunfengqiushui. AdWords 是谷歌提供的一种快速简单的购买广告服务的方式,这种广告服务的针对性强,无论您的预算是多少,它都按每次点击计费 (CPC). 根据谷歌的报告,从2010年三季度到今年二季度,谷歌公司的总收入为333亿美元,而其中约97%来自广告. 究竟是谁在支付如此高额的搜索广告费用.