基于FSG的最大频繁子图挖掘算法*

图挖掘已成为数据挖掘领域研究的热点,然而挖掘全部频繁子图很困难且得到的频繁子图过多,影响结果的理解和应用。可通过挖掘最大频繁子图来解决挖掘结果数量巨大的问题,最大频繁子图挖掘得到的结果数量很少且不丢失信息,节省了空间和以后的分析工作。基于算法FSG提出了最大频繁子图挖掘算法FSG-MaxGraph;结合节点的度、标记及邻接列表来计算规范编码,提出两个定理来减少子图同构判断的次数,并应用改进后的决策树来计算支持度。实验证明,新算法解决了挖掘结果太多理解困难的问题,且提高了挖掘效率。     

基于标准编码的频繁子图挖掘算法

频繁子图挖掘是图挖掘的一个重要研究课题.gSpan算法作为一种高效的子图挖掘算法具有较好的执行效率,它通过最右扩展生成频繁子图,但不能保证每次扩展得到的均为标准编码.针对此问题本文提出了一种改进的算法CSGM,它采用ADI++存储结构,能处理更大规模的图集,同时保证每次最右扩展均生成标准编码,既避免了对非标准编码图的支持度计算,也避免了对输入编码是否为标准编码的计算.在实际数据集上运行的实验结果表明它比原算法提高了挖掘效率.     

基于加权动态网络的频繁模式挖掘研究

不同时刻的动态网络往往具有不同权重,针对加权动态网络的频繁模式挖掘,提出一种挖掘算法WGDM,它适用于加权动态社会网络、生物网络等方面的频繁模式挖掘。WGDM算法利用支持度的反单调性裁剪搜索空间,从而减少冗余候选子图,提高算法效率。通过实验测试了WGDM算法的性能,并根据中国实际股票市场网络,利用WGDM算法挖掘股票市场网络中有趣的频繁模式。     

一种频繁子图挖掘算法

为减少频繁子图规范化检测的时间复杂度,对规范化邻接矩阵的相关性质进行分析。给出相关定理并证明其正确性,从而减少冗余候选子图的产生。在此基础上,提出一种频繁子图挖掘算法——FSM_CAM。实验结果证明,与现有频繁子图挖掘算法FSubGraphM相比,FSM_CAM算法的效率较高。     

GC-BES:一种新的基于嵌入集的图分类方法

已提出很多图分类方法。这些方法在挖掘频繁子图时,只考虑了子图的结构信息,没有考虑子图的嵌入信息。实际上,有些频繁子图挖掘算法在计算子图的支持度时,可以获得嵌入信息。在L-CCAM子图编码的基础上,提出了一种基于嵌入集的图分类方法。该方法采用基于类别信息的特征子图选择策略,充分利用嵌入集,在频繁子图挖掘过程中直接选择特征子图。通过实验表明,该方法是有效的、可行的。     

基于加权有向图的权频繁模式挖掘算法

为解决加权图遍历模式的挖掘问题,提出了一种从加权有向图中挖掘加权频繁模式算法.在该算法中,利用图全局拓扑结构和顶点权值信息评估遍历模式的权支持度,从而将剪枝问题转化成模式可扩展性问题,再利用可扩展模式产生候选模式集.本算法把图,顶点权值融合进来,提高了挖掘结果的准确度.实验结果表明,该算法可以有效地进行基于加权向图的权频繁模式挖掘.     

从图数据库中挖掘频繁跳跃模式

很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.     

一种基于差分隐私的频繁有权子图挖掘算法

目前,在保护频繁子图数据的研究领域中,关于保护带有边权重的子图数据还没有被研究.针对这一问题,在频繁有权子图的挖掘过程中,采用差分隐私技术兼顾地保护频繁子图的边权重和结构的隐私,提出Diff-Wfsm算法.通过扩展已有挖掘算法,将图模型转换成编码形式,并将权重值考虑到编码中.为了更好地保护结构的隐私和提高数据效用性,在挖掘过程中同时采用差分隐私的Laplace机制和指数机制.实验在多个真实数据集中进行,结果表明该算法能在挖掘过程中达到隐私保护的效果,并可以保证输出的频繁有权子图具有较高的数据效用性.     

