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

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)得到的关联电影集合。

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

则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中价值传递的思路较为类似： 一个节点的价值， 最终流到那儿， 就说明这两个节点比较接近。

• 具体挖掘步骤

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

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

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

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

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

核心代码示意

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

通过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