﻿ 利用二部图生成概念格
«上一篇
 文章快速检索 高级检索

 智能系统学报  2018, Vol. 13 Issue (5): 687-692  DOI: 10.11992/tis.201703026 0

### 引用本文

DOU Linli, ZHAN Zhengran. Constructing concept lattice using bipartite graph[J]. CAAI Transactions on Intelligent Systems, 2018, 13(5): 687-692. DOI: 10.11992/tis.201703026.

### 文章历史

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.
Key words: formal context    concept lattice    bipartite graph    maximum complete subgraph    direct subconcept    Hasse diagram    graph theory    induced subgraph

1 基本概念

1.1 概念格

2) 在形式背景 $K = (O,M,I)$ 的概念集合间建立一种偏序关系：给定两个概念 ${C_1} = ({A_1},{B_1})$ ${C_2} = ({A_2},{B_2})$ ，则 ${C_1} < {C_2} \Leftrightarrow {A_1} \subset {A_2}$ (或 ${B_1} \supset {B_2}$ )，那么 ${C_1}$ ${C_2}$ 的子概念， ${C_2}$ ${C_1}$ 的父概念。根据这种偏序关系，形式背景 $K = (O,M,I)$ 的概念节点的集合产生一种格结构，称它为 $K = (O,M,I)$ 的概念格，记为 $L(K)$ 。并且由这种偏序关系可生成 $L(K)$ 的Hasse图：对于 $L(K)$ 中的两个不同的节点 ${C_1}$ ${C_2}$ ，如果 ${C_1} < {C_2}$ ，并且不存在其他的节点 ${C_3}$ ，使得 ${C_1} < {C_3} < {C_2}$ ，则 ${C_1}$ ${C_2}$ 之间就存在一条边。此时 ${C_1}$ 称为 ${C_2}$ 的直接子概念， ${C_2}$ 称为 ${C_1}$ 的直接父概念。

2) 若 $i,j \in M,$ $i \ne j$ $P = \left\{ {o \in O|oIi} \right\}$ $Q =$ $\left\{ {o \in O|oIj} \right\}$ ，若 $P = Q$ ，则可以将两个属性 $i$ $j$ 缩写成一个属性 $ij$ 。显然，缩写后的形式背景与原形式背景生成的概念格相同。

1.2 图论

2) 设 ${V_{\rm{0}}}$ 是图G的任一顶点子集，G中与 ${V_{\rm{0}}}$ 的顶点邻接的所有顶点的集合称为 ${V_{\rm{0}}}$ 的邻集，记作 $N\left( {{V_{\rm{0}}}} \right)$

3) 设 $v \in V\left( G \right)$ G中与顶点v关联的边的数目称为v(在G中)的度。

4) GS是两个图，且 $V\left( S \right) \subseteq V\left( G \right){\rm{,}}$ $E\left( S \right)$ $\subseteq E\left( G \right)$ ，则 $S$ $G$ 的子图，记作 $S \subseteq G$ 。设 ${V^*}$ $G = \left( {V{\rm{,}}E} \right)$ 的顶点集的一个非空子集，以 ${V^*}$ 作为顶点集，以两个端点均在 ${V^*}$ 中的边的全体为边的子图称为由 ${V^*}$ 导出的 $G$ 的子图，记为 $G\left[ {{V^*}} \right]$ ，则 $G\left[ {{V^*}} \right]$ $G$ 的导出子图。

 Download: 图 1 表2对应的二部图 Fig. 1 Bipartite graph for table 2
 Download: 图 2 表2对应的概念格 Fig. 2 Concept lattice for table 2
 Download: 图 3 表1对应的概念格 Fig. 3 Concept lattice for table 1
2 利用二部图生成概念格

1) 最顶层概念为 $\left( {O,\phi } \right)$ ，标号为1。

2) 形式背景 $K = (O,M,I)$ (约简后)，其对应的二部图为 $G = \left( {O{\rm{,}}M{\rm{;}}E} \right)$ ，取属性M中度数最大的顶点 $i$ $N\left( i \right) = P$ ，则 $\left( {P,i} \right)$ 为顶层概念 $\left( {O,\phi } \right)$ 的直接子概念，标号为21。

3) 画出 $G$ 的导出子图 ${S_1} = G[P \cup \left( {N\left( P \right) - i} \right)]$ (约简后)，其对应的形式背景为 ${K_1}$ 。取二部图 ${S_1}$ 的属性集 $N\left( P \right) - i$ 中度数最大的顶点 ${i_1}$ $N\left( {{i_1}} \right) =$ ${P_1}$ ，则 $\left( {{P_1},{i_1}} \right)$ 为形式背景 ${K_1}$ 的概念， $\left( {{P_1},i \cup {i_1}} \right)$ 为形式背景 $K$ 中概念 $\left( {P,i} \right)$ 的直接子概念，标号为31。

