Study of Implication Representation Based on Decision Implication

doi:10.3778/j.issn.1673-9418.2006064

Abstract

Abstract:

Formal concept analysis can use concept lattice and (attribute) implication to visualize and represent knowledge. Decision implication is a special implication, and the study of decision implication is to establish and study one or more closed subsystems in implications, including decision implication subsystem and corresponding semantic and syntactic subsystems. In order to further clarify the relationship between implications and decision implications, it is studied whether the implication systems can be obtained from these decision implications subsystems. In fact, if implications can be deduced from decision implications, the studies on implications and canonical basis can be reduced to the studies of decision implications and decision implication canonical basis. Firstly, some sufficient and necessary conditions are given to determine whether implications can be represented by decision implication. Secondly, an example is given to show that there are some implications that cannot be represented by decision implications, and thus the representation of implications is further divided into direct and indirect representations. Finally, by studying the characteristics of the implication that cannot be directly represented when there is only one decision attribute in decision contexts, a sufficient and necessary condition is presented to determine whether implications cannot be directly represented by decision implication, and a generation method is also designed to generate the implications that cannot be directly represented. This study provides a new perspective for the study of implications and canonical basis, and also forms a foundation for further theoretical study on formal concept analysis.

Key words: formal concept analysis (FCA), concept lattice, implication, decision implication

摘要：

形式概念分析能够使用概念格和（属性）蕴涵来对知识进行可视化和表示。决策蕴涵是一种特殊的蕴涵，而决策蕴涵的研究就是在蕴涵中建立并研究一个/多个封闭的子系统（包括决策蕴涵子系统及相应的语义和语构子系统）。为了进一步厘清蕴涵和决策蕴涵之间的关系，对由决策蕴涵子系统能不能得到整个蕴涵系统进行了研究。事实上，如果蕴涵可以由决策蕴涵推出，那么关于蕴涵和规范基的研究就可以转化为决策蕴涵和决策蕴涵规范基的研究。首先给出了蕴涵可以由决策蕴涵表示的充要条件；接着通过实例表明，存在一些蕴涵不可由决策蕴涵表示，因此进一步区分了直接表示和间接表示；最后通过研究决策背景中只有一个决策属性时不可被直接表示的蕴涵所具有的特点，给出了蕴涵不可由决策蕴涵直接表示的充要条件，并给出了不可被直接表示蕴涵的生成方法。这种研究为蕴涵和规范基的研究提供了一种新视角，同时也为形式概念分析更深入的理论研究工作奠定了基础。

关键词: 形式概念分析（FCA）, 概念格, 蕴涵, 决策蕴涵

