概念格理论发展分析

毛华,康然

(河北大学 数学与信息科学学院,河北 保定　071002)



概念格理论发展分析

毛华,康然

(河北大学 数学与信息科学学院,河北 保定071002)

摘要：通过查找多个国内外数据库,对近年(2009至2015年)国内外概念格理论的发展现状进行统计分析.介绍了近年有关概念格的建格算法、提取规则和关联规则、属性约简的方法以及概念格与其他学科的结合理论，此外还介绍了概念格理论在实体档案馆、排产管理和车辆运输安全性中的应用.

关键词：概念格；建格算法；属性约简；分析

第一作者：毛华(1963-) , 女，河北石家庄人,河北大学教授, 主要研究计算机数学基础及应用.

E-mail: mh@hbu.cn

E-mail: kangran09@163.com

概念格[1-2](concept lattice)，也叫做形式概念分析(formal concept analysis)，是由Wille首先提出的.概念格作为数据统计与分析的有效工具之一，拥有完备性和精确性的特点.概念格是根据对象和属性之间的二元关系建立起来的概念层次结构，又由于概念格能生成Hasse示图，这使它能生动、简明地体现出各概念之间的关系.由于其可视性强，又与其他的理论不断结合，而被广泛地应用于软件工程、知识发现等领域[3-4].

本文利用常用的数据库以及主要文献，对近6年(2009至2015年)概念格在国内外的发展状况进行统计和分析，并着重介绍近几年概念格的相关算法，概念格与其他学科的结合理论，以及在不同领域的应用.

1概念格研究现状

本节主要通过查找国内主要数据库，对与概念格有关的论文进行统计，得到图1.分析图1得知有关概念格理论及应用方面的论文数量一直处于较平稳状态，并于2013年开始有进一步的发展，不论是从文献数量还是引文数量都有所上升.

国际上概念格领域的研究更是科学界的一个热点,每年都会有大量的成果发表于各类期刊杂志(见图2,图3),代表概念格领域最高水平的国际会议ICFCA(international conference of formal concept analysis)自2003年每年举行1次,发表的论文集反应当年的最高研究成果,这些都不断推动概念格理论的扩大与发展.

图1　相关论文数量随年代变化趋势

图2　每年出版的文献数

图3　每年的引文数

2概念格研究方法

从概念格理论诞生[1]到对概念格的完备性等性质[5]的讨论,说明概念格理论的进一步成熟.而后,又有学者研究概念格的建格算法、提取规则和关联规则、属性约简等[6-9]方法,同时,还有学者研究概念格与其他学科理论相结合的问题.

2.1　概念格的建格算法

概念格的建格过程实际上是概念聚类的过程,对同一批数据,所生成的格也是唯一的.在已提出的许多建格算法[10-17]的基础上,谢志鹏[18]，胡可云等[19]提出了一些概念格的改进算法.

近几年来,随着概念格的发展,在国内,Zhang等[7]针对区间概念格的概念外延在区间范围内满足内涵属性的特性,提出基于属性集合幂集的区间概念格的渐进式生成算法.Liu等[6]通过分析粗糙概念格的概念和结构,并结合一般概念格的构建思想,针对决策形式背景,提出一种以决策属性值为切入点的粗糙概念格的分层建格算法,丰富了粗糙概念格的构建理论.周建等[20]将形式背景中的对象和属性之间的二元关系简化为布尔矩阵,并对布尔矩阵进行算法处理,着重分析求外延的算法及计算机语言的实现,得到概念格的一种建格算法.

2.2　概念格的提取规则和关联规则挖掘算法

数据挖掘是知识发现的一门重要技术,关联规则是数据挖掘的重要模式之一.而概念格是数据分析的有力工具,也是进行数据挖掘和规则提取的一种有效方法. 有关基于增量式概念格建造算法上的蕴含规则提取算法，可参见文献[10],有关基于Bordat算法的分类任务，可参见文献[21]，而应用到浏览检索中的概念聚类算法，可参见文献[17].

近几年又有许多学者提出了更为简单、便捷的算法.如Wang等[22]提出的基于对象集的概念格提取规则算法.Guo等[23]针对传统关联规则挖掘算法不利于用户选择关键数据进行分析、无法处理多值属性数据及效率低下等问题,提出了Apriori改进算法，以及多值属性的相关规则挖掘,并且运用概念格理论对多值属性数据进行了重新定义和分类,建立了数据挖掘参数调整机制.Fu等[24]针对现有的基于频繁模式树 FP-tree 和概念格的规则挖掘算法在构造概念格时存在重复遍历 FP-tree 问题,在挖掘后件约束的规则时算法构造的概念格包含冗余结点的这2个问题,提出了通过遍历 FP-tree 生成候选概念格节点的策略,并根据候选概念格节点进一步构造规则约束条件下无冗余概念格.

