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

列了一些之前设计开发百度关键词搜索推荐引擎时, 参考过的论文, 书籍, 以及调研过的推荐系统相关的工具;同时给出参加过及未参加过的业界推荐引擎应用交流资料(有我网盘的链接), 材料组织方式参考了厂里部分同学的整理。
因为推荐引擎不能算是一个独立学科,它与机器学习,数据挖掘有天然不可分的关系,所以同时列了一些这方面有用的工具及书籍,希望能对大家有所帮助。
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

如何与理智的对手沟通谈判

很早前读了《谈判力》这本书,当时觉得非常棒,基本的原则,就是两点:
  1. 所有的谈判, 都要以人为本
  2. 所有的谈判, 都以客观的标准进行
咋一看这两个点是矛盾的,如果所有谈判都基于客观标准进行, 那是不是还需要考虑人的感受?    这就会涉及到刚入职的同学都会碰到的一个概念‘对事不对人’,是什么概念呢? 从字面的意义来看, 就是做事的时候, 主要看怎么样来看这个事,而不是要考虑太多个人感情和关系, 而且这句话最常用的场景就是追究责任的时候: 如果一个人做错了事, 该追究责任就追究, 甚至该处罚就处罚。但工作几年后才发现, 绝对不可能做到对事不对人, 每个人都是一个自由意志的独立体,每个人都有自己做事的方式, 每个人提出建议和接受建议的方式都不一样。
第一次好好反思这个道理的时候,是前两年,号称百度7剑客之一的崔珊珊, 在离开百度后, 被我们部门老大请回来给一些经理人的一次讲座中,提到这个观点。 当时有一种豁然省悟的感觉。所以做事的时候,例如谈判的时候, 都需要考虑别人的感受, 也就是上文提到的以人为本; 而稳重提到的以客观标准进行谈判, 更多是提醒不要有预设的立场区分, 不要对谈判对手有偏见,而是摆事实,讲道理(同时考虑对方的感受)
当然,《谈判力》中介绍的准则,更适用于和自己同一战线, 且比较理智的朋友。如果要应对其他类型的谈判对手,那么罗杰.道森的《优势谈判》会更适合。
以下就具体说下读这本书的感受:
把人和事分开
这就是一个艺术, 就是要在多大程度上将人和事分开。很多时候,在谈判的过程中, 利益不是绝对化的,需要考虑谈判的实质利益和关系利益。 我们可以将实质利益看成是这次谈判所要考虑的利益,而关系利益则是后续是否还能跟对方做生意,保持长期的良好关系。 甚至有些谈判会需要为了与客户保持良好的长期合作关系而牺牲短期的实质利益。所以谈判的过程中要权衡对方个体的感受,权衡实质利益和关系利益。
当然, 很多时候关系利益,需要再获取实质利益前很长时间就开始搭理。例如在一篇文章中提到华为的销售非常厉害,对于潜在的客户,一开始就习性搭理关系利益,甚至一些潜在客户的饭局旅游都包了, 之后,成单就容易多了, 就有了实质利益。 这就是实质利益和关系利益的全很。
另外,在谈判的过程中, 说法的方式也非常重要,如果一开始就直接抛出自己的观点想让对方接受, 经常会适得其反。比较好的方式, 是先换位思考, 从对方的角度出发, 理解对方的开发, 体会对方为什么会有这样的看法, 之后在发现对方的看法中的一些问题, 之后在自然地提出问题,消除分歧。 即以一种: 感知->感受->发现 的方式去谈判
例如: 工作中, RD的思维和PM的思维非常不同, 对于一个功能的实现, RD评估的工作量和PM预估的工作量是不一样的。以前为一些项目的工作排期, RD和PM经常吵得不可开交: PM觉得这些功能点比较重要,而且实现应该不复杂, RD则认为PM希望的排期太紧。。。。 后来发现, 最好的方式, 是从PM的角度去看, 去告诉PM为什么他认为实现这些功能,周期比较短(感知),之后表示理解PM这样的看法(感受), 然后再从RD的角度,摆事实,告诉PM实现这些功能,需要做哪些工作,每一步工作需要多少时间,这些工作的总和又是多长,所以不能满足PM的要求,或者至少要多长时间(发现)。 这样PM就更容易理解分歧所在,重新评估时间, 或是删减不重要的功能点。
着眼于利益而非立场
一般情况下,决定最终谈判结论的,应该是利益而不是立场, 所以一开始需要了解己方的利益,同时也要了解对方的利益。明确双方各自的利益后。比较重要的一点, 就是要让对方觉得我们是理解他们的, 这样能够获取对方的信任, 在获取对方信任后, 办事就方便多了, 因为从认知心理学的角度来看: 一旦一个人信任了你, 你说的所有的话, 他都相信。 之前看过美剧《律师风云》,其中在一场棘手的官司前,Alan向Denny请教如何才能让陪审团相信自己的论点, Denny告诉Alan,你就对着陪审团不停说事实,知道陪审团相信你, 之后你再说出论点。。。。。 这样陪审团就相信你的观点了。
为共同利益创造选择方案
一般说来, 善于创造解决方案,是谈判者最大的财富;比较经典的就是两小孩分橘子的故事, 当然现实生活中很少会出现这种两全其美的场景。 当没有办法找到两全其美的解决方案时, 也可以看下是否之前有解决类似问题的先例可供借鉴(在任何行业,场合都实用); 或者如果有实质问题不能达成一致时, 可以考虑先将解决问题的流程机制定下来。
当然, 看完这本书后, 虽然收货颇多, 但觉得其中说道的一些思路, 还是比较适用于工作中比较理智的谈判对手, 对于一些胡搅蛮缠, 或是会出一些阴招的对手, 这些方法可能就会失效了, 就可以使用《优势谈判》中的一些技巧, 毕竟罗杰.道森跟各种人都打交道, 所以应对的方法会多些。
也可关注微博: 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

