一种基于深度优先的概念格并行构造模型

摘要

形式概念分析是一种对数据进行分析的工具，概念格是形式概念分析理论中的核心数据结构。近年来，它已在知识发现、软件工程、机器学习、信息检索等领域得到了广泛的应用。 在概念格的应用过程中，造格算法具有很重要的地位。概念格所具有的完备性一方面使得格的构造不受数据或属性排列次序和构造方法的影响，最终的形式是唯一的，这是其主要优点；但另一方面，正是由于概念格是一种完全格，使得对于适当大小的数据，它所对应的格结构也是非常庞大的。因此，单纯的依靠改进算法本身来大幅度提高格的构造效率已变得几乎不可能。如何较快的从几乎是海量数据的形式背景中构造概念格仍然是目前形式概念分析领域研究的一个重点和难点。 随着近年来高性能并行计算技术的成熟和高性能并行计算机费用的降低，为解决概念格应用中的这一问题提供了一个新的思路，即利用并行计算机的计算与存储能力进行分布式并行造格。 为此，本文在已有的各种概念格构造算法或模型的基础上，重点对概念格的并行构造进行了研究。通过对格的构造过程的分析，发现在插入对象时将其内涵以深度优先的方式从下而上的与原格中节点做交集，根据交的结果进而采取相应的动作；另外，在做交集的过程中，对满足一定条件的节点设置标志位，可以降低新增对象时节点的比较次数，从而降低造格的时间复杂度。在此基础上，设计并实现了一种基于深度优先的概念格渐进式构造算法(简称AICACLBDF)。之后，将该构造算法并行化，得到一个基于深度优先的概念格并行构造模型。 实验证明，本文提出的基于深度优先的概念格构造算法和并行构造模型是有效的，在时间复杂性上优于传统的渐进式造格算法Godin，有效的提高了造格的效率，尤其是当新增对象(新增节点)的内涵与原格特征域的交集(相似率)较小时，算法的优越性更加明显。 本文的主要贡献如下： 1、设计并实现了基于深度优先的概念格渐进式构造算法，对算法进行了性能分析，在实验的基础上，将其与传统的渐进式造格算法Godin算法进行比较。 2、设计了一种基于深度优先的概念格并行构造模型，对该并行构造模型进行性能分析和实验，并将其与串行构造算法Godin进行比较。

目录

文摘

英文文摘

声明

第1章绪论

1.1形式概念分桥的主要内容及应用

1.1.1形式概念分析的来源

1.1.2形式概念分析的主要内容

1.1.3形式概念分析的应用

1.2概念格构造的研究现状

1.3概念格构造所面临的主要问题及解决方法

1.4本文内容组织

第2章形式概念分析的理论基础

2.1概念格模型的数学基础

2.1.1序论中的基本定义

2.1.2格论中的基本定义

2.2形式概念分析的理论基础

2.2.1形式背景

2.2.2概念格

2.2.3 Hasse图

2.3概念格的构造

2.3.1批处理算法(batch algorithm)

2.3.2渐进式构造算法

2.3.3并行算法

第3章基于深度优先的概念格构造算法

3.1算法思想

3.2基于深度优先的概念格构造算法设计及实现

3.3算法示例

3.4算法性能分析

3.5本算法和Godin算法的比较

3.6小结

第4章概念格并行构造模型

4.1引言

4.2算法思想

4.3示例说明

4.4体系结构

4.5性能分析及实验结果

4.6小结

第5章结论

本文工作总结

未来工作展望

致谢

参考文献

作者攻读硕士学位期间发表的文章