（应用数学专业论文）概念格chein构造算法的改进.pdf

河南大学研究生硕士学位论文第1 页 摘要 形式概念分析作为一种有效的数据分析工具，已经在许多领域得到了广泛的 应用，如：机器学习、知识发现、信息检索、软件工程等等。概念格是形式概念 分析理论中的核心数据结构，而对概念格的许多应用都要涉及到概念格的构造。 概念格的完备性是它的主要优点之一，它使造格的最终的形式是唯一的和可重复 的，因此概念格的构造不受数据或属性排列次序和构造方法的影响。但也因此导 致概念格的结构庞大。在理论上的最坏的情况下，概念的节点个数会随着形式背 景中对象个数和属性个数的增加以指数倍增长。构造概念格需要解决的一个重要 问题就是：如何提高构造概念格的效率，降低时间复杂度。 概念格的c h e i n 构造算法是以分层的方式自下而上进行构造的，具有构造简单 明了，易于生成h a s s e 图的特点。但是，c h e i n 算法构造概念格的效率较差。c h e i n 算法在生成下一层的过程中，对当前层的所有概念进行相交运算，不但耗费运算 时间，而且会在下一层产生大量冗余节点，导致下一层要进行更多的相交运算。 因此，使得c h e i n 算法效率较低，而且需要占用大量的存储空间用来存放冗余节点。 本文在对目前已有的各种概念格构造算法进行研究的基础上，对c h e i n 算法进 行了改进。通过分析概念格的c h e i n 构造算法存在的问题，提出了信息反映度的概 念，并以此解释了c h e i n 算法在构造概念格时产生大量冗余节点却不能删除的原 因，由此提出了对c h e i n 算法的改进。 改进算法的算法思想为：在产生下一层的概念节点之前，先对当前层概念组 成进行分析，确定当前层是否存在冗余概念。如果有冗余概念，则将冗余概念根 据属性集的蕴含关系，找到相应的非冗余概念划分为一组，在生成下一层概念节 点时，只需要将同组的冗余概念和非冗余概念进行相交运算即可，不但减少了生 成时间，而且有效避免了冗余节点在下一层的产生；如果当前层没有冗余节点， 则对所有非冗余节点进行相交运算，相交次数仍然小于c h e i n 算法。从而在提高概 念格构造效率和降低造格时间复杂度的同时，保留了c h e i n 算法结构清晰明了和易 于生成h a s s e 图的优点。 实验和算法分析表明，本文提出的模型和算法是有效的，随着形式背景规模 第1 i 页河南大学研究生硕士学位论文 的增大，相对于c h e i n 算法的优势也会更加明显。因此，适用于对较大规模的形式 背景进行批处理造格。 本文的主要工作如下： ( 1 ) 提出了对c h e i n 算法的改进，用非冗余概念之间的相交运算以及非冗余概 念与冗余概念进行相交运算两种方式，代替了c h e i n 算法中对当前层所有概念两两 进行相交运算的方式，来生成下一层的概念节点，从而提高了构造概念格的效率。 ( 2 ) 在研究c h e i n 算法的过程中，提出了信息反映度的概念，证明了c h e i n 算 法构造概念格在概念信息反映不完全的情况下，不能直接删除冗余概念节点。只 有当冗余节点包含的信息在概念格中得到完全反映之后，才能删除冗余概念节点。 关键词冗余概念；非冗余概念；备用概念；相交运算 河南大学研究生硕士学位论文 第1 i i 页 一一 a b s t r a c t fo m a lc o n c e p ta 1 1 a l y s i sae 虢c t i v et o o l i nd a ：t aa l l a l y s i s ，w m c hh a sb e e n 谢d e l v 印p l i e dt om a l l yf i e l d ss u c ha sm a c k n el e a m i n g ，k n o w l e d g ed i s c o v e 吼i l d b 珊a t j o n r e l n e v a la n ds o 角a r ee n g i n e e r i n g c o n c 印tl a n i c ei s t h et h em a j nd a t as t r u c t u r ei n 幻n n a lc o n c e p ta n a l y s l st h e o a n dm a n ya p p l i c a t i o no fc o n c e p t l a ：t t i c eh a st ot h e c o n 咖c et l l ec o n c 印tl a 仕i c ef i r s t t l l e c o m p l e t e n e s so fc o n c e p tl 枷c ei so n eo fm e m 笱o ra d v 瓤a g e so fc o n c e p tl 删c e i ti n s u r e st h eu n i q u e n e s so f 如e 丘n a lr e s u l t sw h i c h d o e s n tb e e ni n n u e n c e db yt h eo r d e ro fd a t a o ra ：t 仃i b u t e sa 1 1 d t h ec o n s t l l j c t i o n a l g o r i t h m s t i nt h eo t h e r h a l l d ，i tw i l lm a l 【eal a r g el 砌c ee v e n 丹o mas m a l ls e t o f o n g i n a ld a t a t h e o r e t i c a l l ys p e 出n g ，- t h en o d e sn 啪b e ro ft 1 1 el a t t i c ew i l l i n c r e a s e e x p o n e n t l a l l y 、撕也t h eg r o w t ho fo 场e c t sa 1 1 da t t r i b u t e si nt 1 1 ew o r s tc o n d j t i o n s of o rt h e c o n s t m c t l o no 士c o n c 印tl 雒i c ，也e r ei sap r o b l e mt os o l v e ，h o wt oi m p r o v e t h ee 茄c i e n c y o fc o n s t m c t i o na n dr e d u c et h et i m e c o r n p l e x i 够 c h e i n a l g o r i t t l i n ，w h i c hi so n eo ft h e 酊g o r i t l l l l l sl l s e dt oc o n s t m c e1 a 钍i c e t o p d o ，1 1c o n s t m c t i n gt h el a t t i c e i fu s i n gc h e i na l g o d t l l l nt oc o n s t r u c el a 位i c e i t ，s c j 觚t yb e t w e e nc o n c 印t sa z l de a s yt 0 g e n e r a t eh a s s ed i a g 豫m b u t 也ea 】g o 五t h mi s m e 垃1 c l e n t i nt h ep r o c e s so fg e n e r a t i n gt l l e c o n c e p t si nn e w1 e v e l ，i ti n t e r s e c t sa 1 1t h e c o n c 印t sb e t w e e ne a c ho 也e ri nc u 玳n tl e v e l ，w m c hh a st 0c o n s u m em u c ht i m ei 1 1 c a l c u l a t l o na i l dg e n e r a t e sm a i l yc o n c 印t so fr e d u l l d a n c y n l ec o n c 印t so f r e d u n d a n c v m a yc a u s em o r ei n t e r s e c t i o nb 咖e e nc o n c 印t s 协t 1 1 en e x t 】e v e la 1 1 d g e n e r a t em o r e c o n c e p t so tr e d u l l d a l l c yi nm en e x tl e v e l 1 1 1 a t sw h yc h e i na 1 9 0 棚ni si n e 硒c i e n ta 1 1 d h a st ou s eu pa 1 0 to f s t o r a g es p a c et os t o r e 。 b a s e do nm er e s e a r c ho fc o n c 印tl 砌c es t m c t u r eo ft h ec u 玎e n ta l g o r i t l l i l l s ，t h j s p 印e rp - o p o s e da 1 1n e wa l g o r i t l l 】mt oi r n p r o v et 1 1 ec h e i na l g 谢t l 瑚b ya n a l y z i n gt h e e x l s t i i l gp r o b l e m so fc h e i na l g o r i t h m ，t 陆sp a p e ru s e sm ei n f o 彻a t i o nr e n e c t i o nt 0 e x p l a i nw h yc h e i na l g o r i t h i nd on o td e l e t et h ec o n c e p t so f r e d u l l d a n c yi ni t ，sc o n s t m c t p r o c e s s ，a n di m p r o v et h ea l g o r i t h mi nt m sr e s p e c t t h em a i ni d e ao ft h em o d i 6 e da j g o 打【h mi st om a l ( es u r ew h e t h e re x i s tc o n c e d t so f 第1 v 页河南大学研究生硕士学位论文 r e d u n d a i l c y i nc u 玎e n tl e v e l w ec a nc i a s s i 母 c o n c e p t s o fr e d u n d a n c ya n dn l e c o r r e s p o n d i n gn o n r e d u n d 觚tc o n c e p t sa sag r o u pa c c o r d i n gt ot h ec o n t a i nr e l a t i o n s b e t w e e nt h e m ，i fr e d u n d a n tc o n c e p t se x i s t ，w h e ng e n e r a t i n gc o n c e p t si nn e x tl e v e l ，w e c a no i l l ym a k ei n t e r s e c t i o nb e t w e e nn o n - r e d l m d a n tc o n c e p t sa i l d 也e i rc o r r e s p o n d i n g r e d u n d a n tc o n c e p t si ne a c hg r o u p s i ft h e r e sn or e d u n d a n tc o n c e p t se x i s ti nc u r r e n tl e v e l ， w ec a no n l ym a k ei n t e r s e c t i o nb e 觚e e nn o n - r e d u n d a n tc o n c e p t s b yt h i sw a y ，m o d i 矗e d a l g o r i t h r nr e d u c et h et i m e so fi n t e r s e c t i o na n dr e t a j nm ea d v a l l t a g e so f c h e i na l g o r i 也m b ya i l a l y s i sa n de x p e r i i n e n t sc h e i na l g o d 吐na n dm o d i f i e da l g o r i m m ，i ts h o w s t h a tt h em o d i f i e da l g o r i 岫1i sm o r ee 自陪c t i v en l a nc h e i n 灿g o r i t h m ，s p e c i a l l y 谢t ht h e i i l c r e a s i n go fd a t as c a l ei nf o m l a lc o n t e x t s oi t s m o r es u i 饭b l et ou s i i l gm o d i f i e d a l g o r i t m nt oc o n s t m c tl a t t i c ec o m p a r e dw i t l lc h e i na l g o r i t h m ，w h e nt h ed a ：t as c a l eo f f o n l l 削c o n t e x ti sb i g m 匈o rw o r k ： 1 ) a g a i n s tt 1 1 eo r i 西n a la p p r o a u c h ，t 王l i sp a p e rp r o p o s e sam o d i f i e da l g o r i m m ，w 1 1 i c h g e n e r a t e st h ec o n c e p t so fn e x tl e v e lb yi n t e r s e c t i n gn o n - r e d u l l d a n tc o n c e p t si nc u r r e n t l e v e lo ri n t e r s e c t i n gn o n r e d u n d a l l t c o n c e p t s 、v i t h i t s c 0 眦s p o n d i n g r e d u n d a m c o n c e p t si 1 1 c u r r e n tl e v e l t h e s et 、阳w a y sa r em o r ee 压e c t i v em 姐i n t e r s e c t i i l ga l l c o n c e p t si nc u 仃e n tl e v e l ，s om em o d i f i e da l g o 傩吼i sm o r ee 虢c t i v et h a i lc h e i n a 1 9 0 r i t h m 2 ) i nt h er e s e a r c ho fc h e i na l g o r i t h m ，t m sp a p e rr a i s e sm ec o n c e p to fi n f o m a t i o n r e n e “o n ，a n dp r o v e dc h e i n 赳g o r i t l i i lc a i l t d e l e t er e d 岫d a i l tc o n c e p t sw h e nt h e y d o e s n tr e n e c ta 1 1 如ei n f o r m a t i o nt h e yc o n t a i l l i n g 0 1 1 1 yw h e nt h ei 1 1 f o 册a t i o nc o n t a i n e d i nt 1 1 er e d u n d a n tc o n c e p t si st o t a l l yr e f l e c t e d ，m er e d u n d a i l tc o n c e p t sc a l lb ed e l e t e d k e y w o r d s ： r e d u n d a l l t c o n c e p t s ； n o n r e d u n d 肌t c o n c e p t s ； s t a l l d b l e c o n c e p t s ； i n t e r s e c t i o n 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成粟，也不包括其他人为获得任何教育、科研机构的学住或证书而 使用过的材料。与我一同工作备勺同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。t 。 j ： ! ? 。j j ii?。+。 、 学位中请人：，学位论文作者) 签名：一盒狴： j 。，j t ，j ? 。i j 。j 。j j ! j j i jj 、j i 。- 鼻 。，：j ：7 ，2 d 以年6 月f o 日 ? ”、z 鼻7 77 i：7 “。z 玎q b 干b 月f o 日 箩| ，2 ”。，：“i j o =+ ，i ：，一 芬 一 i ； ? t ；，t j 一 t 。 11t 。q ，。i i 雾? o i 、一7 1 1 | o ，叠 ；，。， 5 一7 ： 一关于学位论文著作权使用授权书j ：、 鼍 ：， t i “” 。j ，_ ? j i ?一| 一 一_ 。t 一，“? _ i j 本人经河南大学审核批准授予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论克酌要求，即河南大学有权向国家 图书馆i 科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、查阅。本人授权河赢大学出于宣扬、展览学校 学术发展和进行学术交流等目的，可以采取影印、缩印、扫描帝拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学住获得者( 学位论文作者) 签名：佥! 銎 2 0 学位论文指导教师签名： 2 0o 寥年6 月d 目 河南大学研究生硕士学位论文第1 页 第1 章绪论 形式概念分析”( f o 肌a lc o n c e p ta i l a l y s i s ) 是2 0 世纪8 0 年代初由德国w i l l e 教授提出的，它是以数学化的概念和概念层次为基础的应用数学领域，它的数学 基础是序论( o r d e rt l e o 哆) 及完全格( c o m p l e t e1 a 戗i c e ) 理论。形式概念分析所指的概念 是由哲学理论中的概念发展而来的，它反映了概念的哲学理解，并被用于对概念 的发现、排序和显示。在形式概念分析中，概念格作为形式概念分析的核心数据 结构，描述了对象和特征之间的联系，概念格在本质上是由一组具有泛化、例化 关系的节点组成，每个概念是一个由表示对象子集的外延和表示这个对象子集共 同特征的内涵组成的序偶。概念格之间的泛化、例化关系还可以通过h a s s e 图来表 示。h a s s e 图是偏序集关系图的一种简明而有效的表示，将概念用直观的方式表示 出来，通过它可以生动和简洁地描述概念之间的泛化和特化关系。目前已经在知 识工程、数据挖掘、信息检索、数字图书馆、软件工程和知识发现等诸多领域得 到了应用。 本章主要介绍了形式概念分析产生的背景，以及形式概念分析主要的研究内 容和面临的问题，并引出了本文的课题来源及所要做的主要工作：对已有的c h e i n 算法进行改进，用批处理的方法进行造格。最后简单介绍了下本文内容的组织 安排。 1 1 形式概念分析的产生 人类在认识现实世界的过程中，把对认知的事物的特征加以归纳和概括，称 为概念。在哲学中，概念反映了客观事物的般的、本质的特性，它是包含外延 和内涵两个部分的思想单元。对概念的这种理解源于古希腊哲学，发展于十七世 纪的近代学院派，进一步发展成德国标准，最终成为了世界标准。由于概念是思 维的基本单位，所以基于对概念的研究成为人工智能的一个重要组成部分。在知 识表示、知识管理、机器学习、专家系统等不同的领域的研究者们从不同的角度 和观点出发，用不同的方法对概念进行分析，形成了对概念的不同形式化描述方 法。 第2 页河南大学研究生硕士学位论文 形式概念分析是一种对数据进行分析的工具，它的特点是可以对给定的信息 进行分析和处理。如果要对现实世界繁复多样的信息进行分析，就必须把这种信 息抽象成为对人类有意义并且可以为人类所理解的思维单位。这就要求必须将其 抽象形成形式化的单元。形式化表明的是所处理的数据是形式化的数学实体，不 必和人类思维中的概念完全相同，它同时也指出形式概念分析处理的基本数据形 式是形式背景，形式背景是人类背景知识中的一小部分。 形式概念分析来源于b r i l ( 1 l o f r 格理论的研究和应用。2 0 世纪7 0 年代末期，德 国的d 锄s t 础技术大学数学系在研究b r i l 出o f r 格理论的基础上，提出和发展了形 式概念分析理论，并于1 9 8 1 年在关于有序集合的b a n 行会议的专题演讲上首次对 形式概念分析作了描述。之后，d a m s t a d t 研究小组发表了数以百计的相关论文。 d a m s t a d t 研究小组的研究为形式概念分析做出了巨大的贡献，并且使其逐步实用 化，并在此后从事多达上百个基于格理论的应用软件研究。 d 锄s t a d t 小组的研究显然在形式概念分析的诞生及应用过程中起到了重大的 作用。他们首先把种种可能性系统地详细阐述为一种数据分析方法，并且进行试 验，进一步开发许多应用。该工作成功的决定性因素存在于背景的形式化和把“概 念”作为外延和内涵实体的解释。在这里，“概念”已经被形式化，并且对它的理解 深深植根于哲学，这在文献 1 中有详细的描述。 1 2 形式概念分析的主要内容 2 0 世纪8 0 年代初，在d a m l s t a d t 小组对b i r k h o f r 格理论研究的基础上，德国 的w i l l e 教授将概念格( c o n c e p tl a n i c e ) 【2 】作为一种数学理论引入，奠定了形式概念 分析的理论基础，将哲学的概念进行数学化的描述，从而实现了对概念进行形式 化的描述方法。概念格是形式概念分析理论的核心数据结构，被认为是知识发现 和数据分析的有力数学工具。 1 2 1 基础理论 研究概念的形式化描述和定义、定理、特征等，是形式概念分析的理论基础。 b i 幽o f r 的格理论是形式概念分析最早的理论著作，它是形式概念分析的重要理论 基础也是形式概念分析的理论雏形。在1 9 4 0 年出版的b i r k h o 行关于格理论的著作 河南大学研究生硕士学位论文第3 页 ( l a t t i c e1 1 1 e o 巧) 第一版【3 中，明确提到了关联关系( 如对象属性关系) 的解释，并 解释和说明了如何从一个二维表中来构造完全的格结构。 而第一个全面阐述形式概念分析的则是德国的、胍l l e 教授，他在r e s t r u c 嘶n g la ：t t i c em e o 珂：a ma p p r o a c hb a 娆do nm e r a r c l l i e so fc o n c e p t s 4 中对形式概念分析做了 全面阐述。这部文献利用了b i r k h o f f 格理论的结论所提供的数学可能性进行数据分 析，并且已经包含了许多在文中提及的思想，包括关于概念格基本定理的证明。 由于形式概念的应用的领域日益广泛，同时又需要面对不断增加的新需要， 所以，形式概念分析在b r i k h o f r 的格理论上作了迸一步的扩展和更深入的研究，并 且形式概念分析也不再只着眼于应用的角度，同时也在不断扩展理论的研究。 b a r b u 【4 】中也有值得关注的研究，可参见b a r b u t & m o n a r d e t 【5 】。一些法语作者在他 们的著作中使用t r e i l l i sd eg a l o i s 一词表示“概念格”。 1 2 2 概念格模型的应用 概念格作为一种强大的数据描述和分析工具，由于其完备性其所具有的优良 特性，目前在软件工程、数据挖掘、信息检索等多个领域获得成功应用，以下作 简单介绍。 一、应用于软件工程 在软件工程领域，形势概念分析为软件重用、面向对象程序设计等领域中某 些问题的解决提供了理论支持，并已经取得了一系列的应用成果。 g o d i n 和m i n e a u 等在文献 4 】中描述了使用概念格方法从现存软件系统中生成 和检索摘要的方法，并通过两个软件的重用过程演示了该方法。在文献 5 中研究 者们还将概念格应用于类层次( c l a s sh i e r a r c h y ) 的设计上。$ n e l t i n g g 等在文献【6 】中 采用概念分析技术来根据现有的源代码推断出配置结构，通过对生成的概念格进 行可视化显示，清晰的显示出可能存在的配置结构和性质。s c l l i i l i t t 等在文献【7 中 设计了一个有效的算法，合并具有相互重叠类型的类继承层次，来导出集成的继 承层次，它是以概念格作为类继承层次的形式化机制。 二、应用于知识发现 概念格的节点体现了概念格内涵和外延的统一，概念格的层次结构是节点间 的一种偏序关系，表明概念的泛化和例化关系。目前有不少研究工作探讨了从格 节点和概念格的层次结构中提取规则的问题。试验研究表明，基于概念格的各种 第4 页河南大学研究生硕士学位论文 规则提取系统是有效的，形式概念分析非常适合发现规则型知识。在知识发现方 面，有不少作者探讨过从格上提取规则的问题，也有作者直接用格节点实例匹配 而进行分类。已知的一些基于概念格的分类学习系统主要有：s a l l 锄i 开发的 r u l e a i e r 系统【8 】，n i w o u a 等设计的l e g a l f 【9 】系统等。 已知的一些基于概念格的分类学习系统主要有：s a l l 锄i 开发的r u l e a 】矾e r 系统f 2 纠和而n i i w o u a 等设计的l e g a l e 系统【2 l 】 捌。g o d i i l 等在文献 2 2 】中提出了 从概念格中提取出蕴涵规则的算法。m i s s a o u i 对文献 2 2 】进行了扩展，提出了从概 念格中提取近似规则( 又称为概率蕴涵规则) 的算法【2 3 1 。p a s q u i e r 等在文献 2 4 】 中以已发现的所有频繁项集作为基础，提出了用于提取确定性关联规则的 d u q u e l l i l e g u i g u e 基，以及用于近似关联规则的适当基( p r o p e rb a s i s ) 和结构基 ( s 咖c t 删b a s i s ) 。h otb 研究了基于概念格的概念聚类方法，并实现了一些学习 系统，包括o s h am 【2 5 】和i n c o s h a m 【2 6 】，使用了一种灵活的匹配过程( 组合了逻 辑的、门限的和最近邻的条件) 来允许系统改进它自身的推理性能，从而可以对 未知的实例进行灵活的预测。 在文献【2 7 中，w i l l e 引入多背景( m u l t i c o n t e x t ) 这个概念，并给出了不同形式背 景之间的四种不同的操作。以w i l l e 所提出的多背景为理论依据，文献【2 8 】 2 9 研 究了在概念格框架结构下结构化( 复杂) 对象中的概念学习和规则提取。l i q u i e r e 等在文献 3 0 】中研究了概念格在由标号图( 1 a b e l e dg r 印h ) 描述的实例中的学习。文献 2 5 研究了由标号的、递归的树所描述的数据和数据类，定义了一种数据描述的方 法一通用项( g e n t e m ) 、以及g e m e m l 之间的泛化关系，并且说明了在对象集和通 用项之间存在一个g 豇o i s 联接，从而可以应用g a l o i s 格的聚类方法。 三、应用于信息检索 在信息检索方面，概念格可以作为检索的支撑结构： 切b o h n 和n j d a v i e s 在文献f 3 8 中提出了一种基于概念格结构的网上智能查询 机制，试图分析和揭示各类文档间的内在关联，将其应用于知识管理和信息检索， 实现新知识的获取和己有知识的共享。g o d i n 等在文献 1 2 】中建立了一个概念格结 构的信息检索系统，并将其和其他两种较传统的信息检索系统相比较，得出结论： 基于概念格结构的检索是非常有吸引力的，因为它将主题搜索的良好特性和浏览 器的潜力结合在一起。 四、其他应用 河南大学研究生硕士学位论文第5 页 概念格还获得了其它的一些应用，如文献 3 2 通过使用嵌套线图来对概念层次 的任意组合进行可视化，来替代在o l a p ( 联机分析处理) 中被广泛使用的嵌套图。 埘i l e 在文献 2 7 1 中将概念图和形式概念分析结合起来，从而得到了对初等逻辑的一 种形式化，用于对于知识的表示和处理。斑c h a r d sd e b b i e 冽利用概念格对硒p p l e d o w nr u l e 进行有机的组织；c u l e 的c e m 电子邮件管理系统【3 4 】通过将e m a i l 存储 在概念格中，而不是常用的树状结构中，从而在检索电子邮件时获得了更大的灵 活性；文献 3 5 】则将概念格应用于智能帮助系统的领域建模。 1 2 3 概念格的造格方法及存在的问题 概念格的许多重要的应用，都需要立足于构造完毕的概念格的基础上。因此， 应用概念格，首先需要解决的问题就是如何造格。完备性是概念格的优点，但是， 也正是由于概念格的完备性，使得概念格的结构变得非常庞大。随着内涵和外延 数量的增加，造格的时间复杂度呈现指数级的增长，而且占据的存储空间也非常 巨大。因此如何提高概念格生成的效率就变得极为重要。 目前概念格的构造算法可以分为批处理构造算法和渐进式构造算法两种。其 中，批处理构造算法主要包括g a m e r 算法【1 6 1 、c h e i n 算法【3 2 、b o r d a t 算法【3 7 】和n o u r i n e 算法【3 5 1 等等。渐进式构造的经典算法包括g o d i n 算法【1 6 1 、c a p i n e t o 算法【3 6 】、t b h o 的算法f 2 0 1 。 在批处理构造算法中，c h e i n 算法和b o r d a t 算法在构造概念格时采用了分层构 造的方式。但是，b o r d a t 算法在构造时并没有明确的分层依据，因为它采用的是对 父节点递归生成子节点的方式。b o r d a t 算法的概念节点的生成顺序类似于树的深度 遍历。它的层次只能根据概念节点之间的父子关系，含糊地将某一概念节点的父 节点称为“上一层”，将子节点称为“下一层”，而无法确切定义某节点究竟属于 哪一层，哪些节点可以归为同一层。所以b o r d a t 算法的分层是有局部性的，在整个 概念格结构中，无法界定概念的层次，也无法确定无直接父子关系的概念之间的 层次关系。 c h e i n 算法的构造概念格有明确的层次关系。它采用自底向上的方式，逐层构 造概念格。关于c h e i n 算法，在第三章会有详细的介绍。c h e m 算法构造的概念格， 层次关系简单明了，而且逐层生成的方式很容易生成h a s s e 图。但是，c h e i n 算法在 构造过程中产生了大量的冗余对，因此算法效率较差。 第6 页河南大学研究生硕士学位论文 1 3 课题的来源和内容的组织 1 3 1 课题的来源 本课题的题目是“概念格c h e i n 构造算法的改进”。在目前的概念格批处理构 造算法中，c h e i n 算法采取了明确的分层方式进行构造。用c h e i n 算法构造概念格， 概念之间的层次关系简单明了，而且逐层构造的方式很容易生成h a s s e 图。但是， c h e i n 算法的缺点是在同层和下一层生成了大量的冗余对，不仅需要分配大量不必 要的存储空间，而且算法效率较差。 而随着形式概念分析的发展，需要解决的问题越来越复杂，形式背景的对象 和属性的数量也急剧增加。随着形式背景库和概念格库的迅速膨胀，使得概念格 的构造计算量不断增加，而且造格过程中会占用大量存储空间。在这种情况下， 如何降低概念格构造的时间复杂度和减少冗余节点的产生就变得更加重要。而 c h e i n 算法较低的造格效率和大量冗余对的产生，显然无法满足时间和空间的要 求。本文在对目前已有的造格方法研究分析的基础上，对c h e i n 算法进行了改进， 采用了将当前层的冗余概念与其对应的非冗余概念相交和非冗余概念之间相交的 方式，代替了原有的c h e i n 算法将当前层所有概念两两相交的方式来生成下一层的 概念，从而减少了概念之间进行相交运算的次数，降低了构造概念格的时间复杂 度，而且减少了冗余节点的产生，提高了存储空间的利用效率。 1 3 2 本文研究的内容及意义 概念格的构造是形式背景分析的一个重要方面，许多形式背景分析的应用要 依赖由形式背景构造的概念格来完成。概念格具有完备性的特点，即不受数据或 属性排列次序的影响，不同的构造方法所生成的格形式是唯一的。但是，概念格 的完备性也因此带来严重的问题：即使在数据量有限的情况下，也会产生庞大的 格结构。而形式背景的对象和属性数量增加时，概念节点的数量在理论上会以指 数倍增加。因此造成概念格的构造过程耗费大量的时间。 概念格的批处理构造算法中，c h e i n 算法的具有层次简单明了，并且易于构造 h a s s e 图的特点。但是，c h e i n 算法本身的效率较差，而且会产生大量的冗余节点。 河南大学研究生硕士学位论文第7 页 而随着形式背景分析的应用日益广泛，用来构造概念格的形式背景也日益复杂， 在属性和对象个数增加的情况下，用c h e i n 算法进行概念格的构造时间效率不高。 c h e i n 无法适用于对较大的形式背景的概念格构造。 本文研究的主要内容是如何提高c h e i n 算法的构造效率。在原有的c h e i n 算法 中，生成下一层的方式是对当前层的所有概念两两进行相交运算。在改进算法中， 采用对当前层的冗余概念与其对应的非冗余概念进行相交运算和非冗余概念之间 进行相交运算来生成下一层的概念，从而减少了相交运算的次数，提高了概念格 的构造效率，使得构造概念格的时间复杂度大大降低，并尽可能地减少了冗余节 点的产生，提高了存储空间的利用效率。 1 3 3 本文内容的组织 本文内容的组织如下： 第1 章主要介绍了形式概念分析产生，形式概念分析的主要内容，以及概念 格的造格方法和存在的问题。最后给出了本文的课题来源及所要做的主要工作， 即对c h e m 算法进行改进来构造概念格。 第2 章介绍了概念格的理论基础和构造，详细介绍了概念格的定义及理论基 础。同时介绍了目前主要的几种构造概念格的方法。 第3 章和第4 章是本文的重点。 第3 章介绍了概念格的层次和造格时涉及到层次划分的概念格构造算法。同 时介绍了概念格的清晰化和标准化。 第4 章对c h e i n 算法存在的问题进行分析，并提出了解决的办法。最后，提出 了改进的概念格构造算法并与原有的c h e i n 算法进行了比较和分析。 最后是全文的总结，并展望了在未来时间内应当完善的问题。 第8 页河南大学研究生硕士学位论文 第2 章概念格的构造 现实世界包含了多种多样的对象，其中任何一种对象都存在着和其它某些对 象相似的属性和与其它对象区别开来的独特的属性。概念，就是把人类是所感知 的一类或相近的几类事物进行抽象化，提取它们的共同的本质特点，并加以概括。 通过对概念的抽象和归纳，人类可以快速并深刻地认识事物，更有助于人类知识 的积累和传播。 在哲学中，概念作为思想的单位，包括两个部分：内涵和外延。基于哲学上 对概念的理解，德国的w i l l er 教授在2 0 世纪8 0 年代初提出了形式概念分析 ( f o n l l a lc o n c e d ta n a l y s i s ) 【4 】，用于对概念的发现、排序和显示。在形式概念分析中， 将概念的外延引申为属于这个概念的所有对象的集合，将内涵则引申为概念中所 有对象集合所共有的特征( 即属性) 集，从而实现了对概念的哲学理解的形式化。 形式概念分析的主要内容即是构成概念格的一对集合和它们之间的二元关 系，即g a l o i s 格或者概念格。概念格的每个节点都是由外延和内涵两部分组成的。 外延指形式概念所覆盖的实例，内涵即该概念所覆盖实例的共同特征。概念格的 外延和内涵符合一定条件的映射关系。概念格结构是反映对象与属性之间的联系 以及概念泛化与例化关系的一种完备的概念层次结构。概念格作为形式概念分析 中核心的数据结构，本质上描述了对象和特征之间的联系，表明了概念之间的泛 化与例化关系，其相应的h a s s e 图则实现了对数据的可视化，生动和简洁地体现了 这些概念之间的泛化关系。因此，概念格被认为是进行数据分析的有力工具。作 为序论和格论与实际应用结合的产物，概念格模型的研究具有重要的理论意义。 2 1 概念格的基础理论 形式概念分析【3 6 】是建立在序论( o r d e rt 1 1 e o 巧) 及完全格( c o n l p l e t el a t t i c e ) 理论 基础上的，概念格模型实质上就是序论和完全格与实际应用结合的产物，本节先 介绍一下序论和完全格的基础知识。 定义2 1 设么是一个集合，如果彳上的一个关系灭，对于协，y ，z 么，满足 如下条件： 河南大学研究生硕士学位论文第9 页 抛( 自反性) 斌y ，出jx = y ( 反对称性) 斌v ，纰j 胞( 传递性) 则称r 是彳上的一个偏序关系，把它记为“g 。序偶( 4 ，) 称为偏序集。 定义2 2 设( 么，) 为偏序集，对于魔型，如有口4 ，对b 的任意元素x ，都 满足廊，则称口为子集b 的上界。同理，如果对b 的任意元素x ，都满足怨， 则称口为子集召的下界。 定义2 3 设( 4 ，) 为偏序集，b 酬，口为b 的任一上界，若对b 的所有上界 y 均有口$ ，则称口为b 的最小上界( 上确界s u p r e m 眦) ，记为s u p ( b ) 。同样，若 6 为b 的任一下界，若对b 的所有下界z 均有签6 ，则称6 为b 的最大下界( 下确 界i r l f i m u m ) ，记为i n f ( b ) 。 定义2 4设( 么，) 是一个偏序集，如果a 中任意两个元素都有最小上界和 最大下界，则称( 彳，) 为格。 定义2 5 设( 彳，) 是一个格，如果在彳上定义两个二元运算v 和八，使得对 于任意的口，6 彳，6 等于口和6 的最小上界，口 6 等于口和6 的最大下界，那 么，就称( 彳，v ，八) 为由格( 么，) 所诱导的代数系统。二元运算v 和八分别称为并运 算和交运算。 通常用口v 6 来代替s u p ( 口，6 ) ) ，口 6 来代替i n 坟 口，6 ) ) 。类似地分别用v 召和 人b 来代替s u p ( b ) 和i n f ( b ) 。 定义2 6 设( 么，s ) 是一个偏序集，如果对于任意非空的集合s 型，都存在有 蟠，则( 彳，) 被称为是一个完全并半格，类似地，如果对于任意非空的集合s 型 都存在有心