基于约束的模糊概念格构造算法

摘要/Abstract

摘要： 一般的模糊概念格在构造过程中没有考虑用户的需求,用户对模糊概念格节点中一些属性集形成的内涵并不感兴趣。为了增强模糊概念格的针对性,降低模糊概念格构造的时空复杂性,构造满足用户需求的模糊概念格,首先将用户感兴趣的背景知识定义为约束条件,根据用户关心的属性间关系,将约束条件分为3类:单约束、与约束及或约束,并采用谓词公式表示,进而提出了基于约束的模糊概念格(Constrained Fuzzy Concept Lattice,CFCL)构造算法。该算法自底向上构造模糊概念格,利用模糊概念格父子节点内涵的单调关系,采用剪枝技术来减少构造过程中判断模糊概念是否满足约束的次数,提高了模糊概念格的构造效率。实验结果表明,该算法能够有效地减少模糊概念格的存储空间和构格时间。

关键词: 模糊概念格,谓词逻辑,约束,构造算法

Abstract: The general process of constructing fuzzy concept lattice does not take user’s requirement into account.Users sometimes are not interested in all intensions of attribute sets in fuzzy concept lattice node.In order to enhance the pertinence of fuzzy concept lattice,reduce the time and space complexity and construct fuzzy concept lattice which can meet the need of users,first of all,the background knowledge which users are interested was defined as a constraint condition.We divided the constrainst into three categories:single-constraint,and-constraint and or-constraint by the relation among attributes.Then we formalized the constraint by predicate formula.And a construction algorithm based on constraints(Constrained Fuzzy Concept Lattice,CFCL) was presented.The algorithm presents a bottom-up method to compute the fuzzy concept lattice.By making use of the monotone relation between father fuzzy concept’s intent and child fuzzy concept’s intent,this method reduces the judgment operations between fuzzy concepts and the constraints.Thus the efficiency of building the fuzzy concept lattice is improved.Finally,the experiment results verify that the proposed algorithm can reduce the storage space and time of fuzzy concept lattice construction.

Key words: Fuzzy concept lattice,Predicate logic,Constraint,Construction algorithm

崔芳婷,王黎明,张卓. 基于约束的模糊概念格构造算法[J]. 计算机科学, 2015, 42(8): 288-293. https://doi.org/

CUI Fang-ting, WANG Li-ming and ZHANG Zhuo. Construction Algorithm of Fuzzy Concept Lattice Based on Constraints[J]. Computer Science, 2015, 42(8): 288-293. https://doi.org/

参考文献

[1] Ganter B,Wille R.Formal Concept Analysis[M].Berlin,Heidelberg:Springer,1999
[2] 柴玉梅,王春丽,王黎明.基于频繁项集的互补替代关系挖掘算法[J].模式识别与人工智能,2012,25(1):157-165 Chai Yu-mei,Wang Chun-li,Wang Li-ming.An Algorithm for Mining Complement-Alternative Relationship Based on Frequent Itemsets [J].Pattern Recognition and Artificial Intelligence,2012,25(1):157-165
[3] 柴玉梅,张卓,王黎明.基于频繁概念直乘分布的全局闭频繁项集挖掘算法[J].计算机学报,2012,35(5):990-1001 Chai Yu-mei,Zhang Zhuo,Wang Li-ming.An Algorithm for Mining Global Closed Frequent Itemsets Based on Distributed Frequent Concept Direct Product[J].Chinese Journal of Computers,2012,35(5):990-1001
[4] 王黎明,张卓.基于Iceberg概念格并置集成的闭频繁项集挖掘算法[J].计算机研究与发展,2007,44(7):1184-1190 Wang Li-ming,Zhang Zhuo.An Algorithm for Mining Closed Frequent Itemsets Based on Apposition Assembly of Iceberg Concept Lattices [J].Journal of Computer Research and Deve-lopment,2007,44(7):1184-1190
[5] Young P.Software Retrieval by Samples Using Concept Analysis [J].The Journal of Systems and Computer,2000,54(3):179-183
[6] Belohlavek R,Sklenar V.Formal Concept Analysis Constrained by Attribute-Dependency Formulas[C]∥Proc of the 3rd International Conference on ICFCA.Lens,France,2005:176-191
[7] Belohlavek R,Vychodil V.Formal Concept Analysis with Constraints by Closure Operators[C]∥Proc of 14th International Conference on Conceptual Structures(ICCS 2006).Aalborg,Denmark,2006:131-143
[8] Belohlavek R,Vychodil V.Formal concept analysis with background knowledge:Attribute priorities [J].IEEE Transactions on Systems,2009,39(4):399-409
[9] 张继福,张素兰,蒋义勇.约束概念格的代数性质及其知识表示的完备性[J].模式识别与人工智能,2010,23(3):289-299 Zhang Ji-fu,Zhang Su-lan,Jiang Yi-yong.Algebraic Properties of Constrained Concept Lattice and Its Completeness of Know-ledge Representation [J].Pattern Recognition and Artificial Intelligence,2010,23(3):289-299
[10] Belohlavek R.What is a Fuzzy Concept Lattice?[C]∥Proc of the 13th International Conference on Rough Sets,Fuzzy Sets,Data Mining and Granular Computing.Moscow,Russia,2011:19-26
[11] Burusco A,Fuentes-Gonzalez R.The Study of the L-Fuzzy Concept Lattice [J].Mathware & Soft Computer,1994,1(3):209-218
[12] Fan Shi-Qing,Zhang Wen-Xiu,Xu Wei.Fuzzy Inference Based on Fuzzy Concept Lattice [J].Fuzzy Sets and Systems,2006,157(24):3177-3187
[13] 宋笑雪,张文修,李红.变精度对象概念格的构造及其性质[J].计算机科学,2010,37(12):197-214 Song Xiao-xue,Zhang Wen-xiu,Li Hong.Construction and Properties of Variable Threshold Object-oriented Concept Lattices [J].Computer Science,2010,37(12):197-214
[14] Belohlavek R.Fuzzy Galois Connections[J].Mathematical Logic Quarterly,1999,45(4):497-504
[15] Belohlavek R.Algorithms for Fuzzy Concept Lattices[C]∥Proc of the 4th International Conference on Recent Advances in Soft Computing.Nottingham,UK,2002:200-205
[16] Belohlavek R,De Baets B,Outrata J,et al.Computing the Lattice of All Fixpoints of a Fuzzy Closure Operator [J].IEEE Transactions on Fuzzy Systems,2010,18(3):546-557
[17] 张卓,柴玉梅,王黎明,等.模糊形式概念并行构造算法[J].模式识别与人工智能,2013,26(3):260-269 Zhang Zhuo,Chai Yu-mei,Wang Li-ming,et al.A Parallel Algorithm Generating Fuzzy Formal Concepts[J].Pattern Recognition and Artificial Intelligence,2013,26(3):260-269
[18] Belohlavek R,Vychodil V.Reducing The Size of Fuzzy Concept Lattices by Hedges[C]∥The 14th IEEE International Confe-rence on Fuzzy Systems.Reno,Nevada,USA,2005:663-668
[19] Belohlavek R,Vychodil V.Reducing The Size of Fuzzy Concept Lattices by Fuzzy Closure Operators[C]∥ISIS 2006.Tokyo,Japan,2006:309-314

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed