﻿ 三支概念的一种构建方法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2020, Vol. 15 Issue (3): 514-519  DOI: 10.11992/tis.201904022 0

### 引用本文

MAO Hua, WU Xiu. A new method for constructing three-way concept[J]. CAAI Transactions on Intelligent Systems, 2020, 15(3): 514-519. DOI: 10.11992/tis.201904022.

### 文章历史

A new method for constructing three-way concept
MAO Hua , WU Xiu
School of Mathematics and Information Science, Hebei University, Baoding 071002, China
Abstract: The construction of three-way concept is one of the important research subjects of three-way formal concept analysis. To enrich the research of three-way concept, an algorithm for constructing the three-way concept is proposed by using the matrix structure. First, the definition of attribute matrix is given, which displays or shows attributes and its classes. Then the algorithm of the attribute-induced three-way concept is constructed based upon the definition. The operation process of the abovementioned algorithm is illustrated with an example and the validity of the algorithm is verified. Second, the definition of object matrix is given and the algorithm of object-induced three-way concept is designed according to the object matrix definition. Similarly, an example is used to illustrate the algorithm process. The above processes or concepts show that the proposed algorithms are correct and effective. The research results provide more choices for the application of three-way concept in data processing.
Key words: formal context    classical concept    three-way concept    object-induced three-way concept    attribute-induced three-way concept    matrix    attribute matrix    object matrix

1 基础知识

 ${A^*}: = \{ m \in M|I_{gm}{\text{对于任意}}g \in A{\rm{\} }}$

 ${B^*}: = \{ g \in G|I_{gm}{\text{对于任意}}m \in B{\rm{\} }}$

 $({A_1},{B_1}) \leqslant ({A_{\rm{2}}},{B_{\rm{2}}}) \Leftrightarrow {A_1} \subseteq {A_2}( \Leftrightarrow {B_1} \supseteq {B_2})。$

 ${A^{\bar *}} = \{ m \in M|\forall g \in A({I}_{gm}^c)\}$

 ${B^{\bar *}} = \{ g \in G|\forall m \in B({I_{gm}^c})\}$

 ${X^{ < \cdot }} = ({X^*},{X^{\bar *}})$
 ${(A,B)^{ \cdot > }} = \{ x \in G|x \in {A^*},x \in {B^{\bar *}}\} = {A^*} \cap {B^{\bar *}}。$

$(G,M,I)$ 是一个形式背景。 $^{ < \cdot }:P(M) \to {\rm{DP}}(G)$ $^{ \cdot > }:{\rm{DP}}(G) \to P(M)$ 分别为集合 $X,Y \subseteq G$ $A \subseteq M$ 上的基于属性导出的算子。算子运算方式如下：

 ${A^{ < \cdot }} = ({A^*},{A^{\bar *}}),$
 ${(X,Y)^{ \cdot > }} = \{ v \in M|v \in {X^*},v \in {Y^{\bar *}}\} = {X^*} \cap {Y^{\bar *}}。$

 $(X,(A,B)) \leqslant (Y,(C,D)) \Leftrightarrow X \subseteq Y \Leftrightarrow (C,D) \subseteq (A,B)$

 $({\rm{OE}}_1)\;X \subseteq {X^{ < \cdot \cdot > }},(A,B) \subseteq {(A,B)^{ \cdot > < \cdot }}$
 $({\rm{OE}}_2)\;{X_1} \subseteq {X_2} \Rightarrow X_2^{ < \cdot } \subseteq X_1^{ < \cdot },({A_1},{B_1}) \subseteq ({A_2},{B_2})\Rightarrow$
 ${({A_2},{B_2})^{ \cdot > }} \subseteq {({A_1},{B_1})^{ \cdot > }}$
 $({\rm{OE}}_3)\;{X^{ < \cdot }} = {X^{ < \cdot \cdot > < \cdot }},{(A,B)^{ \cdot > }} = {(A,B)^{ \cdot > < \cdot \cdot > }}$
 $({\rm{OE}}_4)\;X \subseteq {(A,B)^{ \cdot > }} \Leftrightarrow (A,B) \subseteq {X^{ < \cdot }}$
 $({\rm{OE}}_5)\;{({X_1} \cup {X_2})^{ < \cdot }} = X_1^{ < \cdot } \cap X_2^{ < \cdot },(({A_1},{B_1}) \cup ({A_2}$
 ${B_2}){)^{ \cdot > }} = {({A_1},{B_1})^{ \cdot > }} \cap {({A_2},{B_2})^{ \cdot > }}$
 $({\rm{OE}}_6)\;{({X_1} \cap {X_2})^{ < \cdot }} \supseteq X_1^{ < \cdot } \cup X_2^{ < \cdot },(({A_1},{B_1}) \cap ({A_2},$
 ${B_2}){)^{ \cdot > }} = {({A_1},{B_1})^{ \cdot > }} \cup {({A_2},{B_2})^{ \cdot > }}。$

 $((X,Y),A) \leqslant ((Z,W),B) \Leftrightarrow (X,Y) \subseteq (Z,W) \Leftrightarrow B \subseteq A$

 $({\rm{AE}}_1)\;(X,Y) \subseteq {(X,Y)^{ \cdot > < \cdot }},A \subseteq {A^{ < \cdot \cdot > }}$
 $({\rm{AE}}_2)\;({X_1},{Y_1}) \subseteq ({X_2},{Y_2}) \Rightarrow {({X_2},{Y_2})^{ \cdot > }} \subseteq {({X_1},{Y_1})^{ \cdot > }}$
 ${A_1} \subseteq {A_2} \Rightarrow A_2^{ < \cdot } \subseteq A_1^{ < \cdot }$
 $({\rm{AE}}_3)\;{(X,Y)^{ \cdot > }} = {(X,Y)^{ \cdot > < \cdot \cdot > }},{A^{ < \cdot }} = {A^{ < \cdot \cdot > < \cdot }}$
 $({\rm{AE}}_4)\;(X,Y) \subseteq {A^{ < \cdot }} \Leftrightarrow A \subseteq {(X,Y)^{ \cdot > }}$
 $({\rm{AE}}_5)\;{(({X_1},{Y_1}) \cup ({X_2},{Y_2}))^{ \cdot > }} = {({X_1},{Y_1})^{ \cdot > }} \cap ({X_2},$
 ${Y_2}{)^{ \cdot > }},{({A_1} \cup {A_2})^{ < \cdot }} = A_1^{ < \cdot } \cap A_2^{ < \cdot }$
 $({\rm{AE}}_6)\;{(({X_1},{Y_1}) \cap ({X_2},{Y_2}))^{ \cdot > }} \supseteq {({X_1},{Y_1})^{ \cdot > }} \cup ({X_2},$
 ${Y_2}{)^{ \cdot > }},{({A_1} \cap {A_2})^{ < \cdot }} \supseteq A_1^{ < \cdot } \cup A_2^{ < \cdot }。$
2 概念的构建 2.1 依据属性矩阵构建属性三支概念

 ${{{W}}_{{1}}} = \left[ {\begin{array}{*{20}{c}} {(123,4)}&{(3,{\text{Ø}} )}&{(12,{\text{Ø}} )}&{(2,{\text{Ø}} )} \\ {}&{(34,12)}&{(4,{\text{Ø}} )}&{(4,1)} \\ {}&{}&{(124,3)}&{(24,3)} \\ {}&{}&{}&{(24,13)}\\ \end{array}} \right]$

1)生成形式背景 $(G,M,I)$ 的属性矩阵 ${{W}}$ ，并将属性矩阵 ${{W}}$ 的所有元素构成的集合记成集合 $P$

2) $i = 1$

3) $j = 1$

4) $s = 1$

5) $w = {w_{ij}} \cap {w_{is}}$

6) 如果 $w \notin P$ ，则 $P = P \cup \{ w\}$ $s = s + 1$ 并执行7)；反之 $s = s + 1$ ，并执行7)；

7) 如果 $s \leqslant \left| P \right|$ ，则执行5)；反之 $j = j + 1$ ，执行8)；

8) 如果 $j \leqslant \left| P \right|$ ，则执行4)；反之 $i = i + 1$ ，执行9)；

9) 如果 $i \leqslant \left| P \right|$ ，则执行3)；反之执行10)；

