·334 智能系统学报 第12卷 个顶点构成的圈（即三角形）是最稳定的，因此本文 [L,D]是M在模2域上的一个标准矩阵表示，其中 考虑的圈将以三角形为基本单元。 p(b)是I中第i列，而p(e)是D中的第j列，1≤ 随着经济的发展，许多城市面临着严重的交通 i≤r,1≤j≤qo 拥堵。若出行者对自己要经过交通网络的路径、费 引理14 在一个具有n个顶点的无向完全图 用、时间等能够以清晰地、直观地方式得到，则完成 任务的效率将会大大提高。关于在复杂的交通网 中，包含的边数为(n-1) 络的条件下，研究合理的出行路径模型和算法，请 定义4)]形式背景K=(G,M,)定义为一个 参见文献[2-9]。基于多属性条件路径选择问题， 三元数组，其中G中的元素被称为对象，M中的元 文献[2-9]以及目前掌握的材料中，均没有涉及对 素被称为属性。IGxM,用glm表示(g,m)∈I,即 于交通网路信息提取的概念格[1]可视化研究。 对象g具有属性m。 概念格建立了对象和属性之间的一种概念层 定义5)形式背景(G,M,I)中的概念定义为 次结构，是数据分析和规则提取的一种有效工具。 元素对(A,B),其中A二G,BCM,A称为概念的外 Whitney!在1935年首次提出的拟阵已经被广泛 延，B称为概念的内涵，并且满足以下条件： 地应用于信息编码[]和网络安全[]等领域。将拟 1)B'={a∈GHb∈B,alb},A'={b∈M|Ha∈ 阵与概念格理论结合、图论[4]与概念格理论结合 来解决问题，已有许多成功的案例[6-2) A,alb 2)ACA",BCB"; 由于现实生活中，人们出行受多个属性条件的 限制，针对这些限制，经过研究发现K。简单图中形 3)(A)'=04,(9B,)'=0B'。 成三角形圈的一种特殊性质。由此，可以对复杂的 定义6设(A1,B,)、(A2,B2)是L(G,M,I) 交通网络进行分析、转化，形成K简单图。进而，能 中的两个概念，定义二元关系(A1,B,)≤(A2,B2)台 够建立网络模型，构建模型所对应的关联矩阵。依 ACA2台B,CB2,称(A1,B,)是(A2,B2)的子概念， 据K,图所产生的特殊形式背景，建立概念格信息提 (A2,B2)是(A1,B,)的父概念。若不存在概念(A3, 取方法。从而，给出基于二元拟阵K图的一种建格 B3)使得(A1,B1)≤(A3,B3)≤(A2,B2)成立，则称 方法，并利用具体实例验证方法的正确性与有效性。 (A1,B)是(A2,B2)的直接子概念，(A2,B2)是(A1, 1 预备知识 B,)的直接父概念。 不难证明这种父概念一子概念关系（也称泛 本节主要介绍网络K图、拟阵和概念格一些定 化-特化关系)是L(G,M,I)上的一个偏序关系。事 义与相关结论。有关图的基本概念和完全图的定 实上L(G,M,)关于该偏序关系是一个完备格，称 义，读者请参见文献[14]。有关二元拟阵和图的拟 为形式背景(G,M,I)的概念格，记为L(G,M,I)。 阵可表示性请参见文献[11]。 引理2]设(G,M,)是一个形式背景，则 定义1设任意（无向）图G=(V,E),其中 L(G,M,)关于上面定义的序“≤”构成的是完备 顶点集V={u1,2,…,vn},边集E={e1,e2,…,e.}。 格，其中上下确界由下式给出： 用m表示顶点：与边e,关联的次数，可能取值为 0,1,2,称所得矩阵M(G)=（m:)x.为图G的关联 V(4,B)=(A)”,0B) 矩阵。 Λje(4,B)=(∩A,(UB)") 定义24V(G)=XUY,X∩Y=⑦，X中任二 为了模型的建立和讨论表述简捷，给出如下几 项不相邻，Y中任二项不相邻，则G为二部图；若X 个定义。 中每个顶点皆与Y中一切顶点相邻，则G为完全二 定义7含圈基：在K图中满足从一个顶点出 部图，记Km,a,其中m=|x|,n=|Y|。 发，到其他n-1个顶点的相连接的边叫做含圈基。 定义3)设M是关于E={b1,b2,…,b,e1, 定义8基顶点：在K,图中满足从一个顶点出 e2,…,e,}的一个拟阵，其中B=b1,b2,…,b,}是M 发包含的所有相连的含圈基的顶点叫做基顶点。 的一个基。设C,是BU{e,}所含的基本圈，定义r× 定义9基最小圈：在一个三角形最小圈中，满 足一个最小圈中包含两个基的三角形圈，叫做基最 q阶矩阵D=(dg),其中d,= ,若b,∈C,则A= 0,其他 小圈。个顶点构成的圈（即三角形）是最稳定的，因此本文 考虑的圈将以三角形为基本单元。 随着经济的发展，许多城市面临着严重的交通 拥堵。 若出行者对自己要经过交通网络的路径、费 用、时间等能够以清晰地、直观地方式得到，则完成 任务的效率将会大大提高。 关于在复杂的交通网 络的条件下，研究合理的出行路径模型和算法，请 参见文献［２－９］。 基于多属性条件路径选择问题， 文献［２－９］以及目前掌握的材料中，均没有涉及对 于交通网路信息提取的概念格［１０］可视化研究。 概念格建立了对象和属性之间的一种概念层 次结构，是数据分析和规则提取的一种有效工具。 Ｗｈｉｔｎｅｙ ［１１］在 １９３５ 年首次提出的拟阵已经被广泛 地应用于信息编码［１２］ 和网络安全［１３］ 等领域。 将拟 阵与概念格理论结合、图论［１４－１５］与概念格理论结合 来解决问题，已有许多成功的案例［１６－２１］ 。 由于现实生活中，人们出行受多个属性条件的 限制，针对这些限制，经过研究发现 Ｋｎ 简单图中形 成三角形圈的一种特殊性质。 由此，可以对复杂的 交通网络进行分析、转化，形成 Ｋｎ 简单图。 进而，能 够建立网络模型，构建模型所对应的关联矩阵。 依 据 Ｋｎ 图所产生的特殊形式背景，建立概念格信息提 取方法。 从而，给出基于二元拟阵 Ｋｎ 图的一种建格 方法，并利用具体实例验证方法的正确性与有效性。 １ 预备知识 本节主要介绍网络 Ｋｎ 图、拟阵和概念格一些定 义与相关结论。 有关图的基本概念和完全图的定 义，读者请参见文献［１４］。 有关二元拟阵和图的拟 阵可表示性请参见文献［１１］。 定义 １ ［２２］ 设任意（无向）图 Ｇ ＝ （ Ｖ，Ｅ），其中 顶点集 Ｖ ＝ ｛ｖ１ ，ｖ２ ，…，ｖｎ ｝，边集 Ｅ ＝ ｛ ｅ１ ，ｅ２ ，…，ｅｅ ｝。 用 ｍｉｊ表示顶点 ｖｉ 与边 ｅｊ 关联的次数，可能取值为 ０，１，２，称所得矩阵 Ｍ（Ｇ） ＝ （ｍｉｊ ）ｎ×ｅ为图 Ｇ 的关联 矩阵。 定义 ２ ［１４］ Ｖ（Ｇ）＝ Ｘ∪Ｙ，Ｘ∩Ｙ ＝ ⌀，Ｘ 中任二 项不相邻，Ｙ 中任二项不相邻，则 Ｇ 为二部图；若 Ｘ 中每个顶点皆与 Ｙ 中一切顶点相邻，则 Ｇ 为完全二 部图，记 Ｋｍ，ｎ ，其中 ｍ ＝ Ｘ ，ｎ ＝ Ｙ 。 定义 ３ ［１１］ 设 Ｍ 是关于 Ｅ ＝ ｛ ｂ１ ，ｂ２ ，…，ｂｒ，ｅ１ ， ｅ２ ，…，ｅｑ｝的一个拟阵，其中 Ｂ ＝ ｛ｂ１ ，ｂ２ ，…，ｂｒ｝是 Ｍ 的一个基。 设 Ｃｊ 是 Ｂ∪｛ｅｊ｝所含的基本圈，定义 ｒ× ｑ 阶矩阵Ｄ ＝ （ ｄｉｊ ），其中 ｄｉｊ ＝ １， 若 ｂｉ∈Ｃｊ ０， 其他 { ，则Ａ＝ ［Ｉｒ Ｄ］是 Ｍ 在模 ２ 域上的一个标准矩阵表示，其中 φ（ｂｉ）是 Ｉｒ 中第 ｉ 列，而 φ（ｅｊ）是 Ｄ 中的第 ｊ 列，１≤ ｉ≤ｒ，１≤ｊ≤ｑ。 引理 １ ［１４］ 在一个具有 ｎ 个顶点的无向完全图 中，包含的边数为 ｎ（ｎ－１） ２ 。 定义 ４ ［１７］ 形式背景 Ｋ ＝ （Ｇ，Ｍ，Ｉ）定义为一个 三元数组，其中 Ｇ 中的元素被称为对象，Ｍ 中的元 素被称为属性。 Ｉ⊆Ｇ×Ｍ，用 ｇＩｍ 表示（ｇ，ｍ）∈Ｉ，即 对象 ｇ 具有属性 ｍ。 定义 ５ ［１７］ 形式背景（Ｇ，Ｍ，Ｉ）中的概念定义为 元素对（Ａ，Ｂ），其中 Ａ⊆Ｇ，Ｂ⊆Ｍ，Ａ 称为概念的外 延，Ｂ 称为概念的内涵，并且满足以下条件： １）Ｂ′＝ ｛ａ∈Ｇ ∀ｂ∈Ｂ，ａＩｂ｝，Ａ′ ＝ ｛ｂ∈Ｍ ∀ａ∈ Ａ，ａＩｂ｝； ２）Ａ⊆Ａ″，Ｂ⊆Ｂ″； ３）（∪ ｊ∈Ｊ Ａｊ）′＝∩ ｊ∈Ｊ Ａｊ ′，（∪ ｊ∈Ｊ Ｂｊ）′＝∩ ｊ∈Ｊ Ｂｊ ′。 定义 ６ ［１７］ 设（Ａ１ ，Ｂ１ ）、（Ａ２ ，Ｂ２ ）是 Ｌ（Ｇ，Ｍ，Ｉ） 中的两个概念，定义二元关系（Ａ１ ，Ｂ１ ）≤（Ａ２ ，Ｂ２ ）⇔ Ａ１⊆Ａ２⇔Ｂ１⊆Ｂ２ ，称（Ａ１ ，Ｂ１ ）是（ Ａ２ ，Ｂ２ ） 的子概念， （Ａ２ ，Ｂ２ ）是（Ａ１ ，Ｂ１ ）的父概念。 若不存在概念（ Ａ３ ， Ｂ３ ）使得（Ａ１ ，Ｂ１ ） ≤（Ａ３ ，Ｂ３ ） ≤（Ａ２ ，Ｂ２ ） 成立，则称 （Ａ１ ，Ｂ１ ）是（Ａ２ ，Ｂ２ ）的直接子概念，（Ａ２ ，Ｂ２ ）是（Ａ１ ， Ｂ１ ）的直接父概念。 不难证明这种父概念 － 子概念关系（ 也称泛 化－特化关系）是 Ｌ（Ｇ，Ｍ，Ｉ）上的一个偏序关系。 事 实上 Ｌ（Ｇ，Ｍ，Ｉ）关于该偏序关系是一个完备格，称 为形式背景（Ｇ，Ｍ，Ｉ）的概念格，记为 Ｌ（Ｇ，Ｍ，Ｉ）。 引理 ２ ［１７］ 设（ Ｇ，Ｍ，Ｉ） 是一个形式背景，则 Ｌ（Ｇ，Ｍ，Ｉ）关于上面定义的序“ ≤” 构成的是完备 格，其中上下确界由下式给出： ∨ｊ∈Ｊ（Ａｊ，Ｂｊ） ＝ （∪ ｊ∈Ｊ Ａｊ ( ) ″， ∩ ｊ∈Ｊ Ｂｊ） ∧ｊ∈Ｊ（Ａｊ，Ｂｊ） ＝ （∩ ｊ∈Ｊ Ａｊ，（∪ ｊ∈Ｊ Ｂｊ）″） 为了模型的建立和讨论表述简捷，给出如下几 个定义。 定义 ７ 含圈基：在 Ｋｎ 图中满足从一个顶点出 发，到其他 ｎ－１ 个顶点的相连接的边叫做含圈基。 定义 ８ 基顶点：在 Ｋｎ 图中满足从一个顶点出 发包含的所有相连的含圈基的顶点叫做基顶点。 定义 ９ 基最小圈：在一个三角形最小圈中，满 足一个最小圈中包含两个基的三角形圈，叫做基最 小圈。 ·３３４· 智 能 系 统 学 报 第 １２ 卷