（应用数学专业论文）一种基于深度优先的概念格并行构造模型.pdf

河南大学研究生硕士学位论文第1 页 摘要 形式概念分析是一种对数据进行分析的工具，概念格是形式概念分析理 论中的核心数据结构。近年来，它已在知识发现、软件工程、机器学习、信 息检索等领域得到了广泛的应用。 在概念格的应用过程中，造格算法具有很重要的地位。概念格所具有的 完备性一方面使得格的构造不受数据或属性排列次序和构造方法的影响，最 终的形式是唯一的，这是其主要优点；但另一方面，正是由于概念格是一种 完全格，使得对于适当大小的数据，它所对应的格结构也是非常庞大的。因 此，单纯的依靠改进算法本身来大幅度提高格的构造效率已变得几乎不可 能。如何较快的从几乎是海量数据的形式背景中构造概念格仍然是目前形式 概念分析领域研究的一个重点和难点。 随着近年来高性能并行计算技术的成熟和高性能并行计算机费用的降 低，为解决概念格应用中的这一问题提供了一个新的思路，即利用并行计算 机的计算与存储能力进行分布式并行造格。 为此，本文在已有的各种概念格构造算法或模型的基础上，重点对概念 格的并行构造进行了研究。通过对格的构造过程的分析，发现在插入对象时 将其内涵以深度优先的方式从下而上的与原格中节点做交集，根据交的结果 进而采取相应的动作；另外，在做交集的过程中，对满足一定条件的节点设 置标志位，可以降低新增对象时节点的比较次数，从而降低造格的时间复杂 度。在此基础上，设计并实现了一种基于深度优先的概念格渐进式构造算法 f 简称a i c a c l b d f ) 。之后，将该构造算法并行化，得到一个基于深度优先 的概念格并行构造模型。 实验证明，本文提出的基于深度优先的概念格构造算法和并行构造模型 是有效的，在时间复杂性上优于传统的渐进式造格算法g o d i n ，有效的提高 了造格的效率，尤其是当新增对象( 新增节点) 的内涵与原格特征域的交集 ( 相似率) 较小时，算法的优越性更加明显。 本文的主要贡献如下： 1 、设计并实现了基于深度优先的概念格渐进式构造算法，对算法进行 了性能分析，在实验的基础上，将其与传统的渐进式造格算法g o d i n 算法进 行比较。 2 、设计了一种基于深度优先的概念格并行构造模型，对该并行构造模 型进行性能分析和实验，并将其与串行构造算法g o d i n 进行比较。 第1 i 页河南大学研究生硕士学位论文 关键词：概念格：形式概念分析；深度优先；并行构造 河南大学研究生硕士学位论文第1 i i 页 a b s t r a c t f o r m a lc o n c e p ta n a i y s i si sat o o lw h i c hc a na 鹅l y z 9d 4 t a t h e c q n c e p t l a t t i c ei sac o r e ( i a t as t r u c t u r eo fi t i nr e c e n ty e a r s ，c o n c e p tl a t t i c eh a sb e e n w i d e l ya p p l i e dt om a n yf i e l d ss u c ha sm a c h i n e1 e a r n i n g ，k n o w l e d g ed i s c o v e r y ， i n f o r m a t i o nr e t r i e v a la n ds o f t w a r ee n g i n e e r i n g i nt h ea p p l i c a t i o no fc o n c e p tl a t t i c e ，t h el a t t i c ec o n s t r u c t i o na l g o r i t h mp l a y s av e r yi m p o r t a n tr o l e t h ec o m p l e t e n e s so fc o n c e p tl a t t i c eo nt h eo n eh a n d i n s u r e st h eu n i q u e n e s so ft h en n a lr e s u l t sw h i c hi s n ti n f l u e n c e db yt h eo r d e ro f d a t ao ra t t r i b u t e sa n dt h ec o n s t r u c t i o na l g o r i t h m s ，a n do nt h eo t h e rh a n d ，i tw i l l m a k ea l a r g e l a t t i c ee v e nf r o mas m a l ls e to fo r i g i n a ld a t a b e c a u s eo f c o m p l e t e n e s so fc o n c e p tl a t t i c e ，t h es c a l eo fl a t t i c ew i l lm a k ea ne x p o n e n t i a l i n c r e a s ea st h e g r o w t ho fo b j e c t sa n da t t r i b u t e so ff o r m a lc o n t e x t s o ，i t i s i m p o s s i b l et of i n da nc o n s t r u c t i o na l g o r i t h mw h i c hi sb e t t e rt h a ne x i s t i n gi nt h e t i m ec o m p l e x i t y t h u s ，h o wt oc o n s t r u c tai a t t i c ee f f i c i e n t l yf r o ma l a r g ec o n t e x t i ss t i uaf o c u so ft h er e s e a r c ho nf c a w i t ht h em a t u r i n go fp a r a l l e lc o m p u t i n gt e c h n o l o g ya n dt h er e d u c i n gc o s t o fh i g h p e r f o r m a n c ep a r r a l i e lc o m p u t e r ，i to f f e r san e wt h i n k i n gt os o l v et h i s p r o b l e m t h a ti su s i n gc o m p u t e i n ta n ds t o r i n ga b i l i t yo fp a r a l l e lc o m p u t e rt o b u i l dc o n c e p t1 a t t i c e s o ，b a s e do nt h ek n o w ne x i s t e n c ec u r r e n t l yo fc o n s t r u c t i o na l o g r i t h m sa n d m o d e l s ，w ee m p h a s i z e st h er e s e a r c hw o r ko fp a r a l l e lc o n s t r u c t i o no f1 a t t i c e b y a n a l y z i n gt h ec o n s t r u c t i o np r o c e s so f1 a t t i c e ，w ef l n dt h a t ，t h ei n t e n to fn e w o b je c tm a k e si n t e r m i n g l ew i t ha l ln o d e so fo r i g i n a l l yl a t t i c eb o t t o m - u pw h e n i n s e r t i n go b j e c t e s t a b l i s h m e n tm a r ka c c o r d i n gt ot h er e s u l to fi n t e r m i n g l ea n d t h e nd o i n gc o r r e s p o n d i n go p e r a t i o n ，w h i c hc a nr e d u c t i o nn u m b e ro fc o n l p a r i n g w h i c hi sb e t w e e nt h ei n t e n to ft h en e wo b j e c ta n dt h en o d e so ft h eo “g i n a l l y l a t t i c e t h e nt h et i m ec o m p l e x i t yi sr e d u c t e d ，t o o o nt h i sb a s i s ，w ed e s i g na n d i m p l e m e n tai n c r e m e n t a lc o n s t r u c t i o na l g o r i t h m so fc o n c e p tl a t t i c eb a s e do n d e p t hf i r s t ( a i c a c l b d f ) f i n a l l y ，w ea p p l i c a t et h i sc o n s t r u c t i o na l g o r i t h m si n t h ep a r a l l e l i n g t h e nw ec a ng e tam o d e lo fp a r a l l e l i n gc o n s t r u c t i o no fc o n c e p t 1 a t t i c eb a s e do nd e p t hf i r s t t h ee x p e r i m e n t sp r o v e dt h a tt h ea i c a c l b d fa n dt h ep a r a l l e lb u i l d i n ga r e 第1 v 页河南大学研究生硕士学位论文 e f 佗c t i v e t h e yp e r f o r mb e t t e rt h a ng o d i nw h i c hi sat r a d i t i o n a li n c r e m e n t a l c o n s t r u c t i o na l g o r i t h m so nt i m ea n ds p a c ec o m p l e x i t y ，a n di t i m p r o v e se 艏c i e n c y o fc o n s t r u c t i o n1 a t t i c e s e s p e c i a l l y ，s u p e r i o r i t yo ft h ea l g o r i t h m si sm o r eo b v i o u s w h e nt h ei n t e r s e c t i o nb e t w e e nt h ei n t e n to fn e wo b j e c t a n da t t r i b u t er e g i o no f o r i g i n a l l yl a t t i c ei ss m a l l e r c o n t r j b u t i o n sa sf 0 1 l o w s ： 1 ) w ed e s i g na n di m p l e m e n tai n c r e m e n t a lc o n s t r u c t i o na l g o r i t h m so f c o n c e p t1 a t t i c eb a s e do nd e p t h 丘r s t ( a i c a c l b d f ) a n a l y s i sp e r f o r m a n c eo ft h e a l g o r i t h m i ne x p e r i m e n t sf o u n d a t i o n ，w ec o m p a r et h ea l g o r i t h m sw i t hg o d i n w h i c hi sat r a d i t i o n a li n c r e m e n t a lc o n s t r u c t i o na l g o r i t h m s 2 ) w ed e s i g nam o d e lo fp a r a l l e l i n gc o n s t r u c t i o no fc o n c e p tl a t t i c eb a s e do n d e p t hf i r s ta n da n a l y s i st h ee x p e r i m e n t a lr e s u l t so ft h i sm o d e l t h e nw ec o m p a r e t h ea l g o r i t h m sw i t hg o d i n k e yw o r d s ：c o n c e p tl a t t i c e ；f o r m a lc o n c e p ta n a l y s i s ；d e p t hf i r s t ；p a r a l l e l b u i l d i n gl a t t i c e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的，：同荸瓣毒研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意，7 ，；、j ，、。， 学笆事莓0 之学售塞赫主：1 2 1 鸯兰国超 、，j | | 一，j 。j ? j j ”7 j 鬣t itt i ? o ，7 。i ，r 一7 j ，j j | ? 罨| 。露移砖| 。篷j 露慨文毒j 弋，。t 晾 荭；鑫爹；豢荔；j 囊囊；。i - j 甏 銎，关于掌位论文著作权使用授权书j 荔 ：乞一”一| | 麓囊j 鬈麓，勃t 。汐。- j 。+ i 复 本人经河南大学审核批准援系颈砖黟仁。作为学位论文的作者，本人完全 了解并同意河南大学有关保留7 0 j 蝴攀撑潞囊，韵要求，即河痢大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学住论文( 纸质文 本和电子文本) 以供公，焱捡索、鲞皤i 。；誉人投枳河南犬学出于宣扬、展览学校 学术发展和进行学术交流等曰妁t ：可璐恭取影印、缩印、扫描和拷贝等复制手 段保存、汇编学住论文( 纸质文本和电子文本) 。 ( 涉覆保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名： 崴! 坌堡乏 0 学位论文指导教师鍪名： 2 0 “年舌月f o 日 河南大学研究生硕士学位论文第1 页 第1 章绪论 概念是人类认识客观世界及其规律性的重要手段，在哲学中，概念被理 解为由外延和内涵两个部分所组成的思想单元。基于对概念的这一哲学理 解，德国的w i l l e r 【1 j 教授提出了形式概念分析( f o r m a lc o n c e p ta n a l y s i s ) ， 用于概念的发现、排序和显示。在形式概念分析中，概念的外延被理解为属 于这个概念的所有对象的集合，而内涵则被认为是所有这些对象共有的特征 ( 或属性) 集，这实现了对概念的哲学理解的形式化。所有的概念连同它们 之间的泛化例化关系构成了一个概念格。概念格是形式概念分析【2 】理论中的 核心数据结构，它本质上描述了对象和特征之间的联系，表明了概念之间的 泛化与例化关系，其相应的h a s s e 图则实现了对数据的可视化。作为序论和 格论与实际应用结合的产物，概念格一直以来被认为是进行数据分析的有力 工具，对概念格模型的研究具有很重要的理论意义【5 】【引。近年来，概念格获 得了飞速发展，它已经成为进行数据分析的有力工具。 本章主要介绍了形式概念分析理论的来源、主要内容和应用，以及形式 概念分析的研究现状和所面临的主要问题及其解决方法，即针对如何较快的 从几乎是海量数据的形式背景中构造概念格这一问题，采取一种基于深度优 先的并行化构造方法。最后介绍了本文的内容组织安排。 1 1 形式概念分析的主要内容及应用 1 1 1 形式概念分析的来源 概念是人类进行思维的最基本的单位，是用来组成诸如判断、结论等更 为复杂的思想的基础，是人类进行知识表述的一种有效手段，它是一个哲学 的范畴。对概念的这种理解源于古希腊哲学，发展于十七世纪的近代学院派， 进一步发展成德国标准，最终成为了世界标准【3 】。在知识表示、知识管理、 机器学习、专家系统等不同的领域，研究者们从不同的角度和观点来分析概 念，形成了对概念的不同形式化描述方法。 形式概念分析( f o r m a lc o n c e p ta n a l y s i s ) 大约诞生于二十世纪八十年 代，当时位于德国的d a r m s t a d t 研究小组开始系统的研究和发展一种基于格理 论的应用软件。形式概念分析的首次描述是在19 8 1 年关于有序集合的b a n f f 第2 页河南大学研究生硕士学位论文 会议的专题演讲上，从此以后，数以百计的相关论文开始出版和发表。形式 概念分析是一种对数据进行分析的工具和方法，特别是可以对给定的数据进 行调查或处理，从而发现隐藏在数据背后的许多重要信息【4 】。而数据应该是 从人类有意义的、可以理解的思维单位一一概念中抽取而形成的形式化单 元。形式化表明所处理的数据是形式化的数学实体，不必和人类思维中的概 念完全相同，它同时也指出形式概念分析处理的基本数据形式是形式背景， 形式背景是人类背景知识中的一小部分。 许多应用数学领域的问题需要直接借助于格理论来实现其最终的应用。 而从一个二维表中来构造完全的格结构已经在b i r k h o f f f 拘格理论( 1 a t t i c e t h e o r y ) 【7 j 的第一版中有了解释和说明。但是由于新的应用目的和发展的需 要，需要对b r i k h o f f 的格理论做进一步的扩展和更深入的研究。即使不考虑 实际的应用，形式概念分析的提出也引起了研究者的很大兴趣，由此形式概 念分析从应用的角度开始走向理论的形式化研究。 1 1 2 形式概念分析的主要内容 基于b r i k h o 锨寸格理论的贡献，德国的w i l l l e 【3 】教授在19 8 2 年作为一种数 学理论首先引入了概念格( c o n c e p tl a t t i c e ) ，奠定了形式概念分析的理论基础， 将哲学的概念进行数学化的描述，实现了概念的一种形式化描述方法。概念 格是形式概念分析理论的核心数据结构，被认为是知识发现和数据分析的有 力的数学工具。 对形式概念分析理论的研究主要包括以下几个方面的内容： 一、基础理论的研究。研究概念的形式化描述和定义、定理、特征等， 是形式概念分析的理论基础，目前仍有研究者从事这方面的工作。 二、概念格构造。主要关注概念格快速且有效的构造，目前国内外已经 提供了多种概念格的快速构造算法，概念格的构造在形式概念分析中占有十 分重要的地位，是概念格理论实践和概念格应用的基础，本文的主要工作就 是研究格的构造问题。 三、概念格表示。主要研究如何有效地显示概念格的结构，概念格通过 h a s s e 图生动和简洁地体现了这些概念之间的泛化和特化关系，但终归不太 直观和生动。概念格的可视化给人们提供了直观的分析与观察知识单元内在 关系的方法。目前国外已经有不少相关方面的研究，但国内相关的研究还很 少。概念格及其可视化研究【4 】通过对各种自动布局方式特点的分析，提 出了概念格的三维自动布局策略，对三维空间中的层次布局与层内节点自动 布局问题进行探讨并加以实现，较好地解决了二维布局中格节点横向过度扩 河南大学研究生硕士学位论文第3 页 张和线段交叉的问题。 四、概念格的应用。主要研究基于概念格的知识表示、规则发现等各种 问题，将概念格应用于知识发现、软件工程和信息检索等领域。 1 1 3 形式概念分析的应用 作为形式概念分析理论中的核心数据结构，概念格被认为是进行数据分 析的有力工具。作为序论和格论与实际应用相结合的产物，对概念格模型的 研究具有重要的理论意义。目前，概念格已经在知识发现、机器学习、软件 工程、信息检索等诸多领域得到了一定的应用。以下做简单介绍。 一、知识发现 形式概念分析以概念格的形式使数据有机地组织起来，相应的h a s s e 图 实现了对数据的可视化，生动简洁的体现了这些概念之间的泛化与例化关 系，因此，概念格被认为是进行数据分析、知识发现和规则提取的有力工具。 目前有不少研究工作探讨了从格节点和概念格的层次结构中提取规则的问 题。试验研究表明，基于概念格的各种规则提取系统是有效的，形式概念分 析非常适合发现规则型知识。以下简介有关文献中的基于格结构的规则提取 及相关系统。 已知的一些基于概念格的分类学习系统主要有：s a h a m i 开发的 r u l e a r n e r 系统【1 3 1 和n i i w o u a 等设计的l e g a l e 系统【1 4 】【15 1 。g o d i n 等 在文献f 16 中提出了从概念格中提取出蕴涵规则的算法。m i s s a o u i 等【1 7 】对文 献 16 】进行了扩展，提出了从概念格中提取近似规则( 又称为概率蕴涵规则) 的算法。p a s q u i e r 等在文献 1 8 】中以已发现的所有频繁项集作为基础，提出 了用于提取确定性关联规则的d u q u e n n e g u i g u e 基，以及用于近似关联规则 的适当基( p r o p e rb a s i s ) 和结构基( s t r u c t u 豫lb a s i s ) 。h otb 研究了基于概念格 的概念聚类方法，并实现了一些学习系统，包括o s h a m l l9 j 和 i n c o s h a m 【2 0 1 ，使用了一种灵活的匹配过程( 组合了逻辑的、门限的和最 近邻的条件) 来允许系统改进它自身的推理性能，从而可以对未知的实例进 行灵活的预测。 在文献 2 1 】中，w i l l e 引入多背景( m u l t i c o n t e x t ) 这个概念，并给出了不同 形式背景之间的四种不同的操作。以w i l l e 所提出的多背景为理论依据，文献 2 4 1 2 5 1 研究了在概念格框架结构下结构化( 复杂) 对象中的概念学习和规 则提取。l i q u i e r e 等在文献 2 4 中研究了概念格在由标号图( 1 a b e l e dg r a p h ) 描 述的实例中的学习。文献 2 5 研究了由标号的、递归的树所描述的数据和数 据类，定义了一种数据描述的方法一通用项( g e n t e r m ) 、以及g e n t e r m 之间的 第4 页河南大学研究生硕士学位论文 泛化关系，并且说明了在对象集和通用项之间存在一个g a l o i s 联接，从而可 以应用g a l o i s 格的聚类方法。 概念格还可用于知识的表示和处理，如w i l l e 在文献【2 8 中将概念图和形 式概念分析结合起来，从而得到了对初等逻辑的一种形式化。 二、机器学习 在没有领域先验知识的条件下，不确定知识的获取是机器学习研究中的 一个难题文献【3 7 】利用决策表和决策规则的不确定性，通过分析决策表、 决策规则及概念格的知识表示形式，发现这3 种知识表示形式中知识不确定 性之间的关系，进而提出基于概念格的数据驱动不确定知识获取算法 三、软件工程 在软件工程领域，概念格可以从类库的规范说明上构造，从而对类库结 构的可视化以及类库的重构和优化提供支持。形势概念分析为再工程、软件 重用、面向对象程序设计等领域中某些问题的解决提供了理论支持，并已经 取得了一系列的应用成果。 c o r b e t t 和b u r r o w 提出使用概念格表示建筑早期设计软件支持环 境( s e e d ) 中的状态图【6 1 1 。文献 6 2 提出可以使用概念格方法识别以往程序 代码中的潜在模块。 g o d i n 和m i n e a u 等在文献【9 中描述了使用概念格方法从现存软件系统 中生成和检索摘要的方法，并通过两个软件的重用过程演示了该方法。在文 献 1 0 】中研究者们还将概念格应用于类层次( c l a s sh i e r a r c h y ) 的设计上。 s n e l t i n g g 等在文献 1 1 中采用概念分析技术来根据现有的源代码推断出配 置结构，通过对生成的概念格进行可视化显示，清晰的显示出可能存在的配 置结构和性质。s c h m i t t 等在文献 1 2 】中设计了一个有效的算法合并具有相互 重叠类型的类继承层次，来导出集成的继承层次，它是以概念格作为类继承 层次的形式化机制。 四、信息检索 在信息检索方面，可以实现对信息的有机组织，作为检索的支撑结构。 g o d i n 等在文 2 7 中对使用概念格结构的信息检索进行了实验，并和两种 较为传统的检索方法( 在手工建立层次分类系统中导航，以及使用索引项的 布尔查询) 做了比较。结果表明，在布尔检索和概念格检索之间并没有显著 的性能差异，然而，层次分类系统的查全率要明显低于其它两种检索方法。 因而得出结论，概念格结构的检索是非常有吸引力的。 c a r p i n e t o 等【3 0 】设计的g a l o i s 系统和g o d i n 在 2 7 】中所设计的系统基本 类似，一个不同之处在于生成概念格的方法，c a r p i n e t o 等的方法能够处理结 河南大学研究生硕士学位论文第5 页 构化的特征描述子。 在文献f 2 9 1 中，c a r p i n e t o 提出了对基于概念格的文本数据库的自动组织 和混合导航进行了较为全面的研究，并设计了一个检索系统u l y s s e s ，实验 的结果表明该检索系统的性能优于布尔检索。 文献 5 7 】将概念格方法应用于分析和可视化具有l9 6 2 个属性 和4 0 0 0 个处方摘要的医药数据库。文献 5 8 】展示了概念层次进行w 曲文档 索引和导航的能力。文献 5 9 】建造了基于概念格的用于数字图书馆的系 统n e b u l a 及相应接口。u k r o h n 和n j d a v i e s 在文献 2 6 】中提出了一种基于概 念格结构的网上智能查询机制，企图去分析和揭示各类文档间的内在关联， 将其应用于知识管理和信息检索，实现新知识的获取和己有知识的共享。 n e u s s 和k e n t 【1 4 】使用概念格进行i n t e r n e t 上文档元信息的自动分类和分析。 1 2 概念格构造的研究现状 在概念格的应用过程中，格的构造具有非常重要的地位。总的来说，概 念格的构造方法大致可以分为三类：渐进式构造、批处理构造和并行构造， 本文将在第2 章中对概念格的构造方法进行详细的介绍。以下就这三类构造 方法在国内外的研究现状加以论述。 批处理算法的主要思想是首先生成所有概念，然后根据它们之间的直接 前驱一一后继关系生成边，完成概念格的构造，例如b o r d a t 算法例，c h e i n 算法【2 1 ，g a n t e r 算法【2 1 ，n o u r i n e 的算法【”】等；渐进式算法的思想首先初始 化概念格为空，将当前要插入的对象和现有格中所有的形式概念作交运算， 根据交的结果的不同采取不同的行动，典型的算法有g o d i n 【2 1 ，c a p i n e t o 【3 2 j 和t b h o 的算法【20 1 。国内对上述的有些算法做了一些改进，例如改进了的 b o r d a t 算法挖掘关联规则【3 3 】、扩展概念格的渐进式构造算法【3 4 】、基于索引 树的概念格渐进式构造算法【35 】等。渐进式算法被认为是比较有前途的一类， 在渐进式构造概念格的算法中，比较典型的是g o d i n 所提出的算法。 文献 3 6 对g o d i n 的算法做了一些改进，利用图的深度优先遍历算法减 少了新生格节点之间确定父子关系时的遍历次数，利用数据库的内部技术实 现了确定产生子格的查找判断过程，从而减少了部分情况下的时间复杂度。 文献 3 3 】是对b o a d a t 算法的改进，它为了削减格中节点的数目，引进一 个支持度的观点，只有在支持度e 之上的格节点才会生成。算法的基本思想 是格l 初始化为最顶端的节点( o ，巾) ，并通过递归地构造其子节点来扩展， 这种自顶而下的方式有利于修剪掉不满足支持度的节点，提高了算法效率。 第6 页河南大学研究生硕士学位论文 文献 3 4 】提出了一种扩展概念格在数据对象增加时的更新算法，从而对 实际应用中数据对象增长时如何更新扩展概念格的问题提出了一种有效的 解决方法。算法的基本思想是：当渐进式的追加一个新对象时，首先根据格 中概念的变化情况来找到需要修改的概念，因为概念变化时，边也要发生变 化，因此有关的边也要进行相应的修改，然后，根据不同的情况决定如何更 新原来的格。相对于文献【3 4 】中新增对象时的造格，针对已构造好的扩展概 念格，在数据维数很多时，删除数据时若重新构造格是很麻烦的，文献 5l 】、 【5 2 】和 5 3 分别提出了一种扩展概念格的维护算法、约减概念格的纵向维护 算法和基于属性链表的概念格纵横向维护算法，很好的解决了这一问题。 文献【3 5 】提出了采用树结构对概念格节点进行组织，并给出基于这种树 状组织的概念格快速渐进式构造算法，利用格节点的树结构组织有利于识别 出格节点的类型以及约束新生格节点的父节点和子节点的搜索范围，从而有 效的减少算法的执行时间。 一般而言，形式背景的属性个数是有限的，而对象个数往往较大，基于 这种特点，文献 3 9 、 4 0 】和文献 4 1 提出了一种基于属性的渐进式生成概念 格的算法，它不仅为概念格的构造提供了一种新的方法，而且解决了在已构 造好概念格的前提下，属性所带来的概念格更新问题，这是传统的基于对 象的渐进式算法所不能解决的。另外，它也为分布式存储的形式背景及其概 念格的横向合并提供了基础，比传统的基于对象的渐进式造格算法具有更大 的优越性。 相对于之前形式背景确定下格的构造，文献 5 5 提出了一种属性模糊的 概念格构造算法，将“模糊”引入概念知识系统，定义了广义属性模糊概念 格和其上的截运算以简化格构造，并在概念格的节点级定义了两个模糊参数 口和6 以避免提取因偏差导致的无意义规则，使模糊格的构造和分析更加简 洁。与多值背景的单值转换法相比，文献【5 5 】提出的算法做了模糊表示，实 际需要属性少，生成格的规模也较小。 文献 3 7 】探讨了影响g o d i n 算法效率的因素，认为在形式背景中对象的 属性分布均匀的情况下，最佳的对象输入序列是按照它们所包含属性的从多 到少的顺序。 在概念格中，造格算法具有很重要的地位，以上的种种概念格构造算法 虽然各有区别，但归根结底都属于批处理算法或渐进式算法，也称串行构造 算法。随着高性能并行计算技术的发展和成熟，并行计算机强大的计算和存 储能力为解决概念格构造问题提供了一条新的途径。目前有关概念格生成的 并行算法研究不是很多，已经出现的算法通常是以其它经典的串行算法原理 河南大学研究生硕士学位论文第7 页 为基础，将其改造为适合并行计算的并行算法。例如，文献【3 2 】中作者根据 b o r d a t 算法的原理设计了一个并行化版本，p a r a l l e l n e x t c l o s u r e 算法【”】是基 于n e x t c l o s u r e 算法改进的并行化算法。可以预测，对于海量数据的概念格 的生成和应用研究，并行算法必然是一个大的趋势。近些年出现的值得关注 的概念格构造的并行算法有【4 2 【4 3 儿4 4 】 4 5 】【4 6 】 4 7 】【4 8 】【4 9 】 5 0 】等。 虽然目前出现的并行算法不是很多，但是还是可以根据实现思路的不 同，将算法分为两大类：一类是将形式背景划分为多个区间，然后使每台计 算机在各个区间内计算，最后将每台计算机的计算结果合并起来的就是所求 概念格中的所有概念；另一类是将形式背景划分为多片，然后分别独立构造 概念格，然后采用概念格合并算法构造出最终需要的概念格。第二类算法的 特点是产生的中间结果也是概念格，这样的优点是显而易见的，该类算法更 适合于概念格的分布式计算和存储，同时对于那些形式背景经常变动的情 况，第二类算法不需要重新计算所有的数据，仅需把变动的那部分形式背景 构造出概念格，然后和其余的部分合并就可以了。 第一类算法中比较经典的是p a r a l l e l n e x t c l o s u r e算法。 p a r a l l e l n e x t c l o s u r e 是基于分解搜索区间的一种造格算法。它和另外一些已 有的通过分解形式背景来构造概念格的那些分解算法是不同的，因为那些算 法将会产生许多重叠的搜索子区间。p a r a l l e l n e x t c l o s u r e 用一种新的方法即 通过产生非重叠的搜索子区间来分解搜索区间。该算法基于n e x t c l o s u r e 算 法。如果一个分划中至少存在一个概念的话，它可以通过不同的分划来随意 地分解搜索区间。每个分划是独立并且和别的分划共享相同的源数据( 形式 背景) 。可以能用单个处理器对单个分划生成概念，并且互不干扰。 p a r a l l e l n e x t c l o s u r e 算法表现出很好的可扩展性，并且很容易用于并行和分 布式计算。 文献【4 4 】证明了横向合并的子形式背景的概念格和子背景所对应的子概 念格的横向并是同构的，为概念格的横向合并提供了理论依据，并提出了一 种多概念格的横向合并算法，其时间复杂度比直接用形式背景造格有明显改 善。文献 4 6 】在文献【4 4 的基础上提出了同类概念的观点，进一步提高了算 法效率，该算法非常适用于概念格的分布式并行构造。 文献 4 3 提出了一种分布式造格思想，为多概念格的纵向合并提高了理 论依据。文献【4 5 】在此基础上提出了同义概念的观点，由于格中新增概念的 同义概念只需更新其父节点的内涵，节省了大量的比较时间，文献【4 5 1 也提 出了一种利用索引结构来快速查找同义概念的算法，大大提高了格的构造效 率，此算法也非常适用于并行造格。 第8 页河南大学研究生硕士学位论文 利用批处理算法的并行性和渐进式算法的高效性，文献4 8 1 给出了一种 新的概念格并行构造方法。给出了确定子全概念的一个量化的公式，提高了 算法的效率。 随着形式概念分析理论在软件工程、信息检索和知识发现等诸多领域的 广泛应用，国内外对其研究也逐渐增多。由于造格算法对整个形式概念分析 理论的重要性，所以在国内外一直是研究的热点。批处理算法、渐进式算法 等单纯的串行算法在国内外已有很多人在研究，相关方面的文献也有很多。 但由于概念格自身的完备性，形式背景的微小增大将导致所构造概念格的节 点个数呈形式背景对象个数和属性个数的指数备增加，这就导致单纯的依靠 提高算法效率来减小概念格规模变的几乎不可能。随着近年来高性能计算机 并行计算技术的成熟和高性能并行计算机费用的降低，概念格的并行构造思 想应运而生了。但是对并行算法的研究，不管是国内或是国外，都处于一个 初步阶段，当前的并行算法也比较少，已经出现的算法通常是以其它经典的 串行算法为基础，将其改造为适合并行计算的并行算法。所以，对概念格并 行构造算法的研究，不管是在国内或是国外，都有很大的发展空间。 1 3 概念格构造所面临的主要问题及解决方法 概念格所具有的完备性虽然使得格的构造不受数据或属性排列次序和 构造方法的影响，保证其最终形式的唯一性；但另一方面它也使得对于适当 大小的数据，将产生庞大的格结构。理论上讲，最坏情况下概念的节点数目 会以形式背景对象个数和属性个数的指数倍增长。随着数据规模的不断增 长，从形式背景构造概念格需要的时间越来越长，存储概念格所需要的空间 也越来越大，逐渐成为制约概念格应用的一个重要因素。由于概念格的完备 性原因，使得寻找一种时间复杂度比现有算法优很多的概念格构造算法变得 几乎不可能，因此，如何较快的从几乎是海量数据的形式背景中构造概念格 的仍然是目前形式概念分析领域研究的一个重点和难点。 为此，本文在已有的各种概念格构造算法或模型的基础上，重点对并行 造格进行了研究。通过对新增对象内涵的分析，发现在插入对象时将其内涵 按照深度优先的方式自下而上的与原格中的节点做交集，根据交的结果进而 采取相应的动作；另外，在做交集的过程中，对满足一定条件的节点设置标 志位，可以降低新增对象时节点的比较次数，从而降低造格的时间复杂度， 在此基础上，设计并实现了一种基于深度优先的概念格构造算法。之后，我 们将该构造算法并行化，得到一种基于深度优先的概念格并行构造模型。实 河南大学研究生硕士学位论文第9 页 验证明，文章提出的并行构造模型是正确而有效的。 1 4 本文内容组织 本文的主要内容是提出一种基于深度优先的概念格构造算法，提高了格 的构造效率；将串行构造算并行化，从而一定程度上解决面对海量数据形式 背景时概念格的构造效率问题。 本文的内容组织如下： 第二章主要介绍形式概念分析理论的数学基础，包括格论、序论和形式 概念分析理论中的一些基本定义，由基本定义推导得出几个定理并予以证 明；给出了三类造格算法，即渐进式算法、批处理算法和并行算法，并就经 典的批处理算法如b o r d a t 【8 】，c h e i n 【2 】算法，经典的渐进式构造算法如g o d i n 算 法做了详细介绍。 第三章和第四章是本文的重点。 第三章设计并实现了基于深度优先的概念格构造算法，通过与传统的概 念格构造算法g o d i n 对比，验证了其正确性和有效性。尤其是当新增对象的 内涵与原格特征域的交集( 相似率) 较小时，算法的优越性更加明显。 第四章重点讨论了针对随着数据量增大产生的概念格构造的时间复杂 性迅速增大的问题，提出了用高性能并行计算机的计算与存储能力来解决。 从而提出了一种基于深度优先的概念格并行构造模型，阐述了该并行化模型 的体系结构和算法思想，并对实验结果进行分析。 最后是全文的总结，对本文的主要研究工作进行简要的阐述，并探讨和 展望了在未来时间内应当完善的问题。 第1 0 页河南大学研究生硕士学位论文 第2 章形式概念分析的理论基础 形式概念分析( f o r m a lc o n c e p ta n a l y s i s ) 是上个世纪八十年代刚兴起的 一门应用数学的新学科，其数学基础在于序论( o r d e rt h e o r y ) 及完全格 ( c o m p l e t el a t t i c e ) 理论，数学家们关注它则是因为它在许多领域的诸多应 用。形式概念分析反映了概念的哲学理解，并被应用于概念的发现、排序和 显示。现实世界是由各种各样的对象组成，每个对象有自己的一组属性或特 征。概念是把所感知的事物的共同本质特点抽象出来，并加以概括。在哲学 中，概念被理解为由外延和内涵两个部分所组成的思想单元。基于对概念的 这一理解，德国的w i l l er 教授提出了形式概念分析( f o r m a lc o n c e p ta n a l y s i s ) 【l 】，用于概念的发现、排序和显示。在形式概念分析中，概念的外延被理解为 属于这个概念的所有对象的集合，而内涵则被认为是所有这些对象所共有的 特征( 或属性) 集，这就实现了对概念的哲学理解的形式化。形式概念分析 的主要内容即是一对集合之间的二元关系，即g a l o i s 格或者概念格。概念格 的每个节点都是一个由外延和内涵两部分组成的形式概念。外延指形式概念 所覆盖的实例，内涵即该概念所覆盖实例的共同特征。概念格结构是反映对 象与属性之间联系以及概念泛化与例化关系的一种完备的概念层次结构。概 念格作为其核心的数据结构，描述了对象和特征之间的联系，表明了概念之 间的泛化和例化关系，相应的h a s s e 图实现了对数据的可视化，生动简洁的 体现了这些概念之间的泛化与例化关系，因此，概念格被认为是进行数据分 析的有力工具。作为序论和格论与实际应用相结合的产物，概念格模型的研 究具有重要的理论意义，目前已经在知识发现、机器学习、软件工程、信息 检索等诸多领域得到了一定的应用。 2 1 概念格模型的数学基础 概念格模型是序论和格论与实际应用结合的产物，这里我们首先给出序 论和格论中的一些基本定义【56 1 。 2 1 1 序论中的基本定义 定义2 1 设么是一个集合，如果么上的一个关系r ，对于v x ，y ，z 彳， 满足如下条件： x r x ( 自反性) 海南大学硒究生硕士学位论文第ll 页 集。 x 砂，婶工善一y ( 反对称憔) x 缈，艘：搬：