如何使用机器学习解决实际问题-以关键词相关性模型为例

本文以百度关键词搜索推荐工具字面相关性模型为基础,介绍一个机器学习任务的具体设计实现。包括目标的设定,训练数据准备,特征选择及筛选, 以及模型的训练及优化。该模型可扩展到语意相关性模型,搜索引擎相关性及LTR学习任务的设计实现。该模型的设计调研实现,也可以很容易移植解决其他包括语义相关性的问题

目标设定:提升关键词搜索相关性

作为一个搜索+推荐产品,百度关键词搜索推荐系统的产品形态是向凤巢用户推荐适合他业务的关键词。例如一个卖鲜花的广告主,他想在百度上做关键词搜索推广时,需要提交和他业务相关的关键词,而且提交的关键词需要业务相关,例如他需要提交和卖鲜花业务相关的关键词。例如鲜花快递,鲜花速递等。此时他可以在百度关键词搜索推荐系统中进行搜索查询,选择适合他的关键词。

百度关键词搜索推荐系统query搜索

这是一个典型的搜索问题,具体的从输入query,到触发,到排序等会涉及到很多因素,例如如何查倒排,如果处理地域因素等;要提升搜索的质量,我们首先需要保证输入的query和推荐出来的推荐词的相关性,此处我们要解决的主要问题, 就是如何快速,准确地判断两个关键词(输入query和推荐词)的相关性,需要特别注明的是,我们主要的目标是让用户觉得该产品结果很靠谱, 所以该处我们仅考虑字面相关性,更多的语意扩展该模型并未考虑。

注:该模型的调研实验实现方式, 可以很容易平移到语义相关性。例如加入更多语意特征,例如plsa的bm25特征和word2vec的相似度特征(或者和扩展的相关性校验,例如将待推荐词扩展为baidu搜索结果的摘要扩展)提高语义特征的贡献。

相关性也是所有搜索问题的基石,只不过在不同的系统中使用方式不一样, 在一般的搜索中,相关性占有较大权重, 排序基本就以相关性为依据; 在商业系统中,相关性则经常作为搜索展现的门槛用于控制商业推广结果的质量(如果仅考虑CTR, 用户搜索鲜花快递时,给用户展现艳照门的结果,CTR会更高,但相关性较差)。  当然,判断相关性我们可以简单使用某一种方法进行直接判定,例如直接进行两个关键词的TF-IDF计算,或是进行两个关键词的BM25。但这样的方式效果都不太理想,想要达到更好的效果,就需要使用更多特征,而更多特征很自然地,需要使用模型组合这些特征,达到最终的预期效果。

图:相关性在关键词系统中的位置

此处将会使用机器学习的方法解决该问题。本文以下内容会从数据准备, 特征选择, 模型选择, 模

型调优等步骤介绍百度关键词搜索推荐系统如何解决该问题

数据,特征,模型

说到使用机器学习解决问题,我们经常提到的优化思路就是3方面的优化: 数据,特征,模型。首先找到充足的,准确的label数据(该出仅考虑有监督学习任务,例如相关性,或是LTR),之后提取贡献较大的特征作为input space,以label作为output /ground true label,之后优化模型(Hypothesis) )。下面会分别从这3方面对整个优化过程进行阐述

准备训练数据

训练数据的获取一般有几种方式:

  1. 人工标注: 优点是质量较高,噪音较少;缺点是标注结果和标注者本身的认识相关,例如在搜索引擎中,判定苹果和手机的相关性,对于年轻人,一般都认为相关;但对于比较多的老人,可能认为不相关;另外一个缺点就是人工获取标注的成本较高
  2. 从日志中进行挖掘:优点是数据量相对更大,获取成本较低(编写几个hadoop脚本对日志进行统计);缺点是噪音较多,例如搜索引擎中的恶意抓取访问导致的噪音数据

在相关性模型中,一开始我们使用百度关键词搜索推荐系统的人工反馈数据作为label对模型进行训练,分别提取1.5W query-推荐词pair作为正负例进行特征提取,模型训练。

 

如图所示,在交互上,当用户喜欢该关键词时,就会点击‘大拇指’表示该结果符合用户需求(正反馈,该query-推荐词 pair可作为正例);如用户认为该关键词不符合需求,就会点击‘垃圾桶’,将该关键词扔入回收站(负反馈,该query-推荐词 pair 可作为负例)

在实验中,我们发现正例没有问题, 不过负例中会存在较多这样的情形: query-推荐词是相关的, 但该用户不做该业务,所以被定义为负例,所以负例个性化较强。所以后来我们让产品经理同学又对负例子进行筛选,重新标注1.5W负例,进行后续特征提取, 模型训练。

之后我们将正负例打散后(直接使用python random.shuffle)分成10份,进行cross-validation

模型训练前,先定标准和样本

注: 训练样本的挑选完全决定了我们的问题目标,所以在一开始就需要准确选择,如果可能,所有的case都最好人工来搞,或者至少需要人工review。 确定没有问题后,再开展后续工作。特别是相关性类似的问题,比较主观,例如PM和RD在该问题的判断上就可能存在一定差异。

确定完训练样本, 评估标准,之后再小布快跑, 优化模型。

特征提取

一般特征的选择及处理会极大地影响学习任务的效果,而进行特征选择的时候,一般是先增加特征,并实验效果。 对于相关性模型, 我们可以先将传统的信息检索的特征加上,这些特征一般分为以下几类:

  1. query/候选词的一般结构特征: 例如query/候选词长度,term数等
  2. query-候选词的相关性度量:例如TF-IDF, bm25, LMIR及多重变种, plsa相似度度量,word2vec语意向量相似度等; 很多时候,关键词自身信息较少,还可以使用关键词在搜索引擎上的摘要扩展进行相似度度量
  3. 关键词自身在信息检索维度的重要性度量,例如关键词idf, 从语言模型方面的重要度等

在一开始的时候,我们可以先将能够想到,构造出来的特征均加入特征向量进行实验,而且每加一类特征,都可以看下该类特征对整体目标的提升程度。以便对该特征的贡献度有一个直观的感受。

以下数据可以简单看出随着特征的增加,效果的提升,其中的特征仅加不减(模型使用random forest   进行二分类):

等到特征加得差不多,模型准确性已经提升不多的时候, 可以考虑砍特征,有一种比较简单粗暴有效的砍特征的方法,就是使用树模型,就是直接砍掉特征贡献程度及特征重要性较低的特征,例如直砍掉特征贡献度为0的特征,对相关性模型的准确性几乎没有影响

特征贡献度

当增加特征已经很难提升效果, 考虑到为了防止过拟合,同时考虑到模型online预测,需要对特征进行挑选。在使用树模型时,可以直接使用数节点特征贡献度和节点使用次数,判断是否需要去除该特征,以下为使用树模型进行选择特征的例子:

对于特征贡献度和分裂特征使用次数为0的特征,在调研时,直接去除对模型效果几乎没有影响,而且能提升预测的效率。

在选择特征的时候, 有一些经验值得分享:

  1. bm25特征及term weight特征对分类任务有极大贡献
  2. 一些单独的比值类特征并没有太大贡献,例如query,推荐词共同term与query term数,推荐词term数的比值,这些特征并没有太大贡献,但是这些特征与query,推荐词的term数结合到一起,贡献就非常多;所以有些特征需要联合在一起,才有较大作用。
  3. 特征选择需要和目标一致:例如word2vec是非常高大上,且非常靠谱的技术,但用在字面相关性,对目标并没有太大贡献(如果目标是语意相关,那么类似于PLSA,word2vec将会有很大贡献)
  4. 有些特征就就是用来解决特殊case的,虽然贡献不大,但需要保留(当然也可以直接设置为强规则与模型配合),例如query与推荐词拼音一致

模型选择

经典模型

最开始我们尝试了最大熵,SVM和adaboost模型, 考虑到online使用的效率,最终我们选择了adaboost模型作为线上使用的模型,虽然效果不是最好的,但使用简单的weak learner构建的模型的确比较快(参见博文:《adaboost》),并且使用adaboost进行上线并取得较好效果:上线后不仅召回增加,准确性上90%的case相关性高于等于原有结果(采用非模型的版本)

评估结果分布图(2到-2分别代表扩召回结果相关性高于、略高于、等于、略低于、低于线上策略)

集成树模型

