排名算法性能优化研究

摘要

无论在现实生活中，还是在虚拟网络上，当用户需要从大量候选对象中找出那些价值比较大的对象时，如果依靠人工一一查看、分析、识别，工作量会非常巨大，这就需要借助算法对这些对象进行排名，这样即可在很短的时间内将那些比较有价值的对象返回给用户。例如，Web搜索列表排名、热点人员发现排名等。根据排名对象的不同，可将目前的排名算法分为关于一般对象的排名算法和关于人员对象的排名算法两类。另外，按照排名方式的不同，每种对象排名算法又可进一步分为两类:直接排名算法和融合排名算法。直接排名算法通过对数据对象进行直接访问和计算，最终得到一个排名结果。融合排名算法通过将多个排名列表融合为一个综合列表进行排名，得到一个最终排名结果。虽然关于不同对象的排名研究引起了研究者的广泛关注，但在不同应用场景下，仍存在一定的研究空间，本文针对如下问题展开研究:针对一般对象:直接搜索应用中的直接排名算法因没有有效利用图上的某些结构特征，影响了算法的排名效率;联合搜索应用中的列表融合排名算法因忽视了对列表可信度有效考量，影响了列表融合的质量;针对人员对象:热点人物发现应用中的直接排名算法由于忽视了图上某些关键信息的作用，影响了算法的排名质量;投票选举应用中的融合排名算法由于没有区分不同排名信息的可信度，影响了投票列表融合质量的进一步提升。为了达到提高排名质量和排名效率的目的，就需要对现有算法进行各方面的性能优化。在本文中排名效率方面的优化或排名质量方面的优化均称为排名方面的性能优化。为了实现对排名算法的优化，除了需要充分利用图中的多种特征和信息外，还需要全面地度量不同类型的可信度。因此关于一般对象的排名，针对直接搜索和联合搜索这两种应用场景中的排名问题本文分别提出了:基于强连通分量的网页排名高效方法和基于列表可信度的列表融合方法;关于人员对象的排名，针对热点人物发现和投票选举这两种应用场景中的排名问题本文分别提出了:综合多因素的人员影响力排名方法和基于排名可信度的投票列表融合方法。 由上可知，本文的工作内容主要包括以下几点: (1)基于强连通分量的网页排名高效方法。 在这一部分中，基于图上的强连通分量SCC(Strongly Connected Component)子图，分析并利用SCC在网页排名计算中所表现出的特点和性质，提出了一种基于强连通分量SCC的高效优化算法。在算法的研究过程中，通过提出严格的理论基础，为这些算法的正确性提供了强有力的保证。另外，在分析总体规律的同时，也讨论了具体情况下的优化处理措施，全方位地提高了算法的效率。 (2)基于列表可信度的搜索列表融合方法。 本部分致力于将由多个检索系统返回的多个不同列表融合为一个更加可信的综合列表。由于不同的检索系统，因其底层数据及排名算法的不同，必然导致它们所返回的排名列表质量不同。因此在融合多个列表时，对于那些排名质量高的列表所给出的排名信息，应更加予以采信。基于此，本部分致力于在多列表融合过程中无监督地度量出每个列表的可信度，使得高可信度的列表所给出的排名在综合排名时发挥更大的作用，从而达到有效提高列表融合质量的目的。 (3)综合多因素的人员影响力排名方法。 和以往的排名算法不同，本部分在考虑结点间关系的同时，将综合考虑那些反映人员对象自身重要性的信息，从而使得某个人员的排名结果不仅仅依赖于其外在关系（其他结点对它的认可）所反映出的社交能力，也依赖于其自身信息所反映出来的业务能力，从而使得排名结果更全面地反映出人员的综合重要性，有效提高了排名结果的排名质量。另外，在度量人员自身实力时，还考虑了时间信息，度量了人们随着时间的流逝所引起的主观认知方面的遗忘衰减作用的大小，使得排名结果能够更加准确地反映出在某个特定时间下的人员综合影响力的排名情况。 (4)基于排名可信度的投票列表融合方法。 本部分针对一种特殊的列表:投票列表，提出一种将众多投票列表融合为一个综合投票结果列表的算法。在融合众多投票列表时，不同的投票人由于其文化背景和综合能力的不同，导致其所给出的投票列表的可信度也不同;另外，即使在同一个投票列表中，由于投票人对候选人的“了知度”的不同，导致同一个投票列表中关于不同候选人的排名信息的可信度也不同。本部分提出的算法，不仅无监督地度量了每位投票人的可信度，也度量了每位投票人对每位候选人的“了知度”，并依据这些数据得到每条排名信息的可信度。在融合众多投票列表时，更加采信那些高可信度、高了知度的排名信息，从而提高了投票列表融合的质量。 总之，本文致力于为用户提供更加满意的排名服务，这就需要从各个角度对现有算法进行优化研究。在排名对象上，本文不仅提出了针对一般对象的排名，也提出了针对人员对象的排名。在应用场景上，本文分别针对直接搜索、联合搜索、热点人物发现和投票选举四种应用场景，分别分析了这些应用中各自需要解决的排名问题，并提出了相应的算法。在排名方式上，分别研究了直接排名和列表融合两种排名方式。本文提出的这些算法从不同角度有效提高了列表排名的效率和质量。

