针对大规模决策形式背景中决策规则的提取问题,提出了一种将频繁闭项集与决策形式背景相结合以提取无冗余决策规则的新算法.该算法结合了深度优先搜索的思想以及概念格中概念节点之间的父子关系,改进了概念格中频繁闭项集的挖掘算法,得到的频繁决策概念格实现了对一定规模的数据库的压缩,同时得到无冗余决策规则.算法分析表明,该算法复杂度较低,更适用于大规模数据集中挖掘无冗余决策规则.
Aiming at the problem of extraction of decision rules in mass decision formal context, this paper proposes a novel algorithm by combining frequent closed itemsets and decision formal context to extract no redundant decision rules.The algorithm combines the idea of depth-first searches(DFS)and the relationship of conceptual node in concept lattice and improves an existed algorithm of mining frequent closed itemsets in the concept lattice.Using this algorithm,the frequent decision concept lattice of the decision formal context is obtained so that the huge database is compressed. Meanwhile, no redundant decision rules are extracted. After analysis,this algorithm has a lower complexity and is easy to mine decision rules in decision formal context.
[1] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M].Berlin:Springer-Verlag, 1999.
[2] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M] //Ordered Sets. Dordrecht: Springer.Netherlands, 1982: 445-470. DOI:10.1007/978-94-009-7798-3_15.
[3] ZHANG Z X, LI Q G, ZHANG N. M-Algebraic lattices in formal concept analysis[J]. Math Struct Comp Sci, 2019, 29(10): 1556-1574. DOI:10.1017/s0960129519000124.
[4] LI J H, REN Y, MEI C L, et al. A comparative study of multigranulation rough sets and concept lattices via rule acquisition[J]. Knowl-Based Syst, 2016, 91: 152-164. DOI:10.1016/j.knosys.2015.07.024.
[5] SUMANGALI K, CH A K. Concept lattice simplification in formal concept analysis using attribute clustering[J]. J Ambient Intell Human Comput, 2019, 10(6): 2327-2343. DOI:10.1007/s12652-018-0831-2.
[6] SINGH P K. Complex fuzzy concept lattice[J]. Neural Process Lett, 2019, 49(3): 1511-1526. DOI:10.1007/s11063-018-9884-7.
[7] PRISS U. Formal concept analysis in information science[J]. Ann Rev Info Sci Tech, 2007, 40(1): 521-543.DOI:10.1002./aris.1440400120.
[8] AGRAWAL R, IMIELIN 'SKI T, SWAMI A. Mining association rules between sets of items in large databases[C].Proceedings of the 1993 ACM SIGMOD international conference on Management of data. New York: ACM Press, 1993: 207-216. DOI:10.1145/170035.170072.
[9] 付沙,周航军.关联规则挖掘Apriori算法的研究与改进[J].微电子学与计算机,2013, 30(9): 110-114. DOI:10.19304/j.c-nki.issn1000-7180.2013.09.028.
[10] NAÏM H, AZNAG M, DURAND N, et al. Semantic pattern mining based web service recommendation[M]. Cham: Springer International Publishing, 2016: 417-432.
[11] JANOSTIK R, KONECNY J. General framework for consistencies in decision contexts[J]. Inf Sci, 2020, 530: 180-200. DOI:10.1016/j.ins.2020.02.045.
[12] DAMOUR G, NAVAS M L, GARNIER E. A revised trait-based framework for agroecosystems including decision rules[J]. J Appl Ecol, 2018, 55(1): 12-24. DOI:10.1111/1365-2664.12986..
[13] 翟悦,何丹丹.基于概念格的频繁闭项集挖掘方法[J].计算机应用与软件,2014,31(11):54-57. DOI:10.3969/j.issn.1000386x.2014.11.013.
[14] 朱坤,黄瑞章,张娜娜.一种基于MapReduce模型的高效频繁项集挖掘算法[J].计算机科学,2017, 44(7): 31-37. DOI:10.11896/j.issn.1002-137X.2017.07.006.
[15] 罗明,孟传伟,黄海量.基于加权频繁模式树的通信网络告警规则挖掘方法[J].计算机工程,2016, 42(4): 190-196. DOI:10.3969/j.issn.1000-3428.2016.04.034.
[16] 徐嘉莉,杨洪军,赵茂娟,等.一种基于位运算的频繁闭项集挖掘算法[J].计算机应用研究, 2013, 30(11): 3280-3282, 3286. DOI:10.3969/j.issn.1001-3695.2013.11.018.
[17] 魏玲,祁建军,张文修.决策形式背景的概念格属性约简[J].中国科学:E辑,2008, 38(2): 195-208.
[18] LI J H, MEI C L, KUMAR C A, et al. On rule acquisition in decision formal contexts[J]. Int J Mach Learn & Cyber, 2013,4(6): 721-731. DOI:10.1007/s13042-013-0150-z.
[19] 张菁,魏玲.序决策形式背景的规则提取及属性约简[J].模式识别与人工智能,2016, 29(11): 976-984. DOI:10.16451/j.cnki.issn1003-6059.201611003.
[20] 翟岩慧,李德玉,曲开社.决策蕴涵规范基[J].电子学报, 2015, 43(1): 18-23. DOI:10.3969/j.issn.0372-2112.2015.01.004.
[21] LI J Y, WANG X, WU W Z, et al. Attribute reduction in inconsistent formal decision contexts based on congruence relations[J]. Int J Mach Learn & Cyber, 2017, 8(1): 81-94. DOI:10.1007/s13042-016-0586-z.
[22] 刘琳,钱婷,魏玲.基于属性导出三支概念格的决策背景规则提取[J].西北大学学报(自然科学版),2016, 46(4): 481-487. DOI:10.16152/j.cnki.xdxbzr.2016-04-003.
[23] 刘琳,魏玲,钱婷.决策形式背景中具有置信度的三支规则提取[J].山东大学学报(理学版),2017, 52(2): 101-110. DOI:10.6040/j.issn.1671-9352.0.2016.384.
[24] 张文修,魏玲,祁建军.概念格的属性约简理论与方法[J].中国科学:E辑,2005, 35(6): 628-639. DOI:10.3321/j.issn:1006-9275.2005.06.006.
[25] PASQUIER N, BASTIDE Y, TAOUIL R, et al. Efficient mining of association rules using closed itemset lattices[J].1999, 24(1): 25-46. DOI:10.1016/s0306-4379(99)00003-4.
[26] 谢志鹏,刘宗田.概念格的快速渐进式构造算法[J].计算机学报,2002, 25(5): 490-496. DOI:10.3321/j.issn:0254-4164.2002.05.006.
[27] ZOU L G, ZHANG Z P, LONG J. A fast incremental algorithm for constructing concept lattices[J]. Expert Syst Appl, 2015, 42(9): 4474-4481. DOI:10.1016/j.eswa.2015.01.044.
[28] ZAKI M J, HSIAO C J. Efficient algorithms for mining closed itemsets and their lattice structure[J]. IEEE Trans Knowl Data Eng, 2005, 17(4): 462-478. DOI:10.1109/tkde.2005.60. (
