论文部分内容阅读
形式概念分析由Wille教授于1982年提出,其核心结构是形式概念及概念格,该理论已经在知识发现、软件工程及Web服务等领域得到了广泛应用。然而,形式概念分析利用的是二支决策的思想,仅能表达拒绝和接受两种选项。为表达三支决策中的接受、拒绝和不承诺三种抉择,Qi等于2014年将形式概念分析拓广为三支概念分析,其核心结构为三支概念及三支概念格。目前三支概念分析理论还处于起步阶段,如何有效地构建三支概念及三支概念格是该理论顺利发展的关键内容。本文主要研究三支概念及三支概念格的构建算法,设计实现相关的构建算法,为三支概念分析理论提供支撑。首先,分析形式概念串行构建算法Bordat、CbO、InClose、FCbO以及InClose3的性能,借鉴各算法优点,提出三支概念的串行构建算法CbO3C。算法CbO3C通过使用基于部分闭包的正则检测和失效正则检测进行剪枝、使用位操作实现集合运算等技术来提高运行效率、降低内存开销。利用编译开关,自动选择生成三支概念或核心三支概念。论文对多组UCI数据和随机数据进行实验,实验结果表明:算法CbO3C可以有效地计算出给定形式背景的所有三支概念。其次,为了充分利用CPU资源,提高三支概念的构建速度,在分析已有形式概念并行构建算法的基础上,设计出三支概念的并行构建算法PCbO3C。PCbO3C以串行算法CbO3C为基础,借鉴算法PCbO的思想,利用多线程技术并行计算三支概念。其基本思想为:首先串行地计算出第L层的所有三支概念,然后使用P个线程分别调用算法CbO3C,以并行地计算每个L层三支概念的所有亚概念。为了验证算法PCbO3C的效率,在24核CPU环境下对多组数据进行实验,实验结果表明:在运算速度上,算法PCbO3C明显快于CbO3C,当线程数不超过24时,线程数每增加1倍,PCbO3C的速度可平均提高67.05%。最后,为了生成三支概念格的Hasse图,需要确定三支概念间的父子关系。为此,本文给出了两种方法。一种是先使用前文所述算法生成所有三支概念,然后再计算概念间的父子关系,由此设计实现了算法PCbO3CL。另一种是在生成三支概念的同时,确定并记录概念间的父子关系,从而得到了算法Bordat3CL。计算出所有三支概念及其父子关系后,就可以利用已有工具绘制出三支概念格的Hasse图。论文通过对多组随机数据进行实验,分析算法PCbO3CL与Bordat3CL性能,得出PCbO3CL计算效率更高。