Apriori算法用于频繁子图挖掘的改进方法  

Improved method based on Apriori-based frequent sub-graph mining algorithm

作　　者：陈立宁[1] 罗可[1] 

机构地区：[1]长沙理工大学计算机与通信工程学院,长沙410076

出　　处：《计算机工程与应用》2011年第10期113-117,共5页Computer Engineering and Applications

基　　金：国家自然科学基金No.10926189;No.10871031;湖南省科技计划项目(No.2008FJ3015)~~

摘　　要：AGM算法最早将Apriori思想应用到频繁子图挖掘中。AGM算法结构简单,以递归统计为基础,但面临庞大的图数据集时,由于存在子图同构的问题,在生成候选子图时容易产生很多冗余子图,使计算时间开销很大。基于AGM算法,针对候选子图生成这一环节对原算法进行改进,减少了冗余子图的生成,使改进后的算法在计算时间上具有高效性;测试了在不同最小支持度情况下改进方法的时间开销。实验结果表明改进算法比原算法缩短了计算时间,提高了频繁子图的挖掘效率。AGM（Apriori-based Graph Mining） algorithm is the first one to put the Apriori idea into the use of frequent sub-graph mining.This algorithm is simple and based on recursion statistics.But graph data set is very large and sub-graph isomorphism problem is available,when candidate subgraphs are generated and so many redundant sub-graphs would be generated,which makes the high cost in computing time.An improved method based on AGM is proposed to get the reduction of redundant sub-graphs and make the new algorithm more efficient in computing time,compared to AGM algorithm.This paper examines the computing time for various minimum support,the result of which proves that the improved algorithm cuts down the computing time,compared to AGM algorithm,improving the efficiency of frequent sub-graph mining.

关 键 词：频繁子图挖掘 AGM算法 子图同构 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]