现在特别喜欢使用树模型,因为使用的时候,连特征归一化都省了: 如果使用SVM类似的模型,还需要对特征进行归一化等处理, 但使用树模型,直接将特征向量及label扔给模型, 模型自己会根据信息增益,或是基尼系数等标准选择最合适的拆分点进行树节点的拆分(具体的拆分标准可参见博文:《使用impurity选择树模型拆分节点》),开源的树模型,例如大名鼎鼎的Quinlan的C4.5或是C5.0都在调研时都可以拿来试试作为特征选择的依据。

特别是集成树模型的出现,更是极大地提升了树模型效果。所以现在的项目中,我比较喜欢在增加特征的时候就使用集成树模型进行效果实验。 具体树模型使用参见《集成树类模型及其在搜索推荐系统中的应用

集成树模型配置选择

此处的配置选择和传统的模型参数稍有区别,该出的树模型配置主要指集成树模型中树的数量,每棵树的特征选择因子和样本使用因子等。在项目中,考虑到准确率和速度,最终确定的参数是树的数量是20, 特征选择因子和样本选择因子均为0.65(每棵树随机选择0.65的样本和特征进行训练)

具体产品效果可参见www2.baidu.com中百度关键词搜索推荐系统的排序结果:

如何个性化

首要需要考虑的是我们的数据样本,是否本身就是包含个性化的case(此处的答案是否定的); 假设我们的标注case是个性化的,也就是case中本身就包含了个性化结果时,在模型训练流程上其实并没有太大区别, 主要的区别就在于我们选取哪些能够区分这些个性化的特征, 例如百度凤巢中账户(单元)的plsa模型产出的pzd向量与query的相似度等

登录www2.baidu.com->关键词工具->搜索query->查看结果 即可。

更多内容也可参见: 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)得到的关联电影集合。
其中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

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

决策树是经典高效的机器学习分类算法, 非常适用于线性模型效果不能满足需求, 规则描述分布比较合适的场景。而决策树与传统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

关键词推荐工具中的用户引导机制

搜索引擎根据网民输入的检索词(query)猜测网民需要的信息, 之后进行检索, 排序后将相关的信息展现给网民。 因为网名输入的query一般都较短, 而且不同的网民使用搜索引擎的能力也不一样。 所以一般搜索引擎都会有些查询引导机制, 在猜测用户可能的意图后, 推荐一些相关且高质量的种子query给网民。例如在百度搜索框搜索‘关键词工具’,在搜索结果的最下方,出现以下相关搜索结果:
这些相关搜索结果均是根据网民搜索session和网民搜索点击结果挖掘而来(因可能涉及泄密,百度的具体实现此处就不再介绍, 后续会有博文介绍业界相关相关搜索结果的论文), 这些(推荐)query一方面从搜索意图上和网民的搜索意图匹配, 一方面和也能够达到引流的作用,例如能够快速引导网民找到需要的内容, 或者考虑商业变现因素, 能够将搜索引导向与搜索意图匹配且有商业价值的搜索上, 提升搜索引擎的变现效率。
而作为完整的关键词推荐工具, 不仅要能主动分析推荐结果给客户(关键词工具的用户为搜索引擎的商业客户,及广告投放客户), 在用户输入种子query后展现相关结果给客户,还需要在客户操作的每一步, 对客户的行为进行提示和引导。
关键词工具引导机制的功能
关键词推荐工具不仅能根据用户历史行为主动向用户push相关关键词,同时提供搜索功能, 供用户输入种子query后推荐出相关的关键词。 此时就会面临和搜索引擎一样的问题, 用户输入query的质量,将会直接决定推荐结果的好坏, 所以关键词推荐系统需要有完善的引导机制, 提升用户输入query的质量,以便提升整体的推荐质量。
上图为KR关键词推荐工具
引导机制的类型及简单实现思路
一般说来, 根据用户使用关键词工具的交互操作,按照交互阶段,可以将引导机制分为以下三类:
  1. 查询前: 在用户进入关键词工具时, 还未有任何交互时,此时关键词推荐系统主动向用户push用户可能感兴趣的种子query; 具体实现时,可以根据客户历史上采纳的搜索引擎拍卖词(即客户采纳的符合客户客户推广意图的关键词)分析出客户的推广意图或业务点, 使用传统推荐算法(content-based 或 collaborative 推荐算法)找出客户可能感兴趣的种子query进行推荐。该场景更偏推荐问题
  2. 查询中: 即用户已经开始在关键词工具搜索框中进行输入,但输入还未完成的阶段。此时最常采用的方式是使用suggesion的方式,结合客户当前输入,向用户推荐完整的高质量query;具体suggesion挖掘,可以找到一些高频的query,结合session数据,搜索点击数据进行挖掘(百度suggesion具体的算法此处涉及泄密不再介绍,后续会有文章介绍业界公开的suggesion方法)
  3. 查询后: 当客户完成一次搜索后, 客户搜索的内容已经基本明确, 此时就可以根据这次用户的搜索意图,找到相关的更高质量的query,以类似于搜索引擎相关搜索的方式推荐给客户。
