第3期 毛华，等：利用二元拟阵K。图的一种建格方法 ·337. 层概念的集合，V2是第3层概念的集合，则在K。图 为K.时，顶点数为n,与基顶点相连的边为n-1,即 中概念之间满足定义6，(C1,b1)≤(C2,b2)一C, 第2层的概念为n-1个，根据属性b1,b2,…,bn-找 C(台b,二b,),根据子概念-父概念的关系建立连线 到所对应的基最小圈对象。 是一个二部图，如图1所示。 3)找第3层的概念，根据完全图K的特点，基 (C.C;b (C,C b,) (CCb) 最小圈的个数为(-1)-(n-1),即第3层有概念 2 n(n-1)-(n-1)个，由对象C,C2,…,Cg(-,找 ● (Cbbb) (Cbbb) (C,6bb.) 到所对应的属性。 4)第1层中的元（概念），与且仅与第2层的每 图1K,图的二部图 一个元分别连线，第4层的元与且仅与第3层的每 Fig.1 Bipartite graph of K,diagram 个元分别连线，第2层的元与第3层的元之间的 再把第1层和第4层概念(0，{})和({}，P)加 连线关系可以根据定理2进行。这样就可以得到所 进图1，根据定理1建立概念格得Hasse示图，如图 有应该存在的连线。即根据定义6和引理2的偏序 2所示。Hasse图是利用概念之间的泛化和特化进 关系(C1,b)≤(C2,b2)台C1SC2(台b,≤b,),满足 行绘制的，由于概念格的完备性，概念格确定了，其 概念格子概念-父概念的关系，把第1层的概念(0， Hasse图也唯一确定了。概念格最上层是全概念， {})与第2层的概念建立连线，第4层的概念({}， 最下层是空概念。Hasse图中的边分别连接在直接 P)与第3层概念建立连线加入到步骤2)和3)组成 父概念和直接子概念之间。 的二部图中。 (C.C.C) 2.4.3算法的复杂度 根据形式背景的特殊性，此处得到的概念格有 且仅有4层。 (C.C.b)O ○CC,b,) ○(CCb) 第1层的概念和第四层的概念分别是(O,{}) 和({}，P)。 第2层的概念与基顶点连接的边个数为n-1(n (C..bb.b) ○Cb,b,b) ○(Cb,b,b,) 表示顶点数)。 第3层的概念根据K,图所产生的基最小圈个 数N来决定，N=(n1)-(n-1)。根据第2层的概 (,bbbbbb) 2 图2K,图的概念格 念加入属性，即K。图的边，根据属性b1,b2,…,bn- Fig.2 Concept lattice of K diagram 找到所对应的基最小圈对象，知寻找的次数为W: 第3层加入基最小圈即概念的对象时，即K图里的 根据K,图的格结构，利用数学归纳法分别对 K图、K。图、K图进行建格，得出K图建立概念格 基最小圈，根据对象C,C2,…,C-),找到所 的一个算法过程。 对应的属性，可知寻找的次数为nN。即第2层和第 3层运算次数为nN+nN=2nN,复杂度为0(2nn2), 2.4.2算法过程 也就是0(n3)。 通过对特殊限制K图的规律发现，满足K图 与定义5和定义6找寻概念的方式（即参考文 二元标准矩阵特点的都可以建成一个Hasse示图。 献[22]中13页概念格的生成算法1)相比，本文提 对于具有这种特定形式背景的概念，用上面的建格 出的方法更有效。因为，如果存在1G1个对象，1M 方法进行建格，速度很快。下面给出对象是基最小 个属性，那么相应的概念格将可能包含2G或2m 圈，属性是边的形式背景的建格过程。 个概念，计算量太大。而本文构造的概念的算法方 输入形式背景(0，P,I)。 式，由于具有一定的规律性，大大减少了计算量。 输出集合C,(0,P,I)所有的概念。 1)C:={P',P}初始化属性集合B=☑。 3应用实例 2)找第2层的概念，根据规律知道，当完全图 超市里冷冻猪肉和冷鲜猪肉因储存时间的长层概念的集合，Ｖ２ 是第 ３ 层概念的集合，则在 Ｋｎ 图 中概念之间满足定义 ６，（Ｃ１ ，ｂ１ ）≤（Ｃ２ ，ｂ２ ）⇔Ｃ１⊆ Ｃ２（⇔ｂ２⊆ｂ１ ），根据子概念－父概念的关系建立连线 是一个二部图，如图 １ 所示。 图 １ Ｋ４ 图的二部图 Ｆｉｇ．１ Ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｏｆ Ｋ４ ｄｉａｇｒａｍ 再把第 １ 层和第 ４ 层概念（Ｏ，｛｝）和（｛｝，Ｐ）加 进图 １，根据定理 １ 建立概念格得 Ｈａｓｓｅ 示图，如图 ２ 所示。 Ｈａｓｓｅ 图是利用概念之间的泛化和特化进 行绘制的，由于概念格的完备性，概念格确定了，其 Ｈａｓｓｅ 图也唯一确定了。 概念格最上层是全概念， 最下层是空概念。 Ｈａｓｓｅ 图中的边分别连接在直接 父概念和直接子概念之间。 图 ２ Ｋ４ 图的概念格 Ｆｉｇ．２ Ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｏｆ Ｋ４ ｄｉａｇｒａｍ 根据 Ｋ４ 图的格结构，利用数学归纳法分别对 Ｋ５ 图、Ｋ６ 图、Ｋｎ 图进行建格，得出 Ｋｎ 图建立概念格 的一个算法过程。 ２．４．２ 算法过程 通过对特殊限制 Ｋｎ 图的规律发现，满足 Ｋｎ 图 二元标准矩阵特点的都可以建成一个 Ｈａｓｓｅ 示图。 对于具有这种特定形式背景的概念，用上面的建格 方法进行建格，速度很快。 下面给出对象是基最小 圈，属性是边的形式背景的建格过程。 输入 形式背景（Ｏ，Ｐ，Ｉ）。 输出 集合 Ｃ，（Ｏ，Ｐ，Ｉ）所有的概念。 １）Ｃ：＝ ｛Ｐ′，Ｐ｝初始化属性集合 Ｂ ＝⌀。 ２）找第 ２ 层的概念，根据规律知道，当完全图 为 Ｋｎ 时，顶点数为 ｎ，与基顶点相连的边为 ｎ－１，即 第 ２ 层的概念为 ｎ－１ 个，根据属性 ｂ１ ，ｂ２ ，…，ｂｎ－１找 到所对应的基最小圈对象。 ３）找第 ３ 层的概念，根据完全图 Ｋｎ 的特点，基 最小圈的个数为 ｎ（ｎ－１） ２ －（ ｎ－１），即第 ３ 层有概念 ｎ（ｎ－１） ２ －（ｎ－１）个，由对象 Ｃ１ ，Ｃ２ ，…，Ｃｎ（ｎ－１） ２ －（ｎ－１） ，找 到所对应的属性。 ４）第 １ 层中的元（概念），与且仅与第 ２ 层的每 一个元分别连线，第 ４ 层的元与且仅与第 ３ 层的每 一个元分别连线，第 ２ 层的元与第 ３ 层的元之间的 连线关系可以根据定理 ２ 进行。 这样就可以得到所 有应该存在的连线。 即根据定义 ６ 和引理 ２ 的偏序 关系（Ｃ１ ，ｂ１ ）≤（Ｃ２ ，ｂ２ ）⇔Ｃ１⊆Ｃ２（⇔ｂ２⊆ｂ１ ），满足 概念格子概念－父概念的关系，把第 １ 层的概念（Ｏ， ｛｝）与第 ２ 层的概念建立连线，第 ４ 层的概念（｛ ｝， Ｐ）与第 ３ 层概念建立连线加入到步骤 ２）和 ３）组成 的二部图中。 ２．４．３ 算法的复杂度 根据形式背景的特殊性，此处得到的概念格有 且仅有 ４ 层。 第 １ 层的概念和第四层的概念分别是（Ｏ，｛ ｝） 和（｛｝，Ｐ）。 第 ２ 层的概念与基顶点连接的边个数为 ｎ－１（ｎ 表示顶点数）。 第 ３ 层的概念根据 Ｋｎ 图所产生的基最小圈个 数 Ｎ 来决定，Ｎ＝ ｎ（ｎ－１） ２ －（ｎ－１）。 根据第 ２ 层的概 念加入属性，即 Ｋｎ 图的边，根据属性 ｂ１ ，ｂ２ ，…，ｂｎ－１ 找到所对应的基最小圈对象，知寻找的次数为 ｎＮ； 第 ３ 层加入基最小圈即概念的对象时，即 Ｋｎ 图里的 基最小圈，根据对象 Ｃ１ ，Ｃ２ ，…，Ｃｎ（ｎ＋１） ２ －（ｂ－１） ，找到所 对应的属性，可知寻找的次数为 ｎＮ。 即第 ２ 层和第 ３ 层运算次数为 ｎＮ＋ｎＮ ＝ ２ｎＮ，复杂度为 Ｏ（２ｎｎ ２ ）， 也就是 Ｏ（ｎ ３ ）。 与定义 ５ 和定义 ６ 找寻概念的方式（即参考文 献［２２］中 １３ 页概念格的生成算法 １）相比，本文提 出的方法更有效。 因为，如果存在｜ Ｇ ｜个对象， ｜ Ｍ ｜ 个属性，那么相应的概念格将可能包含 ２ ｜ Ｇ｜ 或 ２ ｜ Ｍ｜ 个概念，计算量太大。 而本文构造的概念的算法方 式，由于具有一定的规律性，大大减少了计算量。 ３ 应用实例 超市里冷冻猪肉和冷鲜猪肉因储存时间的长 第 ３ 期 毛华，等：利用二元拟阵 Ｋｎ 图的一种建格方法 ·３３７·