频繁子图挖掘算法的若干问题

杨 盛

(长沙矿山研究院, 湖南长沙 410012)

频繁子图挖掘算法的若干问题

杨 盛

(长沙矿山研究院, 湖南长沙 410012)

介绍了基于频繁子图挖掘算法的思想及其相关算法,提出了频繁子图挖掘算法的一些问题,对所挖掘图的存储方式进行了讨论,重点介绍了隐式存储方式及其优点。在频繁子图挖掘一般步骤的基础上,提出了通过构建频繁子图决策树 (FSDT)来实现挖掘算法的预处理问题,最后初步提出宽度优先子图同构法 (BFSI)来实现频繁子图决策树 (FSDT)。

频繁子图;图存储方式;预处理;频繁子图决策树

在数据挖掘和机器学习的发展中,人们渐渐的意识到传统的属性值和数据项集表示模式已经不能满足许多实际应用领域的要求[1～4],则提出了基于频繁子图的索引方法,通过控制频繁阈值可以控制频繁子图的数量。目前图结构数据的索引方法主要有 2种:基于路径的索引方法;基于频繁子图的索引方法。基于路径的索引方法存在自身的缺点,首先,路径太简单,丢掉了图的结构信息;同时,路径的数量太大,1个图数据库的路径集合往往非常巨大,该索引方法在长沙矿山研究院的数据库应用中就存在效率低的缺点。而基于频繁子图的索引方法使用频繁子图作为索引,融合了部分图的结构信息,在结构信息的使用上比路径索引有优势,因此本文主要介绍和论述此方法。

1 频繁子图挖掘算法

1.1 图的存储

关于图的存储也可以称为图的表示 (graph representation)。目前图的表示有邻接数组 (Adjacency Arrays)、邻接链表 (Adjacency Lists)、邻接矩阵 (Adjacency Matrix)、隐式表示 (Implicit Representation)。其中邻接数组主要用来描述静态数组,邻接链表主要用来表示动态图,邻接矩阵在表示稠密图上有很大优势。本文主要介绍以下 2种隐式表示方式。

(1)区间图表示方法[5]。区间图由一系列区间集合定义,每个区间对应图的 1个结点,2个结点间的关系通过间隔的重叠来表示。这种表示方法的一个优势是可以很容易的判断 1个图是否是连通图。将表示结点的区间的端点按序排列,然后按序扫描这些端点。如果有 1个或以上的区间不与其它区间重叠,那么这个图就不是连通的。否则就是连通的。另外 1个优势是存储图时空间很省,只需要O(n)级别的空间,而且还可进行有效的遍历。

(2)用 BDD来表示图[6]。BDD是 1个基于有序变量集上的布尔函数,其规范和紧凑性使其空间需求非常小,而且查询等操作速度较高,适用于图的数量大且需要较高的查询效率时。主要采用了如下技术进行处理:若图 G有 n个结点,则可定义 k个布尔变量 x1,x2,...,xk,其中 k为不小于 log2(n)的自然数。使用变量集 X=x1,x2,...,xk对每个结点编码,记为 E(u)。为了表示结点间的关联关系,引入另一组变量 X’=x1’,x2’,...,xk’。把 E’(u)称为E(u)的后继编码,这里 E’(u)是把 E(u)中 x1,x2,...,xk用相应的 x1’,x2’,...,xk’替换。如果节点 i和 j之间存在边 E(i,j),则生成 BDDbij:bij=E(i)∧E’(j),图 G的所有关联关系可表示如下:T(G)=∨bij,其中 i,j取遍 1到 n。如果 i和 j不相邻,则 bij=false。此时 BDD T(G)已经能够把无权图 G表示出来。

1.2 图数据库的预处理

原来的各种算法中,除了没有讨论图的存储形式外,也都没有对数据库中的图进行预处理。本文提出对数据库中的图结构数据进行频繁子图挖掘前首先要进行预处理。

图结构数据在各个行业中一般都是以非常大的数量出现,通常是海量信息。当进行频繁子图的挖掘时,就会存在如下问题。

(1)图数据库中存在某些图是另外一些图的子图。当前的频繁子图挖掘算法都是先对图建立规范编码,然后对整个数据库的图逐个进行规范化,以便简化子图同构。下一步就是对整个数据库中的图进行频繁子图的候选子图生成。对于生成候选子图时,必须有基础的频繁子图 (可能是 1个顶点或者 1条边、2条边等组成)。这些频繁子图需要在数据库逐个扫描图时统计其在图数据库各个图中出现的次数,扫描结束时将这个次数与阈值进行比较,从而判断该频繁子图是否是基础频繁子图。这一步是计算基础频繁子图的支持度,需要判断和记录基础频繁子图在图数据库中出现的次数。这样当图数据库中有一些图是另外一些图的子图时,就可以通过预先对图数据库中的图利用规范编码等一些技术对图数据库中的图进行频繁子图判断,并建立频繁子图决策树 (FSDT),来减少基础频繁子图挖掘时所要扫描图的数量。这在图数据库的数量很大或者图数据库中有很多子图包含情况时有很好的效果。

