组里经常招实习生， 在技术问题问得差不多的时候， 我经常会问他们一个问题：‘百度的相关搜索，你会如何设计实现？’   主要想看下实习生会有哪些思路，看看思路是否广，方法是否多， 没有啥方法的话， 我会提示下，看他是否能够一些思路。

其实各大搜索引擎的‘相关搜索‘ 虽然涉及到的细节会比较多， 包括如何权衡点击，用户体验，收入之间的关系等细节，主要的挖掘算法还是比较类似的。 从数据上来说，基本上围绕着网民搜索的session数据，网民点击数据，涉及到商业变现的话，可能会引入广告主的信息。

百度的相关搜索的实现这里就不介绍了（可能涉及泄密），这里主要介绍之前看过的一篇论文： Agglomerative clustering of a search engine query log    使用搜索点击日志进行query聚类，并使用层次聚类结果进行相关搜索结果挖掘与推荐。希望对大家有所帮助。

算法中的创新点， 是在对query进行聚类的同时， 也就将URL进行了聚类。聚类的过程没有使用query的内容信息， 而是直接使用了网民的行为信息（搜索，点击行为）。这种思路和协同过滤类似， 就是不考虑推荐item的内容，而是使用用户的行为数据直接进行推荐。

算法首先使用点击日志， 格式为<query, url>的pair，构建双边图，左边为query， 右边为url，如果搜索query后点击了url则链接该query和该url代表的节点建立一条边。该二分图的建立方式如下：

二分图示例如下，左边为query，右边为被点击url，边为搜索相关query后点击对应的url：

 

定义N(x)为x的邻居点， 则可以定义query点x, y 的相似度如下：

 

该相似度介于[0，1]之间，即， 当x,y 均为query时， 使用与x，y均相邻的节点比例度量他们之间的相似度； 相对地， 当x,y均为url时，使用共同搜索query定义其相似度。

之后的工作便是迭代进行聚类，每次使用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