[1]毛华,刘祎超.基于权值最大圈的概念格构造算法[J].智能系统学报,2016,11(4):519-525.[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(4):519-525.[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(4):519-525.[doi:10.11992/tis.201606006]
基于权值最大圈的概念格构造算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
11
期数:
2016年第4期
页码:
519-525
栏目:
学术论文—知识工程
出版日期:
2016-07-25
- Title:
- An algorithm for concept lattice construction based on maximum cycles of weight values
- Keywords:
- formal context; concept lattice; concept; weight value; maximum cycle; attributes topology; data processing
- 分类号:
- TP18
- 摘要:
- 概念格作为一种有效的知识发现与数据处理的工具，在许多领域得到了广泛应用。寻找形式背景下的所有概念是概念格理论研究的一个基本问题。对于一个给定的形式背景，在属性拓扑图的基础上，结合图论的思想，给出了一种概念格的构造算法。算法过程如下：首先，构造弱化的属性拓扑图；其次，通过寻找弱化的属性拓扑图中的每个权值最大圈方法来生成概念，形式背景的所有概念被生成；最后，构造出概念格。通过分析说明此算法复杂度比以往的一些算法复杂度低。此外，用一个实例验证了这一算法的有效性与正确性。为知识获取提供了有益的思路与方法。
- Abstract:
- As an effective tool for knowledge discovery and data processing, the concept lattice has been widely applied in many fields. Searching all concepts in a formal context is a basic problem for research into concept lattice theory. On the basis of attribute topology and combined with the idea of graph theory, an algorithm to construct a concept lattice in a fixed formal context is given. The process is as follows:firstly, a weakened attribute topology was built up; then, by applying the method of searching the maximum cycle with a weight in the above weakened attribute topology, all of the formal context concepts were obtained; finally the concept lattice was established. Subsequent analysis illustrated that the algorithm can reduce complexity compared with some existing algorithms. In addition, using an example, the accuracy and validity of the algorithm was verified. The result presents a useful idea and method for knowledge acquisition.
- 参考文献/References:
-
[1] WILLE R. Restructuring lattice theory:an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Dordrecht:Springer, 1982.
[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] 王旭杨, 李明. 基于概念格的数据挖掘方法研究[J]. 计算机应用, 2005, 25(4):827-829. WANG Xuyang, LI Ming. Method of data mining based on concept lattice[J]. Computer applications, 2005, 25(4):827-829.
[5] SIFF M, REPS T. Identifying modules via concept analysis[C]//Proceedings of International Conference on Software Maintenance. Washington, DC, USA:IEEE Computer Society, 1997:170-179.
[6] FERJANI F, ELLOUMI S, JAOUA A, et al. Formal context coverage based on isolated labels:an efficient solution for text feature extraction[J]. Information sciences, 2012, 188:198-214.
[7] 邓君, 马晓君, 张巨峰, 等. 基于概念格的实体档案馆用户行为研究[J]. 图书情报工作, 2014, 58(12):109-117. DENG Jun, MA Xiaojun, ZHANG Jufeng, et al. Study on entity archives’ user behavior based on concept lattice[J]. Library and information service, 2014, 58(12):109-117.
[8] 张晓, 龙伟, 卢斌. 基于概念格的关联规则在排产管理的应用[J]. 计算机工程与应用, 2014, 50(9):264-270. v ZHANG Xiao, LONG Wei, LU Bin. Application of association rule based on concept lattice for scheduling management[J]. Computer engineering and applications, 2014, 50(9):264-270.
[9] 张涛, 任宏雷. 形式背景的属性拓扑表示[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.
[10] BERRY A, SIGAYRET A. Representing a concept lattice by a graph[J]. Discrete applied mathematics, 2004, 144(1/2):27-42.
[11] 李立峰, 刘三阳, 罗清君. 弦二部图的概念格表示[J]. 电子学报, 2013, 41(7):1384-1388. LI Lifeng, LIU Sanyang, LUO Qingjun. Representing chordal bipartite graph using concept lattice theory[J]. Acta electronica sinica, 2013, 41(7):1384-1388.
[12] DAVEY B A, PRIESTLEY H A. Introduction to lattices and order[M]. 2nd ed. New York:Cambridge University Press, 2002:66-69.
[13] 王树禾. 图论[M]. 北京:科学出版社, 2009.
[14] ZHANG Tao, REN Honglei, WANG Xiaomin. A calculation of formal concept by attribute topology[J]. ICIC express letters part B:applications, 2013, 4(3):793-800.
[15] 方嘉琳. 集合论[M]. 长春:吉林人民出版社, 1982.
- 相似文献/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):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]
[10]毛华,史明.利用二元拟阵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]
[11]窦林立,展正然.利用二部图生成概念格[J].智能系统学报,2018,13(5):687.[doi:10.11992/tis.201703026]
DOU Linli,ZHAN Zhengran.Constructing concept lattice using bipartite graph[J].CAAI Transactions on Intelligent Systems,2018,13():687.[doi:10.11992/tis.201703026]
[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
收稿日期:2016-06-02。
基金项目:国家自然科学基金项目（61572011）；河北省自然科学基金项目（A2013201119）.
作者简介:毛华,女,1963年生,教授,博士,主要研究方向为计算机数学及其应用、拟阵理论、离散数学。发表学术论文90余篇,其中被SCI、EI检索20余篇。
通讯作者:刘祎超.E-mail:1026074348@qq.com.
更新日期/Last Update:
1900-01-01