最大和网络搜索结果多样性问题及其贪婪策略分析

摘要

随着网络技术的迅猛发展，网民人数的不断增多，互联网资源库中的信息也在呈指数倍地上涨，搜索引擎作为人们在海量信息中获取有效信息的重要检索工具正在受到越来越多人的青睐。在实际检索过程中，用户体验到搜索引擎带来的便捷的同时，也感受到了大量无效信息所带来的困扰，用户常常需要在庞大的结果集合中对信息进行筛查、选择或者细化检索内容，才能定位到自己感兴趣的信息。一方面，由于用户在关键词的“输入长度”、信息结果的“浏览长度”等方面具有“懒惰性”，利用关键词对所需信息进行查询时，用户往往通过给定较少的关键词，要求搜索引擎在结果的前几页显示自己所需信息。另一方面，关键词本身具有广泛的语义、搜索系统一次呈现结果存在数量上的限制。因此，系统常常不能快速地呈现用户的真实需求，返回多而繁杂的搜索结果集不仅耗费了用户大量的时间，还降低了用户的搜索效率。
　　论文从提高搜索引擎效率，提高用户检索满意度的角度，考虑了不仅产生同搜索关键词相关，而且各个结果之间最好应具有能够覆盖关键词多个意义的网络搜索结果呈现问题，给出了该问题的贪婪策略，分析证明了贪婪策略具有的近似性能比。论文的主要研究工作如下：
　　1、本文从搜索结果集合的相关性和多样化两个角度出发，建立了搜索结果多样性问题的数学模型。通过对问题模型的求解分析，得出该问题的算法结果集合，并将其与问题的最优结果集合进行比较，证明策略的有效性。同时，分析了余弦距离相似度条件下搜索结果多样性问题的近似性能比。
　　2、用户往往是通过对搜索结果集合进行筛选而寻找到所需信息，对信息的筛选就是浏览信息的过程，浏览量越多，结果集合同关键词的总体相关性就越高，但每条信息给用户带来的边际满意度随之而降低。针对这一情况，运用非负的单调次模集合函数度量搜索结果问题的相关性，在此基础上建立数学模型，设计了贪婪策略，研究了单调次模情形下的网络搜索结果多样性问题，分析证明贪婪策略具有较好的近似性能比。
　　3、在日新月异的网络信息世界中，不同的时间点用户对同一关键词的信息需求可能会不一样。为了满足用户不断变化的信息需求，本文将通过对静态结果集合中元素的调整，研究信息具有动态性特征的网络搜索结果有效呈现问题。
　　4、为了验证策略的有效性，我们根据近似思想对其进行了仿真实验，实验结果表明，贪婪算法具有很好的理论近似比。
　　本文的分析及结论丰富了现有的搜索结果多样性问题的研究，为相关问题的进一步深入探索奠定了理论基础，对实际搜索结果多样性问题具有一定的理论指导意义。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景及意义

1.2 相关文献综述

1.3 论文的主要工作

1.4 论文的主要研究方法和研究框架

第二章 最大和搜索结果多样性问题建模

2.1 最大和搜索结果多样性问题的基本模型

2.2 最大和搜索结果多样性问题研究的相关引理

2.3 本章小结

第三章 基本模型的贪婪策略设计与分析

3.1 基本模型的进一步分析

3.2 贪婪算法与近似比分析

3.3基本模型下最大和搜索结果多样性问题的一般性应用

3.4 基本模型下最大和搜索结果多样性问题的算例分析

第四章 单调次模度量相关性的最大和搜索结果多样性问题分析

4.1 单调次模函数相关性质

4.2 单调次模函数相关性条件下问题的模型及分析

4.3 单调次模函数表征问题相关性的两个应用

4.4 本章小结

第五章 动态更新情形下最大和搜索结果多样性问题分析

5.1 动态更新情形下最大和搜索结果多样性问题的目标

5.2 更新规则

5.3 动态更新下的最大和搜索结果多样性问题的理论分析

5.4 动态更新下最大和搜索结果多样性问题的仿真分析

5.5 本章小结

第六章 结论与展望

6.1 论文主要工作及结论

6.2 有待进一步研究的工作

致谢

参考文献

攻读硕士学位期间取得的成果