加权最大频繁子图挖掘算法的研究

doi:10.3778/j.issn.1002-8331.2009.20.009

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (20): 31-34.DOI: 10.3778/j.issn.1002-8331.2009.20.009

加权最大频繁子图挖掘算法的研究

王映龙¹，杨珺²，周法国¹，唐建军²

1.江西农业大学软件学院，南昌 330045
2.江西农业大学计算机与信息工程学院，南昌 330045

收稿日期:1900-01-01 修回日期:2009-05-11 出版日期:2009-07-11 发布日期:2009-07-11
通讯作者: 王映龙

Research on algorithm for mining weighted maximal frequent subgraphs

WANG Ying-long¹，YANG Jun²，ZHOU Fa-guo¹，TANG Jian-jun²

1.School of Software，Jiangxi Agriculture University，Nanchang 330045，China
2.College of Computer and Information Engineering，Jiangxi Agriculture University，Nanchang 330045，China

Received:1900-01-01 Revised:2009-05-11 Online:2009-07-11 Published:2009-07-11
Contact: WANG Ying-long

摘要/Abstract

摘要： 如何从大量的图中挖掘出令人感兴趣的子图模式已经成为数据挖掘领域研究的热点之一。传统的频繁子图挖掘方法对满足最小支持度阈值的子图同等对待，但在真实数据库中不同的子图往往具有不同的重要程度。为解决上述问题，提出了一种深度优先的挖掘加权最大频繁子图的新算法。首先给出了一种新的用于计算图的邻接矩阵规范编码的结点排序策略，大大降低了求图规范编码的复杂度，并可以加速子图规范编码匹配的速度。其次，给出了加权最大频繁子图的定义，不仅可以找出较为重要的最大频繁子图，而且可以使挖掘结果同样具有反单调性，从而可加速剪枝。实验结果表明，提出的算法不仅可以有效地减少挖掘结果的数量，而且具有较高的效率。

关键词: 数据挖掘, 最大加权频繁子图, 邻接矩阵, 规范编码

Abstract: Frequent subgraph mining is an active research topic in the data mining community.Another problem is previous frequent subgraph mining algorithms treat graphs uniformly while graphs have different importance actually.To solve the above two problems，authors propose a new depth-first algorithm to discover weighted maximal frequent subgraphs only.Firstly，to lower the complexity of computing canonical code of adjacency matrix of graph，a new vertex sorting strategy is introduced.Meanwhile，the sorting strategy can also speed the matching process of canonical codes.Secondly，weighted maximal frequent subgraph is defined，which can not only discover important maximal subgraph，but also inherit the property of anti-monotony.Thus，the speed of pruning is quickened.Experimental results show the proposed algorithm can not only reduce the number of discovered graph patterns，but also is efficient.

Key words: data mining, weighted maximal frequent subgraph, adjacency matrix, canonical code

王映龙¹，杨珺²，周法国¹，唐建军². 加权最大频繁子图挖掘算法的研究[J]. 计算机工程与应用, 2009, 45(20): 31-34.

WANG Ying-long¹，YANG Jun²，ZHOU Fa-guo¹，TANG Jian-jun². Research on algorithm for mining weighted maximal frequent subgraphs[J]. Computer Engineering and Applications, 2009, 45(20): 31-34.

[1]	宗晓萍，陶泽泽. 基于掌握速度的知识追踪模型[J]. 计算机工程与应用, 2021, 57(6): 117-123.
[2]	高天宇，王庆荣，杨磊. 粗糙集属性依赖度强化的应急数据挖掘模型[J]. 计算机工程与应用, 2021, 57(3): 87-93.
[3]	马洋，赵旭俊. 基于相关子空间的多源离群检测算法[J]. 计算机工程与应用, 2021, 57(17): 88-95.
[4]	张念蓬，吴旭，朱强. 基于熵的过采样框架[J]. 计算机工程与应用, 2021, 57(13): 96-101.
[5]	张博文，刘智，桑国明. 基于核密度波动的异常检测算法[J]. 计算机工程与应用, 2021, 57(12): 132-136.
[6]	饶加旺，马荣华. 改进核密度估计的空间点密度算法[J]. 计算机工程与应用, 2021, 57(11): 260-265.
[7]	王杰，陈志刚，刘加玲，程宏兵. 基于聚类的云隐私行为挖掘技术[J]. 计算机工程与应用, 2020, 56(5): 80-84.
[8]	李建，习文风. 钻井液设计专家系统规则库的检测算法[J]. 计算机工程与应用, 2020, 56(4): 256-261.
[9]	王子龙，李进，宋亚飞. 基于距离和权重改进的K-means算法[J]. 计算机工程与应用, 2020, 56(23): 87-94.
[10]	衣俊艳，吴博雅，雍巧玲. 具有加权特性的弹性网络聚类算法研究[J]. 计算机工程与应用, 2020, 56(22): 55-65.
[11]	纪文璐，王海龙，苏贵斌，柳林. 基于关联规则算法的推荐方法研究综述[J]. 计算机工程与应用, 2020, 56(22): 33-41.
[12]	刘文芬，穆晓东，黄月华. 基于多分辨率网格的异常检测方法[J]. 计算机工程与应用, 2020, 56(17): 78-85.
[13]	孟海东1，2，孙新军2，宋宇辰1. 基于数据场的改进LOF算法[J]. 计算机工程与应用, 2019, 55(3): 154-158.
[14]	雷乐，王丽珍，肖清. 空间co-location模式挖掘中的模糊技术初探[J]. 计算机工程与应用, 2019, 55(21): 158-166.
[15]	郭鹏，蔡骋. 基于聚类和关联算法的学生成绩挖掘与分析[J]. 计算机工程与应用, 2019, 55(17): 169-179.

加权最大频繁子图挖掘算法的研究

Research on algorithm for mining weighted maximal frequent subgraphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics