关键词推荐工具中的用户引导机制之四:种子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

关键词推荐工具中的用户引导机制之三:相关搜索query技术

在上一篇《关键词推荐工具中的用户引导机制之二:suggestion架构》中, 我们提到, 在用户在搜索引擎,或是关键词推荐工具中输入搜索query片段的过程中, 我们可以提供suggestion来对用户搜索进行引导。 我们可以认为此时用户的搜索意图是不全面的。 而当用户已经输入完整query后, 用户的搜索用途已经在某种程度上明确了, 此时我们就可以使用相关搜索, 扩展出与用户输入搜索意图一致/类似的高质量query, 引导用户进行搜索, 让用户更快地获取信息, 得到所求。本文会具体介绍相关搜索类似的关键词推荐系统的策略架构,以及业界常用的相关搜索挖掘算法。
说简单一点, 相关搜索query, 其实也是一个关键词推荐。 和adwords中关键词工具, 或是百度关键词工具不同的地方, 是相关搜索对质量要求非常高,而给出的结果一般比较少, 即高准确, 低召回。
图: 百度相关搜索
图: Google相关搜索
以上分别为Baidu和Google的相关搜索结果, 不知道大家是否发现,Baidu相关搜索结果多样性强一些,同时商业价值也强一些(本文不介绍商业价值机制,后文介绍的优化目标中加入商业价值因素即可)
相关搜索策略架构
因为相关搜索就是一个典型的特定场景的关键词推荐系统, 所以相关搜索从策略架构上,会包含完整的关键词推荐的逻辑。 包括候选词源触发(query retrival)、 相关性过滤(filtering)、排序模型排序(ranking), 以及根据规则进行调整(marketing rule)。 其中每个阶段都可以根据最终的优化目标(或者多目标)设计相应架构。
图:关键词推荐策略架构中的主要处理逻辑,包括query retrival, filtering, ranking, marketing rule几大逻辑
各组件功能
  1. 候选词源触发(query retrival):其主要功能是通过各种offline数据挖掘,得到query(或是成份)之间的关系, 获取到候选的待推荐query,供后续逻辑进行处理。
  2. 相关性过滤(filtering):根据应用场景,对不满足query之间相关性的候选词进行过滤,以减轻后续逻辑的性能负担。 相关性过滤的方法可参见《分类模型在关键词推荐系统中的应用
  3. 排序(ranking):根据应用场景的优化目标,对候选词进行排序。 例如, 如果要提升用户体验,那就直接将高相关性的候选词排在前边(衡量标准可参见《使用NDCG评估关键词推荐系统的相关性》),如果同时需要考虑商业变现, 那么可以考虑将能够获取到较多广告点击量的query排到比较靠前的位置
  4. 业务规则(marketing rule): 例如, ‘黄赌毒’结果必须过滤,或者带有某些特定字眼的关键词必须提到比较靠前的位置。。。。 这些规则更多是人为确定的(例如PM确定)
相关搜索query策略
数据
总的来说,搜索引擎要挖掘相关搜索结果,有以下几类数据可用:
  1. 网民搜索session数据(后续简称session数据): 就是网民在搜索引擎搜索框中连续输入的多个query。 这里有一个假定, 就是同一个session中的query都是有关系的(更进一步, 同一个session中离得近的query更相关; 在多个session中都出现的连续搜索更相关),该数据可以表示为多个query的序列
  2. 搜索点击数据: 即网民输入某个query后,在搜索引擎上点击的url,该数据可以简单表示为的pair
  3. 网页内容信息: url对应的网页内容
