第3期 毛华，等：三支概念的一种构建方法 ·517· 中包含了所有的外延；③若算法1中5)的结果不 因此，三支概念AEL(G2,M2,2八(G2,G2),O)》 属于集合P,则算法1中的6)能够将其纳入集合 的结果，见表3。 P中，因此，执行有限次后，集合P包含所有的外 表3属性三支概念 延。最后，对每个外延寻找相应属性集即可得属 Table 3 Attribute induced three-way concept 性三支概念。 (5,1234),d (2,4),bce) (5,4),bcd) 例2利用文献[8]中的形式背景(G2,M2, (2,1345),e) (25,4),bc) (25,134),b) 2(见表2)对算法1的运行过程及有效性进行说 (1235,4),c) ((0,4),bcde) (125,0),ac) 明。对象集G2为5个病人组成的集合，属性集 (1245,3),a (5,3),abd) (25,0),abc M2为病症的集合，分别为腰痛、尿急、排尿困难、 (2,3),abe) ((2,0),abce) 尿道肿胀以及急性膀胱炎。为了能够对数据集做 (2,134),be) 出合理分析，可先基于该背景进行三支概念构 (5.134),bd ((0.3).abde) (5.0),abcd0 建，以此对后续判断提供依据。 (25,3).ab) (0,0),M2) (0,134),bde) 表2形式背景(G2,M2,2) 依据定理1、2对算法的正确性及有效性进行 Table 2 Formal context (G2,M2,12) 了验证，且实例2运用算法1所得结果与文献[8] G e 中所得一致，再次说明本文方法有效。 形式背景(G2,M2,I2)中1M2l=5,所以，执行算 2 法1的2)10)复杂度为0(5：)：11)16)的复杂 度为0(5×6×21)/2)：因此，对例2执行算法1的 3 复杂度为0(5g5)。 t 2.2依据对象矩阵构建对象三支概念 本小节将对对象三支概念的算法进行设计， 给出相关定义、算法以及实例说明。 首先，由表2中形式背景可知： 定义7形式背景(G,M,D,其中对象集合 w1=(a'na',ana)=(1245,3),w2=(anb,an G={b1,b2,…,bn},定义：V=(va),Va=(bnb,bnb), b)=(25,3),…,was=(dne',d产ne)=(0,134),wss=(e'n b,b,(k,t=1,2,…,n)∈G。称矩阵V为一个n×n对 e,e2ne)=(2,1345). 象矩阵。 可得 例3形式背景(G,M,1)见表1。 由表1可知： T(1245,3)(25,3)(125,0)(5,3) (2,3) y1=(1'n1',1n1)=(ac,bd0,y2=(1'n2,1n2)= (25,134)(25,4)(5,134)(2,134) (ac,b),…,34=(3n4,3n4)=(b,0),y44=(4n4,4n W2= (1235,4)(5,4) (2,4) 4)=(bcd,ad)。 (5,1234)(0,134) 可得： (2,1345) (ac,bd) (ac,b) (a,d) (c,0) 其次，令P={(1245,3),(25,3),(125,0),…,(5,1234). (acd,b) (a,0) (cd,0) VI= (0,134),(2,1345)h,对集合P中元素进行相交，所得 (ab,cd) (b.0 结果中(25,0)，(5,0)，(2,0)，(0,3)，(0,4，(0,0)年P, (bcd,a) 将其添加到集合P中，再次两两相交，相交结 构建对象三支概念的算法过程如算法2。 果均为空。所以得P={1245,3),(25,3).(125,0),…, 算法2生成对象三支概念的算法。 (5,1234),(0,134),(2,1345),(25,0).(5,0),(2,0),(0,3), 输入形式背景(G,M,D。 (0,4),(0,0)1。 输出OEL(G,M,D八{(O,(M,M)川。 之后，执行算法1中11)16)得到三支概念。 1)利用定义7生成形式背景(G,M,)的对象 例如，在矩阵W2中，(1245,3)≤w,可得三支概念 矩阵V,将对象矩阵V的所有元素记入集合F; (1245,3),a;对(25,3)来说，在矩阵W2中，(25,3) 2)k=1; w11,w12,w22,可得三支概念(25,3)，ab)。 3)t=1;P P P 中包含了所有的外延；③若算法 1 中 5) 的结果不 属于集合 ，则算法 1 中的 6) 能够将其纳入集合 中，因此，执行有限次后，集合 包含所有的外 延。最后，对每个外延寻找相应属性集即可得属 性三支概念。 (G2, M2, I2) G2 M2 例 2 利用文献 [8] 中的形式背景 (见表 2) 对算法 1 的运行过程及有效性进行说 明。对象集 为 5 个病人组成的集合，属性集 为病症的集合，分别为腰痛、尿急、排尿困难、 尿道肿胀以及急性膀胱炎。为了能够对数据集做 出合理分析，可先基于该背景进行三支概念构 建，以此对后续判断提供依据。 表 2 形式背景 (G2, M2,I2) Table 2 Formal context (G2, M2,I2) G2 a b c d e 1 × × 2 × × × × 3 × 4 × 5 × × × × 首先，由表 2 中形式背景可知： w11 = (a ∗ ∩a ∗ ,a ∗¯ ∩a ∗¯ ) = (1245,3),w12 = (a ∗ ∩b ∗ ,a ∗¯∩ b ∗¯ ) = (25,3),··· ,w45 =(d ∗ ∩e ∗ ,d ∗¯ ∩e ∗¯ )=(Ø,134),w55 =(e ∗∩ e ∗ , e ∗¯ ∩e ∗¯ )=(2,1345)。 可得 W2 =   (1245,3) (25,3) (125,Ø) (5,3) (2,3) (25,134) (25,4) (5,134) (2,134) (1235,4) (5,4) (2,4) (5,1234) (Ø,134) (2,1345)   P = {(1245,3),(25,3),(125,Ø),··· ,(5,1234), (Ø,134),(2,1345)} P (25,Ø),(5,Ø),(2,Ø),(Ø,3),(Ø, 4),(Ø,Ø) < P P P = {(1245,3),(25,3),(125,Ø),··· , (5,1234), (Ø,134), (2,1345), (25,Ø), (5,Ø), (2,Ø),(Ø,3), (Ø,4),(Ø,Ø)}。 其次，令 ，对集合 中元素进行相交，所得 结果中 ， 将其添加到集合 中，再次两两相交，相交结 果均为空。所以得 W2 (1245,3) ⊆ w11 ((1245,3),a) (25,3) W2 (25,3) ⊆ w11,w12,w22 ((25,3),ab) 之后，执行算法 1 中 11)~16) 得到三支概念。 例如，在矩阵 中， ，可得三支概念 ；对 来说，在矩阵 中， ，可得三支概念 。 因此，三支概念 AEL(G2, M2,I2)\{((G2,G2),Ø)} 的结果，见表 3。 表 3 属性三支概念 Table 3 Attribute induced three-way concept ((5,1234),d) ((2,4),bce) ((5,4),bcd) ((2,1345), e) ((25,4),bc) ((25,134),b) ((1235,4), c) ((Ø,4),bcde) ((125,Ø),ac) ((1245,3),a) ((5,3),abd) ((25,Ø),abc) ((2,134),be) ((2,3),abe) ((2,Ø),abce) ((5,134),bd) ((Ø,3),abde) ((5,Ø),abcd) ((25,3),ab) ((Ø,Ø), M2) ((Ø,134),bde) 依据定理 1、2 对算法的正确性及有效性进行 了验证，且实例 2 运用算法 1 所得结果与文献 [8] 中所得一致，再次说明本文方法有效。 (G2, M2,I2) |M2| = 5 O(54log2 5 ) O((5×6×21)/2) O(54log2 5 ) 形式背景 中 ，所以，执行算 法 1 的 2)~10) 复杂度为 ；11)~16) 的复杂 度为 ；因此，对例 2 执行算法 1 的 复杂度为 。 2.2 依据对象矩阵构建对象三支概念 本小节将对对象三支概念的算法进行设计， 给出相关定义、算法以及实例说明。 (G, M,I) G = {b1,b2,··· ,bn} V = (vkt), vkt = (b ∗ k ∩b ∗ t ,b ∗¯ k ∩b ∗¯ t ), bk ,bt(k,t = 1,2,··· ,n) ∈ G V n×n 定义 7 形式背景 ，其中对象集合 ，定义： 。称矩阵 为一个 对 象矩阵。 例 3 形式背景 (G1, M1,I1) 见表 1。 由表 1 可知： v11=(1∗ ∩1 ∗ ,1 ∗¯ ∩1 ∗¯ )=(ac,bd), v12 =(1∗ ∩2 ∗ ,1 ∗¯∩ 2 ∗¯ ) = (ac,b),··· , v34 = (3∗ ∩4 ∗ ,3 ∗¯ ∩4 ∗¯ ) = (b,Ø),v44 = (4∗ ∩4 ∗ ,4 ∗¯∩ 4 ∗¯ ) = (bcd,a)。 可得： V1 =   (ac,bd) (ac,b) (a,d) (c,Ø) (acd,b) (a,Ø) (cd,Ø) (ab, cd) (b,Ø) (bcd,a)   构建对象三支概念的算法过程如算法 2。 算法 2 生成对象三支概念的算法。 输入 形式背景 (G, M,I)。 输出 OEL(G, M,I)\{(Ø,(M, M))}。 (G, M,I) V V F 1) 利用定义 7 生成形式背景 的对象 矩阵 ，将对象矩阵 的所有元素记入集合 ； 2) k = 1 ； 3) t = 1 ； 第 3 期 毛华，等：三支概念的一种构建方法 ·517·