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

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

context-aware recommendation

智能手机的普及让大家随时随地都可接入互联网,而这样的随时随地的应用场景,也让传统推荐技术需要充分考虑,利用这些信息提升推荐的准确性,同时从另外一方面考虑, 这种符合LBS的推荐, 因为有了这些信息后,也能够更加准确。
传统的推荐系统基本上就是根据用户对物品的打分进行推荐, 或者描述为 USER * ITEM -> RATING。 其工作就是去填充一个matrix,matrix的横坐标为item,纵坐标为user,推荐的任务就是根据当前已经获得的该matrix中非空的元素, 去填充该矩阵中没有值得元素,并保证用于填充matrix的模型, 在非空元素上的误差最小。
什么是Context-Aware Recommendation
但在很多场景下, user的rating会受到context的影响, 这里的context在不同的领域会有不同的定义。例如电影推荐,对是否为工作日这样的因素影响会比较大;在LBS应用中,推荐内容是否会被采纳, 会受到地理位置的影响(特别现在移动是个大趋势,后续更多的访问流量都会转向移动),例如手机美团,如果一个人在饭点上美团,则他购买餐馆团购券的概率应该要比夜晚大,而购买离他距离近的餐馆团购券的概率也要比购买距离比较远的团购券大。 这里的地理位置, 时间,就可以看成是context内容。
而在搜索引擎中,例如百度,要增强搜索的个性化(如果我们将搜索也看成推荐问题),那么网民的IP所在地,或者网民之前输入的几个query,都可以看成是context内容。
那context内容如何与传统Recommender技术融合? 这就是推荐技术中的contex-aware recommedation: 结合上下文的推荐。 例如,大家经常会进行团购,而团购中的项目,要数团购饭点的套餐最为划算了,这其中就会直接涉及到上文提到的时间,地点两个上下文因素。举个例子,如果我周末快到吃饭时间进行套餐的团购, 海底捞离我比较远但小肥羊离我比较近,那我还是有可能会考虑离得比较近的小肥羊, 或者离我比较近的海底捞的店。
在我看来,类似于美团, 大众点评这样的生活服务,是最需要Context-Aware Recommendation技术的了(特别是近些年来智能手机的普及,大家很多时间都是用智能手机上网),需要结合用户诸如位置,时间及之前积累的用户信息(user profile)进行推荐。
如何实现context-aware recommendation
一般来说,可以使用以下3类方法,在推荐技术中引入上下文信息:
  1. Contextual Pre-Filtering
  2. Contextual Post-Filtering
  3. Model-based
Contextual Pre-Filtering
该技术是在数据处理阶段,就使用contextual信息对数据进行处理过滤,之后就可以使用传统的推荐技术进行推荐。假设我们将信息的处理看成是一个漏斗: 在获得候选信息后,逐步根据当前能够获得的信息过滤掉不相关的内容,保留下最相关的内容,则contextual pre-filtering方法就相当于将最严格的信息放在漏斗的最开始,直接过滤掉与用户context不相关的内容。
在实现contextual pre-filtering技术时,需要考虑contextual的表示方式,很多时候可以将这些contextual使用层次信息进行表示,以下是几个例子:
Company: Girlfriend →Friends →NotAlone →AnyCompany;
Place: Theater → AnyPlace;
Time: Saturday →Weekend→ AnyTime.
上边的例子,从左到右越来越泛化。
例如百度关键词搜索推荐系统,推荐地域相关关键词时,如果用户提供了地域信息,例如‘北京’后,在后续的推荐中,就不会考虑‘北京’以外的地域,而北京下属的几个区,都可以作为推荐的候选,这就需要维护一个全国地域term的层次树。 而时间, 关系(上文中的Company)等维度也需要有类似的层次树进行维护。
Contextual Pre Filtering方法优点: 在一开始对contextual信息进行处理后,就可以使用传统方法进行推荐,例如将特定contextual相关的数据过滤出来后,就可以使用传统的按内容推荐,协同过滤等方法进行推荐。 如果是实时的搜索引擎,使用类似于Contextual Pre Filtering的方法, 能够有效地减少后续数据的处理量(相当于建立了一个数据过滤漏斗, 在一开始的阶段即将后续不会用到的数据过滤,减少后续策略的计算量);但推荐系统中如果将没中过contextual信息的数据过滤出来单独训练的话,速度并不会有所提升。
Contextual Post-Filtering
该方式对于数据的处理与传统的推荐方式一致, 区别在于当结果已经推荐出来时, 使用contextual信息对结果进行重新过滤或是重排序。
例如, 对于地域这一维contextual信息,百度关键词搜索推荐(Baidu Keyword Recommender,后续简称KR)中就是用Contextual Post-Filtering方法,例如KR首先使用传统的方法进行推荐,之后在结果返回前,会根据地域对关键词进行排序过滤;又例如,美团的app,在进行餐饮团购推荐是,一开始可以使用传统的推荐算法进行推荐(当然此时就应该根据上下文进行粗过滤,例如对于在北京找餐饮服务的网名, 给他推荐一个上海的海底捞可不是一个好的选择), 当传统推荐算法推荐出结果后, 就可以使用上下文来进行过滤排序了。 例如餐饮服务推荐中国,在其他因素固定时,可以优先推荐离用户地理位置近的item。 最终的结果也不是完全按照时间排序, 时间只是众多考虑因素中的一个因子,例如可以使用另一个CTR模型来预估用户的点击概率, 而网名地理位置离餐馆的远近可以作为一维重要特征(其他特征可
以包含推荐物品与网民兴趣的匹配程度, 该item是否与该网民历史购买能力匹配等)
Contextual Post-Filtering的优点: 该方法的优点和Contextual Pre-Filtering一样,可以使用传统的推荐技术。 但该方法与Contextual Pre-Filtering相比,有一个优点: 最终的过滤排序,都是在推荐算法完成后进行的, 当有新的数据,或是算法接入时,最终的排序过滤标准是可以不做调整,只要在最终排序过滤逻辑前引入新算法的推荐结果即可,另一个优点是,最终出的结果的数量,可以视最终可能被保留下来的结果的数量进行调整, 例如按照严格的contextural信息来过滤,可能最终剩下的结果只有两条,此时如果觉得结果太少,则可以适当放松过滤阈值,或者将接近阈值的结果打上特定标签推荐出来(例如,百度关键词搜索推荐中,如果推荐的结果太少,系统会将一些阈值相对偏低的结果也展现出来,只是结果后边会打上‘结果太少?网民也会这样搜索’);但任何事物都有两面性,Contextual Post-Filtering方法的缺点一开始推荐出来的结果,会在后续直接因为Context不match而直接被过滤掉,这样就白白浪费了在排序过滤前的计算。
在实际应用中,需要根据具体应用选择使用Contextual Pre-Filtering或是Contextual Post-Filtering方法,而更为常见的是,两种实现思路经常会同时在同一系统中出现,仍然以KR中地域属性为例,在进行关键词候选结果选择时(一般称为触发过程),就会使用地域信息对结果进行粗选;在得到候选结果后,会使用地域信息(包括层级地域信息)对关键词进行更精细化的排序过滤。
Contextual-Model
可以理解为传统的Model-based推荐方法, 区别在于在进行模型训练时, 就将Contextual作为特征加入模型进行训练, 该方法的优点是直接可以使用一个模型完成推荐, 缺点在于如果上下文信息维度较多, 会导致训练数据较为稀疏, 同时当结果较差时不容易进行优化,因为众多因素进行了融合,很难指出问题出在什么地方。而Contextual Pre-Filtering和Post-Filtering方法,可以理解为对问题进行了拆解。这样的策略架构,问题定位会相对容易一些。
后记:  前几天看到一个新闻,称美团2013年已经实现盈利。当时看到这个信息的时候还挺震惊的。2011年的时候百团大战时,团购网站都在各种烧钱推广。百度为了让团购网站能够更高效地在凤巢上进行推广(也可以理解为更高效地挣团购网站的钱),设计了无关键词拍卖系统: 团购网站只要提供团购页面(或是团购页面的结构化属性描述),即可在百度上进行推广。但悲剧的是该系统才刚要开发完毕,团购网站的前就已经烧得差不多了, 之后就出现一大批团购网站的倒闭。。。。现在美团居然活得好好的。
同时结合自己做推荐系统的几年,觉得美团和大众点评这样的网站,是最适合加大推荐系统研发投入的: 每个美团/大众点评用户都有自己的ID,也都有自己够买的商品(explicit rating)和自己浏览的网页(implicit rating),同时手机客户端的的位置,时间信息可以作为推荐的context信息增强推荐的准确性。所以如果后续仍想在推荐系统方面做一些工作的话, 美团和大众点评都会是不错的选择。
附上一个index.baidu.com上几个关键词的搜索量变化, 美团的曲线是相当的漂亮!
百度关键词工具介绍参见:http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596
也可关注我的微博: weibo.com/dustinsea
或是直接访问: http://semocean.com