基于化合物库测试的gSpan算法

gSpan算法是一种基于频繁图的数据挖掘算法。该算法基于无候选人产生的频繁子图,采用深度优先搜索策略挖掘频繁连接子图。由于其设计结构具有连续性以及无候选人产生,算法的性能得以提高,在执行速度上可以达到前人算法如FSG算法的15~100倍。基于化合物库Chemical-340测试发现,该算法能够以卓越性能有效挖掘频繁子图。该算法可以应用在搜索具有相同子结构的化合物研究中,对相关领域研究发展具有重要意义。     

基于化合物库测试的gSpan算法

gSpan算法是一种基于频繁图的数据挖掘算法。该算法基于无候选人产生的频繁子图，采用深度优先搜索策略挖掘频繁连接子图。由于其设计结构具有连续性以及无候选人产生，算法的性能得以提高，在执行速度上可以达到前人算法如FSG算法的15～100倍。基于化合物库Chemical_340测试发现，该算法能够以卓越性能有效挖掘频繁子图。该算法可以应用在搜索具有相同子结构的化合物研究中，对相关领域研究发展具有重要意义。     

利用MapReduce平台实现高效并行的频繁子图挖掘

频繁子图挖掘是数据挖掘领域的一个重要问题,并且有着广泛的应用。在Hadoop平台上实现了一种基于MapReduce的高效频繁子图挖掘算法Cloud-GFSG（cloud-global frequent subgraph）。该算法基于Apriori思想,在扩展边生成新的子图时,使用已经挖掘出的k-1阶的频繁子图生成k阶的频繁子图。同时,检查是否存在待扩展生成的子图,设定生成的频繁子图表示规则,保证了频繁子图信息的唯一性。较同类算法相比,该算法在挖掘频繁子图时更具通用性,并且在扩展边时避免产生大量的复制图,从而使得算法的正确性得以保证,且运行效率显著提高。     

一种改进的闭图挖掘算法

频繁子图挖掘是各种图挖掘的基础和瓶颈,为了提高频繁子图挖掘算法的效率,在频繁闭图方法的基础上提出了一种新算法BPCG.首先使用了一种新结构表存储频繁子图集,从而不需扫描图集就可直接扩展最频繁邻接边及计算支持度阈值;然后算法又利用兄弟剪枝策略和删除局部频繁边,缩小搜索空间并减少不必要的操作.通过实验证明,算法优于其他子图挖掘算法.     

一种新的频繁子图挖掘算法

传统Aprior频繁子图挖掘算法中存在大量冗余子图.针对该问题,提出一种新的频繁子图挖掘算法(GAI).介绍一种三层MADI索引结构,用于存储图集的信息,以减少图集的扫描次数,通过扩展ETree树构造频繁子图,并用表来存储候选子图,避免扩展过程中冗余图的产生以及对整个数据库的扫描,从而简化支持度的计算,提高图/子图同构...     

Efficient frequent connected subgraph mining in graphs of bounded tree-width

The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to forests then the problem becomes tractable. In this paper we generalize the positive result on forests to graphs of bounded tree-width. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed in incremental polynomial time. Since subgraph isomorphism remains NP-complete for bounded tree-width graphs, the positive complexity result of this paper shows that efficient frequent pattern mining is possible even for computationally hard pattern matching operators.     

Mining frequent subgraphs from tremendous amount of small graphs using MapReduce

Frequent subgraph mining from a tremendous amount of small graphs is a primitive operation for many data mining applications. Existing approaches mainly focus on centralized systems and suffer from the scalability issue. Consider the increasing volume of graph data and mining frequent subgraphs is a memory-intensive task, it is difficult to tackle this problem on a centralized machine efficiently. In this paper, we therefore propose an efficient and scalable solution, called MRFSE, using MapReduce. MRFSE adopts the breadth-first search strategy to iteratively extract frequent subgraphs, i.e., all frequent subgraphs with \(i+1\) edges are generated based on frequent subgraphs with i edges at the ith iteration. In our design, existing frequent subgraph mining techniques in centralized systems can be easily extended and integrated. More importantly, new frequent subgraphs are generated without performing any isomorphism test which is costly and imperative in existing frequent subgraph mining techniques. Besides, various optimization techniques are proposed to further reduce the communication and I/O cost. Extensive experiments conducted on our in-house clusters demonstrate the superiority of our proposed solution in terms of both scalability and efficiency.     

