.522. 智能系统学报 第11卷 1)由一条边构成，也即自环： M,I),w),ij,t=1,2,…, ，。则进行4)。 2)由两条边构成，也即重边： ②若：∩0=w,0,W(R(0,M,),0),i,j,t= 3)由3条或3条以上的边构成，也即非自环非 ,则将W,={,,∩0，=，e,,6 1,2,…,2 重边的圈。 证明由定义2中3)可知，自环是只有一个顶 W(R(O,M,I),o),0,EW(R(0,M,I),e)}添加到 点的圈；重边是由两个顶点的圈：由定义2中3)可 W(R(O,M,I),w)中。将W,赋值给W,执行①。 知，非自环非重边的圈之顶点个数大于2。 4)取maxw,,开始寻找边上权值包含w,的最 当圈只有一个顶点时，根据定义2中3)可知， 大圈，记录权值心，最大圈的顶点为Y,对应概念为 此时的圈为一个自环： C={(A,B):A=w,B=Y}。 当圈有两个顶点时，根据定义2中3)可知，此 5)①根据4)的原则，若W中存在0+1，s=1,2, 时的圈为重边； …,|MP,则选定0+1，重复4)。 当圈的顶点个数大于2时，符合定义2中2)。 ②若W中不存在0+1，则停止。 因此，圈有且仅有自环、重边、非自环非重边的 若W(R(0,M,I),w)中的元素满足3)中的①， 圈3种情况。 若心，∩心，=0，或0：∩心=0，此处0：，0,0，∈W(R 定理1设(0，M,I)是一个形式背景，(R(0, M,I),w)是(O,M,I)对应的弱化的属性拓扑图，权 (0,M,),w),i,j,t=1,2,…, 1M2I 2 ,则能够进行 值最大圈一定能够生成一个概念。 4)、5),又因为W(R(0,M,I),w)是有限的，因此 证明由引理2可知，弱化的属性拓扑图的权 有限步后算法可以停止。 值w最大圈有且仅有3种情况，下面关于这3种情 若W(R(0,M,I),w)中的元素满足w:∩心= 况分别说明。 M,此 1)当圈为自环时 ,0,gW(R(0,M,),0),i,t=1,2,…, 2 m∈M,圈Y={m},由弱化的属性拓扑图的构造 时会将新生成的w,添加到W(R(O,M,I),0)中，由 1)可知，有meT。根据引理1，(m',m)∈β(0，M, 于w,地，心，c0,0为有限的，因此经过有限步后 I)。而m'=w(m,m),因此，((m,m),m)∈β(0， 一定可以进行3)中①，因此有限步后算法可停止。 M,I)。 2.3算法分析 2)当圈为重边时 根据文献[9]，可以看出1)的复杂度为 m1,m2∈M,圈Y={m1,m2},由弱化的属性拓扑 0门：步骤2将属性拓扑图弱化，首先判断每 图的构造2)可知，不存在其他权值为w(m1,m2)的 边，即不存在其他顶m,m∈M,使w(m1,m2)∈ 个属性是否为顶层属性，其复杂度为O(|M),其 0(m,m),i有，i≥3，j≥1。这就是说，除m1,m2 次需要判断是否为不能构成权值心的最大圈，其复 外，不存在其他属性所拥有的对象集包含w(m, 杂度为0 (MP (MP 2 ,所以2)的复杂度为02)： m2),所以(w(m1,m2),Y)eβ(0，M,)。 3)=当圈的顶点个数大于等于3时 若是3)中①，首先对W中任意两元素取交，有 m1,m2,…,m:∈M,i≥3，若圈Y={m1,m2,… orD个元素，进行og 次，若是3)中②， m},证明过程与第2种情况类似，易证(0(m1, m2),Y)∈β(0，M,I)。 对新生成的集合W,重复次3)，最多重复0次，所 引理3设W(R(0,M,I),0)是一个集族，则 以3)的复杂度为0 (01Wn12 ,其中W,伪元素 任意的其中0：，0，0，∈W(R(0,M,I),0),0.生W 2 IM2| 最多的集合；4)中，每到一个属性节点最多需要判 ((0,M,),0),,u=1,2,,2,它们之间 断M1次该节点是否在当前权值w的最大圈中， 的关系有且仅有以下3种情况之一发生： 最多判断M饮，所以4)的复杂度为0(|M2):5) 1)0:∩w:=0; 的复杂度为0(|OW.)。 2)0:∩0；=0， 因此，整个算法的复杂度为O(2wK10)。 3)0:∩0；=10u9 引理2圈有且仅有以下3种情况： 证明根据文献[15]，可得若W(R(0,M,I),Ｍ，Ｉ），ｗ）， ｉ，ｊ，ｔ ＝ １，２，…， Ｍ ２ ２ 。 则进行 ４）。 ②若 ｗｉ∩ｗｊ ＝ｗｔ，ｗｔÏＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ，ｔ ＝ １，２，…， Ｍ ２ ２ ，则将 Ｗｒ ｒ ＝ ｛ｗｔ：ｗｉ∩ｗｊ ＝ｗｔ，ｗｉ， ｗｊ，Î Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｗｔ ÏＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）｝添加到 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）中。 将 Ｗｒ ｒ赋值给 Ｗｒ，执行①。 ４）取 ｍａｘ êｗｓ ú，开始寻找边上权值包含 ｗｓ的最 大圈，记录权值 ｗｓ 最大圈的顶点为 Ｙ，对应概念为 Ｃ ＝ ｛（Ａ，Ｂ）： Ａ ＝ｗｓ， Ｂ ＝ Ｙ｝。 ５）①根据 ４）的原则，若 Ｗ 中存在 ｗｓ ＋１ ，ｓ ＝ １，２， …， êＭ ú ２ ，则选定 ｗｓ ＋１ ，重复 ４）。 ②若 Ｗ 中不存在 ｗｓ ＋１ ，则停止。 若 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）中的元素满足 ３）中的①， 若 ｗｉ∩ｗｊ ＝ Æ，或 ｗｉ∩ｗｊ ＝ ｗｔ，此处 ｗｉ， ｗｊ，ｗｔ ÎＷ（Ｒ （Ｏ，Ｍ，Ｉ），ｗ）， ｉ，ｊ，ｔ ＝ １，２，…， Ｍ ２ ２ ，则能够进行 ４）、５），又因为êＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ） ú是有限的，因此 有限步后算法可以停止。 若 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ） 中的元素满足 ｗｉ ∩ｗｊ ＝ ｗｔ，ｗｔÏＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ，ｔ ＝ １，２，…， Ｍ ２ ２ ，此 时会将新生成的 ｗｔ添加到 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）中，由 于 ｗｒ¹ｗｓ，ｗｔ ÍＯ，êＯ ú为有限的，因此经过有限步后 一定可以进行 ３）中①，因此有限步后算法可停止。 ２．３ 算法分析 根据 文 献 ［ ９ ］， 可 以 看 出 １ ） 的 复 杂 度 为 Ｏ Ｍ ２ ２ æ è ç ö ø ÷ ；步骤 ２ 将属性拓扑图弱化，首先判断每 个属性是否为顶层属性，其复杂度为 Ｏ( Ｍ ) ，其 次需要判断是否为不能构成权值 ｗ 的最大圈，其复 杂度为 Ｏ Ｍ ２ ２ æ è ç ö ø ÷ ，所以 ２）的复杂度为 Ｏ Ｍ ２ ２ æ è ç ö ø ÷ ； 若是 ３） 中 ①， 首先对 Ｗ 中任意两元素取交， 有 Ｏ( Ｗ ) 个元素，进行 Ｏ Ｗ ２ ２ æ è ç ö ø ÷ 次，若是 ３） 中②， 对新生成的集合 Ｗｒ ｒ重复次 ３），最多重复êＯ ú次，所 以 ３）的复杂度为 Ｏ Ｏ Ｗｒｒ ２ ２ æ è ç ö ø ÷ ，其中êＷｒ ｒ ú为元素 最多的集合；４） 中，每到一个属性节点最多需要判 断êＭ ú－１ 次该节点是否在当前权值 ｗ 的最大圈中， 最多判断êＭ ú次，所以 ４）的复杂度为 Ｏ Ｍ ２ ( ) ；５） 的复杂度为 Ｏ Ｏ Ｗｒｒ ( ) 。 因此，整个算法的复杂度为 Ｏ ２ Ｍ × Ｏ ( ) 。 引理 ２ 圈有且仅有以下 ３ 种情况： １）由一条边构成，也即自环； ２）由两条边构成，也即重边； ３）由 ３ 条或 ３ 条以上的边构成，也即非自环非 重边的圈。 证明 由定义 ２ 中 ３）可知，自环是只有一个顶 点的圈；重边是由两个顶点的圈；由定义 ２ 中 ３）可 知，非自环非重边的圈之顶点个数大于 ２。 当圈只有一个顶点时，根据定义 ２ 中 ３）可知， 此时的圈为一个自环； 当圈有两个顶点时，根据定义 ２ 中 ３）可知，此 时的圈为重边； 当圈的顶点个数大于 ２ 时，符合定义 ２ 中 ２）。 因此，圈有且仅有自环、重边、非自环非重边的 圈 ３ 种情况。 定理 １ 设（Ｏ，Ｍ，Ｉ）是一个形式背景，（Ｒ（Ｏ， Ｍ，Ｉ），ｗ）是（Ｏ，Ｍ，Ｉ）对应的弱化的属性拓扑图，权 值最大圈一定能够生成一个概念。 证明 由引理 ２ 可知，弱化的属性拓扑图的权 值 ｗ 最大圈有且仅有 ３ 种情况，下面关于这 ３ 种情 况分别说明。 １）当圈为自环时 ｍ ÎＭ，圈 Ｙ ＝ ｛ｍ｝，由弱化的属性拓扑图的构造 １）可知，有 ｍ ÎＴ。 根据引理 １，（ｍ′， ｍ） Îβ（Ｏ，Ｍ， Ｉ）。 而 ｍ′ ＝ ｗ（ｍ，ｍ），因此，（ｗ（ｍ，ｍ）， ｍ）Îβ（Ｏ， Ｍ，Ｉ）。 ２）当圈为重边时 ｍ１ ，ｍ２ÎＭ，圈 Ｙ ＝ ｛ｍ１ ，ｍ２ ｝，由弱化的属性拓扑 图的构造 ２）可知，不存在其他权值为 ｗ（ｍ１ ，ｍ２ ）的 边，即不存在其他顶 ｍｉ， ｍｊ ÎＭ，使 ｗ （ ｍ１ ， ｍ２ ） Í ｗ（ｍｉ， ｍｊ）， ｉ ¹ｊ， ｉ≥３， ｊ≥１。 这就是说，除 ｍ１ ， ｍ２ 外，不存在其他属性所拥有的对象集包含 ｗ（ ｍ１ ， ｍ２ ），所以（ｗ（ｍ１ ，ｍ２ ），Ｙ）Îβ（Ｏ，Ｍ，Ｉ）。 ３）＝ 当圈的顶点个数大于等于 ３ 时 ｍ１ ，ｍ２ ， … ，ｍｉÎＭ，ｉ≥３，若圈 Ｙ ＝ ｛ ｍ１ ，ｍ２ ， … ｍｉ｝，证明过程与第 ２ 种情况类似，易证 （ ｗ （ ｍ１ ， ｍ２ ），Ｙ）Îβ（Ｏ，Ｍ，Ｉ）。 引理 ３ 设 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）是一个集族，则 任意的其中 ｗｉ， ｗｊ， ｗｔ ÎＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｗｕ ÏＷ （Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ，ｔ，ｕ ＝ １，２，…， Ｍ ２ ２ ，它们之间 的关系有且仅有以下 ３ 种情况之一发生： １）ｗｉ∩ｗｊ ＝ Æ； ２）ｗｉ∩ｗｊ ＝ｗｔ； ３）ｗｉ∩ｗｊ ＝ｗｕ 。 证明 根据文献［１５］，可得若 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ）， ·５２２· 智 能 系 统 学 报 第 １１ 卷