集成树类模型及其在百度搜索推荐系统中的应用

决策树是经典高效的机器学习分类算法, 非常适用于线性模型效果不能满足需求, 规则描述分布比较合适的场景。而决策树与传统bagging, boosting思想结合在一起, 就形成集成树模型方法, 包括Random Forest,GBDT等方法。 在百度搜索关键词搜索推荐系统策略中,实验证明集成树模型具有非常高的预估分类准确性。

决策树模型

举一个简单例子(引自公司pengzhiming同学的PPT): 老妈让自己相过多次亲的女儿再次去相亲, 女儿简单问了下对方的条件, 以判断是否去; 根据男方条件(特征)对去与不去进行分类的过程, 就是一个CART决策树。

例如:

母女对话如下:

 

如果将女儿的历史相亲经历看成是训练样本(男方条件为特征,女儿到对方后觉得是否靠谱作为label),将女儿积累到现在的相亲经验则是一个CART模型: 根据老妈的描述,就可以判断出是否有必要去见男方。

当然, 决策树模型也可以再细分, 包括经典的ID3,C4.5, CART。 不同的决策树具有不同的树结构,以及不同的节点拆分算法及拆分标准。

树模型的优缺点

总体来说,树类算法都是使用贪心算法, 选择当前最合适属性进行拆分建立整棵决策树,该类模型比较适用于能够用复杂规则描述的应用场景

以下为树模型的优点:

  • 实现较为简单, 且容易实现并行化
  • 训练速度较快, 且一般效果也比较好
  • 能够处理离散连续值特征(和LR类似的模型相比), 不用对特征做归一化即能取得较好效果
  • 能够处理缺失值
  • 能够处理高维特征
  • 训练完毕后, 能够给出哪些特征比较重要;而且很多情况下,即使最终使用其他模型 也可以使用树模型选择特征

当然, 所有的模型都有其弊端:

  • 树模型容易过拟合, 所以需要进行剪枝(以及使用后续将描述的集成学习方法解决)
  • 不能表示复杂结构和运算: 树模型原则上天然表示‘与’操作, 所以不能表示类似于‘异或’的操作

因为树模型的以上优点, 树模型在很多场景均会被选用

树模型训练框架

以下为使用数据集D,属性(特征)集合attribute_list产生决策树的算法框架。该算法未包含任何剪枝。

以上伪代码中(2)~(5)行用来处理数据中都是相同label及无属性拆分的情况,剩余代码使用贪心算法选择最合适的属性后,进行拆分,并递归建立子节点。

在上述伪代码中涉及到attribute_selection_method逻辑, 也就是决策树节点拆分标准的问题。

树模型节点分裂标准

如上所述,决策树使用贪心算法进行拆分, 选择当前认为最优的拆分特征进行树节点的分裂。 这就涉及到选择何种属性作为拆分的标准。一般说来, 经常使用的树节点拆分标准主要有以下几类:

  • information gain

一般情况下, 在决策树中, 使用信息增益(information gain)作为节点分裂的选择标准。

要定义信息增益, 我们需要定义‘信息’,我们将信息定义为: 对于数据集合D,我们需要对D中的各种类别进行编码的字节编码数,即:

 

 

信息量, 也被称为熵(entropy),用于描述不稳定性或多样性。 对样本集合D中, 假设对于某一维度的特征, 该特征A有v种取值, 而每种取值对应的数据样本数为Dj, 则在知道了某属性A的各种取值,并将符合各v值得样本进行分类后, 需要将样本集合D完全分开所需要的信息量为:

其中Dj为符合每个A的取值(假设A为离散可数种取值)的子样本集合。infor(Dj)为完全划分子样本集合所需要的信息量。 此时可定义信息增益:

在ID3算法中, 使用信息增益进行分裂特征的选择, 算法会使用贪心算法选择信息增益最大的特征进行树节点的分裂。 但信息增益有一个缺点: 会选择有众多值的特征进行节点分裂, 极端情况, 对于ID类特征(利用用户ID, 或是item ID), ID的个数与待分类的样本数一样, 这样的分裂是没有意义的, 此时, 使用gain ratio作为节点拆分标准, 能避免该问题。

  • gain ratio

为了解决信息增益偏向于选择属性值较多的特征问题, 在c4.5中引入了gain ratio。 首先定义:

注意splitinfo_A 与info_A的不同: splitinfo的第二项受到的是符合特征A下每种取值的样本数量影响; info_A则受到特征A下每种取值的样本包含的信息的影响。注意参考entropy的定义, 当分布越是不均匀时, 描述这种状态所需要的信息量约小, 分布越是散时, 需要的信息量越大(info值越大), 所以当拆分特征的值越多时, splitinfo会越大。

此时我们定义gainratio, 分母为splitinfo 起到抑制拆分多值特征的倾向。

  • gini index

在CART中, 使用gini index作为节点拆分的标准, gini系数的定义如下:

其中pi为样本集合D中各类的占比(总共有m类, pi=Di/D, 其中Di为D中属于类别i的的样本数量)

定义:

即使用属性A来对样本进行节点拆分后时的gini index, 此时可使用gini_A来对A进行拆分判定, 选择gini系数值下降最快的属性进行拆分。

一般说来information gain,gain ratio, gini index就是最常使用的三种拆分指标。结合前述树模型构建方法, 再加上构建树的过程中/后的限定条件及剪枝, 即可构建出实际中高效的决策树。

 

集成学习方法

集成学习方法是将bagging,boosting思路与树模型结合的高效学习方法。

bagging的思路比较简单, 就是汇集多个模型进行投票, 每个模型的票的权重一样, 获得票数最多的预估类胜出, 该类获得的票数与总票数的比值可以作为置信度。 如果是回归问题, 则多模型预估值得平均值作为bagging结果。

boosting方法在bagging的思想上前进了一步: boosting在训练时会更在乎分类错误的样本, 给予分类错误的样本更高的权重训练模型, 并将这些权重不一的模型根据权重进行bagging。boosting更像是是医疗专家诊断病情一样: 诊断容易出错的病情正确率更高的专家的话语权更高。 具体adaboost的介绍可参见《adaboost

bagging方法, 特别是adaboost方法一般都会使用非常简单的弱分类器进行bagging和boosting, 随着计算机处理能力的增强, 可以使用更加复杂的模型进行bagging&boosting, 而过将弱分类器使用更加复杂的树模型, 就形成‘集成树模型’。比较常用的‘集成树模型’包括Random Forest和GBDT。

虽然单个树模型学习能力有限(拟合复杂的数据分布能力有限), 但多个树模型放到一起, 就能够高精度拟合出复杂的分布(如上图所示), 这就是集成学习的强大之处。

  • Random Forest

Random Forest(RF)是典型的bagging树模型的方法。 其思路就是使用随机的部分样本/特征构建树模型, 之后使用bagging思想进行分类。

RF不仅对特征集合进行采样, 同样也可以对样本进行采样, 例如在进行单个cart训练时, 对每个模型,随机使用这种方式一方面充分利用了所有样本, 特征的贡献, 另一方面, 又能避免部分噪音带来的过拟合。设置合适的样本随机采样率(例如0.6表示每个模型选择60%的样本进行训练)以及何时的特征随机采样率(例如0.6表示每个模型选择特征集合60%的特征进行训练)进行RF训练。

在进行分类时, 根据样本和特征抽样训练出来的模型使用bagging方法进行投票。

相对于boosting会依赖于前一模型分类正确or错误调整样本权值的思路, RF更容易实现并行化, 因为RF中各子树的训练过程是完全独立的不会相互影响

  • GBDT

Grandent Boosting(GB)是将梯度下降思路融入boosting方法中, 不同于传统boosting每一步对分错样本进行加权(或对分对样本进行加权),GB定义整个模型的损失函数。

算法的每一步沿着损失函数下降最快的方向建立新的模型,这样使得算法在每一步均沿着下降最快的方向收敛。 直到满足要求, 建立满足要求的若干组合加权子模型。

Gradient Boosting将问题进行建模,定义loss function为

则对于训练样本集合{y, x}, 我们的任务是寻找最小化loss的函数F*(x):

而gradient boosting的思路是将映射模型函数表示为以下形式:

其中h(x;am)为简单函数/模型, am 为h的参数, 此时, belta, a, 就为我们要预估的最小化loss下的参数:

同时Fm与F_m-1的关系为

 

之后可以求belta和a序列参数, 求解过程如下:

在第i个样本点, 第m个模型里边的伪残差求解方法为:

要构建模型h(x,am), 最快的方法, 就是让所有的样本点处, 损失函数都沿着最快的方向下降。

也就是:

利用最小二乘法求解am后, 即可求解belta_m

依次求解所有am, belta_m后, 即得到最终模型F*(x)

树模型在百度关键词搜索推荐中的应用及实验结果

当然, 很多时候我们不会直接去修改模型, 在应用中, 更多地是使用模型作为工具解决具体问题。 例如在百度关键词搜索推荐中, 我们更多是构建相关性判断的特征样本, 之后对模型参数进行搜索: 例如样本采样率, 特征采样率等参数。 具体效果参见实验部分。百度关键词搜索推荐介绍及交互流程参见《百度关键词搜索推荐系统交互流程

一下为具体应用标注负样本示例,例如‘水仙花’, 从搜索引擎商业价值角度考虑, 是具体描述水仙花这个商品, 而不一样是信息型舞蹈名字query’紫蝶广场舞水仙花开’:

具体GBDT在百度关键词搜索推荐中, 相关性判断的应用方法(包括特征选取和实验结果), 参见《分类模型在关键词搜索推荐中的应用》, 使用树模型, 在没有任何样本,特征调整的情况下, 准确性直接提升了5个点 ,效果惊人。

同时, 正如前述: 树模型还有一个显著优点, 就是在模型建立时, 能够清晰分析出哪些特征对分类贡献大, 哪些对分类影响小(常用的指标包括特征的贡献度, 特征在分裂时的使用频率), 一般情况下特征贡献度和特征使用频率均是越大越好。 例如百度关键词搜索中, 对关键词相关性模型(使用分类模型判断两个关键词是否相关)使用17维特征。 使用Random Forest保留贡献最高的5维特征时, 在交叉验证情况下, 准确性基本保持不变, 召回也就下降1个百分点。

而在排序任务重, 使用衍生GBrank对百度关键词搜索推荐结果进行排序, 一般情况下,效果随着树的深度增长而提升, 但树深度达到8后, 就不再提升。

随着叶子节点书的增长, 效果仍然在提升, 所以在应用中,如果效率允许, 可以让最大叶子节点数多一些。

在实际应用中, 理论上可以对众多参数进行全参数搜索, 找到最优参数。 实际应用中会快速找到比较好的参数后, 策略即上线进行实验。

参考文献:

  1. Friedman J H. Stochastic gradient boosting[J]. Computational Statistics & Data Analysis, 2002, 38(4): 367-378.
  2. Quinlan J R. Induction of decision trees[J]. Machine learning, 1986, 1(1): 81-106.
  3. Breiman L, Friedman J, Stone C J, et al. Classification and regression trees[M]. CRC press, 1984.
  4. 分类模型在关键词搜索推荐中的应用

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

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

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

 

推荐系统经典论文文献及业界应用

列了一些之前设计开发百度关键词搜索推荐引擎时, 参考过的论文, 书籍, 以及调研过的推荐系统相关的工具;同时给出参加过及未参加过的业界推荐引擎应用交流资料(有我网盘的链接), 材料组织方式参考了厂里部分同学的整理。
因为推荐引擎不能算是一个独立学科,它与机器学习,数据挖掘有天然不可分的关系,所以同时列了一些这方面有用的工具及书籍,希望能对大家有所帮助。
Survey方面的文章及资料
  1. Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[J]. Knowledge and Data Engineering, IEEE Transactions on, 2005, 17(6): 734-749. 2005年的state-of-the-art的推荐综述,按照content-based, CF, Hybrid的分类方法进行组织,并介绍了推荐引擎设计时需要关注的特性指标,内容非常全。
  2. Marlin B. Collaborative filtering: A machine learning perspective[D]. University of Toronto, 2004. 从传统机器学习的分类角度来介绍推荐算法,有一定机器学习背景的人来看该文章的话, 会觉得写得通俗易懂
  3. Koren Y, Bell R. Advances in collaborative filtering[M]//Recommender Systems Handbook. Springer US, 2011: 145-186.  RSs Handbook中专门讲述协同过滤的一章,其中对近年协同过滤的一些重要突破进行了介绍,包括因式分解,时间相关推荐,基于近邻的推荐以及多种方法的融合,内部不多,但其中引用的论文值得细看
  4. Su X, Khoshgoftaar T M. A survey of collaborative filtering techniques[J]. Advances in artificial intelligence, 2009, 2009: 4. 协同过滤的篇survey, 按照memory-base, model-based, hybrid分类方法介绍各种协同过滤方法及评价标准,并在其中给出基于netflix数据进行评估的效果对比
  5. Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37.  主要集中在因式分解实现协同过滤方法,如果看完Advances in collaborative filtering[M]//Recommender Systems Handbook的话,这篇文章就没有必要再看了
  6. Pazzani M J, Billsus D. Content-based recommendation systems[M]//The adaptive web. Springer Berlin Heidelberg, 2007: 325-341.从宏观上介绍content-based的策略架构
Content-based方法
content-based方法非常依赖于特定领域item的特征提取及处理,例如音乐推荐或是关键词推荐中很多细节内容信息处理过程都是不一样的,故这里仅列了content-based综述类的几篇文章。
  1. Pazzani M J, Billsus D. Content-based recommendation systems[M]//The adaptive web. Springer Berlin Heidelberg, 2007: 325-341.从宏观上介绍content-based的策略架构
  2. Lops P, de Gemmis M, Semeraro G. Content-based recommender systems: State of the art and trends[M]//Recommender Systems Handbook. Springer US, 2011: 73-105. RS Handbook中专门介绍content-based 算法的章节
  3. Jannach D, Zanker M, Felfernig A, et al. Content-based recommendation   [M] Charpter 3 Recommender systems: an introduction[M]. Cambridge University Press, 2010.
Collaborative Filtering方法
Neighbourhood Based Methods
  1. Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. ACM, 2001: 285-295. KNN进行item-based推荐的经典文章,其中也介绍了多种相似度度量标准
  2. Linden G, Smith B, York J. Amazon. com recommendations: Item-to-item collaborative filtering[J]. Internet Computing, IEEE, 2003, 7(1): 76-80. 经典的亚马逊item-based算法的文章
  3. Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing[C]//VLDB. 1999, 99: 518-529.  LSH
  4. Bell R M, Koren Y. Scalable collaborative filtering with jointly derived neighborhood interpolation weights[C]//Data Mining, 2007. ICDM 2007. Seventh IEEE International Conference on. IEEE, 2007: 43-52.
  5. Indyk P, Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998: 604-613. LSH
  6. Buhler J. Efficient large-scale sequence comparison by locality-sensitive hashing[J]. Bioinformatics, 2001, 17(5): 419-428. LSH应用
Model Based Methods
  1.  Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37.主要集中在因式分解实现协同过滤方法,如果看完Advances in collaborative filtering[M]//Recommender Systems Handbook的话,这篇文章就没有必要再看了
  2. Singh A P, Gordon G J. A unified view of matrix factorization models[M]//Machine Learning and Knowledge Discovery in Databases. Springer Berlin Heidelberg, 2008: 358-373.
Hybrid Methods
  1. Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008: 426-434. 因式分解与Neighbour-based方法融合
  2. Burke R. Hybrid recommender systems: Survey and experiments[J]. User modeling and user-adapted interaction, 2002, 12(4): 331-370.
  3. Burke R. Hybrid recommender systems: Survey and experiments[J]. User modeling and user-adapted interaction, 2002, 12(4): 331-370. 介绍了多种推荐算法进行融合的框架
推荐系统工业界应用
  1. Netflix:Netflix视频推荐的背后:算法知道你想看什么
  2. Netflix:Netflix Recommendations Beyond the 5 Stars
  3. Hulu:Recommender System Algorithm and Architecture-项亮
  4. Youtube: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.  Youtube推荐系统中的主要算法。 百度关键词搜索推荐系统对其进行了优化, 实现了任意类型的级联二部图推荐。 具体内容可参见博文: google youtube 电影推荐算法, 以及百度关键词搜索推荐级联二部图实现
  5. 豆瓣: 个性化推荐系统的几个问题_豆瓣网王守崑
  6. 豆瓣:阿稳_寻路推荐_豆瓣
  7. 豆瓣:豆瓣在推荐领域的实践与思考
  8. 百分点:量化美-时尚服饰搭配引擎
  9. weibo及考拉FM:停不下来的推荐实践_陈开江
  10. 阿里:天猫双11推荐技术应用
  11. 阿里:淘宝推荐系统
  12. 当当:当当网搜索和推荐_庄洪波
  13. 土豆:个性化视频推荐系统土豆_明洪涛
  14. 360:360推荐系统实践-杨浩
  15. 盛大:推荐系统实战与效果提升之道-陈运文
  16. 盛大:智能推荐系统的开发与应用-陈运文
推荐系统书籍
  1. Segaran T. Programming collective intelligence: building smart web 2.0 applications[M]. O’Reilly Media, 2007.寓教于乐的一本入门教材,附有可以直接动手实践的toy级别代码
  2. Shapira B. Recommender systems handbook[M]. Springer, 2011.  推荐系统可做枕头,也应该放在枕边的书籍,看了半本多。如果将该书及其中的参考文献都看完并理解,那恭喜你,你已经对这个领域有深入理解了
  3. Jannach D, Zanker M, Felfernig A, et al. Recommender systems: an introduction[M]. Cambridge University Press, 2010.  可以认为是2010年前推荐系统论文的综述集合
  4. Celma O. Music recommendation and discovery[M]. Springer, 2010. 主要内容集中在音乐推荐,领域非常专注于音乐推荐,包括选取的特征,评测时如何考虑音乐因素
  5. Word sense disambiguation: Algorithms and applications[M]. Springer Science+ Business Media, 2006. 如果涉及到关键词推荐,或是文本推荐, 则可以查阅该书
P.S. 想对某个领域或是工具有深入了解,可以找一本该行业的XX HandBook满怀勇气与无畏细心看完,然后就会对这个领域有一定(较深)了解,当然如果手头有相关项目同步进行,治疗效果更好^_^
推荐系统工具
  1. Mahout:基于hadoop的机器学习,数据挖掘,推荐系统开源工具。我厂的超低版本haodop集群居然不支持Mahout,想跑个Mahout还要进行移植,郁闷。。。该死!!
  2. scikit-learn:基于python的机器学习,数据挖掘库, 方便好用,适合数据量较小的调研任务,不过,一切不支持大数据的机器学习算法,(一定程度上)都是耍流氓。。。。
  3. weka:经典的数据挖掘工具, java版本
  4. R:R语言
  5. Cluto:聚类工具,集成了较多聚类算法及相似度度量方法
  6. RapidMiner:没用过,但据说使用量非常大
