基于信息需求的社区问答答案总结.pdf

硕士学位论文硕士学位论文 基于信息需求的社区问答答案总结 information need based answer summarization for community question answering 刘晨龙刘晨龙 哈尔滨工业大学哈尔滨工业大学 2012 年年 12 月月 国内图书分类号 tp 391 3 学校代码 10213 国际图书分类号 621 3 密级 公开 工学硕士学位论文工学硕士学位论文 基于信息需求的社区问答答案总结 硕 士 研 究 生 刘晨龙 导师 王晓龙教授 申 请 学 位 工学硕士 学科 计算机科学与技术 所 在 单 位 深圳研究生院 答 辩 日 期 2012 年 12 月 授予学位单位 哈尔滨工业大学 classified index tp 391 3 u d c 621 3 dissertation for the master degree of engineering information need based answer summarization for community question answering candidate chenlong liu supervisor prof xiaolong wang academic degree applied for master of engineering specialty computer science and technology affiliation shenzhen graduate school date of defence dec 2012 degree conferring institution harbin institute of technology 摘 要 i 摘 要 近年来 社区问答门户网站作为新兴的一种知识共享平台给问答系统带 来了新的契机 为问答系统提供大量可用的问句及相应的答案信息 因其具 有的交互性和开放性的特点 使它能够很好的满足用户的信息需求 大量的 在线社区问答门户应运而生 其中包括百度知道 搜搜问问 天涯问答等等 用户获取知识的这一新手段 说明了传统搜索引擎仅仅基于关键词的查询方 式已经不能满足用户准确快速搜索自己信息的需求 社区问答门户允许用户 通过发帖的形式进行提问 提问内容中可以包括问题的内容以及对问题上下 文语境进行补充的问题描述 所有用户都可以对这个问题进行回答 提问者 也可以从答案中选择一个作为最佳答案 然而 由于用户对自己想要获取的信息领域并不熟悉 用户可能无法很 好的组织自己的查询语言来帮助自己得到想要的信息需求 因此本课题将用 户查询问句在社区问答门户上进行一个扩展 同时扩展的还有它们的问题描 述信息和答案信息 将包含各种不同信息需求的问题集与答案集进行协同聚 类 获得与用户查询问句相关的各个方面的信息需求 在不同的问题描述 上下文信息 之下的同一问题 它们产生的答案极 可能是完全不同的 例如对于问题 如何买手机 当问题描述是 我应该 到哪里去买 和 怎样才能买到便宜的 时 用户想要得到的信息需求是迥 异的 为了解决这个问题 在协同聚类模型中引入了以问题描述为基础的约 束条件 同时 社区问答回答者所提供的答案质量良莠不齐 有时在提供有用信 息的同时可能附加了无用的信息甚至是错误的信息 这样高冗余的信息 难 以应用于问答系统之中 本课题收集答案中的文本特征以及非文本特征 建 立答案排序模型 通过协同聚类后的簇中排序好的信息来进行答案总结 大量的答案集中必然会包含有较多的重复信息 而这些回答可能存在表 述上的区别而无法通过简单的相似度计算来进行检测 这样 本课题建立一 种答案相似检测模型 通过层次多分类器投票的方法 来检测答案中存在的 重复信息 并进行去除 最终得到正确的答案总结 关键词 答案总结 信息需求 协同聚类 社区问答 abstract ii abstract in recent years more and more community question answering portals emerge as a knowledge sharing platforms and provide new opportunities for qa system they offer plenty of questions and corresponding answers information to qa system they can well meet the users individualized information demand because of its interactivity and the characteristics of open there are lots of online community question answering portals including baidu zhidao sousou wenwen and tianya wenda appear it illustrates that the traditional search engine based on key words query has been unable to allow the users to search their own personalized information needs quickly and accurately the community question answering portals allow users to ask for information by post questions the questions may contain the content of questions and question description for context complement all the users can answer the questions and the questioner would choose one of the answers for best answer however when the users are not familiar with the field of information they need they may not be able to organize their own query language to catch their information needs this paper expands the users query on community question answering portals context information and answers are also extended at the same time we can get all aspects of information needs questions related to the users query by co clustering questions set contain different information needs and their answers set for a same question under different description context information the answer may be completely different for example the question how to buy a mobile phone when the question is described where to buy and how to buy a cheap one the information needs users want to get is totally different in order to resolve this problem introduces the constraint conditions into the co clustering model based on context information meanwhile the answers provided by users are quality uneven sometimes the useful information may be attached to the useless information even false information at the same time so the high redundancy of the information is difficult to be applied to question answering system in this paper we collected textual features and non textual features of the answers to establish the answer sorting model summarize the answers from ranked information in each cluster a large number of answers must contain much duplicate information and the answers may have a difference in the representation it will be difficult to detect by calculated the similarity in this paper we establish an answer abstract iii similarity detection model through leveraging multiple classifiers voting method detecting the duplicate answers and remove them keywords answer summarization information need co clustering community question answering 目 录 iv 目 录 摘 要 i abstract ii 第 1 章 绪 论 1 1 1 课题背景 目的和意义 1 1 2 国内外发展概况 2 1 2 1 问答系统国内外研究现状 2 1 2 2 答案总结国内外研究现状 5 1 2 3 系统评测方法 6 1 3 本文主要研究内容与组织 8 1 3 1 本文的内容 8 1 3 2 本文的组织 8 第 2 章 答案总结整体框架 9 2 1 问题定义 9 2 2 带约束条件的协同聚类模型 11 2 2 1 协同聚类 11 2 2 2 约束条件 11 2 2 3 k means 聚类算法 11 2 3 排序模型 12 2 4 总结生成 13 2 5 答案相似度检测 13 2 6 系统流程 14 2 7 本章小结 14 第 3 章 答案总结算法设计 15 3 1 引言 15 3 2 协同聚类算法 15 3 2 1 协同聚类算法描述 15 3 2 2 无监督的约束条件 16 3 2 3 相似度度量 18 3 2 4 自动选择 k means 聚类数目 18 3 3 答案排序特征 19 3 4 本章总结 21 目 录 v 第 4 章 基于层次多分类器投票的相似文本检测 22 4 1 引言 22 4 2 文本蕴含检测模型设计 22 4 2 1 预处理模块 22 4 2 2 知网语义处理模块 24 4 2 3 特征抽取模块 24 4 2 4 分类器模块 26 4 3 答案相似检测实验过程描述 27 4 3 1 edits 特征数据准备 27 4 3 2 特征选择方法 30 4 4 答案相似检测实验结果和分析 31 4 5 本章小结 32 第 5 章 答案总结系统实现与评测 33 5 1 实验设置 33 5 1 1 数据集 33 5 1 2 性能评测方法 34 5 1 3 阈值调整 35 5 2 系统性能 35 5 2 1 信息需求总结 35 5 2 2 答案总结 35 5 3 系统运行流程 36 5 4 存在的问题 39 5 5 系统演示 40 5 6 本章小结 41 结 论 42 参考文献 43 攻读硕士学位期间发表的学术论文及其他成果 47 哈尔滨工业大学学位论文原创性声明及使用授权说明 48 致 谢 49 第 1 章 绪 论 1 第1章 绪 论 1 1 课题背景 目的和意义 随着现代互联网的飞速发展 人们能够通过互联网轻松进行数据存储 信息传递以及知识共享 尤其是在现今搜索引擎大行其道的时代下 人们开 始大量使用搜索引擎来快速获取知识 然而这种方式的效率并没有期待中的 那么高 因为虽然搜索引擎诸如 google 百度等已经在今天取得了极大的成 就 但这些搜索引擎仅仅能够查询到与用户发送的查询词相关的内容 因此 其返回结果只是一些查询关键词的组合 而不是组织成人类能够直接理解的 自然语言形式来呈现 其提交给用户的结果只是一些带有查询词的相关网页 这其中只有小部分是用户直接想要获取的 而且用户则需要再次从这些网页 信息中寻找需求的信息 事实上 用户可能更乐意于得到直接用自然语言来 组织自己的查询问题而不是只组合关键词 例如使用 海天园有没有交互式 问答 而不是 海天园交互式问答 而且大多情形中 用户信息需求只 是他提出问题的最终答案 而并非与该问题的关键词相关的网页列表 另一 方面 以往出现的应用自然语言的问答系统虽然也能够解答用户提交的问题 但是这些问答系统的知识库大多通过一个有限 不变的信息集合来建立的 而且无法满足用户方方面面的信息需求 基于信息需求的社区问答答案总结 的目标就是解决涉及各行各业不同需求的问题 由于互联网上社区问答门户 信息涉及面极其广泛 其答案总结可以作为问答系统知识库的理想资源 本课题通过从百度知道爬取扩大的问答集 对问句答案进行总结 社区问答门户网站的答案组成是用户提交的答案通过其他用户的挑选而 形成的 最优 答案 社区问答门户网站日趋流行并成为搜索引擎的重要补 充 用户能够期待得到一个由人为选择出来的最适合他提出自然语言问题需 求的答案 但是 这些用户生成的答案内容通常是冗余的 有噪声的 甚至 不正确的 本课题旨在从社区问答门户中抽取出正确的答案集合 并对其进 行总结 增加答案准确性以及多样性 哈尔滨工业大学工学硕士学位论文 2 1 2 国内外发展概况 1 2 1 问答系统国内外研究现状 问答系统技术涵盖了文本处理技术 自然语言处理技术 信息抽取技术 搜索引擎技术等多个方面的技术 1 根据现今存在的问答系统应用的基本原 理的不同 可将其大致分成三种类型 基于知识库的类型 检索式的类型和 基于自由文本的类型 这三种类型的系统得到答案的来源和方式是各异的 第一种的问答系统类型为基于知识库的类型 该类型的系统可以被限定 在单个特定的领域 2 也可以是跨越多个不同的领域 3 4 问题的回答主要从 后台已有的知识库中获取 先要明确组织知识库的形式 并要对知识库进行 建立 整理以及扩展 维护 其中 对知识库进行扩展和维护是非常消耗人 力的 所以 不同于其他类型的问答系统 基于知识库的问答系统 大多是 被限定在某些问题的答案不会经常性 实时性地进行更新或扩充的领域 这 一类的系统应用它们的知识库来组织和存放对应某些领域的知识 应用模式 匹配技术以及信息检索技术等 从已有的知识库中查询到最匹配用户问句的 回答 5 7 为了达到方便查询以及提高查询速度的目的 根据对应不同领域对 知识表述的特点 需要采用不同的组织形式来表达对应各个领域的知识 因 此 知识库中数据的规模以及知识表达的质量 成为了决定基于知识库的问 答系统性能好坏的关键因素 而不同的知识组织形式需要采用不同的查询方 式来对这类问答系统知识库进行检索 因此 要根据不同领域内知识的特点 应当通过何种形式表现更为方便 何种检索技术更为适合知识的查询等 来 选择不同的知识库中知识的组织形式 知识的表示性强弱 表达能力高低和 推理可行性强弱三个考量 8 9 能够用来作为知识组织和表示形式优劣的评价 标准 feigenbaum 提出了 这种通过大量地积累知识 丰富系统知识库的量 变 能够带来计算机高智能的质变 美国微电子和计算机技术公司 简称为 mcc 的 doug lenat 在 1984 年发起了一个名为 cyc cyclopaedia 的缩写 研的究项目 10 cyc 采用了一种类似 lisp 风格的形式语言的知识描述语言 cycl cyc language 的缩写 cyc 消耗了大量的人力和物力来对理解自然 语言 自动学习能力 问题分析与问题求解等人工智能的原理和方法做深入 的研究 其中包括 200 人年的工作量 构建了拥有 50 万断言的知识库的规模 等 相应的在国内 中国科学院也进行了大量有关知识库方面的研究 从上 个世纪八十年代起根据统计数据显示的知识库规模已经多达八千两百亿个字 节 目前 对于这类基于知识库的问答系统 国内研究比较多的 是基于常 第 1 章 绪 论 3 问问题集 faq 库的问答系统 11 13 这样一个系统都有一套自己的常见问题数 据库用以存储用户的常见问题及相应的已经处理好的答案 当用户发出一个 查询问句时 此类系统在它的常见问题库中检索每一个与用户查询词最相近 的问句度 当检索到一个与查询问句的相似度最高的问句 就将该问题在知 识库中存储的答案提交给用户 14 一般情况下 此类系统还需要一个相似度 的阈值 如果常见问题库中的所有问句与用户的查询问句的相似度都不高于 这个阈值 则将本次用户的查询问句和认为处理过的答案新增到常见问题库 中 用来实现常见问题库的可拓展性 近年来 由于本体论技术的快速发展 涌现出了一批通过本体论的方法来创建知识库 15 16 这种系统显著的优势在 于 当用户的查询问句能够在知识库中检索到相应问答 就能够准确返回答 案 还有知识库具有较好的可拓展性 但是同时也会存在很强的缺陷 因为 知识库的规模难以保障 只有当用户的查询问句能够在系统提前预设的知识 库中检索到时 系统才能得到较好的性能 但是一旦检索不到相似问句 系 统将无法回答或者做出荒谬的回答 17 所以通常会发现 这类问答系统的性 能评测曲线 会呈现出一种尖峰状态 第二种为基于检索的问答系统类型 此类系统中很大一部分是研究在开 放领域内的 18 19 主要的核心技术是搜索引擎技术 当此类系统的用户提交 了一个自然语言形式的查询问句 通过一系列的分词 关键词抽取 关键词 语义拓展之后 从网络中或者是系统提前获取的问答集合中 检索出与关键 词列表关联最大的文档或网页提交给用户 此类系统主要应用的核心技术包 括自然语言处理的相关技术和信息检索技术等 基于检索的问答系统一般运 行流程如下所示 20 1 通过爬虫 crawler 技术将因特网上相关的网页内容进行定时或增量 爬取 经处理后加入到索引库中 保证实时更新 2 用户提交查询内容的方式可以为自然语言形式 3 对于用户提交的查询问句分别进行分词 关键词提取 关键词语义 拓展为一个关键词的列表等处理 用索引库的要求的查询表示方式来表达用 户提交查询内容 4 在提前建立好的索引库中检索修改形式后的查询内容 5 将检索到的结果列表 可以是单独的一个相关页面 也可以是根据 搜索引擎相关性排序之后的多个相关页面的结果 也可能是一个检索失败提 示 提交给用户 基于检索的问答系统的经典的有国外的 ask jeeves 系统 21 encarta 系统 22 和国内的 小灵通 系统 23 接受到用户提交的以自然语言形式组织的查 哈尔滨工业大学工学硕士学位论文 4 询内容 ask jeeves1系统不仅可以返回以文本形式呈现的相关答案 还能给 出与这段文字相对应的链接地址 微软公司开发的 encarta12系统 在性能表 现上比较稳定 在回答的精确性和返回速率上都基本达到用户的需求 国内 的 小灵通 系统是国内较经典的第二类基于检索的问答系统 该产品由中 科院计算所设计研发 面对的主要受众为以中文为母语的用户 接受用户提 交的自然语言形式的中文输入后 需要经过预设模板库查询 查询内容词法 语法分析 检索返回列表排序等处理过程 其中最核心的流程是基于预设模 板库中的模式匹配 处理旅游领域信息的 小灵通 系统属于限定领域的基 于检索的问答系统 然而 对比百度 谷歌等搜索引擎 此类系统在回答的 精确性和回答的速率上 存在的优势极不明显 另外 此类系统的很大一部 分的检索结果列表 跟传统搜索引擎的检索结果类似 是一段文本或者直接 是网页 而非用户最想直接得到的答案信息 第三种类型是基于自由文本的问答系统类型 24 此类系统大多具有三个 基本模块 查询内容处理 自由文本检索 答案信息抽取 其中 自由文本 检索是该类系统的核心处理模块 而答案信息抽取模块的优劣直接影响系统 进行回答的评测性能 此类系统包含了多个方面的技术 其中包括文本处理 技术 信息抽取技术 信息检索技术和自然语言处理技术等 通过用自由文 本集合而非传统的知识库集合 此类系统能够大大减少搭建和维护更新知识 库所消耗的人力和物力 并解决了知识库规模无法满足的难题 运用信息抽 取技术 只将确定的答案信息提交给用户 而不仅是相关的文档或者网页 避免用户在获得的大量网页内容或文档信息中二次搜索需求答案而浪费的时 间 当信息抽取的结果较好时 此类系统的性能表现极佳 25 近年来 研究的焦点正逐步趋向于基于万维网的开放领域问答系统 基 于检索的问答系统类型 系统呈现给用户的是与查询内容相关的文档或者网 页 并非用户真正想要得到的答案本身 而基于万维网的开放领域问答系统 将网络作为进行检索的知识库 具有极大的规模 能够有效避免建立和扩展 知识库时遇到的困难 26 27 用户提交自然语言形式的查询后 经过处理 检 索 信息分析 信息提取 去伪存真结果的冲突 还更准确和具体的答案 总体上看 问答技术英文比中文问答技术更加成熟 英语正在迅速走向实用 的问答系统 但相比于英文 汉语问答系统 因为中国自己的特点和解决方 法的限制 大部分只限于某一特定地区或在一定范围内 可以回答问题的类 型也比较简单 真正的面对网络的开放领域问答系统 其准确性和精度不高 1 2 第 1 章 绪 论 5 商业系统并不常用 1 2 2 答案总结国内外研究现状 社区问答门户网站已成为互联网的一个最重要的信息来源之一 得益于 的社会用户之间自发的互动 这种服务在很大程度上弥补了传统搜索引擎需 要人工组织问题及答案的缺点 在社区问答门户网站中的问题数量急剧增加 的情况下 这些问题的再利用就变得非常的重要 传统检索方法只提供给用 户基于其查询相似度的问题排名列表 这就要求用户自己选择最后的答案 然而 答案只反映了普通用户的想法 而非专家的想法 这就可能会导致答 案的片面性 同时 答案的质量也是参差不齐 根据刘元杰对社区问答门户 中问题的调查 28 约 22 的最佳答案并不是最好的 而超过 52 的最佳答案 不是唯一最佳答案 由于用户知识的限制和答案质量的高度差异 用户难以 找到他们想要的信息 因此 对用户的查询提供一个全面和准确的答案总结 成为一项重要的任务 此外 问题检索服务需要用户浏览大量的网页 将会 花费用户许多时间 因此不适合那些需要紧急信息的用户 如移动互联网用 户 用户更喜欢直接 简洁和全面的答案排序列表 在这方面 相似问题的 答案总结是相当重要的 以往的关于社区问答门户问题及答案的研究主要聚焦于相似问题检索 权威答案发现和答案质量度量 29 其中 答案质量度量与本课题的相关性最高 最典型的是 jeon 30 的评估 社区问答门户网站中答案的质量 他们发现来自 问答社区网站上 的 1700 个问答对中大约 1 3 的答案存在质量问题和大约 1 10 甚至是错误的答 案 他们使用 13 个非文本的特征并训练最大熵模型来预测答案质量 他们发 现 当回答的质量度量结合对数似然检索模型时 检索相关性能够明显改善 社区问答门户网站为用户在网上查询资料提供了一个替代的方式 在社 区问答门户网站上发布的问题通常是通过提交查询词给搜索引擎来反映用户 的需求 broder 31 建议搜索查询可以分为三类 即导航 信息和资源 rose 和 levinson 32 提出了一个更详细的分类 其中 信息查询细化为五个子类 资源查询细化为四个子类 在开放域问答系统研究中 从事实类问题的文本 数据库自动提取所需的确切答案 33 的所有的高性能系统都已将问题分类 34 根据 nist trec qa track 过去的经验 社区问答门户网站的问题分类将帮 助以确定给定问题类型的预期最佳答案类型 35 36 目前极少已经完成的研究是直接进行答案总结方面的 刘元杰 28 与唐阳 37 完成的研究比较类似于本课题 刘元杰关注于自动总结社区问答门户网站 哈尔滨工业大学工学硕士学位论文 6 的答案 它建议 文摘技术 38 可以用来创建社区问答门户网站不同的问题类 型的答案总结 对给定问题及其答案创造一个答案总结可以看作是一个多文 档文摘的任务 它只是将文档替换成答案并且应用这些技术来产生答案总结 28 仅仅是手动分析社区问答门户网站上的问题和答案并提出了问题和 答案的分类 他们试图通过总结问题的答案来提高问题的质量 相比之下 37 总结类似问题的答案列表 可以提供更全面的结果给用户 此外 28 的工作只集中在总结观点问题和开放问题 37 放松这个限制 它提供了针 对一般复杂问题的一个共同的框架 最后 37 的工作针对中文答案总结 而 28 的数据是针对英文的答案总结 它提出最大覆盖模型是一类 0 1 背包问 题 可以通过线性规划有效地解决 最大覆盖模型已成功地应用在许多自然 语言处理任务 如多文档文摘等 37 将最大覆盖模型首次应用在答案的总 结之中 在上述答案总结的方法的基础上 本课题提出了一种新的答案总结的方 法 包括答案与问题进行协同聚类 加入上下文信息为约束条件 答案相似 监测方法等将在以后的章节详细叙述 1 2 3 系统评测方法 本课题的主要评测方法采取多文本文摘最常用的自动评测工具包 rouge 38 它通过比较其他理想人为建立的总结来自动确定某些总结的质量 度量方法为计数计算机自动生成的总结和由人为建立的理想的总结之间的重 叠单元数量 例如 n gram 词序列和词对等 它包括了四种不同的评测标准 rouge n rouge l rouge w 和 rouge s 均包含在 rouge 文摘评 测包中 其中的三个已经在 document understanding conference duc 2005 上得到使用 39 传统的总结评测涉及人类对不同的质量指标的判断 例如 连贯性 简 洁性 语法 可读性和内容 40 然而 在 duc 上即使是简单的人工评测总 结对规模大一些语言的质量问题和内容覆盖都将需要超过 3000 小时的人工 时间 这是非常昂贵并且难以进行频繁地生成 因此 如何进行自动评价总 结在近年来总结研究界已经吸引了大量的关注 例如 saggion 41 提出了三种 基于内容的评测方法通过度量总结的相似性 这些方法分别是是 余弦相似 度 单元重叠 例如 1 gram 或 2 gram 和最长公共子序列 然而 他们并没 有显示这些自动评测方法对比相关的人为判断的结果如何 继成功应用自动 评价方法 blue 42 在机器翻译评测 43 说明了类似 bleu n gram 共现统计 的方法可以用于总结评测 第 1 章 绪 论 7 以下介绍 rouge 评测工具包的四种不同的评测标准 1 rouge n n gram 共现统计 形式上 rouge n 是一种候选总结和参考总结之间的 n gram 召回率 rouge n 计算公式 1 1 如下 1 1 式中 n n gram 的长度 n gram 共现在候选总结和参考总结的最大数目 2 rouge l 最长公共子序列 一个序列 1 2 n 是另一个序列 1 2 m 的子序列 如果存在 x 的序号的一个严格递增序列 1 2 使得对所有 1 2 有 44 给定两个序列 x 和 y x 和 y 的最长公共子序列 lcs 是它 们公共子序列的最大长度 lcs 已经用于在从平行文本建立的最佳翻译词典 中确定候选关系 梅拉梅德 45 使用两句话的 lcs 长度和较长那句话的长度的 比例来度量两句话的相关性 他使用 lcs 作为一个近似字符串匹配算法 saggion 41 用归一化成对 lcs 来比较自动文摘中两个文本的相似度 3 rouge w 加权最长公共子序列 lcs 有不错的性能 但是基本的 lcs 也有一个问题 它不区分在其嵌入 序列不同空间关系的 lcs 例如 给定一个参考序列与候选序列 y1和 y2如 下 a b c d e f g 1 a b c d h i k 2 a h b k c i d y1和 y2有相同的 rouge l 得分 然而 在这种情况下 y1应该是比 y2 更好的选择 因为 y1是连续匹配的 为了改进这个情况 引入了 rouge w 加权最长公共子序列方法 4 rouge s skip bigram 共现统计 skip bigram 是按句子顺序的允许间隙的任意一对词 skip bigram 共现 统计计算候选总结和参考总结中 skip bigram 的重叠度 用一个例子来详细 说明 skip bigram 句一 小明 卖掉 了 玫瑰 句二 玫瑰 卖掉 了 小明 句三 小明 玫瑰 卖掉 了 每个句子有 c 4 2 6 个 skip bigram 句一的 skip bigram 包括 小明 卖 掉 小明 了 小明 玫瑰 卖掉 了 卖掉 玫瑰 了 玫瑰 句 哈尔滨工业大学工学硕士学位论文 8 二中的匹配的 skip bigram 只有 卖掉 了 句三种的匹配 skip bigram 包括 小明 卖掉 小明 了 小明 玫瑰 卖掉 了 1 3 本文主要研究内容与组织 1 3 1 本文的内容 在基于信息需求的社区问答答案总结系统中 本课题着重在提高人机日 常对话的智能 主要包括问题 答案和问题描述的文档形成 答案排序特征 抽取 问题和答案的协同聚类 答案句子排序 文本相似计算 答案总结和系 统评测这几个模块 各个主要阶段的任务如下 1 文档形成过程进行问句的预处理 包括停用词过滤 答案排序特征 抽取 问句类型判别 聚类特征抽取和约束条件矩阵生成等 2 问句和答案协同聚类 将不同信息需求的问题和对应答案文档聚类 获得回答多样性结果 3 文本相似计算 提取多种文本特征 通过层次多分类器投票的方法 判断两个文本的相似性 去除答案中冗余的信息 4 答案句子排序 通过提取的答案文本及非文本特征 对簇内的答案 进行排序 并进行冗余处理 生成最终的答案总结 1 3 2 本文的组织 以下是本文各章的内容安排 第一章为绪论部分 主要概述了本课题的背景以及目的和意义 重点部 分是介绍问答系统问答以及答案总结在国内外的发展情况 还简述了本课题 进行评测的工具和标准 最后对本文的内容和组织进行了罗列 第二章主要讲述了本课题中系统构建所用技术和流程顺序 并对本课题 涉及的相关算法进行了简单介绍 第三章详细说明了答案总结算法设计流程与实验过程 重点是协同聚类 算法的设计与实现 通过对收集的真实环境下语料的观察 和人机对话场景 的归纳总结 实验的过程和结果分析都在本章中说明 第四章详细说明了本课题采用的答案文本相似检测的方法 通过文本相 似计算 去除答案中相似度过高的内容 首先介绍了基于层次多分类器投票 的计算相似的方法 之后是实验过程和计算相似的相关阈值的确定 第五章介绍了在本课题的评测方法 系统的搭建 以及后期系统可以改 进的方面等 第 2 章 答案总结整体框架 9 第2章 答案总结整体框架 2 1 问题定义 对于给定的一个问题 本课题的目的是去收集其信息需求和在某些明确 的问题描述下的答案 使用户能够得到更加全面和有用的信息 以解决用户 的信息需求目标 为了扩大覆盖范围的信息需求 答案和上下文信息 语义 上类似的问题视为等价 将他们的帖子合并在一起 作为一个扩大的信息来 源 命名为 解决本课题存在的问题有三个必不可少的基本元素 对 其定义如下 扩大的问题集 标题中的问题和问题描述中的问题构成一个扩大的问题 集 一个问题是代表着一个信息需求 扩大的上下文信息集 将问题描述信息当作与问题集上最相似的句子 分配不同的问题描述给位于同一个帖子的不同的问题 与此相反 根据观察 在大多数情况下同一个帖子的问题可以被视为共享同样的问题描述 如表 2 1 所示 因此 系统使用问题描述中的所有信息包括问题作为上下文信息 所 有 p 中的上下文构成一个扩大的上下文信息集 扩大的答案集 类似的 所有 p 中的答案形成一个扩大的答案集 表 2 1 同问题标题而对应不同问题描述和答案示例 问题标题 如何选购地板啊 问题描述 1 家里最近要装修 不知道如何选择地板 如何才能节约材料 不浪费 回答 1 1 根据自己家庭装饰档次 选择相应档次的木地板与之配套 如属中 高档装饰工程 就不能选择普通地板 反之亦然 问题描述 2 有哪些类型 回答 2 软木地板 软木地板实际上不是用木材加工成地板 而是以栎树 橡 树 的树皮为原料 经过粉碎 热压而成板材 再通过机械设备加工 而成 以上三个要素的关系如图 2 1 所示 在特定的上下文信息中的每个问题 和答案成为一个集合 一共有三个主要的问题需要解决来达到系统的目标 1 一组扩展的内容和答案可能含有大量冗余信息 为去除冗余和增强 新颖性 考虑每一个问题 答案句子作为一个文件并按照多文档主 题摘要的方法存储 聚合关注同一主题的相关信息 信息需求 然 哈尔滨工业大学工学硕士学位论文 10 后根据其重要性和质量来排序信息 问答社区系统的文本特征和非 文本特征都被用来在排序过程中来说明信息的重要度 2 信息需求和答案之间需要建立对应关系 事实上 它们之间的对应 可以类推到协同聚类中对象和特征之间的二元关系 即问题聚类和 答案聚类可以相互促进 因此 协同聚类应用于对将应关系建立模 型 以及同时提高问题聚类和答案聚类的效果 此外 如果问题和 答案之间的词汇的差距影响聚类 还需要将无监督的约束条件加入 到协同聚类算法当中 这些约束条件明确了问题和答案的句子是否 应在同一簇里 自动生成根据语义相似度或问题和答案句子之间的 相对位置 带约束条件的协同聚类模型如图 2 1 所示 更多的细节 在本章 2 2 节详述 3 上下文信息应当用来建立信息需求和回答之间确定关系 这是通过 设置上下文信息和问题 答案之间的语义相似度阈值的方法来进行 只有当相似度高于阈值时才可能存在这种关系 通过调整阈值 上 下文信息对信息需求和回答之间关系的影响也将随之改变 预期的结果如图 2 1 c 中的形式 在不同的上下文信息之下 产生不 同的信息需求 ij 和相应的答案总结 sj 图 2 1 答案总结框架 a b c 第 2 章 答案总结整体框架 11 2 2 带约束条件的协同聚类模型 2 2 1 协同聚类 协同聚类通常可以转化为一个在偶图上的割问题 记偶图 q a 含 有 2 个顶点集 q和 a 其中 行顶点 中的点代表的是问题 而 a 列顶点 中的点代表的是答案 另外 ij是顶点 i q和 j a之间的边的权重 即 相应的问题 i和答案 j之间的语义相似度 邻接矩阵m的二部图如下 0 0 t01 2 1 一个二部图 的协同聚类即是将行顶点 和列顶点 划分为 k 个子图 1 2 其中每个子也是一个二部图 i 1 2 k 协同聚类的目标就是去找到使不同的子图中点之间的边权重最小的划分 2 2 2 约束条件 假设某些顶点被认为属于同一组 预计这样的聚类的结果与一定的先验 知识是一致的 首先通过一个 必定链接 约束矩阵 c 给先验知识建模 1 当 和 在用一个簇 0 否则 2 2 式中顶点 与顶点 来自集合 或 将约束矩阵 c 分解成 0 0 2 3 式中 都是集合 中的行顶点的约束条件 都是集合 中的列顶点的约束条件 带约束条件的协同聚类的目标是去找到使不同的子图中点之间的边权重 最小的划分 同时使满足约束条件的数量最大 2 2 3 k means 聚类算法 k means 算法首先需要确定聚类数目 k 之后把待聚类的 n 个数据对象分 割成为 k 个类别使得其聚类之后能够满足以下两点 第一 被划分在同一个簇中的数据相似度高 第二 没有被划分在同一个簇中的数据相似度低 通过计算各个簇中数据的均值所获得的聚类中心来计算以获得聚类相似 哈尔滨工业大学工学硕士学位论文 12 度 在基于划分的聚类算法当中 k means 算法是其中较为经典的之一 同时 也是十大经典的数据挖掘算法之一 k means 算法的核心思想是随机取得数 据中的 k 个点设为初始聚类中心开始进行聚类 对其他相似度最高的数据划 分为聚类中心的同一类 之后进行迭代过程 依次更新每个簇的聚类中心的 数据 直至聚类的效果达到最优 假设要把样本集分为 c 个类别 算法如算法 2 1 所描述 算法算法 2 1 k means 聚类算法 输入 输入 n 个数据对象 输出 输出 c 个聚类簇 算法 算法 1 适当选择 c 个类的初始中心 2 在第 k 次迭代中 对任意一个样本 求其到 c 个中心的距离 将该样本归到距 离最短的中心所在的类 3 利用均值等方法更新该类的中心值 4 对于所有的 c 个聚类中心 如果利用第 2 步和第 3 步的迭代法更新后 值保持 不变 则迭代结束 否则继续迭代 k means 算法的优势是它能够简单和快捷的进行聚类过程 如何选取初 始的聚类中心以及相似度计算的距离公式是 k means 算法的核心问题 首先 从待聚类的 n 个数据对象中随机选择 k 个数据来当做初始的聚类中心 用一 定的距离公式计算剩下的其他 n k 个数据对象与这个 k 个聚类中心之间的相 似度 距离 将它们划分到与其最相似 距离最近 的 用聚类中心来代表 的 聚类 接下来再通过计算每个簇中所有数据的均值来获得新簇的聚类中 心 迭代进行以上步骤直至定义的标准测度函数收敛 一般的标准测度函数 都用均方差来表示 这样形成的 k 个簇将会拥有如下的特点 各簇内的数据 点较为紧凑 而各个簇之间的数据点尽量的远离 2 3 排序模型 经过协同聚类之后 关注同一个信息需求的相关问题和答案已经被聚类 到了一起 在各个组内 问题和答案要进行通过信息重要性和质量进行排序 信息需求代表 由于只需要一个问题来代表的共享信息需求的同一个簇 中 簇的中心是直接用来当作代表 第 2 章 答案总结整体框架 13 答案排序 区别于问题簇 答案需要根据他们的信息量和质量进行排名 作为答案总结生成的基础 多种因素将会影响答案的排序 记一个因素为 j及 其权重为 j 则答案排序分数可以通过如下公式进行计算 score i j j n j 1 j 0 1 j 1 n j 1 2 4 2 4 总结生成 如上文所述 选择聚类中心问题当作代表 也就是说将聚类中心用来总 结问题簇的信息需求 对于每个答案簇中的总结 由于应用了扩大的答案集 在生成的总结中 信息冗余将会相当严重 所以必须引入必要的冗余控制 系统采用一个简单 而有效的方法来选择总结句子 开始时 从已排序的列表选择一个句子加入 到总结中 依次从已排序列表中选择句子和总结中已有的句子进行比较 只 有当一个句子和总结中的任何一个句子的相似度都不高时才加入总结 相似 计算方法在第三章详细说明 重复这个过程直到句子长度在总结达到长度限 制 在系统的实验中 阈值被设置为 0 8 信息需求和答案总结之间的对应关系通过匹配问题和答案簇 根据协同 聚类模型的目标 如果二分图两边的顶点被划分到同一个子集中则认为一个 问题簇匹配一个答案簇 也就是说 两边顶点的边权重和最大 最终的答案总结从每个簇的子总结中合并 同时加上相应的信息需求 信息需求的簇大小是和热门度呈正相关 因此总结通过他们信息需求的簇的 大小进行排序 2 5 答案相似度检测 由于答案中可能大量存在的重复内容 所以需要引入答案相似度检测方 法 传统的基于词向量距离的相似度检测方法虽然可以很好地通过词重叠去 除掉一部分的重复答案 但是有相当一部分的问题无法解决 这些问题其中 主要集中体现在以下几个方面 1 近义词或同义词匹配 例如 崩塌 与 崩坍 这类同义词 表达 相同的意思缺无法进行匹配 2 矛盾关系挖掘 例如 我是一个很喜欢玫瑰花的人 和 我是一个 不喜欢玫瑰花的人 之间的词向量距离很小 但是表达的却是完全矛盾的意 义 3 上下位关系匹配 例如 我住在中国 和 我住在北京 中国 是 北京 的上位词 故 我住在北京 表达的是比我住在中国更精确的信 哈尔滨工业大学工学硕士学位论文 14 息 针对以上问题 本课题提出了一种基于层次多分类器投票的答案相似度 检测方法 通过抽取大量文本相关特征 建立了一个层次分类模型 并最终 用多分类器投票的方式获得结果 详细的内容将在第四章做具体的阐述 2 6 系统流程 基于信息需求的社区问答答案总结系统 主要包括三大部分 问句答案 协同聚类 答案排序总结 答案复述的判定 系统流程如图 2 2 所示 开始 问句检索 预处理 特征提取 协同聚类 答案排序 相似检测 输入问句 输出总结 结束 图 2 2 基于信息需求的社区问答答案总结系统流程图 2 7 本章小结 本章对基于信息需求的社区问答答案总结系统做了简要的介绍 主要讲 了问题的定义 带约束条件的协同聚类 排序模型 总结生成等 包括本课 题中所用到的聚类算法和文本相似度计算算法 最后 给出了系统流程图 可以清楚系统的整体处理过程 第 3 章 答案总结算法设计 15 第3章 答案总结算法设计 3 1 引言 本课题的最终目标是从大量答案中总结出对应不同信息需求的答案 首 先需要通过协同聚类 得到不同信息需求的问题文档簇和答案文档簇 然后 从答案簇中排序最优结果 并去除冗余 最终生成答案总结 本章将具体阐 述协同聚类和答案总结过程的算法设计流程 3 2 协同聚类算法 3 2 1 协同聚类算法描述 系统应用谱约束模型 scm 算法来进行约束协同聚类 上文提到带约 束条件的协同聚类的目标是找到使不同的子图顶点之间的边权值的最小的划 分 同时满足约束条件的数量最大 给出一个二部图 q a 将约束条 件明确纳入全局优化 即令以下的目标函数最小化 min 1 2 k 0 1 3 1 式中 是约束置信参数 由于系统采用了无监督的约束条件 允许来调整约束条件的影响 定义协同聚类划分矩阵 3 2 式中 行顶点 问题 集 的划分 列顶点 答案