形式概念分析,也叫概念格理论,是Wille R(德国数学家)于1982年提出的。该理论将概念和概念层次以数学化的形式表达出来,已在多个领域得到了广泛应用,如知识工程、信息检索、软件工程等。Qi等人结合三支决策理论和概念格理论。提出了三支概念分析理论。一方面,三支概念分析理论是经典概念格理论的扩展。三支概念可以表达形式背景中“共同具有”和“共同不具有”这两层含义,与经典概念相比可提供更多,更详细的信息。另一方面,三支概念分析也为三支决策理论提供了一种更为具体的模型。根据三支概念的定义,将属性论域或对象论域分为三部分,然后进行三支决策。概念格理论作为一种数据分析的手段,首先需要根据作为数据集的形式背景构建相应的概念格。三支概念分析理论也是如此。在一般情况下,概念格和三支概念格中概念数量的增长是指数级。这样,建格算法的效率就成为决定概念格理论和三支概念分析理论在实际中能否成功应用的关键。传统非分布式的概念格构建算法一般只能处理规模较小的数据集,不能满足日益发展的大数据应用。本文针对经典及三支概念格,设计实现基于Spark的分布式建格算法。首先本文回顾了形式概念分析和三支概念分析的相关定义,以及一些经典概念格的串行构建算法和分布式构建算法。然后借鉴Cbo算法的基本思想,设计了一种分布式经典概念格构建算法,并在Spark平台上实现。Cbo算法采用的是深度优先的搜索策略,然而在集群计算中递归任务是不容易拆分成若干个任务分布到各个节点中计算,因此Cbo算法中的搜索策略并不适用于分布式算法。为了解决这一问题,本文对Cbo算法进行改造,采用广度优先的搜索策略,将Cbo算法中的递归运算改造为迭代运算以适应分布式计算的框架。采用Cbo算法的基本思想以及本文提出的关于三支概念格的性质,以迭代的方式设计分布式三支概念格构建算法;通过Spark提供的一系列对RDDs的转化(Transformation)操作和行动(Action)操作来生成所有的概念,并完成在计算过程的剪枝工作,最终实现基于Spark的三支概念格构建算法。最后,本文对设计的算法进行了实验分析。针对经典概念格,本文将基于Spark平台的算法与基于Hadoop平台的算法进行比较,实验结果表明其效率得到了一定提升。针对三支概念格,本文以k-均匀背景为基础,将基于Spark平台的算法与串行三支概念格构建算法进行对比实验,实验结果表明分布式算法效率更高。