基于关键词复杂网络中的带权最短路径的复杂查询扩展课件

基于关键词复杂网络中的带权 最短路径的复杂查询扩展 杨华1,2姬东鸿*3萧国政2 1贵州师范大学数学与计算机学院 贵阳 550001 2武汉大学文学院 武汉 430070 3武汉大学计算机学院 武汉 430070 即时通信：QQ与微信：905018910（高品低智 ） 摘 要： 基于大型文档集构建了的关键词同现网络 在该网络中，基于带权最短路径长度的概 念，提出了一种新颖的、针对自然语言描 述的复杂查询的扩展方法。完成了针对的 自然语言表达的复杂查询的信息检索任务 ，以验证该查询扩展方法方法的有效性。 实验表明，用我们的方法度量词语与复杂 查询之间的相关度是有效的，但结果依赖 于原始复杂查询的良好分析。 1引言 信息检索系统一般依赖于倒排索引，各种 检索模型基本的操作是判断符号是否存在 于文档中，这是基于布尔运算的、机械式 符号匹配，只有文档包含查询中的词语的 符号，才能被检索到。然而，由于用户查 询与其真实需求之间存在的偏差，很有可 能某些文档符合用户需求但却因为未包含 查询中的词语而不能被检索到。 1引言 查询扩展可以提高检索性能1, 2 。在原始查询基 础上扩展出的新词集合称为扩展词表。 根据扩展词表的来源，目前的查询扩展技术可分 成三类3 ： 1）基于全局语料集分析的方法(简称全局分析法)：在 整个待检索的文档集上统计同现概率、互信息等自动 生成扩展词表48 。 2）基于局部文档集分析的方法(简称局部分析法)：根 据一定的相关性假设获得小规模数据，比如认为初次 检索的前K篇文档是相关的，从中获得扩展词表。 3）基于语义知识辞典的方法：根据语言学知识而获得 基于语义的、含有词语间语义关系信息的人工资源， 获得扩展词表911 。 1引言 本文提出一种与上述三类方法均不类同的 方法，获取扩展词。 基于大型语料，构建文档的关键词同现网 络，对复杂查询进行扩展，其关键步骤是 获取与复杂查询高度相关的词语，事实上也就 是度量词语与短文本的相关性的工作。 2基于关键词复杂网络中的最短路径的查询扩展 基于最短路径和的查询扩展的总体思想如 下： 首先构建了关键词同现网络（Key Term Concurrence Network，KTCN） 在KTCN中获取离复杂查询中的每个词语的带 权最短路径长度最短的词汇 用最短路径长度度量词语之间的相关性，获取 扩展词并对其加权。 2.1网络构建 2.2复杂查询分析 所谓复杂查询，就是用户输入的用自然语言表达的查询，而非 过去普遍研究的单个的、短的词语。 对于自然语言表达的复杂查询Q，如 “列举全球气候变暖的危 害”。 首先用如下方法分解：对L中的每个词语W，如果W包含于字 符串L，则将W加入到Qa中；去除诸如“提问词”之类的停用词 ；且向量中的每个元素的权值为L中每个词语的长度与原始查 询的长度之比。 没有采用分词的方法，因为在查询Q的语境下，“全球气候”，“ 全球气候变暖”等是表达了完整含义的词语，其含义比单独的“ 全球”和“变暖”具备更具体的词义。 以Q=“列举全球气候变暖的危害”为例，最终得到得到的初始查 询向量是：Qa=， ， ， 。 2.3扩展长度设置 本文将使用带权最短路径的长度表达词语之间的语义距离：假设在 KTCN中，两个节点之间的带权路径长度越短，说明相应两个词汇亲 密度越高。 比如对于Qa=， ， ， ， 我们将其中的每个词语称为扩展源，分别对每个扩展源Ts扩展：使用 dijstra算法，依次获取离Ts最短路径长度最短的ExtNum个词。 xtNum即扩展长度：对每个扩展源扩展出的语词的个数（包括扩展源 本身）。 查询扩展过程将针对始查询向量中的每个元素（扩展源），对每个扩 展源Ts，获取的扩展长度为ExtNum个扩展词形成的向量ETs按离扩 展源的最短路径长度从短到长排序，即按与扩展源的亲密程度排序。 有一点值得提及的是，在大型的网络中，最短路径的获取实际是一件困 难的任务，计算的细节，请注意我们进一步将发表的文章。 2.4扩展词加权策略 将每个扩展源 的扩展结果 按照其与扩 展源的亲密 程度排序， 被扩展出的 语词按照亲 密程度的名 次加权；多 个扩展源可 能会扩展出 相同义位， 如果一个词 语被多次扩 展，则扩展 结果中它的 权值则被累 积。具体算 法见图2。 2.5检索过程 2.5.1倒排索引 本文的支持项目的目的本身不是为了查询扩展， 而是探索在复杂网络中如何度量词语的相关性。 这里的查询扩展工作的目的是检验基于复杂网络 的方法的有效性，因此没有采用为汉语检索系统 中常用的一元及二元做倒排索引的方法， 而仅对文本中的关键词做倒排索引FInvIdx，索引 建立过程为： 如果文档D中以语词T为关键词，则对这对“语词文档” 建立索引项。索引项的形式为T，D，F，其中 F为词语T在文档D中作为关键词语出现的频次。 注意，并非T出现在D中，就对其建立索引项。我们目 前的研究尚未发现好的方法使用F帮助以获得比本文更 好的结果，因此下文中仅用表示: T是D的关键 词。 2.5检索过程 2.5.2获取 相关文档 ：这一步 的操作是 根据扩展 后的查询 向量，利 用其中的 语词和相 应权值， 检索结果 文档并按 得分（相 关性）非 递减排序 。 3实验结果 3.1语料与评测参数 采用NTCIR7中的IR4QA任务1315 验证我们的 方法的效果。NTCIR7 中IR4QA的简体中文语料( 检索结果也是简体中文)由新闻文章组成，共 545162篇文档。 中文上的IR4QA的评测数据最终包括了97个话题 。IR4QA任务使用平均正确率(Average Precision ，AP)、Q-measure (Q)16 、标准化折扣累积增 益（Normalised Discounted Cumulative Gain， nDCG）17 作为评测参数。其中AP是IR中研究 比较充分的参数，Q和nDCG可以处理分级的相关 性。 3实验结果 3.2实验结果与分析 经过大量实验测试，alpha设置为200左右，beta 设置为15左右时总体性能比较好。表1列出了 alpha=200，beta=15时在不同的扩展长度得到的 结果。从表中看出扩展长度在25的时候成绩最好 。但是，由于没有参与pooling等因素(NTCIR中 获取测试集的过程)，我们的结果可能比表1所显 示的更好，但是能提高多少暂时无法考证，原因 见文献15 。 3实验结果 3实验结果 3实验结果 图 4各AP得分段的话题个数 3实验结果 图 4列出了表2中C情形，即我们目前取得 的最好成绩的一组数据的AP在各个分值段 的话题个数。可以看出，检索性能性能非 常不平均，两极性比较强： 均值为0.4135的情况下标准差高达0.2231。 在NTCIR7 IR4QA最终评测的97个话题中 AP高于0.675的话题多达18个，其中0.775到0.8的 话题高达9个。 分值小于0.2的话题个数高达22个，仅得分接近0（ 小于0.1）的话题就多达8个。 3实验结果 经过观察得分非常差的话题的初始查询向量，我们发现， 这些话题都分析得非常差。 例如，对话题ACLIA1CST42，即“谁是本拉登？”，没有获得任 何分析结果因此该话题的得分为0，获得的初始查询向量为空（注 ：语料库中确实有包含“本拉登”字符串的文档，但是关键词抽取工 具认为没有一篇文档以“本拉登”作为其关键语词，因此网络中不存 在相应的结点），因此该话题的得分为0； 对话题 ACLIA1CST74，即“列举中俄之间发生的事情”，使用话 题分析策略4，获得的初始查询向量为“俄之间 0.25 发生 0.166667 发生的事情 0.416667 事情 0.166667 之间 0.166667” ，除了“俄之间”非常勉强地和原始话题有点关系外，其 他的语词几乎不会携带与话题相关的信息。该话题的得分是AP得 分0.007。以上现象说明瓶颈在于话题分析阶段。 好的信息：扩展词的寻找和扩展词的加权策略本身性能良好，符 合我们支撑项目最重要的目标； 坏的消息：检索结果严重依赖于话题分析。 4与传统方法的比较 相对于第1节中描述的传统查询扩展，本文 采用的查询扩展方法（简称KTCNQE）有很 多独特之处。 KTCNQE不依赖于人工资源。 相对于局部分析，KTCNQE能避免局部分析中 对局部文档相关性程度的敏感性，而且只需要一 次检索。 与全局分析相同相比 KTCNQE间接利用了全局文档的丰富信息，获取的 语词之间的关联性相对局部分析法更准确。 与全局分析不同的是，KTCNQE不需要计算所有语 词之间的关联度之后才能使用，具有更好的实时性。 4与传统方法的比较 KTCNQE能随着文档集中的文档不断产生， 消失，修改等的动态变化（比如互联网上的 文档）而获得动态的结果，因为这些变化导 致的只是KTCN中的节点，边，权值的增减 操作，因此KTCNQE方法不受限于领域，能 自动跟上由于流行语言的变化。 KTCNQE用于海量文档时，文档数量的越大 ，KTCN的边权值更加能表达语义上的相关 程度，使得查询扩展更准确。KTCNQE可以 检索到不包含原始复杂查询中的词语的相关 文档。 5下一步的工作 本文的目标并不在于查询扩展本身，而是以查询 扩展任务检验我们的度量短文本和词语之间的相 关性的方法的效果。 就查询扩展工作本身而言，有如下工作值得进