基于分布式计算的异构信息网络Top-k相关性用户偏好查询方法研究

发布时间：2014-12-26 12:24

 

【摘要】 我们生活在一个错综复杂的世界中,大部分的数据对象例如个体、组织或机构等都是互相关联和交互的,由此而形成了一个巨大的、互联的复杂网络。不失一般性,这种网络可以被建模成为信息网络。在现实世界中,信息网络随处可见,已经成为现代信息基础设施的重要组成部分。分析和挖掘信息网络或其中的某几种特殊类型的网络,例如社交网络、电子商务网络等,已经成为计算机科学、社会学等领域的研究人员广泛关注的课题。当前在信息网络上的研究按照信息网络的不同可以分为同构信息网络的研究和异构信息网络的研究。在同构信息网络上,代表实体对象的节点都属于同种类型,因而其上的边也仅包含一种含义,例如在朋友关系网络中,节点代表人,边则描述了两者之间的好友关系。至今在同构信息网络上已经有了很多有影响力的算法和应用,例如PageRank算法、社区发现等。但是现实中大部分网络都是异构的,也就是说节点属于多种类型,因而连接不同类型节点的边也蕴含着不同的语义信息。例如在由人人网构建的异构网络上,节点可能有个人、图片、电影、小组等,在人与人之间的边表示好友关系,而人与图片之间可能是浏览、转发,或者是加标签的关系。类似的例子随处可见,从社交媒体到科研网络、在线交易系统等,异构信息网络为真实世界中的各种对象交互行为提供了强大的抽象和描述能力,而其上蕴含的丰富信息也成为数据挖掘新的研究热点。至今已经涌现了很多针对异构网络挖掘分析的研究,相关性查询是异构信息网络上一个基本但很重要的操作,可以应用在诸如推荐、聚类、异常检测等多个领域。现有的异构信息网络上的相关性查询方法主要关注的是同种类型对象间的相似性的度量,本文提出了在异构信息网络上结合元路径选择与用户偏好的Top-k相关性查询的方法来度量不同类型的对象间的相关度。该方法是一个两阶段过程,首先用成对随机游走的思想,沿着给定的元路径计算初始的相关度,之后求解利用用户偏好建模的多目标线性规划问题,确定元路径的权重组合,据此更新初始相关度得到最终结果。此外,本文提出了多种方法来保证算法的效率,包括图划分、分布式矩阵运算和预物化等。最后通过实验度量本文提出的相关性查询方法的查准率、查全率以及计算用时等性能指标,结果表明本文提出的异构信息网络上的相关性查询方法可以有效、准确地实现查询要求。 

第一章绪论

本文提出的在异构信息网络上的top-k相关性查询方法，加入了对用户偏好的考虑，一方面满足对用户的个性化查询的需要，另一方面，通过将用户偏好建模，来获得不同元路径的权重组合，实现优化查询结果的目的。此外，在算法实现阶段，考虑到现有方法的效率问题，提出了图划分和分布式计算两种解决方案。图划分方法是指利用现有的图划分方法将异构信息网络划分为多个子网络，利用剪枝的思想，只针对与源节点在同一子图中的目标节点进行计算，从而减少计算量。剪枝可能导致查询结果准确率的降低，笔耕文化推荐期刊，是一种以准确率换取效率的方法，这种方法可以在某些对准确率要求不高、但是要求实时完成的任务中使用。而分布式计算方法是指将成对随机游走的思想转化为矩阵的运算，通过分布式的矩阵的乘法和规范化计算来实现。虽然矩阵的运算效率可以大大提高，但是矩阵的物化存储又成为一个新的问题，对此本文也有相应的描述和研究。在本文中，针对准确性要求较高的任务，将釆用矩阵分布式计算的方法来进行相关性查询，而对实时性要求较高的任务则采用在划分子图上进行分布式计算的方法来实现，实验结果表明相关性查询方法和分布式计算的加速算法的有效性。
..........

第二章相关研究

2.1引言
信息网络上仅存在两种类型的节点。利用信息网络特别是异构信息网络表示现实中实体对象及其之间的联系后，可以充分利用现有的图相关算法进行挖掘，而且对边上存在的潜在的关系语义实现更深入的挖掘利用。目前信息网络的数据挖掘和知识发现工作己经被广泛的研究，传统数据挖掘的算法如聚类、分类、排序、社区发现、关系预测以及异常检测等有许多已经成功应用到信息网络上来。异构信息网络上的相关性查询，主要是针对输入的源节点，在特定某种类型的目标节点中查找与其最相关的个，通过对网络和问题的有效建模，实现准确高效的相关性查询。异构信息网络上的相关性查询是诸多应用的关键所在，对后续的诸如社区发现搜索、推荐，、网站图片自动加标签等工作具有十分重要的应用价值和现实意义。目前，国内外专家学者已经对信息网络的数据挖掘和知识发现工作展幵了广泛的研弁，而信息网络上的相关性查询工作也有了初步的发展。根据已有的研究成果，在信息网络上，用相似性的概念来度量同种类型对象间的相近程度，而相关性则表示不同种类型对象间的相近程度。已有的相似性或相关性度量的定义方法是基于元路径或者受路径实例约束的，通过沿着这些给定的元路径或路径实例，结合成熟的图上的游走思想进行定义和计算。由于异构网络上存在多种类型的节点对象和蕴含着丰富潜在语义的边关系，可以代表极其复杂的实体联系，使得其上的相关性查询工作更具有普遍意义，同时也增加了查询的难度。

