正在加载图片...
·518… 智能系统学报 第15卷 4)c=1; 因此,三支概念OEL(G2,M2,2八{(O,(M2,M2)》 5)v=vunvkc; 的结果见表4。 6)如果vF,则F=FU,并执行7);反之 表4对象三支概念 直接执行7): Table 4 Object induced three-way concept 7)c=c+1,如果c≤IF1,则执行5);反之令 (3,(c,abde)) (15,(ac,e) (14,(a,bde) t=t+1,执行8) (4,(a,bcde)) (13,(c,bde) (1,(ac,bde)) 8)如果t≤F1,则执行4):反之令k=k+1,执 (2,(abce,d)) (145,(a,e) (1345,(0,e) 行9): 9)如果k≤F1,则执行3):反之执行10): (5,(abcd,e)) (135,(c,e) (1234,(0,d0) 10)对更新过的集合F递归调用2)9),直至 (123,(c,d0) (25,(abc,0) (1235,(c,0) 集合F不再更新; (124,(a,d) (125,(ac,0) (1245,(a,0) 11)H=0,k=1 (12,(ac,d) (G2,(0,0) (134,(0,bde) 12)t=k: 13)如果v≤ya,则令H=HU{bU{b,,t=t+1, 在本例中1G=5,所以执行算法2的复杂度 执行14): 为0(5ioe)。 14)如果t≤1G1,则执行13):反之令k=k+1并 3 结束语 执行15): 15)如果k≤1G,则执行12):反之执行16): 本文给出了属性矩阵与对象矩阵的定义。利 16)输出三支概念OEL(G,M,)1M(O,(M,M)}= 用属性(对象)矩阵,设计了构建属性(对象)三支 U(H.v)o 概念的算法。经验证,上述算法均有效,且在复 由算法1的分析理论可知,算法2在有限步 杂度方面,有所改善。后期,将继续对三支概念 后可以停止,复杂度为OGe:©。 的应用方面进行研究。 例4采用形式背景(G2,M2,2)对算法2的运 参考文献: 行过程进行说明。 [1]WILLE R.Restructuring lattice theory:an approach based 1=(1'n1',1n1)=(ac,bde),y2=(1'n2,1n2)= on hierarchies of concepts[M]//RIVAL I.Ordered Sets. (ac,d0,…,4s=(4n5,4n5)=(a,e,y55=(5n5,5n Dordrecht:Springer,1982:445-470. 5)=(abcd,e)。 [2]YAO Yiyu.Three-way decision:an interpretation of rules 可得 in rough set theory[C]//Proceedings of the 4th Internation- al Conference on Rough Sets and Knowledge Technology. (ac,bde)(ac,d)(c,bde)(a,bde) (ac,e) Gold Coast,Australia,2009:642-649 (abce.d) (c,d0 (a,d) (abc,O) [3]QI Jianjun,WEI Ling,YAO Yiyu.Three-way formal concept analysis[C]//Proceedings of the 9th International V3= (c,abde)(O,bde) (0,e) Conference on Rough Sets and Knowledge Technology (a,bcde)(a,e) Shanghai,China,2014:732-741. (abcd,e) [4]REN Ruisi,WEI Ling.The attribute reductions of three- F=((ac,bde),(ac,d),(c,bde),....(a,bcde),(a,e). way concept lattices[J].Knowledge-based systems,2016, (abcd,e)》,对集合F中两两元素相交,其中结果 99:92-102, (ac,0).(a,0),(c,0),(c,e),(O,d,(0,O)F,将上述结 [5]QI Jianjun,QIAN Ting,WEI Ling.The connections 果添加到集合F中,再次相交,计算结果为空。 between three-way and classical concept lattices[J].Know- ledge-based systems,2016,91:143-151. 可得F={(ac,bde,(ac,d),(c,bde),…,(a,bcde),(a,e), [6]汪文威,祁建军.三支概念的构建算法).西安电子科技 (abcd,e),(ac,0),(a,O),(c,0),(c,e),(0,d),(0,O)}。 大学学报(自然科学版),2017,44(171-76 之后,在矩阵V2中,分别对集合F中每一元 WANG Wenwei,QI Jianjun.The algorithm of construct- 素执行算法2的11)人16):例如,对(ac,O)来说,在 ing three-way concept[J].Journal of Xidian University 矩阵V2中,(ac,O)≤1V2,V5,2,2s,5,可得三支 (natural science edition),2017,44(1):71-76. 概念(125,(ac,O);对(a,bde)来说,在矩阵S2中, [7]QIAN Ting,WEI Ling,QI Jianjun.Constructing three-way (a,bde)≤y,y14,V44,可得三支概念(14,(a,bde)。 concept lattices based on apposition and subposition of4) c = 1 ; 5) v = vkt ∩vkc; 6) 如果 v < F ,则 F = F ∪ {v} ,并执行 7);反之 直接执行 7); c = c+1 c ⩽ |F| t = t+1 7) ,如果 ,则执行 5);反之令 ,执行 8); 8) 如果 t ⩽ |F| ,则执行 4);反之令 k = k+1 ,执 行 9); 9) 如果 k ⩽ |F| ,则执行 3);反之执行 10); F F 10) 对更新过的集合 递归调用 2)~ 9),直至 集合 不再更新; 11) H = Ø, k = 1 ; 12) t = k ; 13) 如果 v ⊆ vkt,则令 H = H ∪ {bk} ∪ {bt},t = t+1, 执行 14); 14) 如果 t ⩽ |G| ,则执行 13);反之令 k = k+1 并 执行 15); 15) 如果 k ⩽ |G| ,则执行 12);反之执行 16); OEL(G, M,I)\{(Ø,(M, M))} = ∪{(H, v)} 16) 输出三支概念 。 O(|G| 4log2 |G| ) 由算法 1 的分析理论可知,算法 2 在有限步 后可以停止,复杂度为 。 例 4 采用形式背景 (G2, M2,I2) 对算法 2 的运 行过程进行说明。 v11=(1∗ ∩1 ∗ ,1 ∗¯ ∩1 ∗¯ )=(ac,bde), v12=(1∗ ∩2 ∗ ,1 ∗¯ ∩2 ∗¯ ) = (ac,d),··· , v45 = (4∗ ∩5 ∗ ,4 ∗¯ ∩5 ∗¯ ) = (a, e), v55 = (5∗ ∩5 ∗ , 5 ∗¯∩ 5 ∗¯ ) = (abcd, e)。 可得 V2 =   (ac,bde) (ac,d) (c,bde) (a,bde) (ac, e) (abce,d) (c,d) (a,d) (abc,Ø) (c,abde) (Ø,bde) (Ø, e) (a,bcde) (a, e) (abcd, e)   F = {(ac,bde),(ac,d),(c,bde),··· ,(a,bcde),(a, e), (abcd, e)} F (ac,Ø),(a,Ø),(c,Ø),(c, e),(Ø,d),(Ø,Ø) < F F F = {(ac,bde),(ac,d),(c,bde),··· ,(a,bcde),(a, e), (abcd, e),(ac,Ø),(a,Ø),(c,Ø),(c, e),(Ø,d),(Ø,Ø)} 令 ,对集合 中两两元素相交,其中结果 ,将上述结 果添加到集合 中,再次相交,计算结果为空。 可 得 。 V2 F (ac,Ø) V2 (ac,Ø) ⊆ v11,v12, v15, v22, v25, v55 (125,(ac,Ø)) (a,bde) S2 (a,bde) ⊆ v11, v14, v44 (14,(a,bde)) 之后,在矩阵 中,分别对集合 中每一元 素执行算法 2 的 11)~16):例如,对 来说,在 矩阵 中, ,可得三支 概念 ;对 来说,在矩阵 中 , ,可得三支概念 。 因此,三支概念 OEL(G2, M2,I2)\{(Ø,(M2,M2))} 的结果见表 4。 表 4 对象三支概念 Table 4 Object induced three-way concept (3,(c,abde)) (15,(ac, e)) (14,(a,bde)) (4,(a,bcde)) (13,(c,bde)) (1,(ac,bde)) (2,(abce,d)) (145,(a, e)) (1345,(Ø, e)) (5,(abcd, e)) (135,(c, e)) (1234,(Ø,d)) (123,(c,d)) (25,(abc,Ø)) (1235,(c,Ø)) (124,(a,d)) (125,(ac,Ø)) (1245,(a,Ø)) (12,(ac,d)) (G2,(Ø,Ø)) (134,(Ø,bde)) |G2| = 5 O(54log2 5 ) 在本例中 ,所以执行算法 2 的复杂度 为 。 3 结束语 本文给出了属性矩阵与对象矩阵的定义。利 用属性 (对象) 矩阵,设计了构建属性 (对象) 三支 概念的算法。经验证,上述算法均有效,且在复 杂度方面,有所改善。后期,将继续对三支概念 的应用方面进行研究。 参考文献: WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Dordrecht: Springer, 1982: 445−470. [1] YAO Yiyu. Three-way decision: an interpretation of rules in rough set theory[C]//Proceedings of the 4th Internation￾al Conference on Rough Sets and Knowledge Technology. Gold Coast, Australia, 2009: 642−649. [2] 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. [3] REN Ruisi, WEI Ling. The attribute reductions of three￾way concept lattices[J]. Knowledge-based systems, 2016, 99: 92–102. [4] QI Jianjun, QIAN Ting, WEI Ling. The connections between three-way and classical concept lattices[J]. Know￾ledge-based systems, 2016, 91: 143–151. [5] 汪文威, 祁建军. 三支概念的构建算法 [J]. 西安电子科技 大学学报(自然科学版), 2017, 44(1): 71–76. WANG Wenwei, QI Jianjun. The algorithm of construct￾ing three-way concept[J]. Journal of Xidian University (natural science edition), 2017, 44(1): 71–76. [6] QIAN Ting, WEI Ling, QI Jianjun. Constructing three-way concept lattices based on apposition and subposition of [7] ·518· 智 能 系 统 学 报 第 15 卷
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有