10)对更新过的集合 $P$ 递归调用2)~ 9)，直至集合 $P$ 不再更新；

11) $Y = {\text{Ø}}$ $i = 1$

12) $j = i$

13) 如果 $w \subseteq {w_{ij}}$ ，则 $Y = Y \cup \{ {a_i}\} \cup \{ {a_j}\}$ $j = j + 1$ ，执行14)；

14) 如果 $j \leqslant n$ ，则执行13)；反之 $i = i + 1$ 并执行15)；

15) 如果 $i \leqslant n$ ，则执行12)；反之执行16)；

16) 输出三支概念 $(w,Y)$

1)首先，生成属性矩阵的复杂度为 $O({{{{\left| M \right|}^2}} / 2})$ ；其次，得外延集的复杂度为 $O({\left| M \right|^{4{{\log }_2}\left| M \right|}})$ ；最后，寻找满足条件的 $w$ 对应的属性集，共比较 ${{\left| M \right|(\left| M \right| + 1)} / 2}$ 次，循环 $\left| P \right|$ 次，所以复杂度为 $O({{\left| M \right|(\left| M \right| + 1)\left| P \right|} / 2})$ ；因此，算法1的复杂度为 $O({\left| M \right|^{4{{\log }_2}\left| M \right|}})$

2)文献[5]中的复杂度受生成标准形式概念的复杂度的影响，选择的方法不同，复杂度则不同；其次，通过找等价类进行概念构建的最大时间复杂度为 $\max \{ {2^{2\left| M \right|}},{2^{\left| G \right| \times \left| M \right|}}\}$ ，因此，两相比较，本文方法较好。

3)文献[6]中的时间复杂度为 $O(\left| G \right|{\left| M \right|^2}\left| C \right|)$ ，其中 $C$ 表示属性三支核心概念的个数。两相比较，本文算法较好。

${w_{11}} = ({a^*} \cap {a^*},{a^{\bar *}} \cap {a^{\bar *}}) = (1245,3),{w_{12}} = ({a^*} \cap {b^*},$ ${a^{\bar *}} \cap {b^{\bar *}}) = (25,3), \cdots ,{w_{45}}\! = \!({d^*} \cap {e^*},{d^{\bar *}} \cap {e^{\bar *}})\! =\! ({\text{Ø}} ,$ $134),{w_{55}} \!= \!({e^*} \cap {e^*}, {e^{\bar *}} \cap {e^{\bar *}}) \!=\! (2,1345) {\text{。}}$

 ${{{W}}_{{2}}} = \left[\!\!\!\! {\begin{array}{*{20}{c}} {(1245,3)}\!\!&\!\!{(25,3)}\!\!&\!\!{(125,{\text{Ø}} )}\!\!&\!\!{(5,3)}\!\!&\!\!{(2,3)} \\ {}\!\!&\!\!{(25,134)}\!\!&\!\!{(25,4)}\!\!&\!\!{(5,134)}\!\!&\!\!{(2,134)} \\ {}\!\!&\!\!{}\!\!&\!\!{(1235,4)}\!\!&\!\!{(5,4)}\!\!&\!\!{(2,4)} \\ {}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{(5,1234)}\!\!&\!\!{({\text{Ø}} ,134)} \\ {}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{(2,1345)} \\ \end{array}} \!\!\!\!\right]$

2.2 依据对象矩阵构建对象三支概念

${v_{11}}\!\! = \!\!({1^*} \cap {1^*},{1^{\bar *}} \cap {1^{\bar *}})\!\! =\!\! (ac,bd),{v_{12}}\! =\! ({1^*} \cap {2^*},{1^{\bar *}} \cap$ ${2^{\bar *}}) = (ac,b), \cdots ,{v_{34}} = ({3^*} \cap {4^*},{3^{\bar *}} \cap {4^{\bar *}}) = (b,{\text{Ø}} ),$ ${v_{44}} = ({4^*} \cap {4^*},{4^{\bar *}} \cap {4^{\bar *}}) = (bcd,a)${\text{。}}

 ${{{V}}_{{1}}} = \left[ {\begin{array}{*{20}{c}} {(ac,bd)}&{(ac,b)}&{(a,d)}&{(c,{\text{Ø}} )} \\ {}&{(acd,b)}&{(a,{\text{Ø}} )}&{(cd,{\text{Ø}} )} \\ {}&{}&{(ab,cd)}&{(b,{\text{Ø}} )} \\ {}&{}&{}&{(bcd,a)}\\ \end{array}} \right]$