频繁子图挖掘算法gSpan的设计与实现

由于大部分图挖掘算法都需要利用频繁子图,频繁子图挖掘逐渐成为了数据挖掘领域中的热点研究内容。目前,很多高效的频繁子图挖掘算法已经被提出。其中,gSpan算法是目前公认的最好的频繁子图挖掘算法。然而,在化合物数据集上,还可以利用化合物的特殊结构进一步优化gSpan算法的性能。文献利用了化合物分子结构的对称性和原子类型分布的不均衡性,提出了一些新的优化策略,进一步改进了gSpan的性能。鉴于gSpan算法在图挖掘领域乃至整个数据挖掘领域的重要性,设计并实现gSpan算法。同时,采用文献[4]中的优化策略,进一步提高gSpan算法在化合物数据集上的运行效率。     

Attributed graph mining in the presence of automorphism

Attributed directed graphs are directed graphs in which nodes are associated with sets of attributes. Many data from the real world can be naturally represented by this type of structure, but few algorithms are able to directly handle these complex graphs. Mining attributed graphs is a difficult task because it requires combining the exploration of the graph structure with the identification of frequent itemsets. In addition, due to the combinatorics on itemsets, subgraph isomorphisms (which have a significant impact on performances) are much more numerous than in labeled graphs. In this paper, we present a new data mining method that can extract frequent patterns from one or more directed attributed graphs. We show how to reduce the combinatorial explosion induced by subgraph isomorphisms thanks to an appropriate processing of automorphic patterns.     

一种基于Apriori思想的频繁子图发现算法

如今,关联规则技术应用在许多非传统领域,许多已有的频繁项集搜索方法已经不适用了。一种解决的方法就是用图的形式表示这些领域的事务,然后利用基于图论的数据挖掘技术发现频繁子图。本文提出了一种基于Aproiri思想的频繁子图发现算法SLAGM,它可以有效地挖掘简单图中的频繁子图。实验证明,该算法在性能上优于另一种子图挖掘算法AGM。     

挖掘不确定频繁子图的改进算法的研究

鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性,不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE,但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS,它用改进过的GSpan算法进行不确定的子图数据预处理,用裁剪子图模式的搜索空间裁剪不确定子图数据,用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。     

NODAR: mining globally distributed substructures from a single labeled graph

Data mining in structured and semi-structured data focuses on frequent data values. However, in graph data mining, the focus is on common specific topologies. Graph mining, although its ubiquity, is a difficult task since it requires subgraph isomorphism which is known to be NP-complete. In order to effectively prune the search space and thereby save computational time, a graph mining algorithm requires that the support measure of a pattern to be no greater than that of its subpatterns. This property of the support measure is referred to in the literature as the down-closure, anti-monotonicity or admissibility. Unfortunately, when mining a single labeled graph, simply counting the occurrences of a graph pattern may not have the down-closure property. For this, most existing approaches mine frequent substructures in a set of labeled graphs (called also the transactional setting) and few efforts have been devoted to mining frequent globally distributed substructures in a single labeled graph. In this paper, we propose a graph mining algorithm, called NODAR(Non-Overlapping embeDding based grAph mineR), for computing common and globally distributed substructures in a single labeled graph. NODAR adopts the Depth-First Search (DFS) strategy and is based on the SMNOES (Size of Maximum Non Overlapping Embedding Set) as support measure. The core idea of NODAR is to automatically extract frequent subpatterns; and thus without frequency computation thanks to the down-closure property of SMNOES. By adopting this strategy in the computation of frequent substructures, NODAR reduces the number of subgraph isomorphism tests needed to compute pattern frequencies. Experimental results on monograph and transactional graph databases; and comparison with well-known probabilistic and exact algorithms; prove the efficacy of NODAR.