第6期 郭伦众，等：一种基于最大满矩阵生成概念格的算法 ·839- 法：刘宏英等基于对多维序列的理解，提出一种 (A1,B),H2=(A2,B2)是K的2个概念，在概念集 新的多维概念格并给出了渐进式构造算法。本文首 L(U,M,I)上定义关系： 先将形式背景看成一个0、1的关系矩阵，然后将形 H1≤H2曰A,CA,(或B2CB,) 式背景化为既约的[o],最后提出了一种基于最大满 在概念集L(U,M,)上定义交并运算分别为 矩阵来获取概念格的算法。 (A1,B1)A(A2,B2)=(A1∩A2f(g(B,UB2)))） 1基本概念 (A1,B1)V(42,B2)=(g(fA1UA2)),B1∩B2) 可以证明L(U,M,)对此运算构成完备格，称 下面给出形式背景的相关概念。 定义1【o)设U是对象集合，M是属性的集 L(U,M,I)为概念格。 合，1是2个集合U与M之间的关系，则称三元组 为了让形式背景尽可能的简单，下面给出净化 K=(U,M,)为一个形式背景（简称背景）。 背景的定义。 对于u∈U,m∈M,(u,m)∈I(或写作lm) 定义3o!如果任意满足f(u)=fh)的2个 表示对象u具有属性m。 元素u,h∈U都有u=h,且对任意满足g(m)= 定义2o设K=(U,M,I)是一个背景。对 g(n)的元素m,n∈M,都有m=n,则称背景 于ASU,BSM。令 (U,M,)是净化的。 fA)={m∈M|Hu∈A,lm} 例1把表1净化后，得到形式背景K2,如表2。 g(B)={u∈U|HmeB,m} 表2形式背景K 如果A、B满足f(A)=B,g(B)=A,则称二元组 Table 2 The formal context K, (A,B)是一个概念。A是概念(4，B)的外延，B是 U a b c,g d e f 概念(A,B)的内涵。 4:101001 用L(U,M,I)表示背景K=(U,M,I)上的所有 u2111011 概念集合。 u3010011 形式背景K,如表1所示，其中对象集U= {u1,2,3,u4},属性集M={a,b,c,d,e,f,g},1表 4001111 示所对应的对象和属性具有关系【，0表示所对应 为了方便，给具有某种特点的对象或属性一个 的对象和属性不具有关系1。 统一的名称。 表1形式背景K 定义4【o当mX,但g(m)=g(X),称m Table 1 The formal context K 为可约属性，称m产生的属性概念 a bc d e fg (g(m),f(g(m)))为A可约的属性概念。 41010011 对应地，当u生H,但f(u)=f(H)时，称u为可 421110111 约对象，称u产生的对象概念(g(f(u)),f(u))为 430100110 V可约的对象概念。 440011111 显然∧可约的属性与V可约的对象是可以删 实际上，该形式背景完全由矩阵 除的。如果所有对象都具有某个属性m,则称m为 「10100117 “满列属性”；对应地，如果有某个对象具有所有 1110111 属性，则称山为“满行对象”。由定义可得“满列属 0100110 性”与“满行对象”都是可约的。 0011111 如果一个净化背景的每个对象概念都是V不 刻画，称此矩阵为形式背景矩阵。 可约的，则称这个背景为行既约的。如果一个净化 可以验证这个背景的全部概念是： 背景的每个属性概念都是∧不可约的，则称这个背 （u14243山4，f)、（u142,acfg）、（u2u34,ef）、 景为列既约的。既是行既约的又是列既约的，则称 （42u4,cfg)、(u2u4,cefg）、（243,bef)、(42, 其是既约的。 abcefg）、(ua,edefg)、(Φ，abedefg)。 例2把表2化成既约的，得形式背景K3,如 设K=(U,M,)是一个形式背景，H1= 表3所示。法；刘宏英等［９］ 基于对多维序列的理解，提出一种 新的多维概念格并给出了渐进式构造算法。 本文首 先将形式背景看成一个 ０、１ 的关系矩阵，然后将形 式背景化为既约的［１０］ ，最后提出了一种基于最大满 矩阵来获取概念格的算法。 １ 基本概念 下面给出形式背景的相关概念。 定义 １ ［１０］ 设 Ｕ 是对象集合， Ｍ 是属性的集 合， Ｉ 是 ２ 个集合 Ｕ 与 Ｍ 之间的关系，则称三元组 Ｋ ＝（Ｕ，Ｍ，Ｉ） 为一个形式背景（简称背景）。 对于 ｕ ∈ Ｕ，ｍ ∈ Ｍ，（ｕ，ｍ） ∈ Ｉ （或写作 ｕＩｍ ） 表示对象 ｕ 具有属性 ｍ 。 定义 ２ ［１０］ 设 Ｋ ＝ （Ｕ，Ｍ，Ｉ） 是一个背景。 对 于 Ａ ⊆ Ｕ，Ｂ ⊆ Ｍ 。 令 ｆ(Ａ) ＝ {ｍ ∈ Ｍ ∀ｕ ∈ Ａ，ｕＩｍ} ｇ(Ｂ) ＝ {ｕ ∈ Ｕ ∀ｍ ∈ Ｂ，ｕＩｍ} 如果 Ａ、Ｂ 满足 ｆ(Ａ) ＝ Ｂ，ｇ(Ｂ) ＝ Ａ， 则称二元组 (Ａ，Ｂ) 是一个概念。 Ａ 是概念 (Ａ，Ｂ) 的外延， Ｂ 是 概念 (Ａ，Ｂ) 的内涵。 用 Ｌ(Ｕ，Ｍ，Ｉ) 表示背景 Ｋ ＝ （Ｕ，Ｍ，Ｉ） 上的所有 概念集合。 形式背景 Ｋ１ 如表 １ 所示， 其中对象集 Ｕ ＝ ｕ１ ，ｕ２ ，ｕ３ ，ｕ４ { } ，属性集 Ｍ ＝ {ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ} ，１ 表 示所对应的对象和属性具有关系 Ｉ ，０ 表示所对应 的对象和属性不具有关系 Ｉ 。 表 １ 形式背景 Ｋ１ Ｔａｂｌｅ １ Ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｋ１ Ｕ ａ ｂ ｃ ｄ ｅ ｆ ｇ ｕ１ １ ０ １ ０ ０ １ １ ｕ２ １ １ １ ０ １ １ １ ｕ３ ０ １ ０ ０ １ １ ０ ｕ４ ０ ０ １ １ １ １ １ 实际上，该形式背景完全由矩阵 １ ０ １ ０ ０ １ １ １ １ １ ０ １ １ １ ０ １ ０ ０ １ １ ０ ０ ０ １ １ １ １ １ é ë ê ê ê ê ê ù û ú ú ú ú ú 刻画，称此矩阵为形式背景矩阵。 可以验证这个背景的全部概念是： （ ｕ１ ｕ２ ｕ３ ｕ４ ， ｆ ）、（ ｕ１ ｕ２ ， ａｃｆｇ ）、（ ｕ２ ｕ３ ｕ４ ， ｅｆ ）、 （ ｕ１ ｕ２ ｕ４ ， ｃｆｇ ）、 （ ｕ２ ｕ４ ， ｃｅｆｇ ）、 （ ｕ２ ｕ３ ， ｂｅｆ ）、 （ ｕ２ ， ａｂｃｅｆｇ ）、（ ｕ４ ， ｃｄｅｆｇ ）、（Φ， ａｂｃｄｅｆｇ ）。 设 Ｋ ＝ （Ｕ，Ｍ，Ｉ） 是 一 个 形 式 背 景， Ｈ１ ＝ Ａ１ ，Ｂ１ ( ) ，Ｈ２ ＝ Ａ２ ，Ｂ２ ( ) 是 Ｋ 的 ２ 个概念，在概念集 Ｌ(Ｕ，Ｍ，Ｉ) 上定义关系： Ｈ１ ≤ Ｈ２⇔Ａ１ ⊆ Ａ２（或 Ｂ２ ⊆ Ｂ１ ） 在概念集 Ｌ(Ｕ，Ｍ，Ｉ) 上定义交并运算分别为 Ａ１ ，Ｂ１ ( ) ∧ Ａ２ ，Ｂ２ ( ) ＝ Ａ１ ∩ Ａ２ ，ｆ ｇ Ｂ１ ∪ Ｂ２ ( ( ( ) ) ) Ａ１ ，Ｂ１ ( ) ∨ Ａ２ ，Ｂ２ ( ) ＝ ｇ ｆ Ａ１ ∪ Ａ２ ( ( ) ) ，Ｂ１ ∩ Ｂ２ ( ) 可以证明 Ｌ(Ｕ，Ｍ，Ｉ) 对此运算构成完备格，称 Ｌ(Ｕ，Ｍ，Ｉ) 为概念格。 为了让形式背景尽可能的简单，下面给出净化 背景的定义。 定义 ３ ［１０］ 如果任意满足 ｆ(ｕ) ＝ ｆ(ｈ) 的 ２ 个 元素 ｕ，ｈ ∈ Ｕ 都有 ｕ ＝ ｈ ，且对任意满足 ｇ(ｍ) ＝ ｇ(ｎ) 的元素 ｍ，ｎ ∈ Ｍ， 都有 ｍ ＝ ｎ ， 则称背景 (Ｕ，Ｍ，Ｉ) 是净化的。 例 １ 把表 １ 净化后，得到形式背景 Ｋ２ ，如表 ２。 表 ２ 形式背景 Ｋ２ Ｔａｂｌｅ ２ Ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｋ２ Ｕ ａ ｂ ｃ，ｇ ｄ ｅ ｆ ｕ１ １ ０ １ ０ ０ １ ｕ２ １ １ １ ０ １ １ ｕ３ ０ １ ０ ０ １ １ ｕ４ ０ ０ １ １ １ １ 为了方便，给具有某种特点的对象或属性一个 统一的名称。 定义 ４ ［１０］ 当 ｍ ∉ Ｘ，但 ｇ(ｍ) ＝ ｇ(Ｘ) ， 称 ｍ 为 可 约 属 性， 称 ｍ 产 生 的 属 性 概 念 (ｇ(ｍ) ，ｆ(ｇ(ｍ) ) ) 为 ∧ 可约的属性概念。 对应地，当 ｕ ∉ Ｈ，但 ｆ(ｕ) ＝ ｆ(Ｈ) 时，称 ｕ 为可 约对象，称 ｕ 产生的对象概念 (ｇ(ｆ(ｕ) ) ，ｆ(ｕ) ) 为 ∨ 可约的对象概念。 显然 ∧ 可约的属性与 ∨ 可约的对象是可以删 除的。 如果所有对象都具有某个属性 ｍ ，则称 ｍ 为 “满列属性”；对应地，如果有某个对象 ｕ 具有所有 属性，则称 ｕ 为“满行对象”。 由定义可得“满列属 性”与“满行对象”都是可约的。 如果一个净化背景的每个对象概念都是 ∨ 不 可约的，则称这个背景为行既约的。 如果一个净化 背景的每个属性概念都是 ∧ 不可约的，则称这个背 景为列既约的。 既是行既约的又是列既约的，则称 其是既约的。 例 ２ 把表 ２ 化成既约的，得形式背景 Ｋ３ ， 如 表 ３ 所示。 第 ６ 期 郭伦众，等：一种基于最大满矩阵生成概念格的算法 ·８３９·