（计算机软件与理论专业论文）检索结果集选取算法研究.pdf

中文摘要 中文摘要 随着网络的发展 网络上的信息量不断增加 为了让人们能够方便地从海量 信息中获得所需信息 搜索引擎技术应运而生并且不断发展壮大 但是现在搜索 引擎上查看的结果都是单一呈现的 结果孤立缺乏整体性 依然需要用户人工对 信息进行组装 进而获得一个完整的信息 同时结果之间包含的信息具有很大的 冗余性 特别是排在前面的结果冗余更大 这就需要寻求一种方法尽量来解决这 个问题 本文分析了现有搜索引擎的排序算法 结果之间新颖性的研究方法以及最小 文档集合生成算法 得出现有搜索引擎返回给用户的相关结果存在着结果之间冗 余性较大 结果单一以及信息不完整等不足 在满足用户查询需求的满意度上有 一定的局限性 所以本文利用了一种基于子主题提取的文档集合生成算法对相关 检索结果进行组合 并且提出了一个并集度的概念 又考虑了新颖性方法 提出 了一个新颖度定义 并给出了公式说明 利用结果集合的相关度 并集度和新颖 度对初始结果集合进行重新排序 保证排在前面的文档集合在不降低相关性的基 础上 尽量使集合包含的信息更加完整 冗余性更小 对于算法中的三个因素 采用了实验对比的方法来确定他们的因子 确定因 子组合后 根据此因子组合得到的文档聚类集合的结果 和初始文档集合进行实 验结果比较 实验结果表明在进行算法改进后 整体相关度有所上升 同时排在 前面的文档集合又具有较大的并集性和新颖性 这样的结果不仅满足了用户的查 询请求 同时让用户获得了更好的查询满意度 关键词 文档聚类 检索结果集 并集度 新颖度 黑龙江大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r k t h ev o l u m eo fi n f o r m a t i o no nt h en e t w o r kh a s b e e ni n c r e a s i n g i no r d e rt ol e tp e o p l eb ea b l et og e ti n f o r m a t i o nf r o mt h ew e be a s i l y s e a r c he n g i n ec o m e si n t ob e i n ga n dc o n t i n u e st og r o wa n dd e v e l o p h o w e v e r t h e r e s u l t so fs e a r c he n g i n e sw h i c hu s e r sc a l lv i e wa r ep r e s e n t e di nas i n g l er e s u l t a n da l e i s o l a t e db u tl a c k i n go fi n t e g r i t y s t i l lr e q u i r ea s s e m b l i n gt h ei n f o r m a t i o nm a n u a l l y a n d t h u so b t a i nac o m p l e t ei n f o r m a t i o n m e a n w h i l et h ei n f o r m a t i o nc o n t a i n e da m o n gt h e r e s u l t sh a sm o r er e d u n d a n c y e s p e c i a l l yt h et o po ft h er e s u l t sa l eg r e a t e r t h i sn e e d st o f i n da w a yo ft r y i n gt os o l v et h i sp r o b l e m t h i sp a p e ra n a l y z e st h er a n k i n ga l g o r i t h mo fe x i s t i n gs e a r c he n g i n e a n dt h e n o v e l t ym e t h o d sa m o n g t h er e s u l t sa n dm i n i m a ld o c u m e n ts e tg e n e r a t i o na l g o r i t h m w e c a ns e et h a tt h er e l e v a n tr e s u l t sw h i c ht h ee x i s t i n gs e a r c he n g i n er e t u r n st ot h eu s e r s h a v em o r er e d u n d a n c yb e t w e e nt h er e s u l t s a n dt h er e s u l t sa l es i n g l ea n di n f o r m a t i o ni s n o tc o m p l e t ee n o u g ht om e e tt h eu s e r s q u e r ys a t i s f a c t i o n s oi nt h i sp a p e r w eu s e d o c u m e n ts e tr e t r i e v a lb a s e ds u b t o p i ce x t r a c t i o nm e t h o dt oa s s e m b l et h er e l e v a n t r e t r i e v a lr e s u l t s a n dp r o p o s eac o n c e p t i n c l u s i o n w i t ht h ef o r m u l ae x p l a n a t i o n a n d m e a n w h i l ec o n s i d e rn o v e l t ya p p r o a c ha n dp r o p o s eac o n c e p t n o v e l t y w i t ht h e f o r m u l ae x p l a n a t i o n u s i n gt h e r e l e v a n c e i n c l u s i o n a n d n o v e l t y t or e r a n kt h e i n i t i a ld o c u m e n ts e t s w h i c he i i s u r et h a tt h et o po ft h ed o c u m e n tc o l l e c t i o n sd o n t d e b a s et h er e l e v a n c e a n dc o n t a i nm o r ec o m p l e t ei n f o r m a t i o na n ds m a l l e rr e d u n d a n c y a sf a ra sp o s s i b l e w ec o m p a r ew i t ht h ee x p e r i m e n t a lr e s u l t st od e t e r m i n et h et h r e ef a c t o r si nt h e a l g o r i t h m a f t e rt h a t w ec o m p a r er e s u l t so f t h ed o c u m e n ts e t sb a s e do nt h ef a c t o r sw i t h t h eo r i g i n a ld o c u m e n ts e t s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h eo v e r a l lr e l e v a n c eh a s i n c r e a s e da f t e ri m p r o v i n gt h ea l g o r i t h m w h i l et h et o po ft h ed o c u m e n tc o l l e c t i o na l s o h a sg r e a t e ri n c l u s i o nd e g r e ea n dn o v e l t yd e g r e e t h i sn o to n l ym e e t st h eu s e r sq u e r y r e q u e s t w h i l ea l l o w i n gu s e r s t og e tab e t t e rq u e r ys a t i s f a c t i o n k e y w o r d s d o c u m e n tc l u s t e r r e t r i e v a lr e s u l t ss e t i n c l u s i o n n o v e l t y h 一 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果 据我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他 人已经发表或撰写过的研究成果 也不包含为获得墨蕉堑太堂或其他教育机构的 学位或证书而使用过的材料 学位论文作者签名 别套渺签字日期 必f 年占月参日 学位论文版权使用授权书 本人完全了解墨蕉堑太堂有关保留 使用学位论文的规定 同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借阅 本 人授权墨蕉堑去堂可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或其他复制手段保存 汇编本学位论文 学位论文作者签名 弘v 夸出 导师签名 猴乏多浚 签字日期 沙i 年6 月g 日签字日期 幽f 年石月岔日 学位论文作者毕业后去向 工作单位 通讯地址 电话 邮编 第1 章绪论 1 1 研究背景及意义 第1 章绪论 1 1 1 搜索引擎的发展 在互联网发展初期 网站相对较少 信息查找比较容易 然而伴随互联网爆 炸性的发展 普通网络用户想找到所需的资料简直如同大海捞针 这时为满足大 众信息检索需求的专业搜索网站便应运而生了 现代意义上的搜索引擎祖先 是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发 明的a r c h i e a r c h i e 的工作原理与现在的搜索引擎已经很接近 它依靠脚本程序 自动搜索网上的文件 然后对有关信息进行索引 供使用者以一定的表达式查询 由于a r c h i e 深受用户欢迎 受其启发 美国内华达s y s t e mc o m p u t i n gs e r v i c e s 大 学于1 9 9 3 年开发了另一个与之非常相似的搜索工具 不过此时的搜索工具除了索 引文件外 已能检索网页 当时 机器人 一词在编程者中十分流行 电脑 机器人 c o m p u t e rr o b o t 是指某个能以人类无法达到的速度不问断地执行某项任务的软件程序 由于专门 用于检索信息的 机器人 程序象蜘蛛一样在网络间爬来爬去 因此 搜索引擎的 机 器人 程序就被称为 蜘蛛 程序 世界上第一个用于监测互联网发展规模的 机器 人 程序是m a t t h e wg r a y 开发的w o r l d 州d ew e bw a n d e r e r 刚开始它只用来统计互 联网上的服务器数量 后来则发展为能够检索网站域名 与w a n d e r e r 相对应 m a r t i nk o s t e r 于1 9 9 3 年1 0 月创建了a l i w e b 它是a r c h i e 的h r t p 版本 a l i w e b 不使用 机器人 程序 而是靠网站主动提交信息来建立 自己的链接索引 类似于现在我们熟知的y a h o o 随着互联网的迅速发展 使得检索所有新出现的网页变得越来越困难 因此 在m a t t h e wg r a y 的w a n d e r e r 基础上 一些编程者将传统的 蜘蛛 程序工作原理作 了些改进 其设想是 既然所有网页都可能有连向其他网站的链接 那么从跟踪 黑龙江大学硕士学位论文 一个网站的链接开始 就有可能检索整个互联网 到1 9 9 3 年底 一些基于此原理 的搜索引擎开始纷纷涌现 其中以j u m p s t a t i o n t h ew o r l dw i d ew e bw o r m g o t o 的前身 也就是今天o v e r t u r e 和r e p o s i t o r y b a s e ds o f t w a r ee n g i n e e r i n g r b s e s p i d e r 最负盛名 然而j u m p s t a t i o n 和w w ww o r m 只是以搜索工具在数据库中找 到匹配信息的先后次序排列搜索结果 因此毫无信息关联度可言 而r b s e 是第 一个在搜索结果排列中引入关键字串匹配程度概念的引擎 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月 当时m i c h a e lm a u l d i n 将j o h n l e a v i r 的蜘蛛程序接入到其索引程序中 创建了大家现在熟知的l y c o s 同年4 月 斯坦福 s t a n f o r d 大学的两名博士生 d a v i df i l o 和美籍华人杨致远 g e r r yy a n g 共同创办了超级目录索引y a h o o 并成功地使搜索引擎的概念深入人心 从此搜索 引擎进入了高速发展时期 目前 互联网上有名有姓的搜索引擎已达数百家 其 检索的信息量也与从前不可同日而语 比如最近风头正劲的g o o g l e 其数据库中 存放的网页已达3 0 亿之巨 随着互联网规模的急剧膨胀 一家搜索引擎光靠自己单打独斗已无法适应目 前的市场状况 因此现在搜索引擎之间开始出现了分工协作 并有了专业的搜索 引擎技术和搜索数据库服务提供商 象国外的i n k t o m i 已被y a h o o 收购 它本 身并不是直接面向用户的搜索引擎 但向包括o v e r t u r e 原g o t o 已被y a h o o 收 购 l o o k s m a r t m s n h o t b o t 等在内的其他搜索引擎提供全文网页搜索服务 国内的百度也属于这一类 搜狐和新浪用的就是它的技术 因此从这个意义上说 它们是搜索引擎的搜索引擎 l 1 9 9 5 年 一种新的搜索引擎形式出现了 元搜 索引擎 am e t as e a r c he n g i n er o u n d u p 用户只需提交一次搜索请求 由元搜索 引擎负责转换处理后提交给多个预先选定的独立搜索引擎 并将从各独立搜索引 擎返回的所有查询结果 集中起来处理后再返回给用户 第一个元搜索引擎 m e t a c r a w l e r 是w a s h i n g t o n 大学硕士生e r i cs d b e r g 和o r e ne t z i o n i 共同创立的 根据艾瑞咨询的2 0 0 9 年中国互联网市场年度总结报告 直至2 0 0 9 年中国搜索引 擎市场规模已突破6 9 5 亿人民币 相比2 0 0 8 年的5 0 3 亿元同比增长3 8 2 网民 中的9 5 都使用搜索引擎 7 1 随着网络信息量的快速增加 搜索引擎已经成为了 第1 章绪论 人们获取w e b 信息的基础设施 成为了除邮件之外的第二大互联网应用 2 3 1 1 2 目前搜索引擎存在的问题 据研究者统计 目前互联网上的搜索引擎己达数千种 仅中文搜索引擎就达 7 0 余种 在庞大的搜索引擎家族中 有囊括各学科 各种主题网络信息的综合性 搜索引擎 有以特定学科或专业领域的网络信息为收录对象的专业性搜索引擎 还有专门列举搜索引擎的搜索引擎指南 搜索引擎作为一个整体 存在着质量参 差不齐 信息的分类加工欠规范 搜索速度慢 死连接过多 以及提供的检索结 果中重复信息及不相关的无效信息过多等弊端 对检索效果形成负面影响 第一 搜索引擎对网络信息的覆盖率在整体上呈下降趋势 网络信息的急剧 增加 令以覆盖所有学科 所有类型信息为宗旨的综合性搜索引擎亦越来越难以 应对 就是号称功能最为强大的搜索引擎在网络信息搜索与加工软件的升级开发 上亦无法跟上网络信息的增长速度 尽管根据现有统计数据不能得出网络信息增 加速度与搜索引擎对网络信息覆盖面的递减速度之间的关系函数 而网上搜索引 擎对网络信息覆盖能力的明显萎缩却是不争的事实 随着网络信息资源呈几何级 数的增长 依搜索引擎在现有态势下对网络信息覆盖率的下滑速率可以推测 搜 索引擎对网络信息的覆盖率还将下降 这将严重影响到作为网络用户对信息的检 索效果 由于检全率与搜索引擎对网络信息的覆盖率有着必然的联系 因此随搜 索引擎对网络信息覆盖面的逐渐下降 用户对网络信息的检全率将首当其冲要受 到影响 第二 搜索引擎在网络信息的组织 加工等环节上缺乏可供操作的 统一的 技术标准 处于各自为政的无序状态 这主要体现在网络信息的分类上 统一的 网络信息分类标准的缺位令网络用户无所适从 他们被迫接受各搜索引擎的分类 体系无法兼容的事实 每使用一种新的搜索引擎就意味着他们必须接受该搜索引 擎与其他搜索引擎在分类体系上的差异 并且 搜索引擎在网络信息分类上存在 的问题还体现在较少考虑网络用户与传统图书馆的文献用户在利用信息时存在的 检索习惯上的关联性 即网络信息分类难于与图书馆文献分类兼容 通过网络信 黑龙江大学硕士学位论文 息分类目录 网络用户能够按类检索所需信息 信息之间依其内在的知识结构序 列 用户通过分类浏览即可一目了然 4 第三 目前各搜索引擎的返回结果数量巨大 其中包含了很多的不相关结果 用户不可能去浏览所有结果 有统计结果表明 6 5 旷7 0 的网民只会点击搜索结 果第一页的网页 即前1 0 条结果 2 0 0 2 5 的网民会去点击搜索结果第二页的网 页 即第1 1 2 0 条结果 而只有3 0 o 4 的网民会点击第二页以后的结果 5 1 各个 结果相互孤立而缺乏整体性 依然需要用户人工进行信息的组装 进而获得一个 完整的信息 同时结果之间包含的信息具有很大的冗余性 特别是排在前面的结 果冗余更大 1 2 搜索引擎排序技术 w e b 自出现开始 就采用h t m l 格式作为信息的基本表示格式 而搜索引擎 也是针对h t m l 格式的数据来实现搜索任务 从技术的发展过程和趋势来看 有 关搜索引擎排序的工作可以概括为3 类 6 1 1 以传统瓜技术为基础的内容分析 技术 2 基于信息发布者知识信息的技术 3 基于信息检索者知识信息的技术 1 2 1 以传统i r 技术为基础的内容分析技术 这类工作最有代表性的算法是 词频位置加权排序算法 7 1 i s 主要思想是判断 关键词与网页的相关度 按照相关度分值进行结果排序 而关键词在网页中的相 关度则由它在网页中出现的频次和位置 包括文本位置和h t m l t a g 位置 两方面 加权计算得出 这类方法的优点是简单 易实现 缺点是过于依赖词的重要性 而没有考虑网页的信息质量 对于一些为了提高搜索结果排名 恶意堆积关键词 的网页无法辨别 所以随着搜索引擎技术的发展 这种算法只作为搜索引擎的辅 助排序方法 不单独使用 6 1 2 2 基于信息发布者知识信息的技术 这类工作最有代表性的算法是 基于链接分析的p a g e r a n k 2 g 并4 h i t s 算法 3 1 第1 章绪论 g o o g l e 创始人之一p a g e 于1 9 9 8 年提出p a g e r a n k 算法 基本思想是通过网页 的质量来对搜索结果中的网页进行排序 这实际上是来自于科学引文索引的思想 在科学引文索引中 如果一篇文章被引用的次数越多 就认为该论文的学术价值 越高 同样 个网页质量越好 被其他网页引用的次数也就越多 就被赋予较 高的p a g e r a n k 值 最后根据p a g e r a n k 值对结果进行排序 k l e i n b e r g 的h i t s 算法 提出了一种更为完善的衡量网页重要程度的度量 是一种依赖于查询的主体精选 算法 提出了网页的权威性与集中性的概念 该算法指出 一个网页的权威性等 于链接向它的所有网页的集中性 而一个网页的集中性等于它指向的所有网页的 权威性 通过这两个值的不断迭代 得到稳定的网页权威性值 最终根据这个值 对结果进行排序1 6 与h i t s 相比 p a g e r a n k 只考虑了网页的权威性 而没有考虑集中性 除此之 外 p a g e r a n k 是一个静态算法 是全局重要性的度量 在用户查询之前事先计算 出所有网页的p r 值 所以权威度的计算只考虑链接关系 与用户查询词无关 这 也是它的一个缺点 而h i t s 是一个实时的动态算法 针对每一个查询 给出网页 针对于查询的权威度 但由于是对返回结果实时计算 所以h i t s 算法效率不高 这两种方法的优点就是都考虑了信息质量对于结果排序的重要性 但缺点在于 随着网络的发展 网页之间的推荐作用在下降 一些商业网站为了获得好的排名 互相链接 导致这些网页排在前面 与用户的需求毫不相关 另外 搜索引擎仅 从用户给出的几个关键字 往往很难判断出用户真实的查询意图 所以单纯从字 面上判断用户查询而给出搜索结果可能并不能完全满足用户需求 6 1 1 2 3 基于信息检索者知识信息的技术 由于每天会有数以万计的人与搜索引擎进行交互 从而产生大量有价值的反 馈信息 这些反馈信息对于信息检索系统十分重要 这类工作就是集中于利用用 户反馈信息进行结果排序 b r o d e r t 5 j 提出 用户的真实需求可以分为 n a v i g a t i o n a l 意图查找一个特定网 页 i n f o r m a t i o n a l 意图查找一些提供静态信息的网页 和t r a n s a c t i o n a l 意图查 黑龙江大学硕士学位论文 找可以进行交互的网页 三种 k e l l y 和t e e v a n l l o i 对隐反馈信息做出了综合概述 提出了利用隐反馈信息做相关性度量的思想 但是还没有应用于实际w e b 环境 j o a c h i m s i 提出了利用隐反馈信息代替人为判断的度量方法 介绍了一种基于点阅 数据信息对结果排序的技术 f o x e d l 2 研究了隐反馈信息和人为判断之间的关系 开发了 种贝叶斯模型 结合隐反馈信息和人为判断做相关性判断 这种模型在 点阅数据的基础上考虑了更多的用户行为 但这种方法重点考虑的是从隐含的用 户行为中预测出清晰的相关性判断 而没有更多地考虑排序方法网 考虑搜索引擎的用户很多时候并不会查看排在后面的结果 y i q u nl i u 1 3 提出 了基于点阅数据 搜索t o p 结果的方法 方法的思想是分析用户搜索日志 提取出 查询的点阅数据信息 提取出n a v i g a t i o n a l 类型的查询 然后寻找历史数据中点击 量最大的结果 标注为最相关结果 该方法的优点是从用户历史数据中 提取出 相关性判断 更符合用户需求 但缺点是只满足n a v i g a t i o n a l 3 0 需求的用户 而占有更大比例的用户是i n f o r m a t i o n a l 型 4 8 5 1 6 1 e u g e n ea g i c h t e i n 和e r i cb r i l l 提出1 1 4 1 5 1 为w e b 搜索用户的行为建立一个模 型 引入更丰富的用户浏览和交互特征 从而给出更好的排序结果 该方法的思 想是定义一些用户行为特征 采用机器学习的方法 训练一个分类器 为用户的 行为特征引入权重 从而导出一个用户偏好的预测模型 对于一个给定的查询 每一条查询结果都用特征描述 相对的用户偏好通过学习到的用户行为模型进行 预测 即给出更符合用户兴趣的排序结果 总体来看 通过聚集大量用户的行为 信息进行分析 可以满足用户的信息需求 比之前单纯基于点阅数据的方法有更 高的准确率和召回率 但对于n a v i g a t i o n a l 类型的查询 排序结果并没有之前单纯 基于点阅数据的方法好 可以考虑加入查询类型分类 对不同类型的查询 建立 不同的用户模型i 6 j 1 3 新颖性研究技术 上述部分的所有工作都是将网页作为独立个体来考虑的 没有将多个网页之 间的冗余性考虑进来 他们关注的都是单个检索结果的质量 即如何以每条结果 6 第1 章绪论 满足一次用户需求这样的形式返回给用户查看 而我们关注的重点是结果的组合 并集 但是我们在研究中为了度量这个组合的信息包含能力 在检索到相关结 果的基础上 就涉及到计算结果集内结果之间的关系 即结果间的新颖性 即冗 余程度 计算组合和查询之间的相关度 最重要的是 我们要利用现在国内外研 究中使用新颖性来判断结果间冗余程度的这个方法 对组合的新颖性 并集度进 行度量 所以在此我们对新颖性研究现状做个概述 各种新颖性发现的研究已经出现了很多 主要集中在两个不同的级别上 事 件级别和语句级别 1 3 1 事件级别上的新颖性发现 1 主题发现和跟踪 事件级别上的新颖性发现研究最先产生于主题发现和跟 踪研究中 此研究主要考虑的是在线新事件的发现 o n l i n en e we v e n td e t e c t i o n 和第一个故事的发现 f i r s ts t o r yd e t e c t i o n f s d 1 6 2 2 1 对于在线新事件的发现 主要是顺序处理一个在线新闻数据流里的故事 比较后面新到的故事和前面已经出现的故事 如果没有超过前面任何一个查询的 界值 就说明这个故事包含一个新的事件 2 t d t 第一个故事发现的任务是把每一个故事都做标记判断它是否是 第 一个 讨论新主题的故事 然后系统为每个故事给定一个分数 分数越高说明这个 故事是 第一个 故事的置信度越高 3 而现在对于新事件发现的技术通常都基于聚类算法 它主要解决两方面 问题 事件建模 其中可以用向量空间模型 语言模型以及语义链模型等等 事件聚类 此任务就是把每个故事都分别放到相应的聚类里 相应的标记上 一 个旧主题的旧故事 和 一个新主题的第一个故事 2 两级别机制的以主题为条件的第一个故事发现方法 f s d 2 3 此方法是 将新颖性发现问题分成两个阶段 1 使用一个有监督学习的算法把一系列在线 文档分别放到预先定义好的各个主题类别里 2 在每个主题里 对那里的文档 执行以主题为条件的新颖性发现 也就是说对每个主题执行传统的f s d 算法 同 黑龙江大学硕士学位论文 时 我们在事件级别的新颖性发现上也使用了指定实体 研究中使用b b n sh i d d e n m a r k o vm o d e ls o f t w a r e 提取7 种类型一般目的的实体 这样在第二阶段里 每篇 文档向量空间里既包含了词的权重 也包含了指定实体的权重 此方法的优点在于 其降低了每个主题里事件之间的混乱程度 因为它是按 照主题把文档进行分类并进行新颖性发现的 而且对文档的向量空间进行了修改 加入了指定实体特征 此方法的限制是需要预先定义主题的类别 并且对每个主 题还要有一个训练数据集 这使得在t d t 文集里是不适用的 3 多阶段新事件发现 n e d 系统 2 4 1 此系统是将各个故事分别分到相应的 分类里 并在每个分类里分别执行新事件发现 通过对传统n e d 模型进行修改 比如 对文档向量描述进行修改 对相似度机制进行修改等 结果证明 所做的 两个修改并没有增加计算时间 并且改进了性能 4 将自由文档向量和词汇链联合形成文档描述来描述一个事件的方法 2 5 1 此 方法中的文档描述混合了自由文档向量 使用传统的关键字索引条目 和一个使 用w o r d n e t 创建的词汇链 达到了最大性能的增加 其中应用我们熟悉的文档聚类 算法进行在线新事件发现和第一个故事发现 其中的相似度度量修改为 分别对 文档和聚类进行词汇链描述和自由文本描述两个向量空间的相似度计算 然后再 将结果进行线性组合 此方法的不足是 创建词汇链的时候依赖于w o r d n e t 来分析 这样 w o r d n e t 结构上的某些不足就会降低词汇链的描述 1 3 2 语句级别上的新颖性发现 在语句级别上的新颖性发现研究和t r e c 新颖性跟踪是相关的 首先给定一 个查询和一个已排好序的相关结果列表 目的就是在列表中找到既相关又新颖的 语句 2 6 2 引 在语句级别上的新颖性发现通常分为两个步骤 相关语句的检索和新 颖性语句的提取 在现有的新颖性发现技术中 我们会判断出现在相关语句中的 新单词 如果有 通常使这个语句获得较大的新颖性分数 进而作为新颖性语句 排在前面 在新颖性发现中也会应用很多相似度函数 通常一个语句和一个给定 第1 章绪论 查询词之间的相似度分数越高 越会增加这个语句的相关度排序 但是 如果一 个语句和出现在他前面的所有语句之间的相似度分数越高 则越会降低这个语句 的新颖性排序 几种常用的新颖性方法如下 1 新词数量度量 n e ww o r dc o u n tm e a s u r e 1 2 9 1 这是最简单的新颖性方法 即简单的计算出现在一个语句中新单词的数量 然后根据这个数量相应的给这个 语句一个分数 把它作为这个语句的新颖性分数 2 新信息度度量 n e wi n f o r m a t i o nd e g r e e n i d 3 0 1 此方法也是判断一个 语句和前面语句相比是否包含新的信息 定义为新信息度n i d 如果一个语句和 前面语句相比n i d 大于1 0 2 0 那么这个语句就作为新信息保留下来 n i d 的 度量方法有两种 第一种是一个语句中包含的前面语句没有出现的新单词的i d f 的 比值 第二种是 个语句中包含的和前面语句没有匹配上的b i g r a m 单词序列数量 的比值 3 基于重叠度的冗余方法 3 l 此方法是计算一个语句分别和前面所有语句所 重叠的单词的数量 然后利用这个语句的长度对这些数量进行标准化之后得到一 个数值 从这些数值中找到一个最大重叠值 作为这个语句的冗余分数 并且设 定一个冗余界值为o 5 5 所有冗余分数超过这个界值的语句都被看做是冗余语句 被去除 4 借助相似度函数进行新颖性发现 3 4 相似度函数有很多 比如说c o s i l l e 相似度 语言模型方法等等 在文献 3 2 中把语句用向量空间形式来描述 并且用 c o s i n e 相似度函数计算一个语句和前面出现的所有语句的相似度分数 用这个分数 来发现新颖性语句 相似度分数越大 说明新颖性越小 在文章 3 3 中引用了 3 4 中的最大边缘相关性模型 t h em a x i m a lm a r g i n a lr e l e v a n c em o d e l m m r 进行新 颖性发现 5 m m r 方法鲫j 它使用 相关新颖度量 来判定新颖性语句 此度量为 计 算语句和查询的相关性 然后再计算语句之间的新颖性 最后将两者线性组合起 来 即如果一个语句有很高的 边缘相关 那么这个语句不仅与查询相关 同时也 和之前选择过的语句有最小的相关 黑龙江大学硕士学位论文 6 使用语句中的论述实体 d i s c o u r s ee n t i t i e s 来判定新颖性 3 5 1 此方法不用 计算语句中新单词的数量 而是引用了论述实体的概念 论述实体都是一些语义 对象 在一个文本中他们有很多种造词实现 比如说 代名词 名词短语和一个 人名都应该属于一个单一实体 同时被看做相同的论述实体 依据这个论述实体 的意义 我们把前面所有语句所包含的论述实体形成一个论述实体历史列表 如 果在一个语句中发现了历史列表中不包含的新的论述实体 那么这个语句就被定 义为新颖性语句 同时把这些新论述实体加入到历史列表里 为后面语句判断使 用 7 使用语句中的新的命名实体和名词短语来判定新颖 3 6 如果一个语句中新 的命名实体和名词短语的数量超过一个预先设定的界值 那么此语句就被设定为 新颖性语句 这个方法是比较早的提出使用命名实体 n a m e de n t i t i e s 来分析语句 的 但是缺点就是所涉及的实体都很简单 8 基于信息模型的新颖性发现 3 7 娜 3 9 1 首先在研究中对新颖性给定了一个比 较完整的定义 把新的信息作为问题的答案 表达用户的需求和信息需要 根据 这个定义 研究中提出的基于信息模型的新颖性方法为 对用户的查询进行分 析 首先将主题分为 特殊主题和一般主题 然后确定能够回答这些主题的语句 里的信息模型的实体 根据主题类型和相应的信息模型 对检索到的语句依据 相应的算法进行排序 提取新颖性语句 本方法的优点是克服了以往新颖性发现方法中对于最初语句的检索状态和检 索质量的依赖 而是对语句中的信息模型进行了研究 确定和查询相关的命名实 体 改进了系统的性能 1 4 最小文档集合生成技术研究 传统的a d h o e 信息检索任务是根据与用户查询主题的相关程度对文档进行排 序的 实际上 每个查询主题并不都是单一的一层含义 通常都由很多不同的子 主题组成 所以一个相关文档可能仅仅覆盖了一个子主题的含义 更好一点文档 可能覆盖多个子主题 那么为了找到能够覆盖所需子主题的一组相关文档 用户 1 0 第1 章绪论 不得不浏览很多条文档信息 这是很费时的 尤其是相关文档并不一定按照子主 题进行排序 同时伴随在线信息的猛增 传统的取检索系统已经不能满足用户这 种求全检索的要求 迫切的要求系统能够帮助用户找到他们想要的完整信息 这 就需要把相关文档进行聚类产生文档集合 在文章 4 0 4 1 中使用和语义相关的聚类 方法来达到用户浏览文档集合的目的 而在文章 4 2 1 中产生的文档集合保证最大化 覆盖子主题的同时包含最少的冗余信息 最小文档集生成策略 就是试图生成一个具有一个最大覆盖并且最小冗余的 文档集合 例如 一个学生想要做一个关于 机器学习 的研究调查 他最感兴 趣的就是找到有关 机器学习 方法的文档 使用传统的检索策略 用户可能仅 仅查看到一些排序靠前的比较流行的 机器学习 方法 例如s v m 4 3 5 川和a n n l 4 4 1 5 l 等 如果用户想要查看所有方法就不得不翻页浏览更多的文档 所以 最小文 档集合的生成都是根据它包含了多少子主题 以及子主题的冗余情况来确定的 在文章 4 5 5 2 中提出了m m r 方法 它把查询词的相关性和文本检索中的信息新 颖性联合起来 共同计算文档之间的冗余 在文章 4 6 5 3 中针对这个问题提出了 一个子主题检索问题模型 在t r e c 6 t r e c 7 t r e c 一8 交互式跟踪中 提出了方 面检索策略 即研究交互式检索系统如何能够更好的让用户得到一个主题更多方 面的信息 4 7 4 8 4 9 1 5 4 5 5 5 6 1 最近的t r e c 问答跟踪中也提出了一个定义类型问题 要 求找到关于一个定义各个方面的信息 5 0 5 7 1 同时 在文章 5 l 5 8 中提出了基于 数据挖掘方法的图论和模糊集策略 它把文档集合根据语义联系创建了一个模型 此模型可适用于文本域和图像域 在m d s r l 4 2 1 中一共介绍了三种最小文档集合生成算法 第一种是基于新颖性 的方法 根据两篇相关文档之间的新颖性分数来产生文档集合 第二种方法是基 于聚类的方法 第三种是基于子主题提取的方法 此方法是从相关文档中去提取 子主题 然后用子主题作为查询来产生排序文档集合 本论文采用了第三种方法 的思想来生成文档集合 并在这个算法基础上进行了改进 同时 论文相关工作还涉及文档聚类技术研究 此技术通常被主体检测和跟 踪研究使用 5 2 5 3 1 5 9 6 0 1 包括基于模型的聚类 在线聚类等 这些都是把搜索结果 黑龙江大学硕士学位论文 聚类成文档满足用户的浏览 v i v i s i m o c o r n 州 就是这项技术的实际应用 1 5 相关工作的不足 目前已有的这些方法都是按照结果网页与查询词的相关性进行排序 而网页 与查询的相关性除了要判断网页内容与查询词的相关程度之外 还需要判断网页 内容本身与用户真实查询需求之间的相关度 而如果仅从用户的几个简单查询词 出发 则很难判断出用户的真实需求 这也是目前这些排序算法所解决得不够完 善的地方 它们都将网页作为独立个体来考虑 没有考虑多个网页之间的冗余性 和覆盖性 关注的都是单个检索结果的质量 即如何以每条结果满足一次用户需 求这样的形式返回给用户查看 并没有考虑信息的完整性 同时 即使进行了文 档聚类集合的研究 所产生的文档集合之间也仅仅考虑了和主题以及子主题之间 的相关性和覆盖性 文档集合之间的冗余性和新颖性并没有考虑 文档本身所包 含的信息程度也没有考虑 所以 针对搜索引擎的这个问题 研究把现有新颖性 的技术和方法应用到改进搜索引擎的结果质量上来 研究每个相关结果对于用户 来说具有多大的新颖性 那么把新颖结果放到一个结果组合里 力求达到所得结 果集的信息含量尽可能大 同时对于用户来说 满足一定的相关性和新颖性 1 6 本论文研究的主要目的和内容 自上个世纪9 0 年代出现以来 建立在因特网 i n t e m e t 之上的万维网 简称 w r e b 已经成为新经济时代分析和决策的重要信息源之一 是人类非常重要的信息 资源 它为全球信息服务发挥着不可替代的作用 因此 如何更好地开发 利用 w e b 上的信息资源 提供更加高质量的信息服务成为一个普遍关注和迫切需要解 决的问题 为了更好的满足用户的个性化搜索需求 在初始搜索引擎技术发展基础上 人们已经开发出多种技术 例如 对用户的查询需求进行外延理解 扩展查询词 提高搜索引擎的针对性 比如垂直搜索引擎的出现 对检索结果进行处理 去除 无关信息 更好对相关结果进行排序 提供更优化的检索结果等 信息检索虽然 1 2 第1 章绪论 取得了很大的进步 但是目前搜索引擎的搜索体验依然不能令人满意 主要存在 以下的几个问题 第一 返回结果数量巨大 其中包含了很多的不相关结果 第 二 结果孤立缺乏整体性 依然需要用户人工进行信息的组装 进而获得一个完 整的信息 第三 结果之间包含的信息具有很大的冗余性 特别是排在前面的结 果相互之间信息冗余度更大 本课题针对后两个问题开展研究工作 不仅考虑了查询词和返回结果之间的 相关性 同时也考虑了结果与结果之间所含相关信息的冗余关系 将结果间的新 颖性也作为一个考虑因素 即考察排在后面的结果在与查询词相关的基础上 其 内容与前面结果相比是否有冗余信息 是否包含新颖性内容 我们将冗余小新颖 性大的结果集排序靠前 这样用户不用点击大量冗余信息就能在靠前位置上快速 得到更多的有用信息 节省了时间 论文的主要研究问题将集中在如何从候选结 果集合中选取相关度高且信息含量大 冗余度小且新颖性大的结果集 将最佳的 结果集返回给用户 此集合既保证了满足用户的查询需求 又能给用户尽量提供 比较大的信息量 这种方法使得检索系统更加的人性化 用户进行更少次数的点 阅 就能找到自己想要的更完全的信息量 从而节省了用户的查询时间和精力 这对于w e b 用户来说很有实际意义的 1 7 论文的算法概述及结构 针对上一节中介绍的论文主要目的和内容 即本文要对结果进行集合 保证 用户的少点击次数多获得信息的查询需求 故本文利用基于子主题提取的文档集 生成算法生成结果组合 算法核心思想为 首先提取每个主题的子主题 然后把 子主题看成每个小主题 利用v s m 算法对相关结果进行从大到小排序 得到针对 每个子主题的相关结果列表 最后根据这些结果列表利用贪婪算法思想得到文档 集合 此算法的论述主要在第二章中进行 此算法虽然已经满足了结果集生成的 要求 但是返回给用户的结果集合的排序是按照聚类时产生的顺序 所以在第三 章中对相关结果集合进行重新排序 主要思想为 计算结果集合的平均相关度 并集度和新颖度 用这三个因子进行线性组合得到每个文档集合最后的分数 进 1 3 黑龙江大学硕士学位论文 而由大到小排序 所以在第三章中主要描述相关度 并集度和新颖度的计算方法 依据以上的概述 全文可分为以下几部分 第1 章绪论 介绍课题的研究背景和意义 提出了本文所要研究的主要目的 和内容 同时介绍问题的研究现状和相关工作 主要介绍了现有的搜索引擎排序 算法以及存在的问题 结合事件和语句新颖性研究算法 提出本文检索结果集算 法的优点 第2 章检索结果集的选取算法研究 此章节主要介绍结果集选取算法以及算 法的实现过程 第3 章相关结果集的排序算法研究 此章主要介绍了如何对所获得相关结果 集进行最后的排序 第4 章实验与结果分析本章介绍了实验所用数据集和评估方法 并对初始 算法和改进算法进行了实验比较 同时针对相关度 并集度和新颖度三个因子的 线性组合数值进行实验确定 结论给出本文研究结论 不足之处以及未来的工作方向 第2 章检索结果集的选取算法 第2 章检索结果集的选取算法 2 1 查询主题与相关结果的获取 为了实现本文算法和评估工作 我们设定了1 9 个查询主题 可从t r e c 主页 上的t r e c 一6 t r e c 7 t r e c 8 这三个实验数据集上获得 柏 5 5 1 查询主题样式如图 2 1 所示 同时对于每个主题 t r e c 又根据实例的描述从相关文档里确定出了多 个子主题 使之能够尽量的反映出主题所涉及到的各个方面 每个主题都大约有7 到5 6 个子主题 平均有2 0 个 例如 图2 1 所示的主题4 3 1 i 共有4 5 个子主题 图2 2 给出了该主题的前几个子主题 n u m b e r 4 3l i t i t l e r o b o t i ct e c h n o l o g yl a t e s td e v e l o p m e n t su s e i n s t a n c e s i nt h et i m ea l l o t t e d p l e a s ef m da sm a n yd f e 剐卧汀d e v e l o p m e n