1)利用定义7生成形式背景 $(G,M,I)$ 的对象矩阵 ${{V}}$ ，将对象矩阵 ${{V}}$ 的所有元素记入集合 $F$

2) $k = 1$

3) $t = 1$

4) $c = 1$

5) $v = {v_{kt}} \cap {v_{kc}}$

6) 如果 $v \notin F$ ，则 $F = F \cup \{ v\}$ ，并执行7)；反之直接执行7)；

7) $c=c+1$ ，如果 $c \leqslant \left| F \right|$ ，则执行5)；反之令 $t = t + 1$ ，执行8)；

8) 如果 $t \leqslant \left| F \right|$ ，则执行4)；反之令 $k = k + 1$ ，执行9)；

9) 如果 $k \leqslant \left| F \right|$ ，则执行3)；反之执行10)；

10) 对更新过的集合 $F$ 递归调用2)~ 9)，直至集合 $F$ 不再更新；

11) $H = {\text{Ø}} ,k = 1$ ;

12) $t = k$

13) 如果 $v \subseteq {v_{kt}}$ ，则令 $H = H \cup \{ {b_k}\} \cup \{ {b_t}\}$ $t = t + 1$ ，执行14)；

14) 如果 $t \leqslant \left| G \right|$ ，则执行13)；反之令 $k = k + 1$ 并执行15)；

15) 如果 $k \leqslant \left| G \right|$ ，则执行12)；反之执行16)；

16) 输出三支概念 ${\rm{OEL}}(G,M,I)\backslash \{ ({\text{Ø}} ,(M, M))\} = \cup \{ (H,v)\}$

${v_{11}}\!\!=\!\! ({1^*} \cap {1^*},{1^{\bar *}} \cap {1^{\bar *}})\!\!=\!\!(ac,bde),{v_{12}}\!\!=\!\!({1^*} \cap {2^*},{1^{\bar *}} \cap {2^{\bar *}})$ $\! = (ac,d), \cdots ,{v_{45}} = ({4^*} \cap {5^*},{4^{\bar *}} \cap {5^{\bar *}}) = (a,e),{v_{55}} = ({5^*} \cap {5^*},$ ${5^{\bar *}} \cap {5^{\bar *}}) = (abcd,e){\text{。}}$

 ${{{V}}_{{2}}} = \left[\!\! {\begin{array}{*{20}{c}} {(ac,bde)}\!\!&\!\!{(ac,d)}\!\!&\!\!{(c,bde)}\!\!&\!\!{(a,bde)}\!\!&\!\!{(ac,e)} \\ {}\!\!&\!\!{(abce,d)}\!\!&\!\!{(c,d)}\!\!&\!\!{(a,d)}\!\!&\!\!{(abc,{\text{Ø}} )} \\ {}\!\!&\!\!{}\!\!&\!\!{(c,abde)}\!\!&\!\!{({\text{Ø}} ,bde)}\!\!&\!\!{({\text{Ø}} ,e)} \\ {}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{(a,bcde)}\!\!&\!\!{(a,e)} \\ {}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{}\!\!&\!\!{(abcd,e)}\\ \end{array}} \!\!\right]$

$F = \{ (ac,bde),(ac,d),(c,bde), \cdots ,(a,bcde),(a,e),$ $(abcd,e)\}$ ，对集合 $F$ 中两两元素相交，其中结果 $(ac,{\text{Ø}} ),$ $(a,{\text{Ø}} ),(c,{\text{Ø}} ),(c,e),({\text{Ø}} ,d),({\text{Ø}} ,{\text{Ø}} ) \notin F$ ，将上述结果添加到集合 $F$ 中，再次相交，计算结果为空。可得 $F = \{ (ac,bde),(ac,d),(c,bde), \cdots ,(a,bcde),(a,e),$ $(abcd,e),(ac,{\text{Ø}} ),(a,{\text{Ø}} ),(c,{\text{Ø}} ),(c,e),({\text{Ø}} ,d),({\text{Ø}} ,{\text{Ø}} )\}$

3 结束语

 [1] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Dordrecht: Springer, 1982: 445−470. (0) [2] YAO Yiyu. 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, Australia, 2009: 642−649. (0) [3] QI Jianjun, WEI Ling, YAO Yiyu. Three-way formal concept analysis[C]//Proceedings of the 9th International Conference on Rough Sets and Knowledge Technology. Shanghai, China, 2014: 732−741. (0) [4] REN Ruisi, WEI Ling. The attribute reductions of three-way concept lattices[J]. Knowledge-based systems, 2016, 99: 92-102. DOI:10.1016/j.knosys.2016.01.045 (0) [5] QI Jianjun, QIAN Ting, WEI Ling. 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 (0) [6] 汪文威, 祁建军. 三支概念的构建算法[J]. 西安电子科技大学学报(自然科学版), 2017, 44(1): 71-76. WANG Wenwei, QI Jianjun. The algorithm of constructing three-way concept[J]. Journal of Xidian University (natural science edition), 2017, 44(1): 71-76. (0) [7] QIAN Ting, WEI Ling, QI Jianjun. 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 (0) [8] MAO Hua, ZHAO Shufeng, YANG Lanzhen. Relationships between three-way concepts and classical concepts[J]. Journal of intelligent and fuzzy systems, 2018, 35(1): 1063-1075. DOI:10.3233/JIFS-17530 (0) [9] 刘琳, 钱婷, 魏玲. 基于属性导出三支概念格的决策背景规则提取[J]. 西北大学学报(自然科学版), 2016, 46(4): 481-487. LIU Lin, QIAN Ting, WEI Ling. Rules extraction in formal decision contexts based on attribute-induced three-way concept lattices[J]. Journal of Northwest University (natural science edition), 2016, 46(4): 481-487. (0) [10] SINGH P K. Three-way fuzzy concept lattice representation using neutrosophic set[J]. International journal of machine learning and cybernetics, 2016, 8(1): 69-79. (0) [11] SINGH P K. Medical diagnoses using three-way fuzzy concept lattice and their Euclidean distance[J]. Computational and applied mathematics, 2018, 37(3): 3283-3306. DOI:10.1007/s40314-017-0513-2 (0) [12] YU Huiying, LI Qingguo, CAI Mingjie. 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.007 (0) [13] KONECNY J. On efficient factorization of standard fuzzy concept lattices and attribute-oriented fuzzy concept lattices[J]. Fuzzy sets and systems, 2018, 351: 108-121. DOI:10.1016/j.fss.2018.01.012 (0) [14] CIOBANU G, VĂIDEANU C. A note on similarity relations between fuzzy attribute-oriented concept lattices[J]. Information sciences, 2018, 460-461: 254-263. DOI:10.1016/j.ins.2018.05.034 (0) [15] LI Meizheng, WANG Guoyin. 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 (0) [16] CIOBANU G, VĂIDEANU C. An efficient method to factorize fuzzy attribute-oriented concept lattices[J]. Fuzzy sets and systems, 2017, 317: 121-132. DOI:10.1016/j.fss.2016.07.004 (0) [17] 李美争, 王国胤. 三支近似概念格中基于对象−概念辨识矩阵的属性约简方法[J]. 控制与决策, 2016, 31(10): 1779-1784. LI Meijing, WANG Guoyin. Attribute reduction based on object-concept indentified matrix in approximate three-way concept lattices[J]. Control and decision, 2016, 31(10): 1779-1784. (0) [18] 陈雪, 魏玲, 钱婷. 基于AE-概念格的决策形式背景属性约简[J]. 山东大学学报(理学版), 2017, 52(12): 95-103. CHEN Xue, WEI Ling, QIAN Ting. Attribute reduction of decision formal context based on AE concept lattices[J]. Journal of Shandong University (science edition), 2017, 52(12): 95-103. (0) [19] 李乔. 矩阵论八讲[M]. 上海: 上海科学技术出版社, 1988. (0) [20] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin Heidelberg: Springer-Verlag, 1999. (0)