引导机制在整个系统中的地位
引导机制无论是在搜索引擎中, 或是关键词推荐系统中, 都是必不可少的功能环节,能够带来以下收益:
  1. 推荐给客户能有多而好的检索结果的种子词,并逐步进行优化,提升用户体验,提高客户提词量;对于搜索引擎而言是优化输入query。
  2. 降低未曾使用过KR的客户的使用门槛,让KR的使用更为简单便利,扩大关键词工具的市场占有率;对于搜索引擎而言, 也能够快速提升其他用户经常搜索的相同/类似意图的query给网民,提升搜索量。
  3. 通过种子词引导客户对账户关键词的优化,提高客户的ROI,提升百度收益,达到双赢目的。对搜索引擎而言则是能将搜索引导至相同/类似意图的搜索上,提升搜索引擎的变现效率。
如对以上功能感兴趣, 各位可以在www2.baidu.com上注册一个凤巢帐号(无需缴费), 在百度凤巢系统中的关键词工具中试用上述功能。
更多内容参见:
百度凤巢系统: www2.baidu.com
suggestion的一种实现方法: Cao, Huanhuan, et al. 2008. Context-Aware Query Suggestion by Mining Click-Through and Session Data. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2008, 875-883.
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com

搜索引擎点击日志聚类实现相关搜索

组里经常招实习生, 在技术问题问得差不多的时候, 我经常会问他们一个问题:‘百度的相关搜索,你会如何设计实现?’   主要想看下实习生会有哪些思路,看看思路是否广,方法是否多, 没有啥方法的话, 我会提示下,看他是否能够一些思路。
其实各大搜索引擎的‘相关搜索‘ 虽然涉及到的细节会比较多, 包括如何权衡点击,用户体验,收入之间的关系等细节,主要的挖掘算法还是比较类似的。 从数据上来说,基本上围绕着网民搜索的session数据,网民点击数据,涉及到商业变现的话,可能会引入广告主的信息。
百度的相关搜索的实现这里就不介绍了(可能涉及泄密),这里主要介绍之前看过的一篇论文: Agglomerative clustering of a search engine query log    使用搜索点击日志进行query聚类,并使用层次聚类结果进行相关搜索结果挖掘与推荐。希望对大家有所帮助。
算法中的创新点, 是在对query进行聚类的同时, 也就将URL进行了聚类。聚类的过程没有使用query的内容信息, 而是直接使用了网民的行为信息(搜索,点击行为)。这种思路和协同过滤类似, 就是不考虑推荐item的内容,而是使用用户的行为数据直接进行推荐。
算法首先使用点击日志, 格式为的pair,构建双边图,左边为query, 右边为url,如果搜索query后点击了url则链接该query和该url代表的节点建立一条边。该二分图的建立方式如下:
二分图示例如下,左边为query,右边为被点击url,边为搜索相关query后点击对应的url:
在这里,query的内容和url的内容不重要,直接将其mapping到一个唯一ID也没问题
定义N(x)为x的邻居点, 则可以定义query点x, y 的相似度如下:
该相似度介于[0,1]之间,即, 当x,y 均为query时, 使用与x,y均相邻的节点比例度量他们之间的相似度; 相对地, 当x,y均为url时,使用共同搜索query定义其相似度。该度量方式和Jaccard度量方式原理类似。
之后的工作便是迭代进行聚类,每次使用url计算两两query的相似度,合并最相似的query; 之后使用query作为特征计算两两url的相似度,合并最相似的url;一直迭代直到终止条件。
之所以每轮迭代都要对query和url分别进行,是因为只有这样才能找出原来不明显的一些聚类关系。例如下图,在点1,2 合并为1’前, 是不能直观看出a和c之间的关系的:
终止条件一直是agglomerative聚类的重要问题, 一般的思路是一直合并到不能合并为止, 但实验中一般这样的话会合并出很多较大的cluster, 所以很多时候会采用控制每个cluster的大小(或是层数),以及最多的类的个数等因素作为合并的终止条件。
使用该方法即可将搜索引擎的点击日志进行聚类。 具体应用时,当网民输入某个具体query的时候, 判断该query所属的cluster, 之后该cluster中的query即可作为相关搜索的结果的候选,当然cluster的query具体展现哪些, 以及如何排序, 又可以有很多因素需要考虑, 例如点击率, 用户体验, 倒流量的能力等, 此处不再进一步讨论。 使用该方法最大的优势是不用考虑query的内容信息, 而是直接使用网民的行为信息进行聚类(此处与推荐系统中协同过滤有异曲同工之处)。 当然, 具体工程实现中, 我们也可以使用类似于推荐系统的思路, 融合入按内容的特征联合进行聚类, 取得更好的效果。 例如重新重新定义相似度度量方式, 使用点击关系和内容相似度进行加权作为最终相似度:
其中cross_ref_similarity表示根据关系数据得到的相似度, 更多内容可参见‘Query Clustering Using User Logs’
更多内容参见原论文:
Beeferman, Doug and Berger, Adam. 2000. Agglomerative Clustering of a Search Engine Query Log. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2000, 407-416.
Wen, Ji-Rong, Nie, Jian-Yun and Zhang, Hong-Jiang. 2002. Query Clustering Using User Logs. ACM Transactions on Information Systems. January 2002, Vol. 20(1), pp. 59-81.
也可关注微博: weibo.com
或是直接访问: http://semocean.com

adaboost

使用机器学习方法解决问题时,有较多模型可供选择。 一般的思路是先根据数据的特点,快速尝试某种模型,选定某种模型后, 再进行模型参数的选择(当然时间允许的话,可以对模型和参数进行双向选择)
因为不同的模型具有不同的特点, 所以有时也会将多个模型进行组合,以发挥‘三个臭皮匠顶一个诸葛亮的作用’, 这样的思路, 反应在模型中,主要有两种思路: Bagging和Boosting
Bagging
Bagging 可以看成是一种圆桌会议, 或是投票选举的形式,其中的思想是:‘群众的眼光是雪亮的’,可以训练多个模型,之后将这些模型进行加权组合,一般这类方法的效果,都会好于单个模型的效果。 在实践中, 在特征一定的情况下,大家总是使用Bagging的思想去提升效果。 例如kaggle上的问题解决,因为大家获得的数据都是一样的,特别是有些数据已经过预处理。
以下为Data Mining Concepts and Techniques 2nd 中的伪代码
基本的思路比较简单,就是:训练时,使用replacement的sampling方法, sampling一部分训练数据k次并训练k个模型;预测时,使用k个模型,如果为分类,则让k个模型均进行分类并选择出现次数最多的类(每个类出现的次数占比可以视为置信度);如为回归,则为各类器返回的结果的平均值。
在该处,Bagging算法可以认为每个分类器的权重都一样。
Boosting
在Bagging方法中,我们假设每个训练样本的权重都是一致的; 而Boosting算法则更加关注错分的样本,越是容易错分的样本,约要花更多精力去关注。对应到数据中,就是该数据对模型的权重越大,后续的模型就越要拼命将这些经常分错的样本分正确。 最后训练出来的模型也有不同权重,所以boosting更像是会整,级别高,权威的医师的话语权就重些。
以下为Data Mining Concepts and Techniques 2nd 中adaboost伪代码:
训练时:先初始化每个训练样本的权重相等为1/d  d为样本数量; 之后每次使用一部分训练样本去训练弱分类器,且只保留错误率小于0.5的弱分类器,对于分对的训练样本,将其权重 调整为 error(Mi)/(1-error(Mi)) ,其中error(Mi)为第i个弱分类器的错误率(降低正确分类的样本的权重,相当于增加分错样本的权重);
与测试:每个弱分类器均给出自己的预测结果,且弱分类器的权重为log(1-error(Mi))/error(Mi) ) 权重最高的类别,即为最终预测结果。
在adaboost中,  弱分类器的个数的设计可以有多种方式,例如最简单的就是使用一维特征的树作为弱分类器。
adaboost在一定弱分类器数量控制下,速度较快,且效果还不错。
我们在实际应用中使用adaboost对输入关键词和推荐候选关键词进行相关性判断。随着新的模型方法的出现, adaboost效果已经稍显逊色,我们在同一数据集下,实验了GBDT和adaboost,在保证召回基本不变的情况下,简单调参后的Random Forest准确率居然比adaboost高5个点以上,效果令人吃惊。。。。
Bagging和Boosting都可以视为比较传统的集成学习思路。 现在常用的Random Forest,GBDT,GBRank其实都是更加精细化,效果更好的方法。 后续会有更加详细的内容专门介绍。
参考内容:
Data Mining Concepts and Techniques 2nd
Soft Margin for Adaboost
也可关注我的微博: weibo.com/dustinsea
或是直接访问: http://semocean.com

