您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (12): 52-62.doi: 10.6040/j.issn.1671-9352.4.2022.7343

•   • 上一篇    下一篇

三支概念的恢复集

陈曜琦(),徐伟华*(),蒋宗颖   

  1. 西南大学人工智能学院, 重庆 400715
  • 收稿日期:2022-08-12 出版日期:2023-12-20 发布日期:2023-12-19
  • 通讯作者: 徐伟华 E-mail:1312941662@qq.com;chxuwh@gmail.com
  • 作者简介:陈曜琦(1998—)，女，硕士研究生，研究方向为粒计算、认知计算. E-mail: 1312941662@qq.com
  • 基金资助:
    国家自然科学基金资助项目(62376229);重庆市研究生科研创新项目(CYS21133)

Recovery set of three-way concept

Yaoqi CHEN(),Weihua XU*(),Zongying JIANG   

  1. School of Artificial Intelligence, Southwest University, Chongqing 400715, China
  • Received:2022-08-12 Online:2023-12-20 Published:2023-12-19
  • Contact: Weihua XU E-mail:1312941662@qq.com;chxuwh@gmail.com

RichHTML

2

PDF (PC)

186

摘要：

将三支形式概念分析这一工具引入到数据恢复领域，通过定义三支概念的恢复集和恢复度，研究三支概念间的隐藏信息，提出了一种有效的形式背景恢复算法。同时，针对三支概念恢复集问题，研究三支概念对形式背景二元关系的约束，设计了恢复集的合取范式化简(conjunctive normal form simplification，CNFS) 算法，进一步给出了恢复集的动态更新算法，以适应形式背景的不断变化。最后，使用UCI机器学习数据库中的数据集对CNFS算法进行了测试。实验结果表明，CNFS算法在形式背景恢复方面具有较高的准确性和有效性，同时也验证了不同概念对认知的重要程度是不同的。

关键词: 合取范式, 动态更新, 三支概念, 形式概念分析

Abstract:

The theory of three-way formal concept analysis is introduced into the field of data recovery in this paper. By defining the recovery set and recovery degree of three-way concept, it explores the hidden information from three-way concepts, and proposes an effective formal context recovery algorithm. Additionally, to solve the three-way concept recovery set problem, the constraints of three-way concept are considered on formal context binary relations, and a conjunctive normal form simplification algorithm is designed for the recovery set (CNFS). Furthermore, a dynamic update algorithm is provided for the recovery set to adapt to the continuous changes of the formal context. Finally, some numerical experiments on public datasets from the UCI perform the effectiveness of our proposed method. Experimental results indicate that the proposed algorithm has high accuracy and effectiveness in formal context recovery, and also verifies that different concepts have different important degrees in cognition.

Key words: conjunctive normal form, dynamic update, three-way concept, formal context analysis

中图分类号: 

  • TP181

表1

生物与水形式背景"

OB a1 a2 a3 a4 a5 a6 a7 a8 a9
o1 1 1 0 0 0 0 1 0 0
o2 1 1 0 0 0 0 1 1 0
o3 1 1 1 0 0 0 1 1 0
o4 1 0 1 0 0 0 1 1 1
o5 1 1 0 1 0 1 0 0 0
o6 1 1 1 1 0 1 0 0 0
o7 1 0 1 1 1 0 0 0 0
o8 1 0 1 1 0 1 0 0 0

图1

例4进行算法1的流程图"

图2

例5进行算法2的流程图"

表3

实验数据集描述"

编号 数据集 对象数 属性数 概念数
1 生物与水[35] 8 9 43
2 西瓜数据集3.0 [40] 14 7 878
3 Acuteinflammations [40] 120 6 48
4 Shuttle_landing_control [40] 15 16 2 752

表4

生物与水形式背景概念数与恢复度"

概念个数比例/% 概念个数 平均恢复度/% 最大恢复度/% 最小恢复度/%
5 2 32.14 47.22 19.44
10 4 56.53 77.78 37.50
15 6 73.28 93.06 50.00
20 9 90.83 100.00 70.83
30 13 96.56 100.00 87.50
50 21 99.58 100.00 94.44

表5

西瓜数据集3.0概念数与恢复度"

概念个数比例/% 概念个数 平均恢复度/% 最大恢复度/% 最小恢复度/%
5 44 98.27 100.00 95.75
10 88 99.94 100.00 99.35
15 132 99.99 100.00 99.67
20 176 100.00 100.00 100.00
30 236 100.00 100.00 100.00
50 439 100.00 100.00 100.00

表6

Acute inflammations概念数与恢复度"

