论文部分内容阅读
近年来,数据挖掘领域中关于异质信息网络的研究受到越来越多研究者的关注。由于从现实世界中提取的大多数的图数据是异构的,人们花费更多的注意力在图数据中节点和边的多样性上,因此,异质信息网络上的重要概念――元路径承担着关键的作用。元路径是异质信息网络上的一个包含语义的重要工具,大量的数据处理依赖于有效的元路径。然而,在模式丰富的异质信息网络上,由于点的数量众多,类型繁杂,元路径难以通过人工设计得到。基于以上情形,我们研究了元路径挖掘问题,并提出了高效算法用来解决模式丰富异质信息网络中存在的这个难题。在简单异质信息网络中,本文探索了通过给定节点对生成具有最大相似度元路径的方法。首先,本文提出了一种基于网络模式的短元路径集挖掘算法――生成验证算法。此算法主要分为生成模块与验证模块两个部分,首先通过生成模块列举出所有的短元路径,然后在验证模块中通过路径限制随机游走筛选出具有最高关联度的元路径集。同时为了提高算法效率,本文提出了生成验证算法算法的改进算法,改进算法融合了生成模块和验证模块,在生成元路径的同时验证元路径的相关性,然后根据元路径的相关性又对生成模块进行剪枝,从而极大提高了算法的时间效率。然而在复杂异质信息网络中,网络模式往往过于巨大难以进行元路径挖掘。为了解决网络模式失效这一难题,本文构建了一种新颖的局部网络模式。此结构既有简单异质信息网络中网络模式的高效性和规模小的特点,又最大限度的存储了复杂异质信息网络的网络模式所蕴含的丰富信息。将此新型的数据结构替代复杂异质信息网络上失效的网络模式,极大提升了本文算法的效率。同时,为了应对节点多类型选择问题,本文总结了常用的异质信息网络节点相似性度量方法的缺点,设计了一个新颖的类型评价函数。通过对输入点对集的特殊性和支持度两方面考量,同时综合了前文提出局部网络模式的结构特点,提出了基于类型评分的元路径相似性度量方法。基于上文提出的类型选择方法和元路径相似性度量方法,本文在局部网络模式上设计了快速特殊路径挖掘算法,能从模式丰富的异构信息网络中自动提取有效的元路径。在新型局部网络模式和自动化类型选择的辅助下,问题的时间复杂度大大降低。借助于挖掘的元路径,能够在相似性测度、聚类、分类、链接预测、排名、推荐、信息融合等方面进行更深入的研究。该算法主要包括三部分:第一部分是关于局部层次化图的快速生成过程;第二部分是结合类型选择将生成的多个局部层次化图融合,生成上述新型的局部网络模式;第三部分则是在局部网络模式上的元路径快速挖掘方法。综合这三个过程,就构成了本文的最大相似度元路径挖掘算法。本文通过在Yago数据库和DBpedia数据库上进行大量的实验,对所提出的算法进行了详细评估。在各个知识图谱上的链路预测实验和聚类实验结果表明,此算法相较其他元路径挖掘算法不仅时间效率大大提升,同时精确度也有不同程度的提高。通过实验,可以得出本文算法具有高效与稳定的优点。