第4期 毛华，等：基于权值最大圈的概念格构造算法 ·521. ②若m'1cm'2且m',∩m'2≠0，则用“→”连接 之间再添加一条边e,(图中用虚线表示)，并且令 m,和m2表示为m2→m1; e1的权值也为o(u,v)。 ③若m',∩m'2=g,则m,和m2没有边连接。 完成1)~3)后得到的加权无向图称为弱化的 2)设(A(0,M,I),w)为(0，M,I)的属性拓扑 属性拓扑图，用(R(O,M,I),w)表示。 图，e(m,m)∈E(A(0,M,I),o)),E(A(0,M,I), 此外，显然，在上述3)中的e与e,是重边。 w)为(A(0,M,I),w)的边集，e(m:,m)上的权值用 例3下面图3为图2所对应的(A(O,M,I), (m,m)表示，心(m,m)为属性m:和m之间的公 心)之弱化的属性拓扑图。 共对象{g1,g2,…,gn}的集合，称w(m:,m）为m:和 m之间的权值。 24 4,6 3)设m∈M,b∈M,若与m连接的边均为非单 {1,2,4} 24} 2.45 向入边，即与m连接的边均为m→b或m←b,则称 2) {4 m为顶层属性，顶层属性的集合用T表示。 例2图2为表1形式背景(0，M,I)对应的属 多 4124 3 性拓扑图。 h 3,4 {2,4} 123 3 2.4号 {2,41 5 (2 {4 {13.5 4得 图3(R(O,M,I),w) {4 1,2 3 Fig3(R(O,M,I),w】 1,3 定义4设(0，M,I)是一个形式背景，(R(0, {3 M,),心)是(O,M,I)对应的弱化的属性拓扑图， 5 {m1,m2,…,m,}cM且{m1,m2,…,mw}'≠，若不存 f 在任意m。∈M,m.是{m1,m2,…,m.},使得{m1, 图2(A(0,M,I),w) m2,…,m}'={m1,m2,…,m4,m。}',则称Y={m1, Fig.2 (A(O,M,I),w) m2,…,ma}为权值w({m1,m2,…,m%})的最大圈。 引理1设(0，M,)是一个形式背景，(A(0, 例如图3中，Y={bdga}为权值{2}的最大圈。 M,I),w)为(O,M,I)的属性拓扑图，若m∈T,则 说明3为了描述方便，有时将w(m,m)简写 (m',m)∈β(0，M,I)。 为W。 2.2算法过程 2概念格的构造 对于给定的形式背景(O,M,I),构造概念格的 在搜索概念的过程中，为了不受方向的限制，首 过程如下： 先进行属性拓扑图弱化，将有向图变为无向图，实际 输入形式背景(O,M,I)以及W(R(O,M,I), 上目前结合图论生成概念格的算法，都是在无向图 0)={w1,02,…,0n},0,≠0，T,s,n=1,2,…, 的基础上进行的。其次，给出弱化后属性拓扑图关 MI 于某个权值的最大圈的定义。最后，给出利用权值 2o 的最大圈构造概念算法，并进行算法分析。 输出所有概念B(0,M,I)1{(0,0),(0,M)}。 2.1弱化的属性拓扑图 1)对于(O,M,I),绘制属性拓扑图，根据属性 设(O,M,)是一个形式背景，按照如下规则对 拓扑图中的箭头指向，确定顶层属性集合T。 属性拓扑图进行弱化： 2)将属性拓扑图转化为弱化的属性拓扑图。 1)去掉属性拓扑图中的方向，得一无向图。 3)①初始将W(R(O,M,I),0)赋值给W,对任 2)若m在(A(0,M,I),w)中为顶层属性，则在 1)中的无向图中，加一个以m为顶点的自环。 意两，求n,=1,2,1。者 3)若在1)中的无向图中，包含权值w(u,v)的 0,∩w,=⑦或0：∩w=0,此处w:,0,地，∈W(R(0, 只有一条边e,其中，u、u为e的两个端点，则在u与②若 ｍ′１Ìｍ′２且 ｍ′１∩ｍ′２¹Æ，则用“®” 连接 ｍ１和 ｍ２表示为 ｍ２®ｍ１ ； ③若 ｍ′１∩ｍ′２ ＝ Æ， 则 ｍ１和 ｍ２没有边连接。 ２） 设（Ａ（Ｏ，Ｍ，Ｉ），ｗ）为（Ｏ，Ｍ，Ｉ）的属性拓扑 图，ｅ（ｍｉ，ｍｊ）ÎＥ（ Ａ（Ｏ，Ｍ，Ｉ），ｗ）），Ｅ（ Ａ（Ｏ，Ｍ，Ｉ）， ｗ）为（Ａ（Ｏ，Ｍ，Ｉ），ｗ）的边集，ｅ（ｍｉ，ｍｊ）上的权值用 ｗ（ｍｉ，ｍｊ）表示，ｗ（ｍｉ，ｍｊ）为属性 ｍｉ和 ｍｊ之间的公 共对象｛ｇ１ ， ｇ２ ，…，ｇｎ ｝的集合，称 ｗ（ｍｉ，ｍｊ）为 ｍｉ和 ｍｊ之间的权值。 ３）设 ｍ ÎＭ，ｂ ÎＭ，若与 ｍ 连接的边均为非单 向入边，即与 ｍ 连接的边均为 ｍ ®ｂ 或 ｍ «ｂ，则称 ｍ 为顶层属性，顶层属性的集合用 Ｔ 表示。 例 ２ 图 ２ 为表 １ 形式背景（Ｏ，Ｍ，Ｉ）对应的属 性拓扑图。 图 ２ （Ａ（Ｏ，Ｍ，Ｉ），ｗ） Ｆｉｇ．２ （Ａ（Ｏ，Ｍ，Ｉ），ｗ） 引理 １ 设（Ｏ，Ｍ，Ｉ）是一个形式背景，（Ａ（Ｏ， Ｍ，Ｉ），ｗ） 为（Ｏ，Ｍ，Ｉ） 的属性拓扑图，若 ｍ ÎＴ，则 （ｍ′， ｍ）Îβ（Ｏ，Ｍ，Ｉ）。 ２ 概念格的构造 在搜索概念的过程中，为了不受方向的限制，首 先进行属性拓扑图弱化，将有向图变为无向图，实际 上目前结合图论生成概念格的算法，都是在无向图 的基础上进行的。 其次，给出弱化后属性拓扑图关 于某个权值的最大圈的定义。 最后，给出利用权值 的最大圈构造概念算法，并进行算法分析。 ２．１ 弱化的属性拓扑图 设（Ｏ，Ｍ，Ｉ）是一个形式背景，按照如下规则对 属性拓扑图进行弱化： １）去掉属性拓扑图中的方向，得一无向图。 ２）若 ｍ 在（Ａ（Ｏ，Ｍ，Ｉ），ｗ）中为顶层属性，则在 １）中的无向图中，加一个以 ｍ 为顶点的自环。 ３）若在 １）中的无向图中，包含权值 ｗ（ｕ，ｖ）的 只有一条边 ｅ，其中，ｕ、ｖ 为 ｅ 的两个端点，则在 ｕ 与 ｖ 之间再添加一条边 ｅ１（图中用虚线表示），并且令 ｅ１ 的权值也为 ｗ（ｕ，ｖ）。 完成 １） ～ ３）后得到的加权无向图称为弱化的 属性拓扑图，用（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）表示。 此外，显然，在上述 ３）中的 ｅ 与 ｅ１ 是重边。 例 ３ 下面图 ３ 为图 ２ 所对应的（Ａ（Ｏ，Ｍ，Ｉ）， ｗ）之弱化的属性拓扑图。 图 ３ （Ｒ（Ｏ，Ｍ，Ｉ），ｗ） Ｆｉｇ．３ （Ｒ（Ｏ，Ｍ，Ｉ），ｗ） 定义 ４ 设（Ｏ，Ｍ，Ｉ）是一个形式背景，（Ｒ（Ｏ， Ｍ，Ｉ），ｗ） 是（Ｏ，Ｍ，Ｉ） 对应的弱化的属性拓扑图， ｛ｍ１ ，ｍ２ ，…，ｍｈ ｝ÍＭ 且｛ｍ１ ，ｍ２ ，…，ｍｈ ｝¢¹Æ，若不存 在任意 ｍａ ÎＭ， ｍａ Ï｛ ｍ１ ，ｍ２ ，…，ｍｈ ｝， 使得｛ ｍ１ ， ｍ２ ，…，ｍｈ ｝¢＝ ｛ｍ１ ，ｍ２ ，…，ｍｈ ， ｍａ ｝ ¢，则称 Ｙ ＝ ｛ｍ１ ， ｍ２ ，…，ｍｈ ｝为权值 ｗ（｛ｍ１ ，ｍ２ ，…，ｍｈ ｝¢）的最大圈。 例如图 ３ 中，Ｙ ＝ ｛ｂｄｇａ｝为权值｛２｝的最大圈。 说明 ３ 为了描述方便，有时将 ｗ（ｍｉ，ｍｊ）简写 为 ｗ。 ２．２ 算法过程 对于给定的形式背景（Ｏ，Ｍ，Ｉ），构造概念格的 过程如下： 输入 形式背景（Ｏ，Ｍ，Ｉ）以及 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ）， ｗ） ＝ ｛ ｗ１ ， ｗ２ ， …， ｗｎ ｝， ｗｒ ¹ｗｓ， ｒ， ｓ， ｎ ＝ １， ２， …， Ｍ ２ ２ 。 输出 所有概念 β （Ｏ，Ｍ，Ｉ） ＼｛（Ｏ，Æ），（Æ，Ｍ）｝。 １）对于（Ｏ，Ｍ，Ｉ），绘制属性拓扑图，根据属性 拓扑图中的箭头指向，确定顶层属性集合 Ｔ。 ２）将属性拓扑图转化为弱化的属性拓扑图。 ３）①初始将 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）赋值给 Ｗｒ，对任 意 ｗｉ，ｗｊ ÎＷｒ，求 ｗｉ ∩ｗｊ， ｉ，ｊ ＝ １，２，…， Ｍ ２ ２ 。 若 ｗｉ∩ｗｊ ＝ Æ或 ｗｉ∩ｗｊ ＝ ｗｔ，此处 ｗｉ， ｗｊ， ｗｔÎＷ（Ｒ（Ｏ， 第 ４ 期 毛华，等：基于权值最大圈的概念格构造算法 ·５２１·