国内推荐系统站点
  1. http://www.resyschina.com/
因为我一直认为推荐系统不是一个独立的学科,它很多技术都是直接来自于机器学习,数据挖掘和信息检索(特别是文本相关的搜索推荐),所以以下也整理了一些之前工作及工作之余看过,了解过,或者准备看的这方面的资料
数据挖掘资料
  1. Han J, Kamber M, Pei J. Data mining: concepts and techniques[M]. Morgan kaufmann, 2006. 数据挖掘方面的handbook,教科书类型,虽然厚,却通俗易懂(再次提醒,要了解某一领域,找本该领域的啥啥handbook耐心认真读完,那你基本对该领域有一定认识了)
  2. Chakrabarti S. Mining the Web: Discovering knowledge from hypertext data[M]. Morgan Kaufmann, 2003.介绍了一个搜索引擎中的大部分技术,包括spider,索引建立,内部的机器学习算法,信息检索,而且非常具有实用性,我在百度商务搜索部开发的spider,就是按照其中的架构设计开发的
  3. Liu B. Web data mining: exploring hyperlinks, contents, and usage data[M]. Springer, 2007. 如果说 Mining the Web: Discovering knowledge from hypertext data更偏web mining更偏整体,工程的话,这本书就更偏策略,两本都读过的话,你对搜索引擎中的数据挖掘算法的了解,就比较全面了
  4. Wu X, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1-37. 专门将2006年评选出来的10大数据挖掘算法拎了出来讲讲
  5. Rajaraman A, Ullman J D. Mining of massive datasets[M]. Cambridge University Press, 2012.介绍如何使用hadoop进行数据挖掘,如果有hadoop环境则非常实用
  6. Feldman R, Sanger J. The text mining handbook: advanced approaches in analyzing unstructured data[M]. Cambridge University Press, 2007.文本挖掘的handbook
机器学习资料
  1. Tom M Mitchell,Machine Learning, McGraw-Hill Science/Engineering/Mat, 1997,非常早起的机器学习书籍,非常适合入门, 浅显易懂, 但对于工业界应用, 只能说是Toy级别的算法。
  2. Bishop C M, Nasrabadi N M. Pattern recognition and machine learning[M]. New York: springer, 2006. 进阶型的书籍,对每种算法都有较为具体的理论介绍
  3. 课程: 机器学习(Stanford->Andrew Ng)http://v.163.com/special/opencourse/machinelearning.html,大名鼎鼎的Andrew Ng的机器学习公开课,网易上字幕版本;配合课程stanford cs229对应的handout及习题一起学习效果更好
信息检索
  1. Agirre, Eneko, and Philip Glenny Edmonds, eds. Word sense disambiguation: Algorithms and applications. Vol. 33. Springer Science+ Business Media, 2006.
  2. Manning C D, Raghavan P, Schütze H. Introduction to information retrieval[M]. Cambridge: Cambridge University Press, 2008.
  3. MOFFAT A A, Bell T C. Managing gigabytes: compressing and indexing documents and images[M]. Morgan Kaufmann, 1999.一本很老的介绍搜索引擎的书了,不过09年的时候看还是被震撼到了,书中各种变着戏法使用几十M内存处理上G数据,感觉非常牛叉。
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com

关键词推荐工具中的用户引导机制之四:种子query推荐

上一篇《关键词推荐工具中的用户引导机制之三:相关搜索query技术》中, 我们提到可使用用户query-点击日志,session数据,及网页内容,挖掘与query意图相关(同时具有变现价值)的相query推荐给客户引导用户优化搜索。 如用户还未输入,此时搜索引擎默认直接展示搜索框。但在关键词推荐系统中,更好的选择是push与用户相关高质量query,帮助用户高效发现兴趣点,本文将介绍在关键词推荐系统中,实现种子词推荐产品及策略
什么是种子query推荐功能
什么是种子词query推荐,先向大家展示两个直观的例子: 百度锁屏,以及百度关键词推荐种子词推荐功能。
 
图: 百度锁屏种子词query推荐
图:红框部分为关键词推荐工具中种子query功能
种子query推荐功能作用
种子query,就是在用户在搜索框中,还没有任何搜索时,通过线下挖掘计算,主动push推荐用户潜在感兴趣的query的功能。 例如百度锁屏功能的种子query,当用户锁屏准备解锁时,app推荐用户可能感兴趣的搜索引擎候选query(种子query)后,用户可以直接点击进行搜索,以提升搜索引擎访问量; 在百度关键词推荐系统中,用户还没有输入适合自己的query时,可以根据用户的历史搜索,以及百度推广业务等信息,推荐高质量的种子query给客户。
大家可能会有疑惑,既然关键词推荐就是一个推荐系统,那为什么还要有种子词推荐? 而Baidu,或是Google首页上,也没有种子词推荐?  从我的角度来看,Baidu,Google首页之所以没有种子词推荐功能,一方面是这两个搜索引擎简单的首页的访问量实在太大,首页上任何的信息,可点击的内容均会对网民带来影响巨大的引导作用, 举个例子: 之前就曾经发生过类似的时间,就是在百度首页上放了一个大型网站(具体网站名不便透露)的文字链,结果在很短时间内,该网站就被来自百度该文字链的流量压垮;反过来说, 在搜索引擎首页上增加种子词推荐,也会分散用户的注意力。 另一方面网民的搜索内容太泛,要做到准确推荐的确有难度。
在关键词推荐系统中,特定用户搜索的(商业)query对应的意图,产品范围均相对集中,或者说使用关键词推荐系统的用户,兴趣点相对集中,难点是用户很难想出来搜索引擎上可能接受的描述该兴趣点的千奇百怪的表述。 所以就需要使用种子词推荐功能进行搜索引导。
如何设计种子词推荐策略
可以很简单, 也可以很难。。。
为什么说很简单, 例如,在搜索引擎上, 最简单的方式, 就是直接使用一定时间内网民的搜索, 过滤掉黄赌毒反结果,作为推荐结果。 但这样做有一个问题, 就是有些搜索query,基本上可以说任何时候,搜索量都比较高, 例如搜索query “淘宝”。 为了避免该类问题, 可以使用在某一段时间内搜索量变化比较大的query作为种子query。
为什么说可以很难?  因为这本来就是一个关键词推荐问题: 根据用户历史行为,数据,推荐用户可能感兴趣的query。 当然, 种子词推荐有它的特殊性, 因为推荐的优化目标是不一样的,它是一个多目标的优化问题:
  1. 符合用户的搜索意图(搜索引擎中为搜索意图,百度推广中为推广意图)
  2. 用户使用该种子词搜索后,为搜索引擎/商业系统带来的效用
假设搜索意图质量为Q(Quality),带来的效用为U(Utility),则这个多目标优化问题可以描述为:
S = Q^(t) * U^(1-t)
其中S为最终的Score,使用t控制Q与U在最终结果中的权重。
我们可以使用经典的colleborative filtering, 或是content-based recommendation方法, 获取到推荐词源, 之后使用以上双目标优化方式计算S来进行结果的filtering和ranking,给出Score权值最高的top n 结果。
例如, 在关键词推荐系统中,我们希望用户使用种子query进行搜索后, 一方面结果要相关, 另一方面,返回的结果数要超过阈值(或者尽可能多), 此时, 搜索结果相关可以被定义为Q(可以离线挖掘时使用PLSA等技术进行判断相关性), 同时使用返回结果数作为U, 最终对挖掘的种子词进行filtering和ranking。
更多内容请参考:
《recommender systems handbook》
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com

