[1]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]
Copy

Constructing concept lattice using bipartite graph

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 13 Number of periods: 2018 5 Page number: 687-692 Column: 学术论文—人工智能基础 Public date: 2018-09-05
Title:
Constructing concept lattice using bipartite graph
Author(s):
DOU Linli;  ZHAN Zhengran
Basic Teaching Department, The Great Wall College, China University of Geosciences, Baoding 071002, China
Keywords:
formal context; concept lattice; bipartite graph; maximum complete subgraph; direct subconcept; Hasse diagram; graph theory; induced subgraph
CLC:
TP18
DOI:
10.11992/tis.201703026
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.
References:
[1] GANTER B, WILLE R. Formal concept analysis:mathematical foundations[M]. FRANZKE C, trans. Berlin Heidelberg:Springer-Verlag, 1999.
[2] WILLE R. Restructuring lattice theory:an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Berlin Heidelberg:Springer, 1982:445-470.
[3] BELOHLAVEK R, SIGMUND E, ZACPAL J. Evaluation of IPAQ questionnaires supported by formal concept analysis[J]. Information sciences, 2011, 181(10):1774-1786.
[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.
[5] GODIN R, MISSAOUI R, ALAOUI H. Incremental concept formation algorithms based on Galois (concept) lattices[J]. Computational intelligence, 1995, 11(2):246-267.
[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.
[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
[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.
[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.
[10] BERRY A, SIGAYRET A. Representing a concept lattice by a graph[J]. Discrete applied mathematics, 2004, 144(1/2):27-42.
[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.
[12] BERRY A, SANJUAN E, SIGAYRET A. Generalized domination in closure systems[J]. Discrete applied mathematics, 2006, 154(7):1064-1084.
[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
[14] 李立峰. 链图的概念格表示[J]. 计算机科学, 2014, 41(2):264-266 LI Lifeng. Chain graph and their concept lattice representation[J]. Computer science, 2014, 41(2):264-266
[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
[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
[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
[18] 黄天民, 徐扬, 赵海良, 等. 格、序引论及其应用[M]. 成都:西南交通大学出版社, 1998.
[19] 王树禾. 图论[M]. 北京:科学出版社, 2009.
[20] 肖位枢. 图论及其算法[M]. 北京:航空工业出版社, 1993.
Similar References:

Memo

-

Last Update: 2018-10-25

Copyright © CAAI Transactions on Intelligent Systems