（应用数学专业论文）概念格的构造、约简及其应用研究.pdf

广西大学学位论文原创性声明和使 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除己注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均已在论文中明确说明并致谢。 论文作者签名： 学位论文使用授权说明 年月日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务： 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：导师签名：年月日 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 概念格的构造、约简及其应用研究 摘要 概念格理论是德国数学家w f f i er 教授在2 0 世纪8 0 年代提出的，由于 其思想新颖、方法独特，已经成为知识发现的一个重要数学工具，是当前计 算机科学领域的一个热门研究课题。概念格也称为g 山i s 格，是形式概念分 析理论中的核心数据结构，它具体而形象地描述了对象和特征之间的关系， 表明了概念之间的泛化和特化关系因此概念格作为一种具有极大潜力的 有效的知识发现工具而备受广大研究者的关注，目前，概念格正在被广泛 应用于数据分析、决策分析和数据挖掘等，然而，它仍是一个年轻并在高速 发展的领域。本文对概念格中的若干基本问题进行了研究： 在概念格构造方面，通过研究概念的性质，给出并证明了反映概念之 间关系的几个定理，以此为基础提出了两种基于基本概念的渐进式概念格 构造算法。为了提高算法的效率，概念运算采用二进制运算方式，对提出的 算法作了进一步的完善。 在概念格约简方面，文章给出了一种属性重要性的定义及其性质，提 出了一种新的概念格属性约简算法。目前已有不少关于概念格构造和约筒 的算法，但这些算法大多是概念格的构造和约简分别进行的，在实际应用 中难以发挥其作用为此，在概念格构造和约简算法的基础上，提出了一种 在概念格构造过程中进行约简的算法。该算法首先生成基本概念，并对基 本概念进行约简，然后利用约简后的基本概念构造所有概念，得到约简后 的概念格 在概念格应用方面，利用概念格和b p 神经网络的各自优势，提出了一 种基于概念格的b p 神经网络模型。该模型首先利用概念格的理论对样本数 据进行属性约简，提取其中关键要素作为b p 神经网络的训练样本，用简化 的训练样本对b p 神经网络进行训练，建立优化的基于概念格的b p 神经网 络模型。仿真实验结果表明，基于概念格的b p 神经网络模型能简化b p 神 经网络的训练样本，优化b p 神经网络，提高了系统的学习效率和精度 关键词：概念格构造约简神经网络 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 c o n s t r u c t i o na n dr e d u c t i o no fc o n c e p tl a t t i c ea n di t s a p p l i c a t i o n a bs t r a c t c o n c e p tl a t t i c et h e o r yw a se l a b o r a t e db yp r o f e s s o rw i l l eo fg e r m a ni nt h ee i g h t i e so ft h et w e n t i e t hc e n t u r y w i t ht h ed e v e l o p m e n to ft h er e s e a r c ha b o u tc o n c e p tl a t t i c e t h e o r y ，i th a sb e c o m ean o t a b l er e s e a r c ht o p i ci nc o m p u t e rs c i e n c ef i e l d k n o w na s g a l o i sl a t t i c e ，c o n c e p tl a t t i c ei st h ec o r ed a t as t r u c t u r eo fc o n c e p tl a t t i c et h e o r ya n d r e p r e s e n t st h eo r d e rr e l a t i o n s h i pb e t w e e nt h ec o n c e p t sc o n c r e t e l ya n dc o n i c a l l y t h u s t h ec o n c e p tl a t t i c ea sag r e a tp o t e n t i a lf o re f f e c t i v ek n o w l e d g ed i s c o v e r yt o o l sh a sa t t r a c t e dw i d ea t t e n t i o no fr e s e a r c h e r s a tp r e s e n t ，t h ec o n c e p tl a t t i c ei sb e i n gw i d e l y u s e di nd a t aa n a l y s i s ，d e c i s i o na n a l y s i sa n dd a t am i n i n g ，b u ti ti ss t i l lar a p i d l yd e v e l o p - i n gy o u n ga r e a t h i sp a p e rm a i n l ys t u d i e ss o m eb a s i cp o i n t so fc o n c e p tl a t t i c e ，w h o s e c r e a t i v er e s e a r c hw o r k sa r ea sf o l l o w s ： t h ec o n s t r u c t i n gm e t h o do fc o n c e p tl a t t i c e i nt h i sp a p e r ，s e v e r a lt h e o r e m sw h i c h r e f l e c tt h er e l a t i o n s h i pb e t w e e nc o n c e p t sa r el i s t e da n dp r o v e db ys t u d y i n gt h ec h a r - a c t e r i s t i c so fc o n c e p t s f u r t h e r ，t w oi n c r e m e n t a lb u i l d i n ga l g o r i t h m so fc o n c e p tl a t t i c e b a s e do i lb a s i cc o n c e p ta r ei l l u m i n a t e d i no r d e rt oi m p r o v ee f f i c i e n c yo fa l g o r i t h m s ， b i n a r yo p e r a t i o ni su s e dt oc a l c u l a t et h ec o n c e p t s t h er e d u c t i o nm e t h o do fc o n c e p tl a t t i c e t h i sp a p e rp r e s e n t st h ed e f i n i t i o na n d n a t u r e so fa t t r i b u t ei m p o r t a n c ei nc o n c e p tl a t t i c e ，a n da c c o r d i n g l yi l l u m i n a t e sa na t t r i b u t er e d u c t i o na l g o r i t h mo fc o n c e p tl a t t i c e t h e r ea r ean u m b e ro fe f f i c i e n tc o n s t r u c - t i o na n dr e d 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 e ，b u tt h ec o n s t r u c t i o na n dr e d u c t i o n o fc o n c e p tl a t t i c ea r es e p a r a t ei nm o s to ft h e s ea l g o r i t h m s ，w h i c ha r ed i f f i c u l tt op l a y t h e i rr o l ei np r a c t i c a la p p l i c a t i o n b a s e do nt h ec o n s t r u c t i o na n dr e d u c t i o nm e t h o d o fc o n c e p tl a t t i c e ，t h i sp a p e rp r e s e n t sa na l g o r i t h mo fr e d u c t i o ni nt h ep r o c e s so f c o n s t r u c t i n gc o n c e p tl a t t i c e ab a s i cc o n c e p ti sf i r s tg e n e r a t e da n dr e d u c e di nt h i s a l g o r i t h m ，a n dt h e nt h ep o s t r e d u c t i o nb a s i cc o n c e p ti se m p l o y e dt oc o n s t r u c ta l lt h e c o n c e p t st oo b t a i nt h ep o s t r e d u c t i o nc o n c e p tl a t t i c e t 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 b a s e do i lt h ea d v a n t a g e so fc o n c e p tl a t t i c e s n a n db pn e u r a ln e t w o r k s ，t h i sp a p e r p r e s e n t sac o n c e p tl a t t i c e - b a s e db pn e u r a ln e t w o r k m o d e l t h em o d e le m p l o y sc o n c e p tl a t t i c et h e o r yt oc a r r yo na t t r i b u t er e d u c t i o no f c o n c e p tl a t t i c ea n dt h e nt h ek e ye l e m e n t sa r ee x t r a c t e d ，w h i c hc a nb eu s e da si n p u to f b pn e u r a ln e t w o r k f u r t h e r m o r e ，t h ec o n c e p tl a t t i c e - b a s e db pn e u r a ln e t w o r km o d e l c a nb es e tu pa f t e rt h es a m p l et r a i n i n go fb pn e u r a ln e t w o r k f i n a l l y , t h er e s u l t s o fs i m u l a t i v ee x p e r i m e n ts h o wt h a tt h em o d e lc a ns i m p l i f yt h eb pn e u r a ln e t w o r k t r a i n i n gs a m p l e ，o p t i m i z et h eb pn e u r a ln e t w o r ks t r u c t u r ea n da l s oe n h a n c et h es t u d y e f f i c i e n c ya n dp r e c i s i o no ft h es y s t e m k e yw o r d s ：c o n c e p tl a t t i c e ；c o n s t r u c t i o n ；r e d u c t i o n ；n e u r a ln e t w o r k m 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 目录 第一章绪论1 1 1 课题背景1 1 2 国内外研究现状2 1 3 研究工作及成果4 1 4 本文的组织结构4 第二章概念格5 2 1 基本概念5 2 2 概念格的性质7 第三章概念格的构造9 3 1 概念格经典构造算法介绍9 3 2 基于基本概念的概念格构造算法9 3 3 概念格构造算法的进一步改进1 7 3 4 本章小结2 2 第四章概念格的约简2 3 4 1 概念格约简简介2 3 4 2 概念格属性约简的相关定义2 3 4 3 概念格属性约简算法2 4 4 4 概念格构造与约简结合算法2 9 4 5 本章小结3 2 第五章形式概念的应用3 3 广西大学硕士 5 1 5 2 5 3 5 4 本章小结4 0 第六章结论和展望4 1 参考文献4 2 致谢4 6 攻读硕士学位期间撰写论文情况4 7 附件一4 9 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 i i 课题背景 第一章绪论 概念格的理论与方法最早由德国的w i u e r 于1 9 8 2 年提出，它是一种可用于数 据分析、知识表示和信息管理等方面的理论方法，目前该理论己在许多领域取得了非 常成功的应用，并仍具有很好的应用价值对这一理论及其应用的研究可以大致分为 两个阶段 。 从概念格理论与方法提出后的十五年左右的时间里，对其的研究主要集中在德 国几位学者中间这一时期的研究主要在理论方面，对相关问题的描述、分析和论证 多采用数学的，抽象的方法；与此同时，概念格理论与方法在德国的几个大型项目中取 得了成功的应用，其中包括著名的t o s c a n a 系统等 最近的十几年里，有关概念格理论及其应用的研究，在国际上得到了广泛关注 导致这种变化的原因是多方面的，其主要原因是信息科学的迅速发展，同时概念格理 论中的某些数据结构也为信息科学的研究提供了一些基本而有效的信息表示方法例 如，在知识发现中，概念格理论与方法中的核心数据结构一概念格，可以将数据有机 的组织起来，格中的结点体现了概念内涵和外延的统一，因此非常适合用来发现规则 型知识 概念格( c o n c e p tl a t t i c e ) 是概念格理论与方法中的核心数据结构其中如何高效 率地生成概念格是概念格理论与方法在其应用过程中首先要解决的一个基础性问题， 一直以来都是概念格理论与方法中的重要研究内容，国内外许多学者对此进行了研究， 提出了很多包括概念格生成算法等一系列成果然而，概念格作为数据分析和知识获 取的工具，也存在着一定的不足，主要的问题之一是概念格的生成结构规模过于庞大 如何根据不同需要对其进行约简，也是概念格理论与方法在其应用过程中要解决的一 个问题随着人们对概念格理论与方法研究的深入，其应用范围不断扩大能不能再 将概念格应用到更多的领域，也是值得研究的一个问题 目前，概念格被从事数据挖掘研究工作的国内外专家学者们一致认为是进行数据 分析的有力工具，同时已在各个领域获得了广泛应用，并且以其独特的优势正在赢得 越来越多学者的关注有关概念格的国际会议( i n t e r n a t i o n a lc o n f e r e n c eo nc o n c e p t u a l s t r u c t u r e ，i c c s ) 每两年举行一次，自1 9 9 2 年以来已经成功举办了9 届，这使得概念 l 格的基础知识，为国内外学者研究概念格及其在各个领域中应用提供了基础现在该 书的中文版【2 】已经由辽宁科技大学马垣、张学东等主持翻译并出版，此书为国内的研 究者提供了更加便利的研究条件 目前，概念格理论的研究主要集中在以下几个方面： ( 1 ) 概念格的构造从形式背景构造概念格的过程实际上是一种概念聚类过程由 同一形式背景所生成的概念格是唯一的构造概念格算法可以分为批处理算法和增量 算法两类 3 - 5 其中，批处理算法根据其构造概念格的方式不同，又可以分为三类：自 底而上算法，从顶向下算法和枚举算法而增量算法的思想基本上都是大致相同的，其 基本思想是将当前要插入的对象与概念格中所有的概念做交运算，根据交运算的结果 采取不同的处理，主要区别在于连接边的方法h ot b 研究了基于概念格的概念聚 类算法，并实现了一些学习系统，如o s h a m h 6 和i n c o s h a m t 国内的研究主要集 中在非经典概念格的构造 8 - - 1 1 】和对现在构造算法的改进 1 2 - 1 6 两个方面 ( 2 ) 规则提取由于形式概念分析以概念格的形式使数据有机的组织起来，概念格 节点反映了概念内涵与外延的统一，节点间关系体现了概念之间的泛化和例化关系，因 此用来发现规则型知识非常适合，概念格上提取的规则与其他分类器相比具有相当或 更好的分类效果已有不少学者讨论了从概念格提取规则或函数依赖的问题g o d i n r 等给出了在增量式建格算法基础上用概念格来提取蕴涵规则的算法【硎，其基本思 想是由系统生成当前节点的所有幂集，并检查其是否包含在其父节点中，若有，则生 成以该集合为前件的规则m i s s a o u ir 等提出了近似蕴涵规则的提取算法【1 8 】；h uk y 提出了一种在概念格上提取分类和关联规则的集成算法【捌此外，国内也有不少 学者提出了几种规则提取的算法 2 0 - - 2 2 】 ( 3 ) 概念格属性约简概念格属性约简使得形式背景中隐含知识的发现变得更容 易，也使得这些知识的表示变得更简单，这对概念格理论的研究和应用都有重要的意 2 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 义概念格约筒就是在保持对象集不变的前提下，寻找最小的属性集，它能够完全确 定形式背景上的概念及其层次结构，也就是说这个最小属性集确定的概念格与全体属 性集确定的概念格同构目前，国内外学者提出了基于可区分矩阵 2 3 - - 2 5 、映射1 2 7 _ 2 9 】、 粗糙集理论【2 3 一、形式背景【3 l 】的概念格属性约简方法，对于概念格属性约简方法的 研究是一个年轻并在高速发展的领域，急待完善 ( 4 ) 应用概念格理论已成功地应用于数字图书馆及文献检索、软件工程、知识发 现等领域，而且已取得了良好的经济效益和社会效益【3 2 一删如c o l er 等将概念格方 法应用于分析和可视化具有1 9 6 2 个属性和4 0 0 0 个处方摘要的医药数据库【3 5 】；e k l u n d p w 等展示了概念格层次进行w e b 文档索引和导航的能力【笳】；c o l er 等的c e m 电 子邮件管理系统通过将e m i a l 存储在概念格中，而不是常用的树状结构中，从而在检 索电子邮件时获得了更大的灵活性 3 7 1 ；f e r n a n d e z - m a n j o nb 等则将概念格应用于智能 帮助系统的领域建模【3 8 1 ( 5 ) 其它方面在概念格的简化方面，由于概念格中的节点数是指数增长的所以 在大型数据库的情况下，控制概念格中的节点的增长是非常有必要的概念格的简化 即对概念格进行修剪以控制其中节点的增长【4 7 】一般的，不同的建格算法所采用不同 的修剪方法比如，建格的批处理算法b o r d a t 是通过先引入一个节点的支持度门限， 在建格过程中对于支持度小于门限的节点不予继续展开而达到剪枝的目的而增量算 法的情形就相对复杂，由于必须维护格的特性，修剪只能从格的底部开始进行；在 背景网络下的概念格研究方面，w i l l er 在文献【鸫】中指出，有时候仅考虑一个形式背景 是不够的，因此他提出了背景网络的形式方法，并以此为理论依据，f a i dm 等以不同 形式背景的对象集和属性集之间的关系为基础，研究了在概念格框架结构下对复杂对 象所进行的概念学习和规则提取【4 9 - 别在概念格模型的推广方面，已有学者从不同 的角度提出了几种模糊概念格模型【5 1 】； 在概念格构造方面，已有的研究主要集中在对现有算法的改进和非经典概念格构 造，本文将从概念间的内在关系出发，利用基本概念构造概念格在概念格约简方面， 大多算法是在已有概念格的基础上进行约简，概念格的构造和约简分别进行的，在实 际应用中难以发挥其作用而本文从基本概念的角度出发，提出了一种在概念格构造 过程中进行约简的算法在应用方面，将概念格和b p 神经网络进行融合，从一个新的 角度探索概念格的应用 3 第三章概念格的构造首先简单介绍了概念格的经典构造算法；批处理算法、渐 进式算法及国内现有算法然后，本文提出了一种基于基本概念的快速生成概念的算 法和一种改进的概念格构造算法 第四章概念格的约简首先简单介绍了目前对于概念格进行约简的主要方法给 出了一种基于属性重要性的概念格约简算法，最后结合概念格的构造，进一步完善了 概念格约简算法，实现了概念格的构造和约简同时进行的算法 第五章形式概念的应用首先介绍了形式概念分析的核心数据结构概念格的 应用领域然后分析了神经网络和概念格的优缺点并以此为基础把神经网络与概念 格融合，改进了神经网络算法 第六章结束语总结本文的研究工作 4 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 第二章概念格 概念格理论与方法是以数学化的概念和概念层次为基础的应用数学领域，它激 发了人们对概念数据分析和知识处理的数学思考 “概念的基本观点是由哲学理论中的概念发展而来的：在哲学中，概念被理解为 由外延和内涵两个部分所组成的思想单元基于概念的这一哲学理解，德国的w r 教 授于1 9 8 2 年提出了概念格理论与方法这一理论，用于概念的发现、排序和显示在概 念格理论与方法中，概念用一有序对( x ，b ) 来表示，概念的外延被理解为属于这个概 念的所有对象的集合x ，而内涵则被认为是所有这些对象所共有的特征( 或属性) 集 b ，这样就实现了对概念的哲学理解的形式化所有的概念连同它们之间的泛化例化 关系则构成一个概念格，其相应的h a s s e 图实现了对数据的可视化近二十年来基于 概念格系统的各个领域的应用与研究都将有更好地发展 本章主要介绍了概念格的基本知识及概念格的相关性质1 1 , 2 1 2 1 基本概念 定义2 1 称( 以a ，) 为一个形式背景，其中u = 【z 1 ，x 2 ，z n 为对象集，每 个婉a 佗) 称为一个对象；a = 口l ，a 2 ，口m ) 为属性集，每个啦0 m ) 称为一 个属性；j 为u 和a 之间的二元关系，uxa 若( z ，a ) i ，则说z 具有 属性8 ，记为x i a 若用1 表示( z ，a ) i ，用0 表示( z ，o ) 簪，这样形式背景就可以表示为只 有0 和1 的表格 例1 表2 - 1 是来源于外国的一个科教电影“生物和水，的形式背景，表中的对象 是电影中提及的生物，属性是电影所强调的特性一个形式背景可以用一个2 维表来 表示，每一行是一个对象，每一列是一个属性行列的交叉处是1 或0 ，1 表示对象有 属性 其中，a t 需要水，b ：在水中生活，c t 在陆地生活，d t 有叶绿素，e 双子叶，l 单 子叶，9 。能运动， t 有四肢，i 。喃乳 对于形式背景( 仉a ，i ) ，在对象集x u 和属性集b a 上分别定义运算。 5 广西大学硕士学位论文 u口 l 蚂蝗 2 鱼 3蛙 4 狗 5 水草 6 芦苇 7豆 8 玉米 b + = z i z 以 c a b ，x i a ( 2 2 ) v x u ，记 z 为矿；v a a ，记 口) + 为a + 如果v z 矾z + 圣，z 4 a 且 v a a ，a 圣，a u ，则称形式背景( 阢a ，j ) 是正则的 定义2 2 设( 阢a ，j ) 为形式背景如果一个二元组( x ，b ) 满足x + = b 且b + = x ，则称( x ，b ) 是一个形式概念，简称概念其中x 称为概念的外延，b 称为概念的内 涵 例2例1 中令( x ，b ) = ( 7 ，a c d e ) ，由于矿= a c d e ， a c d e + = 7 于是称僻，b ) 是概念若令( x ，b ) = ( 6 7 8 ，c d e ) ，由于 6 7 s = 口以) b ，则我们说( x ，b ) 不是概 念 形式背景( 阢a ，) 的概念可以用超概念与亚概念的关系来定义它们之间的序关 系t ( 噩，b 1 ) ( x 2 ，b 2 ) 铮x 1 恐( b 2 冬b 1 )( 2 3 ) 则“”是一个偏序关系，( 阢a ，j ) 的所有概念的偏序集记为l ( 阢a ，i ) ，称为概念 格。其中( x 1 ，b 1 ) 叫作( 拖，岛) 的亚概念，( 恐，岛) 叫作( x 1 ，b 1 ) 的超概念 6 ( 6 ) ( x ，x “) 和( b ，b ”) 都是概念 证明： 1 ) 设任意a 弼，则任意刃x 2 都有( z ，a ) i ，但x lg 恐，所以任意z x 1 ， 也有( z ，a ) i 即a x t 故弼舛同理可证b 1 b 2 号噬研 2 ) 设任意z x ，a x + ，则有( z ，a ) i 这意味着任意a x + ，都有( z ，a ) i ， 所以z x ”故x x “同理可证b b ” 3 ) 首先由2 ) 知x + ( x + ) ”，其次xgx ”，由1 ) 得( x “) + x + ，故x + = x ”+ 同理可证b + = b “4 下证x b 兮b x + ，x b 对任意z x ，任意a b ， 有( z ，回i 成立对任意a b ，任意z x ，有( z ，a ) i 成立b x 4 ) a ( x 1u 恐) 。兮( z ，o ) i ( 对任意z x 1ux 2 ) 兮( z ，a ) ，( 对任意z x 1 或 x 2 ) ，n 埘且a 鹭铮a ( 嚣n 弼) 同理可证( b lu 3 2 ) k 研n 彩 5 ) 先证( x lnx 2 ) + 2x tu 弼 对任意a x fu 弼兮( z ，a ) i ( 对任意z x 1nx 2 ) 冷a ( x t nx 2 ) 同理可证( b 1ub 2 ) 2 研n 筋 7 广西大学硕士学位论文( 2 0 1 0 年)概念格的趋堡! 塑箜垦羞壁旦墅窒 6 ) 由性质3 ) ，有( x 木木) 木- - x 木，由概念格定义易知“，x ) 是概念同理可证 ( b + ，b ”) 是概念 8 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 第三章概念格的构造 3 1 概念格经典构造算法介绍 在概念格的应用过程中，概念格的构造效率始终是一大难题，概念格的构造问 题是形式概念分析应用的前提由于概念格的时空复杂度是随着形式背景的增加而指 数性的增大，有关概念格的生成问题一直是形式概念分析应用研究的一个重点自从 g o d i n 提出渐进式构造概念格以来，有关概念格的构造算法及其算法改进的研究一直 没有停止过因此，研究概念格的构造算法十分重要已经有许多文献提出了概念格 多种的构造算法，这些算法大致可分为两类：批处理构造算法和渐进式构造算法但 大多算法计算量大，计算复杂，需要寻找更高效的算法 3 2 基于基本概念的概念格构造算法 本节通过研究概念的性质，给出并证明了反映概念间关系的几个定理，提出了两 种基于基本概念的渐进式概念格生成算法 3 2 1 算法原理 命题3 1 对于形式背景( u , a ，i ) ，任意a a ，( 矿，a ) 是概念的充分必要条件是 a $ = a 命题3 2 对于形式背景( u , a ，i ) ，任意z x ，( z + ，x ) 是概念的充分必要条件是 z = z 定理3 1 对于形式背景( u , a ，i ) ，任意a a ，( 矿，矿+ ) 是概念，特别地，若a = a ， 则概念( a + ，矿) 可表示为( a ，n ) ，即概念( a ，a “) 和概念( a ，a ) 可统一表示为( a 4 ，8 ”) 定理3 2 对于形式背景( 阢a ，j ) ，任意z a ，( z ”，矿) 是概念，特别地，若z = z ， 则概念( z 村，z + ) 可表示为( z ，矿) ，即概念( z ”，矿) 和概念( z ，z + ) 可统表示为( z ”，z + ) 为了叙述方便，对于形式背景( 阢a ，) ，我们引入以下记号； b l a = ( 矿，口) i 任意a 舢= ( o + ，n ) l 任意a a 且a ”= o u ( n + ，a ”) l 任意 o a 且a n ) b l a a = b i 其中，b ) b l a 9 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 b l o = ( z ”，z + ) i 任意z u ) = ( z ，z ) i 任意z u 且矿= z ) u ( 矿+ ，矿) i 任意 z u 且z + + z 】 b l 0 0 = x l 其中( x ，b ) b l o 分别称b l a 和b l a a 为基于属性的基本概念集和基于属性的基本概念的属性集， 简称属性基本概念集和属性基本概念属性集，分别称b l o 和b l 0 0 为基于对象的基 本概念集和基于对象的基本概念的对象集，简称对象基本概念集和对象基本概念对象 集属性基本概念集和对象基本概念集统称基本概念集，其元素称为基本概念 定理3 3 设伍，b ) 为概念格l ( 阢a ，j ) 中的任意一个概念，则b 可表示为若干属 性基本概念的属性的并，即b = u a i ，其中a i b l a a 证明s 设存在bgb l a a ，使b = ( u a i ) ub ，其中a i b l a a 由于( x ，b ) 是概念，故 有x = b = ( ( u a i ) u6 ) + = ( n a i + ) nb + ，x + = ( b + ) + = ( ( n a i ) n6 + ) + 2 ( u a i ”) ub “= ( u a i ) ub 3 ( u a i ) ub = b ，即x + 3b 这与( x ，b ) 是概念相矛盾，故b b l a a 定理3 4 设伍，曰) 为概念格l ( 仉a ，j ) 中的任意一个概念，则x 可表示为若干对 象基本概念的对象的并，即x = u x i ，其中x i b l 0 0 证明：设存在y 隹b l 0 0 ，使x = ( u x i ) uy ，其中x i b l 0 0 由于( x ，b ) 是概念，故 有b = x + = ( ( u z i ) u3 ) + = ( n x i ) n y 4 ，b = ( x ) + = ( ( n z i ) n 可) 。( u x i + ) u y + + = ( u x i ) uy 料3 ( u x i ) u 秒= x ，即b + ) x 这与( x ，b ) 是概念相矛盾，故y b l 0 0 定理3 5 设伍，b ) 为概念格l w , a ，i ) 中的任意一个概念，则( x ，b ) 可表示为若 干属性基本概念的交，即( x ，b ) = a ( a i + ，a i ) ，其中( 舐+ ，a i ”) b l a 证明；由定理3 3 ，设概念( x ，b ) = ( x ，u a i ) ，其中0 4 b l a a 一方面，因为x = b + = ( u a 0 = n a i + ，即x = n a i + ，b = x 。= ( n a i 4 ) 。故 ( x ，b ) = ( n a i + ，( n a i + ) + ) 另一方面，a ( a i + ，a i ”) = ( n a i 。，( u a i ”) 料) = ( n a i + ，( m a i 料) + ) = ( n a i ，( n a i + ) + ) 所以 ( x ，b ) = ( o t + ，a i ”) 定理3 6 设伍，b ) 为概念格l ( 阢a ，) 中的任意一个概念，则( x ，b ) 可表示为若 干对象基本概念的并，即( x ，b ) = v ( z ”，z + ) ，其中( z 料，矿) b l o 证明；由定理3 4 ，设概念僻，b ) = ( u x i ，b ) ，其中甄b l 0 0 一方面，因为b = x + = ( u z i ) + = n x i ，即b = f l x i * x = b 4 = ( n x i + ) + 故 1 0 广西大学硕士学位论文( 2 0 1 0 年) 概念格的构造、约简及其应用研究 伍，b ) = ( ( n x i + ) ，n x i ) 另一方面，v ( 捌”，x i ) = ( ( u x i ”) 料，n x i + ) = ( ( n x i ”4 ) + ，n x i + ) = ( ( n x i ) ，n x i ) 所以 ( x ，b ) = v ( x i ”，x i + ) 3 2 2 算法的实现 由定理3 5 和定理3 6 可知，任意的概念可由属性( 对象) 基本概念生成因此，算 法的基本思想是先求属性( 对象) 基本概念，再由基本概念生成其它概念，由于在生成 新的概念进行集合的交运算时，对象集( 属性集) 会不断变小，而对象集( 属性集) 是有 限，故当对象集或属性集交为空时，算法结束根据以上思想，可以得到以下的概念格 构造两个算法 基于基本概念的概念格建立算法基本步骤 输入。形式背景 输出：输出概念格 s t e pls 对眈u 和a i a ，分别求z 矿和崩 s t e p2s 对a i a ( x i u ) ，求a i ( z ；+ ) s t e p3 ：求出基本概念 s t e p4 t 求所有基本概念的交g 年) ，直到对象集( 属性集) 的交为空 s t e p5 ：输出概念格 算法3 1 基于属性基本概念的概念格建立算法 输入。形式背景 输出；输出概念格 初始化 u a i = 【】；用。和l 矩阵形式表示的形式背景 l = 【1 ；存放中间概念 l l = f 】；唏放临时概念 i o k = 【】；唏放已求概念 f o ri = i - m m 为形式背景对象数 f o rj = 1 ：n n 为形式背景对象数 i fu a i ( i ，j ) = - - - - 1 1 1 w h i l el 不为空集 2 4 l k - 空集； 2 5f o ri = 1 ：il f o r 卢i + 1 ：lli 2 7i f ix i i 1a n dix ji 1a n dx inx j 不为空集( 其中( x i ，b i ) ，( x j ，b j ) 属 于l ) 3 7e n d 3 8e n d 3 9 l = l l ； e n d ex i nx j = u x k ； i f 环在l 的对象集中并且1 ) 。【l 1 l o k - - i d k u ( 殛，【术) = l o k u ( 凇，nx k 奉) ； l l = l l u ( ) 。【，n x k 丰) ； e n d i f 环在蚴对象集中并且1 ) o ( i = 1 l o 脚k u ( 殛，) o “) = l o k u ( 【，nx k 术) ； e n d 9 加 n 抬 培 “ ” 璩 协 乱 船 鹞 ； 船 弘 广西大学硕士学位论文( 2 0 1 0 年) 概金堑堕垫孳、丝堕垄基壁旦堑窒 e n d - 输出所有概念l o k 算法3 2 基于对象基本概念的概念格建立算法 输入：形式背景 输出。输出概念格 l b e g i n 2 i 木= 空集； 3 j 枉空集； 。 b k 空集；( b l 为基本概念集) 5f o ri = lt oi n ( m 为对象个数) e f o rj = lt on ( n 为属性个数) r i fm ( i ，j ) = 1 i 车= i 木ui j 车= j 幸uj) 8 ) 9f o ri = lt om ( 求基本概念) 1 0 l l 计算i 水木； 1 2i fi 宰木= i t s t k 成概念( i ，i 丰) b l = b l u ( i ，i 木) ) 1 4e l s e t t 成概念( i ，c 木，i 掌) b l = b lu ( i 木幸，i 丰) ) 1 6e n d i f 1 7 ) 1 8l u a i - b l - of o re a c h ( x i ，b i ) ，( x j ，b j ) i nl u a i ( 生成所有概念) 乱i f ( x i ，b i ) 与( x j ，b j ) 未进行过并运算且ib i i 1 ，lb j l 1 ，ib i nb jl 不为空集 勉 执行( x i ，b i ) u ( x j ，b j ) 船l i r a i _ l u a iu ( x i ，b i ) u ( x j ，b j ) 2 4e n d i f ) 筇输出概念格l u a i 1 3 广西大学硕士学位论 3 2 3例子 设形式背景如表3 - 1 所示，下面用分别用算法3 1 和算法3 2 来构造它的概念格 下面给出算法3 1 求构造形式背景( 见表3 - 1 ) 相应概念格的过程 s t e p1 ，对各属性和对象计算： 口。= ( 1 2 a ，b + = 1 2 3 ，矿= 1 3 5 ，d + = ( 2 4 6 ，矿= 3 4 ) ，= 5 ) ，9 。= 2 4 ) ，h = 7 ) 1 + = 0 6 c ) ，2 + = a b d g ) ，3 = ( b e e ，4 + = a d e g ，5 + = c ，