相关搜索的算法, 总的来说都是围绕上述数据, 其中 1,2类数据我们可以认为是网名的行为数据,而3可以认为是内容数据。 一般而言, 很多算法直接使用1,2类行为数据即能取得较好效果。 也有一些算法会结合网页内容信息提升效果。
候选词源触发方式
以下是几种典型的用于相关搜索的算法:
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.
使用Agglomerative Clustering方法, 首先使用query点击数据,对query和URL进行聚类, 取得相近query(具体算法介绍参见《搜索引擎点击日志聚类实现相关搜索》);得到query聚类后,在新query到来时,可以先判断网民query与哪个/些聚类最相近,然后该聚类下的词,都作为待推荐的关键词后续,进行后续排序过滤。 该方式优点是完全使用网民查询点击的行为数据,而没有使用到网民的内容, 或是query的内容; 此类思路和协同过滤类似。
图: query-点击关系
图: Agglomerative Clustering Init
图: Agglomerative Clustering Iterative
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.
该方式不仅使用了query-点击数据对query进行了聚类,同时还是用了query内容等信息。 也就是说, 网民行为和内容, 作为相似度度量的最终标准。
图: 结合查询行为及内容相似度度量
BM Fonseca, PB Golgher  2003 Using association rules to discover search engines related queries Web Congress, 2003  – ieeexplore.ieee.org
该方法中直接使用2项关联规则进行related-query的挖掘, 满足提前设定的支持度, 置信度阈值后后, 就作为推荐结果候选
Z Zhang, O Nasraoui   2006 Mining search engine query logs for query recommendation – Proceedings of the 15th international conference …, 2006 – dl.acm.org
该方法, 也是直接使用session数据对相关搜索结果进行挖掘总的思路也是根据session中共现概率较高的关键词作为高相关的query pair。 其中的一个创新, 是计算session之间的距离的时候, 使用了衰减方式。
论文中认为: session 中的pair, 离得越远, 相似度就越低, 例如, 假设session中每一步的相似度是d(d属于(0, 1)), 则两步的相似度为 d^2, 使用该方式进行衰减, 两步的相似度为  d + d^2  而不是2d  (当然, 实际中也可以选择, 两步的相似度, 就是d^2, 而不是d^2 + d)
图:session中随着间隔的增加,权重衰减
R Baeza-Yates, C Hurtado, M Mendoza 2005 Query recommendation using query logs in search engines Current Trends in Database 2005 – Springer
以该文为代表的方式, 还同时使用了搜索query和点击URL对应页面中的term之间的关系, 使用点击URL对应页面中出现的term作为query的表示,同事考虑了query的受欢迎程度作为相似度度量。 不过该方法因为挖掘代价较大,所以并未做该类实验, 毕竟, 简单也是一种美: )
其中q为代表特定query的向量, Pop(q,u)为搜索query q后点击URL u的PV, Tf(ti,u)为在在u对应的网页中, ti出现的词频。
排序过滤
产生了大量候选词后,一般会使用相关性模型直接过滤高度不相关候选词(参见《分类模型在关键词推荐系统中的应用》),之后进行排序。 排序时,一般按照优化目标进行排序。例如,假设我们一方面要考虑相关性(使用Q表示),同时要考虑商业变现收入(使用R表示), 则我们可以将优化目标表示为:
T=Q^(t) * R^(1-t), 其中t属于[0,1],通过调整t来控制在相关性和商业变现收入之间的权衡,该方式也可扩展为更多目标优化场景。
当然,对于现实中的相关搜索, 可以融合多种策略算法的数据以提高最终质量。
更多内容请参考:
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.
BM Fonseca, PB Golgher  2003 Using association rules to discover search engines related queries Web Congress, 2003  – ieeexplore.ieee.org
R Baeza-Yates, C Hurtado, M Mendoza 2005 Query recommendation using query logs in search engines Current Trends in Database 2005 – Springer
也可关注我的微博:  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

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

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

客户想要在百度上做搜索广告,就需要找到能够准确描述自己推广意图的关键词集合;但另一方面,目前百度凤巢系统拍卖词接近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

协同过滤中item-based与user-based选择依据

协同过滤是大家熟知的推荐算法。 总的来说协同过滤又可以分为以下两大类:
  1. Neighborhood-based:计算相似item 或user后进行推荐
  2. Model-based: 直接训练模型预测Rating
在Neighborhoold-based算法中,又细分为user-based CF(Collaborative Filtering)和item-based CF。合适选择使用userd-based CF,什么时候item-based CF更适用就会是一个需要权衡的问题。一般而言,可以以下几个标准进行选择:
  1. Accuracy:一般而言,少数置信的邻居的推荐要比很多的没有太多区分性的邻居更加准确,所以一般我们会选择数量较少的因素(item or user)作为based的算法。 例如, amazon中的商品的种类很多,但远没有注册的用户多,所以该场景使用item-based CF比较合适; 反过来,在百度关键词推荐系统中,商业客户(user)量级是100W左右,而待推荐的关键词(item)是10亿量级,此时使用user-based会是更明智的选择。
  2. Efficiency
  3. Stability:一般情况下倾向于使用变动频率和变动量较少的因素作为based的因素, 例如item变动较少, 则选择item-based, 否则选择user-based
  4. Justifablity(说服力):推荐系统中,推荐理由越白盒,用户越容易理解就越有说服力。所以从这方面考虑,item-based CF会更有说服力,例如显示‘因为你浏览了三星 Galaxy,所以给你推荐了HTC One’的理由会比‘和你相似的用户也喜欢XXX’更有说服力,因为推荐系统是不披露哪些用户和我详细,怎么证明和我相似的,而且这种说法显得比较含糊。
  5. Serendipity:多样性就是user-based的一大优势,和自己相似的用户,总能发现一些自己还没发现的新东西。 如果追求多样性, userd-based会是不错的选择。
