Central Concept and Its Application in Rule Extraction

doi:10.3778/j.issn.1673-9418.2001010

Abstract

Abstract:

Rule extraction of decision information system is one of the important research contents of data analysis. Formal concept analysis is efficient for data analysis and information processing. Based on formal concept, com-prehensive concepts and central concepts are defined in this paper, and then the algorithm for concise rule extraction is proposed. In this process, the decision attributes of the formal decision context take participate in the generation of the concepts. After removing redundant comprehensive concepts at each level, the rest parts are central concepts and they are the decision rules. The central concepts reflect the implication relationship between conditional attributes and decision attributes in information systems, and make formal concepts with richer knowledge. Meanwhile they also effectively combine decision rules with concepts together. The corresponding Hasse diagram is more meaningful than the traditional one. The proposed algorithm avoids the complexity of traditional methods which have to generate conditional concepts and decision concepts respectively and then to get rules by complex computation. Finally, the effectiveness and correctness of the algorithm are verified by case analysis and comparative experiments with UCI datasets.

Key words: decision information system, comprehensive concept, central concept, rule extraction

摘要：

决策信息系统的规则提取是数据分析的研究内容之一。形式概念分析是一种数据分析与信息处理的方法。从决策形式背景出发，定义综合概念以及中心概念，提出了一种在生成中心概念过程中进行规则提取的算法。在此过程中决策形式背景的决策属性参与整体概念的生成，在每一层生成的综合概念中去掉冗余综合概念之后，剩余的中心概念即为获得的决策规则。中心概念体现出信息系统中条件属性与决策属性之间的关系，给予概念更丰富的关联知识的含义，同时也实现了决策规则与形式概念之间的有效结合，所形成的概念Hasse图意义丰富而明确。该算法避免了传统方法中分别生成条件概念与决策概念，再根据它们之间的关系确定决策规则的过程复杂性。通过实例分析与基于UCI数据集上的对比实验说明了该算法的正确性与有效性。

关键词: 决策信息系统, 综合概念, 中心概念, 规则提取

WEN Xin, YAN Xinyi, CHEN Zehua. Central Concept and Its Application in Rule Extraction[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(11): 1967-1974.

温馨，闫心怡，陈泽华. 中心概念及其在规则提取中的应用[J]. 计算机科学与探索, 2020, 14(11): 1967-1974.

References

[1] Wang G Y. Rough set theory and knowledge acquisition[M]. Xi??an: Xi??an Jiaotong University Press, 2001. 王国胤. Rough集理论与知识获取[M]. 西安: 西安交通大学出版社, 2001.
[2] Wille R. Restructuring lattice theory: an approach based on hierarchies of concepts[C]//Proceedings of the NATO Advanced Study Institute Held at Banff, Canada, Aug 28-Sep 12, 1981. Berlin, Heidelberg: Springer, 1981: 445-470.
[3] Qin L Z, Li J H, Wang Y Y. Concept lattice based knowledge discovery and its application to analysis of employment data in universities[J]. Journal of Shandong University (Natural Science), 2015, 50(12): 58-64. 覃丽珍, 李金海, 王扬扬. 基于概念格的知识发现及其在高校就业数据分析中的应用[J]. 山东大学学报(理学版), 2015, 50(12): 58-64.
[4] Niu J J, Fan M, Li J H, et al. Knowledge discovery method for heterogeneous data based on concept lattice[J]. Computer Science, 2017, 44(9): 62-66. 牛娇娇, 范敏, 李金海, 等. 基于概念格的异构数据知识发现方法[J]. 计算机科学, 2017, 44(9): 62-66.
[5] Valverde-Albacete F J, Calabozo J M G, Pe?as A, et al. Sup-porting scientific knowledge discovery with extended, gene-ralized formal concept analysis[J]. Expert Systems with App-lications, 2015, 44: 198-216.
[6] Zhi H L, Li J H. Granule description based knowledge dis-covery from incomplete formal contexts via necessary attri-bute analysis[J]. Information Sciences, 2019, 485: 347-361.
[7] Chen Z H, Zhang Y, Xie G. Mining algorithm for concise decision rules based on granular computing[J]. Control and Decision, 2015, 30(1): 143-148. 陈泽华, 张裕, 谢刚. 基于粒计算的最简决策规则挖掘算法[J]. 控制与决策, 2015, 30(1): 143-148.
[8] Li J H, Mei C L, Kumar C A, et al. On rule acquisition in decision formal contexts[J]. International Journal of Machine Learning and Cybernetics, 2013, 4(6): 721-731.
[9] Dai J H, Tian H W, Wang W T, et al. Decision rule mining using classification consistency rate[J]. Knowledge Based Systems, 2013, 43(2): 95-102.
[10] Ren Y, Li J H, Kumar C A, et al. Rule acquisition in formal decision contexts based on formal, object-oriented and property-oriented concept lattices[J]. The Scientific World Journal, 2014: 685362.
[11] Qin K Y, Li B, Pei Z. Attribute reduction and rule acquisition of formal decision context based on object (property) oriented concept lattices[J]. International Journal of Machine Learning and Cybernetics, 2019, 10(10): 2837-2850.
[12] Shao M W, Leung Y, Wu W Z, et al. Rule acquisition and comprehensiveity reduction in formal decision contexts[J]. International Journal of Approximate Reasoning, 2014, 55(1): 259-274.
[13] Zhang J, Wei L. Rules acquisition and attribute reduction of ordered formal decision contexts[J]. Pattern Recognition and Artificial Intelligence, 2016, 29(11): 976-984. 张菁, 魏玲. 序决策形式背景的规则提取及属性约简[J]. 模式识别与人工智能, 2016, 29(11): 976-984.
[14] Li J H, Wu W Z, Deng S. Multi-scale theroy in formal concept analysis[J]. Journal of Shandong University (Natural Science), 2019, 54(2): 34-44. 李金海, 吴伟志, 邓硕. 形式概念分析的多粒度标记理论[J]. 山东大学学报(理学版), 2019, 54(2): 34-44.
[15] Li J H, Li Y F, Mi Y L, et al. Meso-granularity labeled method for multi-granularity formal concept analysis[J]. Journal of Computer Research and Development, 2020, 57(2): 447-458. 李金海, 李玉斐, 米允龙, 等. 多粒度形式概念分析的介粒度标记方法[J]. 计算机研究与发展, 2020, 57(2): 447-458.
[16] Shao X Y, Li Y, Li L H. Transformation of no-commitment decision in coordination decision information system[J]. Jour-nal of North China University of Science and Technology (Natural Science Edition), 2018, 40(2): 100-105. 邵晓艳, 李言, 李丽红. 协调决策信息系统中不承诺决策的转化[J]. 华北理工大学学报(自然科学版), 2018, 40(2): 100-105.
[17] Chen Z H, Zhang Y, Xie G. CrC method of rule acquisition for inconsistent decision table[J]. Control and Decision, 2015, 30(4): 709-714. 陈泽华, 张裕, 谢刚. 不一致决策表规则获取的粒计算方法[J]. 控制与决策, 2015, 30(4): 709-714.
[18] Li J H, Mei C L, Xu W H, et al. Concept learning via gra-nular computing: a cognitive viewpoint[J]. Information Sci-ences, 2015, 298: 447-467.