目录

声明

摘要

1．1研究背景和意义

1．2国内外研究现状

1．3本文的研究内容

1．3．1现有排名算法面临的问题和挑战

1．3．2本文主要研究内容

1．3．3不同研究内容间的内在逻辑关系

1．4本章的组织结构

第二章基于强连通分量的网页排名高效方法

2．1引言

2．2预备知识及基本概念介绍

2．2．1网页排名PR

2．2．2强连通分量SCC

2．3基于强连通分量的网页排名算法

2．3．1基本概念和标识符号

2．3．2基于强连通分量SCC的SBPR算法

2．3．3基于强连通分量SCC的ASBPR优化算法

2．3．4 ASBPM与PBPM的对比分析

2．4实验

2．4．1实验环境和实验数据集

2．4．2算法的准确度

2．4．3算法效率的对比分析

2．4．4小结

2．5本章总结

2．6本章附录

第三章基于列表可信度的搜索列表融合方法

3．1引言

3．2问题定义

3．3多列表融合排序算法MC

3．4基于列表可信度的多列表融合算法FPM

3．4．1列表可信度向量C的计算

3．4．2元素相关度向量P的计算

3．4．3算法FPM

3．5实验

3．5．1实验环境和实验数据集

3．5．2算法的准确性

3．5．3算法的时间效率

3．5．4小结

3．6本章总结

第四章综合多因素的人员影响力排名方法

4．1引言

4．2人员影响力评估模型

4．3业绩重要度评估模型

4．3．1业绩对象所属类别的权重计算

4．3．2业绩对象在所属类别中的重要性计算

4．4时间衰减作用度量评估模型

4．4．1业绩对象的留存度计算

4．4．2业绩对象留存度的优化计算

4．5人员影响力排名算法

4．6实验

4．6．1实验环境和实验数据集

4．6．2对外界变化反应更敏锐

4．6．3对人员排名反映更全面

4．6．4对各种应用适用更灵活

4．6．5小结

4．7本章总结

第五章基于排名可信度的投票列表融合方法

5．1引言

5．2标记符号和投票系统

5．3 BC算法和STV算法

5．4排名可信度的含义及其影响因素

5．5基于名次信息可信度的列表融合算法

5．5．1名次了知度及投票人可信度的计算

5．5．2基于名次信息可信度的列表融合排名

5．6基于距离信息可信度的列表融合算法

5．6．1距离了知度及投票人可信度的计算

5．6．2基于距离信息可信度的列表融合排名

5．7实验

5．7．1实验环境和实验数据集

5．7．2算法的准确度

5．7．3参数取值对算法准确度的影响

5．7．4小结

5．8本章总结

第六章结论

6．1本文的主要贡献与结论

6．2进一步的工作

参考文献

致谢

攻博期间发表的论文

攻博期间参与的项目

作者简介