挖掘不确定频繁子图的改进算法的研究

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (3): 112-116.

• 数据库、数据挖掘、机器学习 • 上一篇下一篇

挖掘不确定频繁子图的改进算法的研究

胡健1，何林波2，毛伊敏1，杨健2

1.江西理工大学应用科学学院，江西赣州 341000
2.江西理工大学信息工程学院，江西赣州 341000

出版日期:2015-02-01 发布日期:2015-01-28

Research of improved mining frequent subgraph patterns in uncertain graph databases

HU Jian1, HE Linbo2, MAO Yimin1, YANG Jian2

1.Applied Science Institute of Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000, China
2.School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000, China

Online:2015-02-01 Published:2015-01-28

摘要/Abstract

摘要： 鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性，不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE，但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS，它用改进过的GSpan算法进行不确定的子图数据预处理，用裁剪子图模式的搜索空间裁剪不确定子图数据，用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。

关键词: 不确定图, 图挖掘, 频繁子图集, 划分思想, 混合策略

Abstract: Mining frequent subgraph patterns in graph databases is a popular and important problem which has wide application in lots of domains. At the moment, the MUSE is a typical algorithm for graph mining, but its expected supports computation costs a lot and the time efficiency is so low. So this paper proposes a method that combines classification thought with BFS thought to find frequent subgraph patterns（EDFS）. It uses improved GSpan algorithm to deal with uncertain graphs to reduce the space of subgraph patterns, then integrates classification thought with BFS thought to mine frequent subgraph patterns. The subgraph isomorphism tests and the edge whether existing tests indicate that EDFS is more efficient than MUSE.

Key words: uncertain graph, graph mining, frequent subgraph patterns, classification thought, mixed algorithm

胡健1，何林波2，毛伊敏1，杨健2. 挖掘不确定频繁子图的改进算法的研究[J]. 计算机工程与应用, 2015, 51(3): 112-116.

HU Jian1, HE Linbo2, MAO Yimin1, YANG Jian2. Research of improved mining frequent subgraph patterns in uncertain graph databases[J]. Computer Engineering and Applications, 2015, 51(3): 112-116.

[1]	刘峰，Godfred Kim Mensah，李欣芸，刘鸿丽，李瑶，郭浩. 不确定脑网络的异常拓扑分析及分类研究[J]. 计算机工程与应用, 2020, 56(2): 127-132.
[2]	王凯，陈丹伟. 基于LSTM的动态图模型异常检测算法研究[J]. 计算机工程与应用, 2019, 55(5): 76-82.
[3]	夏吾吉1，2，华却才让1. 基于混合策略的藏文人称代词指代消解研究[J]. 计算机工程与应用, 2018, 54(7): 66-69.
[4]	辛娟娟，曹佳. 基于复杂网络的文献热点挖掘及可视化[J]. 计算机工程与应用, 2016, 52(12): 261-264.
[5]	吴桥1，陈琼2. 期权工具存在下的最优混合采购策略研究[J]. 计算机工程与应用, 2015, 51(8): 231-235.
[6]	杨书新，徐丽萍，王鹏. 基于图挖掘和决策树的软件故障定位研究[J]. 计算机工程与应用, 2015, 51(20): 67-71.
[7]	张健，王晋东，张恒巍. 静态贝叶斯博弈在信息系统风险分析中的应用[J]. 计算机工程与应用, 2015, 51(11): 76-82.
[8]	吴桥1，殷辉2. 期货市场存在下原材料混合采购策略研究[J]. 计算机工程与应用, 2015, 51(10): 237-241.
[9]	王全，王维，李焱，刘大学. 基于混合策略的轮式机器人路径规划方法[J]. 计算机工程与应用, 2014, 50(4): 45-49.
[10]	雷小刚，尚学群，王淼. CoClique：从生物网络中挖掘频繁关联相似模式[J]. 计算机工程与应用, 2011, 47(32): 155-158.
[11]	陈立宁，罗可. Apriori算法用于频繁子图挖掘的改进方法[J]. 计算机工程与应用, 2011, 47(10): 113-117.
[12]	田生伟¹，吐尔根·依布拉音¹，禹龙². 混合策略的汉维句子对齐[J]. 计算机工程与应用, 2010, 46(34): 143-145.
[13]	陈北京^1，2，何可佳¹，涂桢³，应宏微¹ . 改进混合策略的多分辨率3D医学图像配准[J]. 计算机工程与应用, 2010, 46(30): 173-177.
[14]	郭会林,苏一丹. 一种基于混合策略的蚁群聚类算法[J]. 计算机工程与应用, 2008, 44(16): 154-156.
[15]	时燕张化祥赵瑞东. 一种新的混合策略进化算法[J]. 计算机工程与应用, 2007, 43(13): 89-91.

挖掘不确定频繁子图的改进算法的研究

Research of improved mining frequent subgraph patterns in uncertain graph databases

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics