JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (12): 52-62.doi: 10.6040/j.issn.1671-9352.4.2022.7343

Previous Articles     Next Articles

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)

201

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

CLC Number: 

  • TP181

Table 1

The context of living beings and water"

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

Fig.1

Flowchart of example 4"

Fig.2

Flowchart of example 5"

Table 3

Description of experimental data sets"

编号 数据集 对象数 属性数 概念数
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

Table 4

Concept number and degree of recovery of living beings and water"

概念个数比例/% 概念个数 平均恢复度/% 最大恢复度/% 最小恢复度/%
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

Table 5

Concept number and degree of recovery of watermelon data set"

概念个数比例/% 概念个数 平均恢复度/% 最大恢复度/% 最小恢复度/%
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

Table 6

Concept number and degree of recovery of 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

Table 7

Concept number and degree of recovery of 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] LIU Ying-ying, MI Ju-sheng, LIANG Mei-she, LI Lei-jun. Three-way interval-set concept lattice [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(3): 70-80.
[2] JI Ru-ya, WEI Ling, REN Rui-si, ZHAO Si-yu. Pythagorean fuzzy three-way concept lattice [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(11): 58-65.
[3] REN Rui-si, WEI Ling, QI Jian-jun. Rules acquisition on three-way weakly consistent formal decision contexts [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 76-85.
[4] LIU Lin, WEI Ling, QIAN Ting. Three-way rules extraction in formal decision contexts with confidence [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(2): 101-110.
[5] CHEN Xue, WEI Ling, QIAN Ting. Attribute reduction in formal decision contexts based on AE-concept lattices [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(12): 95-103.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] YANG Jun. Characterization and structural control of metalbased nanomaterials[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 1 -22 .
[2] HE Hai-lun， CHEN Xiu-lan* . Circular dichroism detection of the effects of denaturants and buffers on the conformation of cold-adapted protease MCP-01 and  mesophilic protease BP01[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 23 -29 .
[3] ZHAO Jun1, ZHAO Jing2, FAN Ting-jun1*, YUAN Wen-peng1,3, ZHANG Zheng1, CONG Ri-shan1. Purification and anti-tumor activity examination of water-soluble asterosaponin from Asterias rollestoni Bell[J]. J4, 2013, 48(1): 30 -35 .
[4] SUN Xiao-ting1, JIN Lan2*. Application of DOSY in oligosaccharide mixture analysis[J]. J4, 2013, 48(1): 43 -45 .
[5] LUO Si-te, LU Li-qian, CUI Ruo-fei, ZHOU Wei-wei, LI Zeng-yong*. Monte-Carlo simulation of photons transmission at alcohol wavelength in  skin tissue and design of fiber optic probe[J]. J4, 2013, 48(1): 46 -50 .
[6] YANG Lun, XU Zheng-gang, WANG Hui*, CHEN Qi-mei, CHEN Wei, HU Yan-xia, SHI Yuan, ZHU Hong-lei, ZENG Yong-qing*. Silence of PID1 gene expression using RNA interference in C2C12 cell line[J]. J4, 2013, 48(1): 36 -42 .
[7] MAO Ai-qin1,2, YANG Ming-jun2, 3, YU Hai-yun2, ZHANG Pin1, PAN Ren-ming1*. Study on thermal decomposition mechanism of  pentafluoroethane fire extinguishing agent[J]. J4, 2013, 48(1): 51 -55 .
[8] YANG Ying, JIANG Long*, SUO Xin-li. Choquet integral representation of premium functional and related properties on capacity space[J]. J4, 2013, 48(1): 78 -82 .
[9] LI Yong-ming1, DING Li-wang2. The r-th moment consistency of estimators for a semi-parametric regression model for positively associated errors[J]. J4, 2013, 48(1): 83 -88 .
[10] DONG Wei-wei. A new method of DEA efficiency ranking for decision making units with independent subsystems[J]. J4, 2013, 48(1): 89 -92 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd