频繁子图挖掘算法

挖掘出所有频繁子图的计算方法

频繁子图挖掘算法是一种思路简单，以递归计数为基础，就可以挖掘出所有频繁子图的计算方法。

定义与分类

(1)按照模式挖掘算法的输入数据类型进行分类:分为graph-transaction和single-graph两种类型。graph-transaction型模式挖掘所处理的输入数据是由许多规模相对较小的图构成的集合，每个图可能只包含几十到几百个顶点;而single-graph型模式挖掘的对象则只有-个大图，这个大图包含成千上万个顶点。这两种类型的区别还在于它们计算候选子图频度时所使用的策略。graph-transaction型计算模式在图集合每个图中是否出现，不管它在同-个图中出现了多少次均计数-次，而single-graph型则计算模式在这个大图中不同位置出现的总次数。根据两种类型的特征，解决graph-transaction类型的算法不能用来解决single-graph类型模式挖掘，但是Single-graph类型的算法却能方便应用于graph-transaction类型。

(2)按照采用度量的不同进行分类:分为支持度(support)、支持度-置信度、MDL(minimumdescri-Ptionlength)三种。支持度型挖掘是以子图在输入图中出现的次数来作为度量的，大部分算法都是基于支持度的;MDL型挖掘是以压缩输入数据的程度来度量，-般采用公式valuo(s，g)=dl(g)/(dl(g1)+dl(g2))来计算，其中:是子图，g是输入的图集合，dl(g)表示图集合g的存储空间，dl(g2)表示把g中所有出现:的地方都用同-个顶点替换后的图形所需的存储空间;支持度-置信度型挖掘是以既要满足最小支持度又要满足最小置信度来衡量的。还有其它-些度量方法，这里就不再介绍了。

(3)按照挖掘出的频繁子图的类型进行分类:分为一般子图、连通子图、诱导子图等。

算法思路

算法的思路比较简单，但是对于包含较多图的输入集合来说执行效率非常低，主要是因为挖掘算法在生成候选子图时要判断是否存在相同的k-1子图，当川尺大时，这需要花费很长时间。并且通过每次添加一个顶点来产生候选子图时会产生许多冗余k+l子图。

在剪枝的过程中，也需要很多时间来判断每个k+l候选子图的所有k子图是否都是频繁的。剪枝后的候选子图仍然很多，因此需要大量的重复扫描输入图集合来计算候选子图的支持度。这就占用了大量的内存空间和CPU处理时间，很难发现较大的模式子图，执行效率不高。而频繁子图挖掘算法是在挖掘算法算法的基础上提出来的。区别在于频繁子图挖掘算法旨在发现连通的频繁子图，采用了一些特殊的技巧以提高性能。

它引入了半连通图的概念，图G是半连通图当且仅当G是连通图或G只由一个连通分支和一个孤立点组成。在频繁子图挖掘算法中所使用的规范化标记将顶点的标号也考虑在内，同时还应用了诸如规范化标记发现和砂树等技巧来提高其性能。Kuramochi.M等人提出的FSG算法采用完全不同的找寻方法挖掘频繁子图。在他们的算法中采取每次添加一条边的策略，而不是每次添加一个顶点，并加强了候选子图的剪枝，在计算候选子图的支持度时采用TID列表帮助加速计算，使得执行效率较挖掘算法有所提高。

经典算法

Apriori算法

k-频繁子集用于生成 k+1-子集，根据downward closure property性质进行剪枝，生成 k+1候选集，通过对数

据库进行扫描判断候选子集中哪些是频繁的。如此下去，直到不能找到频繁项集。

如果 k+1子集的任何一个k子集是非频繁的，则是k+1子集一定也是非频繁的。

a. AGM算法

每次添加一个顶点

b. FSG算法

每次添加一条边

FP-growth算法

主要思想：

将产生频繁集的数据压缩到一棵频繁模式树FP-tree中，用FP-tree存储项的关联信息，然后对模式树产生频繁集。