一种有效的在不确定图数据库中挖掘频繁子图模式的MUSIC算法

王文龙　李建中

摘要：近年来，如何在不确定图数据库中挖掘频繁子图模式得到了越来越多的关注。该问题的主要难点在于，不仅存在着海量的可能子图模式需要检验，而且还需要做大数量的子图同构性测试来判别图中是否蕴含一个给定的模式。传统的算法是利用近似算法计算子图模式的期望支持度，但计算开销仍然十分巨大。为此提供一个基于建立在不确定数据库上的索引的算法。算法首先根据apriori性质枚举所有可能的首选子图模式，然后利用索引对候选子图模式空间进行剪枝以减少子图同构性检验从而减少期望支持度的计算开销。通过在一个真实数据集上的实验显示本算法可以有效地在不确定图数据库中挖掘频繁子图模式。

关键词：不确定图； 频繁子图模式； 期望支持度； 不确定图索引

中图分类号：TP311.13 [KG*2]文献标识码：A[KG*2][HT5”H]文章编号：2095-2163（2013）05-0020-04

0引言

在不确定图数据库中挖掘频繁子图模式是一个具有挑战性的问题。在期望语义下，检验子图模式是否频繁的标准由其在不确定图数据库的所有蕴含图数据库中的支持度的期望值来评价，称之为期望支持度。

在文献[1]中通过将问题转化为DNF计数问题的一个实例，给出了一个计算子图模式的期望支持度的近似算法。虽然该方法可以减少针对单一不确定图的计算开销，但整体开销仍然非常巨大。文献[2，3]分别给出了一个有效的子图同构性检验算法，但由于本问题巨大的子图同构性检验次数，并不能有效降低挖掘所需的时间。

本文提出了MUSIC算法，来解决在不确定图数据库中挖掘频繁子图模式的问题。算法通过索引来减少判断支持度的计算开销。文中的实验显示了MUSIC算法的有效性。

1数据模型和问题定义