4) 画出 ${S_1}$ 的导出子图 ${S_2} = {S_1}[{P_1} \cup \left( {N\left( {{P_1}} \right) - {i_1}} \right)]$ (约简后)，其对应的形式背景为 ${K_2}$ ，取二部图 ${S_2}$ 的属性集 $N\left( {{P_1}} \right) - {i_1}$ 中度数最大的顶点 ${i_2}$ $N\left( {{i_2}} \right) = {P_2}$ ，则 $\left( {{P_2},{i_2}} \right)$ 为形式背景 ${K_2}$ 的概念，故 $\left( {{P_2},i \cup {i_1} \cup {i_2}} \right)$ 为形式背景K中概念 $\left( {{P_1},i \cup {i_1}} \right)$ 的直接子概念，标号为41。继续下去，直到 ${P_l}$ 为单点集，则 $\left( {{P_l},i \cup {i_1} \cup {i_2} \cdots \cup {i_l}} \right)$ 为形式背景K的倒数第二层概念，它由导出子图 ${S_l}$ 生成，其直接子概念为最底层概念 $\left( {\phi ,M} \right)$ ，标号为 $\left( {l + 2} \right)1$ ，最底层概念 $\left( {\phi ,M} \right)$ 的标号为 $l + 3$

5) 从标号为 $r1$ 的概念回到生成它的导出子图 ${S_{r - 2}}$ ，考察二部图 ${S_{r - 2}}$ 的属性集中未考虑过的度数最大的顶点 ${i_{r - 2}}^*$ 。如果 $N\left( {{i_{r - 2}}^*} \right) = {P_{r - 2}}^*$ 是已生成的概念的外延，且当此已生成概念的内涵包含 $i \cup {i_1} \cup$ ${i_2} \cdots \cup {i_{r - 2}}^*$ 时，说明以 ${P_{r - 2}}^*$ 为外延的概念及其子概念已生成，则不必再考虑此顶点；而当此已生成概念的内涵等于 $i \cup {i_1} \cup {i_2} \cdots \cup {i_{r - 2}}^*$ 时，则 $\left( {{P_{r - 2}}^*,{i_{r - 2}}^*} \right)$ $\left( {{P_{r - 1}},{i_{r - 1}}} \right)$ 的直接子概念，且此概念及其子概念已生成(已标号)，此顶点也不必再往下考虑。如果 ${P_{r - 2}}^*$ 不是已生成概念的外延，则 $\left( {{P_{r - 2}}^*,{i_{r - 2}}^*} \right)$ $\left( {{P_{r - 1}},{i_{r - 1}}} \right)$ 的直接子概念，标号为 $\left( {r - 1} \right)2$ ，然后按步骤3）和步骤4）的方法画出 ${S_{r - 2}}$ 的导出子图 ${S_{r - 1}}^* =$ ${S_{r - 2}}[{P_{r - 1}}^* \cup \left( {N\left( {{P_{r - 1}}^*} \right) - {i_{r - 1}}^*} \right)]$ ，接着再取未考虑过的最大度数顶点生成概念，直到倒数第二层概念。

6) 从标号为 $\left( {l + 2} \right)1$ 的概念起，重复5)，便可得到所有概念以及它们之间的父子关系。

3 实例

1) 最顶层概念为 $\left( {1234567,\phi } \right)$ ，标号为1。

2) 画出形式背景(约简后)所对应的二部图 $G$ ，其属性中度数最大的顶点为 $b$ $N\left( b \right) = \{ 1,3,4,5,$ $6\}$ ，故 $\left( {13456,b} \right)$ $\left( {1234567,\phi } \right)$ 的直接子概念，标号为21。

3) 画出 $G$ 的由 $P = \left\{ {1,3,4,5,6} \right\}$ $N\left( P \right) - b =$ {a,c, ${ df,e} \}$ 导出的子图 ${S_1}$ ，二部图 ${S_1}$ 的属性集中度数最大的顶点 $c$ $N\left( c \right) = \left\{ {1,4,5,6} \right\}$ ，故 $\left( {1456,bc} \right)$ $\left( {13456,b} \right)$ 的直接子概念，标号为31。

4) 画出 ${S_1}$ 的由 ${P_1} = \left\{ {1,4,5,6} \right\}$ $N\left( {{P_1}} \right) - c =$ {a,df, ${ e} \}$ 导出的子图 ${S_2}$ ，二部图 ${S_2}$ 的属性集中度数最大的顶点 $a$ $N\left( a \right) = \left\{ {1,6} \right\}$ ，故 $\left( {16,abc} \right)$ $\left( {1456,bc} \right)$ 的直接子概念，标号为41。画出 ${S_2}$ 的由 ${P_2} = \left\{ {1,6} \right\}$ $N\left( {{P_2}} \right) - a = \left\{ e \right\}$ 导出的子图 ${S_3}$ ，二部图 ${S_3}$ 的属性集中度数最大的顶点 $e$ $N\left( e \right) = \left\{ 1 \right\}$ ，故 $\left( {1,abce} \right)$ $\left( {16,abc} \right)$ 的直接子概念，标号为51。此时 ${P_3} = \left\{ 1 \right\}$ 为单点集，故 $\left( {1,abce} \right)$ 为倒数第二层概念，其直接子概念只有 $\left( {\phi ,abcdef} \right)$ $\left( {\phi ,abcdef} \right)$ 为最底层概念，标号为6。

