Incomplete information and concept lattices

We present a mathematical model of sets with incomplete information about identity of elements and the membership relation. The model is based on L-valued sets where L is a complete atomic Boolean algebra. We present general foundations of the theory with emphasis on partially ordered sets and complete lattices. As an application, we show a method for constructing structures that represent the concept lattice of an incomplete binary dataset.     

粗糙本体构建的格-树转化方法

粗糙本体是处理不精确性信息的一种基础性工具,其存在形式是由粗糙概念和粗糙关系构成的树形结构。粗糙本体的具体形式因为参与构建的领域专家的不同而呈现多样性,然而同样也是由粗糙概念和粗糙关系构成的粗糙概念格却具有结构上的惟一性。粗糙本体的构建因而可以利用格和树的组成与结构的相似性,构建粗糙概念格,转化生成粗糙本体。探讨了格-树转化方法的实现步骤：构建粗糙概念格;聚类粗糙概念格中的粗糙概念生成粗糙概念树;转化粗糙概念树为粗糙本体。构建实例阐释了格-树转换方法的具体应用。     

基于属性的概念格渐进式生成算法

提出了一种新的基于属性的渐进式概念格生成算法 ,通过不断地渐增属性来构造概念格 .该算法不仅为概念格的构造提供了一种新的方法 ,还解决了在已构造好概念格的前提下 ,增加属性所带来的概念格更新问题 .给出了算法的实现方法 ,并结合实例说明了概念格的更新过程 .试验表明 ,在通常情况下 ,基于属性的渐进式概念格生成算法的性能往往更优越     

区间概念格的纵向合并算法

为解决直接对不同形式背景的数据构建区间概念格后分别抽取关联规则会存在规则缺失的实际问题,必须首先对不同的区间概念格进行合并.为提高格结构的生成与合并效率,首先对区间概念格的渐进式生成算法进行改进,将概念分为存在概念、冗余概念和空概念,分别以结构体的形式存储;进一步,分析区间概念格中外延和内涵之间的二元关系,给出了区间概念格纵向合并的充分条件——区间概念格的一致性;讨论了内涵一致的概念在合并后分为六种情况,并给出相应的判定定理;应用广度优先原则,通过对原区间概念格节点内涵的类型判定及不同的处理方法,设计了一种区间概念格的纵向合并算法.最后,通过实例验证了算法的有效性和高效性.     

多维概念格与关联规则发现

在引用多维数据序列对概念内涵进行不同维度的描述的基础上,提出了多维概念格的形式化定义及其构造方法;并给出了基于多维概念格的关联规则提取方法,该方法通过发现最大频繁多维数据序列研究不同维度属性之间的依赖关系。实例表明,多维概念格利于发现内容更丰富的有用信息。     

一种新的概念格并行构造算法

概念格作为形式概念分析理论中的核心数据结构,在数据挖掘和知识发现、人工智能、信息检索、粗糙集[1]等领域得到了广泛的应用。概念格的构造在其应用过程中是一个主要问题。提出了一种基于闭包系统划分的概念格并行构造算法——Para_Prun算法,它将概念集合看作初始闭包系统,引入了子闭包系统的有效性判断,迭代生成相互独立的多个子闭包系统,然后在每个子闭包系统中独立生成概念,有效地提高了概念的求解速度。最后用实验证明了算法的正确性和有效性。     

一种近似概念格及其在知识发现中的应用研究*

针对经典概念格基于完备形式背景,在缺值形式背景下不能很好的获取关联规则知识的问题,在偏小近似形式背景的基础上,提出了一种τ-近似概念格来解决信息不完备背景下的知识发现问题,利用它能够获取精度和可信度较高的关联规则知识。文章对τ-近似概念格的构建及其关联规则提取过程进行了详细描述,并将其与偏小近似概念格和偏大近似概念格这两种解决策略进行了案例分析对比,验证了它的可行性和有效性。     

Structure identification of Boolean relations and plain bases for co-clones

We give a quadratic algorithm for the following structure identification problem: given a Boolean relation R and a finite set S of Boolean relations, can the relation R be expressed as a conjunctive query over the relations in the set S? Our algorithm is derived by first introducing the concept of a plain basis for a co-clone and then identifying natural plain bases for every co-clone in Post's lattice. In the process, we also give a quadratic algorithm for the problem of finding the smallest co-clone containing a Boolean relation.     

基于负载均衡的模糊概念并行构造算法

提高模糊概念格直接构造效率是形式概念分析领域的主要问题之一,而当前基于模糊伽罗瓦联系的闭包运算仍是构造模糊概念的主要计算负荷,为此,提出一种基于负载均衡的并行构造模糊概念算法.该算法使用树状结构组织,遍历由自然数区间简化的搜索空间,逐级并行产生模糊概念、缩减搜索区间,并通过重新划分子搜索空间,实现各个计算节点负载均衡.实验结果表明,所提出的算法在稀疏数据集上表现优秀,能够有效地提高模糊概念构造效率.     

形式背景的蕴涵规则提取算法

