一种基于频繁子图的集成分类算法

doi:10.3969/j.issn.1006-2475.2017.01.006

计算机与现代化

一种基于频繁子图的集成分类算法

(中国航空工业集团公司西安航空计算技术研究所，陕西西安 710068)

收稿日期:2016-05-20 出版日期:2017-01-12 发布日期:2017-01-11
作者简介:刘意(1990-)，男，陕西咸阳人，中国航空工业集团公司西安航空计算技术研究所助理工程师，硕士，研究方向：数据挖掘，容错。

An Ensemble Classification Algorithm Based on Frequent Subgraphs

(Aeronautics Computing Technique Research Institute, AVIC, Xi’an 710068, China)

Received:2016-05-20 Online:2017-01-12 Published:2017-01-11

摘要/Abstract

摘要： 针对基于频繁子图的图分类算法不能有效解决高效和分类正确率并存的矛盾，提出G-Bagging图分类算法。该算法利用传统图分类算法训练出多个基图分类器，集成学习加权构造集成分类器，余度管理实时更新权值。通过实验，表明G-Bagging算法降低了对最小支持度和训练样本空间大小的要求，即在算法效率提高的同时，保证了分类正确率。

关键词: 图分类, 集成学习, 余度管理

Abstract: Aiming at the contradiction of efficiency and correct rate existing in graph classification based on frequent subgraphs, the paper comes up with an algorithm for graph classification named G-Bagging. The algorithm makes base classifiers by traditional algorithm, and makes ensemble classifier by ensemble learning base classifiers, and updates ensemble classifier by redundancy management. Then we demonstrate that the algorithm can reduce the requirement of minimum support and training samples space by experiment, also is that the algorithm can ensure both efficiency and correct rate.

Key words: graph classification, ensemble learning, redundancy management

中图分类号:

TP391

刘意. 一种基于频繁子图的集成分类算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2017.01.006.

LIU Yi. An Ensemble Classification Algorithm Based on Frequent Subgraphs[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.01.006.

参考文献

[1] Mayer-Schonberger V, Cukier K. Big Data: A Revolution That Will Transform How We Live, Work and Think[M]. Eamon Dolan: Houghton Mifflin Harcourt, 2013.

[2] Chang Ray-Yaung, Podgurski A, Yang Jiong. Discovering neglected conditions in software by mining dependence graphs[J]. IEEE Transactions on Software Engineering, 2008,34(5):579-596.

[3] Inokuchi A, Washio T, Okada T, et al. Applying the Apriori-based graph mining method to mutagenesis data analysis[J]. Journal of Computer Aided Chemistry, 2001,2:87-92.

[4] 于戈,谷峪,包玉斌,等. 云计算环境下的大规模图数据处理技术[J]. 计算机学报, 2011,34(10):1753-1767.

[5] Lian Wang, Cheung D W, Mamoulis N, et al. An efficient and scalable algorithm for clustering XML documents by structure[J]. IEEE Transactions on Knowledge and Data Engineering, 2004,16(1):82-96.

[6] Huan Jun, Wang Wei, Prins Jan. Efficient mining of frequent subgraphs in the presence of isomorphism[C]// Proceedings of the 3rd IEEE International Conference on Data Mining. 2003:549-552.

[7] Horvath T, Gartner T, Wrobel S. Cyclic pattern kernels for predictive graph mining[C]// Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2004:158-167.

[8] Liu Yang, Wu Bin, Wang Hongxu. BPGM: A big graph mining tool[J]. Tsinghua Science and Technology, 2014,19(1):33-38.

[9] Deshpande M, Kuramochi M, Wale N, et al. Frequent substructure-based approaches for classifying chemical compounds[J]. IEEE Transactions on Knowledge and Data Engineering, 2005,17(8):1036-1050.

[10] Yang Guizhen. Computational aspects of mining maximal frequent patterns[J]. Theoretical Computer Science, 2006,362(1-3):63-85.

[11] Chakrabarti D, Faloutsos C. Graph mining: Laws, generators, and algorithms[J]. ACM Computing Surveys, 2006,38(1): Article No. 2.

[12] 张春霞,张讲社. 选择性集成学习算法综述[J]. 计算机学报, 2011,34(8):1399-1410.

[13] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970,49(2):291-307.

[14] 曹莹,苗启广,刘家辰,等. AdaBoost算法研究进展与展望[J]. 自动化学报, 2013,39(6):745-758.

[15] 丁悦,张阳,李战怀,等. 图数据挖掘技术的研究与进展[J]. 计算机应用, 2012,32(1):182-190.

[16] Breiman L. Bagging predictors[J]. Machine Learning, 1996,24(2):123-140.

[17] 刘意,王勇,尚学群. 一种基于特征子图的不确定图分类算法[J]. 陕西师范大学学报(自然科学版), 2014,42(5):16-19.

一种基于频繁子图的集成分类算法

An Ensemble Classification Algorithm Based on Frequent Subgraphs

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

[1]	王杰, 徐祥, 罗晓丹, 张萌, 黄澈, 洪冠中, 汪翔. 基于集成学习的巢湖面雨量计算方法[J]. 计算机与现代化, 2023, 0(09): 38-43.
[2]	龚云翔, 袁仕芳, 刘付谦. 基于集成学习与不平衡数据的返贫预测[J]. 计算机与现代化, 2022, 0(04): 12-16.
[3]	王磊, 宋波. 基于ADE-Stacking的心力衰竭非计划性再入院风险预测模型[J]. 计算机与现代化, 2022, 0(01): 23-27.
[4]	王继民, 季昌政, 李家欢, 曹颖. 基于集成学习的中小河流洪水预报[J]. 计算机与现代化, 2021, 0(05): 51-58.
[5]	王海, 江峰, 杜军威, 赵军. 过采样与集成学习方法在软件缺陷预测中的对比研究[J]. 计算机与现代化, 2020, 0(06): 83-.
[6]	李科心, 李静, 邵佳炜, 肖屹. 多层次序列集成的高维数值型异常检测[J]. 计算机与现代化, 2020, 0(06): 73-.
[7]	刘树艺，李静，胡春，王伟. 基于卷积神经网络与集成学习的交通标志识别[J]. 计算机与现代化, 2019, 0(12): 67-.
[8]	顾陈楠,曾晓勤 . 基于3D卷积神经网络的动态手势识别[J]. 计算机与现代化, 2019, 0(11): 75-.
[9]	乔媛，廖小平，邵开霞. 基于跳跃显露模式挖掘算法的癌症分类[J]. 计算机与现代化, 2018, 0(05): 100-.
[10]	雷武1,2，廖闻剑2，彭艳兵2. 基于随机森林与LambdaMART的搜索排序模型[J]. 计算机与现代化, 2017, 0(3): 54-.
[11]	李瑞1，袁小玲2. 半动态集成选择分类方法[J]. 计算机与现代化, 2015, 0(2): 48-.