因式分解实现协同过滤-及源码实现

在设计实现推荐系统,选择推荐算法时, 肯定会考虑协同过滤(CF)的使用,而CF中经常使用的两种方法包括: neighbour-based方法和因式分解。 作为一个搜索推荐系统,百度关键词系统中也使用了CF(包括neighbour-based和因式分解方法)为用户推荐流量,考虑到可解释性和工程上在hadoop上实现的便利性,最终主要使用了neighbour-based中的item-based方法。但学术上,因式分解会从全局考虑用户投票的影响,所以理论和实践上效果都会更好。本文主要结合之前对因式分解的调研理解及调研demo代码, 介绍因式分解实现协同过滤的方法, 同时感兴趣的同学可以下载源码及MovieLens数据进行实验。
注:
为了方便理解, 以下介绍均使用MovieLens 100K数据进行介绍(公司数据太大, 且包含过多预处理过程, 同时涉及泄密,你懂的:)
文中的代码可从文章最后的参考内容链接中下载。
推荐算法对比基线的建立
要评估一个策略的好坏,就需要建立一个对比基线,以便后续观察算法效果的提升。此处我们可以简单地对推荐算法进行建模作为基线。假设我们的训练数据为:  三元组, 其中user为用户id, item为物品id(item可以是MovieLens上的电影,Amazon上的书, 或是百度关键词工具上的关键词), rating为user对item的投票分数, 其中用户u对物品i的真实投票分数我们记为rui,基线(baseline)模型预估分数为bui,则可建模如下:
其中mu(希腊字母mu)为所有已知投票数据中投票的均值,bu为用户的打分相对于平均值的偏差(如果某用户比较苛刻,打分都相对偏低, 则bu会为负值;相反,如果某用户经常对很多片都打正分, 则bu为正值), bi为该item被打分时,相对于平均值得偏差。 bui则为基线模型对用户u给物品i打分的预估值。该模型虽然简单, 但其中其实已经包含了用户个性化和item的个性化信息, 而且特别简单(很多时候, 简单就是一个非常大的特点, 特别是面对大规模数据时)
基线模型中, mu可以直接统计得到,我们的优化函数可以写为:
其中参数lambda1及之后的式子是为了防止过拟合产生。 其中rui为已知的投票, mu可直接统计, 对每个用户的参数bu, 对每个item的bi可求(相当于AX=B,求X,此处X即为bu, bi,可使用最小二乘法, 例如可使用Numerical Recipes: The Art of Scientific Computing中提供的优化函数) ,当然, 最简单的方法就是直接根据当前的观测值, 直接统计出bu 和bi, 统计方式如下:
其中lambda2, lambda3为手动设定参数(在MovieLens上为20左右效果比较好, 才参数相当于降低投票较少的用户, 以及被投票较少的item对整体预估效果的影响), R(u)为用户u投了的item的rating集合,R(i),为投票给item i的rating集合。
基线实验结果
还有一种更简便的方法, 就是直接使用user,item的rating的平均值直接预估bi,bu,例如直接计算bu = sum(Ru)/len(Ru),其中Ru为用户u投票的集合, sum(Ru)为这些rating值得和, len(Ru)为该集合大小。bi = sum(Ri)/len(Ri), 其中Ri为用户i被投票的集合, sum(Ri)为这些rating的分值之和, len(Ri)为这个集合的大小。我们将此方法记为baseline1,上文描述的方法记为baseline2。 以下为两种方法在不同lambdau,lambdai值下的具体表现(其中两个lambda值在实际应用中可以根据代价进行全空间搜索最优解), 具体分值代表RMSE。
图: 两种基线的RMSE效果表现
可以看到,随着lambdai和lambdau的增长, 两种方法的RMSE均在下降, 且效果上, baseline2 优于baseline1。
基线源代码
源码文件对应为RecBaseLine.h,其中RecBaseLine封装了baseline1的实现, RecBaseLineAdv封装了baseline2策略的实现, 而每个推荐算法均继承自RecTask, 所有每个推荐算法除了接受该算法特有的参数外,还必须提供以下接口。
其中代码在上传时添加了部分注释。
因式分解实现协同过滤
上文中实现的两种基线算法,仅仅孤立地去考虑user, item的投票偏差, 并没有将二者建立内在联系。此时我们可以对这种内在联系通过隐主题进行建模。 最经常使用的方式莫过于SVD。
以MovieLens电影推荐为例,SVD(Singular Value Decomposition)的想法是根据已有的评分情况,分析出评分者对各个因子的喜好程度以及电影包含各个因子的程度,最后再反过来根据分析结果。
使用SVD对问题进行建模
SVD的想法抽象点来看就是将一个N行M列的评分矩阵R(R[u][i]代表第u个用户对第i个物品的评分),分解成一个N行F列的用户因子矩阵P(P[u][k]表示用户u对因子k的喜好程度)和一个M行F列的物品因子矩阵Q(Q[i][k]表示第i个物品的因子k的程度)。用公式来表示就是
R = P * T(Q) ,其中T(Q)表示Q矩阵的转置
下面是将评分矩阵R分解成用户因子矩阵P与物品因子矩阵Q的一个例子。R的元素数值越大,表示用户越喜欢这部电影。P的元素数值越大,表示用户越喜欢对应的因子。Q的元素数值越大,表示物品对应的因子程度越高。分解完后,就能利用P,Q来预测Zero君对《七夜》的评分了。按照这个例子来看,Zero君应该会给《七夜》较低的分数。因为他不喜欢恐怖片。
图: 推荐问题的因式分解建模
实际上,我们给一部电影评分时,除了考虑电影是否合自己口味外,还会受到自己是否是一个严格的评分者和这部电影已有的评分状况影响。例如:一个严格评分者给的分大多数情况下都比一个宽松评分者的低。你看到这部电影的评分大部分较高时,可能也倾向于给较高的分。在SVD中,口味问题已经有因子来表示了,但是剩下两个还没有相关的式子表示。因此有必要加上相关的部分,提高模型的精准度。改进后的SVD的公式如下:
其中mu表示所有电影的平均分,bu表示用户评分偏离mu的程度,bi表示电影评分偏离mu的程度,P,Q意思不变。特别注意,这里除了mu之后,其它几个都是向量。其中qi, pu的维度, 就是隐主题的维度。
分解完后,即(1)式中的五个参数都有了正确的数值后,就可以用来预测分数了。假设我们要预测用户u对电影i的评分:
加入了防止过拟合的lambda参数后, 我们的优化函数为:
有了这个优化目标函数后, 就可以使用较多的手段来进行优化了。
以下主要使用梯度下降法解优化目标函数。具体的公式推导可参见论文。同时还可以使用ALS算法进行求解(该方法已经融合进mahout,后续会有专门文章对该算法进行介绍并给出实验结果)
最终推导出的求解公式为:
在实现时, 设定最大的迭代次数, 以及收敛的误差, 即可经过迭代球接触bu, bi, qi, pu
因式分解同过滤代码实现
因式分解的实现使用了RecTask, 故封装使用了一致的接口。具体感兴趣的同学可直接review source code
图:使用梯度下降求解因式分解CF推荐。
因式分解CF效果对比
此处就仅给出两组程序直接运行出来的结果及对应参数, 可以看到, 在latent factor的维度为30, 设定gama和lambda后, RMSE就降低至0.903105,效果比较明显。
以下为具体配置参数:
task:SGD30,mae:0.687782,rmse:0.903105
mu:3.528350,lambda:0.200000,gama:0.020000,min_res_err:0.010000,max_iter_num:10000,fea_dim:30
上文描述算法的hadoop版本未上传网盘, 如感兴趣可以邮件沟通。
参考文献:
Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008: 426-434.
Zhou Y, Wilkinson D, Schreiber R, et al. Large-scale parallel collaborative filtering for the netflix prize[M]//Algorithmic Aspects in Information and Management. Springer Berlin Heidelberg, 2008: 337-348.
Bell R, Koren Y, Volinsky C. Modeling relationships at multiple scales to improve accuracy of large recommender systems[C]//Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2007: 95-104.
Shapira B. Recommender systems handbook[M]. Springer, 2011.
文中描述算法代码实现及评测框架参见:http://pan.baidu.com/share/link?shareid=2198676312&uk=1493671608
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com

