（应用数学专业论文）面向对象概念格与面向属性概念格的属性约简理论.pdf

中文摘要 概念格理论，亦称形式概念分析，是德国数学家r w i l l e 于1 9 8 2 年提出的一种用 于概念的发现，排序和显示的数据分析方法在描述具体概念时，不同的刻画方式可以 构造不同的概念格利用粗糙集理论中的近似算子刻画概念的外延以及内涵，y y y a o 提出了面向对象概念格，d u n t s c h 和g e d i g a 构造面向属性概念格对于这两种新的概念 格：面向对象概念格以及面向属性概念格，本文研究了其属性约简问题 本文的主要成果包括以下凡方面： 1 研究并给出了面向对象概念格、面向属性概念格的协调集判定定理，作为判定属 性集是否是约简集的基础；更进一步，得到约简集判定定理 2 在得到了所有概念格约简的前提下，具体分析属性集中每一个属性的特征并且 得出直接判断属性特征的判定定理；以此为基础，给出了面向对象概念格与面向属性 概念格的属性约简集的结构 关键词 面向对象概念格，面向属性概念格，约简，属性特征 a b s t r a c t ( 英文摘要) c o n c e p tl a t t i c et h e o r y , a l s oc a l l e df o r m a lc o n c e p ta n a l y s i s ，p r o p o s e db yr w i l l ei n19 8 2 ，i s am e t h o df o rd a t aa n a l y s i su s e di nf i n d i n g ，o r d e r i n ga n dd i s p l a y i n go fc o n c e p t s w ek n o wt h a t d i f f e r e n tc o n c e p tl a t t i c e sa r ec o n s t r u c t e db yd i f f e r e n td e s c r i p t i o no fc o n c e p t s u s i n gap a i ro f a p p r o x i m a t i o no p e r a t o r s ，y y y md e f i n e dt h eo b j e c to r i e n t e dc o n c e p tl a t t i c e s ，a n d ，d u n t s c h a n dg e d i g a t h ep r o p o s e dt h ep r o p e r t yo r i e n t e dc o n c e p tl a t t i c e s n i st h e s i ss t u d i e st h e r e d u c t i o nt h e o r yo ft h eo b je c to r i e n t e dc o n c e p tl a t t i c e sa n dt h ep r o p e r t yo r i e n t e dc o n c e p t l a t t i c e s ，w h i c hi se a s yt od i s c o v e r yt h eu s e f u li n f o r m a t i o na m o n gt h e m ，a n de l i m i n a t e r e d u n d a n ta t t r i b u t e s t h em a i nr e s u l t sa n di n n o v a t i o n si nt h et h e s i sa r es u m m a r i z e da sf o l l o w s ： 1 f i r s t l y , t h i sp a p e re x p l o r et h ej u d g m e n tt h e o r e m sf o rt h ec o n s i s t e n ts e to ft h eo b j e c t o r i e n t e dc o n c e p tl a t t i c e sa n dt h ep r o p e r t yo r i e n t e dc o n c e p tl a t t i c e s ，w h i c hi su s e dt oj u d g et h e p r o p e r t ys e tc o n s i s t e n to rn o t m o r e o v e r , t h er e d u c t i o nt h e o r e m sa r eo b t a i n e d 2 o nt h ep r e m i s eo ft h ec a l c u l a t i o no fa l ll a t t i c er e d u c t i o n ，w ea n a l y s i se v e r ya t t r i b u t e c h a r a c t e r i s t i co ft h e p r o p e r t ys e t ，a n df i n d t h ej u d g m e n tt h e o r e m sf o rt h ea t t r i b u t e c h a r a c t e r i s t i c a f t e rs t u d y i n gt h ei m p o r t a n c ed e g r e eo fe v e r ya t t r i b u t e ，w ea n a l y s i st h e r e d u c t i o ns t r u c t u r eo ft h eo b je c to r i e n t e dc o n c e p tl a t t i c e sa n dt h ep r o p e r t yo r i e n t e dc o n c e p t l a t t i c e s ，a n dc o n s t r u c ta t t r i b u t er e d u c t i o nb yd i f f e r e n tt y p e so fa t t r i b u t ed i r e c t l y k e y w o r d o b j e c to r i e n t e dc o n c e p t l a t t i c e s ，p r o p e r t yo r i e n t e dc o n c e p tl a t t i c e s ， r e d u c t i o n ，a t t r i b u t e sc h a r a c t e r i s t i c s 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子 版。本人允许论文被垒阅和借l 列。本人授权西北大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编小学位沦义。同l i 、j 授十义r i 困科：学 技术信息研究所等机构将本学位论文收录到中国学位论文全文数 据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 量! 】熔蔓指导教师签名：丞丝! 加加年多月r 日 劢抨石月，日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和 致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成 果，也不包含为获得西北人：学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明j i ：表示驸意。 学位论文作者签名：到锄 为7 9 年占rs目 西北大学硕_ i 二学位论文 第一章绪论 1 1 研究背景 概念是人类进行知识表达的一种手段，知识是人类认识客观世界的结果，同 时也是人们指导自己行为的准则，人们可以从不同途径获取知识、发现知识 知识发现，它是从数据集中识别正确、新颖、有潜在应用价值以及最终可为 人们理解的模式的方法，数据库知识发现的过程就是将数据库中蕴含的知识形式 化成有用概念的过程，是人工智能的核心问题自从1 9 8 9 年8 月在美国底特律召 开的第1 1 届国际人工智能联合会议作为专题讨论以后，知识发现或者说数据库中 的知识发现备受重视 在信息技术飞速发展的今天，信息系统中的信息量膨胀迅速，冗余信息繁杂， 如何从大量数据中提取有效信息并能为人们所利用和理解这一研究领域和课题就 显得尤为重要去除大量冗余信息有利于准确而快速地提取有效信息，有利于高效 地做出正确的决策 在哲学中，概念被理解为由外延和内涵所组成的思想单元基于概念的这一 哲学理解，德国数学家w i u er 于1 9 8 2 年首先提出了形式概念分析用于概念的 发现，排序和显示【1 1 形式概念分析理论是一种基于概念和概念层次的数学化的 表达，它是根据数据集合中对象与属性之间的二元关系建立的一种概念层次结 构，概念格结构模型是形式概念分析理论中的核心数据结构，生动简洁地体现 了概念之间的泛化和例化关系【9 】所有的概念同它们之间的泛化以及例化关系 构成一个概念格，概念格的每个节点是一个形式概念其相应的h a s s e 图则实现 了数据的可视化因此，概念格被认为是进行数据分析的有力工具 近些年来，概念格理论的研究主要集中在概念格的建造f 2 】，概念格的简化f 12 1 ， 规则提取背景网络下的概念格研究等方面，并且已取得了良好的经济效益和社 会效益，比如应用于知识工程、数据挖掘、信息检索数字图书馆以及文献检索 等【1 8 加, 4 0 1 n e u s s 和k e n t 使用概念格进行i n t e m e t 上文档元信息的自动分类和分 析他们讨论的两个著名的资源发现服务w h o i s + + 和h a r v e s t ，都可以包含 在一个基于概念格的更为一般和具有良好结构的方法中；e k l u n d 将概念格方法 应用于分析和可视化具有1 9 6 2 个属性和4 0 0 0 个处方摘要的医药数据库；e k l u n d 和m a r t i n 展示了概念层次进行w e b 文档索引和导航的能力，描述了一个基于概 第一章绪论 念格的工具w e b k b ，提供了一种形式语言，用来描述概念的语义及概念间的层 次关系；k e n t 和b o w m a n 建造了基于概念格的用于数字图书馆的系统n e b u l a 除 此之外，还在软件工程领域广泛应用，c o r b e t t 和b u r r o w 提出使用概念格表示建 筑早期设计软件支持环境中的状态图的表示，使得设计中获得的知识可以重用； s i f t 和r e p s 提出可以使用概念格方法识别以往程序代码中的潜在模块；g o d i n 和m i n e a u 等人描述了使用概念格方法从现存软件系统中生成和检索摘要的方法 1 6 , 1 7 , 1 9 , 2 0 2 2 之9 1 他们通过两个重要的软件重用过程演示了该方法的有用性，给人 们的生活工作带来了便利概念格理论自提出到现在，以其内在的优势吸引越来 越多的科研工作者的关注，迅速在多个领域得到发展 同时，针对知识发现的研究问题，粗糙集理论及方法也是一种较为有效的方 法这个理论是波兰数学家z p a w l a k 予1 9 8 2 年提出的一种分析数据的数学理论， 是一种研究不精确不确定性知识的工具到1 9 9 1 年，z p a w l a k 的专著( ( r o u g hs e t s ： t h e o r e t i c a la s p e c t so fr e a s o n i n ga b o u td a t a ) ) 的问世标志着粗糙集理论及其应用的 研究进入了活跃时期目前粗糙集理论已经成为信息科学最为活跃的研究领域 概念格理论与粗糙集理论是两种不同的数据分析方法，它们从不同的角度研 究数据集合中所隐含的知识，都已被成功的应用于许多领域概念格理论的数据表 现方式是形式背景，其研究基础是概念格；而粗糙集理论的数据表现方式是信息 系统，其研究基础是对象间的等价关系虽然是两种不同的理论，但有许多相似之 处，而且有很多研究者将二者结合起来研刭5 6 1 ，便于我们更好的分析和理解数据 利用粗糙近似算子定义了两个外延与内涵平衡的条件，y y y a o 提出了面向对象概 念格，d “u n t s c h 和g e d i g a 构造了另外一种新的概念格一面向属性概念格得到了 两种新的概念格：面向对象概念格和面向属性概念格，丰富了概念格理论，为数 据分析提供了新的理论依据b o , 1 1 概念格理论和粗糙集理论自提出以来，其内在的优势得到越来越多的科研工 作者的注意，并在多个领域得到迅速的发展和广泛的应用然而概念格理论的研究 仍是一个极其年轻、发展迅速的领域，有很大的发展前景和应用潜力，进一步的 研究方向包括：实际知识发现任务中高效的构造概念格算法及剪枝算法；拓广格 中概念；从概念格上产生有用的规则，还有其他的数据挖掘、知识发现中的应用； 各种概念格约简的统一框架问题；概念格中的属性依赖性分析和属性重要性问题； 决策形式背景的知识发现问题；决策形式背景中对基于概念格的规则提取；基于 2 西北大学硕上学位论文 概念格的知识发现的不确定分析研究目前还比较少，随着对复杂系统的深入研究， 新的不确定性问题也随之产生，讨论在保持一些特定的不确定性度量下的知识约 简成为概念格数据分析不可避免的问题等等【1 3 , 1 4 , 1 5 , 2 1 1 近些年来，大型数据库中的数据挖掘的粗糙集方法已经提出来了，其中包括 综合缺省规则、综合近似推理模式以及建立从数据提取更高层的知识等方法，是 很有前景的研究领域7 , 8 , 3 0 。3 ，3 6 1 1 2 本文研究内容与安排组织 本文以形式背景为研究对象，研究了面向对象概念格和面向属性概念格的约 简理论与方法，分析了形式背景的属性特征，提出了约简集的构造方法 全文共分六章，各章主要内容组织安排如下： 第一章：阐述了概念格理论的研究背景和研究现状，指出本文的研究内容、 内容安排以及主要成果 第二章：介绍概念格的约简理论给出形式背景、经典概念格、经典协调集、 经典约简集等相关的定义 第三章：研究面向对象概念格和面向属性概念格的约简理论，从介绍面向对 象概念格和面向属性概念格出发，提出了面向对象协调集、面向属性协调集，面 向对象约简集、面向属性约简集的相关定义，得到了一系列面向对象协调集、面 向属性协调集的判定定理，最后，根据面向对象概念格与面向属性概念格的关系， 得出面向对象约简集、面向属性约简集的判定定理 第四章：根据形式背景中属性的重要性研究概念格不同类型属性的特征，将 属性分为：核心属性( 绝对必要属性) 、相对必要属性和绝对不必要属性，进而， 研究得到了三种不同类型属性的判定定理 第五章：以形式背景属性特征的分类为基础，分析面向对象约简集( 面向属性 约简集) 的结构，进一步得到属性约简集的构造方法 最后对全文进行总结，并提出了进一步可研究的方向 3 第二章经典概念格及其约简理论 第二章经典概念格及其约简理论 知识发现的一个重要分支就是知识约简，在概念格理论的研究过程中，张文修与魏 玲等人于2 0 0 5 年首次较为完整的研究了基于格同构的概念格知识约简和知识发现的问 题，研究获得了形式背景在概念格同构意义下的属性约简理论与方法【1 2 , 1 3 弦3 引 本章主要介绍经典概念格的属性约简理论，并得到了一些有意义的结论 2 1理论基础 定义2 1 t 3 8 1 设尺是集合x 中的二元关系，如果r 满足： ( 1 ) 自反性：x r x ( v x x ) ： ( 2 ) 反对称性：x r y ，y r xjx = y ( v x ，y x ) ； ( 3 ) 传递性：x r y ，y r zjx r z ( v x ，y ，z x ) ； 则称r 是x 上的偏序关系，通常用符号“”记偏序关系r 集合x 和集合x 上的一 个偏序关系一起构成的有序对称为偏序集，记为( z ) 定义2 2 t 3 8 1 偏序集( z ) ，qsx ，a x 如果对于任意x eq ，总有x 口，则 称口为集合q 的一个上界； 如果对于任意xeq ，总有a x ，则称a 为集合q 的一个下界 如果集合q 的所有上界组成的集合的最小元存在( 若存在，则必唯一) ，则称该最 小元为集合q 的最小上界，或者上确界； 类似的，如果集合q 的所有下界组成的集合的最大元存在( 若存在，则必唯一) ， 则称该最小元为集合q 的最大下界，或者下确界 定义2 3 t 3 8 1 设( x ，) 是偏序集，如果对于任意a ，b x ，都有下确界a 6 和上确 界a v b 存在，则称( x ，) 是格，通常简称x 是格 定义2 4 网设( x ，) 是格，ysx ，y a 如果对于】，中任意元素a 和b 都有 aa b y ，a v b y ，则称】，是x 的子格 2 2 经典概念格保持格结构不变的属性约简 概念格理论所分析的数据一般用形式背景来描述，设u 是数据库中所有数据的集 合，通常称为论域，么表示数据库里的数据特征或者属性 定义2 5 3 7 1 三元组丁= ( u ，a ，r ) 是一个形式背景，其中u = x t ，x 2 ，矗 为对象集， 每个而( f 忍) 称为一个对象，a = a l , a 2 ，以。) 为属性集，每个口，( _ ，聊) 称为一个属性， 4 两北大学硕士学位论文 r 是对象集u 和属性集4 之间的二元关系集，且r u x a 在形式背景t = ( u ，a ，尺) 中，如果( 工，口) r ，则称对象x 具有属性a ，记为x r a 通 常在二值背景中，用1 表示( x ，a ) r ，用0 表示( x ，a ) 萑r ，这样形式背景可以表示成只 有0 和l 的表格 例如，表1 是一个形式背景，其中对象是病人甲、乙、丙、丁，属性是关于是否咳 嗽、流鼻涕、头疼、体温高这四个症状性质，第f 个对象具有第，种属性在表中对应的 位置用1 表示，用0 表示第f 个对象不具有第歹种属性 表1 形式背景 对于形式背景t = ( u ，a ，r ) ，在对象集栅u 和属性集v y 互a 上定义运算 定义2 6 t 3 7 1 对于任意的x 互u ，x = yi ) ，彳， q xex ，x r y ) ；对于任意的】，sa ， ，= x i x u ，砂y , x r y 显然，表示对象集石中所有对象所共同具有的属性集，矿 表示共同具有y 中所有属性的对象集 若v x u ，f 2 j ，a ，而且v 口a ，a + a ，a u ，则称形式背景r = ( u ，a ，r ) 是正则的其中，工+ 表示 工 + ，a + 表示缸) 定义2 7 1 3 7 1 形式背景丁= ，a ，尺) ，如果对象集栅u 和属性集v 】，彳组成的二 元组( x ，即满足x = ，一且，= x ，则称( x ，”是一个形式概念，简称概念其中，彳称 为概念的外延，y 称为概念的内涵 用三( u ，a ，r ) 表示形式背景t = ，a ，r ) 的概念全体形式背景t = ( u ，a ，r ) 的基本 性质如下：眠，五，x 量ug v b , ，垦，b a ( 1 ) 五噩jz 墨，置冬垦j 鹾研； ( 2 ) x x ”，b b ”； ( 3 ) x = x ，b = b 一； ( 4 ) x b 营b x ； 5 第二章经典概念格及j e 约简理论 ( 5 ) ( 五u 五) = 墨n 五+ ，( 且u 垦) + = 置n 垦； ( 6 ) ( 五n 五) 2 五u 五，( 墨n b ) 2 蜀u b ； ( 7 ) ( x ”，x ) 和( 口，曰”) 都是概念； 将三( 【，a ，r ) 上的偏序关系定义如下：( 五，尽) ( 置，b p c , x , s 五( 旦2 垦) 其中， ( 五，蜀) 叫作( 置，展) 的亚概念，( 五，垦) 叫作( 五，e ) 的超概念 更进一步，对于( 五，e ) 和( 五，岛) 两个概念，若( 五，蜀) ( 五，垦) ，而且不存在 ( x ，】，) ，( x ，】，) ( 五，且) ，( x ，y ) ( 置，岛) ，使得( 五，蜀) ( x ，y ) ( 置，色) ，则称( 置，蜀) 是( 五，垦) 的子概念，( t ，垦) 是( 五，尽) 的父概念 定义 2 8 m 若( 五，尽) 和( 置，岛) 是概念，则( 五，蜀) 人( 置，垦) = ( 五n 置， ( 骂ub o “) ，( 五，蜀) v ( 五，垦) = f i x , u 置) ”，置n 色) 也是概念，从而缈，a ，尺) 是格，并 且是完备格 定义2 9 1 3 7 1 设l ( u ，a ，r ) 是概念格，其所有概念外延的集合记为 乙( u ，么，r ) = x | ( x ，b ) t ( u ，a ，尺) ) 如果对于两个概念格l ( u ，4 ，蜀) 和l ( u ，4 ，恐) ，有厶( 【，4 ，r ) ，4 ，r ) ，则 称概念格l ( u ，4 ，墨) 和三缈，4 ，垦) 相等，通常记为l ( u ，4 ，墨) = u l ( u ，4 ，是) 如果l ( u ，4 ，置) = u l ( u ，4 ，恐) ，显然有l ( u ，4 ，足) 兰l ( u ，4 ，是) 定义2 1 0 吲设互= 三( 【，4 ，r ) 和互= 三( u ，4 ，足) 是两个概念格，如果对于任意的 ( 五，垦) el ( u ，4 ，r ) ，总是存在( 五，b pel ( u ，4 ，墨) ，使得五= 置，则称l ( u ，4 ，墨) 细 于三( u ，4 ，足) ，通常记为l ( u ，4 ，蜀) 三( u ，4 ，是) 如果l ( u ，4 ，置) l ( u ，4 ，是) ，显然岛( 【，4 ，置) 2 岛( u ，4 ，恐) ，更进一步的，如果 l ( u ，4 ，r ) l ( u ，4 ，r i ) ，那么l ( u ，4 ，置) = c ，l ( u ，4 ，垦) 定义2 1 1 t 3 7 】对于形式背景t = ( 【，a ，r ) ，如果存在d a ，d g ，使得 l ( u ，d ，r n ) = 【，l ( u ，a ，r ) ，则称d 是形式背景t = ( u ，a ，r ) 的协调集若v d d ， l ( u ，d - d ，r n 制 ) 毛l ( u ，a ，r ) ，则称d 是形式背景t = ( u ，a ，r ) 的约简 注：l 、形式背景丁= ( u ，a ，r ) ，d a ，记r n = r n ( u x d ) ，那么乃= ( u ，d ，如) 也是一 个形式背景 2 、运算在形式背景t = ( u ，a ，r ) 中用x + 表示；在t o = ( u ，d ，r n ) 中用x 。表示；显 6 西北大学硕十学位论文 然也= r ，x 一= x + ，x d = x _ n d = x + n d ，x o x 定义 2 1 2 3 7 1 设形式背景丁= ( ，彳，矗) 的所有约简为 d fld f 是约简，i f ) ( f 是指标集) 属性集彳可以分为以下三部分： 绝对必要属性( 核心属性) b ：6 n 皿 相对必要属性c ：c u b n q i e r拓f 绝对不必要属性d ：d 4 一u q 拒f 2 2 例子 例1 ：表2 是一个形式背景互- - ( u ，4 ，蜀) ，+ 其中u = 1 ，2 ，3 ，4 ，5 是对象集， 4 = 口，b ，c ，d ，e , s ，g ) 是属性集 表2 形式背景写= ( u ，4 ，蜀) 该形式背景共有六个概念： ( “) ，和，b ，d ，p ) ，( 托，_ ) ， 口，b ，c ) ) ，( “，而) ，) ) ， ( “，艺，毛 和，妨) ，( u ，囝) ，( a ，彳) 根据父概念和子概念的关系，该形式背景的概念格如下： ( u ，a ) 一八 ( 传，毛 ， 田) ( 五，毛，i j ( 以6 ) l 1 图2 1 l ( u ，a ，r ) 从图中我们可以清楚地看出各概念之间的泛化和例化的关系，充分体现了它的优点 7 第二章经典概念格及其约简理论 ，刀) 。而，毛i a q 溢毛，；田，( 而，毛) ， ) ( 毛，毛：毛) 田) ，卿 一企 ( ( 而，毛 ， d ) )( 五，而： 6 ) ( “) ，1 口，田)( 而，而， d ) ( 0 ，d 1 ) ( “ ， 6 ，田)( 玉，屯， 6 ，c ) 。 ，d 2 ) 图2 2 l ( u ，d l ，) 图2 3 l ( u ，0 2 ，如) 由经典概念格的约简判定定理，获得该形式背景的两个属性约简集：o l = 徊，c ，d ) ， 砬= 6 ，c ，d ) 基于该形式背景的约简集，得到绝对必要属性集( 核心集) ： c ，d ，相对 必要属性集：徊，6 ) ，绝对不必要属性集：泐 8 西北大学硕士学位论文 第三章面向对象概念格和面向属性概念格及其约简理论 y y y a o 提出了面向对象概念格，d “u n t s c h 和g e d i g a 构造了另外一种新的概念 格面向属性概念格得到了两种新的概念格：面向对象概念格和面向属性概念二 格就目前所知，在概念格理论中，没有相关文献研究面向对象概念格和面向属性 概念格的约简理论p o 】 本文给出一般意义下面向对象概念格和面向属性概念格的约简理论，即在保 持对象集不变的前提下，寻找最小属性集，它能够完全确定形式背景上的概念及 其层次结构显然，概念格约简简化了形式背景的知识发现过程，使得形式背景中 隐含知识的发现变得更加一目了然，这使得概念格理论的研究和应用都具有重要 的意义 本章首先介绍面向对象概念格和面向属性概念格的相关定义，在此基础上给 出其约简理论和判定方法 3 1理论基础 定义3 1 t 3 0 】设t = ( u ，a ，月) 是形式背景，在拟u _ l z 定义一对近似算子口，： 2 u 哼2 ，x 。= y ai v x u ( x r yx x ) ) ；x o = y a 3 x e u ( x r y x x ) 对应的，在v y 互a 上定义一对近似算子r l ，o ：2 一专2 u ， p = x ui 砂4 ( x r y = y y ) ) ；y o = x ui 砂a ( x r y y d ) 下面给出近似算子的性质：v x ，置，置u ，v y ，x ，e a ， ( 1 ) 五置j 矸霹，f 墨；x 艺j 罕珂，甲p ； ( 2 ) x 酏x x o 口；y 口o y 互p 。； ( 3 ) x 砒= r ；x 删= x o ；y 口钯= y 口；y = y o ； ( 4 ) ( 五n x 2 ) 。= 矸n 霹；( 墨u 五) o = 砰u 霹； ( xne ) 。= 甲n 珂；( xu r n ) o = z 。ue ； 定义3 2 t 3 0 1 设r = ( u ，彳，尺) 是形式背景，如果对于栅互u ，v ysa ，满足 x = y 。且y = x 。，则称二元组( x ，y ) 为面向对象概念；如果二元组( x ，】，) 满足 x 篁p 和y = x 。，则称( x ，n 为面向属性概念 通常，将形式背景t = ( u ，a ，r ) 上所有的面向对象概念所组成的集合记为 厶( u ，a ，r ) 或厶，记所有的面向属性概念所组成的集合为4 ( u ，4 ，r ) 或4 9 第三章面向对象概念格和面向属性概念格的约简理论 对于形式背景t = ( u ，a ，r ) 上的所有面向对象概念， v ( 五，i ) ，( 五，e ) l o ( u ，a ，r ) ， ( 五，k ) ( 置，蔓) = “五n x 2 ) ”，in e ) ， ( 五，x ) v ( t ，匕) = ( 五u 置，( zn 艺) 钿) 那么, i fz o 是一个格，称为面向对象概念格 同时，v ( 五，x ) ，( 五，艺) 4 ( u ，a ，尺) ，( 五，i ) ( 置，k ) = ( 五n 五，( xn y p 酏) ， ( x l ，x ) v ( 五，e ) = ( ( 墨u 五) o nxu 艺) ，那么4 称为面向属性概念格 例子3 1 表3 是一个形式背景t = ( u ，a ，r ) ，其中u = 1 ，2 ，3 ，4 ，5 是对象集， a = 和，b ，c ，d ，e ，f ，g ) 是属性集 表3 形式背景t = ( u ，a ，r ) 入 广1 l f 图3 1 l o ( u ，a ，r ) 图3 2 l e ( u ，a ，r ) 该形式背景有九个面向对象概念：( u ，a ) ，( 1 2 3 4 ，c d e f ) ，( 1 2 5 ，a b d e g ) ， ( 1 3 4 ，巧) ，( 1 2 ，d e ) ，( 2 5 ，b a g ) ，( 1 ，e ) ，( 2 ，d ) ，( o ，g ) 其概念格如图3 1 所示 该形式背景有九个面向属性概念：( u ，a ) ，( 1 3 4 5 ，a b c e f g ) ，( 2 3 4 5 ，a b c d f g ) ， ( 1 3 4 ，a c e f ) ，( 3 4 5 ，a b c f g ) ，( 2 5 ，a b d g ) ，( 3 4 ，c f ) ，( 5 ，a b e , ) ，( g ，o ) 其概念格如图 3 2 所示 定义3 3 设形式背景丁= ( u ，彳，月) ，d a ，如果易缈，d ，) 气乙( u ，么，尺) ， n o 是面向对象协调集；如果l e ，d ，r o ) = ，l e ( u ，a ，尺) ，n o 是面向属性协调集 1 0 ；， 西北大学硕士学位论文 更进一步，d 是面向属性协调集，v d d 名i l o ( u ，d - d ，珏) 气l o ( u ，a ，r ) ， 则称d 是形式背景丁= ( ，彳，尺) 的面向对象约简集；若 0 缈，d 一) ，如叫 ) 气( u ，a ，r ) ，那么称d 是形式背景丁= ( 【，a ，r ) 的面向属性 约衙集 注：形式背景r = ( u ，a ，r ) ，v dc ：a ，o d ，o d 表示形式背景r = ( u ，a ，r ) 的子背景 r o = ( u ，d ，r o ) 上的一对近似算子显然，v b d ，锻u ，x 吻= fn d ， b o d = b 。 3 2 面向对象概念格保持格结构不变的属性约简 根据定义3 3 ，不难得知形式背景t = ( u ，a ，r ) 的约简集d 需要满足下面两个条 件：( 1 ) d a ，d 是一个协调集； ( 2 ) v d d ，d - d ) 不是协调集 首先，给出一系列判断属性集a 的子集d 是否是面向对象协调集的定理 定理 3 1 设r = ( u ，a ，r ) 是形式背景，d 冬a ，d o 那么 易( 以4 固 对于一个面向对象概念格，有如下的结论： ( 1 ) a 是核心属性 帕一如) ) o a 。 ( 2 ) 口绝对不必要属性营( a 钿一如 ) o = a o 且乃o = a o ( 3 ) a 相对必要属性0 伯一 口) ) 。= a o 且互o a o 证明：( 1 ) 是定理4 2 的逆否命题，显然成立 ( 2 ) 必要性口是绝对不必要属性，因此( a 铀一 n ) ) 。= 口o 必有属性集d 满足 ( a 铀n d ) o = a o 对于任意的b a 钿n d ，必有b a 钿，得知b o 互a o ，同时b d ， 则b a ，那么b 不是绝对不必要属性因此b 。a 。，b 。c 口。，得知0 冬a 。另 一方面，口o = 0 钿n d ) o z o 因此，得证p = 口。 充分性假设口不是绝对不必要属性，必存在约简d ，口d ，且满足 ( a o 口f l ( d 一 口 ”o a 。因为a o d n ( d 一 口 ) a o 。，( a o 口n ( d 一 口) ) ) 。口。= 口o ， 则 o 口n ( d 一缸) ) ) 。ca o 显然，口芒瓦，乏= ( 互n ( d 一 口) ) ) u ( 互n ( a - d ) ) 那么，互o = ( zn 一和) ) ) 。u ( 乙n ( a - d ) ) o ，分下面两种情况讨论： 乏= 6 aib 。c 口。 ， 显然， 乃oc 口o ，所以乏ca 钿因此， ( n ( d n 口 ) ) 。c ( 口。口n ( d n 口) ) ) o v e 乃n ( a - d ) ，显然p 乏，所以p 钿ca o o r a 诺p 钿，又由于e ( a - d ) 且 d 是协调集，所以矿( 产n ( d 一缸) ) ) 。 因此， ( zn ( 彳一d ) ) 。= ( u 力。=u ( 口。0 n ( d 一 口 ) ) 。 * f 1 ( a - o ) * 毛f 1 ( 一d ) 那么，z o = ( 乃n ( d n 扣) ) ) 。u ( r on ( a - d ) ) oc0 0 口n ( d 一 口 ) ) 。妄 0 0 ) 9 - d 。， 与“o = 口矛盾所以假设不成立 1 8 西北大学硕士学位论文 f i t ( 1 ) 和( 2 ) 易知( 3 ) 成立即证 口 4 2 面向属性概念格的属性特征 在3 3 节中，我们得到的结论是：同一背景丁= ( u ，a ，r ) 的面向对象概念格和面 向属性概念格有相同的约简集设其约简为 qib 是约简，f f ) 那么d i ( i f ) 既 是面向对象约简集又是面向属性约简集，根据定义n q 是核心属性；ud f n q 是 拒ff e fl e t 相对必要属性；a - u d , 是绝对不必要属性那么，同一背景丁= ( u ，a ，r ) 的面向对 i e r 象概念格和面向属性概念格有相同的属性分类 总之，同一背景t = ( u ，a ，r ) 的面向对象概念格和面向属性概念格有着相同的协 调集、约简集以及属性分类，因此，4 1 中的所有结论：定理4 1 4 4 同样适用于判断 面向属性概念格属性分类 4 3 例子 再续上面的例子考察如表3 所示的形式背景t = 缈，a ，r ) ( 1 ) a 钿= 1 2 5 。= a b d e g ，( a 把一 口) ) o = b d e g o = 1 2 5 = 口o ，乏= b d e g ) ， p = 口o = 1 2 5 ，因此口是绝对不必要属性 ( 2 ) 6 0 0 = 2 5 ) 。= b d g ，( 6 0 口一 6 ) ) 。= 匆) o = 2 5 = 6 。，乃= f ，乃。= 2 ) b 。， 因此，b 是相对必要属性同理，c ，厂，g 是相对必要属性 ( 3 ) d 钿= d ) ，( d 钿一 d ) ) o = a 。d o ，因此，d 是核心属性同理，e 是核心属 性 由例3 4 所得结论知道形式背景的约简集合：d l = 6 ，c ，d ，e ) ，砬= p ，d ，e ，f ) ， 4 d 3 = c ，d ，p ，g ) ，皿= ，p ，厂，g ) ，根据属性特征的定义：核心属性为n q = 彤，p ) ； 44 4 相对必要属性u 皿一n 口= 6 ，c ，厂，鲥；绝对不必要属性么一u 口= 口) 显然，由两种判断方法得到的结果是一致的 1 9 第五章面向对象概念格与面向属性概念格属性约简集结构 第五章面向对象概念格与面向属性概念格属性约简集结构 根据前面的分析以及研究，易知形式背景的属性特征是由属性约简集定义的， 那么，我们考虑由不同类型的属性来描述属性约简集的结构 5 1 面向对象概念格属性约简集的构造 首先，定义下面几个集合，皿( i f ) 是形式背景t = ( u ，a ，r ) 的全部面向对象 属性约简集，核心属性集c = n 4 ，相对必要属性集s = u 4 一nd i ，k = a - u z ) , 摇fi e r拒f l e t 是绝对不必要属性集 定理5 1 形式背景t = ( u ，a ，r ) ，c ，s 和k 分别为形式背景t = ( u ，a ，r ) 的 核心属性集，相对必要属性集和绝对不必要属性集合那么，对于任意的面向对象 属性约简集d ，a ( j f ) 有以下命题成立： ( 1 ) c 哆； ( 2 ) 若s o ，贝, j i s i 1 ，且qn s o ； ( 3 ) d ，n k = a ； ( 4 ) q c u s ： 证明：( 1 ) c = n 皿哆； i e r ( 2 ) 若s a ，贝j j3 a s 根据定理4 3 ：3 b s ，b a ，s t a o = 矿，得知，b s ， 那么f s l 1 下面证明d ，n s f 2 j ( 反证) 假设存在面向对象属性约简集皿( k e 力，s t 级ns = o 那么，根据定义s = u 4 一n 口，知：q n 4 ，即，q 包含在任 f e f i e ri e r 意的面向对象属性约简集中 于是，存在面向对象属性约简集4 ，s t qcq ，与“q 是面向对象属性约 简集“矛盾因此，s a ，则d ；n s o ( 3 ) k = 彳一u q ，显然bn k = 彩 ( 4 ) c u s = ( u q - n d , ) u ( n q ) ， i e ri e ri e r 由于nd f u 口，那么d c u s 口 l e ti e r 形式背景丁= ( u ，a ，r ) ，v b a ，在属性集b 上定义，全 ( 口，b ) eb x b la 。动o ) ， 2 0 西北大学硕十学位论文 易知，是属性集b 上的等价关系，由等价关系所确定曰上的划分记为 b r n = 【6 】口lb b ) ，其中，【6 】口= a bl ( 口，b ) r n ，b b ) r l 定理5 2s 是形式背景t = ( u ，a ，r ) 的相对必要属性集，记 s b 三 s ，是，s k ：七f ) ，若d 是形式背景t = ( u ，a ，r ) 的面向对象属性约简集 则i d c l s , i = l ( i f ) 证明：( 反证) 假设存在墨s 如，s t