论文部分内容阅读
在信息检索系统中由于查询过短和存在歧义等原因，单纯依靠用户自己构造查询往往不能准确地表达搜索意图，导致搜索效果不佳，查询推荐是解决这一问题的关键技术之一。查询推荐技术的最直接应用就是搜索引擎中提供的“相关搜索”，除此之外推荐技术还被广泛应用在计算广告和电子商务等领域中，具有很高的研究价值。本文研究如何利用Web搜索日志这一资源来解决目前查询推荐的一些问题。
查询推荐的核心问题在于如何度量两个查询之间的相似度。本文通过分析相关工作发现前人方法通常利用各种特征(公有子串、共同点击次数等)直接对两个查询的相似度建模，当特征不足时，有些相似度难以计算出来，导致结果不准确(甚至无结果)。针对此问题，本文先根据查询间的转移关系构造查询关系图，其中节点表示查询，边表示查询的某种直接联系，然后引入一种基于图结构的相似度计算方法—SimRank来挖掘查询间更多的隐含关系。SimRank算法能够利用邻接节点相似信息来迭代计算图节点间的相似度，这样难以直接计算相似度的查询经过图中其他查询的间接联结而具有一定相似性。
然而，原始的SimRank算法应用在查询推荐中存在缺陷：所有查询关系被等同看待，没有考虑到关系强弱，导致结果不准确；不能计算直接相邻节点的相似度；时间复杂度和空间复杂度偏高，不适合大规模应用。
针对原始SimRank算法的不足，本文提出了一种改进的SimRank算法WeightedSimRank。与原始SimRank算法相比，它在保持收敛性的同时，具有如下优点：
1.增加边权重信息，使得相似度计算结果更为准确；
2.增设查询初始相似度为相连边权重，避免相邻节点无法计算问题。
针对原始SimRank和Weighted SimRank在大规模数据环境下的计算复杂度偏高问题，我们分别从四方面进行优化：
1.采用图搜索算法减少查询对数目；
2.应用动态规划思想保存中间结果减少重复计算；
3.变换公式减少无效计算；
4.采用剪枝策略提高速度并过滤噪声。
在大规模的真实Web搜索日志语料上，我们实现了几种常见的查询推荐方法并将它们进行了对比。实验结果表明，本文提出的Weighted SimRank方法优于其他的方法，其MAP指标接近0.9。
此外，我们利用包含约107次查询的真实搜索日志实现了一个基于Weighted SimRank算法的查询推荐原型系统，该系统在实时推荐中能够迅速响应，且能挖掘出许多语义相关查询。