在上一篇《关键词推荐工具中的用户引导机制之二：suggestion架构》中， 我们提到， 在用户在搜索引擎，或是关键词推荐工具中输入搜索query片段的过程中， 我们可以提供suggestion来对用户搜索进行引导。 我们可以认为此时用户的搜索意图是不全面的。 而当用户已经输入完整query后， 用户的搜索用途已经在某种程度上明确了， 此时我们就可以使用相关搜索， 扩展出与用户输入搜索意图一致/类似的高质量query， 引导用户进行搜索， 让用户更快地获取信息， 得到所求。本文会具体介绍相关搜索类似的关键词推荐系统的策略架构，以及业界常用的相关搜索挖掘算法。
说简单一点， 相关搜索query， 其实也是一个关键词推荐。 和adwords中关键词工具， 或是百度关键词工具不同的地方， 是相关搜索对质量要求非常高，而给出的结果一般比较少， 即高准确， 低召回。
图： 百度相关搜索
图： Google相关搜索
以上分别为Baidu和Google的相关搜索结果， 不知道大家是否发现，Baidu相关搜索结果多样性强一些，同时商业价值也强一些（本文不介绍商业价值机制，后文介绍的优化目标中加入商业价值因素即可）
相关搜索策略架构
因为相关搜索就是一个典型的特定场景的关键词推荐系统， 所以相关搜索从策略架构上，会包含完整的关键词推荐的逻辑。 包括候选词源触发(query retrival)、 相关性过滤(filtering)、排序模型排序(ranking)， 以及根据规则进行调整（marketing rule）。 其中每个阶段都可以根据最终的优化目标（或者多目标）设计相应架构。
图：关键词推荐策略架构中的主要处理逻辑，包括query retrival, filtering, ranking, marketing rule几大逻辑
各组件功能
- 候选词源触发(query retrival)：其主要功能是通过各种offline数据挖掘，得到query（或是成份）之间的关系， 获取到候选的待推荐query，供后续逻辑进行处理。
- 相关性过滤（filtering）：根据应用场景，对不满足query之间相关性的候选词进行过滤，以减轻后续逻辑的性能负担。 相关性过滤的方法可参见《分类模型在关键词推荐系统中的应用》
- 排序(ranking)：根据应用场景的优化目标，对候选词进行排序。 例如， 如果要提升用户体验，那就直接将高相关性的候选词排在前边（衡量标准可参见《使用NDCG评估关键词推荐系统的相关性》），如果同时需要考虑商业变现， 那么可以考虑将能够获取到较多广告点击量的query排到比较靠前的位置
- 业务规则（marketing rule）： 例如， ‘黄赌毒’结果必须过滤，或者带有某些特定字眼的关键词必须提到比较靠前的位置。。。。 这些规则更多是人为确定的（例如PM确定）
相关搜索query策略
数据
总的来说，搜索引擎要挖掘相关搜索结果，有以下几类数据可用：
- 网民搜索session数据（后续简称session数据）： 就是网民在搜索引擎搜索框中连续输入的多个query。 这里有一个假定， 就是同一个session中的query都是有关系的（更进一步， 同一个session中离得近的query更相关； 在多个session中都出现的连续搜索更相关），该数据可以表示为多个query的序列
- 搜索点击数据： 即网民输入某个query后，在搜索引擎上点击的url，该数据可以简单表示为的pair
- 网页内容信息： 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
