第15卷第3期 智能系统学报 Vol.15 No.3 2020年5月 CAAI Transactions on Intelligent Systems May 2020 D0:10.11992tis.201904022 三支概念的一种构建方法 毛华，武秀 (河北大学数学与信息科学学院，河北保定071002) 摘要：三支概念构建是三支形式概念分析的研究内容之一。为丰富三支概念的研究内容，利用矩阵结构，提 出一种三支概念构建算法。首先，给出属性矩阵的定义，并设计利用属性矩阵构建属性三支概念的算法过程， 对实例进行算法运算，以此对算法步骤进行说明，对算法正确性进行了相应验证。其次，定义对象矩阵，并设 计依据此矩阵构建对象三支概念的算法，对实例进行算法运算。经上述研究验证，所提算法正确且有效。研究 结果为三支概念在数据处理中的应用提供了更多选择。 关键词：形式背景：标准概念；三支概念；对象三支概念：属性三支概念；矩阵；属性矩阵：对象矩阵 中图分类号：TP18文献标志码：A文章编号：1673-4785(2020)03-0514-06 中文引用格式：毛华，武秀.三支概念的一种构建方法.智能系统学报，2020,15(3)：514-519. 英文引用格式：MAO Hua,WU Xiu.A new method for constructing three-way concept J.CAAI transactions on intelligent sys-. tems,2020,153:514-519. 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 op- eration process of the abovementioned algorithm is illustrated with an example and the validity of the algorithm is veri- fied.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. Keywords:formal context;classical concept;three-way concept;object-induced three-way concept;attribute-induced three-way concept;matrix;attribute matrix;object matrix 概念格是由Wille)于1982年提出的理论，一 支概念与属性三支概念。 般可用于解决数据处理等相关的问题。Yao1于 从完备性方面区分，形式背景分为完备形式 2009年将延迟决策引入粗糙集的二支决策中，将 背景与不完备形式背景。本文研究建立在完备形 二支决策进而拓展为更符合现实决策情况的三支 式背景之上。对完备形式背景的研究中，研究方 决策理论。三支决策被引入概念格理论，Q等) 向通常分为对三支概念的属性约简、概念构建以 提出了三支概念的定义，将三支概念分为对象三 及其他方面的研究。在属性约简方面，Ren等侧 设计了4种属性约简方法，对4种约简方法之间 收稿日期：2019-04-10. 的联系进行了分析；在三支概念构建方面，Qi等 基金项目：国家自然科学基金项目(61572011)：河北省自然科 学基金项目(A2018201117). 在对标准形式概念的分析基础上，设计了一种利 通信作者：武秀.E-mail:yxwxhb@126.com 用标准概念求得三支概念的方法：汪文威等在
DOI: 10.11992/tis.201904022 三支概念的一种构建方法 毛华，武秀 （河北大学 数学与信息科学学院，河北 保定 071002） 摘 要：三支概念构建是三支形式概念分析的研究内容之一。为丰富三支概念的研究内容，利用矩阵结构，提 出一种三支概念构建算法。首先，给出属性矩阵的定义，并设计利用属性矩阵构建属性三支概念的算法过程， 对实例进行算法运算，以此对算法步骤进行说明，对算法正确性进行了相应验证。其次，定义对象矩阵，并设 计依据此矩阵构建对象三支概念的算法，对实例进行算法运算。经上述研究验证，所提算法正确且有效。研究 结果为三支概念在数据处理中的应用提供了更多选择。 关键词：形式背景；标准概念；三支概念；对象三支概念；属性三支概念；矩阵；属性矩阵；对象矩阵 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2020)03−0514−06 中文引用格式：毛华, 武秀. 三支概念的一种构建方法 [J]. 智能系统学报, 2020, 15(3): 514–519. 英文引用格式：MAO Hua, WU Xiu. A new method for constructing three-way concept[J]. CAAI transactions on intelligent systems, 2020, 15(3): 514–519. 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. Keywords: formal context; classical concept; three-way concept; object-induced three-way concept; attribute-induced three-way concept; matrix; attribute matrix; object matrix 概念格是由 Wille[1] 于 1982 年提出的理论，一 般可用于解决数据处理等相关的问题。Yao[2] 于 2009 年将延迟决策引入粗糙集的二支决策中，将 二支决策进而拓展为更符合现实决策情况的三支 决策理论。三支决策被引入概念格理论，Qi 等 [3] 提出了三支概念的定义，将三支概念分为对象三 支概念与属性三支概念。 从完备性方面区分，形式背景分为完备形式 背景与不完备形式背景。本文研究建立在完备形 式背景之上。对完备形式背景的研究中，研究方 向通常分为对三支概念的属性约简、概念构建以 及其他方面的研究。在属性约简方面，Ren 等 [4] 设计了 4 种属性约简方法，对 4 种约简方法之间 的联系进行了分析；在三支概念构建方面，Qi 等 [5] 在对标准形式概念的分析基础上，设计了一种利 用标准概念求得三支概念的方法；汪文威等[6] 在 收稿日期：2019−04−10. 基金项目：国家自然科学基金项目 (61572011)；河北省自然科 学基金项目 (A2018201117). 通信作者：武秀. E-mail：yxwxhb@126.com. 第 15 卷第 3 期 智 能 系 统 学 报 Vol.15 No.3 2020 年 5 月 CAAI Transactions on Intelligent Systems May 2020
第3期 毛华，等：三支概念的一种构建方法 ·515· CbO算法的基础上进行调整，提出了CbO3C算法 A={m∈MNg∈A(Im)》 用于构建三支概念；Qian等利用上位背景和下 属性集合BcM,定义 位背景，设计了一种三支概念构建方法；Mao等倒 B={g∈GVm∈B(Im)} 研究了标准概念与对象（属性）三支概念间的关 如果A=B和B=A同时成立，则称(X,A)为 系，并根据所得关系设计了构建三支概念的算 一个标准形式概念。所有负算子“”下成立的标 法；在其他方面，刘琳等利用属性三支概念对规 准形式概念(X,A)记成集合NCL(G,M,)。 则提取问题进行了讨论；Singhto通过对中智图、 定义3假设(G,M,D形式背景，={x∈Gx∈A',x∈B}=A'nB 支概念格方面的研究参考文献[12-16。 (G,M,D是一个形式背景。：DP(G)→P(M)分别为集合XY≤G和ASM 美争等可定义了对象-概念辨识矩阵来研究三支 上的基于属性导出的算子。算子运算方式如下： 近似概念的约简问题；陈雪等利用差别矩阵及 A=(A°，A), 差别函数计算得到了决策形式背景下的属性约简 (XY)>={w∈Mv∈X',veY=XnY 结果。 定义4形式背景(G,M,D,如果在对象集 本文将矩阵思想与三支概念构建的研究相结 合X二G,属性集合A,BSM上，X=(A,B)和 合，定义出属性（对象）矩阵，并利用属性（对象） (4,B)>=X同时成立，则称(X,(A,B)为对象三支 矩阵结构设计了构建三支概念的算法。 概念。全体(X,Y,A)记人集合OEL(G,M,D。 任意三支概念(X(A,B)和(Y,(C,D)之间的关 1基础知识 系定义如下： 对于相对成熟的矩阵理论，在此不做赘述，相 (X,(A,B)≤(Y,(C,D)台XSY台(C,D)≤(A,B) 性质1I对于集合XX1,X2cG:A,A,A2,B,B, 关内容详见文献[19]。本节将对利用到的标准形 B2SM,则有以下性质成立： 式概念及三支概念的一些定义及性质进行说明， (OE)XX,(A.B)C(A,B) 其中标准形式概念的内容详见文献[20]，三支概 (OE2)X1X2→X5≤X,(A1,B1)∈(A2,B2)→ 念的相关知识详见文献[3,5]。 (A2,B2)>≤(A1,B)> 定义10形式背景(G,M,D是由两个集合G (OE3)X=X-,(A,B)=(A,B)> 和M以及G与M间的二元关系I组成。G为对 (OE)XC(A,B)(A,B)CX 象集，M为属性集，IcG×M。在对象集合AsG (OEs)(XiUX2)=Xn,((A1,B)U(A2 中，令 B2)=(A1,B1)>n(A2B2) (OE6)(X1nX2)2XUX,(41,B1)n(A2 A':={m∈MLm对于任意g∈A} B2)>=(41,B1)>U(A2,B2) 其中Im表示对象3与属性m间满足二元关系 定义51形式背景(G,M,D,如果在属性集 I(或者对象g具有属性m)。 合ASM,对象集合XY二G上A=(X)和(X,Y)>=A 在属性集合BSM中，令 同时成立，则称(X,Y),A)为属性三支概念。全体 B:={g∈Gm对于任意m∈B吲 三支概念(X,Y),A)记入集合AEL(G,M,)。 若对集合A、B有A'=B和B=A同时成立， 对于任意的属性三支概念(X,),A)和 则(4，B)称为一个标准形式概念。其中标准形式 (Z,W,B),给出如下定义： 概念的外延为A,标准形式概念的内涵为B。 (X,Y),A)≤(Z,W,B)台(X,Y≤(Z,W)台B三A 所有基于正算子“”形成的概念(A,B)构成集 性质2的在集合XX1,X2,YY,Y2CG,A,A,A2S 合CL(G,M,D M上有以下性质成立： 任意的概念(A1,B1)与(42，B2)间的关系如下： (AE1)(X)(X,Y)>,AA> A1,B1)≤(A2,B2)台A1≤A2(台B12B2) (AE2)(Xi,Yi)C(X2,Y2)=(X2,Y2)C(Xi,Yi) 定义22o1假设(G,M,是一个形式背景， A1二A2→A2CA F=(G×M0-I,对象集合AcG,定义 (AE)(X,Y>=(X,Y)2,A=A
CbO 算法的基础上进行调整，提出了 CbO3C 算法 用于构建三支概念；Qian 等 [7] 利用上位背景和下 位背景，设计了一种三支概念构建方法；Mao 等 [8] 研究了标准概念与对象 (属性) 三支概念间的关 系，并根据所得关系设计了构建三支概念的算 法；在其他方面，刘琳等[9] 利用属性三支概念对规 则提取问题进行了讨论；Singh[10] 通过对中智图、 中智格和 Gödel 剩余格的性质分析，设计了基于 模糊概念格生成分量式三支模糊概念的方法，并 将其层次顺序可视化；Singh[11] 利用单值中智图的 概念格的性质对医学数据集进行分析，提出了计 算三支模糊概念的欧几里德距离的方法。其他三 支概念格方面的研究参考文献 [12-16]。 在采用矩阵结构进行三支概念的研究中，李 美争等[17] 定义了对象−概念辨识矩阵来研究三支 近似概念的约简问题；陈雪等[18] 利用差别矩阵及 差别函数计算得到了决策形式背景下的属性约简 结果。 本文将矩阵思想与三支概念构建的研究相结 合，定义出属性（对象）矩阵，并利用属性（对象） 矩阵结构设计了构建三支概念的算法。 1 基础知识 对于相对成熟的矩阵理论，在此不做赘述，相 关内容详见文献 [19]。本节将对利用到的标准形 式概念及三支概念的一些定义及性质进行说明， 其中标准形式概念的内容详见文献 [20]，三支概 念的相关知识详见文献 [3, 5]。 (G, M,I) G M G M I G M I ⊆ G × M A ⊆ G 定义 1 [20] 形式背景 是由两个集合 和 以及 与 间的二元关系 组成。 为对 象集， 为属性集， 。在对象集合 中，令 A ∗ := {m ∈ M|Igm对于任意g ∈ A} Igm g m I g m 其中 表示对象 与属性 间满足二元关系 (或者对象 具有属性 )。 在属性集合 B ⊆ M 中，令 B ∗ := {g ∈ G|Igm对于任意m ∈ B} A ∗ = B B ∗ = A (A,B) A B 若对集合 A、B 有 和 同时成立， 则 称为一个标准形式概念。其中标准形式 概念的外延为 ，标准形式概念的内涵为 。 ∗ (A,B) CL(G, M,I) 所有基于正算子“ ”形成的概念 构成集 合 。 任意的概念 (A1,B1) 与 (A2,B2) 间的关系如下： (A1 ,B1) ⩽ (A2 ,B2) ⇔ A1 ⊆ A2(⇔ B1 ⊇ B2) (G, M,I) I c = (G × M)− I A ⊆ G 定义 2 [ 2 0 ] 假设 是一个形式背景， ，对象集合 ，定义 A ∗¯ = {m ∈ M|∀g ∈ A(I c gm)} 属性集合 B ⊆ M ，定义 B ∗¯ = {g ∈ G|∀m ∈ B(I c gm)} A ∗¯=B B ∗¯ = A (X,A) ∗¯ (X,A) NCL(G, M,I) 如果 和 同时成立，则称 为 一个标准形式概念。所有负算子“ ”下成立的标 准形式概念 记成集合 。 (G, M,I) : DP(M) → P(G) X ⊆ G A,B ⊆ M 定义 3 [5] 假设 形式背景， 和 分别为集合 和 上的基于对象导出的算子。算子运算方 式如下： X = {x ∈ G|x ∈ A ∗ , x ∈ B ∗¯ } = A ∗ ∩ B ∗¯ (G, M,I) : DP(G) → P(M) X,Y ⊆ G A ⊆ M 是一个形式背景。 和 分别为集合 和 上的基于属性导出的算子。算子运算方式如下： A = {v ∈ M|v ∈ X ∗ , v ∈ Y ∗¯ } = X ∗ ∩Y ∗¯ (G, M,I) X ⊆ G A,B ⊆ M X = X (X,(A,B)) ((X,Y),A) OEL(G, M,I) 定义 4 [5] 形式背景 ，如果在对象集 合 ，属性集合 上 ， 和 同时成立，则称 为对象三支 概念。全体 记入集合 。 任意三支概念 (X,(A,B)) 和 (Y,(C,D)) 之间的关 系定义如下： (X,(A,B)) ⩽ (Y,(C,D)) ⇔ X ⊆ Y ⇔ (C,D) ⊆ (A,B) X,X1,X2 ⊆ G;A,A1,A2,B,B1, B2 ⊆ M 性质 1 [5] 对于集合 ，则有以下性质成立： (OE1) X ⊆ X ,(A,B) ⊆ (A,B) ·> ⊆ (A1 ,B1) ·> (OE3) X = (A,B) ·> (OE4) X ⊆ (A,B) ·> ⇔ (A,B) ⊆ X = (A1 ,B1) ·> ∩(A2 ,B2) ·> (OE6) (X1 ∩ X2) = (A1 ,B1) ·> ∪(A2 ,B2) ·> (G, M,I) A ⊆ M X,Y ⊆ G A = A ((X,Y),A) ((X,Y),A) AEL(G, M,I) 定义 5 [5] 形式背景 ，如果在属性集 合 ，对象集合 上 和 同时成立，则称 为属性三支概念。全体 三支概念 记入集合 。 ((X,Y),A) ((Z,W),B) 对于任意的属性三支概念 和 ，给出如下定义： ((X,Y),A) ⩽ ((Z,W),B) ⇔ (X,Y) ⊆ (Z,W) ⇔ B ⊆ A X,X1,X2,Y,Y1,Y2 ⊆ G,A,A1 A2 ⊆ M 性质 2 [5] 在集合 ， 上有以下性质成立： (AE1) (X,Y) ⊆ (X,Y) ·> (AE2) (X1 ,Y1) ⊆ (X2 ,Y2) ⇒ (X2 ,Y2) ·> ⊆ (X1 ,Y1) ·> A1 ⊆ A2 ⇒ A = (X,Y) ·> ,A <· 第 3 期 毛华，等：三支概念的一种构建方法 ·515·
·516· 智能系统学报 第15卷 (AE)(X,Y)∈A台A二(X, 7)如果s≤P,则执行5)：反之j=j+1,执行8)： (AE)(X1,Y)U(X2,Y2)>=(X1,Y1)>n(X2 8)如果j≤1P叫，则执行4)：反之i=i+1,执行9)： Y2),(41UA2)=AnA 9)如果i≤P1,则执行3)：反之执行10)： (AE6)(X1,Y1)n(X2,Y2)>2(X1,Y1)>U(X2, Y2)>,(41nA2)2AUA 10)对更新过的集合P递归调用2)~9)，直至 集合P不再更新； 2概念的构建 11)Y=0,i=1; 12)j=i: 2.1依据属性矩阵构建属性三支概念 13)如果w≤w,则Y=YU{aU{ah,j=j+1, 定义6形式背景(G,M,D,其中属性集合 执行14)： M={a1,a2,…,an}。定义：令W=(wwj=(gna 14)如果j≤n,则执行13)：反之i=i+1并执 ana:a,aeM:neZt:i,j=1,2,…,n。则W为一个 行15)： n×n的属性矩阵，易得属性矩阵W为对称矩阵。 15)如果i≤n,则执行12)：反之执行16)： 例1形式背景(G,M1,)如表1所示，在此 16)输出三支概念(w,Y)。 基础上构建属性矩阵W。 因为集合P为有限集合，所以算法1在有限 表1形式背景(G1,M1,I) 步后可以停止。 Table 1 Formal context(G,M,1) 复杂度分析： GI b c d 1)首先，生成属性矩阵的复杂度为OM/2): 1 + X 其次，得外延集的复杂度为O(Me:最后，寻找 2 X 满足条件的w对应的属性集，共比较M(M+1)/2 3 + 次，循环P叫次，所以复杂度为OMM+1)P/2): 因此，算法1的复杂度为O(Me:)。 4 + 2)文献[5]中的复杂度受生成标准形式概念 注：本文中，当对象具有某属性时在表中用×”表示，反之则 的复杂度的影响，选择的方法不同，复杂度则不 为空 同；其次，通过找等价类进行概念构建的最大时 由表1可知：w11=(ana,dna)=(123,4),w2= 间复杂度为max{24M,2Gww,因此，两相比较，本 (acnb,dnb)=(3,0,…,w34=(cnd,c2nd)=(2,3), 文方法较好。 w44=(dnd,d产nd)=(24,13)。 3)文献[6]中的时间复杂度为OGM1C), 所以 其中C表示属性三支核心概念的个数。两相比 较，本文算法较好。 (123,4) (3,0) (12,0) (2.0) 下面给出算法1正确性的理论支持。 (34.12) (4,0) (4.1) 定理1(G,M,D为一形式背景，基于属性矩 W= (124,3) (24,3) 阵W得到的概念均为属性三支概念。 证明如果(A,A)不是属性三支概念，则 (24,13) A>≠A。令A>=A00 构建属性三支概念的算法过程如算法1。 下面证明A6=A:由AE1、AE2性质可知， 算法1属性三支概念生成算法。 AA>=A0,则A6二A;另外，由A=A可知， 输入形式背景(G,M,). A>,所以A≤A6。因此 输出AEL(G,M,I)八(G,G),O)1e A6=A成立。 1)生成形式背景(G,M,)的属性矩阵W,并 定理2(G,M,)为一形式背景，矩阵W 将属性矩阵W的所有元素构成的集合记成集合P: 为(G,M,D上的属性矩阵，则算法1可得到除 2)i=1; (G,G),O)外的所有属性三支概念。 3)j=1 证明属性矩阵W中的元素构成的集合记 4)s=1; 为集合P,下面分3种情况对集合P进行讨论： 5)w=w∩ws; ①若算法1中5)的结果为空集，因为0为任何集 6)如果wP,则P=PU{wl,s=s+1并执行 合的子集，所以矩阵W中包含了所有的外延； 7);反之s=s+1,并执行7)： ②若算法1中5)的结果仍属于集合P,则集合P
(AE4) (X,Y) ⊆ A (AE5) ((X1 ,Y1)∪(X2 ,Y2))·> = (X1 ,Y1) ·> ∩(X2 , Y2) ·> ,(A1 ∪ A2) ⊇ (X1 ,Y1) ·> ∪(X2 , Y2) ·> ,(A1 ∩ A2) , A A = A0 证明 如果 不是属性三支概念，则 。令 。 A = A0 A = A0 A <· A <· ⊆ A <· 0 A <· 0 = A <· 下面证明 ：由 AE1、AE2 性质可知， ，则 ；另外，由 可知， ，又因为 ，所以 。因此 成立。 (G, M,I) W (G, M,I) ((G,G),Ø) 定 理 2 为一形式背景，矩阵 为 上的属性矩阵，则算法 1 可得到除 外的所有属性三支概念。 W P P Ø W P P 证明 属性矩阵 中的元素构成的集合记 为集合 ，下面分 3 种情况对集合 进行讨论： ①若算法 1 中 5) 的结果为空集，因为 为任何集 合的子集，所以矩阵 中包含了所有的外延； ②若算法 1 中 5) 的结果仍属于集合 ，则集合 ·516· 智 能 系 统 学 报 第 15 卷
第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·
·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 of
4) 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 International 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 threeway 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]. Knowledge-based systems, 2016, 91: 143–151. [5] 汪文威, 祁建军. 三支概念的构建算法 [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. [6] QIAN Ting, WEI Ling, QI Jianjun. Constructing three-way concept lattices based on apposition and subposition of [7] ·518· 智 能 系 统 学 报 第 15 卷
第3期 毛华，等：三支概念的一种构建方法 ·519· formal contexts[J].Knowledge-based systems,2017,116: Fuzzy sets and systems,2017,317:121-132 39-48. [17刀李美争，王国胤.三支近似概念格中基于对象-概念辨 [8]MAO Hua,ZHAO Shufeng,YANG Lanzhen.Relation- 识矩阵的属性约简方法).控制与决策，2016,31(10) ships between three-way concepts and classical 1779-1784. concepts[J].Journal of intelligent and fuzzy systems,2018, LI Meijing,WANG Guoyin.Attribute reduction based on 35(1):1063-1075. object-concept indentified matrix in approximate three- [9]刘琳，钱婷，魏玲.基于属性导出三支概念格的决策背景 way concept lattices[J].Control and decision,2016, 规则提取[).西北大学学报（自然科学版），2016,46(4)： 31(10):1779-1784. 481-487. [18]陈雪，魏玲，钱婷.基于AE-概念格的决策形式背景属 LIU Lin,QIAN Ting,WEI Ling.Rules extraction in form- 性约简[J,山东大学学报（理学版），2017,52(12)： al decision contexts based on attribute-induced three-way 95-103 concept lattices[J].Journal of Northwest University (natur- CHEN Xue,WEI Ling,QIAN Ting.Attribute reduction al science edition),2016,46(4):481-487. of decision formal context based on AE concept [10]SINGH P K.Three-way fuzzy concept lattice representa- lattices[J].Journal of Shandong University (science edi- tion using neutrosophic set[J].International journal of ma- tion),2017,52(12):95-103. chine learning and cybernetics,2016,8(1):69-79. [19]李乔.矩阵论八讲[M.上海：上海科学技术出版社， [11]SINGH P K.Medical diagnoses using three-way fuzzy 1988. concept lattice and their Euclidean distance[J].Computa- [20]GANTER B,WILLE R.Formal concept analysis:math- tional and applied mathematics,2018,37(3):3283-3306. [1]YU Huiying,LI Qingguo,CAI Mingjie.Characteristics of ematical foundations[M].Berlin Heidelberg:Springer- Verlag,1999. three-way concept lattices and three-way rough concept lattices[J].Knowledge-based systems,2018,146: 作者简介： 181-189. 毛华，教授，博士，主要研究方向 [13]KONECNY J.On efficient factorization of standard fuzzy 为概念格、图论、拟阵论。发表学术论 concept lattices and attribute-oriented fuzzy concept lat- 文100余篇。 tices[J].Fuzzy sets and systems,2018,351:108-121. [14]CIOBANU G,VAIDEANU C.A note on similarity rela- tions between fuzzy attribute-oriented concept lattices[J]. Information sciences,2018,460-461:254-263 [15]LI Meizheng,WANG Guoyin.Approximate concept con- 武秀，硕士研究生，主要研究方向 struction with three-way decisions and attribute reduction 为概念格、图论。 in incomplete contexts[J].Knowledge-based systems, 2016,91:165-178 [16]CIOBANU G,VAIDEANU C.An efficient method to factorize fuzzy attribute-oriented concept lattices[J]
formal contexts[J]. Knowledge-based systems, 2017, 116: 39–48. 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. [8] 刘琳, 钱婷, 魏玲. 基于属性导出三支概念格的决策背景 规则提取 [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. [9] 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. [10] 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. [11] 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. [12] 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. [13] CIOBANU G, VĂIDEANU C. A note on similarity relations between fuzzy attribute-oriented concept lattices[J]. Information sciences, 2018, 460-461: 254–263. [14] 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. [15] CIOBANU G, VĂIDEANU C. An efficient method to factorize fuzzy attribute-oriented concept lattices[J]. [16] Fuzzy sets and systems, 2017, 317: 121–132. 李美争, 王国胤. 三支近似概念格中基于对象−概念辨 识矩阵的属性约简方法 [J]. 控制与决策, 2016, 31(10): 1779–1784. LI Meijing, WANG Guoyin. Attribute reduction based on object-concept indentified matrix in approximate threeway concept lattices[J]. Control and decision, 2016, 31(10): 1779–1784. [17] 陈雪, 魏玲, 钱婷. 基于 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. [18] 李乔. 矩阵论八讲 [M]. 上海: 上海科学技术出版社, 1988. [19] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin Heidelberg: SpringerVerlag, 1999. [20] 作者简介： 毛华，教授，博士，主要研究方向 为概念格、图论、拟阵论。发表学术论 文 100 余篇。 武秀，硕士研究生，主要研究方向 为概念格、图论。 第 3 期 毛华，等：三支概念的一种构建方法 ·519·