基于同义概念和同类概念的概念格并行构造模型

摘要

概念格作为形式概念分析理论中的核心数据结构，在机器学习、知识发现、信息检索、软件工程等领域得到了广泛的应用。在概念格的应用过程中，造格算法具有很重要的地位。概念格所具有的完备性一方面使得概念格的构造不受数据或属性排列次序和构造方法的影响，最终的形式是唯一的，另一方面使得对于适当大小的数据，也将产生庞大的格结构。理论上说，最坏情况下概念的节点个数会以形式背景对象个数和属性个数的指数倍增长。随着数据规模的不断增长，从形式背景构造概念格需要的时间越来越长，存储概念格所需要的空间也越来越大，逐渐成为制约概念格应用的一个重要因素。由于概念格的完备性原因，使得寻找一种时间复杂度比现有算法优很多的概念格构造算法变得几乎不可能，因此，如何较快的从几乎是海量数据的形式背景中构造概念格的仍然是目前形式概念分析领域研究的一个重点和难点。 随着近些年来高性能并行计算技术的成熟和高性能并行计算机费用的降低，以及概念格良好的数学性质和适合批处理等特点，越来越多的学者把目光转向利用高性能并行计算机的计算和存储能力进行并行分布式的概念格构造，但如何合理有效的进行并行分布式计算和存储目前无论从理论还是技术上都有待进一步研究。 本文在目前已有的各种概念格构造算法或模型的基础上，重点对概念格合并的并行模型进行了研究。通过分析概念格合并的数学模型，以及在该模型下外延独立和内涵独立的两个同域概念格合并的并运算，发现如果两个形式概念具有相同的外延或者内涵，将对概念格的合并过程产生良好的影响，进而提出了同类概念和同义概念两个重要概念，并对相应的数学性质进行了研究。基于此，设计、实现了高效的概念格并行构造算法。 实验和算法分析表明，本文提出的模型和算法是有效的，且非常适合于概念格的分布式计算和存储，同时对于那些形式背景经常变动的情况，具有很好的灵活性特点。其中，概念格的合并算法在该类模型中处于关键的位置，其性能的优劣直接影响概念格并行构造的最终性能。 本文的主要贡献如下：(1)从形式概念的角度提出了“同类概念”和“同义概念”这两个概念，并利用同类概念和同义概念的特性，提出基于同类概念和同义概念的概念格合并算法。实验表明本文提出的概念格合并算法在时间上要优于文献中提到的概念格合并算法AUATSTICL和HUMCL。 (2)设计了一种基于概念格并运算的概念格并行构造模型，并对模型的实验结果进行分析，和串行构造概念格的经典算法进行比较。 (3)参与开发了IsoFCA原型系统，在其中实现了本文的全部思想，主要用于对同构生成的概念格进行并行合并以形成完整的概念格。

目录

文摘

英文文摘

关于学位论文独立完成和内容创新的声明及关于学位论文著作权使用授权书

第1章绪论

第2章概念格构造基础

第3章概念格合并的数学模型及其算法

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

第五章并行构造在IsoFCA系统中的应用

结束语

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果