论文部分内容阅读
当今,社会已经进入了网络信息时代,计算机与网络信息技术的飞速发展使得各个领域的数据和信息急剧增加(信息爆炸),同时人类的参与使数据与信息系统中的不确定性更加显著。如何有效地实现对数据的分析和处理,如何快速地从数据中提取出隐含的知识,长期以来一直是人工智能领域的研究热点。在此背景下诞生的知识发现KDD(Knowledge Discovery in Databases)和数据挖掘DM(Data Mining)给人们提供了一种新的认识数据和理解数据的智能手段。在DM和KDD诸多方法中,粗糙集理论(Rough set)的明显优势在于不需要任何预备的或额外的有关数据信息。而概念格(Concept Lattice),以其完备的结构和坚实的理论基础成为数据挖掘过程中的主要模型之一。由于概念格的完备性原因,使得寻找一种时间复杂度比现有算法优秀很多的概念格构造算法变得几乎不可能,因此如何比较快速地从海量的形式背景中构造概念格仍然是目前形式概念分析领域研究的一个重点和难点。本文首先从方法及应用等方面论述了知识发现和数据挖掘的发展状况,重点介绍了粗糙集理论和形式概念分析理论在KDD中的应用。在粗糙集理论及形式概念分析理论的基础上,阐述二者之间的联系。接着重点讨论了概念格的建格算法。这一章节分为两个部分,前半部分分析了串行建格算法的原理以及一些经典的概念格构造算法,并提出了一种新的基于边缘概念的建格算法。这种算法与其它传统串行算法相比,最大特点在于边缘概念的提出。求出边缘概念以后,将不再依赖形式背景便可以分层构建概念格,并且同时生成概念格所对应的Hasse图。这一章的后半部分主要论述了适合并行计算的并行算法。随着高性能并行计算技术的发展和成熟,利用并行计算存储能力改善算法在时间和空间上的性能为解决概念格构造问题提供了一条新的途径。本文分析经典的ParallelNextClosure算法,并改进了多概念格合并算法。改进的概念格横向合并算法对于除了同类概念以外的其它特殊概念也有相应的处理方法,从而提高了概念格横向合并的效率。文章的最后对并行构造概念格的模型进行了分析和尝试,通过对其性能的分析证明本文所改进的并行概念格横向合并算法是正确而有效的。同时也对未来的工作提出了新的挑战。