WANG Yali, ZHAI Yanhui, ZHANG Shaoxia, JIA Nan, LI Deyu. Study of Implication Representation Based on Decision Implication[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(7): 1322-1331.

王亚丽, 翟岩慧, 张少霞, 贾楠, 李德玉. 蕴涵的决策蕴涵表示研究[J]. 计算机科学与探索, 2021, 15(7): 1322-1331.

References

[1] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[C]//LNCS 5548: Proceedings of the 2009 International Conference on Formal Concept Analysis, Darmstadt, May 21-24, 2009. Berlin, Heidelberg: Springer, 2009: 314-339.
[2] QI J J, QIAN T, WEI L. The connections between three-way and classical concept lattices[J]. Knowledge-based Systems, 2016, 91: 143-151.
[3] XU W H, PANG J Z, LUO S Q. A novel cognitive system model and approach to transformation of information granules[J]. International Journal of Approximate Reasoning, 2014, 55(3）: 853-866.
[4] XU W H, LI W T. Granular computing approach to two-way learning based on formal concept analysis in fuzzy datasets[J]. IEEE Transactions on Cybernetics, 2016, 46(2): 366-379.
[5] LI J H, HUANG C C, QI J J, et al. Three-way cognitive concept learning via multi-granularity[J]. Information Sciences, 2017, 378: 244-263.
[6] ZHI H L, LI J H. Granule description based on formal concept analysis[J]. Knowledge-Based Systems, 2016, 104: 62-73.
[7] LI J H, MEI C L, XU W H, et al. Concept learning via granular computing: a cognitive viewpoint[J]. Information Sciences, 2015, 298: 447-467.
[8] ISHIGURE H, MUTOH A, MATSUI T, et al. Concept lattice reduction using attribute inference[C]//Proceedings of the IEEE 4th Global Conference on Consumer Electronics, Osaka, Oct 27-30, 2015. Piscataway: IEEE, 2015: 108-111.
[9] KUMAR C A, DIAS S M, VIEIRA N J. Knowledge reduction in formal contexts using non-negative matrix factorization[J]. Mathematics and Computers in Simulation, 2015, 109: 46-63.
[10] SHAO M W, LEUNG Y, WU W Z. Rule acquisition and complexity reduction in formal decision contexts[J]. International Journal of Approximate Reasoning, 2014, 55(1): 259-274.
[11] WEI L, QI J J, ZHANG W X. Attribute reduction theory of concept lattice based on decision formal contexts[J]. Science in China: Series E Information Sciences, 2008, 38(2): 195-208.
魏玲, 祁建军, 张文修. 决策形式背景的概念格属性约简[J]. 中国科学: E辑信息科学, 2008, 38(2): 195-208.
[12] LI J H, KUMAR C A, MEI C L, et al. Comparison of reduction in formal decision contexts[J]. International Journal of Approximate Reasoning, 2017, 80: 100-122.
[13] ZHANG W X, WEI L, QI J J. Attribute reduction theory and approach to concept lattice[J]. Science in China: Series E Information Sciences, 2005, 35(6): 628-639.
张文修, 魏玲, 祁建军. 概念格的属性约简理论与方法[J]. 中国科学: E辑信息科学, 2005, 35(6): 628-639.
[14] WU W Z, LEUNG Y, MI J S. Granular computing and knowledge reduction in formal contexts[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21: 1461-1474.
[15] MA Y, ZHANG X D, CHI C Y. Compact dependencies and intent waned values[J]. Journal of Software, 2011, 22(5): 962-972.
马垣, 张学东, 迟呈英. 紧致依赖与内涵亏值[J]. 软件学报, 2011, 22(5): 962-972.
[16] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin, Heidelberg: Springer, 1999.
[17] ZHAI Y H, LI D Y, QU K S. Fuzzy decision implications[J]. Knowledge-Based Systems, 2013, 37: 230-236.
[18] ZHAI Y H, LI D Y, QU K S. Fuzzy decision implication canonical basis[J]. International Journal of Machine Learning and Cybernetics, 2018, 9(11): 1909-1917.
[19] QU K S, ZHAI Y H, LIANG J Y, et al. Study of decision implications based on formal concept analysis[J]. International Journal of General Systems, 2007, 36(2): 147-156.
[20] ZHANG S X, LI D Y, ZHAI Y H, et al. A comparative study of decision implication, concept rule and granular rule[J]. Information Sciences, 2020, 508: 33-49.
[21] DUQUENNE V, GUIGUES J L. Famille minimale d’implications informatives résultant d??un tableau de données binaires[J]. Mathématiques et Sciences Humaines, 1986, 24(95): 5-18.
[22] QU K S, ZHAI Y H. Generating complete set of implications for formal contexts[J]. Knowledge-Based Systems, 2008, 21: 429-433.
[23] ZHAI Y H, LI D Y, QU K S. Decision implications: a logical point of view[J]. International Journal of Machine Learning and Cybernetics, 2014, 5(4): 509-516.
[24] STUMME G, TAOUIL R, BASTIDE Y, et al. Fast computation of concept lattices using data mining techniques[C]//Proceedings of the 7th International Workshop on Knowledge Representation Meets Databases, Berlin, Aug 21, 2000: 129-139.
[25] LI D Y, ZHANG S X, ZHAI Y H. Method for generating decision implication canonical basis based on true premises[J]. International Journal of Machine Learning and Cybernetics, 2017, 8(1): 57-67.
[26] JIA N, ZHANG S X, ZHAI Y H, et al. Study of inference rules and deduction process on decision implications[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(2): 344-352.
贾楠, 张少霞, 翟岩慧, 等. 决策蕴涵上的推理规则和推理过程研究[J]. 计算机科学与探索, 2020, 14(2): 344-352.
[27] ZHAI Y H, LI D Y, QU K S. Canonical basis for decision implication[J]. Acta Electronica Sinica, 2015, 43(1): 18-23.
翟岩慧, 李德玉, 曲开社. 决策蕴涵规范基[J]. 电子学报, 2015, 43(1): 18-23.
[28] ZHAI Y H, LI D Y, QU K S. Decision implication canonical basis: a logical perspective[J]. Journal of Computer and System Sciences, 2015, 81(1): 208-218.
[29] MAIER D. The theory of relational data bases[M]. Rockville: Computer Science Press, 1983.
[30] ZHAI Y H, LI D Y. Knowledge structure preserving fuzzy attribute reduction in fuzzy formal context[J]. International Journal of Approximate Reasoning, 2019, 115: 209-220.
[31] ZHAI Y H, LI D Y, ZHANG J. Variable decision know-ledge representation: a logical description[J]. Journal of Computational Science, 2018, 25: 161-169.