百度关键词搜索推荐系统交互流程

如果把百度凤巢系统比作商场,那这个商场的主要商品是什么?答案就是‘流量’,而关键词,就是流量对广告主最直观的表现载体。

客户想要在百度上做搜索广告,就需要找到能够准确描述自己推广意图的关键词集合;但另一方面,目前百度凤巢系统拍卖词接近10亿,百度每天有PV关键词约数十亿。从这些词海中淘出优质关键词,无论对于客户本身,还是为客户打理账户的客服而言都是一大挑战。
此时百度关键词搜索推荐工具(KR)就显现出它的重要作用。
那KR到底是什么呢?顾名思义,KR(Keyword Recommendation缩写)就是百度向客户推荐关键词的工具。当然,KR不仅提供诸如被动,主动,按URL,按行业等推荐形式为客户推荐个性化关键词,同时还提供像种子词,种子URL,Suggestion等引导提词技术;另外KR还提供客户账户诊断优化服务,一方面优化客户账户结构,提升客户提词,账户管理效率,同时也达到提升客户消费,提升百度凤巢系统整体消费的功能。

因为该工具是提供给百度广告主使用的,所以在网络上没有直接的入口,需要再www2.baidu.com上注册帐号后,找到‘关键词工具’后进行访问。

百度关键词搜索推荐交互

以下为关键词工具使用流程:

广告主进入KR入口(www2.baidu.com)中有多个入口,此时KR会根据广告主在凤巢中的历史操作行为,为其推荐种子关键词,广告主可以直接点击种子关键词进行搜索(种子关键词主要是面向对KR使用不熟练的客户,对他们的使用进行引导,百度搜索框也没有该功能,该功能为KR独有); 之后网民可输入搜索搜索query获取和该query字面,语义相似的关键词,同时系统会返回和这些关键词相关的属性。然后用户可以对关键词进行筛选及分组(系统会提供多种分组建议)

图: 百度关键词搜索推荐系统交互示意图

同时KR也提供传统推荐的方式为广告主推荐关键词。就是根据客户历史提词行为,使用SVD,图关系挖掘等协同过滤技术直接将结果推荐给广告主,广告主无需有任何交互输入,直接进入提词页面就能看到结果。

搜索系统策略架构

百度关键词搜索推荐系统(KR)不仅提供典型的推荐服务,即不搜既得,同时也提供搜索功能,即用户输入关键词进行搜索,KR推荐出与该关键词最相关的top n 关键词, 这些关键词不仅附带有容易理解的推荐理由(表明该关键词为何推荐出来),同时附带有关键词的各种属性(例如关键词在百度上的流量,竞争激烈程度等信息),同时对关键词按照字面,语义进行聚类;推荐出来的关键词默认已按照字面,语义相关性及marketing rule进行了排序。 以下为KR搜索过程online部分的策略架构(offline部分涉及较多数据挖掘逻辑,参见之前的文章介绍)

其中最底层为各种基础数据及这些基础数据经过预处理, 清洗后的存储, 以及基于这些过程的挖掘数据。当用户发起一次请求时,系统会经历以下主要步骤:

  1. 关键词触发: 根据经典的字面进行触发以及语义, 同购关系及复杂图关系的挖掘数据,触发出推荐关键词的候选。对应到百度搜索引擎上,该步骤就是query改写变换及文档的检索。
  2. 相关性准入:考虑到后续的过滤步骤, 触发的关键词量一般需要比最终需要的关键词数量多以保证召回。此时需要对这些候选关键词进行相关性过滤。例如使用GBDT模型进行二分类: 相关 or 不相关。
  3. audit:推荐出的关键词可能涉及黄赌毒, 为避免风险, 这些关键词需在推荐时尽早过滤。搜索引擎上,也需要对一些黄赌毒反内容进行过滤。
  4. ranking:为提升KR推荐的效率, 使用提词率模型,效用模型及价值模型对剩下的候选关键词进行排序,同时需要根据应用场景对关键词进行过滤(例如用户有pv过滤需求,则需要将pv值小于阈值的关键词过滤);对应到百度上, 最重要的技术就是ctr预估及质量度。
  5. marketing rule:此处集中了人工干预的逻辑,例如: 假设某个时间段需要KR推荐该消费的关键词,此时可以在此处增加逻辑对候选关键词队列进行重排序; 或者对于某些bad case进行过滤。搜索引擎上也需要有该逻辑层, 以便最快速度对结果进行人工干预。
  6. UI:关键词的展现, 以及保存等功能,同时包含传统推荐系统的正负反馈信息收集,反馈等机制; 以及KR独有的关键词分组功能,信息筛选功能等。对应到搜索引擎上就是前端的展示。

主动推荐策略架构

KR中的主动推荐,就是传统的推荐技术在百度关键词搜索推荐中的应用。所谓主动,是针对KR而言的:关键词,广告主无需发起交互操作,KR即使用传统推荐技术: content-based, collaborative filtering及多种技术混合的hybrid filtering方法向广告主推荐结果。

以下为KR主动推荐的策略架构, 一方面KR使用网民搜索日志,点击日志,广告库数据构建item候选集合,另一方面系统收集广告主的反馈(explicit or implicit)构建user profile,之后基于这些信息使用推荐算法向客户进行推荐。如果KR中的搜索功能是即搜即得, 那么主动推荐就是不搜即得

图:百度关键词搜索推荐系统主动推荐策略架构

按网页内容进行推荐

百度凤巢广告主都有自己的推广网站(或主页),而要达到较好的推广效果,广告主应该提交与网页相关性较高的关键词,否则即使广告主因为提交了一个高PV的关键词导致来到网站的流量较高, 也会因为内容与关键词不相关而导致转化较低而得不偿失。

KR为此提供了按URL进行推荐, 即广告主在KR搜索框中输入某一个网址(例如semocean.com),则KR会抓取该网站并分析其中的主题词进行推荐, 以下为主要的策略流程。

图:KR按URL推荐策略处理流程

 

每一种KR推荐算法, 或者做一个延伸:每一个商业搜索引擎中, 都会包含以下几个模块:触发,相关性过滤,rank,marketing rule。

其中触发是根据输入,找到一个相对较大的候选集合, 之后的所有排序过滤都是针对该集合的(在学术界使用的数据;例如搜索引擎中,根据网民输入的query,进行简单的字面语义匹配后,找到潜在的候选集合作为后续处理的对,又例如在学术界使用的LTR任务的开放数据LETOR中,直接使用BM25进行校验,筛选出相关性较高的top N进行后续的ranking实验; 之后对返回的结果进行相关性过滤及排序,最后根据一些业务规则进行强制过滤及重排序,包括黄赌毒反动内容的过滤,或是某些特定的人工干预。

图:KR搜索推词逻辑

 

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

经典聚类算法及在互联网的应用

此处并不会列举每一种聚类(Clustering)算法,因为学术界Clustering算法如果真要细分,还真有很多变种。此处只会介绍几种在我近几年互联网工作生涯中实际碰到的具体问题, 以及如何使用Clustering算法解决这些问题。

一般来说,我们可以将Clustering认为是将出现的数据进行Data Segmentation,也就是经常说的哲理: 物以类聚。 从机器学习的观点来看, Clustering算是Unsupervised Learning,或者叫做Learning by Observation,根据观察到的情况进行Clustering。 因为形成簇的数据都被聚到一起,所以Clustering 方法也可以用来发现噪音或是异常点。

Clustering 算法大致可以分为以下几类(参见Data Mining Concepts and Techniques):

  1. Partitioning Methods:这是一类经典的,最简单的聚类方式,就是直接按照类内的点距离最近,类间距离足够远的原则进行数据Clustering。该类方法比较经典的方法有K-Means 和K-Medoids。下文中会以广告分段问题来具体介绍K-Means的实现(K-Medoids类似)
  2. Hierachical Methods:层次Clustering算法,又大致分为bottom-up和top-down两种思路,bottom-up为自底向上,逐渐合并离得比较近的类以形成更大的类,top-down为一种divisive的思路,逐渐对离得比较远的类进行分裂。下文中会以如何合并搜索引擎中的同意,近义词词形成簇的的方式具体介绍bottom-up hierachical methods。
  3. Density-based Methods:以上两种方法基本上都是在高维空间中将数据聚成球形的多个类的方法,却不能处理非球形的聚类,Density-based Methods就是解决非球形数据的聚类方法。
  4. Model-based Methods:对数据进行建模,之后使用观察到的数据预估模型参数,比较经典的使用EM方法,先假设数据服从某种分布(例如k个高斯分布),并且这k个高斯分布由一系列隐随机变量决定。之后在E步预估这些隐随机变量,而在M步固定这些隐随机变量后,使用最大似然估计迭代得到最优参数。

文章以下内容将介绍3种聚类方法解决3个问题:

  1. 使用K-Means方法对广告受众网民进行Data Segmentation。
  2. 使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐。
  3. 使用EM方式寻找数据中的隐藏主体。

 使用K-Means方法对广告受众网民进行Data Segmentation

K-Means是一种球形的聚类,在二维空间中,类别会被聚成以圆心为中心的圆,三维空间中则会被聚成以球心为中心的球状簇(当然,这与选择的相似度度量有关,例如使用cosine计算归一化后的两个向量长度,就会变成计算二向量的夹角)

在K-Means算法运行前,有两个因素比较重要: 数据预处理和距离度量方法。具体距离度量参见博文相似度度量 ,数据预处理则包括数据归一化, 去除噪音等操作。

因为K-Means算法本身较为简单,此处直接给出Andrew Ng机器学习公开课教案中的伪代码:

k-means

其中uj为第j个簇的中心点,ci为第i条数据的簇类别。基本步骤就是遍历数据,每一轮迭代,先计算当前数据与哪个类中心最近,该条数据属于距离最近的簇,之后根据新计算出来的每条数据的类别,更新类中心。下图给出在指定数据上给出2个类的4轮迭代情况:

k-means-4-iteration

使用distortion function度量分类的好坏情况, distortion 越小越好,当然,一般distortion大小需要和类别 k 的数量间进行权衡。

distortion_function

应用: 虽然k-means堪称最简单的算法,但之前在实习时,在前东家还是用了一把,应用场景是使用MSN用户的注册信息(年龄,喜好,性别),以及MSN用户在 msn.com上经常访问的导航类别,搜索关键词等数据,使用决策树选出区分度较大的特征构成特征向量,使用L1-Norm进行归一化后,对特征向量进行Clustering。之后按Clustering向广告主售卖这些用户的pv。 该模式的优势是具有一定的兴趣定向作用。

 

右侧即为MSN展示广告。当然,该方法已经是2007年所使用的方法,现在相信MS已经使用更精准的方法了 。

该过程中尝试较多的是如何选择合适的类别数量k值,以及如何初始化初始类中心。当时迫于项目进度,k值最后根据经验并进行了粗略的搜索选择,初始类中心则使用在相同k值得情况下进行多次随机初始化Clustering

使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐

例如在搜索引擎中, 很多网民的query意图的比较类似的,对这些query进行聚类,一方面可以使用类内部的词进行关键词推荐; 另一方面, 如果聚类过程实现自动化, 则也有助于新话题的发现;同时还有助于减少存储空间等。

例如:

训龙记国语  训龙记2 寻龙记  训龙记博克岛的骑手  驯龙记电影

骂人大全    骂人不带脏字的顺口溜    骂人带脏字越毒越好  骂人脏字的狠话

要设计层次聚类,就需要考虑一下几个因素及环节:

  1. 使用何种聚类算法: top-down 还是bottom-up 还是其他
  2. clusting的合并策略
  3. 使用哪些特征
  4. 如何度量距离
  5. 使用何种评估标准对效果进行评估

确定以上5个因素后,聚类算法也就确定了。

层次聚类

聚类算法:考虑到实现的复杂度, 一开始我们就确定使用bottom-up的方式作为聚类策略;后续也就没有尝试top-down的方式。

clusting的合并策略:

一般有两类合并策略: 选取最相近的两个clustering进行合并;求连通分量。 因为寻找相近cluster的方式, 时间复杂度会达到O(n^2), 所以最后决定使用连通分量。

特征: 我们使用字面特征及query在session中的共现特征; 例如, 对字面进行切词后的term(做适当过滤降维:idf太小则过滤)

距离函数, 尝试过cosine和jaccard后, 最终使用jaccard作为距离度量。

也可关注微博: weibo.com

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