·840. 智能系统学报 第10卷 表3形式背景K 的共同属性不会多于其子集所具有的共同属性。所 Table 3 The formal context K; 以对象集A,具有的共同属性应该小于或等于其子 U a b c.g d e 集A,具有的共同的属性。 4110 100 性质2设(U,M,I)为一形式背景，对任意的 u,1110 1 属性集B,CB,CM,有 01001 l1(M:)≤l(M) 4400 11 1 成立，M,M:分别为B,、B2的最大对象满矩阵。 这里把属性f删除，将属性c与g合并成一个属 说明：该性质的依据就是具有的共同属性越多，则 性也不会影响概念格的结构。 其对象集的个数不会增多。所以具有属性集B,的对 由于对具有相同内涵的对象和具有相同外延的 象个数应该小于或等于具有属性集B,的对象个数。 属性的各自合并所得的概念格与原概念格同构。所 定义7若(A,B)为形式概念，则称由对象集 以在生成概念之前可以先把形式背景化为既约的， A所在的行和属性集B所在的列组成的矩阵M为 这样就会使形式背景变得简单些。 概念矩阵。 定理1概念矩阵一定是最大属性满矩阵和最 2满矩阵与概念 大对象满矩阵。 定义5设（U,M,I)为一形式背景，在其对应 证明：由定义5~7可直接得到结论。反之，定 的形式背景矩阵中，取出对象集A二U对应的任意 理1不一定成立，即最大属性满矩阵，最大对象满矩 行和属性集BCM对应的任意列组成新的矩阵 阵不一定是概念矩阵。如在例1中，对象u1与属性 M,则称M为形式背景矩阵的子矩阵。 acg组成的子矩阵为最大属性满矩阵，但由概念的 若子矩阵M的每个元素都为1，则称子矩阵 定义知(u,acfg)不是形式概念，又对象u1山2和属 性α组成的子矩阵为最大对象满矩阵，但由概念的 M为满矩阵。 定义知(u山2，α)不是形式概念，即可得出定理1的 在满矩阵M中，规定矩阵的列数即 逆不成立。 |B|为矩阵的属性秩，记为r(M)=|B|:矩阵MA 下面给出满矩阵是概念矩阵的一个充分条件： 的行数即|A为矩阵的对象秩，记为l(M)=A|, 定理2若满矩阵M攻，既是对象集A的最大 其中1·表示集合中元素的个数。 属性满矩阵，且是属性集B的最大对象满矩阵，则 定义6在形式背景矩阵中，对于对象集A二 满矩阵M是概念矩阵。 U,如果属性集BCM有 证明反证，假设满矩阵M不是概念矩阵，说 r(M)≤r(Mi),HYCM 明(A,B)不是概念即f(A)≠B或g(B)≠A成立。 成立，则称M为对象集A对应的最大属性满矩阵。 若f4)≠B,则存在对象集A2A,使f4')=B成 对偶地，可以定义最大对象满矩阵： 立，也就是说属性集B有更大的对象满矩阵，与满 在形式背景矩阵中，对于属性集B二M,如果 矩阵M是属性集B的最大对象满矩阵矛盾：同理 对象集ACU有 可证，若g(B)≠A,则存在属性集B2B,使 l(M)≤l(M),HX≤U g(B)=A成立，也就是说对象集A有更大的属性满 成立，则称M为属性集B对应的最大对象满矩阵。 矩阵，与满矩阵M是对象集A的最大属性满矩阵 说明：给定对象集，则其对应的最大属性满矩阵 矛盾，即假设不成立，得证。 是唯一的：给定属性集，则其对应的最大对象满矩阵 为了找出形式背景中所有的概念，根据定理1， 是唯一的。 可以先找出它的所有最大属性满矩阵或最大对象满 性质1设(U,M,I)为一形式背景，对任意的 矩阵，进而根据定理2判断那些满矩阵为概念矩阵， 对象集ACA2二U,有 最后得到所有的概念。 r(M:)≤r(M) 成立，MM分别为A1、A2的最大属性满矩阵。 3方法 说明：该性质的依据就是对象集越大，则其具有 设(U,M,)是一形式背景，显然，它可以看作表 ３ 形式背景 Ｋ３ Ｔａｂｌｅ ３ Ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｋ３ Ｕ ａ ｂ ｃ，ｇ ｄ ｅ ｕ１ １ ０ １ ０ ０ ｕ２ １ １ １ ０ １ ｕ３ ０ １ ０ ０ １ ｕ４ ０ ０ １ １ １ 这里把属性 ｆ 删除，将属性 ｃ 与 ｇ 合并成一个属 性也不会影响概念格的结构。 由于对具有相同内涵的对象和具有相同外延的 属性的各自合并所得的概念格与原概念格同构。 所 以在生成概念之前可以先把形式背景化为既约的， 这样就会使形式背景变得简单些。 ２ 满矩阵与概念 定义 ５ 设 （ Ｕ，Ｍ，Ｉ ）为一形式背景，在其对应 的形式背景矩阵中，取出对象集 Ａ ⊆ Ｕ 对应的任意 行和属性集 Ｂ ⊆ Ｍ 对应的任意列组成新的矩阵 Ｍ Ｂ Ａ ， 则称 Ｍ Ｂ Ａ 为形式背景矩阵的子矩阵。 若子矩阵 Ｍ Ｂ Ａ 的每个元素都为 １，则称子矩阵 Ｍ Ｂ Ａ 为满矩阵。 在满 矩 阵 Ｍ Ｂ Ａ 中， 规 定 矩 阵 Ｍ Ｂ Ａ 的 列 数 即 Ｂ 为矩阵的属性秩，记为 ｒ Ｍ Ｂ Ａ ( ) ＝ Ｂ ；矩阵 Ｍ Ｂ Ａ 的行数即 Ａ 为矩阵的对象秩，记为 ｌ Ｍ Ｂ Ａ ( ) ＝ Ａ ， 其中｜·｜表示集合中元素的个数。 定义 ６ 在形式背景矩阵中，对于对象集 Ａ ⊆ Ｕ， 如果属性集 Ｂ ⊆ Ｍ 有 ｒ Ｍ Ｙ Ａ ( ) ≤ ｒ Ｍ Ｂ Ａ ( ) ，∀Ｙ ⊆ Ｍ 成立，则称 Ｍ Ｂ Ａ 为对象集 Ａ 对应的最大属性满矩阵。 对偶地，可以定义最大对象满矩阵： 在形式背景矩阵中，对于属性集 Ｂ ⊆ Ｍ ，如果 对象集 Ａ ⊆ Ｕ 有 ｌ Ｍ Ｂ Ｘ ( ) ≤ ｌ Ｍ Ｂ Ａ ( ) ，∀Ｘ ⊆ Ｕ 成立，则称 Ｍ Ｂ Ａ 为属性集 Ｂ 对应的最大对象满矩阵。 说明：给定对象集，则其对应的最大属性满矩阵 是唯一的；给定属性集，则其对应的最大对象满矩阵 是唯一的。 性质 １ 设（ Ｕ，Ｍ，Ｉ ）为一形式背景，对任意的 对象集 Ａ１ ⊆ Ａ２ ⊆ Ｕ ，有 ｒ Ｍ Ｂ２ Ａ２ ( ) ≤ ｒ Ｍ Ｂ１ Ａ１ ( ) 成立， Ｍ Ｂ１ Ａ１ 、Ｍ Ｂ２ Ａ２ 分别为 Ａ１ 、Ａ２ 的最大属性满矩阵。 说明：该性质的依据就是对象集越大，则其具有 的共同属性不会多于其子集所具有的共同属性。 所 以对象集 Ａ２ 具有的共同属性应该小于或等于其子 集 Ａ１ 具有的共同的属性。 性质 ２ 设（ Ｕ，Ｍ，Ｉ ）为一形式背景，对任意的 属性集 Ｂ１ ⊆ Ｂ２ ⊆ Ｍ， 有 ｌ Ｍ Ｂ２ Ａ２ ( ) ≤ ｌ Ｍ Ｂ１ Ａ１ ( ) 成立， Ｍ Ｂ１ Ａ１ ，Ｍ Ｂ２ Ａ２ 分别为 Ｂ１ 、Ｂ２ 的最大对象满矩阵。 说明：该性质的依据就是具有的共同属性越多，则 其对象集的个数不会增多。 所以具有属性集 Ｂ２ 的对 象个数应该小于或等于具有属性集 Ｂ１ 的对象个数。 定义 ７ 若 (Ａ，Ｂ) 为形式概念，则称由对象集 Ａ 所在的行和属性集 Ｂ 所在的列组成的矩阵 Ｍ Ｂ Ａ 为 概念矩阵。 定理 １ 概念矩阵一定是最大属性满矩阵和最 大对象满矩阵。 证明：由定义 ５ ～ ７ 可直接得到结论。 反之，定 理 １ 不一定成立，即最大属性满矩阵，最大对象满矩 阵不一定是概念矩阵。 如在例 １ 中，对象 ｕ１ 与属性 ａｃｆｇ 组成的子矩阵为最大属性满矩阵，但由概念的 定义知 (ｕ１ ，ａｃｆｇ) 不是形式概念，又对象 ｕ１ ｕ２ 和属 性 ａ 组成的子矩阵为最大对象满矩阵，但由概念的 定义知 (ｕ１ ｕ２ ，ａ) 不是形式概念，即可得出定理 １ 的 逆不成立。 下面给出满矩阵是概念矩阵的一个充分条件： 定理 ２ 若满矩阵 Ｍ Ｂ Ａ ，既是对象集 Ａ 的最大 属性满矩阵，且是属性集 Ｂ 的最大对象满矩阵，则 满矩阵 Ｍ Ｂ Ａ 是概念矩阵。 证明 反证，假设满矩阵 Ｍ Ｂ Ａ 不是概念矩阵，说 明 (Ａ，Ｂ) 不是概念即 ｆ(Ａ) ≠ Ｂ 或 ｇ(Ｂ) ≠ Ａ 成立。 若 ｆ(Ａ) ≠ Ｂ ，则存在对象集 Ａ ′ ⊇ Ａ， 使 ｆ Ａ ′ ( ) ＝ Ｂ 成 立，也就是说属性集 Ｂ 有更大的对象满矩阵，与满 矩阵 Ｍ Ｂ Ａ 是属性集 Ｂ 的最大对象满矩阵矛盾；同理 可证， 若 ｇ(Ｂ) ≠ Ａ ， 则存在属性 集 Ｂ ′ ⊇ Ｂ， 使 ｇ Ｂ ′ ( ) ＝ Ａ 成立，也就是说对象集 Ａ 有更大的属性满 矩阵，与满矩阵 Ｍ Ｂ Ａ 是对象集 Ａ 的最大属性满矩阵 矛盾，即假设不成立，得证。 为了找出形式背景中所有的概念，根据定理 １， 可以先找出它的所有最大属性满矩阵或最大对象满 矩阵，进而根据定理 ２ 判断那些满矩阵为概念矩阵， 最后得到所有的概念。 ３ 方法 设 (Ｕ，Ｍ，Ｉ) 是一形式背景，显然，它可以看作 ·８４０· 智 能 系 统 学 报 第 １０ 卷