基于图数据的极大频繁子树挖掘算法研究  

Algorithm of maximum frequent sub-tree mining based on graph data

作　　者：唐德权 黄金贵[3] TANG De-quan;HUANG Jin-gui(School of Mathematics and Statistics,Hunan Normal University,Changsha 410081,China;Department of Information Technology,Hunan Police Academy,Changsha 410138,China;College of Information Science and Engineering,Hunan Normal University,Changsha 410081,China)

机构地区：[1]湖南师范大学数学与统计学院,湖南长沙410081 [2]湖南警察学院信息技术系,湖南长沙410138 [3]湖南师范大学信息科学与工程学院,湖南长沙410081

出　　处：《微电子学与计算机》2020年第10期54-58,共5页Microelectronics & Computer

基　　金：国家自然科学基金资助项目(61471169);湖南省科技重大专项项目(2017SK1040)。

摘　　要：由于极大频繁子树中已经隐含了所有频繁子树信息,尤其处理大型图数据集时候,挖掘极大频繁子树对提高频繁子树挖掘算法效率具有重要意义.首先在有效编码的基础上提出连接和扩展操作算法,通过两个算法产生所有极大候选子树;其次引入嵌入集计算解决子树同构问题,对子树同构问题进行了优化,进一步提出了一种新的极大频繁子树挖掘算法(MFST);最后证明了算法的正确性和分析了算法在最坏情况下的时间性能,并与其它基于半结构化数据集的频繁子树挖掘算法进行了比较.实验结果表明,MFST算法具有更好的时间性能和空间性能,可以在图数据集中有效挖掘频繁子树.In view of the the current frequent subtree mining problems,the maximal frequent subtree mining algorithm can improve the efficiency of the frequent subtree mining algorithm.Firstly,propose two operations of the join and extension on the basis of effective coding,which are generate all candidate subtrees.Secondly,the embedded set is used to solve the problem of subtree isomorphism,and a new maximum frequent subtree mining algorithm(MFST)is proposed.Finally,the correctness of the algorithm is proved and the time performance of the algorithm in the worst case is analyzed.And compared with other frequent subtree mining algorithms based on semi-structured data sets,prove this algorithm is superior to the current frequent subtree mining algorithms.The experimental results show that the MFST algorithm has better time and spatial performance,and can effectively mining frequent subtree on the graph data sets.

关 键 词：极大频繁子树 图数据集 候选子树 子树同构 半结构化数据集 

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