5) 从标号为51的概念 $\left( {1,abce} \right)$ 开始返回到生成它的二部图 ${S_3}$ ，其属性集中除 $e$ 外无其他顶点。所以返回到标号为41的概念 $\left( {16,abc} \right)$ 的二部图 ${S_2}$ ，其属性集中除 $a$ 外还有顶点 $df$ $e$ 。先看 $df$ $N\left( {df} \right) = \left\{ 5 \right\}$ ，未出现过以5为外延的概念，故 $\left( {5,bcdf} \right)$ $\left( {1456,bc} \right)$ 的直接子概念，标号为42，此时 ${P_2}^* = \left\{ 5 \right\}$ 为单点集，故 $\left( {5,bcdf} \right)$ 为倒数第二层概念，其直接子概念只有 $\left( {\phi ,abcdef} \right)$ 。再看 $e$ $N\left( e \right) = \left\{ 1 \right\}$ ，已出现过以1为外延的概念 $\left( {1,abce} \right)$ ，且其内涵 $abce$ 真包含 $bce$ ，故此处不再考虑。

 Download: 图 4 生成概念格的过程 Fig. 4 Process of generating concept lattice
4 结束语

 [1] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. FRANZKE C, trans. Berlin Heidelberg: Springer-Verlag, 1999. (0) [2] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Berlin Heidelberg: Springer, 1982: 445–470. (0) [3] BELOHLAVEK R, SIGMUND E, ZACPAL J. Evaluation of IPAQ questionnaires supported by formal concept analysis[J]. Information sciences, 2011, 181(10): 1774-1786. DOI:10.1016/j.ins.2010.04.011 (0) [4] 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. DOI:10.1016/j.eswa.2011.11.085 (0) [5] GODIN R, MISSAOUI R, ALAOUI H. Incremental concept formation algorithms based on Galois (concept) lattices[J]. Computational intelligence, 1995, 11(2): 246-267. DOI:10.1111/coin.1995.11.issue-2 (0) [6] HO T B. Incremental conceptual clustering in the frame-work of Galois lattice[C]//LU H, MOTODA H, LIU H. KDD: Techniques and Applications. Singapore: World Scientific, 1997: 49–64. (0) [7] 张文修, 魏玲, 祁建军. 概念格的属性约简理论与方法[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. (0) [8] 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. DOI:10.1016/j.ins.2003.06.013 (0) [9] 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. (0) [10] BERRY A, SIGAYRET A. Representing a concept lattice by a graph[J]. Discrete applied mathematics, 2004, 144(1/2): 27-42. (0) [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. (0) [12] BERRY A, SANJUAN E, SIGAYRET A. Generalized domination in closure systems[J]. Discrete applied mathematics, 2006, 154(7): 1064-1084. DOI:10.1016/j.dam.2005.04.009 (0) [13] 李立峰, 刘三阳, 罗清君. 弦二部图的概念格表示[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. DOI:10.3969/j.issn.0372-2112.2013.07.022 (0) [14] 李立峰. 链图的概念格表示[J]. 计算机科学, 2014, 41(2): 264-266. LI Lifeng. Chain graph and their concept lattice representation[J]. Computer science, 2014, 41(2): 264-266. DOI:10.3969/j.issn.1002-137X.2014.02.058 (0) [15] 张涛, 洪文学, 路静. 形式背景的属性树表示[J]. 系统工程理论与实践, 2011, 31(S2): 197-202. ZHANG Tao, HONG Wenxue, LU Jing. Attribute tree representation for formal context[J]. Systems engineering-theory and practice, 2011, 31(S2): 197-202. (0) [16] 张涛, 任宏雷. 形式背景的属性拓扑表示[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. DOI:10.3969/j.issn.1000-1220.2014.03.030 (0) [17] 张涛, 路静, 任宏雷. 一种基于树图的属性约简算法[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. DOI:10.3969/j.issn.1000-1220.2014.01.036 (0) [18] 黄天民, 徐扬, 赵海良, 等. 格、序引论及其应用[M]. 成都: 西南交通大学出版社, 1998. (0) [19] 王树禾. 图论[M]. 北京: 科学出版社, 2009. (0) [20] 肖位枢. 图论及其算法[M]. 北京: 航空工业出版社, 1993. (0)