当然上述原则都不是绝对的,而且在真实工业界推荐系统中, 两种方法一般都是混合着使用。例如百度关键词推荐系统中,就会分别使用item-based和user-based方法找到待推荐关键词候选后,再统一使用model进行后续ranking。
参考文献:
  1. RSs Handbook
  2. Evaluating Collaborative Filtering Recommender Systems, Jonathan L.Herlocker
也可关注我的微博:  weibo.com/dustinsea
也可直接访问: http://semocean.com

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

此处并不会列举每一种聚类(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

PageRank的经济学效用解释

google大名鼎鼎的pagerank算法大家都耳熟能详,基本的思路就是: 网页的重要性由指向该网页的链接,及指向网页的重要性决定。
那从经济学的角度, 背后隐藏的深层含义是什么呢?  说简单点,就是‘具有流动性的市场对商品价值的客观定价’。
我们先举一个简单而又经典的例子: 假设在原始社会中, 没有货币的概念, 所有的交换均为物物交换。 且生产社会中只有三个生产者:  农夫(使用F表示), 生产衣服的人(使用C表示)和生产工具的人(使用M表示)。 三个生产者生产出来的物品, 除一部分留己自用外, 其余均用于与其余二人进行交换。 交换关系如下:
图1: 三生产者的交换比例关系
F M C
F 1/2 1/3 1/2
M 1/4 1/3 1/4
C 1/4 1/3 1/4
图2:三生产者的交换关系邻接关系
以农民为例,除1/2生产的农作为自行享用外,剩余1/4与工具制造人换取他制造的1/3的工具,用剩下的1/4与衣服制造人交换他生产的1/2的衣服。 则根据列昂惕夫生产投入产出理论, 在自由市场下,交换的比例也即反映出该产品的内在价值。 以上图为例,假设:
一份农产品的内在价值为x1,一份生产出的工具内在价值为x2,一份衣服的为x3,则获得方程如下:
1/2 * x1 + 1/3 * x2 +  1/2 * x3 = x1
1/4 * x1 + 1/3 * x2 + 1/4 * x3 = x2
1/4 * x1 + 1/3 * x2 + 1/4 * x3 = x3
即可用解线性方程组的方法解除各内在价值。 该方程组背后的思想是: 任一物品的价值由自由市场中其他商品对其的认可程度决定。  后续会讲到, PageRank中迭代求稳定特征向量的过程, 其实就相当于是在自由市场中, 货物经过长时间流通后所反映出来的市场价值认可程度。
上述例子是在知道了邻接矩阵(转移关系)的情况下直接求解内在价值的过程。 如果我们对每种物品进行初始定价, 则能够计算在该转移矩阵的作用下,物品的价格在市场的作用下逐渐趋向于内在价格。
又例如:
教科书中一个非常经典的例子,是小镇上已婚女性和单身女性每年的数量问题:某小镇上,每年30%的已婚女性离婚,20%的单身女性结婚,镇上有8000已婚女2000单身女,假设小镇上女性总量为常数,分别求一年,二年后的女性数量?
求解方式为构建已婚,单身女性的转移矩阵A=[[0.7, 0.2],[0.3, 0.8]]   (此处使用python第三方库 numpy方式表示matrix)   x=[8000, 2000]为当前已婚,单身女的数量向量。 则一年后小镇上已婚,单身女性的数量向量x1 = A*x  两年后为 x2 = A* x1 = A*A * x    ;  如将x 写为已婚,单身女性的比例, 则该过程为Markov Process(Markov Process为随机过程)
PageRank
PR其实就是随机过程在网页ranking过程中的应用,该算法假设网页都是有价值的, 且价值是可以传递的,同时价值传递时也会衰减。 价值大的节点传递给指向的网页的价值也比较大。该算法中的思想其实是个人类学的问题: 和权威的人关系紧密的人, 一般也较有权威; 也经常说: 你的收入和你关系最近的5个人类似  啥的说法都比较类似。
PR的计算方式如下:
其中PR(n)为节点n的PR值,它由指向n的节点q集合的PR值及系数w决定, 1/|V| 为随机跳转概率避免闭环
所有节点的PR值计算方式如上, 其中C即为转移矩阵。
实际应用中, 一般是制定PR的迭代次数作为停止条件。
而PR值其实就可以直接看作是一种价值转移直到稳定状态。
参考文献:
  1. 经济学原理
  2. The PageRank Citation Ranking: Bringing Order to the Web
也可关注微博: weibo.com/dustinsea
或是直接访问: http://semocean.com