1.1 研究背景及意义
概念格（也叫形式概念分析）[1]是由德国数学家 Wille 教授在 1982 年提出，其核心思想是基于形式背景中属性与对象之间的二元关系构建概念以及概念之间偏序关系的过程，它作为一种数据分析和规则提取的强有力工具，已被成功的应用于案例推理[2,3]、最近邻搜索[4]、智能家居[5]、中医临床术语编码[6]、信息检索[7,8]、基因表达[9]等众多数据分析领域[2-13]。随着互联网的飞速发展，人们在互联网上的行为产生了大量的数据，使得形式背景的规模逐渐增大，导致概念格的规模呈指数增加。在实际应用过程中，生成概念格的形式背景会随着时间的推移产生大量的冗余信息，久而久之使得概念格中的无效概念增多，最终导致概念格的规模变得庞大，同时降低知识抽取的效率。因此需要不断的从形式背景中去除这些冗余信息，从而压缩概念格的规模，提高知识提取的速率。目前已经提出了多种概念格的渐减式构造方法，张磊等人[13]提出基于单个属性消减的渐减式维护的新方法，依据概念格中节点的遍历方式不同，提出自底向上和自顶向下两种渐减式算法，能够在原始概念格的基础上同时对概念节点和 Hasse 图进行调整，而不是传统方式下的重新构格，具有良好的时间性能。文献[15]提出基于单个对象消减的渐减式维护的新方法即 DeleteObject 算法，该算法是在原始概念格的基础上减去某些对象的维护算法，其维护过程与文献[13]是互逆算法。文献[16]同样是基于对象的渐减式构造算法称为 FastDeletion 算法，它是对 DeleteObject 算法的删除节点的父子节点之间边更新过程进一步改进得到的，实验结果表明，不管在稀疏还是稠密数据集上，FastDeletion 算法比 DeleteObject 算法时间性能更优越。姜琴等人[17]提出多属性同步消减的维护算法，它可以实现同时删除多个属性得到新概念格，实验表明该算法消减属性个数较多时表现出良好的时间性能。文献[18]同样是多属性渐减式构造，与文献[17]不同的是，它利用剩余属性集 N 决定多个等价类，将需要保留的最大元素和边分别保存到概念集合 D 和边的集合 L 中，未被保留的则自动被删除，该算法大大缩小了对原背景概念的考察范围，当减少多个属性时有较好的时间性能。
.........
1.2 国内外研究现状及分析
对于概念格的应用离不开形式概念或者概念格的构造，因此，概念格的构造成为形式概念分析研究的热点问题。现阶段概念格的构造算法大致可以分成两类：
1）批处理算法是根据形式背景生成所有的形式概念节点，然后建立所有形式概念之间的父子关系，并不考虑形式背景的更新，始终从形式背景重新构格。典型的代表算法有 Ganter 的 NextCloure 算法[19]按照 X 集特征向量的拓扑排序枚举概念格中所有概念节点，该算法最终没有生成 Hasse 图。Bordat 算法[20]从最小上界节点出发，生成该节点的所有子节点，然后对每个子节点重复该过程，其缺点是节点被其父节点生成了多次，消耗了大量的构格时间，Bordat 算法最后生成了 Hasse 图。
2）渐进式算法是依据形式背景的动态变化，在原始概念格基础上作相应的调整得到新概念格，避免从形式背景上重新构造概念格，从而提高了构造格的时间效率。典型代表有 Godin 算法[21]，它是基于对象渐增的概念格构造算法，通过将当前要插入的对象和概念格中的所有形式概念节点求交，根据交集的结果采取不同的方法。实验表明，Godin 算法的速度在某个特定点后比 Bordat 算法以及 NextCloure 算法都要好。文献[22]提出一种基于属性增加的构造算法，该算法利用概念节点的树结构组织可以约束更新节点与产生子格节点的搜索范围，从而有效地减少了算法的执行时间。文献[23]提出了基于属性渐增式的构造算法，即 AddIntent 算法，它基于节点间的直接前驱后继关系，能够快速找到更新节点以及标准产生子节点，明显地提高了概念格的构造效率，被认为是近年来最快的概念格构造算法之一。
..........
2 相关概念与算法
2.1 概念格理论
本节对概念格的基本定义、性质以及图形化的表示方式进行简单的介绍，具体详细的描述参照文献[1]。德国数学家 Wille 教授于 1982 年提出形式概念分析理论(Formal ConceptAnalysis, FCA)，也叫概念格，如今经过了三十多年的发展已经广泛的应用到了信息检索，知识发现等诸多领域。形式概念分析主要从内涵和外延两个方面对概念进行形式化的描述，是一种有效地知识表示与知识发现的形式化工具。实质上概念格的生成过程是一种概念聚类的过程，下面对基本概念进行简要介绍。
.....
2.2 概念格渐减式算法
概念格的构造是一切实际应用的前提，如何快速有效地构造出概念格仍然是当前研究的热点。渐减式算法作为一类重要的算法已得到广泛的研究。渐减式算法是指当形式背景中某个对象或属性被删除时，通过在原始概念格的基础上做调整得到新的概念格，避免重新建格，节约了大量的构造格时间，提高了格的构造效率。张磊团队提出了基于属性[14]和对象[15]消减的渐减式算法，同样地，文献[16]与文献[18]讨论了多属性渐减式构造。其中基于属性消减的 BUAD算法构造思想如下：1）从最大下界节点出发，自底向上遍历每个形式概念节点，判断节点是否为更新节点和删除节点，判断依据为概念节点的内涵与消减属性 m 之间的关系。若是跳到步骤（2），否则，循环继续进行直到所有节点均被访问为止。2）对于更新节点，则将概念节点的内涵减去属性 m，外延保持不变；对于删除节点则直接从概念节点集合 CS ( K )中删除即可，同时删除其父节点和子节点的边，此时还需考虑删除节点的父子节点之间是否存在直接的父子关系，若存在需新增边。概念格在实际应用中，如果形式背景中的属性发生变化需要删除时，利用BUAD 算法可以直接从原始概念格中将消减属性 m 直接删除掉，比重新从新形式背景K 构造格花费的时间要少得多。对于属性消减算法更详细的介绍参考文献[14]。
..............
3 基于二元关系消减的概念格维护算法.....11
3.1 基本概念.....11
3.2 相关理论.... 12
3.3 算法描述.... 17
3.4 算法分析.... 21
3.5 实例分析.... 22
3.6 本章小结.... 24
4 有限内存下基于外存的概念格维护算法....... 25
4.1 基本概念.... 25
4.2 相关理论.... 26
4.3 算法描述.... 29
4.3.1 分块策略.....29
4.3.2 内外存调度策略.......31
4.3.3 具体过程.....32
4.4 算法分析.... 36
4.4.1 I/O 复杂度分析..........36
4.4.2 时间复杂度分析.......36
4.5 实例分析.... 37
4.6 本章小结.... 39
5 实验结果与分析......40
5.1 DelRelation 算法实验......405
5.2 BlockLattice 算法实验.....45
5.3 本章小结.... 53
5 实验结果与分析
5.1 DelRelation 算法实验
实验环境：Win8 操作系统、Java 实验平台以及单处理器四核计算环境，除操作系统之外，无其它程序同时运行。实验目的：测试 DelRelatione 算法的完备性以及运行效率。实验数据集：由 MATLAB 自动生成的 4 组关系密度不同的随机数据集进行运行效率分析以及 3 组 UCI 公共数据集分别为 Leaf、Cloud、Plates Faults 进行完备性验证。具体说明如下：从 UCI 公共数据集上选择以下 3 个数据集，对数据集去除分类属性后分别进行归一化处理，然后小于 0.5 的值设置为 0，大于等于 0.5 的值设置为 1，从而生成了 3 个形式背景。具体地，Leaf 数据集[46]对象数 340，属性数 14，关系密度为 34.1%，Cloud 数据集[47]对象数 1024，属性数 27，关系密度 43.5%，PlatesFaults 数据集[48]对象数 1941，属性数 27，关系密度为 29.8%，其中关系密度又叫做非零项所占的比。数据集 1：由 MATLAB 随机生成，共 15 个属性数，对象数从 10 个依次增加 10 个直至 200 个，关系密度为 30%，一共 20 组形式背景。数据集 2：由 MATLAB 随机生成，共 15 个属性数，对象数从 10 个依次增加 10 个直至 200 个，关系密度为 50%，一共 20 组形式背景。数据集 3：由 MATLAB 随机生成，共 15 个属性数，对象数从 10 个依次增加 10 个直至 200 个，关系密度为 60%，一共 20 组形式背景。数据集 4：由 MATLAB 随机生成，共 25 个对象数，属性数从 25 个依次增加 25 个直至 500 个，关系密度为 30%，一共 20 组形式背景。
结论
概念格作为形式概念分析的数据结构，已被广泛的应用于数据分析和知识发现等诸多领域。概念格的应用离不开概念格的构造，因此，如何快速有效地构造概念格是当前研究的热点问题之一。随着形式背景中大量冗余信息的出现，导致概念格中无效概念增多，使得概念格在实际应用过程中，概念格的规模变得庞大，从而降低知识提取的效率。目前对于形式背景中冗余信息的删除主要集中于对象或属性粒度的删除，相反，对于对象与属性之间冗余二元关系粒度的删除工作研究很少，虽然二元关系的删除可以通过对象和属性粒度的渐增式算法和渐减