关键词推荐工具中的用户引导机制之二:suggestion架构

在《关键词推荐工具中的用户引导机制之一》 我们分析了用户用到机制对搜索引擎/关键词工具的重要性,同时也提到按照用户在搜索引擎/或者关键词工具上交互的阶段,可以按交互前,交互中和交互后为用户分别提供种子query,suggestion和相关搜索词对用户进行引导。 种子query是比较经典的推荐问题, 对于‘相关搜索’,后续会有博文专门介绍, 该文以下内容主要介绍如何构造高效的suggestion服务。包括架构及内部检索逻辑。
suggestion到底有多大作用呢, 在很多搜索引擎中, 一方面,从自然搜索结果的角度,suggestion能够引导客户将输入表现的更利于搜索引擎理解用户的意图,得到更优质的搜索结果; 另一方面, 从商业变现的角度看, 大的suggestion策略的上线, 往往能够带来搜索引擎几个点cpm的提升, 这可是非常了不起的贡献。 所以对于搜索引擎, 和关键词推荐工具这样的基于搜索的系统, suggestion的作用就至关重要。
图: 百度suggestion效果
图:关键词推荐系统suggestion
基本概念
要了解suggestion的设计细节,需要先定义以下名词:
  • Query片段:特指query的前缀,例如用户输入的query为“鲜花快递”,其全部query片段为‘鲜’,‘鲜花’,‘鲜花快’,‘鲜花快递’。
  • 拼音片段:本文中特指query片段对应的拼音片段,例如用户输入query为‘鲜花’,则全部拼音片段为‘x’,‘xi’,‘xia’,‘xian’,‘xianh’,‘xianhu’,‘xianhua’。
  • 候选query:指挖掘出的候选种子query。
  • wcode:建立suggestion 索引时,为每个候选query的编号,该编号值表示对应字面在数组结构中的下标位置,为无符号整型。
  • 个性化suggestion:根据客户帐户信息进行推荐的query suggestion。
  • 通用suggestion:与个性化suggesion对应,所有客户都适用的query suggestion。
解决方案的权衡
索引方式
suggestion可以做得比较简单, 也可以比较复杂,例如在搜索引擎搜索框中, 可以输入汉字, 拼音, 或者输入几个汉字后,又将输入法切换为拼音进行输入, 或是正好反过来。 这样对于suggestion,就需要考虑是只对汉字输入query提供suggestion结果, 还是需要对混合输入(拼音+汉字)query提供结果。 不同的功能会导致实现不一样。
 
