Research on construction methods and algorithms of three-way concept lattices based on isomorphism theory
QIAN Ting1,3, ZHAO Siyu2,3, WANG Juntao1
1.College of Science, Xi’an Shiyou University, Xi’an 710065, China 2.College of Mathematics and Information Science, Xianyang Normal University, Xianyang 712000,Shaanxi Province, China 3.Institute of Concepts, Cognition and Intelligence, Northwest University, Xi’an 710127, China
Abstract：Three-way concept analysis has now become an effective tool for data analysis and knowledge discovery. In this paper, the isomorphism relationship between three-way concept lattice and concept lattice are discussed by studying the characteristics of formal context. And furthermore, the construction methods of three way concept lattice are studied. Firstly, the definitions of dual attribute and attribution dual context are given. Secondly, it is proved that three-way concept lattice and concept lattice of the dual formal context are isomorphic. Furthermore, the dual attribute and attribute dual context are generalized, and then the dual intersectable attribute and attribute dual intersectable context are given. It is also proved that three-way concept lattice and concept lattice of attribute dual intersectable context are isomorphic. Finally, two algorithms to determine the attribute dual context and attribute dual intersectable context and the construction methods of three-way concept lattice are proposed.
钱婷, 赵思雨, 王军涛. 基于同构理论的三支概念格的构造方法与算法研究[J]. 浙江大学学报（理学版）, 2020, 47(3): 322-328.
QIAN Ting, ZHAO Siyu, WANG Juntao. Research on construction methods and algorithms of three-way concept lattices based on isomorphism theory. Journal of ZheJIang University(Science Edition), 2020, 47(3): 322-328.
1 WILLE R . Restructuring lattice theory: An approach based on hierarchies of concepts[J]. Ordered Sets, 1982,83: 445-470.DOI:10.1007/978-94-009-7798-3_15 2 洪文学, 栾景民, 张涛, 等 . 基于偏序结构理论的知识发现方法[J]. 燕山大学学报, 2014, 38(5): 394-402. HONG W X, LUAN J M, ZHANG T, et al . A new method for knowledge discovery based on partial ordered structure theory[J]. Journal of Yanshan University, 2014, 38(5): 394-502.DOI:10.3969/j.issn.1007-791X.2014.05.004 3 GANAPATHY V, KING D, JAEGER T, et al . Mining security sensitive operations in legacy code using concept analysis[C]//The 29th International Conference on Software Engineering. Minneapolis:IEEE, 2007:458-467. DOI:10.1109/icse.2007.54 4 TONELLA P . Using a concept lattice of decomposition slices for program understanding and impact analysis[J]. IEEE Transactions on Software Engineering, 2003, 29(6): 495-509.DOI:10.1109/tse.2003.1205178 5 YAO Y Y . An outline of a theory of three-way decisions[C]//7th International Conference Rough Set and Knowledge Technology. Berlin: Springer,2012:1-17. DOI:10.1007/978-3-642-32115-3_1 6 QI J J, WEI L, YAO Y Y . Three-way formal concept analysis[C]// 9th International Conference. Rough Set and Knowledge Technology Switzerland: Springer, 2014:732-741. DOI:10.1007/978-3-319-11740-9_67 7 QI J J, QIAN T, WEI L .The connections between three-way and classical concept lattices[J]. Knowledge-Based Systems, 2016, 91: 143-151.DOI:10.1016/j.knosys.2015.08.006 8 QIAN T, WEI L, QI J J . Constructing three-way concept lattices based on apposition and subposition of formal contexts[J].Knowledge-Based Systems,2017,116: 39-48. DOI:10.1016/j.knosys.2016.10.033 9 祁建军, 汪文威 . 多线程并行构建三支概念[J]. 西安交通大学学报, 2017,51(3): 116-121. QI J J, WANG W W . A multithreaded parallel algorithm for constructing three-way concepts[J]. Journal of Xi’an Jiaotong University, 2017,51(3): 116-121. 10 REN R S, WEI L . The attribute reductions of three-way concept lattices[J]. Knowledge-Based Systems, 2016, 99:92-102. DOI:10.1016/j.knosys.2016.01.045 11 LI M Z, WANG G Y . Approximate concept construction with three-way decisions and attribute reduction in incomplete contexts[J]. Knowledge-Based Systems, 2016, 91: 165-178.DOI:10.1016/j.knosys.2015.10.010 12 SHIVHAREL R, CHERUKURI A K . Three-way conceptual approach for cognitive memory functionalities[J]. International Journal of Machine Learning and Cybernetics, 2017, 8(1):21-34. 13 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.DOI:10.1016/j.ins.2016.04.051 14 王志海, 胡可云, 胡学钢, 等 . 概念格上规则提取的一般算法与渐进式算法[J]. 计算机学报, 1999, 22(1): 66-70. DOI:10.3321/j.issn:0254-4164.1999.01.010 WANG Z H, HU K Y, HU X G,et al . General and incremental algorithms of rule extraction based on concept lattice[J]. Chinese Journal of Computers, 1999, 22(1): 66-70.DOI:10.3321/j.issn:0254-4164.1999.01.010 15 谢志鹏, 刘宗田 . 概念格的快速渐进式构造算法[J]. 计算机学报, 2002, 25(5): 490-496.DOI:10.3321/j.issn:0254-4164.2002.05.006 XIE Z P, LIU Z T . A fast incremental algorithm for building concept lattice[J]. Chinese Journal of Computers, 2002, 25(5): 490-496.DOI:10.3321/j.issn:0254-4164.2002.05.006 16 ZOU L G, ZHANG Z P, LONG J . A fast incremental algorithm for constructing concept lattices[J]. Expert Systems with Applications, 2015, 42(9): 4474-4481. DOI:10.1016/j.eswa.2015.01.044 17 智慧来, 李金海 . 基于必然属性分析的粒描述[J]. 计算机学报, 2018, 41(12): 2702-2719. DOI:10.11897/SP.J.1016.2018.02702 ZHI H L, LI J H . Granule description based on necessary attribute analysis[J]. Chinese Journal of Computers, 2018, 41(12): 2702-2719. DOI:10.11897/SP.J.1016.2018.02702 18 郝晨, 范敏, 李金海, 等 . 多标记背景下基于粒标记规则的最优标记选择[J]. 模式识别与人工智能, 2016, 29(3): 272-280.DOI:10.16451/j.cnki.issn1003-6059.201603009 HAO C, FAN M, LI J H, et al . Optimal scale selection in multi-scale contexts based on granular scale rules[J]. Pattern Recognition and Artificial Intelligence, 2016, 29(3): 272-280.DOI:10.16451/j.cnki.issn1003-6059.201603009 19 YU H Y, LI Q G, CAI M J . Characteristics of three-way concept lattices and three-way rough concept lattices[J]. Knowledge-Based Systems, 2018, 146: 181-189. DOI:10.1016/j.knosys.2018.02.0072018, 146: 181-189.DOI:10.1016/j.knosys.2018.02.007 20 GANTER B, WILLE R . Formal Concept Analysis:Mathematical Fundations[M]. Berlin: SpringerVerlag, 1999.
2020, Vol. 47 
