[1]窦林立,展正然.利用二部图生成概念格[J].智能系统学报,2018,13(5):687-692.[doi:10.11992/tis.201703026]
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]
点击复制
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]
利用二部图生成概念格
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
13
期数:
2018年第5期
页码:
687-692
栏目:
学术论文—人工智能基础
出版日期:
2018-09-05
- Title:
- Constructing concept lattice using bipartite graph
- Keywords:
- formal context; concept lattice; bipartite graph; maximum complete subgraph; direct subconcept; Hasse diagram; graph theory; induced subgraph
- 分类号:
- TP18
- 摘要:
- 概念格作为一种有效的知识发现与数据处理的工具，在许多领域得到了广泛应用，概念格的构造在其应用中具有重要的意义。每个概念格的形式背景都可以对应一个二部图，本文通过二部图的极大完全子图的概念来生成概念格，给出了基于二部图的深度优先的概念格的迭代算法。首先，对形式背景进行必要的约简；其次，利用二部图的极大完全子图得到顶层概念的直接子概念；最后，通过求二部图的导出子图来简化形式背景，并得出每个概念的直接子概念和所有子概念，从而生成概念格。
- 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.
- 相似文献/References:
-
[1]杜秋香,张继福,张素兰.概念特化的概念格更新构造算法[J].智能系统学报,2008,3(5):443.
DU Qiu-xiang,ZHANG J i-fu,ZHANG Su-lan.An improved algor ithm based on concept spec ialization for constructing concept lattices[J].CAAI Transactions on Intelligent Systems,2008,3():443.
[2]马丽,米据生.决策形势背景的命题推演[J].智能系统学报,2015,10(6):934.[doi:10.11992/tis.201507055]
MA Li,MI Jusheng.Propositions reasoning of decision formal contexts[J].CAAI Transactions on Intelligent Systems,2015,10():934.[doi:10.11992/tis.201507055]
[3]康向平,苗夺谦.一种基于概念格的集值信息系统中的知识获取方法[J].智能系统学报,2016,11(3):287.[doi:10.11992/tis.201603055]
KANG Xiangping,MIAO Duoqian.A knowledge acquisition method based on concept latticein set-valued information systems[J].CAAI Transactions on Intelligent Systems,2016,11():287.[doi:10.11992/tis.201603055]
[4]刘保相,孟肖丽.基于关联分析的气象云图识别问题研究[J].智能系统学报,2014,9(5):595.[doi:10.3969/j.issn.1673-4785.201306049]
LIU Baoxiang,MENG Xiaoli.The study on nephogram recognition based on relational analysis[J].CAAI Transactions on Intelligent Systems,2014,9():595.[doi:10.3969/j.issn.1673-4785.201306049]
[5]王雯,康向平,武燕.概念格在不完备形式背景中的知识获取模型[J].智能系统学报,2019,14(5):1048.[doi:10.11992/tis.201809021]
WANG Wen,KANG Xiangping,WU Yan.Knowledge acquisition model of concept lattice in an incomplete formal context[J].CAAI Transactions on Intelligent Systems,2019,14():1048.[doi:10.11992/tis.201809021]
[6]毛华,武秀.三支概念的一种构建方法[J].智能系统学报,2020,15(3):514.[doi:10.11992/tis.201904022]
MAO Hua,WU Xiu.A new method for constructing three-way concept[J].CAAI Transactions on Intelligent Systems,2020,15():514.[doi:10.11992/tis.201904022]
[7]胡小康,王俊红.基于相容模糊概念的规则提取方法[J].智能系统学报,2016,11(3):352.[doi:10.11992/tis.201603043]
HU Xiaokang,WANG Junhong.Research on rule extraction method based on compatibility fuzzy concept[J].CAAI Transactions on Intelligent Systems,2016,11():352.[doi:10.11992/tis.201603043]
[8]石慧,何苗,魏玲.基于不可约元下集格的概念获取[J].智能系统学报,2014,9(2):244.[doi:10.3969/j.issn.1673-4785.201307019]
SHI Hui,HE Miao,WEI Ling.Concept acquisition based on the down-set lattice of irreducible elements[J].CAAI Transactions on Intelligent Systems,2014,9():244.[doi:10.3969/j.issn.1673-4785.201307019]
[9]毛华,刘祎超.基于权值最大圈的概念格构造算法[J].智能系统学报,2016,11(4):519.[doi:10.11992/tis.201606006]
MAO Hua,LIU Yichao.An algorithm for concept lattice construction based on maximum cycles of weight values[J].CAAI Transactions on Intelligent Systems,2016,11():519.[doi:10.11992/tis.201606006]
[10]温云霞,王俊红.横向拆分形势背景下的快速规则提取方法[J].智能系统学报,2016,11(4):526.[doi:10.11992/tis.201606008]
WEN Yunxia,WANG Junhong.Research on a fast method for extracting rules based on horizontal splitting[J].CAAI Transactions on Intelligent Systems,2016,11():526.[doi:10.11992/tis.201606008]
[11]毛华,史明.利用二元拟阵Kn图的一种建格方法[J].智能系统学报,2017,12(3):333.[doi:10.11992/tis.201704022]
MAO Hua,SHI Ming.A constructive method of lattice using the Kn diagram of binary matroid[J].CAAI Transactions on Intelligent Systems,2017,12():333.[doi:10.11992/tis.201704022]
[12]张晓鹤,米据生,李美争.粒协调决策形式背景的属性约简与规则融合[J].智能系统学报,2019,14(6):1138.[doi:10.11992/tis.201905050]
ZHANG Xiaohe,MI Jusheng,LI Meizheng.Attribute reduction and rule fusion in granular consistent formal decision contexts[J].CAAI Transactions on Intelligent Systems,2019,14():1138.[doi:10.11992/tis.201905050]
[13]张晓鹤,陈德刚,米据生.基于信息熵的对象加权概念格[J].智能系统学报,2020,15(6):1097.[doi:10.11992/tis.202006043]
ZHANG Xiaohe,CHEN Degang,MI Jusheng.Object-weighted concept lattice based on information entropy[J].CAAI Transactions on Intelligent Systems,2020,15():1097.[doi:10.11992/tis.202006043]
备注/Memo
收稿日期:2017-03-21。
基金项目:河北省高校科研基金项目（Z2015137）.
作者简介:窦林立,女,1975年生,硕士研究生,讲师,主要研究方向为计算机数学、离散数学。参与完成多项省级和市级课题。发表学术论文6篇;展正然,女,1981年生,硕士研究生,讲师,主要研究方向为微分方程。发表学术论文9篇,被EI检索2篇,SCI检索1篇,出版教材1部。
通讯作者:窦林立.E-mail:1321407258@qq.com.
更新日期/Last Update:
2018-10-25