2.3　概念格的属性约简算法

概念格属性约简是保持对象集不改变,找出概念格中最小的属性集的过程.属性约简的过程能够完全确定形式背景上的概念及其层次结构, 更容易发现形式背景中隐含的知识,也使得这些知识的表示变得更简单.

Ganter[5]提出属性约简的思想,而Zhang等[25]提出了不同于Ganter的属性约简理论,进一步扩充了概念格约简理论.最近,Chen等[8]提出了一种面向对象概念格的属性约简方法并指出概念格的协调集和约简集与对象概念格的并不可约元的外延集之间的关系.Liu等[9]通过对概念格和同构理论的研究,发现不同的概念格之间存在同构关系,并提出一系列概念格同构的判定定理.基于这一理论,Liu等提出了概念格同构意义下属性约简的方法,这一方法能够降低形式背景结构空间复杂度,提高知识处理效率.

2.4　概念格与其他学科结合产生的方法

为了扩大和充实概念格理论,也为了该理论的广泛应用,必须将该理论与其他学科相结合.由目前研究成果得知,概念格与其他学科的结合较为广泛,其中与粗糙集和模糊集的结合成果相对丰富.

1)与粗糙集的结合

粗糙集[26]是发现知识、挖掘知识的数学工具,能有效地分析和处理不精确、不完备的信息.粗糙集利用等价关系对数据表进行分类[27],而概念格是基于相同数据表,并结合序理论对概念分层加以讨论.

Xu等[28]将变精度粗糙集β-上、下分布约简算法的优势与概念格形式背景相结合,提出了基于变精度粗糙集的概念格约减算法,同时分析了变精度粗糙集模型中的β值的选取算法、可辨识矩阵属性约简,以及传统算法中存在的问题,并且对传统算法进行了改进.Mao等[29]通过利用变精度粗糙集中的β-上、下近似与概念格中概念相结合,提出了概念格上的变精度粗糙集近似算子,并根据这一近似运算对形式背景中任意不可定义的对象集进行近似,求出与其最接近的概念的外延,并得到了上、下近似概念.

2)与模糊集的结合

Burusco[30]在1994 年提出L-模糊概念,最早将模糊思想引入概念格.定义了基于三角模或蕴涵算子的求导算子,之后Burusco[31]通过迭代求不动点可以得到模糊概念.Ma等[32]提出了一种基于模糊形式概念分析的模糊本体学习方法,该方法意图从领域文档中获取模糊概念和模糊概念关系,并通过模糊形式概念分析,将其添加到源模糊本体转化的模糊概念格中,以完成模糊本体学习.

3概念格的应用

概念格良好的结构特征使其不断飞速发展,已被广泛地应用于知识发现和数据挖掘等领域[2-3,33-34].本文将重点对概念格在实体档案馆、排产管理和车辆运输安全性的应用进行阐述和分析.

3.1　在实体档案馆中的应用

邓君等[35]对实体档案用户行为进行实践调研,以此形成实体档案馆用户行为的单值形式背景,并构建实体档案馆用户行为概念格,提出基于概念格的实体档案用户行为研究方法.该方法通过初步细分档案用户的信息,提出与档案用户相关的关联规则,并挖掘出与档案用户行为相关的规律,为探索新型档案用户服务手段奠定了良好的基础.

3.2　在排产管理中的应用

针对汽车冲压厂生产数据量急剧增加的问题,Zhang等[36]提出了在冲压厂生产信息数据中运用基于概念格的关联规则挖掘技术,并且采用横向拆分与纵向合并的策略构造概念格,将普通概念格转化为量化概念格来生成关联规则.该方法具有较高的挖掘效率,且能有效地寻找数据间隐藏的信息,为企业排产管理提供理论依据.

3.3　在车辆运输安全性中的应用

Yang等[37]为自然语言的处理建立了一种数学工具，即基于Lukasiewicz蕴涵代数的语言真值概念格,将其应用于车辆运输安全性能的语言信息分析系统中,为了考察车辆的运输安全性,作者选择机动灵活性能及安全性能这2个因素作为研究对象,选取“载重量”、“爬坡能力”、“运行速度”、“使用时间”、“能耗量”这几个因素作为研究的属性,根据所给出的影响车辆运输能力的语言真值形式背景,构造出语言真值概念格,从而使得各因素的取值及它们之间的关系较为清晰地以Hasse图呈现出来.

4结束语

