（基础数学专业论文）基于关系的概念格属性约简及集合近似.pdf

摘要 粗糙集理论是波兰数学家p a w l a kz 于1 9 8 2 年提出的一种用于处理不精确 含糊性 和不确定性数据的数学工具 它在现实应用与理论研究中都引起广泛关注 利用粗糙集 理论中上 下近似的概念 挖掘出隐藏在信息系统中的知识 得出决策规则 概念格理 论 亦称形式概念分析 是德国数学家w i l l er 于同一年提出的一种用于概念的发现 排序和显示的数据分析方法 概念格是一个序层次结构 它由数据表中对象和属性间二 元关系产生 每一个概念是一个二元 对象 属性 组 它由两部分组成 外延和内涵 粗糙集理论与概念格理论作为有效的 具有极大潜力的知识发现工具 备受人工智能工 作者的关注 目前 它们正在被广泛应用于数据挖掘 机器学习 模式识别 决策分析 计算机网络 软件工程等领域 知识约简是知识发现的一个重要方面 因此也是粗糙集与概念格理论研究的重要内 容 本文研究概念格属性约简与粗糙近似问题 提出了新的约简方法 给出形式背景下 集合的一种近似方法 本文的主要内容有 1 利用概念格约简中不同类型属性的特征讨 论了形式背景的属性约简 提供了一种从属性类型分析获得概念格约简的方法 2 基于 依赖空间理论提供了形式背景属性约简的一种等价方法 给出了信息系统属性约简的一 种新的判定方法 3 定义了形式背景和决策形式背景的优势约简 通过构造优势可辨识 矩阵 得到了属性约简的一种布尔计算方法 4 研究形式背景下集合的粗糙近似问题 定义了类近似算子 讨论近似算子的性质 并给出它们的公理刻画 关键字 形式背景概念格属性约简依赖空间优势约简类近似算子 a b s t i a c t 1 1 1 et l l e o 巧o fr o u g hs e t sw a l so r i g i n a l l yp r o p o s e db yp a w l a l z i n1 9 8 2 硒am a t h e m a t i c a l a p p r o a c ht oh a i l d l ei m p r e c i s i o n v a g u e n e s s 觚du n c 洲n t y i nd a 舾锄a i y s i s i th 硒r e c e n y r e c e i v e dw i d ea t t e n t i o ni nr e a l 1 i f ea p p l i c a t i o n sa n dt l l e o r e t i c a lr e s e a r c h b yu s i n gm ec o n c 印t so fl o w e r 锄du p p e ra p p r o x i m a t i o n si nr o u g h s e tm e o l i l o w l e d g el l i d d e ni ni n f o 彻a t i o n s y s t e m sm a yb eu i l r a v e l l e da n de x p r e s s e di nm ef o m o fd e c i s i o nm l e s c o n c e p tl a m c et h e o r y a l s oc a l l e df o 肌a lc o n c 印ta n a l y s i s p r o p o s e db yw i u e r i nm es 锄ey e 碣i sam e m o d f o rd a t aa i l a l y s i su s e di nf i n d i n go r d 耐n g 锄dd i s p l a y i n go fc o n c e p t s ac o i l c 印tl a t t i c ei s 锄 o r d e r e d h i e r a r c h ym a ti sd e f i n e d b yab i n a r yr e l a t i o nb e 锕e e n0 b j e c t sa n d 甜曲u t e si na d a t a s e t e a c hf o m a lc o n c e p ti sa no b j e c t a t t r i b u t ep a 址w h i c hc o n s i s t so ft w op a r t s t h ee x t e n s i o n 锄di n t i e n s i o n r e c e n t l y t h et w ot h f i e sh a v eb e e n 印p l i e di nv 碰o u sr e s e a f c ha r e a s s u c ha s d a t am i n i n g m a c h i n el e a m i n g e x p 酣s y s t e m d e c i s i o n 锄a l y s i s c o m p u t e rn e t w o r k s o f t w a r e e n g i n e 耐n g a n ds oo n k h o w l e d g er e d u 嘶o ni s 锄i n l p o n a i l ta s p e c ti nk i l o w l e d g ed i s c o v e 哆i ti sm e r e f o r e 锄 i m p o r t 锄tp a r ti nt 1 1 es t u d yo fr o u g h s e tt h e o 巧a i l df o 肌a lc o n c e p ta n a l y s i s t 1 1 i st h e s i ss t u d i e s a t t r i b u t er e d l l c t i o ni nf o n n a lc o n c 印tl a t t i c e sa n dr o u g h 叩p r o x i m a t i o n so fas e ti naf o 加1 a 1 c o n t e x t 1 1 l em a i nr e s u l t sa i l do r i g i n a l i t i e sa r es u m m 撕z e da sf o l l o w s 1 b ye m p l o y i n gt h ec h a r a c t e r i s t i c so fd i 仃e r e n t 锣p eo f 触u t e w ep r o p o s e am e t l l o do f a t t r i b u t er e d u c t i o ni nc o n c e p tl a t t i c e s 2 f r o mt h ep o i n to f e wo fd e p e n d e n c es p a c e s t w oe q u i v a l e ma p p r o a c h e so f 砌b u t e r e d u c t i o nf o raf b m l a lc o n t e x ta i l d 觚i n f b m a t i o ns y s t e ma r ep r o p o s e d r e s p e c t i v e l y 3 w ei i 帅d u c es o m en e wc o n c e p t so fd o m i n a n c er e d u c t i o ni nf o r m a lc o n t e x ta i l dd e c i s i o nf o m a lc o n t e x t s o m eb a s i cp r o p e n i e so f 血e s ec o n c e p t sa r cd i s c u s s e d a n dam e t h o do f d o m i n a n c er e d u c t i o ni sp r o p o s e db yu s i n gt l l ed i s c 啪i b i l i 哆a t t i i b u t es e t 4 f i n a l l y es t u d yr o u g ha p p r o x i m a t i o n si nf o m a lc o n t e x t s an o v e lc o n c 印to fs i l i l i l 孙 i 够a p p r o x i m a t i o no p e r a t o ri sp r o p o s e d a i l dm ep r o p e n i e so fm ea p p r o x i m a t i o no p e r a t o r sa f e d i s c u s s e d n l e 戚m a t i cc h a r a c t e r i z a t i o no ft t l i so p e r a t o ri st l l e ne x 锄i n e d k e yw o r d s f 0 m a lc o n t e x t c o n c e p tl a t t i c e s a t f i b u t er e d u c t i o nd e p e n d e n c es p a c e s d o m i n a n c er e d u c t i o n s i i i l i l a r i t ya p p r o x i m a t i o no p e r a t o r s 学位论文原创性声明 本人所提交的学位论文 基于关系的概念格属性约简及集合近似 是在导师的指 导下 独立进行研究工作所取得的原创性成果 除文中已经注明引用的内容外 本论文 不包含任何其他个人或集体已经发表或撰写过的研究成果 对本文的研究做出重要贡献 的个人和集体 均已在文中标明 本声明的法律后果由本人承担 论文作者 签名 王硅矬 矽罗年岁月形日 指导教师确认 签名 怍r 旯妒 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘 允许论文被查阅和借阅 本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或其它复制手段保 存 汇编学位论文 保密的学位论文在 年解密后适用本授权书 论文作者 签名 列生撞 纵田夕年夕月膨日 指导教师 签 7 伊 于年矿月0 百 i i 引言 当今世界 任何国家都把拥有知识当作最大的财富 世界级管理大师德鲁克指出 世界上没有贫穷的国家 只有无知的国家 知识的生产率将日益成为一个国家 一个 行业 一家公司竞争的决定因素 知识是人类认识客观世界的结晶 同时也是指导人们 行为的准则 但是如何产生知识却是一个从古到今为人们探索的课题 这就是认知理论 人们在 大量实践与实验的基础上获取信息 通过大脑对信息的不断加工 才能获取知识 而且对 于知识的不断检验修正才能推进知识的进步 无疑 信息是获取知识的基础 由于计算 机科学与技术的发展 特别是计算机网络的发展 每日每时为人们提供了大量的信息 这些信息可帮助人们提炼更多更好的知识 但另一方面 也使得大量知识掩盖在海量信 息之中 在这种尖锐的矛盾中 扩充人类思维的知识发现就成为一个崭新的研究热点 知识发现一直是人工智能的核心问题 但是它被正式提出来 是在1 9 8 9 年8 月美国 底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上 从那以后 知识发现备受 重视 1 9 9 5 年 在加拿大召开了第一届知识发现与数据挖掘国际学术会议 第一本关于 知识发现的国际学术杂志 d a t am i n i n ga n dk h o w l e d g ed i s c o v e r y 也于19 9 7 年3 月创 刊发行 目前 u c m a a a i a c m s i g m o d 等代表人工智能研究最高水平的国际学术 会议都将知识发现列为重要的研究方向 许多研究人员根据自己对知识发现的理解与认识 给出了知识发现的定义 其中被 大家公认为比较深刻而完整的定义是f a y y a d 于1 9 9 6 年提出的 1 他将知识发现定义为 m en o n 锄i a lp m c e s so fi d e n t i 母i n gv a l i d n o v e l p o t e n t i a l l yu s e f u l a n du l t i m a t e l yu n d e r s t 锄d a b l ep a t t e m si nda t a 即知识发现是指从数据中识别正确 新颖 有潜在应用价值以及最终可为人们理解 的模式的方法 目前 人们已经掌握了多种获取知识与发现知识的手段 而其中最重要的是从数据 中发现知识 称为数据库中的知识发现 信息系统是一个具有对象和属性关系的数据库 这种数据库通过数据隐含着知识的对象与属性之间的关系 最终表达的知识模式是用属 性来表达的 它有明确的直观意义 由于数据库的复杂性和规模性 知识表达的对象和 属性之间的关系不是能直接观察到的 必须依赖于一定的数学方法和计算工具 2 0 世 纪5 0 年代以来 人们尝试着用各种方法发现知识 比如统计学方法 神经网络方法 遗 传算法 支持向量机方法等 粗糙集理论 r o u g l ls e tt l l e o 巧 与概念格理论 c o n c e p tl a t t i c e t l le 0 叮 是2 0 世纪8 0 年代初期产生的两个新的数学分支 由于其思想新颖 方法独特 已成为知识发现的两个重要数学工具 因此2 0 多年来 粗糙集理论与概念格理论在理论 1 研究和应用方面都得到了迅速发展 作为具有巨大潜力和有效的知识获取工具 受到人 工智能工作者的广泛关注 目前已经成功地应用于知识工程 管理科学 数据挖掘 决 策分析等领域 粗糙集理论是波兰数学家p a w l a kz 于1 9 8 2 年提出的一种分析数据的数学理论 2 最初关于粗糙集理论的研究主要集中在波兰等一些东欧国家 并没有引起国际计算机界 和数学界的重视 直到1 9 9 0 年前后 由于该理论在数据的决策与分析 模式识别 机器 学习和知识发现等方面的成功应用 才逐渐引起了世界各国学者的广泛关注 1 9 9 1 年 p a w l a kz 的专著 r o u g hs e t s r n l 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 的问世 6 标志着粗糙集理论及其应用的研究进入了活跃时期 1 9 9 2 年在波兰召开了关于粗糙集理 论的第一界国际学术会议 1 9 9 5 年a c mc o m m u n i c a t i o n 将粗糙集列为新浮现的计算机 科学的研究课题 目前 粗糙集理论已成为信息科学最为活跃的研究领域之一 粗糙集理论是一种研究不精确 不确定性知识的数学工具 通常处理含糊性和不确 定的问题 粗糙集对不精确概念的描述是通过上近似和下近似两个精确概念来实现的 一个概念的上近似由可能属于该概念的粒子组成 其下近似由肯定属于该概念的粒子组 成 粗糙集理论的主要思想就是在保持分类能力不变的前提下 通过知识约简 导出问题 的决策或分类规则 7 它与概率方法 模糊集方法和证据理论方法等其他处理不确定性问 题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息 粗 糙集 模糊集 8 和随机集理论在处理不确定性和不精确问题方面都推广了经典集合论 它们都可以用来描述知识的不确定性和不完全性 然而它们的侧重面不同 对粗糙集的 研究主要集中在其数学性质 粗糙集拓广 粗糙集理论与其他理论的关系 基于粗糙集 的逻辑 约简 9 1 1 等方面 概念格 又称形式概念分析 是德国数学家w i l l er 于1 9 8 2 年首先提出的 用于概 念的发现 排序和显示 1 2 1 3 概念格同样是建立在分类基础上 但它比分类有更大的概 括性 它往往在归纳几个分类的基础上产生一个概念 概念将属性与对象作为统一体 更好地反映了人的思维特征 所有的概念同它们之间的泛化 例化关系构成一个概念格 概念格的每个节点是一 个形式概念 概念格结构模型是形式概念分析理论中的核心数据结构 它是根据数据集 中对象与属性之间的二元关系 建立对象集与属性集之间的某种对应 本质上描述了对 象和特征之间的联系 生动简洁地体现了概念之间的泛化与例化关系 其相应的h a s s e 图 则实现了对数据的可视化 因此 概念格被认为是进行数据分析的有力工具 概念格理 论的研究主要集中在概念格的建造 简化 规则提取 背景网络下的概念格研究以及应 用等方面 2 概念格理论与粗糙集理论为数据分析提供了相互关联和相互补充的方法 它们之间 的关系引起了许多研究者的关注 已经有一些文献在一定程度上讨论了r s t 和f c a 形 式概念分析 之间的关系 比如在f c a 中引入近似算子 1 4 1 6 或者将粗糙集的一些概念 包括等价类 上 下近似等通过概念格来表示 1 7 这些工作对于我们理解两者的相似性 与不同性有很大的帮助 属性约简分别是它们的核心内容之一 属性约简可以使知识表 达更加简洁 使隐藏在数据表中的知识更加清晰 而粗糙集理论在属性约简方面具有独 特优势 与粗糙集理论相比 有关形式概念分析中的属性约简 1 8 q 1 的研究工作并不多 本文研究概念格属性约简与形式背景下的集合近似问题 我们知道形式背景的属性 可以从约简的角度分为三种类型 核心属性 相对必要属性和绝对不必要属性 我们首先 给出了三种不同类型属性的特征 获得了与文献 2 2 等价的判别它们的充分必要条件 同时提供了一种从属性类型分析获得概念格约简的方法 n o v o t n ym 提出了依赖空间的 概念 另辟新径 在属性集而不是在对象集上研究属性约简等问题 本文基于依赖空间 理论 给出了一种概念格的约简方法 证明概念格的约简与其诱导出的依赖空间中全集 的超约简是等价的 同时 利用依赖空间理论 也得到了一种信息系统的约简方法 证明 此信息系统的约简与其转化为形式背景后所诱导出的依赖空间中全集的约简是等价的 接着 用粗糙集理论中的知识模块定义了形式背景和决策形式背景一种新的约简形式一 优势约简 通过构造优势可辨识矩阵 得到了属性约简的布尔方法 最后 研究形式背 景下的粗糙近似问题 利用形式背景中的关系定义类下近似算子 证明了它与木算子等 价 把它推广到了模糊形式背景中 给出了它们的公理刻画 利用对偶性 对类上近似 算子和类模糊上近似算子进行了类似的讨论 3 1 基于一致关系的概念格属性约简 1 1 预备知识 定义1 1 1 瞄 称 配a 为一个形式背景 其中u z 1 z n 为对象集 每一 个 i 佗 称为一个对象 a 0 1 o m 为属性集 每一个 u m 称为一个属 性 为u 和a 之间的二元关系 j u a 在形式背景 配a j 中 若 z o 则称z 具有属性o 记为z j n 若 z n 譬j 则 称z 不具有属性n 用1 表示 z o 用 表示 z o 岳j 这样形式背景就可以表示为 对象关于属性的取值只有0 和1 的表格 对于形式背景 以a j 在对象子集x u 和属性子集b a 上分别定义水算子 x o i o a v z x z o b z l z 玩讹 b z o 其中 x 表示x 中所有对象共同具有的属性集合 b 表示具有b 中所有属性的对 象集合 比 配记 z 为z v n a 记 n 为n 若比 配z o 矿 a 且讹 a o 仍 o 以则称形式背景 以a 是正则的 定义1 1 2 2 2 设 配a 为一个形式背景 如果二元组 x b x 以b a 满 足x b 且x b 则称 x b 是一个形式概念 简称概念 其中x 称为概念的外 延 b 称为概念的内涵 对于形式背景 配4 我们可得以下基本性质 v x l x u 且v b l 岛 b a 1 x 1 局 争巡 x b 1gb 2 争b b 2 x x 料 j e i b 3 x x b b 料 4 x b 铮b x 5 x 1u 恐 k 舛n 趟 b 1u 岛 k 研n 骘 6 x 1n 恐 x u 端 b 1nb 2 2b iub 7 x x 和 j e i b 料 都是概念 用l 以a 表示形式背景 a j 的全体概念 记 x 1 b 1 咒 岛 x 1 施 兮b 12 岛 则 是l ua j 上的偏序关系 4 若 五 b 1 和 恐 岛 是概念 则 噩 b 1 恐 岛 x 1n 咒 b 1u 岛 x l b 1 v 恐 岛 x 1u 托 抖 b 1n 岛 也是概念 从而l ua 是格 并且是完备格 定义1 1 3 f 2 3 设三 以a 为概念格 其所有概念外延的集合记为 l u 以a x i x b l 以a 若对于两个概念格l 以4 1 和己 玩a 2 厶 有l u 配a 1 l u 配4 2 厶 则称 工 u a l 厶 和l 以a 2 厶 相等 记作三 配a 1 ul 以a 2 如 如果己 配a 1 厶 l 以a 2 厶 那么显然有l a 1 垡三 以如 l 定义1 1 4 2 3 设l 配4 1 厶 和三 配a 2 j 1 2 为两个概念格 如果对于任意 x b l 阢a 2 j 1 2 总存在 x b 己 配a 1 厶 使得x x 则称l 以a l 厶 细于三 配a 2 厶 记作l 以a 1 五 己 配a 2 如 如果l 以a l l 阢a 2 j 1 2 那么三u u a l 三c 以a 2 j 1 2 如果又有l 以a 2 厶 三 a 1 那么l 阢a 1 ul 配a 2 厶 在形式背景 配a j 下 v d a 记如 n u d 那么 以d 易 也是一个形 式背景 对于运算x x u 在 以a 下仍用x 表示 在 以d 而 下用x 如表 示 显然厶 j x a x x d x and x nd x d x 定理1 1 1 2 2 设 ua j 为一个形式背景 vd a 且d 0 则上 阢a j l 玑d 易 成立 定义1 1 5 2 2 对于形式背景l 配a 如果存在属性集d a 使得 三 d 易 矿己 配a 则称d 是l 以a 的属性协调集 若进一步 v d d 三 以d 一 以 如 d ul 弘a 则称d 是三 巩a 的属性约简 所有l 配a j 的属性约简的交集称为三 玩a 的属 性核心 定理1 1 2 2 2 设 配a j 是一个形式背景 d a 且d d 那么d 是一个协调 集兮l 以d 而 己 配a 定义1 1 6 f 2 2 设形式背景 阢a 的所有属性约简为 皿i 现 t 乃 丁是一个指 标集 按照属性的重要性程度 可将属性集a 中的元素分为以下3 类 5 1 绝对必要属性 核心属性 6 6 n 7 d i 2 相对必要属性c c u t 丁现一n 丁皿 3 绝对不必要属性d d a u 7 i 皿 定义1 1 7 f 2 4 设a 是一个非空集 p a 是a 的幂集 k 是p a 上的一个等价关 系 那么k 叫作p a 上的一个一致关系当它满足下列条件 若x 1 m 托 k p a 且 x 1 k k 咒 k k 则 x 1u mu 蚝 k 此时 我们称序对 4 k 为一 个依赖空间 定义1 1 8 2 4 设 a k 是一个依赖空间 x p a 集合z p a 叫作x 的一 个k 约简如果它是满足z 冬x 且 x z k 的极小集合 定义1 1 9 设 k 是一个依赖空间 x p 4 集合z p a 如果满足下列 性质 1 和 2 就叫作x 的一个k 超协调集 1 z x 2 对任意x x 都存在z z 使得 彳 x k 进一步 若z p a 是满足上面性质的极小集合 则称z 是x 的一个k 一超约简 定义1 1 1 0 2 5 称 以a f 为一个信息系统 其中集合u z l 为对象 集 每个瓤 i 礼 称为一个对象 集合a n l o m 为属性集 每个 d m 称 为一个属性 f 乃i 乃 u 一巧 歹 m 为u 和a 的关系集 巧为属性 的值域 定义1 1 1 1 2 5 设 以a f 为一个信息系统 对于b a 如 戤 巧 i 五 既 五 奶 讹 b 是u 上的 个等价关系 从而产生u 上的一个分划 u i 兄b b 翰 u 其中 翰 日 巧l 翰 冗b 巧i 五 五 v n l b 定义1 1 1 2 2 5 设 以a f 为一个信息系统 b 4 若满足冗口 冗a 则称b 为 信息系统 配a f 的协调集 进一步 若满足v6 b r b 一 6 冗a 则称j e 7 为信息系统 以a f 的约简 1 2 基于属性特征的属性约简 定理1 2 1 2 2 设 以4 为一个形式背景 v 口 4 定义g n 夕囟 a 矿 o 下列命题成立 1 o 是核心属性仁令 矿 一 n 4 o 2 o 是绝对不必要属性 令 口 一 o n 且g n n 3 口是相对必要属性仁今 o 一 n o 且伊 n o 在形式背景 以a 中 对任意o 6 a 若满足口 扩 则称口 6 在a 中是等价 的 记a 中包含 的等价类为m 则 0 扣 a p 扩 a 中属性的等价关系可将a 6 划分为多个不相交的属性子集 定理1 2 2 设 阢a 为一个形式背景 v o a 下列命题成立 1 n 是核心属性台今 o 一 o n 且m o 2 o 是绝对不必要属性乍净 n 一 叫 4 口 3 n 是相对必要属性 令 口 一 n o 且 o 口 证明由定理1 2 1 1 我们需要证明 n 料一 o 口 仁令 o 一 叫 矿且 0 o 仁 显然 暑 由于口料 n 一 o 2o 抖一 o 贝0o o 料宰 o 料一 我们知道 叫 o 这就是说 o 一 口 d 因为 n 一 n 0 一 o 而 口 一 o n 这就有 n 料一 n n 与已知矛盾 所以 0 o 2 我们需要证明 o 料一 o o 且口 o o 牟令 n 一 n 口 首先 证明g o o 抖一 o v6 a 6 o 料兮扩2n 铮扩 口 或者扩 n 聿 o 今6 g o u 叫 则 料 g o u n 而g o n n d 所以g o o 一 o 号 由上显然 车一 o 一 o o n 林 n 一 口 o 一 口 所以o 口料 o 料一 口 lj 一 j lj 一 一 口 一 n 口 因此 o 一 o o 3 由 1 和 2 可以得到 由此定理知若 是相对必要属性 则m 中的元素都是相对必要属性 口是绝对不必 要属性 则 n 中的元素都是绝对不必要属性 即m 中的元素具有相同的性质 由定理1 2 2 也可以看出对于一个形式背景 a j 来说 vo a 口是核心属性乍号不存在 的等价类以外的一个属性集生成的概念的外延与口生成 的概念的外延相同 且 的等价类中只有自己 n 是绝对不必要属性仁今存在 的等价类以外的一个属性集生成的概念的外延与口 生成的概念的外延相同 o 是相对必要属性等令不存在 的等价类以外的一个属性集生成的概念的外延与 生成的概念的外延相同 且 的等价类除了n 外还包含其他元素 所以根据上述讨论对于 个给定的信息系统 配a 来说 首先根据r o 6 i o 矿 这个等价关系对a 进行分类 使信息系统的属性合并 得到 阢a v 0 彳 若只 要 o 所在的列值为1 6 所在的列值也为1 把这样的 6 拿出来作成集合g 口 6 i f 6 n n 7 若g 凶 o 则n 为绝对不必要属性 若g 凶 0 且 叫 o 则 为相对必要属性 若g 凶 m 且 o o 则 为核心属性 这样就得到了所有属性的分类 下面我们举一例子来说明 例1 2 1 形式背景 以a 如表l 所示 表1 n6cde z 1 1l011 z 2 11100 口3 00 010 z 4 11100 根据表1 可以得出4 的划分为 o 6 o 6 c c 翻 田 e e 则得 配a 如表2 所示 表2 m c 明 e z l 1011 z 2 1100 z 3 o010 z 4 110o g m d 矿 o a 3 n 所以 为相对必要属性 翻 o 6 所以6 也为相对必要属性 g c m n r c c c 所以c 为核心属性 g 问 0 0 问 d 田 所以d 为核心属性 g e muc d 4 同u 问 e r 所以e 为绝对不必要属性 定理1 2 3 2 2 设 配a 是一个形式背景 dca d d e 4 一d 则 d 是属性协调集譬令ve e e 料nd e d 是约简牟今ve e e nd e 4 且vd d 矿 n d 一 d 矿 定理1 2 4 设 以a j 为一个形式背景 a n 1 u u 口n u 厶1 u u u c t u u h 其中o 为核心属性 6 l 6 m 为相对必要属性类 c 1 b 为绝对不必要属性类 则从 6 1 6 m 这些等价类的每一类中任意取出一个元素记为 6 1 小 6 m 和则d o l 6 1 n 6 m 为形式背景 配a j 的一个属性约简 8 证明ve a d 若e 鸭 防 为 6 6 m 中的某 个 则存在幻岛 d 啄 e 则乃略 e 所以 岛 e nd 6 耘2 e nd 因此e 2 矿 nd 又因为 e n d 2e u d e e 所以 e e 料n d 记c c l u u a c 为属性协调 集 若e c 则e e 料n a c 因为 e n d e n o l 6 1 1 一 e n a 1 o n u 6 l n 6 m i e 料n 0 1 u e 料n 6 1 t 6 戚 e 料n 0 1 n e 料n 6 6 m t e n 6 1 t 6 m i e 蚪n 6 1 n n e 料n 6 m e n 6 1 n n e 料n 6 m e u 6 1 u u 6 仇 所以 e nd e 料n a c e 这样由定理1 2 3 d 是一个属性协调集 vd d 若d 口l n n 有 d 一 d d d 一 d 扩 d n d 一 d 2 d 一 d 4 d 因此 d 4n d 一 d 4 扩 若d 6 1 t 以n t 且 扩 n d 一 d 矿 因为矿 扩料 扩 一 明 扩 n a 一 d s 扩 n d 一 d 4 扩 所以 扩 一同 扩由定理1 2 2 可得d 是一个绝对不必要属性 这和d 是 相对必要属性矛盾 所以 扩 n d 一 d 扩从而我们得出d 是一个约简 由定理1 2 4 可以看出形式背景的所有约简集的基数相同 等于核心属性的个数加上 相对必要属性类的个数 约简的总数取决于相对必要属性类的个数和相对必要属性类中 元素的个数 举例来说 若有m 个相对必要属性类 第1 类中有t 1 个元素 第2 类中有 i 2 个元素 第m 个中有 个元素 则属性约简的总数为i 1 z 2 例1 2 2 在例1 2 1 中已对属性进行了分类 核心属性集为 c 以 相对必要属性集 为 o 6 o 绝对不必要属性集为 e 相对必要属性只有1 类 且其中有2 个元素 所 以约简的个数为2 每个约简中有3 个元素 约简为 o c d 和 6 c d 1 3 基于依赖空间的属性约简 定理1 3 1 2 4 设a 是一非空集 p a 是a 的幂集 k 是p a 上的等价关系 如果对任意x 1 五 y p a x 1 恐 k 有 x 1uk 恐uy 那么k 是尹 a 上的一致关系 定理1 3 2 设a 是一非空集 p a 是a 的幂集 a k 是一个依赖空间 那么 p a 的每个k 等价类中必存在最大元 证明如果p a 的某一类里仅有一个元素则是显然的 假设存在某一类b 至少有两 个元素 j e i c 且b c 因为k 是一个一致关系 b b k c c k b c k 有 bub cub k cub cug k 就是 buc b k buc c k 因此 buc b c 在同一个等价类b 中 由于buc2b 且buc2c 因为a 是一个有限 的集合 按照归纳法可以得到最大元 9 定理1 3 3设t 以a 为一个形式背景 记驴 b 1 岛 p a p 4 i 研 鹾 则旷是p a 上的一个一致关系 证明驴显然是 个等价关系 若b 1 岛 玩 p a b 1 岛 铲 那么b 届 因为 b 1ub 3 研n 磁 gn 磁 岛u 玩 这就有 夙u 昆 岛u 岛 所 以 酽 是p a 上的一致关系 由定理1 3 3 可知 4 k t 是一个依赖空间 我们把它叫作由形式背景t 阢a 诱导出的依赖空间 定理1 3 4 设t 阢a j 为一个形式背景 a k t 是由t 诱导出的依赖空间 则b 4 是一个概念的内涵当且仅当b 是p 4 的每个k t 等价类中的最大元 证明 乍 假设日是b p 矽中的最大元 但不是内涵 那么bcj e i 料 因为b b 料 有 b b 料 萨 有b 料 b 这与b 是等价类b 中的最大元相矛盾 专 若b 是一个概念的内涵 那么b b 因此 曰 b 胪 b 和b 属于 同一个等价类b 如果c b 那么矿 b c 矿 b 料 b 所以 b 是等价类b 中的最大元 由定理1 3 4 可以得出p a 关于护的等价类的数目和形式背景t 中概念的数目是 相等的 定理1 3 5 设t 以a j 为一个形式背景 a 矿 是由t 诱导出的依赖空间 d a 那么d 是a 的一个护 超约简 兮d 是t 的一个属性约简 证明 穹 由定理1 1 1 有三 以a j 三 配d 而 因此只需要证明三 以d 而 l 配a v x j e i l 配a 有b x 由于d 是a 的一个k t 一超约简 且驴是 p a 上的一个一致关系 必存在一个最大元d l d 使得 b d 1 矽 那么x b d 由定理1 3 4 可以知道d l 是一个概念的内涵 因此 d d 1 l 以d 而 也就是有 x d 1 l 配d 如 因此三 配d 场 三 a 所以 三 配d 而 垡三 配a j d 是t 的属性协调集 若d 仅是t 的协调集而非约简 那么存在qcd 使得q 为t 的约简 记8 b i b 是t 中一个概念的内涵 由于q 是t 的约简 vb 召 存在 q q 使得b q 即 男 q 胪 vc a 必存在b 召满足 c k t 事 实上 c c k t 驴 是一个概念的内涵 从上面的证明可以知道一定存在q sq 使得 b q 矿 因此 c q k t 由超约简的定义可得 q 是a 的k t 一超约简 且qcd 这就与d 是a 的一个铲 超约简矛盾 总结一下可以得到d 是t 的一个约 简 仁 假设d 为t 的一个约简 那么v b 8 有b b n d 即 b b n d 胪 vc a 类似以上证明 存在 召使得 c b 驴 由于 b nd 一 则 0 c b nd k t 所以 d 是舻的超协调集 如果d 不是a 的舻 超约简 则存在 q cd 使得q 是a 的k t 一超约简 由定理充分条件的证明 可以得到q 是t 的约简 但是qcd 则d 不是t 的约简 与假设矛盾 因此 d 是a 的一个驴 超约简 例1 3 1 给出形式背景t 配a j 如例1 2 1 中的表1 所示 容易计算出 1 仍 z 1 z 2 z 3 z 4 2 o 6 o 6 z 1 z 2 z 4 3 c 事 6 c o c o 6 c z 2 z 4 4 d z l z 3 5 e 6 d 6 e o e d e q d n 6 e o 6 d 6 d e o d e 口 6 d e z 1 6 c e c d 6 c d 6 c e c d e o c d o c e o 6 c d 6 c d e o c d e o 6 c e 口 6 c d e 谚 因此p a 被驴分成六类 配d z z 2 z 4 o 6 z 2 z 4 o 6 c z 1 z 3 d z 1 o 6 d e d a 是形式背景t 的6 个概念 利用文献 2 4 求一个集合k t 超约简的算法 可以求得a 的两个 一超约简为 玩 o c 田和玩 1 用反证法 假设 0 与d 不只交于一个元素 不防设交于两元6 c 则矿 矿 6 c d 因为d 一 6 d 所以7 而s 一 6 v 可 一 6 有矿d o 旷d m 下面分三种情况进行讨论 1 若c 矿d 一伯 则c y d 邛 d 一 6 u 6 d 因为矿 矿 所以6 z 拥 6 剪 d 有z d 可 d 15 2 若c 譬z d 一伯 且c 馨可 d 一 d 一 6 u 6 d 因为6 c 所以6 譬z d 6 隹 秒 d 有z 4 d 可 d 3 若c 簪z d 一 6 但c 可 d 一伯 d 一 6 u 6 d 因为6 c 所以6 譬z d 6 秒 d 更有z d 可 d 综上得 z 所以 一僻 所以 一 6 死 这与d 是优势约简矛盾 命题得证 根据属性与各优势约简的关系 可以对a 中的元素进行如下分类 定义2 1 4 设形式背景 ua j 的所有优势约简为 d d i 是约简 i m m 是 一个指标集 可将属性集a 分为以下3 部分 1 优势绝对必要属性 优势核心属性 6 6 n 拒m d t 2 优势相对必要属性c c u i m 皿一n i m 皿 3 优势绝对不必要属性d d a u m d t 定理2 1 4 设 ua 为一个形式背景 则下列命题等价 1 o 4 是优势核心属性 2 死一 n 垡乃 3 o 是优势不可约属性类 且i o i 1 证明 1 兮 2 假设死一 n 死 由定理2 1 2 可知4 一 o 是优势协调集 显然 至少存在一个优势约简皿 皿 a 一 n a 隹现 这与 是优势核心矛盾 2 兮 1 假设o a 不是优势核心属性 则存在一个优势约简现 n 现 所以 皿 a 一 o 死一 死 这与死一 n 垡死矛盾 2 号 3 若l o i 1 由定理2 1 3 可知瓦 死一 a 这与死一懈垡万矛盾 所以 i 1 再由死一 口 死一 口 星死 可得 o 是优势不可约屙陛类 3 号 2 显然 定理2 1 5 设 以a j 为一个形式背景 则下列命题等价 1 o a 是绝对不必要属性 2 瓦一 a 死 丁 o 及口 其中丁 o u 一 n i 兀 b a 证明 1 兮 2 由口是绝对不必要属性 可知死一 口 死 且 不存在于任何优势 约简中 于是对于任意 五 b a 必有 一 死 否则 死一 d 呸死 则对于 任意b 冬口一 a 乃垡五 从而b 为优势约简且o b 这与 是绝对不必要属性矛 盾 所以丁 o 正口 2 令 1 若丁 o 及口 对vb a 死 必有 一 口 兀 兀u 死 于是 一 n 亿 死 得到 一f 凸 五一似n 巧口 u 亿 一 口 n 正口 u 一 n 亿 16 死u 死一 口 n 冗 死 从而n 不存在于任何优势约简中 即 是绝对不必要属性 定理2 1 6 设 以a 为一个形式背景 则下列命题等价 1 a 是相对不必要属性 2 死一 口 死 丁 口 匡正口 证明由定理2 1 4 定理2 1 5 可得 可以利用粗糙集理论中求可辨识矩阵的方法获得形式背景的优势约简 定义2 1 5 设 以a 为一个形式背景 v 毛 q 配记 d 奶 巧 口 ai 玩 巧 簪兀 o aiz 垡巧d 为既与 的可辨识属性集 刃 d 祝 巧 为形式背景 阢4 j 的可辨识属性矩阵 记刀1 0 d z t z j d 定理2 1 7 设 以a 为一个形式背景 b a 则下列命题等价 1 b 是优势协调集 2 vd 兢 巧 仇 有bnd 戤 吻 o 3 vb a 若b nb 0 贝0b 譬仇 证明 1 兮 2 b 是优势协调集铮 死铮 戤 巧 隹死时 有 婉 譬 净d 盈 巧 d 时 有 巧 隹 即存在o b 使口 d 以 巧 令d 甄 巧 d 时 bnd 甄 d 3 由 1 2 即证 定理2 1 8 设 配a 为一个形式背景 口 a o 是核心属性的充要条件是存在 毛 巧 u 满足d 妃 巧 o 证明设 是核心属性 若任意包含 的可辨识属性集d 钆 巧 中至少有两个元 素 令b u i 向 d 甄 巧 一 8 则bnd 协 巧 0 于是由定理2 1 7 的 2 可知 死 死 因而存在c j e i 使c 是约简 显然 隹c 这与n 是核心属性矛盾 反之 若存在甄 使d 甄 巧 o 则 必为核心属性 为此 我们只需证死 瓦一 口 则v6 a 一 n z 尹 弓6 于是 玩 巧 死一 口 而 瓤 隹死 所以死 死一似 设 以a 是形式背景 令 v 吼 n i 玩 黾 则 的极小析取范式中 每一合取项对应形式背景的一个优势约简 因此 从 的极小析取范式可以得到所有的 优势约简 例2 1 1 形式背景 配a 如例1 2 1 中的表1 所示 容易得出 1 7 z lz 2z 3z 4 z 1 0出口6 e 如 z 2 c0 n 6 c d z 3 0ddd z 4 e0 a 6 c o 贝 j dve ov6ve 人c d ov6vc o 八c d v 6 八c d v c 人d e 所以此形式背景的优势约简有三个分别为d o c d d 2 6 c d 和忱 c d e 核心属性为c 和d 相对必要属性为口 6 和e 没有绝对不必要属性 定理2 1 9 2 3 设 以4 为一个形式背景 对任意z 配有m 免 z 定理2 1 1 0 2 3 设 以a j 为一个形式背景 对任意的z m m 免 是概念 定理2 1 1 1 设 配a j 为一个形式背景 x 三u 配a 则x 可以表示为 m 乃 z u 中若干元并的形式 证明vz x 则z 茁料 所以z u z xz 这样x u z xz 料 由定理2 1 9 和 定理2 1 1 0 有x u 霉 x z 菝 u 茁 x z 而x x u z x z 料 n 茹 x 矿 n 霉 x m 敦 u x z 张 u x 茁 玖 因此 x u z x z 霸 由定理2 1 1 l 我们可以得到吲乃 z u 中的元素是构成概念外延的基本单位 这也 提供了一种通过m 霸 z u 来构造形式概念的方法 但其逆不成立 即m 死 z u 中 若干元并的形式不一定形成概念的外延 定理2 1 1 2 设 配a 为一个形式背景 则此形式背景的属性协调集一定是它的 优势协调集 证明设d 为形式背景 以a 的属性协调集 则对于任意概念 x b l 以a j 必存在 b l 配d 如 使x x 由定理2 1 9 对任意z 配m 为一概念的外 延 则存在p 而 使m m 而 所以死 即d 是形式背景的优势协调集 但定理2 1 1 2 的