搜索小二-漫谈个性化query推荐

我最初对推荐系统的了解来源于阅读开发了享誉业界的Amazon的推荐引擎的大牛 - Greg Linden（著名的 Item-based 推荐算法的提出者）的技术博客：[Geeking with Greg]（需要翻墙），如今这个博客是个性化推荐领域最有影响力的博客（没有之一），Amazon 每年从这个推荐引擎创收几十亿甚至百亿美刀也是后话，如果说Amazon的推荐引擎是世界上最好的，我相信没有人持反对意见。后起之秀[netflix]将推荐系统发言光大，2006年发起[netflixprize]推荐系统算法竞赛，声称如果有谁的算法能让现有的推荐引擎的准确率提升10%，将会奖励100万美元，[netflix的官方技术博客]有对这项赛事的仔细描述，还公布获奖者的名单和算法。

历史的车轮滚滚向前，国内的几家高科技公司也在推荐系统领域有所斩获，比如豆瓣（我也是豆瓣的资深粉丝之一）的推荐引擎就做得非常出色。如今，推荐无处不在，早已经不是新鲜事物，推荐系统和算法，无论是在工业界和学术界都被研究和讨论，究其原因，一方面是个体的差异，对事物的体验和需求的不同导致目前一刀切的互联网产品很难满足个性化的需求；另一方，大势所趋，要么引领整个潮流，要么被淹没到浪潮之中，成为过客。个性化的时代来临，你还在等什么！

聊完了八卦，进入正题。我们今天聊的主题是个性化query推荐。所谓query推荐，目前的主流搜索引擎大都提供两种产品形态，在用户输入完整query之前，搜索引擎会在搜索框中弹出一系列推荐的query，我们称之为下拉推荐；在用户输入完整query点击enter键之后，搜索引擎都会在搜索结果页的周围（一般是上方或者下方）会给出和输入query相关的query，我们称为相关推荐。淘宝目前的下拉推荐和相关推荐并没有做人群区分，无论你是屌丝男还是高富帅，无论你是男还是女还是人妖，都一视同仁，给出的结果都是一样。这些推荐query一般都经过两个步骤产生:

1、从query log中挖掘出大量的候选query。下拉推荐要求保持前缀相同（google对于某些query也会给出一些后缀匹配的结果），相关推荐要求候选query和输入query具备某种相关性。

2、依据某种法则给候选计算一个分数，最后选择出top 10个作为最终结果。

上面的描述滤过了大量的细节，因为这个不是这篇文章考虑的重点。问题的重点来了，假如要给淘宝的下拉推荐或者相关推荐加上个性化的元素，该怎么做呢？

凡是问Google. Google 的下拉推荐会将用户最近搜索的query保存（客户端或者服务器端都可以），当用户输入query的前缀，如果匹配上，会将这个搜索的query放在下拉推荐的前几个位置，并标上不同的颜色。除此之外，在下拉框的最右边，会贴心的放上删除按钮，如果用户对最近搜索的query不是很满意，可以直接删除之，以防干扰视听。个人觉得这个功能给用户带来的体验很好。我经常在Google上搜索论文或者某人的blog, 有时候论文下载之后忘记放到了什么地方，有时候blog忘记订阅, 想再次寻找的时候，只要你依稀记得论文title的几个关键词, 并且只要你曾经搜索过，Google会将历史结果推荐出来，这个时候，你是不是觉得很happy 呢？我们暂且称这个为下拉推荐的“历史query”功能。如果我们要实现它，该如何做呢？

先考虑最简单的方案。这个和算法没有半毛钱关系，只涉及到工程上的实现。基本想法是，在服务器端为每个用户保存最近一段时间内搜索最频繁的几个历史query，在用户输入完整query之前，如果输入的部分query是某个或者几个历史query的前缀，则将这几个历史query挑出来作为候选。很简单，是不是？这里面忽略了几个很重要的环节：

·淘宝的活跃用户有几千万，每个用户每天搜索的query少则几个，多则上千。如何存储这些user-query数据呢？

