An Ensemble Classification Algorithm Based on Frequent Subgraphs

doi:10.3969/j.issn.1006-2475.2017.01.006

Abstract

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

CLC Number:

TP391

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

References

[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.