东南大学计算机科学与工程学院,江苏,南京,210096
纸质出版:2008
移动端阅览
杨 彬, 徐宝文, 许 蕾. 基于概念内涵最小生成子的伪内涵计算方法[J]. 电子学报, 2008,36(11):2125-2131.
YANG Bin, XU Bao-wen, XU Lei. Generating All Pseudo-Intents with Minimal Generators of Formal Concept[J]. Acta Electronica Sinica, 2008, 36(11): 2125-2131.
伪内涵是形式概念分析理论的一个重要概念
伪内涵问题的研究是当前研究的热点.传统的伪内涵计算方法为了获得形式背景中所有的伪内涵
需要搜索形式背景中所有的非内涵属性集
而属性的组合容易导致搜索空间爆炸.为此
本文从概念内涵生成子的角度
刻画伪内涵的特性
给出伪内涵判定的充要条件;在此基础上
提出计算伪内涵的GPI算法.GPI算法只需对概念内涵的最小生成子进行计算
便可获得形式背景中所有的伪内涵
有助于缩减算法的搜索空间
提高伪内涵计算效率.理论分析和实验结果表明
本文的算法是有效可行的.
Pseudo-intent is one of the significant notions of formal concept analysis.Pseudo-intents of formal contexts have gained interest in recent years
since this notion is helpful for finding minimal representations of implicational theories.In order to obtain all pseudo-intents from a given formal context
the existing approaches need to examine all combinations of attributes
which are not intents of formal concepts.However
the number of attribute combinations can be exponential in the number of attributes
which may easily leads to the explosion of search space.To address this problem
this paper provides characterizations of pseudo-intents from the point of view of minimal generators of concept intents.The necessary and sufficient conditions of pseudo-intents are derived.Based on these results
an algorithm
called GPI
is designed to generate all pseudo-intents from a formal context.The efficiency of the algorithm is analyzed and several optimizations are presented.The algorithm computes pseudo-intents starting from minimal generators of concept intents and is helpful to reduce the search space of non-intents.Thus it improves the computational efficiency of pseudo-intents.Theory analysis and experimental results show the feasibility and effectiveness of the algorithm.
0
浏览量
697
下载量
2
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621