RAKING:一种高效的不确定图K-极大频繁模式挖掘算法

RAKING:An Efficient K-Maximal Frequent Pattern Mining Algorithm on Uncertain Graph Database

由于不确定图蕴含了指数级的可能图实例,基于确定图模型的频繁图模式挖掘算法通常难以在不确定图集合上高效运行.文中提出了一种不确定图数据集上的基于随机游走的K极大频繁子模式挖掘算法.首先,将每个不确定图转换为相应的确定图并挖掘候选频繁模式;然后,将候选频繁模式恢复为不确定图并生成极大频繁模式搜索空间;最后,通过随机游走以相同概率随机地选择K个极大频繁模式.理论分析和实验结果表明文中提出的算法能够高效地获得不确定图集合的K-极大频繁模式.

An uncertain graph can represent a large number of possible graph instances.This greatly reduces the efficiency of existing frequent pattern mining algorithms.The paper proposes a random walk based K-maximal frequent pattern mining algorithm on uncertain graph set.Firstly,each uncertain graph is converted to a graph without uncertain information.Candidate frequent patterns are retrieved from the converted graph set.Then,the candidate frequent patterns are transformed to corresponding uncertain graph pattern and searching space of maximal frequent patterns are constructed as well.Finally,K-maximal frequent patterns are selected from all maximal frequent patterns equiprobably.Theoretical analysis and experimental results show that the proposed algorithm can efficiently retrieve the K-maximal frequent patterns of an uncertain graph set.