·你不可能把用户所有的历史query都存下来，你得有所取舍，存哪些query是最好的呢？所谓最好是，比如，那些符合用户最近的搜索意图的query可能会被保存下来？那么如何预测用户最近的搜索意图？

·是否要支持实时更新？(这个问题在这篇文章不会涉及）

问题一比较简单。假设用户ID用长整型保存，再假设我们存8000万用户，为每个用户存最近搜索最频繁的3（这个数字你可以自己定）个query，我们假设query的平均长度是4个汉字,采用GBK编码（实际的query长度可能比这个长，也可能比这个短，没有关系，这并不影响我们分析问题），可以估算共耗费内存：80M * (4 * 3 * 2 + 8) = 2560M = 2.56G. 如果我们用hash_map来存储，考虑到数据结构本身的内存开销，实际耗费内存可能在还要乘以2（也就是耗费的内存可能在2.56G到5.12G之间），可能更多。

当然，我前面是假设所有的内容都一次性加载到内存中，实际实现的时候，可以仅将热点数据加载到内存，其余数据仍然可以保存在磁盘上。也就是所谓的Cache, 除了cache miss带来的性能开销，其它还OK. 看来，我们迈出了坚实的第一步。

考虑我们上面提到的第二个问题，用户的历史query很多，如何挑选最优的N个query？这个问题是我们探讨的重点。前面其实已经包含了我们挑选query的策略，按照query被搜索的频度来挑选，我们选择top N个搜索次数最多的query作为候选。但这个策略是不是最优的呢？

我们可以更进一步，因为仅仅凭借当前用户的输入query，可能会忽略某些信息。我们可以考虑当前query之前用户的搜索query, 这些最近搜索的query可以当作用户搜索的上下文，作为我们挑选候选query的凭据。假设我们定义上下文的长度为里面包含的用户最近搜索query的个数，我们可以考虑各种长度的上下文来调整我们的挑选策略。为了分析问题的方便，我们先探讨上下文长度为1的情况，也就是在考虑用户当前搜索query的同时，我们同时考虑这个query之前的用户搜索的第一个query（有可能为空，没有关系，这个时候据没有上下文，比如用户搜索的第一个query）。有了上下文，那么我们如何挑选候选query呢？

到了这，不得不提 query session. 一个逻辑上的query session是一定时间间隔内用户连续做出的一系列动作的集合，当然包括用户搜索的一系列query。query session是搜索上下文最好的载体，当也存在一个问题：在一个query session内，用户可能发生topic 转移，这是很正常的现象，通常用户在一个query session中会完成多个搜索任务，这些任务会触发用户搜索不同的query，所以，我们在考虑上下文的时候，通常假设用户的搜索意图是一致的，也就是说搜索意图没有发生转移的情况。如果这个假设不成立，那么我们会对session进行切分，切分后的session 只表征一个搜索意图，这个session内的query通常是相关的。session切分本身是一个研究课题，这里不做深入探讨，有兴趣的同学可以阅读相关文献。

回到前面的讨论，现在我们假设有了用户搜索的上下文，以及用户当前的输入query,我们如何挑选出top N个最好的query推荐给用户呢？上面一节提到，上下文通常会考虑用户的query session, session内的query通常是相关的，那么一个简单的想法是，将用户的上下文和候选query映射到某个空间，然后我们计算每个初始选择的query和上下文的相似度，越相似的query，越能表征当前用户的搜索意图，那么分数越高，这个时候就排名越靠前。问题紧接着来了：

· 如何将上下文和候选query映射到同一个空间？

· 映射之后，如何计算它们的相似度？

我们其实可以把这个问题转化一下，在信息检索领域，一个query过来，我们要查询相关的document. query 和document之间的相似度的计算是将两者表示成一个高维度的向量，向量里面的每一维可以是一个词，一个短语，一个ngram, whatever. 每一维的权重，最常用的是TF*IDF. 我们可以将前面的问题转化成一个类似的问题，我们把context当作query，把候选query当作document, 那么这个问题其实就是一个普通得不能再不同的match问题。同样，我们可以把query和context表示成词的向量，那么相似度的计算沿用最简单的cosine similarity计算即可，假设我们用v(q), v(c)来表示query和context的向量，那么他们的相似度可以计算为：

sim(q, c) = / ||v(q)|| * ||v(c)||.

到目前为止，一切都很自然，但上面的方法中有一个核心的问题没有提到，那就是，这个向量怎么来? 换句话说，表征query和context的词如何生成？前面我们提到，如果上下文中只考虑一个query，那么上下文的向量表示就是这个query本身的向量表示，假设上下文包含t个query，比如， C=q(1),...,q(t) 表示这个上下文，V(q1), ..., V(qt)分别是这些query的向量，那么上下文的向量我们可以表示成这些向量的一个线性组合：

注意每个向量都赋予了一个权重，通常认为，距离当前query越近的query会赋予相对高一点的权重。还是回到原来那个问题，向量如何表示？要知道，在用户搜索的历史query当中，有重复query或者term的query是比较少的，假设我们把当前query和上下文的query切分，这样我们会得到一个term 集合，然后我们在这个集合上表征我们的向量，向量的值仍然可以沿用TFIDF, 但数据的稀疏性会导致我们的向量大部分都为0。那么如何解决数据稀疏的问题呢？

一个想法是利用query session构建推荐query树。这个想法是这样的，给定一个query（假设表示成A)，通常我们会从query session中挖掘出和这个A相关的其它query(假设其中一个query为B)（如果用到下拉推荐当中，我们可以加上前缀匹配这个约束），然后我们在找到和B相关的query（假设其中的一个query为C)....以此类推，这个过程，其实我们是在深度遍历一棵树，这棵树上的每个节点都是上一层上的节点的相关query。有了这个棵相关query树，我们可以这样来表示用户当前输入的query和上下文。我们将树上的每个query切分成词，然后广度遍历这棵树，直到停在树上某个层次，可以到了叶子节点退出，可以中途停止。我们现在来考虑query 的向量表示。给定一个q, 假设z是一个词，假设我们用v来表示q的向量，如果z不在树中，那么v[z]=0, 如果在树中，我们可以表示v[z]如下：

