基于频繁模式树的频繁连通闭图集挖掘算法.docx

基于频繁模式树的频繁连通闭图集挖掘算法
一、介绍
频繁连通闭图集挖掘算法（FCGAM）是一种基于频繁模式树的图论算法，用于发现频繁连通闭图集。FCAM能够处理实现高效发现连通图集的问题，而这些图集在实际的应用中非常有用。例如，生物网络研究中可能需要寻找同源结构，或查找化合物之间的相互作用。FCGAM提高并优化了以前的算法，如CCGAM（connectedclosedgraphminingalgorithm）和FCI（frequentconnectedinducedsubgraph）。
二、FCGAM算法
FCGAM的基本思想是建立一个FPTree来查询频繁模式。FPTree是一种数据结构，用于将模式转换为有序模式列表。这个列表类似于FPgrowth算法中的条件基。在FCGAM中，我们需要将模式从一个无序的顺序中提取出来，并将其放入一个有序的链表中以便后面的搜索。FCGAM使用了一种新的技术来构建FPTree，称为FCtree（FrequentConnectedtree）。
在FCGAM中，用‘连通闭图’来寻找频繁模式。连通闭图是指，它的所有节点都是紧密相连的，并且不能再添加任何新的边或节点。连通闭图对于描述化合物和蛋白质结构非常有用。FCGAM的主要任务是找到频繁连通闭图，而其它频繁模式则可以从其中直接获得。
FCGAM的大体流程是:
输入:数据库D,最小支持度（minimumsupport）minsup，最小连通度（minimumconnectivity）mincon。
输出:频繁连通闭图列表。
第一步：构建FCtree。
FCtree的根节点表示全图。我们先对数据库D中所有的图层进行排序，然后对于每个图层，我们按照连通度对其进行分类。假设有L个图层，对于第i个图层Li（1≤i≤L),所有连通度为j的图形组成一组，其中j的最小值为1，最大值为图形的大小-1。假设Li中共有m个图形，我们将这m个图形按照连通方式相同的类别划分为m’个集合。然后我们将每个集合都加入到FCtree中。根据该类别标记的支持度计算最小支持度，确定哪些集合是频繁的。
第二步：寻找频繁连通闭图
我们递归的寻找FCtree中所有满足最小支持度和最小连通度的频繁连通闭图。所谓递归是指，我们从根节点开始，采用深度优先搜索的遍历方式，依次访问每个ToNode（即FCtree中的节点）。如果一个ToNode（或者一个叶节点）的连通度大于或等于mincon，则可以产生一个连通闭图。如果该闭图的支持度大于或等于minsup，则其为频繁连通闭图。如果该闭图中还有儿子，则继续递归处理以这些儿子节点为根的树。如果该节点是叶节点，则直接退出。
三、优化策略
FCGAM优化了以前算法的模式计数方法，提高了效率，具体优化方案如下:
1.使用FCtree提取模式。FCtree是FP-tree的改进版。因为网络中的连通性是一个必要且重要的特征，FCtree在计算模式时将考虑这个特征。
2.将模式计数方法从所有点到模式点转换为子格中的模式点。
3.选择最符合条件的模式，减少计算量，减少噪音。
4.使用DFS遍历来查找和处理所有的连通闭图。在这个过程中，FCGAM遵循最小支持度和最小连通度的条件，在每个节点上进行剪枝策略，只处理深度优先遍历中的模式子集。
四、评估和应用
实验表明，FCGAM明显快于以前算法，例如F-Miner和CCGAM等算法。然而，FCGAM需要更高的内存使用率，这对于硬件容量有限的设备来说可能产生一些障碍。从结果来看，FCGAM的优势在于它能处理大型数据集，并确定连接子图比其他算法更好。它已经被成功应用于生物网络数据挖掘，例如基因网络和蛋白质网络。
五、结论
FCGAM是一种基于频繁模式树的图论算法，它用于查找频繁连通闭图集。由于网络中的连通性是一个重要的特征，因此它在模式计数时考虑了这一特征，并使用FCTree建立了模式列表。FCGAM通过选择最符合条件的模式、处理所有连通闭图以及剪枝等方法优化了以前的算法，提高了效率和应用性。它已被成功应用于生物网络数据挖掘，取得了良好的成果。