异质网络数据挖掘研究综述

目前，已有研究者在异质网络上开展了几种数据挖掘任务的研究，例如，基于排序（ranking-based）的聚类、分类方法［6，7，9，10］。 2011年，Sun等人首次提出了基于元路径的异质网络挖掘框架，给出了一个基于元路径的相似性度量，该度量通过指定不同路径反映异质网络中隐含的语义信息，并在该框架上实现了top-k异质网络的同类元素间的相似性查询［4］。之后，Shi等人对异质网络相似性查询问题进行了扩展，实现了不同类型元素间的相似性查询［12］ 。 2012年，Sun等人又针对异质网络聚类问题，设计了基于元路径的聚类算法［8］。2012年，Kong等人设计了基于元路径的异质网络分类算法［11］。此外，Sun等人提出基于元路径的异质网络关系预测［13］。此外，异质数据网络在现实中存在越来越普遍，并且形式复杂多样，涉及的领域也很广泛，新的挖掘需求不断出现。例如，研究大数据环境下异质网络上的相似性查询、相似性连接（similarity join）［16，17］、特异群组挖掘［18，19］等挖掘任务。

相似性连接任务是一项具有广泛应用的重要分析任务，这方面已有大量研究工作。文献［16］（2011年）和［17］（2013年）指出了网络数据上的相似性连接任务的重要性和广泛的应用领域，如相似网页检测、实体解析、数据清洁、链路预测和相似文献检索等。早期研究是在空间数据库中返回满足指定相似性阈值最相似的数据对或前k个数据对（top-k相似性连接），通常采用欧式距离度量对象间的相似性［21］。最近，更多的相似性连接研究集中在集合（set-）［22］和字符串（String-）[23］上，相似性度量通常用海明距离、编辑距离或Jaccard相似性度量。然而，关于网络的相似性连接工作很少。Silc-Join［24］和Distance-Join［25］分别研究了路网和图模式匹配的相似性连接问题，采用最短路径距离。2011年，Sun等人研究了网络上的相似性连接问题［16］，采用了基于连接（link-based）相似性度量（PPR和SR）。前已述及，PPR和SR忽略了异质网络中的不同路径蕴含的语义信息。此外，LS-join采用迭代计算模型计算PPR和SR，该方法对于大规模的网络不是有效的。2013年，Zheng等人提出了针对图的基于SimRank的相似性连接算法（SRJ）［17］，然而该方法仍采用SR作为相似性度量，该度量不能抓住不同路径下的语义信息。上述研究都没有考虑异质网络特征，没有考虑蕴含的语义信息，因此有必要在异质数据网络上开展相似性连接问题的研究［18］。

前已述及，特异群组挖掘的目的是发现数据集中明显不同于大部分数据对象（不具有相似性）的数据集合。但是，异质数据网络上的特异群组特异性度量更加复杂，需要在异质数据网络上设计与实现特异群组挖掘算法。(www.xing528.com)

另一方面，大数据环境下，挖掘算法的效率是十分重要的。由于异质数据网络挖掘研究目前仍处于起始阶段，主要集中在探究新的准则和方法以保证挖掘结果反映异质网络隐含的语义信息。具有代表性的是异质网络中基于元路径的相似性度量的提出［4］，但是也存在几个问题：①基于该度量的相似性查询方法［1］难以满足大数据集上的实时快速响应的查询需求；②相似性连接任务虽然可以离线完成，实时响应不是第一需求，但相似性连接涉及的计算量庞大，设计高效的相似性连接算法也很重要；③在异质数据网络特异群组挖掘方面，该任务是挖掘少部分对象形成的特异群组（具有低密度高价值的数据特性），效率上的考虑是关键，要求设计有针对性的算法优化策略。