对形式概念分析中如何从概念格提取出形式背景的完备的无冗余的蕴涵规则集进行了研究,从数学理论上证明了通过求出的概念格中的每个概念的真内涵缩减集可以得到形式背景的完备的蕴涵规则集,提出了如何再去除其中的冗余蕴涵得到形式背景的完备的无冗余的蕴涵集合的方法并从数学理论上证明了该方法的正确性,给出了一个从概念格得到形式背景的完备的无冗余的蕴涵规则集的算法。     

模糊概念因子格的子格构造算法

为了完善因子格的构造,提出了一种基于模糊伽罗瓦联系的模糊概念因子格的子格算法(Factor Lattice Algorithm算法)。该算法依据已给出的模糊概念因子格的上下界限,采用批处理的方式自顶向下根据模糊下邻生成因子,计算出模糊概念节点的直接下邻集合,将模糊概念格进行局部构建,逐步完成局部完备模糊概念因子格的构造得到完备的模糊概念格的子格。并从理论分析和实验结果证明此算法构造得到的模糊概念因子格具备了完备性。     

基于矩阵秩的概念格生成算法

形式概念分析的核心是概念格,它在本质上描述了对象和属性之间的联系,表明了概念之间的泛化和例化关系。利用矩阵行秩的概念及概念格上的二元运算提出了一种基于矩阵秩的概念格生成算法,实例表明该算法行之有效。     

基于同义概念的概念格纵向合并算法

在FCA中,如何提高概念格构造算法的效率一直是研究的重点之一。将形式背景进行分解后造格是解决这一问题的有效途径,其中概念格的合并算法是关键。提出同义概念的观点,在格的合并算法中引入了概念格的线性索引结构,通过寻找同域概念格之间的同义概念,根据父概念-子概念的关系实现对其所有父节点的快速更新。实验表明,该算法和文献中的同域概念格纵向合并算法相比,其时间性能有明显改善。     

FUZZY LABELS,IMPRECISION AND CONTEXTUAL DEPENDENCY Comments on Milan Zelený's “Cognitive Equilibrium: a Knowledge-based Theory of Fuzziness and Fuzzy Sets”

Formal concept analysis is a method of exploratory data analysis that aims at the extraction of natural clusters from object-attribute data tables. The clusters, called formal concepts, are naturally interpreted as human-perceived concepts in a traditional sense and can be partially ordered by a subconcept-superconcept hierarchy. The hierarchical structure of formal concepts (so-called concept lattice) represents a structured information obtained automatically from the input data table. The present paper focuses on the analysis of input data with a predefined hierarchy on attributes thus extending the basic approach of formal concept analysis. The motivation of the present approach derives from the fact that very often, people (consciously or unconsciously) attach various importance to attributes which is then reflected in the conceptual classification based on these attributes. We define the notion of a formal concept respecting the attribute hierarchy. Formal concepts which do not respect the hierarchy are considered not relevant. Elimination of the non-relevant concepts leads to a reduced set of extracted concepts making the discovered structure of hidden concepts more comprehensible. We present basic formal results on our approach as well as illustrating examples.     

基于概念格的数据挖掘方法在库存管理中的应用*

库存管理是物流系统优化的一个重要内容,利用概念格的数据挖掘方法来实现多目标优化过程中,给出了库存模型向概念格模型转换的方法,提出了一种具体的概念格的渐进式构造算法;对于概念格的数据挖掘方法,具体定义了概念格中的关联规则,并提取了库存模型中的隐藏知识,进而为实现库存模型的多目标优化提供了决策支持。     

容差近似空间的广义概念格模型研究

在粗糙集合理论中,近似空间概念格之间存在着有趣的对应关系,利用概念格研究知识的约简和发现。更直观和更有效,但已有的概念格模型是基于近似空间的等价类划分的。等价类划分过于苛刻,扩展的基于容差关系的近似空间具有更广泛的意义,但目前未见有相应的格模型被提出。该文提出了容差近似空间的一种格模型,称为广义概念格,给出了定义,描述了建立方法和由它产生规则的原则,讨论了空间复杂性问题,并且与其它相近方法做了比较     

基于形式概念分析理论的完全格存储模型

完全格的存储是一个有实际应用价值的关键问题。在利用矩阵存储完全格时,识别完全格中的不可约元;分别对上确界不可约元和下确界不可约元用对象标签和属性标签进行标注,使得对象标签和属性标签分别对应矩阵的行和列;根据不可约元之间的关系确定矩阵中元素的值。与采用邻接矩阵存储完全格相比,该方法只存储不可约元的相关信息,能够提高存储的效率。     

概念格与粗糙集的关系研究

概念格理论和粗糙集理论是两种不同的知识表示与知识发现的工具,都已被成功应用于许多领域.粗糙集理论的数据表现方式是信息系统,其研究基础是对象之间的等价关系;概念格理论的数据表现方式是形式背景,其研究基础是一种有序的层次结构--概念格.本文讨论了概念格理论与粗糙集理论之间的基本联系;重点分析了形式概念与等价类之间、概念格与分划之间的关系;证明了概念格与分划之间可以相互转换,给出了转换算法,并用例子加以说明.     

增量式广义概念格结构的生成算法研究与实现

介绍分析了概念格的研究现状,给出了基于规则的广义概念格的基本定义.通过构建树结构,缩小产生子格节点的范围,产生增量式广义概念格算法.最后,通过实例验证了所提出的算法的时空有效性,并给出了对几种概念格的生成算法有效性的比较结果.