分析构建后的频繁子图决策树时发现,深度大于等于阈值的层上的图 (GLDET)是频繁子图,同时其任何子图也是频繁子图。这时如果按照 FSG算法来取所有以 1条边和 2条边为基础频繁子图的话,那么频繁子图决策树上满足深度大于等于阈值的图的所有单边及其任何 2条边的连通组合都是基础频繁子图。建立这个 FSDT的优势在于可以自动挖掘出大量的频繁子图,而且可以通过将不是 GLDET的图与未成为 FSDT的图在采用普通的频繁子图生成方法进行扫描计数。

(2)计算候选子图的支持度时需要多次扫描候选集的情况。在进行计算频繁子图的支持度时,就会重复进行若干子图同构测试。目前我们使用的 2种计算候选子图支持度的方法分别为:embedding list方法和 recomputed embedding方法[7]。

embedding list。对于只有 1个顶点的图,存储输入数据库中出现该顶点的所有图的编号。对于多顶点子图,存储输入数据库中所有出现该子图的图的编号以及该子图在这些图中的位置。这种方法计算起来速度快,但是要占用大量的存储空间,不适合大型输入数据库。

recomputed embedding。每次记录下出现该频繁子图的那些图的编号,通过扫描出现过 k频繁子图的那些图来计算 k+1候选子图的支持度,这样每次只记录图的编号,不用记录子图出现的位置,通过重复计算来获得规模为 k+1的子图的支持度,从而避免了全局扫描数据库。可以用来处理大型数据库,但是速度不如第一种方法。

从上面介绍的 2种方法可以看出处理大型数据库时,当需要生 k+1规模的子图时要扫描 k频繁子图集合,同样可以把 FSDT方法用在 k频繁子图集合中,可减少同构的次数和生成 k+1规模频繁子图。规模为 k+1的频繁子图可在 FSDT中寻找,同时还可以将 GLDET中的各个图添加一条边来生成规模为 k+1的频繁子图。同样规模为 k+2的频繁子图也同样可以采用如上的方法。但是生成的频繁子图也有许多冗余频繁候选子图需要才剪掉,比较原先的 Level-wise search方法、贪心方法和深度优先等方法来说,具有非常好的效果。

2 构建频繁子图决策树 (FSDT)的算法

采用宽度优先子图同构法 (BFSI)构建频繁子图决策树,即通过对图库中的图依次进行子图同构来构建子图决策树。

图数据库中 GD={G1,G2,...,Gn},对图库中的图按大小排序后建立的图的链表为 T={T1,T2,...,Tn},其中 T1为大小最大的图集,T2为大小小于 T1的图集,依次排序。Ti为图的大小相同的图的集合的数组,i∈n;Tij为 Ti图集中的图。j∈n。具体算法如下:

该算法通过宽度优先的方式从大到小进行子图同构,然后建立频繁子图决策树,从而可以使以后的频繁子图挖掘算法中的多次扫描数据库和计算候选子图支持度时的子图同构得以大幅减少,从而提高算法效率。该算法本身的复杂度为O(n2/2)级别的子图同构。

3 总 结

本文讨论了基于图的频繁子图的挖掘算法的算法思想和基于这些思想上的一些算法,介绍了基于Apriori思想和 FP-growth思想的及其衍生的各种频繁子图挖掘算法,归纳了频繁子图挖掘算法的基本步骤和流程。

文章中对前人忽视的图库中图的存储方式进行了介绍,并且介绍了 2种隐式存储方式。这 2种隐式存储方式可以节省大量空间,并且对图的各种处理有若干优势,是图存储的发展方向,也是图的频繁子图挖掘算法的基础,是未来改进图的频繁子图的性能的重要突破点之一。另外提出了 FSDT来处理图数据库中存在多个图是另外一些图的子图的问题,讨论了 FSDT解决方案的优点,及其在基础频繁子图的生成和候选子图生成时的作用和优势,并提出了宽度优先子图同构法来构建频繁子图决策树。

[1] BerendtB.,Hotho A.,Stumme G.Towards semantic web mining[C].IS WC,2002:264-278.

[2] DeshpandeM.,KuramochiM.,Karypis G.Automated approaches for classifying structures[C].In Proc.of the 2nd Workshop on Data Mining in Bioinformatics(B I OKDD’02),2002:11-18.

[3] Deshpande M.,KuramochiM.,Karypis G.Frequent sub-structure based approaches for classifying chemical compounds[C].In Proc.of 2003 IEEE International Conference on Data Mining(ICDM),2003:35-42.

[4] Gonzalez J.,Holder L.B.,Cook D.J.Application of graphbased concept learning to the predictive toxicology domain[J].In Proc.of the Predictive Toxicology Challenge Workshop,2001.

[5] KurtMehlhorn.Algorithms and Data Structures[C].Springer-Verlag Berlin and Heidelberg GmbH&Co.K,2008.

[6] Huan Jun,Wang Wei,Prins Jan.Efficient Mining of Frequent Subgraph in the presence of Isomorphism[C].ICDM,2003.

[7] 王艳辉,吴 斌,王 柏.频繁子图挖掘算法综述[J].计算机科学,2005,32(10):193-197.

2011-07-26)

杨 盛 (1983-),女,湖南衡阳人,助理工程师,研究方向为计算机科学与技术,Email:ys-89@hotmail.com。