一种基于偏序集直积的增量式概念格构造算法

目前,概念格的构造算法可分为批处理式和增量式两类.已有的增量式算法只适用于单个对象的逐个插入更新的情况,然而,在大多数的数据库中,更新操作往往是同时插入多个对象.为了适应这种情况,基于偏序集的直积运算,提出了一种新的增量式概念格构造算法,这种算法可以一次性地加入一个对象集合,而且在生成概念的同时,能够构造出概念格的Hasse图,从而完全解决了上述问题.最后,用一个实例检验了算法的正确性.     

双序渐进式概念格合并算法

针对传统的概念格合并算法仅为单向的纵向或横向合并,提出一种基于概念内涵、外延升降序的双序渐进式合并算法。按照概念的内涵或外延的升序和降序,从两个方向(由上到下和由下到上)同时进行子概念格的纵向或横向合并。算法分析和示例结果表明,该算法不仅在结构上较好地保留了原有信息,而且在效率上也获得了显著的提高。     

一种新颖的概念格属性约简算法

概念格是知识处理与分析的一个有力的工具,在知识约简方面有着重要的利用。首先给出了概念格中不同类型属性的等价刻画定理,在此基础上得到了一种新颖的概念格属性约简算法,最后通过实例表明了该约简算法的可行性与有效性。     

基于属性的概念格快速渐进式构造算法

提出了一种新的基于属性的概念格快速渐进式构造算法,通过不断地渐增属性来构造概念格。以往的渐进式算法嘟是基于对象的,当数据库属性数目发生变化时,需要重新构造概念格。该算法不但解决了这个问题,而且提供了一种渐进式构造概念格的新方法和思路。给出了该算法的实例,用来说明形式背景在新添加属性后概念格的更新过程。实例与实验表明基于属性的概念格快速渐进式构造算法是快捷有效的。     

同义概念格的纵向合并

由于概念格自身的完备性,构造效率一直是制约其进一步应用的瓶颈。本文从概念格的构造入手,提出了同义概念格的观点,并利用其性质进一步提出了一种纵向合并同义概念格的算（VUSCL算法）。实验表明,随着节点数的增加,该算法与文献[8]中的纵向合并算法相比,其时间性能有明显改善。     

一种粒度概念格模型及其构造方法研究

概念格构造的时间复杂度一直是影响其应用的主要因素。针对这个问题,提出了根据一个近似关系构造形式背景上的覆盖,进而依据用户参数选定一个覆盖分类集形成子形式背景的方法,给出了子形式背景对应的粒度概念格模型及其构造方法,证明了粒度概念格和原概念格之间的关系,通过子概念格的合并可以生成原概念格,通过实例说明了该方法的有效性。     

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

概念格作为形式概念分析理论中的核心数据结构,在机器学习和数据挖掘等领域有着广泛的应用.构造概念格十分重要,针对此引入了概念矩阵思想,提出了基于概念矩阵的概念格生成算法CMCG(Concept-Matrix Based Concepts Generation).该算法从格的顶端节点开始构造,基于概念矩阵,利用属性的秩为每个节点生成它的所有子节点,完成子节点到父节点之间的链接,并生成哈斯图.给出了这种算法的理论依据.最后提供了这一算法的伪码,并通过实验证明了CMCG算法的时间性能优于Lattice算法.     

一种求概念格属性约简的方法

概念格是根据数据集中对象与属性之间的二元关系建立的一种概念层次结构,在知识约简方面有着重要的应用。文章给出了概念格不同类型属性的刻画定理,并在此基础上得到了一种求属性约简的方法。     

基于最大概念的概念格增量构造算法

针对增量概念格构造过程中,节点更新和生成元判定效率较低、边更新阶段的复杂度较高等问题,提出基于最大概念的概念格增量构造算法,通过跟踪与概念格中的概念具有相同真实内涵的最大概念,简化生成元的判断过程。该算法缩小了寻找新生节点父节点时的搜索范围,避免对生成元非必要边的判断,提高构造概念格的速度。复杂度分析结果表明,该算法的时间性能优于其他同类算法。     

基于一一映射的概念格属性约简算法*

首先给出了基于一一映射的概念格不同类型属性的等价刻画定理,在此基础上得到了一种新颖的概念格属性约简算法;最后通过实例表明了该约简算法的可行性与有效性。     

基于形式背景级联运算的关联规则挖掘算法