图:全拼音模式suggestion
图:汉字+拼音混合模式suggestion
经过统计,候选query平均长度为13.9字节(约7汉字),其对应的拼音平均22.1个字母。如果仅对汉字建立索引,则可假设每个候选query对应7个query片段索引片段,而如果要对汉字+拼音建立索引,则每个候选query需要对应约30个索引片段(7+22=29)。但建立拼音片段能够支持用户拼音输入,或是中英文混合的情况,所以要达到较好的用户体验, 最好是实现: 索引结构支持拼音+汉字方式
性能
作为引导机制,suggestion的性能必须足够快, 应该做到迅雷不及掩耳的速度,否则在用户灵活的手指配上高效的输入法下出现任何一顿一顿的感觉, 都会异常影响用户体验, 所以在内存允许的情况下, 所有数据常驻单机内存,是比较理想的情况, 如果单机内存存放不下, 那么可能的选择是使用资源定位系统,将数据进行水平拆分(最简单的方式, 按照query签名作为key,然后取模)
P.S. 对于如何对数据进行扩展, 推荐大家仔细揣摩《ebay网站架构原则》, 每一条原则都值得细心思考体会。
图: 水平拆分,例如按照key签名取模
使用该方式, 请求可轻松达到1w+/s
结果merge及rank
suggestion返回结果由个性化suggestion(针对每个用户单独挖掘)与通用suggestion结果组成,个性化结果在前,通用结果在后的方式,当个性化结果不足时由通用结果补足。
其中,不管个性化结果,还是通用结果,由两部分组成:原始query片段索引结果与拼音query片段索引结果。对于二者的merge方式存在两种思路:
  • 原始query片段索引结果与拼音query片段索引结果merge,按权重从高到低排序,返回前N个结果。
  • 优先返回原始query片段索引结果,数量不足时由高权重的拼音query片段索引结果补充。
从用户体验与效率考虑,原始query片段索引结果与拼音query片段索引结果的merge方式采用思路2。
思路2还有一个问题需要考虑,原始query片段索引结果数量不足时,进行字音转换成拼音串后,存在拼音串片段检索结果与用户输入query的汉字串前缀不一致的情况。例如:query为“鲜花”,转换成拼音串“xianhua”后的检索结果可能有“鲜花”,“仙花”,“闲话”,这时候的检索结果可能包含“仙花”,“闲话”同音但不同字的suggestion结果。从检索逻辑复杂性、效率、数量量考虑,针对纯汉字串片段索引结果数量不足时,不进行字音转换后的拼音片段索引检索。
针对非纯汉字串,原始query片段索引结果数量不足时,通过字音转换成拼音串片段进行检索。在检索过程中,考虑最大汉字前缀匹配的方式。例如:query为“鲜hua”,转换成拼音串“xianhua”后的检索结果可能有“鲜花”,“仙花”,“闲话”。在此例子中,会使用汉字前缀“鲜”去与候选query进行匹配,最终得到候选query“鲜花”。
使用上述方式, 可以在保证结果个性化(个性化结果需要在离线进行挖掘)的同时,保持suggestion应有的高效。
内存数据结构
在决定了使用全内存的存储方式后, 就需要考虑内部数据结构的设计了。 要想让效率最高,最快的方式就是直接使用hash进行query片段签名查找。
图: hash方式进行倒排查找。
索引中主要包括以下结构:
片段索引字典:存储片段签名到片段推荐词倒排的偏移地址。使用bsl::hashmap存储
片段至推荐词倒排索引:存储每个片段到候选关键词wcode的倒排索引。使用hashmap存储。通用拉链与个性化拉链倒排拉链合并存储,区别在于个性化拉链不仅包含关键词wcode,还包含关键词的个性化weight。两种结构根据标志位flag进行区分。为了提高在线服务时,合并字面返回的效率,针对每个索引的拉链会有序(weight从大到小)存储。
字面队列:存储具体wcode字面与字面权重,使用bsl::deque存储,片段至推荐词倒排索引中的wcode值即为该队列索引下标。
在线检索流程
当用户在搜索框进行suggestion请求时,会经过对片段进行归一化,查找汉字索引片段,查找拼音片段及merge结果阶段,结果merge及rank主要的原则是汉字片段结果排在拼音结果前, 各类结果内部按照线下挖掘的权值进行rank。 线下挖掘在业界及学术界的方法参见后续博文。 附上一个流程图, 类似的画法是在工作中逐渐形成的习惯, 其中将function和data structure单独分开表示, 虚线表示数据依赖, 实现表示处理逻辑依赖。  该方式自己觉得比较清晰, 特别是对照着文档写代码的过程中:)
更多内容可参见:
《eBay网站的架构原则》 : 网上都有,每一条扩展原则都值得细心揣摩及体会,各大搜索引擎大数据的支持原则异曲同工
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com