Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2020, Vol. 47 Issue (3): 322-328    DOI: 10.3785/j.issn.1008-9497.2020.03.009
数学与计算机科学     
基于同构理论的三支概念格的构造方法与算法研究
钱婷1,3, 赵思雨2,3, 王军涛1
1.西安石油大学 理学院, 陕西西安 710065
2.咸阳师范学院 数学与信息科学学院, 陕西咸阳 712000
3.西北大学 概念认知与智能研究中心, 陕西西安 710127
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
 全文: PDF(1145 KB)   HTML  
摘要： 三支概念分析理论目前已经发展成为数据分析与知识发现的有效工具。主要通过形式背景特征的研究, 讨论三支概念格与概念格的同构关系, 进一步研究了三支概念格的构造方法。首先给出了对偶属性、属性对偶背景的定义, 并证明了在对偶背景下三支概念格与概念格是同构的。其次, 推广了对偶属性、属性诱导的对偶背景, 给出对偶可交属性及属性对偶可交背景的定义, 同时, 证明了在对偶可交背景下，三支概念格与概念格是同构的。最后基于上述理论, 给出了判定属性对偶背景与属性对偶可交背景的2种算法以及三支概念格的构造方法。
关键词： 概念格;  三支概念格;  同构;  形式背景;  算法    
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
收稿日期: 2019-07-31 出版日期: 2020-06-25
CLC:  O29  
基金资助: 国家自然科学基金资助项目(11801440, 61772021, 61976244)； 陕西省创新人才推进计划——青年科技新星项目(2017KJXX -60)； 陕西省自然科学基础研究计划项目(2019JQ-816)； 陕西省教育厅科研计划资助项目(19JK0929)； 咸阳师范学院专项科研基金项目(XSYK180245).
作者简介: 钱婷(1985—), ORCID:http://orcid.org/0000-0001-5872-7024, 女, 博士, 讲师, 主要从事形式概念分析、粗糙集、三支决策、拓扑学等研究，E-mail: qiant2000@ 126.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
钱婷
赵思雨
王军涛

引用本文:

钱婷, 赵思雨, 王军涛. 基于同构理论的三支概念格的构造方法与算法研究[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.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2020.03.009    或    https://www.zjujournals.com/sci/CN/Y2020/V47/I3/322

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] 华荣伟, 潘虹, 严甜海. 可移动周期性维护排序问题的算法研究[J]. 浙江大学学报（理学版）, 2023, 50(3): 303-309.
[2] 肖冉, 安新磊, 祁慧敏, 乔帅. 电场作用下HR神经元的分岔分析及参数辨识[J]. 浙江大学学报（理学版）, 2022, 49(6): 691-697.
[3] 姚茂群, 冯杰, 刘志强, 李聪辉. 基于RTD可编程逻辑门的n变量函数实现算法[J]. 浙江大学学报（理学版）, 2022, 49(4): 474-480.
[4] 钟颖,王松,吴浩,程泽鹏,李学俊. 基于SEMMA的网络安全事件可视探索[J]. 浙江大学学报（理学版）, 2022, 49(2): 131-140.
[5] 汤求毅,王超,杜震洪,张丰,刘仁义. 基于时空老化模型的服务端瓦片缓存置换算法[J]. 浙江大学学报（理学版）, 2022, 49(2): 210-218.
[6] 杨祎巍, 匡晓云, 黄开天, 洪超, 郑昌立, 蒋小文. 基于Memetic算法的仿真用例集约简技术[J]. 浙江大学学报（理学版）, 2021, 48(3): 331-337.
[7] 王颖志, 沈雅婕, 王立君. 基于改进兴趣度度量与Apriori算法的交通事故多发点成因分析[J]. 浙江大学学报（理学版）, 2021, 48(3): 349-355.
[8] 陆晔, 张伟, 李飞, 杜震洪, 张丰, 刘仁义. 一种基于主题时空价值的服务器端瓦片缓存算法[J]. 浙江大学学报（理学版）, 2020, 47(1): 12-19.
[9] 曾亮. 基于振荡序列的灰色GM(1,1|sin)幂模型及其应用[J]. 浙江大学学报（理学版）, 2019, 46(6): 697-704.
[10] 徐锋, 厉晓华. 检测含无关项旋转对称逻辑函数的快速算法[J]. 浙江大学学报（理学版）, 2019, 46(5): 574-578.
[11] 贾玉杰, 杜震洪, 张丰, 刘仁义. 基于属性权重优化算法的土地利用绩效评价及差异分解分析[J]. 浙江大学学报（理学版）, 2019, 46(5): 610-618.
[12] 林耿. 求解最大二等分问题的混合二进制人工蜂群算法[J]. 浙江大学学报（理学版）, 2019, 46(5): 556-564.
[13] 李静, 张玉林. 考虑多阶段决策信息集结的新算法及其应用[J]. 浙江大学学报（理学版）, 2019, 46(4): 439-444.
[14] 张彩红, 韩广国, 陈丽虹, 张惠玲. 区传递的2(v,6,1)设计与典型单群PSpn(q)[J]. 浙江大学学报（理学版）, 2018, 45(6): 661-664.
[15] 喻奇, 王伦耀, 夏银水. 基于library-free映射的电路面积快速优化算法[J]. 浙江大学学报（理学版）, 2018, 45(6): 733-740.