通过近几年来概念格在国内外发展的现状统计和分析表明,概念格以其独有的特性不断地赢得众多学者的关注,其应用范围也不断地拓展.从概念格理论研究历史中得出,将其他学科与概念格理论相结合会创造出新思想、新方法.拟阵论始创于1935年,由Whitney[38]首先提出,后又不断地发展[39-40].在查找近些年有关概念格与其他理论的结合应用方面的文献时,发现文献[41]是国内较早研究概念格与拟阵相结合的文章.目前也有学者研究拟阵与人工智能相结合的问题[42-43].今后期望有更多其他学科与概念格理论相结合[44],使概念格理论不断地被充实,发挥出自身的优势,也使其他相关理论得到进步和发展.国内外众多学者应当抓住这一领域,以其为契机,将概念格理论不断的扩充、延伸,使其得到更进一步的发展.

参考文献:

[1]WILLE R. Restructuring lattice theory: An approach based on hierarchies of concepts[C]//RIVAL I. Ordered Sets. Boston: Dordrecht Reidel, 1982: 445-470.

[2]DAVEY B A, PRIESTLEY H A. Introduction to Lattices and Order[M]. Cambridge: Cambridge University Press, 2002.

[3]ZHOU Wan, ZHOU Caixue. Research on the extracting rules of text categorization based on the extended concept lattice model[J]. Computer Engineering and Science, 2009, 24(1): 34-39.

[4]HE Chao, CHEN Xueqi, GUO Jiafeng. Mining hierarchical concept lattice for faceted navigation[J]. Chinese Journal of Computers, 2011, 34(9): 1589-1602.

[5]GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin: Springer, 1999.

[6]LIU Baoxiang, CHEN Huanhuan, LIU Jiebing. Layered construction algorithm and application of rough concept lattice[J]. Computer Science, 2013, 40(4): 214-216.

[7]ZHANG Chunying, WANG Liya. Incremental construction algorithm based on attribute power set for interval concept lattice [J]. Application Research of Computer, 2014, 31(3): 731-734.

[8]CHEN Yongping, YANG Sichun, SU Xin. Attribute reduction of object-oriented concept lattices based on join-irreducible elements[J]. Computer Engineering and Applications, 2014, 50(10): 131-135.

[9]LIU Jianming, LIU Baoxiang. On attribute reduction and its algorithm based on concept lattice isomorphism[J]. Computer Applications and Software, 2014, 31(5): 34-37.

[10]GODIN R. Incremental concept formation algorithm based on Galois (concept) lattices[J]. Computational Intelligence, 1995,11(2): 246-267.

[11]HO T B. An approach to concept formation based on formal concept analysis[J]. IEICE Trans Information and Systems, 1995, E78-D(5): 553-559.

[12]BODA J P. Calcul pratique du treillis de galois d-une correspon-dence[J]. Math Sci Humaines, 1986, 96(2): 31-47.

[13]CHEIN M. Algorithm de recherche des sous-matrices premieres d-une matrice[J].Bull Math Soc Sic Math,1969,13(6):21-25.

[14]GUENOCHE A. Construction du treillis de galois d’une relation binaire[J]. Mathématiques et Sciences Humaines, 1990,109: 41-53.

[15]NOURINE L, RAYNAUD O. A fast algorithm for building lattices[J]. Information Processing Letters, 1999, 71: 199-204.

[16]CARPINETO C, ROMANO G. Galois: an order-theoretic approach to conceptual clustering[Z]. Proceedings of the Tenth Znternational Conference, Amherst, 1993.

[17]HO T B. Incremental conceptual clustering in the frame work of Galois lattice[Z]. Proceeding of Knowledge Discovery and Date Mining, Singapore, 1997.

[18]谢志鹏，刘宗田.概念格的快速进展式构造算法[J].计算机学报，2002，25(5)：490-496.

XIE Zhipeng, LIU Zongtian. A fast incremental algorithm for building concept lattice[J]. Chinese Journal of Computers, 2002, 25(5): 490-496.

[19]胡可云，陆玉昌，石纯一.概念格及其应用进展[J].清华大学学报：自然科学版，2000，40(9)：77-81.

HU Keyun, LU Yuchang, SHI Chunyi. Advances in concept lattice and its application[J]. Journal of Tsinghua University: Science and Technology,2000, 40(9): 77-81.

[20]周建，莫智文.形式背景下概念格的一种建格算法[J].江南大学学报：自然科学版，2013，12(4)：429-431.

ZHOU Jian, MO Zhiwen. Study of establishing lattice algorithms based on the concept lattice under the formal contexts[J].Journal of Jiangnan University:Natural Science Edition, 2013, 12(4): 429-431.

[21]NJIWOUA P, NGUIFO E M. Forwarding the choice of bias LEGAL-F: using feature selection to reduce the complexity of LEGAL[Z]. Proceedings of ENELEARN-97, ILK and INFOLAB, Tiburg, 1997.

[22]WANG Zhihai, HU Keyun, HU Xuegang, et al. General and incremental algorithms of rule extraction based on concept lattice[J]. Chinese Journal of Computers, 1999, 22(1): 66-70.

