【毕业学位论文】（Word原稿）基于用户反馈的个性化检索技术研究-网络与分布式系统博士论文

博士研究生学位论文 题目： 基基于用户反馈的个性化 检索技术研究 姓 名： 学 号： 院 系： 信息科学技术学院 专 业： 计算机系统结构 研究方向： 网络与分布式系统 导师姓名： 李晓明教授 二零 年 五 月 in of ( i 2007 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 i 摘 要 随着互联网的飞速发展，搜索引擎日渐成为人们必不可少的一项工具。然而一方面由于搜索引擎的用户大多是普通用户，很难将自己复杂的检索目的组织成搜索引擎所需要的简单的查询词表示；因此为用户提供更多的交互式接口，提供启发式检索手段就显得特别重要。另一方面在通用搜索引擎中，当不同的用户输入同一个检索词时，搜索引擎将 不做区分的返回同样的检索结果。然而实践证明，用户的检索目的是多种多样的。即使是同样的检索词，不同用户所期待的检索结果也是各不相同的。此时需要一些更加贴近用户的手段来改变这种检索方式，使得用户能够得到真正自己关心的信息。这也就是“个性化检索”所试图解决的问题。 个性化检索系统是指那些针对不同用户背景返回不同检索结果的信息检索系统。在这些系统中，文档的相关性是基于不同用户的背景和兴趣而单独计算的。而用户的兴趣和背景通常是通过显式或隐式的用户反馈来获得。通过对基于用户反馈的个性化检索技术的深入研究和探讨，本文得到 了如下研究成果和结论： (1) 一种无须人工干预的、用于衡量搜索引擎排序结果质量的方法和指标 of a 该指标能够用于衡量一个文档排序结果的质量；在实际的检索过程中，该指标不需人工干预即可计算得到，而以往的指标都需要有人工标注的结果集才可计算。实验结果表明了 标与 成正比，也就是说 标确实反映了一个排序结果的真实质量。 (2) 一种基于 标的个性化重排序算法。在有了 标的基础上，就可以通过当前排序结果的质量来衡量用户不同反馈文档的相关度高低，这正是 权 排序算法的思想。通过这种方法，相关度较高的反馈文档将对重排序过程起着更重要的作用，从而有效的改进了个性化排序的结果质量。 (3) 一种 利用分类辅助的 摘要比较算法 摘要比较算法是个性化重排序算法过程中必 不可少的一个子模块。 法的主要思想是 根据 搜索引擎返回 摘要的特点，利用分类技术来扩展短摘要的信息，以改进摘要比较算法。 该方法有效的克服了摘要文本短，内容少，无法直接比较的特点；从而改进了摘要比较的结果，进而提高了排序算法的质量。最终的 实验结果验证了该方法的有效性。 (4) 一种无损的基于聚类的层次 类算法。 法是一种经典的分类算法，然而其在处理大规模训练文档时效率上存在缺陷。本文利用层次聚类算法对训练文档进行有效的组织，实现了在提高分类效率的同时，分类质量不下降。 (5) 在深入研究并探讨了训练数据集对分类结果的影响之后，本文提出了一种稳定的分类评测指标 评测指标具有如下优点：（ a） 在不同的训练数据集上， 1 表现较稳定；（ b） 使用新的评测指标，不同的研究工作在不同训练数据集上的性能可以直接 进行比较；（ c） 在给定一个分类器在某个训练数据集上的 1 值时，可以推导得到该分类器在另一个训练数据集上的分类结果（即真实的分类精度、召回率以及 ）。 (6) 一 个 个 性 化 检 索 系 统 原 型 。它是一种基于显式用户反馈的个性化检索系统，该系统通过一个客户端来完成用户信息的搜集以及检索结果的重排序工作。用这种方式可以对不同的用户产生不同的排序效果，满足用户不同的检索目的，从而达到个性化检索的目的。 关键词 ：搜索引擎，信息检索，个性化， 相关反馈，分类 do a in to s a do do a in It is an to by of as In is to by 1) A of a is to of a R be of a R is in to CG R be to of a 2) of is to of is In an in of is of is 3) An to A is a in as is to of by CG of 4) An is in a to a of do in to to of 0 as NN ) A of is to of of on on of an on as on be of 6) A is to v of in is a to 目 录 第 1 章 引言 . 1 究工作的背景和意义 . 1 户反馈技术的 线装概述 . 2 何获得用户反馈信息 . 4 何使用用户反馈信息 . 9 何评价反馈技术 . 14 文的主要工作 . 18 文的主要研究内容 . 18 文的创新之处 . 20 文的组织结构 . 21 第 2 章 对重排序算法的研究 . 22 绍 . 22 关工作 . 24 一个排序结果质量的评估 . 25 量一个排序质量的现有指标 . 25 个特征以及 标 . 26 于新指标 实验 . 30 用 标改进的重排序算法及实验结果 . 34 章小结 . 36 第 3 章 利用分类改进的摘要比较算法 . 37 言 . 37 用分类技术改进的摘要比较算法 . 37 言 . 37 关工作 . 39 要比较算法 . 40 验设置和实验结果 . 44 结 . 47 分类算法效率的改进 . 47 言 . 47 关工作 . 49 于聚类的无损层次 类算法 . 49 验结果和算法分析 . 53 结 . 55 章小结 . 55 第 4 章 对中文分类评测方法的研究 . 57 言 . 57 关研究 . 59 个因素 . 60 素 1 训练集中的文档比例 . 60 素 2：类半径 . 62 素 3：类间距 . 64 评测指标以及实验 . 66 评测指标 . 66 验 1:同一个分类器在不同数据集上的表现 . 67 验 2:12 个不同分类器在 2 个不同数据集上的表现 . 68 评测指标的优点 . 69 章小结 . 70 第 5 章 一个应用实例及应用前景 . 72 性化检索技术应用现状 . 72 个应用实例 . 74 他应用场景及实例 . 76 户端 服务器 . 76 反馈 显式用户反馈 . 77 用搜索引擎 个性化搜索引擎 . 78 关工作及系统 . 78 章小结 . 79 第 6 章 总结和展望 . 81 文的总结 . 81 一步的研究工作 . 83 参考文献 . 85 博士期间录用和提交的论文 . 93 博士期间的主要科研项目与所获奖励 . 94 致谢 . 96 图示 图 1拟评测 . 18 图 2果序列的特征 . 29 图 2询样例 . 31 图 2计相关文档个数 . 32 图 2征 2：半径 . 33 图 2征 3：可能的相关文档比例 . 33 图 2R 指标与 的关系 . 34 图 2排序算法 流程 . 34 图 2. 36 图 3要实例 A . 39 图 3要实例 B . 39 图 3要实例 C . 39 图 3网搜索引擎返回摘要 . 41 图 3文网页分类器的工作流程 . 43 图 3要比较算法 . 46 图 3 关系图 . 47 图 3个反例 . 50 图 3定规则说明 . 51 图 3例：二维空间 . 54 图 42 个不同分类器在 2 个不同数据集上的宏平均精度 . 59 图 4档比例对分类结果的影响 . 62 图 4素 2：类半径的含义 . 63 图 4半径对分类结果的影响 . 64 图 4素 3：类间距的含义 . 65 图 4间距对分类结果的影响 . 65 图 . 68 图 5性化检索系统 . 73 图 5于用户反馈的个性化检索原型 . 75 x 图 5使用过程 . 76 图 5统说明 . 78 表格 表 1种用户行为的分类 . 6 表 3本集中类别及实例数量的分布情况 . 42 表 3文网页分类器 . 43 表 3询集合说明 . 45 表 3次 法效 率 . 54 表 3法效率 . 54 表 4息检索系统的评价标准 . 57 表 . 67 表 4据集 . 68 表 4据集 . 69 表 42 个不同的分类器在 2 个数据集 上性能评价 . 69 表 5性化检索系统的划分 . 73 第 1 章 引言 1 第 1章 引言 究工作的背景和意义 随着 模的迅速增长和内容的不断丰富，用户越发的需要搜索引擎这一信息服务形式以帮助 用户 快速、准确的在信息的海洋中找到自己需要的内容。 一个典型的使用场景是：用户将自己的检索目的组织成若干个查询词作为输入送给搜索引擎；搜索引擎根据查询词 进行检索，将检索结果返回给用户；用户浏览这些结果并点击查看自己想要的结果页面。然而一个突出的问题是：一个查询结果集中往往包含了成千上万参差不齐、内容各异的结果。这些结果有些是符合用户检索目的的，但是大部分都是不相关文档，也就是说查询结果集的精度低。从 年的评测结果中也说明了通用搜索引擎的这一问题，而“查询词的内容含糊”是导致这种情况的主要原因之一。 由于检索目的不明确或是对检索环境的不熟悉 et 1998等因素，许多事实表明用户无法将自己的检索意图组织成高质量的查询词。 经验丰富的用户，能够构造出“好”的查询词；所谓“好”的查询词是指查询中包含大量区分度高的词（即在少量文档中大量出现的词）。但是大多数用户并不能清楚的描述他的需求，最终得到的检索结果也往往难以令人满意。 因此搜索引擎需要一些额外的技术来辅助挖掘用户的查询意图，改进检索结果。 另一方面，在通用搜索引擎中，当不同的用户输入同一个检索词时，搜索引擎将不做区分的返回同样的检索结果。然而实践证明，用户的检索目的是多种多样的。即使是同样的检索词，不同用户所期 待的检索结果也是各不相同的。此时需要一些更加贴近用户的手段来改变这种检索方式，使得用户能够得到真正自己关心的信息。这也就是“个性化检索”所试图解决的问题。 相关反馈技术（ 在个性化检索方面最重要的方法之一（ 传统的相关反馈技术主要是用于查询扩展，然而近些年相关反馈技术已经广泛的应用在了各种个性化检索系统中。这一点将会在后面的章节中说明） 。经典的信息检索模型通常由 4个要素组成 ),(,ji 中： （ 1） D 是对一个大文档集合的逻辑表示； （ 2） Q 是对用户信息需求的逻辑表示； （ 3） 第 1 章 引言 2 （ 4） R(qi,一个排序算法。对任意一个用户信息需求 （即用户检索词），该算法计算得到每个文档 的相关度权值 983。 而相关反馈技术最主要的作用是提供一个新的排序算法 ),(，在增加了一个已知条件 用户的反馈信息集合）的情况下，重新计算对于查询 ,文档 相关度权值；从而改变原来的排序结果，进而改进检索质量。需要注意的是，对于d ， （即 在一个相关反馈系统中，实际的操作流程如下： 用户对检索出的文档显式或隐式的进行相关性判定，系统根据这些判定生成新的查询，对检索结果进行重排序。这一过程可以不断的迭代进行，直到用户找到满意的相关文档集合。许多实验结果都证明了这一方法能够有效的改进查询结果的质量，这种改进主要得益于查询扩展以及对查询词权重的重新计算。 根据所记录的用户反馈历史长短，相关反馈技术可以分为长期及短期两种：长期（ 关反馈即长期记录用户 的行为，建立并维护用户模型（ 根据用户模型对用户的行为进行预测；短期（ 关反馈只处理一个会话（ 的用户行为（通常指一次信息检索查询中对查询结果集的优化），因此也就不涉及用户长期历史以及用户模型的变迁维护。本文中主要讨论的是短期用户反馈所使用的各种相关技术。 相关反馈相对于其他查询处理方法而言，具有如下优点： （ 1）用户只需对文档做出相关性判断，而不需要了解查询处理的技术细节； （ 2）用户反馈技术将整个检索过程分割成 3 个用户容易理解的部分：提交查询，进 行相关性判断，对查询结果的重排序； （ 3）它提供了一种可控制的方法来突出某些查询词或是削弱某些查询词。 由此可见，相关反馈技术是理解用户检索意图、实现个性化排序、改进搜索引擎排序结果，提高用户对搜索引擎结果满意度的重要工具。因此本文将对基于用户反馈的个性化检索技术 这一具有重要理论意义和广阔应用前景的课题进行研究和探索。 户反馈技术的现状概述 第 1 章 引言 3 传统的用户相关反馈技术主要包括 2 个方面的研究内容：查询扩展（ 及权值调整（ 随着技术的进步，相关 反馈的研究内容逐渐发生了变化。目前的相关反馈技术主要可以划分为以下 3 个方面的研究工作：如何获得用户反馈信息（即上文所提到的 ；如何使用用户反馈信息来改进检索系统的质量（即如何构造新的排序算法),( ） ；如何评价用户反馈技术。 如何获得用户反馈信息？在传统相关反馈技术中，主要是通过用户显式的对文档进行相关性标记来获得。要求用户显式的相关反馈会导致用户不堪负荷，这也是传统的相关反馈技术不能广泛应用的最大限制。目前，有许多新的反馈 获得方法，隐反馈（ 伪反馈（ 其中最突出的两种技术。隐反馈技术是指从用户的行为（例如点击、浏览、打印 .1997; Le et 2001; 004中，通过种种数据挖掘技术来发现用户隐含的兴趣及爱好，并将这些隐含的信息作为反馈信息来辅助检索。伪反馈技术 et 2005是指将检索结果中的若干个文档假设为“相关文档”作为反馈信息来辅助检索。 如何使用用户反馈信息来改进检索系统的质量？根据所使用的信息检索模型的不同，可以将对这一问题的研究分成三个方向。这三个信息检索模型为：向量空间模型、概率模型和语言模型。不论使 用哪一种信息检索模型，其中心思想都是尽可能的将查询贴近用户的检索兴趣即用户的反馈信息。 如何评价用户反馈技术？这里涉及到评价所使用的数据集、评价指标、评测方式以及评测环境的构建。不同的评测环境会带来不同的评测结果。 本小节的主要贡献是对相关反馈领域当前的研究进展，做了全面的介绍；同时将用户反馈问题划分成 3 个基本的技术问题（如何获得反馈信息、如何使用反馈信息以及如何评价反馈技术）；并对目前这 3 个基本问题的常用解决方法以及研究进展进行了介绍。以前也曾经有过一些综述性的工作，例如 003; 003; 004。但是其中 004只是对相关反馈技术做了很简略的说明； 003的工作完成的比较早，遗漏了一些重要的部分（比如隐反馈以及语言模型），而这两个部分都是目前研究工作较集中的方面。文献 003只是对隐反馈中的主要文章做了说明，主要内容是侧重于介绍如何取得反馈，关于第 1 章 引言 4 性能评价以及如何使用反馈信息以改进检索系统的质量并没有做出很好的说明。 本文的以下部分是这样组织的：第 说明了如何获得用户反馈信息，介绍了当前主要的 3 种用户反馈信息取得手段以及对应的典型系统及优缺点。第 说明了如何使用用户反馈信息来改进检索系统的排序质量，同时介绍了在 3 种模型下各 种不同的反馈算法。第 说明了如何评价用户反馈技术。 何获得用户反馈信息 获得用户反馈信息主要有 3 种手段：显式用户反馈（ 隐式用户反馈（ 及伪反馈（ 显式用户反馈是一种经典的方法；许多研究人员还在考虑如何从用户的交互行为中隐式的发现信息作为用户反馈，也就是隐反馈；伪反馈的思想是从返回结果中选择一些文档作为用户反馈。 显式用户反馈 早期的用户反馈技术主要是用于文本信息检索领域，当时主要是采用显式用户反馈来获取用户的反馈信息。 统 990就是显式用户反馈方面的一个经典系统。该系统要求用户对检索结果显式的做出标记行为，给出反馈信息。例如指定关键词、对文档进行选择或是标注、给出自己的兴趣范围等等，这些方式都称为显式用户反馈。这种方式有一个前提是：用户在检索期间是有一个明确的检索目的，而这一目的不会变更。当把所有检索结果文档呈现在用户面前时，用户能够从中挑选出符合自己检索意图的相关文档或是不相关文档做出标记。这一过程是可以迭代进行的：用户给出一次显式反馈，检索系统根据用户标记的反馈文档，使用反馈算法来改进检索结果的质量；在新的 结果集上，用户还可以继续给出反馈。这一过程可以不断进行直到用户满意为止。 如何显式的获得用户反馈信息，通常的做法是把检索结果按照其与查询词之间的相关度大小排序之后返回给用户，以供用户浏览；并在界面上提供接口，允许用户在浏览时，对其中的某些文档进行标注，例如标注为“相关文档”或是“不相关文档”。如何提供更方便实用的接口来显式的与用户进行互动，这一问题更多的是依赖于人机交互领域的技术，在本文中将第 1 章 引言 5 不详细进行讨论。 在显式获得用户反馈技术方面，有 2 个值得说明的问题：一是主动学习（ 在显式用户反馈中的研究；二是关于负反馈信息的处理。 主动反馈“ et 2000; 001; 003; 005是指在用户对检索结果进行反馈之前，先对结果集进行一些预处理，并选择其中的部分文档集展示给用户。主动反馈的目的是保证所得到的反馈文档能带来最大的信息增益，加快反馈迭代过程，从而尽可能快的达到用户的检索目标。 主动反馈的算法有很多，列举