概念个数比例/% 概念个数 平均恢复度/% 最大恢复度/% 最小恢复度/%
5 2 26.64 38.89 8.33
10 5 55.89 73.37 32.78
15 7 70.37 81.53 55.14
20 9 79.99 94.44 62.08
30 14 93.62 100.00 81.94
50 24 99.55 100.00 94.31

表7

Shuttle_landing_control概念数与恢复度"

概念个数比例/% 概念个数 平均恢复度/% 最大恢复度/% 最小恢复度/%
5 138 99.92 100.00 99.17
10 275 100.00 100.00 100.00
15 413 100.00 100.00 100.00
20 550 100.00 100.00 100.00
30 826 100.00 100.00 100.00
50 1 376 100.00 100.00 100.00
1 WILLE R . Formal concept analysis[J]. Electronic Notes in Discrete Mathematics, 1999, 2 (1): 199- 200.
2 QI J J, WEI L, YAO Y Y. Three-way formal concept analysis[C] //Proceedings of the 9th International Conference on Rough Sets and Knowledge Technology. Shanghai: Springer, 2014: 732-741.
3 YAO Y Y. Three-way decision: an interpretation of rules in rough set theory[C]//Proceedings of the 4th International Conference on Rough Sets and Knowledge Technology. Gold Coast: Springer, 2009: 14-16.
4 ZHAN J , YE J , DING W , et al. A novel three-way decision model based on utility theory in incomplete fuzzy decision systems[J]. IEEE Transactions on Fuzzy Systems, 2022, 30 (7): 2210- 2226.
doi: 10.1109/TFUZZ.2021.3078012
5 HAO F , GAO J , BISOGNI C , et al. Stability of three-way concepts and its application to natural language generation[J]. Pattern Recognition, 2021, 149, 51- 58.
6 HAO F , YANG Y , MIN G , et al. Incremental construction of three-way concept lattice for knowledge discovery in social networks[J]. Information Science, 2021, 578, 257- 280.
7 WEI L , LIU L , QI J , et al. Rules acquisition of formal decision contexts based on three-way concept lattices[J]. Information Science, 2020, 516, 529- 544.
doi: 10.1016/j.ins.2019.12.024
8 祁建军, 汪文威. 多线程并行构建三支概念[J]. 西安交通大学学报, 2017, 51 (3): 116- 121.
QI Jianjun , WANG Wenwei . A multithreaded parallel algorithm for constructing three-way concepts[J]. Journal of Xi'an Jiaotong University, 2017, 51 (3): 116- 121.
9 钱婷. 经典概念格与三支概念格的构造及知识获取理论[J]. 西安: 西北大学, 2016.
QIAN Ting. The constructions of classical concept lattices and three-way concept lattices and knowledge acquisition[J]. Xi'an: Northwest University, 2016.
10 QIAN T , WEI L , QI J . Constructing three-way concept lattices based on apposition and subposition of formal contexts[J]. Knowledge-Based Systems, 2017, 116, 39- 48.
11 王明, 魏玲. 基于K-Modes聚类的OE-概念格压缩[J]. 模式识别与人工智能, 2018, (8): 704- 714.
WANG Ming , WEI Ling . OE-Concept lattice compression based on K-Modes clustering[J]. Pattern Recognition and Artificial Intelligence, 2018, (8): 704- 714.
12 HAO F , YANG Y , MIN G , et al. Incremental construction of three-way concept lattice for knowledge discovery in social networks[J]. Information Sciences, 2021, 578, 257- 280.
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.
14 HUANG C , LI J , MEI C , et al. Three-way concept learning based on cognitive operators: an information fusion viewpoint[J]. International Journal of Approximate Reasoning, 2017, 84, 1- 20.
15 YUAN K H , XU W H , LI W T , et al. An incremental learning mechanism for object classification based on progressive fuzzy three-way concept[J]. Information Sciences, 2022, 584, 127- 147.
16 HE X , WEI L , SHE Y . L-fuzzy concept analysis for three-way decisions: basic definitions and fuzzy inference mechanisms[J]. International Journal of Machine Learning and Cybernetics, 2018, 9 (11): 1857- 1867.
17 LIU X , MAO W , DAI J , et al. Comprehensive fuzzy concept-oriented three-way decision and its application[J]. Information Sciences, 2022, 593, 233- 270.
18 SUBHASHINI L , LI Y , ZHANG J , et al. Integration of semantic patterns and fuzzy concepts to reduce the boundary region in three-way decision-making[J]. Information Sciences, 2022, 595, 257- 277.
19 SINGH P . Three-way fuzzy concept lattice representation using neutrosophicset[J]. International Journal of Machine Learning and Cybernetics, 2016, 8 (1): 1- 11.
20 YAO Y Y . Interval sets and three-way concept analysis in incomplete contexts[J]. International Journal of Machine Learning and Cybernetics, 2017, 8 (1): 3- 20.
21 LI J H , MEI C L . Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction[J]. International Journal of Approximate Reasoning, 2013, 54 (1): 149- 165.
22 LI M , WANG G . Approximate concept construction with three-way decisions and attribute reduction in incomplete contexts[J]. Knowledge-Based Systems, 2016, 91, 165- 178.
23 ZHI H , CHAO H . Three-way concept analysis for incomplete formal contexts[J]. Mathematical Problems in Engineering, 2018, 2018, 1- 11.
24 YAO Y Y . Three-way conflict analysis: reformulations and extensions of the Pawlakmodel[J]. Knowledge-Based Systems, 2019, 180, 26- 37.
25 FAN Y, QI J J, WEI L. A conflict analysis model based on three-way decisions[C]// Proceedings of International Joint Conference. QuyNhon: Springer, 2018: 522-532.
26 SINGH P K . Medical diagnoses using three-way fuzzy concept lattice and their Euclidean distance[J]. Computational and Applied Mathematics, 2018, 37, 3283- 3306.
27 SUBRAMANIAN C M , CHERUKURI A K , CHELLIAH C . Role based access control design using three-way formal concept analysis[J]. International Journal of Machine Learning and Cybernetics, 2018, 9 (11): 1- 31.
28 LONG B H , XU W H , ZHANG X Y , et al. The dynamic update method of attribute-induced three-way granular concept in formal contexts[J]. International Journal of Approximate Reasoning, 2020, 126, 228- 248.
29 NIU J , HUANG C , LI J , et al. Parallel computing techniques for concept-cognitive learning based on granular computing[J]. International Journal of Machine Learning and Cybernetics, 2018, 9 (11): 1785- 1805.
30 SHI Y , MI Y L , LI J H , et al. Concept-cognitive learning model for incremental concept learning[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2021, 51 (2): 809- 821.
31 SHI Y , MI Y L , LI J H , et al. Concurrent concept-cognitive learning model for classification[J]. Information Sciences, 2019, 496, 65- 81.
32 ZHANG T , LI H , LIU M , et al. Incremental concept-cognitive learning based on attribute topology[J]. International Journal of Approximate Reasoning, 2020, 118, 173- 189.
33 YUAN K H , XU W H , LI W T , et al. An incremental learning mechanism for object classification based on progressive fuzzy three-way concept[J]. Information Sciences, 2022, 584, 127- 147.
34 QI J J , QIAN T , WEI L . The connections between three-way and classical concept lattices[J]. Knowledge-Based Systems, 2016, 91, 143- 151.
35 GANTER B , WILLE R . Formal concept analysis: mathematical foundations[M]. New York: Springer, 1999.
36 郭莹, 张长胜, 张斌. 求解SAT问题的算法的研究进展[J]. 计算机科学, 2016, 43 (3): 8- 17.
GUO Ying , ZHANG Changsheng , ZHANG Bin . Research advance of SAT solving algorithm[J]. Computer Science, 2016, 43 (3): 8- 17.
37 张文修, 梁怡, 徐萍. 基于包含度的不确定推理[M]. 北京: 清华大学出版社, 2007.
ZHANG Wenxiu , LIANG Yi , XU Ping . Uncertainty reasoning based on inclusion degree[M]. Beijing: Tsinghua University Press, 2007.
38 魏玲, 曹丽, 祁建军, 等. 形式概念分析中的概念约简与概念特征[J]. 中国科学(信息科学), 2020, 50, 1817- 1833.
WEI Ling , CAO Li , QI Jianjun , et al. Concept reduction and concept characteristics in formal concept analysis[J]. Science China(Information Sciences), 2020, 50, 1817- 1833.
39 曹丽, 魏玲, 祁建军. 保持二元关系不变的概念约简[J]. 模式识别与人工智能, 2018, 31 (6): 516- 524.
CAO Li , WEI Ling , QI Jianjun . Concept reduction preserving binary relations[J]. Pattern Recognition and Artificial Intelligence, 2018, 31 (6): 516- 524.
40 周志华. 机器学习[M]. 北京: 清华大学出版社, 2016.
ZHOU Zhihua . Machine learning[M]. Beijing: Tsinghua University Press, 2016.
[1] 胡成祥,张莉,黄晓玲,王汇彬. 面向属性变化的动态邻域粗糙集知识更新方法[J]. 《山东大学学报(理学版)》, 2023, 58(7): 37-51.
[2] 时俊鹏,张燕兰. 面向对象删除的局部邻域粗糙集动态更新算法[J]. 《山东大学学报(理学版)》, 2023, 58(5): 17-25.
[3] 韩培磊,魏玲,王振,赵思雨. FCA中的互补概念及其性质与生成[J]. 《山东大学学报(理学版)》, 2022, 57(8): 60-67.
[4] 唐洁,魏玲,任睿思,赵思雨. 基于可能属性分析的粒描述[J]. 《山东大学学报(理学版)》, 2021, 56(1): 75-82.
[5] 李金海,贺建君,吴伟志. 多粒度形式概念分析的类属性块优化[J]. 《山东大学学报(理学版)》, 2020, 55(5): 1-12.
[6] 刘营营,米据生,梁美社,李磊军. 三支区间集概念格[J]. 《山东大学学报(理学版)》, 2020, 55(3): 70-80.
[7] 姬儒雅,魏玲,任睿思,赵思雨. 毕达哥拉斯模糊三支概念格[J]. 《山东大学学报(理学版)》, 2020, 55(11): 58-65.
[8] 李粉宁,范敏,李金海. 形式概念分析中面向对象粒概念的动态更新[J]. 《山东大学学报(理学版)》, 2019, 54(4): 105-115.
[9] 任睿思,魏玲,祁建军. 三支弱协调决策形式背景的规则获取[J]. 山东大学学报（理学版）, 2018, 53(6): 76-85.
[10] 陈保会,张凌,史开泉. P-信息智能动态融合与信息规律状态智能识别[J]. 山东大学学报（理学版）, 2018, 53(2): 83-87.
[11] 李金海,吴伟志. 形式概念分析的粒计算方法及其研究展望[J]. 山东大学学报（理学版）, 2017, 52(7): 1-12.
[12] 刘琳,魏玲,钱婷. 决策形式背景中具有置信度的三支规则提取[J]. 山东大学学报（理学版）, 2017, 52(2): 101-110.
[13] 陈雪,魏玲,钱婷. 基于AE-概念格的决策形式背景属性约简[J]. 山东大学学报（理学版）, 2017, 52(12): 95-103.
[14] 汤亚强, 范敏, 李金海. 三元形式概念分析下的认知系统模型及信息粒转化方法[J]. 山东大学学报（理学版）, 2014, 49(08): 102-106.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 杨军. 金属基纳米材料表征和纳米结构调控[J]. 山东大学学报（理学版）, 2013, 48(1): 1 -22 .
[2] 何海伦， 陈秀兰*. 变性剂和缓冲系统对适冷蛋白酶MCP-01和中温蛋白酶BP-01构象影响的圆二色光谱分析何海伦， 陈秀兰*[J]. 山东大学学报（理学版）, 2013, 48(1): 23 -29 .
[3] 赵君1,赵晶2,樊廷俊1*,袁文鹏1,3,张铮1,丛日山1. 水溶性海星皂苷的分离纯化及其抗肿瘤活性研究[J]. J4, 2013, 48(1): 30 -35 .
[4] 孙小婷1,靳岚2*. DOSY在寡糖混合物分析中的应用[J]. J4, 2013, 48(1): 43 -45 .
[5] 罗斯特,卢丽倩,崔若飞,周伟伟,李增勇*. Monte-Carlo仿真酒精特征波长光子在皮肤中的传输规律及光纤探头设计[J]. J4, 2013, 48(1): 46 -50 .
[6] 杨伦，徐正刚，王慧*，陈其美，陈伟，胡艳霞，石元，祝洪磊，曾勇庆*. RNA干扰沉默PID1基因在C2C12细胞中表达的研究[J]. J4, 2013, 48(1): 36 -42 .
[7] 冒爱琴1, 2, 杨明君2, 3, 俞海云2, 张品1, 潘仁明1*. 五氟乙烷灭火剂高温热解机理研究[J]. J4, 2013, 48(1): 51 -55 .
[8] 杨莹,江龙*,索新丽. 容度空间上保费泛函的Choquet积分表示及相关性质[J]. J4, 2013, 48(1): 78 -82 .
[9] 李永明1, 丁立旺2. PA误差下半参数回归模型估计的r-阶矩相合[J]. J4, 2013, 48(1): 83 -88 .
[10] 董伟伟. 一种具有独立子系统的决策单元DEA排序新方法[J]. J4, 2013, 48(1): 89 -92 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发