基于概念内涵最小生成子的伪内涵计算方法  

Generating All Pseudo-Intents with Minimal Generators of Formal Concept

作　　者：杨彬[1] 徐宝文[1] 许蕾[1] 

机构地区：[1]东南大学计算机科学与工程学院,江苏南京210096

出　　处：《电子学报》2008年第11期2125-2131,共7页Acta Electronica Sinica

基　　金：国家杰出青年科学基金(No.60425206);国家自然科学基金(No.60503033);江苏省自然科学基金(No.BK2006094)

摘　　要：伪内涵是形式概念分析理论的一个重要概念,伪内涵问题的研究是当前研究的热点.传统的伪内涵计算方法为了获得形式背景中所有的伪内涵,需要搜索形式背景中所有的非内涵属性集,而属性的组合容易导致搜索空间爆炸.为此,本文从概念内涵生成子的角度,刻画伪内涵的特性,给出伪内涵判定的充要条件;在此基础上,提出计算伪内涵的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.

关 键 词：形式概念分析 伪内涵 概念内涵 最小生成子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]