2.2信息网络上的相关性查询研究
总体来说，在同构信息网络上的相似性查询有两种思路：一种是利用图节点间的连接关系进行迭代计算确定二者之间的相关性；另一种是利用节点的共同邻节点来进行度量。其中，使用连接关系计算的方法可以看做是图上的随机游走即从查询节点幵始，模拟用户的随机访问顺序在同构网络上进行随机的游走，计算某点的可达概率。这种方法通常面临着处理大规模矩阵运算的问题，导致实时性较差。而利用节点的共同邻节点进行相关性的度量，每次仅能确定一条边的两个节点间的相关性，而对不邻接的节点则无法度量。总而言之，在二分网络上的相关性查询算法不管是基于迭代思想还是随机游走的方式，已经开始出现异构网络上存在的效率问题了。而且，二分网络在描述现实世界中实体对象间的联系上表达能力远不如异构信息网络。总之，异构网络因为其包含的相比较于同构和二分网络更加丰富的语义和连接信息，使得其上的挖掘更具有实际的应用价值。目前的异构网络上的相关性度量的计算方法都是基于元路径的随机游走思想，效果虽好但是效率低下，也已有研究关注于效率问题，将在下一小节进行阐述。

第三章结合元路径与用户偏好的top-k相关性查询方法.....17
3.1异构信息网络的定义...................17
3.2问题定义和方法框架...........19
3.3基于元路径的相关性度量的计算..........20
第四章相关性査询方法的加速算法....26
4.1概述............26
4.2基于图划分的查询加速算法...........27
第五章实验分析.....35
5.1实验环境和数据集..........35
5.2方法的性能分析....36
5.3元路径的长度对结果的影响分析.....37
5.4图划分前后效率和效果的分析.............39

第五章实验分析

5.1实验环境和数据集
实验首先用算法计算得到原始的相关性度量的值，得到一个矩阵，每一行都沿着相对应的元路径计算得到的相关度，每一列表示对应的电影在给定的四条元路径下做成对随机游走计算得到的与源节点的相关性度量的初始值。根据公式，将通过历宋数据分析得到的用户偏好建模成为一个多目标线性规划问题并求解得到一个四维的行向量作为对应的四条元路径的权重。

5.2方法的性能分析
也就是说并不是与源节点的该流派下的电影所属的其他流派下的其他电影也属于源节点的流派，比如很多电影属于爱情类，但是爱情类的电影有的是轻松幽默的喜剧，有的则是惊悚剧。元路径长度影响相关性查询结果的准确率是有原因。一方面，在异构信息网络上，不同的元路径蕴含不同的语义信息，可能某两种类型的节点间的连接关系强度强于该节点与另外类型的节点间的关系强度，比如在5.1节末的例子中，电影与流派之间的关系强度就强于电影与观影人群的关系强度；另一方面，直观上来说，如果从源节点出发到达目标节点要经过的步数越多，二者之间的相关度越低。本章基于两个数据集进行了相关性查询的实验，首先介绍了和数据集的网络模式和由此构建的异构信息网络的规模，之后从多方面对基于本文提出的相关性查询的方法进行实验。实验首先从准确率、召回率和值三方面对比分析了本文提出的相关性查询方法与已有方法的效果，之后展示了元路径长度对结果的影响，接下来对本文提出的加速方法的可行性作了对比实验。一系列的实验结果表明，本文提出的方法能够有效地提高异构信息网络上相关性查询的准确度和效率。
...........

第六章总结展望

异构信息网络上的相关性査询可以用于多种应用中，例如商品推荐、搜索以及自动添加图片标签等工作。目前在异构信息网络上的相关性査询的研究还处于初级阶段，主要是使用基于元路径的成对随机游走的思想，效率较低，且使用的元路径来自于历史经验或者专家推荐，一次只支持一条元路径的计算，准确率也不够理想。本文针对异构信息网络上相关性查询中存在的问题进行研究，主要研究成果如下：提出基于多条元路径下相关性度量的计算方法，并给出根据用户偏好确定元路径权重组合的方法。一方面整合了多条元路径的计算结果，另一方面充分利用了用户容易输入或通过对往期用户历史数据的挖掘易于获得的的用户偏好信息。通过将用户偏好建模成为一个多目标线性规划问题，釆用遗传算法求解确定元路径的权重组合，并据此更新获得的初始相关性度量的值。在頂和数据集上的实验结果证明通过多条元路径的组合进行相关性计算后得到的结果的准确性更高。

..........

参考文献：

[1] 于潇.  基于J2EE框架和XML建模的人力资源数据分析与展现平台架构设计与实现[D]. 山东大学 2014
[2] 黄亮.  税务海量数据仓库的设计与优化[D]. 山东大学 2014
[3] 郭亚宁.  基于哈希编码的文本拷贝检测算法优化与实现[D]. 山东大学 2014
[4] 严冲.  石家庄联通社区经理服务满意度调查系统设计和实现[D]. 山东大学 2014
[5] 许宁.  移动通信网络性能管理系统的设计与实现[D]. 山东大学 2014
[6] 姜飞.  基于加权异构信息网络的多维文本数据分析技术研究[D]. 山东大学 2014
[7] 庄绪良.  智能照明统计分析子系统的设计与开发[D]. 山东大学 2013
[8] 张静.  信息网络多维分析方法的研究[D]. 山东大学 2013
[9] 邢磊.  基于STRUTS框架的社会保险网上查询系统的数据库设计与实现[D]. 山东大学 2013
[10] 张冬兵.  胜利农村合作银行计算机设备管理系统的设计与实现[D]. 山东大学 2013



本文编号：10894