基于二分图的查询推荐算法

摘要

当前，互联网已经成为全世界最大的一个知识库，蕴含着海量的信息，人们可以获取的网络信息与日俱增。用户在面对大规模的网络信息时，却往往茫然于如何更快更准确地找到所需要的信息。搜索引擎可以帮助人们从海量数据中获取信息，已经成为用户获取网络信息的最主要甚至必不可少的工具之一。但目前的搜索引擎与用户的交互方式仍然是主要通过用户根据信息需求自主输入查询关键词进行检索，搜索引擎返回查询结果。由于输入的查询词一般较为简短，并且查询词自身存在歧义性和多义性，搜索引擎并不能准确理解用户真实的搜索意图。基于此种背景下，查询推荐技术如今已经被搜索引擎普遍采用，帮助搜索引擎更准确地了解用户真实的查询意图以及帮助用户构造更加完善的查询。
　　本文主要研究了一种基于二分图的查询推荐算法。采用搜狗查询日志作为实验数据集，对该数据集进行分析与预处理之后，抽取31万条用户历史点击数据作为实验用数据。将用户点击URL在搜索引擎返回结果列表中的排序号和用户点击该URL的顺序号考虑到二分图连接边的权重计算公式中，利用TF-IDF思想计算边的权重，得到Query-URL加权二分图。利用用户点击的URL集合构造向量来表示对应的查询，然后使用余弦相似度方法计算任意两个不同查询间的相似度，最后构建一个描述查询问相关度的查询关系网络图。对一个输入查询推荐N个候选查询的过程是:首先在查询关系网络图上找到该输入查询所在节点的邻居节点构成初始候选查询集合H。若集合H中查询的数目不小于N，直接选取前N个与输入查询相关度得分较高的候选查询进行推荐;若集合H中查询的数目小于N，则将和输入查询节点间接连接的h-hop范围内节点也加入集合H中，利用k-means算法对集合H中的查询进行聚类，最后对包含输入查询的簇进行排序，推荐前N个与输入查询相关度得分较高的候选查询。实验结果表明，本文研究的查询推荐算法具有良好的推荐效果和一定的应用价值。

目录

声明

摘要

第1章 绪论

1．1 研究的背景与意义

1．2 本文的组织结构

第2章 查询推荐国内外研究现状

2．1 引言

2．2 国内外研究现状

2．2．1 基于文档的方法

2．2．2 基于日志的方法

2．3 本文的主要研究工作

2．4 本章小结

第3章 查询日志的分析与预处理

3．1 引言

3．2 搜索引擎原理概述

3．3 搜狗查询日志的分析

3．3．1 日志的数据格式

3．3．2 对查询关键字的分析

3．3．3 对点击URL与点击序号的分析

3．3．4 对查询和点击URL长度的分析

3．4 数据的预处理

3．5 本章小结

第4章 基于二分图的查询推荐算法

4．1 引言

4．2 基于二分图的查询推荐

4．2．1 算法步骤概览

4．2．2 构造Query-URL加权二分图

4．2．3 查询问的相似度计算

4．2．4 构造查询关系网络

4．2．5 查询推荐

4．3 本章小结

第5章 实验与分析

5．1 前言

5．2 实验运行环境

5．3 数据挖掘工具——WEKA

5．4 实验结果与分析

5．4．1 数据稀疏性对推荐效果的影响

5．4．2 阈值对推荐效果的影响

5．4．3 k-means聚类查询

5．5 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