top2-k查询：一种top-k查询结果简化查询算法

摘要

随着网络的普及，越来越丰富的网络服务如雨后春笋般呈现在人们的视野中。这些服务以方便用户为宗旨，然而随着服务提供给用户的信息以爆炸式的方式呈现给用户，用户很难方便快捷的得到满意的信息。即使使用用户查询约束，在如今的网络大数据时代仍然不能够准确的给用户提供信息。以网上预订旅馆为例，虽然用户能够在网上根据搜索条件搜索出很多的旅馆信息，但是，网络上提供的各种旅馆信息多而杂，如何帮助用户更好的选择最适合自己的旅馆显得尤为重要。top-k查询是解决该问题的一种重要的数据挖掘方法。根据调查，目前，安居客、携程等知名网络公司均使用top-k给注册用户提供个性化推荐。但是目前的top-k查询在解决这类问题时包含了一个不容忽视的缺陷，它忽视了旅馆的利益，将旅馆推荐给了非潜在用户，同时增加了用户的选择困难。在推荐旅馆时如何避免将旅馆推荐给非潜在用户是一个亟待解决的问题。
　　为了解决上述问题，首先，本文在传统的top-k查询基础之上定义了多用户偏好的top-k查询，该查询根据用户不同的用户偏好，给出用户定制的top-k查询结果，满足用户查询结果多样化需求。针对该查询问题，从不同的角度，给出了两种多用户top-k查询的算法:VBA算法和 LBA算法。并通过理论论证这两种算法的正确性与完备性。
　　其次，针对上述问题，给出了top2-k查询的形式化定义，并给出了解决top2-k查询三个算法。基于多用户偏好top-k查询算法给出了WTop2-k算法与STop2-k算法。并在给出上述两个算法后，针对固定数据集，给出了优化查询算法OTop2-k，该算法对查询效率进行了优化， 降低了查询时间。
　　最后，针对基于多用户的top-k查询以及top2-k查询进行了实验。通过IBM的数据生成器给出了可靠的模拟数据。在多用户的top-k查询实验中，针对不同维度的数据进行了多组k值不同的实验。实验表明，多用户偏好的两个查询算法VBA算法及LBA算法查询效率理想。在top2-k查询查询的实验中，针对二维情况，做了不同k值得多组实验，结果表明，优化算法OTop2-k的效率优于算法WTop2-k及算法STop2-k。
　　本文在传统的top-k查询的基础之上定义了多用户的top-k查询，并提出解决该查询的两个查询算法，即VBA算法和LBA算法，理论论证了其正确性与完备性，实验结果表明，VBA算法及LBA算法的查询效率高。在多用户的top-k查询的基础上提出了top2-k查询，并给出了两种方式的top2-k查询算法，即先从用户的角度进行top-k查询的WTop2-k算法与先从旅馆的角度进行top-k查询的STop2-k算法。为了提高top2-k查询的查询效率，提出了优化算法OTop2-k。对优化算法OTop2-k做了正确性和完备性的理论证明并进行了实验，结果表明，算法OTop2-k与算法WTop2-k和算法STop2-k相比在查询效率方面有了很大提高。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景和意义

1.2 研究内容

1.3 国内外研究现状及发展动态分析

1.4 本文组织结构

2 数据挖掘相关基础知识

2.1 数据挖掘简介

2.2 数据挖掘无法解决的问题

2.3 数据挖掘与数据仓库

2.4 数据挖掘与OLAP

2.5 数据挖掘与机器学习以及统计

2.6 数据挖掘应用

2.7 本章小结

3 top-k查询

3.1 传统的top-k查询基础知识

3.2 多用户的top-k查询基础知识

3.3 本章小结

4 top2-k查询算法

4.1 top2-k查询的定义

4.2 top2-k查询算法

4.3 本章小结

5 实验与分析

5.1 多用户top-k查询实验与分析

5.2 top2-k查询分析

5.3 本章小结

6 总结与展望

参考文献

攻读硕士学位期间的研究成果

致谢