概念格的分布并行处理及约简构造研究

摘要

自从德国的Wille教授提出了形式概念分析以来，作为形式概念分析的核心数据结构，概念格已经引起了人们的广泛关注，并且已经在知识发现、软件工程、信息检索等诸多领域得到了广泛的应用。其中，概念格的构造是其应用的前提。可是由于概念格自身的完备性，构造概念格的时间、空间复杂度一直是影响形式概念分析应用的主要障碍。研究采用新的方法和手段来构造概念格，就成为概念格研究的主要内容之一。 随着网络技术特别是Internet技术的飞速发展，数据分布式存储与并行处理的需求越来越迫切。针对这些复杂的问题都包含着大量子问题的基本特点，再结合人类已经积累的分析问题与解决问题的方法与经验，可以应用一定的并行算法，将这些复杂问题分为既有相对的相互独立性又有一定联系的若干子问题，然后将这些子问题分别分给若干台处理器，使得这些处理器能够同时地解决这些子问题。在各处理器同时解决这些子问题的过程中，采用一定的策略对这些并行的过程进行控制，协调它们的停止与运行；然后将这些子问题所得到的结果进行整合与处理，得到问题的最终解。通过这样的处理，可以提高解决问题的效率，缩小解决问题的时间。 本文主要就此领域的相关问题展开系列研究，主要工作如下：随着处理的形式背景的逐渐增大，概念格的构造复杂度将呈指数增长。现在已经提出的构造概念格的算法基本上都是针对单个概念格的。采用分而治之的策略是解决这一问题的有效途径之一。我们提出一种对概念格的分布处理算法，在渐进式构造概念格算法(如Godin算法)的基础上，对形式背景进行合理拆分，分别构造出部分概念格，对得到的部分概念格进行合并，提出两种合并的算法。并理论分析证明了构造出概念格的完备性和正确性，实验结果表明这是一种行之有效的概念格构造方法，为降低概念格构造的时间复杂度提供了一种思路。 利用高性能并行计算机的计算与存储能力来构造和存储是有效地解决高复杂性科学问题的根本途径。我们提出一种基于消息传递机制的Godin算法并行化方法，分析其迭代过程中的主要耗时点，对其采用并行处理。并行算法中无法进行结构体的直接发送，我们提出用分治策略的方法，求得结构体数组的长度之后，将其转化为字符类型，分别发送，并将这一思想运用到了并行程序的设计过程中，进一步提高了算法的并行性。该算法和直接用形式背景来渐进式构造概念格的算法相比，其时间复杂度会有显著改善，性能提高30％-40％左右。 降低概念格构造的空间复杂度，是概念格研究的另一个重要目标，可以结合用户兴趣度来实现概念格的约简构造，但是目前用户兴趣度的给定中人为因素很明显。我们提出一种基于信息熵的约简概念格构造算法，把信息论中熵的概念引入到兴趣度的给定中来，用信息熵来衡量不同属性的重要性，这不仅使得属性重要性的度量具有一定的科学性和客观性，而且具有一定的可预知性，适合渐增式构造概念格。信息熵值本身包含随机信息的信息量测量，所以没有必要每次重新度量熵值，为此我们采用间隔一定时间更新的方法，进一步缩短了构造概念格的复杂度。

目录

文摘

英文文摘

第1章引言

第2章概念格模型及其构造

第3章分布式概念格的数学模型及其相应运算

第4章基于MPI的概念格并行处理

第5章概念格的约简构造

第6章结束语

参考文献

致谢

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