提出了一种基于形式背景级联运算的关联规则挖掘方法,该方法能够挖掘出隐含在多个形式背景之间的知识。此外,还提出了用“索引链表”来辅助快速地找到所有的频繁结点,从而缩小了结点的搜索范围,降低了概念格挖掘关联规则算法的复杂度。最后,用一个实例检验了给出的各个方法的正确性。     

基于消息传递的概念格并行构造

作为形式概念分析的主要工具，概念格已在知识发现、软件工程等诸多领域取得广泛的应用。但是由于概念格自身的完备性：构造复杂性一直是困扰其进一步发展的一大难题。利用高性能并行计算机的计算与存储能力来构造和存储是解决这一问题的有效途径。首先介绍外延独立的同域概念格相关概念及其合并运算，在此基础上提出了一种基于MPI（Message Passing Interface）消息传递机制的概念格并行构造算法。分析表明，该算法是高效、可行的。     

概念格的对象渐减更新算法

为解决访问控制中的删除某个对象后重新构造概念格耗时的问题,对概念进行了分类,深入研究了概念格中删除对象后各个概念以及边的变化,分析了概念之间及边之间的联系和规则,在此基础上提出一种概念格的对象渐减更新算法.该算法采用渐进式构造方法,不需要重新构造概念格,而且是在原概念格的基础上采用广度优先遍历的顺序对概念格进行调整,进...     

基于抽样的概念层次挖掘算法

本文通过对数据挖掘的几种传统属性归纳算法的分析,发现它们存在以下不足：（1）不能处理不平衡的概念层次;（2）没有考虑实际数据分布对最后的泛化规则的影响。因此,本文提出了基于抽样的概念层次挖掘算法,它先采用抽样方法,对概念层次进行初步调整,然后扫描整个数据文件,利用扫描信息再次调整概念层次,最后通过统计调整后的概念层次的叶子信息就可以得到泛化规则。本算法不仅克服了传统算法的不足,而且具有最优的时间复杂度O（n)和空间复杂度O(c)。     

INCREMENTAL CONCEPT FORMATION ALGORITHMS BASED ON GALOIS (CONCEPT) LATTICES

The Galois (or concept) lattice produced from a binary relation has proved useful for many applications. Building the Galois lattice can be considered a conceptual clustering method because it results in a concept hierarchy. This article presents incremental algorithms for updating the Galois lattice and corresponding graph, resulting in an incremental concept formation method. Different strategies are considered based on a characterization of the modifications implied by such an update. Results of empirical tests are given in order to compare the performance of the incremental algorithms to three other batch algorithms. Surprisingly, when the total time for incremental generation is used, the simplest and less efficient variant of the incremental algorithms outperforms the batch algorithms in most cases. When only the incremental update time is used, the incremental algorithm outperforms all the batch algorithms. Empirical evidence shows that, on the average, the incremental update is done in time proportional to the number of instances previously treated. Although the worst case is exponential, when there is a fixed upper bound on the number of features related to an instance, which is usually the case in practical applications, the worst-case analysis of the algorithm also shows linear growth with respect to the number of instances.     

概念格上规则提取的一般算法与渐进式算法

许多研究表明概念格是数据分析与规则提取的一种有效工具。本文首先提出一种在对象与描述符数目较多、概念聚类具有一定规模条件下,在已建造好的概念格上有效地提取规则的算法。这种方法主要依据格结点的直接泛化来产生相应无冗余规则,然后改进了一种渐进式更新概念格与相应Ｈａｓｓｅ图的算法,并将之应用于渐进式提取规则。目前,这些方法已用于我们所开发的数据库知识发现工具原型系统中。     

基于相干概念覆盖的增量分类规则挖掘

现实应用中的许多信息表都随着时间增量地添加信息，提出了一种适用于此特点的增量概念信息推导方法。首先，介绍了形式概念分析的一些基本定义和概念格结构；然后，介绍了一种较概念格结构有很多优点的新的概念结构：相干概念覆盖结构；接着，提出了一个发现相干概念覆盖的增量算法；最后，利用该增量相干概念覆盖算法进行数据挖掘的重要任务之一的分类规则挖掘。     

基于偏序关系的子概念格判定算法

基于偏序关系给出子概念格的定义和判定定理,描述子概念格的判定算法,提出对概念格中的子概念格进行折叠的思想,最后,通过FCA原型系统验证了算法的有效性,借助Direct3D技术可视化地展示了子概念格的折叠和互操作过程.子概念格的折叠简化了概念格的显示,从而方便用户对格信息的查询.