分类模型在关键词推荐系统中的应用

以下内容均基于百度关键词推荐系统进行讨论
本文内容主要集中在使用机器学习方法判断两个短文本的相关性为基础构建商业关键词推荐系统。 为方便读者理解, 会先介绍该技术的具体应用背景及场景。
广告主在百度或google上进行广告投放时, 需要选择关键词, 以向搜索引擎表述自己想要覆盖的有商业价值的网民搜索流量。 在选择关键词后, 还需要设定具体的关键词匹配模式, 以告诉搜索引擎选择的关键词以何种方式去匹配网民的搜索。 举个例子: 网民在百度上搜索 ‘鲜花快送’, 假设商家A是卖花的, 搞鲜花速递业务的, 则A可以在百度凤巢系统中选择‘鲜花快送’这个关键词,同时设定匹配模式为精确匹配(即网民搜索和A在凤巢系统中选择的关键词完全一致时才出A的广告, 更多细节参见:http://yingxiao.baidu.com/), 假设B在凤巢中未选择‘鲜花快递’, 但选择了‘鲜花速递’, 假设B选择了广泛匹配(语义近似即匹配,具体参见http://yingxiao.baidu.com/), 则B的广告也会被触发(具体是否会展现, 还和出价, 质量度等诸多因素有关)
此时会面临一个问题: 广告主在凤巢系统中选择关键词时, 仅凭自己去想, 很难完全想到所有符合自己需求的关键词(网民的搜索query千奇百怪), 故需要提供工具, 帮助凤巢客户快速找到和自己推广意图一致或相近的关键词,即: 关键词推荐工具。
从交互上来看,可以将关键词工具看成一个搜索引擎,凤巢客户输入一个种子词(种子query),返回一个和种子query意图相近的推荐词list。
当然作为推荐系统, 其中还会包括属性披露, 推荐理由, 关键词行业分类, 关键词自动分组等支持, 这些内容会在接下来的其他博文进行介绍。
整个推荐流程大致如下
整个推荐流程, 大致分为5步:
  1. 基础日志,数据清洗即预处理
  2. 候选词触发: 根据输入种子query触发得到系统性能支持的最大关键词候选(供后续流程进行筛选过滤及排序),当然为保证性能, 该过程中会保留触发关键词的各种基础属性,例如PV, 行业, 主题等; 一般业界的检索,推荐系统会有较多触发逻辑逻辑,故触发出的关键词会比较多
  3. 相关性过滤:因为触发出的推荐关键词较多,故需要判断推荐关键词与种子query的相关性;既要保证召回,又需要保证准确性。
  4. ranking
  5. 使用业务,商业规则对最终结果进行排序调整及过滤(最经典的, 黄赌毒必须过滤删除)
对于相关性过滤,很早以前我们也是使用规则进行过滤,但随着规则数量的急剧增加,一方面导致系统架构性能下降,另外一方面也使系统策略越难约维护,故最终决定使用机器学习方法进行相关性过滤。
涉及到机器学习方法解决问题, 就会涉及到3方面的问题: 用哪些数据,准备哪些数据,如何处理数据? 使用哪些特征? 选用何种model ?
数据
一般来说,如果数据选择有问题, 那基本可以说后边无论再做多少努力, 这些努力都会付诸东流, 公司里这样的机器学习相关的项目也不少见: 几个人全情投入几个月或是1年多,效果总提不上去,回过头来发现数据就有问题,哭都没有眼泪。
所以一开始我们选择数据就比较慎重,还好关键词推荐工具隐性和显性反馈数据都还算比较丰富(推荐系统中都需要有这些信息, 将整个数据流形成完整的迭代闭环): 我们可以认为用户输入一个query并选择了这个query返回的某个候选推荐词的pair,就是一个正例(即模型是判断是否相关,相关为正例,不相关为),而输入一个query后,用户将返回的某个词放入垃圾箱(关键词工具交互上支持该操作),则query及被放入垃圾箱的关键词组成的pair,即为负例。
获得数据后, 很快就发现一个问题: 客户操作得到的正例, 就是毫无疑问的正例;但用户的负反馈(用户使用种子query搜索得到返回结果后,被扔入垃圾箱的的case)很多时候并不一定和query不相关, 甚至是很相关,只是因为用户个性化的原因导致客户认为这个case 不适合自己。
比如: 一个客户主要卖各种花茶, 像菊花茶, 桂花茶等,但他不卖茉莉花茶,此时如果用户输入花茶, 从相关性来说, 推荐‘菊花茶’,‘茉莉花茶’, ‘桂花茶’其实都是OK的,但用户将‘茉莉花茶’放入垃圾箱,因为他不卖该产品。其实并不能说明花茶和茉莉花茶不相关。
为了消除因个性化带来的负例不准的情况,我们人工标注了1.5W非个性化的负例。 并进行随机sampling, 使正负例数量基本相当。
最终使用1/10数据作为测试样本,9/10作为训练样本。
特征
数据准备就绪后,下一步就是如何选择合适的特征了。 因为整个关键词推荐系统所能触发的关键词各式各样, 各种类型千奇百怪, 所以如果直接使用各种地位特征(例如字面,或是ID类)的话,会导致特征空间较大而数据比较稀疏,导致完成分类基本上变成不可能完成的任务; 所以我们不能直接使用字面, ID作为特征进行分类,而是要使用更加泛化,高维的特征。
在特征选择过程中,我们也充分贯彻了站在巨人的肩膀上远眺的方式,充分利用手头的资源,例如短串核心判断,同意变化扩展等基础工具进行特征设计。更详细的特征此处不便于列出,仅列出两个有代表性的特征供大家参考。
  1. 推荐词与种子query经过切词后的相同term的长度之和与种子query经过切词后的term的长度之和的比值;类型为double类型。
  2. 推荐词基本切词后切词顺序包含 query, 特征值为1,默认值为0;类型为double类型。
  3. 推荐词,种子query的topic向量相似度。
  4. 。。。。更多高维特征。。。。。
利用多个类似的高维特征,就能很好地覆盖推荐词与种子query; 当然特征的设计会直接影响关键词推荐中相关性的定义,例如如果字面(重合)相关特征较多, 则推荐主要表现为字面相关,如特征主要为语义特征, 则推荐结果反映为语义相关。如果特征中有用户的历史行为信息特征(例如用户已经选择的关键词),则可以认为相关性模型就已经实现了个性化处理。
 模型
很多项目因为周期比较赶, 所以小步快跑的起步阶段并没有太多时间去做模型和参数的双向搜索,所以综合效率和时间的代价,选择了部分模型及在经验参数下的效果,进行模型的初选。
最终综合考虑性能,准确性和召回诸多因素下,选择了adaboost,在adaboost ratio 和 弱分类器数量上进行了参数实验。 准确性/召回 效果如下:
具体adaboost算法参见: adaboost介绍
WLRatio 300 500 1000 1500
0 0.87/0.89 0.87/0.91 0.87/0.9 0.86/0.91
-0.1 0.81/0.95 0.79/0.96 0.8/0.96 0.8/0.97
-0.2 0.74/0.98 0.73/0.98 0.73/0.98 0.73/0.98
-0.3 0.66/0.99 0.64/1 0.65/1 0.64/1
评估
以上内容均属于线下模型优化部分,所有的指标均可以线下获得, 但最终需要用线上的效果说话, 最后说服力的, 还是线上A/B Test, 因为是后台策略的升级, 故这样的实验在成熟的A/B test框架下比较容易做; 线上实验的最终效果也比较符合预期, 保证准确性的情况下召回大为提升(此处就不贴具体数值)
后文:后来将adaboost直接替换为Random Forest,在未改变模型的基础上效果立刻提升非常多,可见模型选择也较为重要。
参考文献:
百度凤巢关键词工具: www2.baidu.com
Data.Mining.Concepts.and.Techniques.2nd.Ed
也可关注微博: weibo.com
或是直接访问: http://semocean.com