背景
我们今天聊的主题是个性化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挑出来作为候选。很简单，是不是？这里面忽略了几个很重要的环节：
·淘宝的活跃用户有几千万，每个用户每天搜索的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 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作为推荐。
驭宝SEO培训第十八期与7月15-7月21正式开课，
参加培训报名联系企业qq：800066939
