级联二步图关系挖掘关键词推荐系统及实现代码

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

google youtube 电影推荐算法

在面试实习生的时候,我有个习惯,就是面试快结束的时候,会像聊天一样和面试的学生聊一下他们对某个技术方向的看法。很多时候不是期望他们能提供什么灵感,也不期望能聊出太多结果,更多的是想通过这些沟通,看一下现在学生对这些问题的看法达到什么程度,而且这些沟通很能反映一个面试者的个性。 比如有些人对问题比较坚持, 或者叫做偏执,或者叫做执着,都能够反映出来。
前几天面试的时候到了最后环节的时候,忘了是说什么问题了,面试的实习生提到一般工业界使用的推荐算法都是比较简单的,不会去尝试复杂的算法。 我问他为什么,他说觉得工业界不会投入太多人力; 后来我告诉他还需要考虑处理的数据量和可维护性等因素。 当然他说的这个现象的确比较普遍: 工业界一般都倾向于使简单粗暴有效的算法,只有这些方法都搞不定时,才会尝试更复杂的潜在算法。
两个例子: 一个是 youtube 使用的电影推荐算法(参见论文: The Youtube Video Recommendation System);另一个例子就是Baidu关键词推荐系统中使用的级联二步图;  应该说Baidu关键词推荐系统中的级联二步图的思路是借鉴于youtube电影推荐算法并应用在关键词推荐的场景中。 下边就简单介绍下youtube Video推荐算法。
算法的思想其实比较简单:使用关联规则找到有关联的电影,计算权值后进行ranking推荐。其中的新意在于,这种关联关系能够进行多次传递,逐渐扩大和种子电影相关的电影集合(当然关系传递得越远,一般关联程度也会相应减弱)
具体的推荐过程可以分为3步:
建立video间的关系
建立video间关系的方式比较简单,使用关联规则中的共现方式即可。此处youtube使用的是24小时内session的co-visitation。具体为:
使用 r(vi, vj) = cij/f(vi,vj) 表示video i和video的关联程度, 其中 r为两个video/item的相关系数, ci为i,j共同出现次数, f 为 vi, vj归一化后的分母总量(最简单的方式就是ci * cj),这样就能找到相关的两个vedio
产生特定用户的video候选
该过程在经典信息检索中可以被理解为触发逻辑,及找到待推荐video/item的候选(触发逻辑在推荐系统中所处的位置及重要性参见另外一篇blog: 传统推荐引擎系统架构)
定义S为特定用户的种子video集合, 例如在youtube推荐系统中可以选择用户最新观看(或者最新完整观看的video),之后的问题就是怎么找到和种子词相关的video进行推荐。我们将其分为以下3步:
  1. 定义Cn(S)为和种子集合S相关联的,通过n步扩展后的推荐候选集合。 例如 C1(S) = 所有Ri的并, 其中Ri是与S中的vi相关联的v(寻找相关联v的过程参见上述:产生特定用户的video候选)。 相当于找到所有与S中种子vi想关联的v的并集;该做法的缺点是可能范围比较小且太相似。
  2. 使用Cn(S)进行触发, 即得到C(n-1)(S)后,再找到与C(n-1)(S)中每一个vi相关联的v,之后去除种子词S,我们称Cn(S)为对S的n步扩展。
  3. 同时在C(n)(S)中保留着每一个v被找到的原因, 便于后续ranking及给出explanation。
经过上述3步,对于特定user的候选video就触发完毕了。 该触发步骤可以说是该论文中的值得借鉴的点。 组里之前一位工程架构策略都很牛的同学指导实习生实现了一个通用的级联二步图算法框架, 该算法框架能够将有关联的节点的关系进行传递:
例如对于关键词,我们可以使用topic 主题(由topic model产生)建立关键词之间的跳转关系, 或是关键词中的核心term(一般是归一化后的核心term)建立跳转关系。 而该框架更令人着迷的是, 二步图的左右两边可以不是同样的item, 例如左边节点是keyword而右边是user, 则可以使用topic 直接建立keyword与user的关系进行推荐。
 Ranking
youtube 的ranking策略主要考虑以下3个因素:
  1. video质量, 这个可以通过网名对video投票打分得到。这一项和用户及对应偏好, 仅和video自身质量有关,就类似于搜索中pagerank得到的page质量度一样
  2. user specificity: 在触发后,可以通过使用user profile和电影的一些质量, 或是内容属性进行排序。这一项反映的是用户对电影的偏好得分
  3. divercification:特别是类似video这种兴趣相关的内容, divercification的引入就显得非常重要了,否则推荐的video会逐渐收拢到可数的一两个品类,可以使用的方式是限制每一个category video的推荐数量,或者本文中限制每个seed video出的video的数量;相反, divercification在不同的场景下可能不同,百度关键词推荐中, 根据种子词直接检索得到的结果需要考虑与种子query的强相关性, 此时divercification的引入, 或者引入的程度需要比较慎重保守。
当然, ranking机制一般都会非常复杂, 论文中此处只是简单介绍; 例如在构造百度关键词推荐系统的过程中, 我们引入了提词率预估, 效用预估, 价值预估等模型对返回结果进行ranking。同时也需要结合user interaction的样式,算法出口(interface)等进行调整。 具体ranking机制会在后续blog中介绍。
效果上, 级联二步图的引入,能够找到非常多靠谱的结果(当然二步图边的建立是核心,选对了边的建立方式,才会有好效果),具体效果数据就不便透露了:)   反正是基本上能够覆盖全部凤巢用户,每个客户都能推出数量惊人的关键词(当然,需要使用字面, 语义等技术进行后续filtering and ranking)
更进一步, 级联二步图是图关系挖掘的一个简单有效的特例, 使用类似于pagerank等经典算法, 也能够很好地找出类似的关系进行推荐。
参考来源:
  1. 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.
  2. Google Adwords
  3. 百度关键词推荐工具 :http://support.baidu.com/product/fc/4.html?castk=e6f89hg77d37ada65d612
或者直接访问 http://semocean.com