[23]GUO Xiaobo, ZHAO Shuliang, WANG Changbin, et al. Multi-valued attribute association rules mining based on concept lattice[J]. Computer Science, 2014, 41(3): 267-272.

[24]FU Dongmei,WANG Zhiqiang. Mining algorithm of association rule based on FP-tree and constrained concept lattice and application research[J]. Application Research of Computers, 2014, 31(4): 1013-1016.

[25]ZHANG Wenxiu, WEI Ling, QI Jianjun. Attribute reduction theory and approach to concept lattice[J]. Science in China Series E-Information Science, 2005, 35(6): 628-639.

[26]PAWLAK Z. Rough sets [J]. International Journal of Computer and Information Sciences, 1982, 11: 341-356.

[27]WANG Guoyin, YAO Yiyu, YU Hong. A survey on rough set theory and its application[J]. Chinese Journal of Computers, 2009, 32(7): 1229-1246.

[28]XU Hongsheng, ZHANG Ruiling. Application of improved variable precision rough set in concept lattice construction[J]. Computer Science, 2013, 40(3): 271-275.

[29]MAO Hua, KANG Ran. Variable precision rough set approximations in concept lattice[J]. Journal of Progressive Research in Mathematics, 2015, 2(1): 47-56.

[30]BURUSCO A, FUENTES G R. Concept lattices defined from implication operators[J]. Fuzzy Sets and Systems, 2000, 114: 431-436.

[31]BURUSCO A, FUENTES G R. The study of the L-fuzzy concept lattice[J]. Mathware and Soft Computing, 1994, 3: 209-218.

[32]MA Di, LI Guanyu. A fuzzy ontology learning method based on fuzzy formal concept analysis[J]. Computer Applications and Software, 2014, 31(9): 166-172.

[33]SU Yajuan, ZHANG Tao. A kind of fuzzy concept lattice defined from product implication operators[J]. Computer Engineering and Applications, 2012, 48(19): 42-45.

[34]TILLEY T, COLE R, BECKER P, et al. A survey of formal concept analysis support for software engineering activities [EB/OL]. (2010-10-11)[2015-04-09]. http://citeseerx.ist.pus. edu/viewdoc/download?doi=10.1.1.105.372 6&rep=rep1&type=pdf.

[35]邓君，马晓君，张巨峰,等.基于概念格的实体档案馆用户行为研究[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.

[36]ZHANG Xiao, LONG Wei, LU Bin. Application of association rule based on concept lattice for scheduling manage-ment[J]. Computer Engineering and Applications, 2014, 50(9): 264-270.

[37]YANG Li, WANG Yuhui, XU Yang. Linguistic truth-valued concept lattice based on graded linguistic values chain and its application[J]. Computer Applications, 2012, 32(9): 2523-2526.

[38]WHITNEY H. On the abstract properties of linear dependence[J]. American Journal of Mathematics, 1935, 57: 509-533.

[39]WELSH D J A. Matroid Theory[M]. London: Academic Press, 1976.

[40]OXLEY J. Matroid Theory [M]. New York: Oxford University Press, 2011.

[41]MAO Hua. The relation between matroid and concept lattice[J]. Advances in Mathematics, 2006, 35(3): 361-365.

[42]ZHU W, WANG Shiping. Rough matroids based on relations[J]. Information Sciences, 2013, 232: 241-252.

[43]MAO Hua. Characterization and reduction of concept lattices through matroid theory[J]. Information Sciences, 2014, 281: 338-354.

[44]SINGH P K, KUMAR C A. Bipolar fuzzy graph representation of concept lattice[J]. Information Sciences, 2014, 288: 437-448.

(责任编辑：孟素兰)

Development analysis of concept lattice theory

MAO Hua, KANG Ran

(College of Mathematics and Information Science, Hebei University, Baoding 071002, China)

Abstract:By searching many databases at home and abroad in recent years (2009-2015), we statistically analyze these databases and obtain the current situation of development of concept lattice theory. After that, we also describe some algorithms of building lattices, extract rules and association rules, and attribute reduction of concept lattices. In addition, we introduce some combinations of concept lattice. We also introduce the applications of concept lattice theory, such as in entity archives, production scheduling management and the safety of transportation.

Key words:concept lattice; building lattices; attribute reduction; analyze

通信作者：康然(1988-), 女, 河北保定人，河北大学在读硕士研究生，主要研究概念格理论及应用.

基金项目：国家自然科学基金资助项目(61073121; 61572011; 61202178); 河北省自然科学基金资助项目(A2013201119)

收稿日期：2015-04-19

中图分类号：TP18

文献标志码:A

文章编号：1000-1565(2015)06-0667-06

DOI：10.3969/j.issn.1000-1565.2015.06.018