带权不确定图的K最近邻查询算法-计算机科学与技术专业论文.docx

万方数据 万方数据 上海海洋大学硕士学位论文 答辩委员会成员名单 姓名 工作单位 职称 备注 吴耿峰 上海大学 教授 主席 黄冬梅 上海海洋大学 教授 委员 贺琪 上海海洋大学 副教授 委员 王振华 上海海洋大学 副教授 秘书 答辩地点 信息学院 205 答辩日期 2015.6.5 3 上海海洋大学硕士学位论文 上海海洋大学硕士学位论文 带权不确定图的 K 最近邻查询算法 摘 要 在社会经济迅速发展的时代背景下，以生物技术、信息技术等为代表的高科技 产业取得了令人瞩目的成就，其成果广泛应用于社会各个角落。社会朝数字化、信 息化的方向发展，产生了大量的数据。由于归纳统计、隐私保护等原因，衍生出了 不确定数据。不确定数据结构复杂、数量巨大、表现形式多样。在生物技术领域， 需要进行实验计算的蛋白质的数量往往达到指数级，蛋白质间发生不同的化学反 应，蛋白质的形态各式各样，实验中通常需要寻找与指定蛋白质关系最密切的蛋白 质群；在移动通信领域中，持有手机终端的人数高达数十亿之多，设备的地理位置 不断变化，之间通过网络连接的通道方式不一，在两个设备之间寻找最便捷的通信 网路是该领域的关键应用；在虚拟社交领域中，注册用户产生的信息量巨大，信息 种类繁多且不尽真实，用户间互动产生的信息量繁杂浩大，用户经常需要查找与自 己关系最亲密的好友。因此，如何对复杂、海量、多样的不确定数据进行有效准确 的查询成为当前复杂网络亟需解决的问题。 在复杂网络中，图是一种良好的数据建模工具。随着数据中融入了不确定性， 对应的数据建模工具也由传统的确定图衍变为不确定图，不确定图是在图中加入 不确定因素。然而在当前的不确定图研究中，只是片面考虑边概率，而没有考虑边 的权重，这会降低不确定数据查询的准确度。以往不确定数据查询具体体现在生物 领域时，只考虑蛋白质发生化学反应概率而不考虑反应次数；在移动通信领域只关 心连接通路的可能性而没有考虑通信带宽的大小；在社交网路领域只考虑用户间 好友关系成立的概率却没有关注彼此互动的频率。因此本文给出了加入了权重变 量的不确定图定义。带权不确定图是一个包括权重和概率的四元组，兼顾了数据的 不确定性和权重因素，并把带权不确定图细分为不同的带权不确定子图，去除无用 的边，进一步明确图中顶点之间的关系，能够有效准确地存储复杂网络中的不确定 数据。 本文采用带权不确定图来存储复杂网络中的不确定数据，并针对复杂网络中 的不确定数据查询问题，提出了针对带权不确定图的 KNN 查询定义：GrapKDist I 查询。通过定义带权不确定图的路径步、源顶点层和层半径等概念以区分图中不同 顶点的关系；通过推导出两个查询定理：邻步定理和层次局部性定理，明确了查询 过程中 ProWeiDist 距离与路径步、源顶点层的联系。本文提出了实现 GrapKDist 查 询的 SubDistK 算法，并从准确度和效率方面对算法进行了优化。实例分析和实验 结果证明查询算法能够有效、准确地查询复杂网络的不确定数据。 本文主要创新点如下： 1. 针对复杂网络中的不确定数据，指出传统建模方式只考虑概率不考虑权重 的缺陷，提出了兼顾概率和权重的不确定图建模方式，实现了复杂、多样、海量的 不确定数据的有效存储； 2. 针对传统不确定图中顶点关系和距离不明确的问题，首次提出了带权不确 定图中的路径步、ProWeiDist 距离、源顶点层和层半径概念，区分了图中不同顶点 的层次关系，并给出了不同顶点的距离计算方法，实现了带权不确定图的简化； 3. 针对不确定数据在复杂网络中的查询难题，定义了基于带权不确定图的 K 最近邻查询，并给解决该查询的 SubDistK 算法。从实例分析和多组实验证明了算 法的准确性和高效性。 关键词：不确定数据，带权不确定图，ProWeiDist 距离，SubDistK 算法 II K-nearest Neighbors Query Algorithm in Weighted Uncertain Graph ABSTRACT Under the era background of social and economic rapid development, high-tech areas has made remarkable achievements and the results are widely used in every corner of society, which is represented by biological technology, information technology and so on. Society is developing in the direction of digitization and info