第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201703026 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180423.1019.008.html 利用二部图生成概念格 窦林立，展正然 (中国地质大学长城学院基础课教学部，河北保定071002) 摘要：概念格作为一种有效的知识发现与数据处理的工具，在许多领域得到了广泛应用，概念格的构造在其 应用中具有重要的意义。每个概念格的形式背景都可以对应一个二部图，本文通过二部图的极大完全子图的 概念来生成概念格，给出了基于二部图的深度优先的概念格的迭代算法。首先，对形式背景进行必要的约简： 其次，利用二部图的极大完全子图得到顶层概念的直接子概念：最后，通过求二部图的导出子图来简化形式背 景.并得出每个概念的直接子概念和所有子概念，从而生成概念格。 关键词：形式背景；概念格；二部图；极大完全子图：直接子概念；Hasse示图；图论：导出子图 中图分类号：TP18 文献标志码：A 文章编号：1673-4785(2018)05-0687-06 中文引用格式：窦林立，展正然.利用二部图生成概念格.智能系统学报，2018,13(5)：687-692. 英文引用格式：DOU Linli,ZHAN Zhengran.Constructing concept lattice using bipartite graph Jl.CAAI transactions on intelli-- gent systems,2018,13(5:687-692. Constructing concept lattice using bipartite graph DOU Linli,ZHAN Zhengran (Basic Teaching Department,The Great Wall College,China University of Geosciences,Baoding 071002,China) Abstract:As an effective tool for knowledge discovery and data processing,concept lattices have been widely applied in many fields,and in these applications,it is important to efficiently construct concept lattice.The formal context of each concept lattice corresponds to a bipartite graph.In this paper,the maximum complete subgraph of a bipartite graph is used to generate a concept lattice,and then where an iterative algorithm with depth priority is proposed based on a bi- partite graph.The process is as follows:first,a formal context is reduced;then,the direct subconcepts of the top concept are obtained using maximal complete-subgraph of bipartite graph;finally,through the derivation of the induced sub- graph of bipartite graph to reduce the formal context,and find direct subconcepts and all subconcepts of every concept, then the concept lattice was established. Keywords:formal context;concept lattice;bipartite graph;maximum complete subgraph;direct subconcept,Hasse dia- gram;graph theory;induced subgraph 形式概念分析又称概念格，是由德国Wile 的属性约简的方法；Elloumi等基于模糊形式背 教授在20世纪80年代首次提出的，它提供了一 景建立了一个多层次的约简理论。 种支持数据分析和知识处理的数学工具B。近 近几年许多学者从图论方面对概念格进行研 些年来，国内外各位学者提出了许多的构造算 究。例如：Amilhastre等9与Bery等o-将二部图 法。例如：Godin等提出了概念格的渐进生成算 与概念格进行了交叉研究；李立峰等3利用弦 法；Ho提出了基于概念格的概念聚类算法；张文 二部图和链图对概念格进行表示；张涛等5) 修等给出了在保持格同构的条件下建立概念格 利用属性树和属性拓扑图来表示形式背景，简化 收稿日期：2017-03-21.网络出版日期：2018-04-24 了形式背景的表示结构，并提出了基于树图的属 基金项目：河北省高校科研基金项目（亿2015137） 通信作者：窦林立.E-mail:1321407258@qq.com. 性约简算法。本文通过二部图的极大完全子图的
DOI: 10.11992/tis.201703026 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180423.1019.008.html 利用二部图生成概念格 窦林立，展正然 （中国地质大学长城学院 基础课教学部，河北 保定 071002） 摘 要：概念格作为一种有效的知识发现与数据处理的工具，在许多领域得到了广泛应用，概念格的构造在其 应用中具有重要的意义。每个概念格的形式背景都可以对应一个二部图，本文通过二部图的极大完全子图的 概念来生成概念格，给出了基于二部图的深度优先的概念格的迭代算法。首先，对形式背景进行必要的约简； 其次，利用二部图的极大完全子图得到顶层概念的直接子概念；最后，通过求二部图的导出子图来简化形式背 景，并得出每个概念的直接子概念和所有子概念，从而生成概念格。 关键词：形式背景；概念格；二部图；极大完全子图；直接子概念；Hasse 示图；图论；导出子图 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2018)05−0687−06 中文引用格式：窦林立, 展正然. 利用二部图生成概念格[J]. 智能系统学报, 2018, 13(5): 687–692. 英文引用格式：DOU Linli, ZHAN Zhengran. Constructing concept lattice using bipartite graph[J]. CAAI transactions on intelligent systems, 2018, 13(5): 687–692. Constructing concept lattice using bipartite graph DOU Linli，ZHAN Zhengran (Basic Teaching Department, The Great Wall College, China University of Geosciences, Baoding 071002, China) Abstract: As an effective tool for knowledge discovery and data processing, concept lattices have been widely applied in many fields, and in these applications, it is important to efficiently construct concept lattice. The formal context of each concept lattice corresponds to a bipartite graph. In this paper, the maximum complete subgraph of a bipartite graph is used to generate a concept lattice, and then where an iterative algorithm with depth priority is proposed based on a bipartite graph. The process is as follows: first, a formal context is reduced; then, the direct subconcepts of the top concept are obtained using maximal complete-subgraph of bipartite graph; finally, through the derivation of the induced subgraph of bipartite graph to reduce the formal context, and find direct subconcepts and all subconcepts of every concept, then the concept lattice was established. Keywords: formal context; concept lattice; bipartite graph; maximum complete subgraph; direct subconcept; Hasse diagram; graph theory; induced subgraph 形式概念分析又称概念格[1-2] ，是由德国 Wille 教授在 20 世纪 80 年代首次提出的，它提供了一 种支持数据分析和知识处理的数学工具[3-4]。近 些年来，国内外各位学者提出了许多的构造算 法。例如：Godin 等 [5]提出了概念格的渐进生成算 法；Ho[6]提出了基于概念格的概念聚类算法；张文 修等[7]给出了在保持格同构的条件下建立概念格 的属性约简的方法；Elloumi 等 [8]基于模糊形式背 景建立了一个多层次的约简理论。 近几年许多学者从图论方面对概念格进行研 究。例如：Amilhastre 等 [9]与 Berry 等 [10-12]将二部图 与概念格进行了交叉研究；李立峰等[13-14]利用弦 二部图和链图对概念格进行表示；张涛等[ 1 5 - 1 7 ] 利用属性树和属性拓扑图来表示形式背景，简化 了形式背景的表示结构，并提出了基于树图的属 性约简算法。本文通过二部图的极大完全子图的 收稿日期：2017−03−21. 网络出版日期：2018−04−24. 基金项目：河北省高校科研基金项目 (Z2015137). 通信作者：窦林立. E-mail：1321407258@qq.com. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
·688· 智能系统学报 第13卷 概念来生成概念格，给出了基于二部图的深度优 0={1,2,3,4,5,6,7,M={a,b,c,d,e,f,g,表2为约简 先的概念格的迭代算法。 后的形式背景。其中属性的个数由7个约简成 5个。 1基本概念 表1形式背景(O,M,D 本节主要介绍概念格与二部图的基本知识。 Table 1 Formal context (O,M,/ 关于概念格的更多内容参见文献[1,18]，有关图论 对象 0 的详细内容参见文献[19-20]。 1.1概念格 2 定义11)在形式概念分析中，一个形式背 3 景是一个三元数组K=(O,M,),其中O是对象集 4 合，M是属性集合，I是O与M之间的一个二元 5 关系。用olm表示“对象o有属性m”。对于A二O及 B≤M,定义：A'={m∈MVo∈A,olm},B={o∈OI m∈B,olml。则形式背景K=(O,M,)的概念定义 为元素对(A,B),其中ASO,BSM,A'=B,B=A。 表2约简后的形式背景(O,M,) 概念(A,B)的外延是A,内涵是B。 Table 2 Reduced formal context(O.M.D 2)在形式背景K=(O,M,D的概念集合间建立 对象 d 一种偏序关系：给定两个概念C1=(A1,B)和 C2=(A2,B2),则C1 则C,与C之间就存在一条边。此时C称为C,的直 1.2图论 接子概念，C2称为C的直接父概念。 定义31)设V,和V2是图G的顶点子集，使 形式背景K=(O,M,D中集合O和M中所含元 V1UV2=V(G),V1nV2=Φ且G的每一条边都是一个 素的个数直接影响到生成概念格的复杂程度，所 端点在V,中另一个端点在V中，则称G为二部图， 以我们有必要对形式背景进行约简。 记作G=(V,V2:E)。如果V中的顶点与V中的每一 定义21)在形式背景K=(O,M,D中，若存在 个顶点都相邻，则称为完全二部图。 meM,对任意的o∈O,都有olm成立，即属性m与 2)设V是图G的任一顶点子集，G中与V的 对象集中每个对象都满足关系【，则可以从形式 顶点邻接的所有顶点的集合称为V的邻集，记作 背景中去掉这个属性m,所得概念格L(K)与原形 N(Vo)。 式背景所生成的概念格(K同构。要得到L(K), 3)设v∈V(G),G中与顶点v关联的边的数目 只需在L(K)的每个概念的内涵中都添加属性m即可。 称为（在G中）的度。 2)若i,j∈M,且i≠，P={oE Ololi,Q={oE Ololj, 4)G与S是两个图，且V(S)sV(G),E(S)SE(G), 若P=Q,则可以将两个属性和j缩写成一个属性 则S是G的子图，记作SsG。设V是G=(V,E)的顶 。显然，缩写后的形式背景与原形式背景生成 点集的一个非空子集，以V作为顶点集，以两个端 的概念格相同。 点均在V中的边的全体为边的子图称为由V导出 通过上述两种方法约简形式背景后，就可以 的G的子图，记为G[V],则G[V]是G的导出子图。 有效地减少形式背景中属性集合中的元素个数， 由概念格和二部图的定义可知，每个形式背 从而降低生成概念格的难度，更迅速地生成概 景都对应一个二部图，其中二部图的顶点集为 念格。 OUM,顶点o∈O与meM之间有一条边当且仅当 例1表1给出了形式背景K=(O,M,),其中 o与m满足关系I
概念来生成概念格，给出了基于二部图的深度优 先的概念格的迭代算法。 1 基本概念 本节主要介绍概念格与二部图的基本知识。 关于概念格的更多内容参见文献[1,18]，有关图论 的详细内容参见文献[19-20]。 1.1 概念格 K = (O, M,I) oIm o m A ⊆ O B ⊆ M A ′ = {m ∈ M|∀o ∈ A,oIm} B ′ = {o ∈ O| ∀m ∈ B,oIm} K = (O, M,I) (A,B) A ⊆ O B ⊆ M A ′ = B B ′ = A (A,B) 定义 1 1) 在形式概念分析中，一个形式背 景是一个三元数组 ，其中 O 是对象集 合，M 是属性集合，I 是 O 与 M 之间的一个二元 关系。用 表示“对象 有属性 ”。对于 及 ，定义： ， 。则形式背景 的概念定义 为元素对 ，其中 ， ， ， 。 概念 的外延是 A，内涵是 B。 K = (O, M,I) C1 = (A1,B1) C2 = (A2,B2) C1 < C2 ⇔ A1 ⊂ A2 B1 ⊃ B2 C1 C2 C2 C1 K = (O, M,I) K = (O, M,I) L(K) L(K) L(K) C1 C2 C1 < C2 C3 C1 < C3 < C2 C1 C2 C1 C2 C2 C1 2) 在形式背景 的概念集合间建立 一种偏序关系：给定两个概念 和 ， 则 (或 ) ，那么 是 的子概念， 是 的父概念。根据这种偏序 关系，形式背景 的概念节点的集合产 生一种格结构，称它为 的概念格，记为 。并且由这种偏序关系可生成 的 Hasse 图：对于 中的两个不同的节点 和 ，如果 ，并且不存在其他的节点 ，使得 ， 则 与 之间就存在一条边。此时 称为 的直 接子概念， 称为 的直接父概念。 形式背景 K = (O, M,I) 中集合 O 和 M 中所含元 素的个数直接影响到生成概念格的复杂程度，所 以我们有必要对形式背景进行约简。 K = (O, M,I) m ∈ M o ∈ O oIm m m L(K ∗ ) L(K) L(K) L(K ∗ ) m 定义 2 1) 在形式背景 中，若存在 ，对任意的 ，都有 成立，即属性 与 对象集中每个对象都满足关系 I，则可以从形式 背景中去掉这个属性 ，所得概念格 与原形 式背景所生成的概念格 同构。要得到 ， 只需在 的每个概念的内涵中都添加属性 即可。 i, j ∈ M, i , j P = {o ∈ O|oIi} Q = {o ∈ O|oI j} P = Q i j i j 2) 若 且 ， ， ， 若 ，则可以将两个属性 和 缩写成一个属性 。显然，缩写后的形式背景与原形式背景生成 的概念格相同。 通过上述两种方法约简形式背景后，就可以 有效地减少形式背景中属性集合中的元素个数， 从而降低生成概念格的难度，更迅速地生成概 念格。 例 1 表 1 给出了形式背景 K = (O, M,I) ，其中 O = {1,2,3,4,5,6,7}，M = {a,b, c,d, e, f,g}，表 2 为约简 后的形式背景。其中属性的个数由 7 个约简成 5 个。 表 1 形式背景 (O, M,I) Table 1 Formal context (O, M,I) 对象 a b c d e f g 1 × × × × × 2 × × × × 3 × × × × 4 × × × 5 × × × × × 6 × × × × 7 × × 表 2 约简后的形式背景 (O, M,I) Table 2 Reduced formal context (O, M,I) 对象 a b c df e 1 × × × × 2 × × 3 × × 4 × × 5 × × × 6 × × × 7 × 1.2 图论 V1 V2 G V1 ∪V2 = V (G),V1 ∩V2 = ϕ G V1 V2 G G = (V1,V2;E) V1 V2 定义 3 1) 设 和 是图 的顶点子集，使 且 的每一条边都是一个 端点在 中另一个端点在 中，则称 为二部图， 记作 。如果 中的顶点与 中的每一 个顶点都相邻，则称为完全二部图。 V0 V0 V0 N (V0) 2) 设 是图 G 的任一顶点子集，G 中与 的 顶点邻接的所有顶点的集合称为 的邻集，记作 。 3) 设 v ∈ V (G)，G 中与顶点 v 关联的边的数目 称为 v(在 G 中) 的度。 V (S ) ⊆ V (G),E (S ) ⊆ E (G) S G S ⊆ G V ∗ G = (V,E) V ∗ V ∗ V ∗ G G[V ∗ ] G[V ∗ ] G 4) G 与 S 是两个图，且 ， 则 是 的子图，记作 。设 是 的顶 点集的一个非空子集，以 作为顶点集，以两个端 点均在 中的边的全体为边的子图称为由 导出 的 的子图，记为 ，则 是 的导出子图。 O∪ M o ∈ O m ∈ M o m 由概念格和二部图的定义可知，每个形式背 景都对应一个二部图，其中二部图的顶点集为 ，顶点 与 之间有一条边当且仅当 与 满足关系 I。 ·688· 智 能 系 统 学 报 第 13 卷
第5期 窦林立，等：利用二部图生成概念格 ·689· 下面用具体实例来说明以上定义。 下面给出二部图的极大完全子图与概念的对 例2图1是例1中约简后的形式背景表2 应关系。 对应的二部图，图2是表2对应的概念格，原形式 定理1S=(A,B:E)(其中ASO,BSM)是二部 背景表1对应的概念格即为图3。 图G=(O,M:E)的极大完全子图的充要条件为 6 (A,B)是概念。 证明由概念格的定义知充分性显然成立。 下证必要性，用反证法。假设(A,B)不是概念， 则有A'≠B或B≠A。如果A'≠B,因为S=(A,B:E) 是完全二部图，所以B中的顶点与A中的每个顶 点都相邻，故至少存在一个顶点m∈M,有m与 图1表2对应的二部图 A中的每个顶点都相邻，即A'=BUm。这样可以 Fig.1 Bipartite graph for table 2 得到S1=(A,BUm:E)为完全二部图，与S是二部 (1234567,) 图G的极大完全子图矛盾，故A=B。同理可证 (13456,b) (235,d) (127,e B=A。因此，(A,B)是概念。 下面的定理2和定理3就是利用二部图的极 (1456,bc) (35,bd) 大完全子图得到顶层概念(O,)的直接子概念。 (16,abc) (5,bcdf) (2,def) 定理2形式背景K=(O,M,D对应的二部图 为G=(O,M:E),i为图G的顶点集M中度数最大的 (1,abce) 顶点，N)=P,则i与P构成的G的导出子图 (o,abcdef) G[PU是G的极大完全子图，即(P)为概念，且 图2表2对应的概念格 (P,)为顶层概念(O,)的直接子概念。 Fig.2 Concept lattice for table 2 证明用反证法。假设G[PU不是G的极大 (1234567,g) 完全子图，即存在o∈O-P,有S1=(PUo,iE)为完 全二部图，或存在m∈M,有S2=(P,iUm:E2)为完全 (13456,bg) (235,d) (127,eg) 二部图。若有第一种情况，则顶点i与PUo相邻， (1456,bcg) (35,bdg） 此与N()=P矛盾。若有第二种情况，由完全二部 图的定义知Um与P中每个顶点都相邻，如果 (16,abcg) (5,bcdfg) (2,defg) m的邻集恰好为P,则i与m应约简为im,与i和 (1,abceg) m是两个顶点矛盾；如果m的邻集包含P,即至少 存在o1∈O,使m与PUo相邻，则m的度数大于i的 (o,abcdefg) 度数，此与为M中度数最大的顶点矛盾。因此，GPU门 图3表1对应的概念格 是G的极大完全子图，即(P,)为概念。且其为顶 Fig.3 Concept lattice for table 1 层概念(O,)的直接子概念，因为不存在概念C,使 2利用二部图生成概念格 (P,)<C<(O,)o 定理3若j是形式背景K=(O,M,D对应的二 形式背景中的数据，在很多情况下，对象的个 部图G=(O,M:E)的顶，点集M中除外度数最大的顶 数较大，而属性的个数则相对较少，在这种情况 点，N)=P。若PtP,则(P,)为顶层概念(O,) 下，基于属性来生成概念格，可以有效地减少算 的直接子概念；若PcP,则以P为外延的概念应 法的执行时间。本文基于属性，利用二部图子图 为(P)的子概念。 和邻集的知识来生成概念格。 证明同定理2。 本节中的形式背景是指约简后的形式背景， 由定理2和定理3可以得到顶层概念(O,) 二部图也指约简后的形式背景所对应的二部图。 的直接子概念。 首先给出二部图的极大完全子图的定义。 以下的定理4给出了利用二部图的子图来求 定义4若S是二部图G的子图，且S是完全二 (O,)的直接子概念(P,的直接子概念及其所有子 部图，对任意的v∈V(G)-V(S),G由V(S)Uv导出的 概念的依据。 子图GV(S)Uv不是完全二部图，则S称为二部图 定理4形式背景K=(O,M,)对应的二部图 G的极大完全子图。 为G=(O,M:E),i是图G的属性集M中度数最大的
下面用具体实例来说明以上定义。 例 2 图 1 是例 1 中约简后的形式背景表 2 对应的二部图，图 2 是表 2 对应的概念格，原形式 背景表 1 对应的概念格即为图 3。 1 2 3 4 5 6 7 a b c df e 图 1 表 2 对应的二部图 Fig. 1 Bipartite graph for table 2 (1234567, f) (13456, b) (235, df ) (127, e) (1456, bc) (35,bdf ) (2, def ) (16, abc) (5, bcdf ) (1, abce) (f, abcdef ) 图 2 表 2 对应的概念格 Fig. 2 Concept lattice for table 2 (1234567, g) (13456, bg) (235, dfg) (127, eg) (1456, bcg) (35, bdfg) (16, abcg) (5, bcdfg) (2, defg) (1, abceg) (f, abcdefg ) 图 3 表 1 对应的概念格 Fig. 3 Concept lattice for table 1 2 利用二部图生成概念格 形式背景中的数据，在很多情况下，对象的个 数较大，而属性的个数则相对较少，在这种情况 下，基于属性来生成概念格，可以有效地减少算 法的执行时间。本文基于属性，利用二部图子图 和邻集的知识来生成概念格。 本节中的形式背景是指约简后的形式背景， 二部图也指约简后的形式背景所对应的二部图。 首先给出二部图的极大完全子图的定义。 S G S v ∈ V (G)−V (S ) G V (S )∪v G[V (S )∪v] S G 定义 4 若 是二部图 的子图，且 是完全二 部图，对任意的 ， 由 导出的 子图 不是完全二部图，则 称为二部图 的极大完全子图。 下面给出二部图的极大完全子图与概念的对 应关系。 S = (A,B;E) A ⊆ O,B ⊆ M G = (O, M;E) (A,B) 定理 1 (其中 ) 是二部 图 的极大完全子图的充要条件为 是概念。 证明 由概念格的定义知充分性显然成立。 (A,B) A ′ , B B ′ , A A ′ , B S = (A,B;E) m ∈ M A ′ = B∪m S 1 = (A,B∪m;E ∗ ) A ′ = B B ′ = A (A,B) 下证必要性，用反证法。假设 不是概念， 则有 或 。如果 ，因为 是完全二部图，所以 B 中的顶点与 A 中的每个顶 点都相邻，故至少存在一个顶点 ，有 m 与 A 中的每个顶点都相邻，即 。这样可以 得到 为完全二部图，与 S 是二部 图 G 的极大完全子图矛盾，故 。同理可证 。因此， 是概念。 (O, ϕ) 下面的定理 2 和定理 3 就是利用二部图的极 大完全子图得到顶层概念 的直接子概念。 K = (O, M,I) G = (O, M;E) i G M N (i) = P i P G G[P∪i] G (P,i) (P,i) (O, ϕ) 定理 2 形式背景 对应的二部图 为 ， 为图 的顶点集 中度数最大的 顶点， ， 则 与 构成的 的导出子图 是 的极大完全子图，即 为概念，且 为顶层概念 的直接子概念。 G[P∪i] G o ∈ O− P S 1 = (P∪o,i;E1) m ∈ M S 2 = (P,i∪m;E2) i P∪o N (i) = P i∪m o1 ∈ O m P∪o1 m i i M G[P∪i] (P,i) (O, ϕ) C (P,i) < C < (O, ϕ) 证明 用反证法。假设 不是 的极大 完全子图，即存在 ，有 为完 全二部图，或存在 ，有 为完全 二部图。若有第一种情况，则顶点 与 相邻， 此与 矛盾。若有第二种情况，由完全二部 图的定义知 与 P 中每个顶点都相邻，如果 m 的邻集恰好为 P，则 i 与 m 应约简为 im，与 i 和 m 是两个顶点矛盾；如果 m 的邻集包含 P，即至少 存在 ，使 与 相邻，则 的度数大于 的 度数，此与为 中度数最大的顶点矛盾。因此， 是 G 的极大完全子图，即 为概念。且其为顶 层概念 的直接子概念，因为不存在概念 ，使 。 j K = (O, M,I) G = (O,M;E) M i N (j) = P ∗ P ∗ 1 P (P ∗ , j) (O, ϕ) P ∗ ⊂ P P ∗ (P,i) 定理 3 若 是形式背景 对应的二 部图 的顶点集 中除 外度数最大的顶 点， 。若 ，则 为顶层概念 的直接子概念；若 ，则以 为外延的概念应 为 的子概念。 证明同定理 2。 由定理 2 和定理 3 可以得到顶层概念 (O, ϕ) 的直接子概念。 (O, ϕ) (P,i) 以下的定理 4 给出了利用二部图的子图来求 的直接子概念 的直接子概念及其所有子 概念的依据。 K = (O, M,I) G = (O,M;E) i G M 定理 4 形式背景 对应的二部图 为 ， 是图 的属性集 中度数最大的 第 5 期 窦林立，等：利用二部图生成概念格 ·689·
·690· 智能系统学报 第13卷 顶点，N()=P,则(P,)为形式背景K的概念。G的 为形式背景K的倒数第二层概念，它由导出子图 导出子图记为S=GPU(M-小，与二部图S相对应 ,生成，其直接子概念为最底层概念（Φ，M0,标号 的形式背景约简后记为K=(P,(M-),),若j是 为1+2)1，最底层概念(，M0的标号为1+3。 S的顶点集M-i中度数最大的顶点，N()=Q,则 5)从标号为1的概念回到生成它的导出子图 (Q,)为形式背景的概念，(Q,iU》为形式背景 S-2,考察二部图S-2的属性集中未考虑过的度数 K的概念，且(Q,iU)是(P,)的直接子概念。 最大的顶点i,-2'。如果N(i-2)=P-2‘是已生成的概 证明(P,)为形式背景K的概念，(Q,)为形式 念的外延，且当此已生成概念的内涵包含UU 背景K的概念，前文已证。下证(Q,iU)为形式背 i2Ui,-2时，说明以P,-2'为外延的概念及其子概 景K的概念，即需证G[Q,iU为二部图G的极大完 念已生成，则不必再考虑此顶点；而当此已生成 全子图。 概念的内涵等于iUnUi2Ui-2'时，则(P,-2∴，i-2) 用反证法。假设G[Q,iU不是二部图G的极 是(P,-1,i-)的直接子概念，且此概念及其子概念 大完全子图，那么可能有下列两种情况：1)至少 已生成（已标号），此顶点也不必再往下考虑。如 存在o∈P-Q,使G[QUo,iU为完全二部图；2)至 果P2'不是已生成概念的外延，则(P-2',i-2)是 少存在meM-i-j,使G[2,iujUm为完全二部 (P-,i-)的直接子概念，标号为(r-1)2,然后按步 图。如果出现第一种情况，由完全二部图的定义 骤3)和步骤4)的方法画出S,2的导出子图S,-‘= 知在图S中顶点j与QUo中的每个顶点相邻，此与 S-2[P-1U(W(P,-)-i,-小，接着再取未考虑过的 在形式背景K中N()=Q矛盾。如果出现第二种 最大度数顶点生成概念，直到倒数第二层概念。 情况，由完全二部图定义知在图S中m与集Q中 6)从标号为1+2)1的概念起，重复5)，便可得 的每个顶点相邻，那么m在S中的邻集必包含 到所有概念以及它们之间的父子关系。 j在S中的邻集，这与形式背景已约简且j是S的顶 点集M-中度数最大的顶点相矛盾。所以(Q,U) 3实例 为形式背景K的概念，并且不能找到集合B,使 下面通过例3来具体说明此方法如何产生慨 {i)cBc{iU,因此(Q,iU)是(P)的直接子概念。 念格。 根据定理4可以通过求G的导出子图的概念 例3形式背景同例1，其中的对象0={1,2,3,4， 来简化形式背景，并求出(P,)的直接子概念。这 5,6,7表示1班至7班共7个班级，属性M={a,b,c,d, 样经过反复的分解和约简，使形式背景越来越简 e,f,g表示班级特色，其中a表示团结，b表示纪律 化，同时也能求出(P,)的所有子概念。 严明，c表示学风端正，d表示卫生环境好，e表示 因此便能生成顶层概念的所有直接子概念以 干部队伍过硬，∫表示英语四六级通过率高，g表 及它们各自的子概念。这便是基于二部图的深度 示课余活动丰富。 优先的概念格的迭代算法。 下面用基于二部图的深度优先的概念格的迭 基于二部图的深度优先的概念格的迭代算法： 代算法来生成概念格。 1)最顶层概念为(O,),标号为1。 1)最顶层概念为(1234567，)，标号为1。 2)形式背景K=(O,M,D(约简后)，其对应的二 2)画出形式背景（约简后）所对应的二部图 部图为G=(O,M:E),取属性M中度数最大的顶点 G,其属性中度数最大的顶点为b,N(b)={1,3,4,5, i,N()=P,则(P,)为顶层概念(O,)的直接子概念， 6,故(13456，b)为(1234567，)的直接子概念，标号 标号为21。 为21。 3)画出G的导出子图S1=G[PUW(P)-](约 3)画出G的由P={1,3,4,5,6和N(P)-b={a,c, 简后)，其对应的形式背景为K。取二部图S的属 df,导出的子图S,二部图S的属性集中度数最 性集N(P)-i中度数最大的顶点i,N(i)=P,则 大的顶点c,N(c)={1,4,5,6,故(1456，bc)为(13456，b) (P,)为形式背景K的概念，(P,iUi)为形式背景 的直接子概念，标号为31。 K中概念(P,)的直接子概念，标号为31。 4)画出S:的由P1={1,4,5,6和N(P)-c={a,df 4)画出S,的导出子图S2=SPU(W(P)-iJ e导出的子图S2,二部图S2的属性集中度数最大 (约简后)，其对应的形式背景为K2,取二部图S2的 的顶点a,N(a)=1,6,故(16，abc)为(1456，bc)的直接 属性集N(P)-i,中度数最大的顶点i2,N(i)=P2, 子概念，标号为41。画出S2的由P2={1,6和 则(P2,)为形式背景K2的概念，故(P2,iUiU)为形 N(P2)-a={el导出的子图S3,二部图S3的属性集中 式背景K中概念(P,iU)的直接子概念，标号为 度数最大的顶点e,N(e)={1h,故(1，abce)为(16，abc) 41。继续下去，直到P为单点集，则(P,iUnUi2U) 的直接子概念，标号为51。此时P3={1为单点
N (i) = P (P,i) K G S = G[P∪(M −i)] S K ∗ = (P,(M −i),I ∗ ) j S M −i N (j) = Q (Q, j) K ∗ (Q,i∪ j) K (Q,i∪ j) (P,i) 顶点， ，则 为形式背景 的概念。 的 导出子图记为 ，与二部图 相对应 的形式背景约简后记为 ，若 是 的顶点集 中度数最大的顶点， ，则 为形式背景 的概念， 为形式背景 的概念，且 是 的直接子概念。 (P,i) K (Q, j) K ∗ (Q,i∪ j) K G [ Q,i∪ j ] G 证明 为形式背景 的概念， 为形式 背景 的概念，前文已证。下证 为形式背 景 的概念，即需证 为二部图 的极大完 全子图。 G [ Q,i∪ j ] G o ∈ P− Q G [ Q∪o,i∪ j ] m ∈ M −i− j G [ Q,i∪ j∪m ] S j Q∪o K ∗ N (j) = Q M −i (Q,i∪ j) {i} ⊂ B ⊂ {i∪ j} (Q,i∪ j) (P,i) 用反证法。假设 不是二部图 的极 大完全子图，那么可能有下列两种情况：1）至少 存在 ,使 为完全二部图；2）至 少存在 ， 使 为完全二部 图。如果出现第一种情况，由完全二部图的定义 知在图 中顶点 与 中的每个顶点相邻，此与 在形式背景 中 矛盾。如果出现第二种 情况，由完全二部图定义知在图 S 中 m 与集 Q 中 的每个顶点相邻，那么 m 在 S 中的邻集必包含 j 在 S 中的邻集，这与形式背景已约简且 j 是 S 的顶 点集 中度数最大的顶点相矛盾。所以 为形式背景 K 的概念，并且不能找到集合 B，使 ，因此 是 的直接子概念。 G (P,i) (P,i) 根据定理 4 可以通过求 的导出子图的概念 来简化形式背景，并求出 的直接子概念。这 样经过反复的分解和约简，使形式背景越来越简 化，同时也能求出 的所有子概念。 因此便能生成顶层概念的所有直接子概念以 及它们各自的子概念。这便是基于二部图的深度 优先的概念格的迭代算法。 基于二部图的深度优先的概念格的迭代算法： 1) 最顶层概念为 (O, ϕ) ，标号为 1。 K = (O, M,I) G = (O,M;E) i N (i) = P (P,i) (O, ϕ) 2) 形式背景 (约简后)，其对应的二 部图为 ，取属性 M 中度数最大的顶点 ， ，则 为顶层概念 的直接子概念， 标号为 21。 G S 1 = G[P∪(N (P)−i)] K1 S 1 N (P)−i i1 N (i1) = P1 (P1,i1) K1 (P1,i∪i1) K (P,i) 3) 画出 的导出子图 (约 简后)，其对应的形式背景为 。取二部图 的属 性集 中度数最大的顶点 ， ，则 为形式背景 的概念， 为形式背景 中概念 的直接子概念，标号为 31。 S 1 S 2 = S 1[P1 ∪(N (P1)−i1)] K2 S 2 N (P1)−i1 i2 N (i2) = P2 (P2,i2) K2 (P2,i∪i1 ∪i2) (P1,i∪i1) Pl (Pl ,i∪i1 ∪i2 ··· ∪il) 4) 画出 的导出子图 (约简后)，其对应的形式背景为 ，取二部图 的 属性集 中度数最大的顶点 ， ， 则 为形式背景 的概念，故 为形 式背景 K 中概念 的直接子概念，标号为 41。继续下去，直到 为单点集，则 S l (ϕ, M) (l+2)1 (ϕ, M) l+3 为形式背景 K 的倒数第二层概念，它由导出子图 生成，其直接子概念为最底层概念 ，标号 为 ，最底层概念 的标号为 。 r1 S r−2 S r−2 ir−2 ∗ N (ir−2 ∗ ) = Pr−2 ∗ i∪i1∪ i2 ··· ∪ir−2 ∗ Pr−2 ∗ i∪i1 ∪i2 ··· ∪ir−2 ∗ (Pr−2 ∗ ,ir−2 ∗ ) (Pr−1,ir−1) Pr−2 ∗ (Pr−2 ∗ ,ir−2 ∗ ) (Pr−1,ir−1) (r −1)2 S r−2 S r−1 ∗ = S r−2[Pr−1 ∗ ∪(N (Pr−1 ∗ )−ir−1 ∗ )] 5) 从标号为 的概念回到生成它的导出子图 ，考察二部图 的属性集中未考虑过的度数 最大的顶点 。如果 是已生成的概 念的外延，且当此已生成概念的内涵包含 时，说明以 为外延的概念及其子概 念已生成，则不必再考虑此顶点；而当此已生成 概念的内涵等于 时，则 是 的直接子概念，且此概念及其子概念 已生成 (已标号)，此顶点也不必再往下考虑。如 果 不是已生成概念的外延，则 是 的直接子概念，标号为 ，然后按步 骤 3）和步骤 4）的方法画出 的导出子图 ，接着再取未考虑过的 最大度数顶点生成概念，直到倒数第二层概念。 6) 从标号为 (l+2)1 的概念起，重复 5)，便可得 到所有概念以及它们之间的父子关系。 3 实例 下面通过例 3 来具体说明此方法如何产生概 念格。 O = {1,2,3,4, 5,6,7} M = {a,b, c,d, e, f,g} 例 3 形式背景同例 1，其中的对象 表示 1 班至 7 班共 7 个班级，属性 表示班级特色，其中 a 表示团结，b 表示纪律 严明，c 表示学风端正，d 表示卫生环境好，e 表示 干部队伍过硬，f 表示英语四六级通过率高，g 表 示课余活动丰富。 下面用基于二部图的深度优先的概念格的迭 代算法来生成概念格。 1) 最顶层概念为 (1234567, ϕ) ，标号为 1。 G b N (b) = {1,3,4,5, 6} (13456,b) (1234567, ϕ) 2) 画出形式背景 (约简后) 所对应的二部图 ，其属性中度数最大的顶点为 ， ，故 为 的直接子概念，标号 为 21。 G P = {1,3,4,5,6} N (P)−b = d f, e} S 1 S 1 c N (c) = {1,4,5,6} (1456,bc) (13456,b) 3) 画出 的由 和 {a,c, 导出的子图 ，二部图 的属性集中度数最 大的顶点 ， ，故 为 的直接子概念，标号为 31。 S 1 P1 = {1,4,5,6} N (P1)−c = e} S 2 S 2 a N (a) = {1,6} (16,abc) (1456,bc) S 2 P2 = {1,6} N (P2)−a = {e} S 3 S 3 e N (e) = {1} (1,abce) (16,abc) P3 = {1} 4) 画出 的由 和 {a,df, 导出的子图 ，二部图 的属性集中度数最大 的顶点 ， ，故 为 的直接 子概念，标号 为 4 1 。画出 的 由 和 导出的子图 ，二部图 的属性集中 度数最大的顶点 ， ，故 为 的直接子概念，标号为 51。此时 为单点 ·690· 智 能 系 统 学 报 第 13 卷
第5期 窦林立，等：利用二部图生成概念格 ·691· 集，故(I,abce)为倒数第二层概念，其直接子概念 1456为外延的概念(16，abc)和(1456，bc),且其内涵 只有(，abedef),(,abcde f)为最底层概念，标号为6。 真包含a和c,故此二顶点不再考虑。N(df)={2,3,5, 5)从标号为51的概念(L,abce)开始返回到生 未出现过以235为外延的概念，故(235，df)为 成它的二部图S:,其属性集中除e外无其他顶点。 (1234567,)的直接子概念，标号为22。然后接着 所以返回到标号为41的概念(16，abc)的二部图S2, 画出G的由P={2,3,5}和N(P)-df=b,c,e导出的 其属性集中除a外还有顶点df和e。先看df, 子图S,二部图S的属性集中度数最大的顶点为 N(df)={5,未出现过以5为外延的概念，故(5，bcdf) b.N(b)={3,5,已出现过以35为外延的概念(35，bdf), 为(1456，bc)的直接子概念，标号为42，此时P2={5) 此概念的内涵恰好为bdf,则(35，bdf)也为(235，df) 为单点集，故(5，bcdf)为倒数第二层概念，其直接 的直接子概念，此顶点不再考虑。S,的属性集中 子概念只有(，abcdef)。再看e,N(e)={1,已出现 除b外，还有c和e,N(c)={5,已出现外延为5的概 过以1为外延的概念(1，abce),且其内涵abce真包 念(5，bcdf,且其内涵真包含cdf,故此顶点不再考 含bce,故此处不再考虑。 虑。N(e)=2,未出现过以2为外延的概念，故 现在返回到生成标号为31的概念(1456，bc)的 (2,def)为(235，df)的直接子概念，标号为33。此时 二部图S1,其属性集中除c外还有顶点a,dfe。其 其外延P'=2)为单点集，其直接子概念只有 中N(a)={1,6,N(e)={1,已出现过以16和1为外 延的概念(16，abc)和(1，abce,且其内涵真包含ab和 (,abcdef)。 be,故此二顶点不再考虑。而N(df)=3,5,未出 返回二部图G中的属性e,N(e)={1,2,71,未出 现过以35为外延的概念，故(35，bdf)为(13456，b)的 现过以127为外延的概念，故(127，e)为(1234567，) 直接子概念，标号为32。然后接着画出S:的由 的直接子概念，标号为23。接着画出G的由P== P'=3,5)和N(P)-df={c导出的子图S,二部图 {1,2,7)和N(P)-e={a,b,c,df月导出的子图S:",二 S:的属性集中度数最大的顶点为c,N(c)={5,已 部图S,"的属性集中a、b、c的邻集相等，约简后属 出现过以5为外延的概念(5，bedf),此概念的内涵 性集中度数最大的顶点为abc和df,N(abc)={1, 恰好为bcdf,则(5，bcdf)也为(35，bdf)的直接子概 N(df)=2,已出现过以1和2为外延的概念 念，此顶点不再考虑。 (1,abce)和(2，def),其内涵恰好为abce和def,则 现在返回到生成标号为21的概念(13456，b)的 (1,abce)和(2，def)也为(127，e)的直接子概念，此二 二部图G,其属性集中除b外，还有a、c、df和e。其 顶点不再考虑。 中N(@)=1,6,N(c)={1,4,5,6,已出现过以16和 到此已生成所有概念，见图4。其概念格见图3。 l. (16,abc) 6 41 (1,abce) (1456.bc 51* 31 (5,bcdf) S 35,bdf 42 32 5 (13456.b 21 (5,bcdf) 42 (35,bd) (235,d) 32 (o,abcdef) 6 22￥ 2,def 33 (127,e) G (1,abce) 23 (1234567,) 51 约简 12,def) 33# abc 图4生成概念格的过程 Fig.4 Process of generating concept lattice
(1,abce) (ϕ,abcde f) (ϕ,abcde f) 集，故 为倒数第二层概念，其直接子概念 只有 ， 为最底层概念，标号为 6。 (1,abce) S 3 e (16,abc) S 2 a d f e d f N (d f) = {5} (5,bcd f) (1456,bc) P2 ∗ = {5} (5,bcd f) (ϕ,abcde f) e N (e) = {1} (1,abce) abce bce 5) 从标号为 51 的概念 开始返回到生 成它的二部图 ，其属性集中除 外无其他顶点。 所以返回到标号为 41 的概念 的二部图 ， 其属性集中除 外还有顶点 和 。先看 ， ，未出现过以 5 为外延的概念，故 为 的直接子概念，标号为 42，此时 为单点集，故 为倒数第二层概念，其直接 子概念只有 。再看 ， ，已出现 过以 1 为外延的概念 ，且其内涵 真包 含 ，故此处不再考虑。 (1456,bc) S 1 c a,d f, e N (a) = {1,6} N (e) = {1} (16,abc) (1,abce) ab be N (d f) = {3,5} (35,bd f) (13456,b) S 1 P1 ∗ = {3,5} N (P1 ∗ )−d f = {c} S 2 ∗∗ S 2 ∗∗ c N (c) = {5} (5,bcd f) bcd f (5,bcd f) (35,bd f) 现在返回到生成标号为 31 的概念 的 二部图 ，其属性集中除 外还有顶点 。其 中 ， ，已出现过以 16 和 1 为外 延的概念 和 ，且其内涵真包含 和 ，故此二顶点不再考虑。而 ，未出 现过以 35 为外延的概念，故 为 的 直接子概念，标号为 32。然后接着画出 的由 和 导出的子图 ，二部图 的属性集中度数最大的顶点为 ， ，已 出现过以 5 为外延的概念 ，此概念的内涵 恰好为 ，则 也为 的直接子概 念，此顶点不再考虑。 (13456,b) G b a c d f e N (a) = {1,6} N (c) = {1,4,5,6} 现在返回到生成标号为 21 的概念 的 二部图 ，其属性集中除 外，还有 、 、 和 。其 中 ， ，已出现过以 16 和 (16,abc) (1456,bc) a c N (d f) = {2,3,5} (235,d f) (1234567, ϕ) G P ∗ = {2,3,5} N (P ∗ )−d f = {b, c, e} S 1 ∗ S 1 ∗ b N (b) = {3,5} (35,bd f) bd f (35,bd f) (235,d f) S 1 ∗ b c e N (c) = {5} (5,bcd f) cd f N (e) = {2} (2,de f) (235,d f) P1 ∗ = {2} (ϕ,abcde f) 1456 为外延的概念 和 ，且其内涵 真包含 和 ，故此二顶点不再考虑。 ， 未出现过 以 2 3 5 为外延的概念，故 为 的直接子概念，标号为 22。然后接着 画出 的由 和 导出的 子图 ，二部图 的属性集中度数最大的顶点为 ， ，已出现过以 35 为外延的概念 ， 此概念的内涵恰好为 ，则 也为 的直接子概念，此顶点不再考虑。 的属性集中 除 外，还有 和 ， ，已出现外延为 5 的概 念 ，且其内涵真包含 ，故此顶点不再考 虑。 ，未出现过以 2 为外延的概念，故 为 的直接子概念，标号为 33。此时 其外延 为单点集，其直接子概念只有 。 G e N (e) = {1,2,7} (127, e) (1234567, ϕ) P ∗∗ = {1,2,7} N (P ∗∗)−e = {a,b, c,d f} S 1 ∗∗ S 1 ∗∗ a b c abc d f N (abc) = {1} N (d f) = {2} (1,abce) (2,de f) abce de f (1,abce) (2,de f) (127, e) 返回二部图 中的属性 ， ，未出 现过以 127 为外延的概念，故 为 的直接子概念，标号为 23。接着画出 G 的由 和 导出的子图 ，二 部图 的属性集中 、 、 的邻集相等，约简后属 性集中度数最大的顶点为 和 ， ， ，已出现过 以 1 和 2 为外延的概念 和 ，其内涵恰好为 和 ， 则 和 也为 的直接子概念，此二 顶点不再考虑。 到此已生成所有概念，见图 4。其概念格见图 3。 S2 * S2 51# (1, abce) 41# (16, abc) 42# (5, bcdf ) 42# (5, bcdf ) 51# (1, abce) 6 # (f, abcdef ) 33# (2, def ) e 1 6 S3 约简 1 # (1234567, f) G 23# (127, e) S1 * 33# (2, def ) 22# (235, df ) 32# (35, bdf ) a b c df e 1 2 3 4 5 6 7 a b c df 1 2 7 S1 21# (13456, b) 32# (35, bdf ) e 31# (1456, bc) a c df e 1 3 4 5 6 a df e 1 4 5 6 2 3 5 b c c 3 5 S1 ** abc df 1 2 7 S2 ** 图 4 生成概念格的过程 Fig. 4 Process of generating concept lattice 第 5 期 窦林立，等：利用二部图生成概念格 ·691·
·692· 智能系统学报 第13卷 4结束语 Very fast instances for concept generation[M]//MIS- SAOUI R,SCHMIDT J.Formal Concept Analysis.Ber- 本文结合图论的内容，将概念格的形式背景 lin,Heidelberg:Springer,2006,3874:119-129. 和一个二部图相对应，利用二部图的极大完全子 [12]BERRY A.SANJUAN E.SIGAYRET A.Generalized 图来寻找概念，并且同时得到概念之间的父子关 domination in closure systems[J].Discrete applied math- 系，最终构造出概念格。此方法同时生成Hasse图， ematics.2006.154(7):1064-1084 简单直观，能够快速生成概念格。基于概念格的 [13]李立峰，刘三阳，罗清君.弦二部图的概念格表示).电 形式背景与图论内容的高度关联性，二者之间其 子学报，2013,41(7)：1384-1388 余理论的相互应用是我们下一进努力的方向。 LI Lifeng,LIU Sanyang,LUO Qingjun.Representing chordal bipartite graph using concept lattice theory[J]. 参考文献： Acta electronic sinica,2013,41(7):1384-1388 [14]李立峰.链图的概念格表示[.计算机科学，2014 [1]GANTER B,WILLE R.Formal concept analysis:mathem- 41(2)264-266 atical foundations[M].FRANZKE C,trans.Berlin Heidel- LI Lifeng.Chain graph and their concept lattice represent- berg:Springer-Verlag,1999. ation[J].Computer science,2014,41(2):264-266. [2]WILLE R.Restructuring lattice theory:an approach based [15]张涛，洪文学，路静.形式背景的属性树表示).系统工 on hierarchies of concepts[Ml//RIVAL I.Ordered Sets. 程理论与实践，2011,31(S2:197-202 Berlin Heidelberg:Springer,1982:445-470. ZHANG Tao,HONG Wenxue,LU Jing.Attribute tree [3]BELOHLAVEK R.SIGMUND E.ZACPAL J.Evaluation representation for formal context[J].Systems engineering- of IPAQ questionnaires supported by formal concept ana- theory and practice,2011,31(S2):197-202. lysis[J].Information sciences,2011,181(10):1774-1786. [16]张涛，任宏雷.形式背景的属性拓扑表示[).小型微型 [4]NGUYEN TT,HUI S C,CHANG Kuiyu.A lattice-based 计算机系统，2014,35(3)：590-593 approach for mathematical search using formal concept ZHANG Tao,REN Honglei.Attribute topology of form- analysis[].Expert systems with applications,2012,39(5): al context[J].Journal of Chinese computer systems,2014, 5820-5828 35(3590-593. [5]GODIN R.MISSAOUI R,ALAOUI H.Incremental [17刀张涛，路静，任宏雷.一种基于树图的属性约简算法[)， concept formation algorithms based on Galois(concept) 小型微型计算机系统，2014,35(1)：177-180 lattices[J].Computational intelligence,1995,11(2): ZHANG Tao,LU Jing,REN Honglei.An algorithm based 246-267 on free graph for calculation for attribute reduction[J]. [6]HO T B.Incremental conceptual clustering in the frame- Journal of Chinese computer systems,2014,35(1): work of Galois lattice[C]//LU H,MOTODA H,LIU H. 177-180. KDD:Techniques and Applications.Singapore:World Sci- [18]黄天民，徐扬，赵海良，等.格、序引论及其应用M.成 entific,1997:49-64. 都：西南交通大学出版社，1998 [7]张文修，魏玲，祁建军.概念格的属性约简理论与方法凹 [19]王树禾.图论M.北京：科学出版社，2009， 中国科学E辑：信息科学，2005,35(6)：628-639. [20]肖位枢.图论及其算法[M.北京：航空工业出版社， ZHANG Wenxiu,WEI Ling,QI Jianjun.Attribute reduc- 1993. tion theory and approach to concept lattice[J].Science in 作者简介： China series E:information sciences,2005,35(6): 实林立，女，1975年生，硕士研究 628-639. 生，讲师，主要研究方向为计算机数 [8]ELLOUMI S,JAAM J,HASNAH A,et al.A multi-level 学、离散数学。参与完成多项省级和 conceptual data reduction approach based on the 市级课题。发表学术论文6篇。 Lukasiewicz implication[J].Information sciences,2004, 163(4:253-262. [9]AMILHASTRE J.VILAREM M C,JANSSEN P.Com- plexity of minimum biclique cover and minimum biclique 展正然，女，1981年生，硕士研究 decomposition for bipartite domino-free graphs[J].Dis- 生，讲师，主要研究方向为微分方程。 crete applied mathematics,1998,86(2/3):125-144. 发表学术论文9篇.被E检索2篇.SCI [10]BERRY A,SIGAYRET A.Representing a concept lat- 检索1篇，出版教材1部。 tice by a graph[J].Discrete applied mathematics,2004, 144(1/2)27-42. [11]BERRY A,MCCONNELL R M,SIGAYRET A,et al
4 结束语 本文结合图论的内容，将概念格的形式背景 和一个二部图相对应，利用二部图的极大完全子 图来寻找概念，并且同时得到概念之间的父子关 系，最终构造出概念格。此方法同时生成 Hasse 图， 简单直观，能够快速生成概念格。基于概念格的 形式背景与图论内容的高度关联性，二者之间其 余理论的相互应用是我们下一进努力的方向。 参考文献： GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. FRANZKE C, trans. Berlin Heidelberg: Springer-Verlag, 1999. [1] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Berlin Heidelberg: Springer, 1982: 445–470. [2] BELOHLAVEK R, SIGMUND E, ZACPAL J. Evaluation of IPAQ questionnaires supported by formal concept analysis[J]. Information sciences, 2011, 181(10): 1774–1786. [3] NGUYEN T T, HUI S C, CHANG Kuiyu. A lattice-based approach for mathematical search using formal concept analysis[J]. Expert systems with applications, 2012, 39(5): 5820–5828. [4] GODIN R, MISSAOUI R, ALAOUI H. Incremental concept formation algorithms based on Galois (concept) lattices[J]. Computational intelligence, 1995, 11(2): 246–267. [5] HO T B. Incremental conceptual clustering in the framework of Galois lattice[C]//LU H, MOTODA H, LIU H. KDD: Techniques and Applications. Singapore: World Scientific, 1997: 49–64. [6] 张文修, 魏玲, 祁建军. 概念格的属性约简理论与方法[J]. 中国科学 E 辑：信息科学, 2005, 35(6): 628–639. ZHANG Wenxiu, WEI Ling, QI Jianjun. Attribute reduction theory and approach to concept lattice[J]. Science in China series E: information sciences, 2005, 35(6): 628–639. [7] ELLOUMI S, JAAM J, HASNAH A, et al. A multi-level conceptual data reduction approach based on the Lukasiewicz implication[J]. Information sciences, 2004, 163(4): 253–262. [8] AMILHASTRE J, VILAREM M C, JANSSEN P. Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs[J]. Discrete applied mathematics, 1998, 86(2/3): 125–144. [9] BERRY A, SIGAYRET A. Representing a concept lattice by a graph[J]. Discrete applied mathematics, 2004, 144(1/2): 27–42. [10] [11] BERRY A, MCCONNELL R M, SIGAYRET A, et al. Very fast instances for concept generation[M]//MISSAOUI R, SCHMIDT J. Formal Concept Analysis. Berlin, Heidelberg: Springer, 2006, 3874: 119–129. BERRY A, SANJUAN E, SIGAYRET A. Generalized domination in closure systems[J]. Discrete applied mathematics, 2006, 154(7): 1064–1084. [12] 李立峰, 刘三阳, 罗清君. 弦二部图的概念格表示[J]. 电 子学报, 2013, 41(7): 1384–1388. LI Lifeng, LIU Sanyang, LUO Qingjun. Representing chordal bipartite graph using concept lattice theory[J]. Acta electronic sinica, 2013, 41(7): 1384–1388. [13] 李立峰. 链图的概念格表示[J]. 计算机科学, 2014, 41(2): 264–266. LI Lifeng. Chain graph and their concept lattice representation[J]. Computer science, 2014, 41(2): 264–266. [14] 张涛, 洪文学, 路静. 形式背景的属性树表示[J]. 系统工 程理论与实践, 2011, 31(S2): 197–202. ZHANG Tao, HONG Wenxue, LU Jing. Attribute tree representation for formal context[J]. Systems engineeringtheory and practice, 2011, 31(S2): 197–202. [15] 张涛, 任宏雷. 形式背景的属性拓扑表示[J]. 小型微型 计算机系统, 2014, 35(3): 590–593. ZHANG Tao, REN Honglei. Attribute topology of formal context[J]. Journal of Chinese computer systems, 2014, 35(3): 590–593. [16] 张涛, 路静, 任宏雷. 一种基于树图的属性约简算法[J]. 小型微型计算机系统, 2014, 35(1): 177–180. ZHANG Tao, LU Jing, REN Honglei. An algorithm based on free graph for calculation for attribute reduction[J]. Journal of Chinese computer systems, 2014, 35(1): 177–180. [17] 黄天民, 徐扬, 赵海良, 等. 格、序引论及其应用[M]. 成 都: 西南交通大学出版社, 1998. [18] [19] 王树禾. 图论[M]. 北京: 科学出版社, 2009. 肖位枢. 图论及其算法[M]. 北京: 航空工业出版社, 1993. [20] 作者简介： 窦林立，女，1975 年生，硕士研究 生，讲师，主要研究方向为计算机数 学、离散数学。参与完成多项省级和 市级课题。发表学术论文 6 篇。 展正然，女，1981 年生，硕士研究 生，讲师，主要研究方向为微分方程。 发表学术论文 9 篇，被 EI 检索 2 篇，SCI 检索 1 篇，出版教材 1 部。 ·692· 智 能 系 统 学 报 第 13 卷