Please wait a minute...
浙江大学学报（理学版）
Journal of Zhejiang University (Science Edition)  2020, Vol. 47 Issue (3): 322-328    DOI: 10.3785/j.issn.1008-9497.2020.03.009
Mathematics and Computer Science     
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
Download: HTML ( )    PDF(1145KB)
Export: BibTeX | EndNote (RIS)      

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.

Key words： concept lattice      three-way concept lattice      isomorphism      formal context      algorithm     
Received: 31 July 2019      Published: 25 June 2020
CLC:  O29  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
QIAN Ting
ZHAO Siyu
WANG Juntao
Cite this article:

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.

URL:

https://www.zjujournals.com/sci/EN/Y2020/V47/I3/322


基于同构理论的三支概念格的构造方法与算法研究

三支概念分析理论目前已经发展成为数据分析与知识发现的有效工具。主要通过形式背景特征的研究, 讨论三支概念格与概念格的同构关系, 进一步研究了三支概念格的构造方法。首先给出了对偶属性、属性对偶背景的定义, 并证明了在对偶背景下三支概念格与概念格是同构的。其次, 推广了对偶属性、属性诱导的对偶背景, 给出对偶可交属性及属性对偶可交背景的定义, 同时, 证明了在对偶可交背景下，三支概念格与概念格是同构的。最后基于上述理论, 给出了判定属性对偶背景与属性对偶可交背景的2种算法以及三支概念格的构造方法。

关键词： 概念格,  三支概念格,  同构,  形式背景,  算法 
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.
[1] Rongwei HUA, Hong PAN, Tianhai YAN. Scheduling problem with flexible periodic maintenance activities on two parallel machines[J]. Journal of Zhejiang University (Science Edition), 2023, 50(3): 303-309.
[2] Ran XIAO, Xinlei AN, Huimin QI, Shuai QIAO. Bifurcation analysis and parameter identification of HR neurons under electric field[J]. Journal of Zhejiang University (Science Edition), 2022, 49(6): 691-697.
[3] Maoqun YAO, Jie FENG, Zhiqiang LIU, Conghui LI. A realization algorithm of n-variable functions based on RTD programmable logic gate[J]. Journal of Zhejiang University (Science Edition), 2022, 49(4): 474-480.
[4] Ying ZHONG,Song WANG,Hao WU,Zepeng CHENG,Xuejun LI. SEMMA-Based visual exploration of cyber security event[J]. Journal of Zhejiang University (Science Edition), 2022, 49(2): 131-140.
[5] Qiuyi TANG,Chao WANG,Zhenhong DU,Feng ZHANG,Renyi LIU. Server-side cache replacement algorithm based on spatiotemporal aging model for tiles[J]. Journal of Zhejiang University (Science Edition), 2022, 49(2): 210-218.
[6] YANG Yiwei, KUANG Xiaoyun, HUANG Kaitian, HONG Chao, ZHENG Changli, JIANG Xiaowen. Simulation test case suite reduction based on Memetic algorithm[J]. Journal of Zhejiang University (Science Edition), 2021, 48(3): 331-337.
[7] WANG Yingzhi, SHEN Yajie, WANG Lijun. The causes analysis of traffic accident black spots based on improved interest measurement and Apriori algorithm[J]. Journal of Zhejiang University (Science Edition), 2021, 48(3): 349-355.
[8] ZENG Liang. Grey GM(1,1|sin) power model based on oscillation sequences and its application[J]. Journal of Zhejiang University (Science Edition), 2019, 46(6): 697-704.
[9] XU Feng, LI Xiaohua. A fast algorithm for detecting rotation symmetric logical function with don’t-care-terms.[J]. Journal of Zhejiang University (Science Edition), 2019, 46(5): 574-578.
[10] JIA Yujie, DU Zhenhong, ZHANG Feng, LIU Renyi. Land use performance evaluation based on attribute weight optimization algorithm and analysis of land use performance differentiation.[J]. Journal of Zhejiang University (Science Edition), 2019, 46(5): 610-618.
[11] LIN Geng. A hybrid binary artificial bee colony algorithm for the max-bisection problem.[J]. Journal of Zhejiang University (Science Edition), 2019, 46(5): 556-564.
[12] LI Jing, ZHANG Yulin. A new algorithm for aggregating interval information of multistage decision making problems and its application[J]. Journal of Zhejiang University (Science Edition), 2019, 46(4): 439-444.
[13] YU Qi, WANG Lunyao, XIA Yinshui. A fast area optimization method using library-free mapping[J]. Journal of Zhejiang University (Science Edition), 2018, 45(6): 733-740.
[14] FENG Hailin, LI Xiuxiu. Residual life prediction based on a stochastic effect Wiener degradation model[J]. Journal of Zhejiang University (Science Edition), 2018, 45(6): 679-684,693.
[15] ZHOU Jie, WANG Guijun. Construction and algorithm of fuzzy systems based on Bernstein polynomials as a rule's consequence.[J]. Journal of Zhejiang University (Science Edition), 2018, 45(4): 394-399.