显然这是一个类TFIDF机制，但对于包含z的处在不同树的层次上的节点会赋予不同的权重。

有了向量表示，我们可以尽情的计算它们之间的相似度了。

到现在为止，我们谈的内容其实和推荐系统的主流算法之一，Item based 算法有点神似。我们换个角度来考虑这个问题，假设用户的搜索意图可以用一系列query（或者term)来表征，那么同一个搜索意图在不同人之间的表达通常会不同，但也能有迹可循。于是，基本想法是，假设大量用户的搜索遵循某种规律，那么当某个个体出现的时候，我们可以按照这个规律来推荐出合适的query。按照推荐系统的术语来说，就是协调过滤。

那么，我们如何做呢？在购物系统中，通常会构建一个User-Item矩阵，这个矩阵的每一行是这个用户的在过去一段时间内买过的物品，每一列代表某个物品被多少人买过，可以是0/1值（买过，或者没有买过），也可以是数量。我们也可以构建一个类似的User-Query矩阵，每一行是用户在过去一段时间内搜索的query，每一列是这个query被多少人搜索过多少次。有了这个矩阵，通常会进行一个SVD分解，SVD分解会将这个矩阵分成3个矩阵。SVD在这里的作用是，一方面是降维（类似PCA), 另一方，是将用户和query映射到一个更紧凑的空间，这个空间的每一维是矩阵的每个特征向量对应的特征值的开方，我们称为奇异值，因此，SVD分解又称为奇异值分解。每个奇异值其实代表了用户的某个特征，比如偏好，兴趣等，所以SVD从另外一个角度会将兴趣相同的用户聚类，这样我们在推荐query的时候，其实是先找到兴趣偏好类似的用户，然后用这些用户搜索的历史query作为推荐。

netflixprize 的推荐引擎的核心在06年以前都是基于SVD搭建，可见SVD在推荐系统中的重要程度，不仅如此，SVD无论在数值优化中，还是在数据挖掘中，都能占一席之地，Google已经开发了并行的SVD算法，这个可以算是对人类的一个重要贡献（参考吴军老师的 ‘数学之美’）。