（计算机软件与理论专业论文）粗糙集理论中的属性约简方法研究.pdf

西华大学硕士学位论文 粗糙集理论中的属性约简方法研究 计算机软件与理论专业 研究生陈洪华指导老师裴峥 随着信息化时代的到来，数据的存储、获取和产生都变得非常容易，人们 轻而易举就可以获得容量达g b 甚至t b 的数据，并且这些数据每天都还在不 断地增长中。但这是否意味着拥有了足够的知识了呢? 不是，我们虽然拥有了 海量的数据，其实对知识知之不多，大量的数据通常被描述为“数据丰富，但 知识贫乏”。面对如此巨大的数据资源，人们迫切需要一类工具和方法，以便能 够从迅速增长的、杂乱无章的数据资源中提取出人们感兴趣的、有用的知识， 从而帮助人们在生产、生活的各个领域科学地进行各种决策。 上个世纪5 0 年代以后，人们尝试着用各种方法发现知识，比如神经网络方 法、统计学习方法、遗传算法、支持向量机方法等，但这些方法得到的知识是 一些隐性知识，不能被人们很好地直接理解。 粗糙集理论( r o u g hs e t st h e o r y ) 是波兰数学家z p a w l a k 于上个世纪八十 年代初期提出的一套处理不完整、不精确数据的数学工具。它不需要专家的知 识，也不需要设置专门的机构为原有的数据提供更多的解释；它可以直接从原 有知识出发，得出具有同等表达能力的新信息系统。更为重要的是利用它所得 到的知识是人们可以理解的关联规则，这些关联规则符合人类的经验，更适合 在管理决策中应用。 尽管粗糙集理论已成功地应用在许多商业用途中，也能够很好地处理不精 确和不完备的数据，但是对粗糙集理论的研究还有一定的空间：例如如何将一 般信息系统的约简方法扩展到决策信息系统，进而不协调的决策信息系统，如 何将变精度粗糙集运用于更多的领域等等。本论文针对一般信息系统以及协调 决策信息系统，提出一种新的属性约简( 知识约简) 方法，并针对不协调决策 信息系统，提出一种得到其二元辨识矩阵的方法。 西华大学硕士学位论文 与粗糙集同一年提出的另一个重要理论就是概念格( c o n c e p tl a t t i c e s ) ，概 念格同样可以挖掘出一些人们可以理解的关联规则，这些规则同样符合人类的 经验，同样适合在管理决策中应用。因此2 0 多年来，粗糙集方法和概念格理论 同样都得到了迅速的发展。 对于一个形式背景，其概念是固定的。对于删除属性或对象等操作，其概 念是变化的。本文不仅从数量上分析了形式背景变化前后概念变化的情况，而 且分析了其变化的形式。旨在可以指导形式背景的动态分析。 关键词：租糙集理论，属性约简，知识约简，蚁群算法，形式背景 i i 西华大学硕士学位论文 s t u d yo fa t t r i b u t e sr e d u c t i o n i nr o u g hs e t st h e o r y c o m p u t e rs o f t w a r e t h e o r y m d c a n d i d a t e ：h o n g h u ac h e ns u p e r v i s o r ：z h e n gp d p e o p l ec a r lo b t a i n ，s t o r ea n dd e a lw i t hag r e a td e a lo fd a t am o r ee a s i l yi nt h e i n f o r m a t i o nt i m e s ，a n dt h ed a t ai n c r e a s ee v e r yd a y b u td o e si tm e a nt h a tw eh a v e h a de n o u g hk n o w l e d g e ? i td o e s n t a l t h o u g hw eh a v ee i l o u g l ld a t a , w eh a v el i t t l e k n o w l e d g ef r o mt h e s ed a t a w eh a v e t on e e dat o o lo rm e t h o dw h i c hc a r lb eu s e dt o d i s t i l lk n o w l e d g ef r o mt h e s ei n c r e a s i n ga n du n o r d c r l yd a t a t h ed i s t i l l e dk n o w l e d g e s h o u l db eu s e f u la n di n t e r e s t i n gt h a tc a nb eu s e df u rm a k i n gd e c i s i o n si np r o d u c t i o n a n dl i r e a f t e r5 0i nt h el a s tc e n t u r y , p e o p l et r i e dt ob i l em a n ym e t h o d ss u c ha sn e u r a i n e t w o r k ，s t a t i s t i c ss t u d y , a n ds u p p o r tv e c t o rm a c h i n ea n d s oo nt od i s c o v e r k n o w l e d g e b u tt h eo b t a i n e dk n o w l e d g ei sl a t e n ta n dc a nn o t b eu n d e r s t o o dw e l lb y p e o p l e r o u g h s e t st h e o r yi sam a t h e m a t i ct o o lw h i c hi sp r o p o s e di n1 9 8 2b yz p a w l a k w h oi sam a t h e m a t i c i a ni np o l a n d ，a n dt h i st o o li su s e dt op r o c e s sh a l f - b a k e da n d i m p r e c i s ed a t a i tn e e d n te x p e r t s k n o w l e d g ea n dr e a s o n sf r o ms p e c i a lo r g a n s ；i tc a n b eu s e dt oo b t a i nan e wi n f o r m a t i o ns y s t e mw h i c he q u a l st ot h eo r i g i n a li n f o r m a t i o n s y s t e mi ne x p r e s s i o ns o m e t h i n g a n dm o r e ，u s i n gi t ，w ec a no b t a i nk n o w l e d g et h a t i su n d e r s t o o dr u l e s ，a n dt h e s er o l e sa c c o r dw i t hp e o p l e se x p e r i e n c e sa n dm o r ef i t f u l i nd e c i s i o nm a k i n g a l t h o u g hr o u g hs e t st h e o r yh a sb e e nu s e di nm a n yc o m m e r c i a lf i e l d sa n di tc a n b eu s e dt op r o c e s si m p r e c i s ea n di m p e r f e c t i o nd a t a ，t h e r ea l es t i l ls o m ea s p e c t st h a t c a l lb es t u d i e di nr o u g hs e t st h e o r y s u c ha si m p r o v i n gt h ea t t r i b u t e sr e d u c t i o n m e t h o d si ng e n e r a li n f o r m a t i o ns y s t e m s ，s oa st ot h e s em e t h o d sc a l lb eu s e di n i i i 西华大学硕士学位论文 d e c i s i o ni n f o r m a t i o ns y s t e m sa n ds oo n t h i sp a p e rp r o p o s e san e wm e t h o da b o u t a t t r i b u t e sr e d u c t i o nw h i c hc a l lb cu s e di nag e n e r a li n f o r m a t i o ns y s t e mo ra c o n s i s t e n td e c i s i o ni n f o r m a t i o ns y s t e m ，a n dan e wm e t h o da b o u th o wt oo b t a i n b i n a r yd i s c e m i b i l i t ym a t r i xi 1 1i n c o n s i s t e n td e c i s i o ni n f o r m a t i o ns y s t e m s a l s oi n1 9 8 2 ，c o n c e p tl a t t i c e st h e o r yi sp r o p o s e dt oo b t a i ns o m er u l e sf r o md a t a a n dt h e s er u l e sa r ca l s ou n d e r s t o o d ，s of o i l 曲s e t st h e o r ya n dc o n c e p tl a t t i c e st h e o r y d e v e l o pr a p i d l yt h e s e2 0y e a r s f o raf o r m a lc o n t e x t ，i t sc o n c e p t s 饕es t a t e d b u ti fw ed e l e t es o m ea t t r i b u t e so r o b j e c t s ，i t sc o n c e p t sa r cc h a n g e d t h i sp a p e ra n a l y s e st h ec o n c e p t sc h a n g i n gc a s e s w h e nw ed e l e t es o m ea t t r i b u t e so ro b j e c t sf r o maf o r m a lc o n t e x t k e y w o r d s ：r o u g hs e t st h e o r y , a t l r i b u t e sr e d u c t i o n ，k n o w l e d g er e d u c t i o n ，a n tc o l o n y a l g o r i t h m ，f o r m a lc o n t e x t w 西华大学硕士学位论文 声明 本学位论文是在导师的指导下完成的研究工作和取得的研究成果。除了文 中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包括为西华大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。论文成果归西华大学所有，特此声明。 作者签名：帛、陟啤旁咖蹭 导师签名 舻如少同 西华大学硕士学位论文 1 绪论 1 1 数据挖掘方法 随着信息技术的高速发展，人们积累的数据量急剧增长，动辄以t b 计， 并且这些数据每天部还在不断地增长中。面对如此巨大的数据资源，人们迫切 需要一类工具和方法，以便能够从迅速增长的、杂乱无章的数据资源中提取出 人们感兴趣的、有用的知识，从而帮助人们在生产、生活的各个领域科学地进 行各种决策。 数据挖掘就是为顺应这种需要应运而生发展起来的数据处理技术，它是知 识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 的关键步骤。数据挖掘( d a t am i n i n g ) 可以 从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、 人们事先不知道的、但又是潜在有用的信息和知识的过程。 数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力 将会不停地促进它的发展。每年都有新的数据挖掘方法和模型问世，人们对它 的研究正日益广泛和深入。尽管如此，数据挖掘技术仍然面临着许多问题和挑 战：如数据挖掘方法的效率有待提高，尤其是超大规模数据集中数据挖掘的效 率：开发适应多数据类型、容噪的挖掘方法，以解决异质数据集的数据挖掘问 题：动态数据和知识的数据挖掘；网络与分布式环境下的数据挖掘等：另外， 近年来多媒体数据库发展很快，面向多媒体数据库的挖掘技术和软件今后将成 为研究开发的热点。 目前的数据挖掘方法主要有以下几种 7 6 1 ： ( 1 ) 神经网络方法 神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储 和高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们 的关注。典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函 数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以 h o p f i e l d 的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反 馈式神经网络模型；以a n 模型、k o h o l o n 模型为代表的，用于聚类的自组织映 西华大学硕士学位论文 射方法。神经网络方法的缺点是”黑箱”性，人们难以理解网络的学习和决策过 程。 ( 2 ) 遗传算法 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿 生全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使 得它在数据挖掘中被广泛应用。 s u n i l 已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两 个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据 挖掘的有效方法之一。遗传算法的应用还体现在与神经网络、粗集等技术的结 合上。如利用遗传算法优化神经网络结构，在不增加错误率的前提下，删除多 余的连接和隐层单元；用遗传算法和b p 算法结合训练神经网络，然后从网络 中提取规则等。但遗传算法比较复杂，且收敛于局部极小的较早收敛问题尚未 解决。 ( 3 ) 决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从 中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快， 特别适合大规模的数据处理。最有影响和最早的决策树方法是由q u i n l a n 提出的 著名的基于信息熵的i d 3 算法。它的主要问题是：i d 3 是非递增学习算法：i d 3 决策树是单变量决策树，复杂概念的表达困难；同性间的相互关系强调不够； 抗噪性差。针对上述问题，出现了许多较好的改进算法，如s c h l i m m e r 和f i s h e r 设计了i d 4 递增式学习算法：钟鸣，陈文伟等提出了i b l e 算法等。 ( 4 ) 粗糙集方法 粗糙集理论是一种研究不精确、不确定知识的数学工具。粗糙集方法有几 个优点：不需要给出额外信息：简化输入信息的表达空间；算法简单，易于操 作。粗糙集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管 理系统和新发展起来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基 础。但粗糙集的数学基础是集合论，难以直接处理取值连续的属性。而现实信 息表中往往包含这种取值连续的属性。因此连续值属性的离散化是制约粗糙集 理论实用化的难点。现在国际上已经研制出来了一些基于粗糙集的工具应用软 件，如加拿大r e g i n a 大学开发的k d d r 、美国k a n s a s 大学开发的l e r s 等 1 3 】【1 3 1 5 】 西华大学硕士学位论文 【1 7 】。 ( 5 ) 形式概念分析方法 形式概念分析理论用来进行数据表达的基本形式就是交叉表( c r o s st a b l e ) ， 用来表示形式背景( f o r m a lc o n t e x t ) 。形式概念分析理论可以用来表示单值属性 背景，也可用来表示更复杂的数据类型，如多值属性背景，对于多值属性背景， 一种处理方式是通过概念定标( c o n c e p t u a ls c a l i n g ) 的方法将其转换为基本的类 型( 即单值属性背景) ，另外一种处理方式就是不转换，直接根据低层概念之间 的关系抽象出高层的概念。形式概念分析理论的基本概念是形式背景( f o r m a l c o n t e x t ) 和形式概念( f o r m a lc o n c e p t ) 1 8 - 2 4 1 。 形式概念分析理论是基于数学中的偏序理论( p a r t i a lo r d e r i n gt h e o r y ) 的， 特别是基于完备格的理论。 ( 6 ) 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性 关系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分 析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行 常用统计( 求大量数据中的最大值、最小值、总和、平均值等) 、回归分析( 用回 归方程来表示变量问的数量关系) 、相关分析( 用相关系数来度量变量间的相关 程度) 、差异分析( 从样本统计量的值得出差异来确定总体参数之间是否存在差 异) 等。 ( 7 ) 模糊集方法 即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别 和模糊聚类分析。一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性 的。李德毅等人在传统模糊理论和概率统计的基础上，提出了定性定量不确定 性转换模型一云模型，并形成了云理论 31 3 3 。 1 2 粗糙集理论研究现状 粗糙集理论( r o u g hs e t st h e o r y ) 是波兰数学家z p a w l a k 于上个世纪八十 年代初期提出的一套处理不完整、不精确数据的数学工具 1 】。它不需要专家的 西华大学硕士学位论文 知识，也不需要设置专门的机构为原有的数据提供更多的解释：它可以直接从 原有知识出发，得出具有同等表达能力的新信息系统。关于粗糙集理论的最初 研究主要集中在波兰，因此当时并没有引起国际计算机界和数学界的重视，研 究地域仅限于东欧一些国家。直到1 9 9 0 年前后，由于该理论在数据的决策与分 析、模式识别、机器学习与知识发现等方面的成功应用，才逐渐引起世界各国 学者的广泛关注。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 f r e a s o n i n ga b o u td a t a ”的问世，成为r s 理论发展的一个重要里程碑。1 9 9 5 年 a c mc o m m u n i c a t i o n 将r s 列为新浮现的计算机科学的研究课题。近年来r s 已成为信息科学最为活跃的研究领域之一，同时该理论还在医学、化学、管理 科学、商业和金融等领域得到了成功的应用。我国也在国家自然科学基金、国 家8 6 3 计划和一些省市基金的支持下开展了一定的研究工作，逐渐取得了一些 研究成果。 更为重要的是利用它所得到的知识是人们可以理解的关联规则，这些关联 规则符合人类的经验，更适合在管理决策中应用。概括地说，粗糙集处理数据 的过程就是划分、约简、求取规则、学习的过程，其中约简是粗糙集求解的关 键1 2 3 1 1 1 3 1 5 。到目前为止，已有许多学者做了大量的研究，提出了一系列求 解约简的方法【扣1 2 】 1 6 】。 尽管粗糙集理论己被成功地应用在许多商业用途中，也能够很好地处理不 精确和不完备的数据，但是对粗糙集理论的研究还有一定的空间：例如如何将 一般信息系统的约简方法扩展到决策信息系统，进而不协调的决策信息系统， 如何将变精度粗糙集运用于更多的领域等等。在本课题中，针对这些方面做了 进一步的研究。 当前关于r s 的研究主要集中在以下几个方面【1 6 】： ( 1 ) r o u 【g h 逻辑从逻辑角度进行不确定推理、决策； ( 2 ) r o u 【g h 代数讨论r s 的代数结构、拓扑结构以及收敛性问题， 致力于构造或生成约简空间； ( 3 ) r o u l g h 约简包括各种约简算法的研究，求解尽可能小的约简及 并行实现； ( 4 ) 知识粒度在不同的层次下解释知识： ( 5 ) 与其他处理模糊性或不确定性理论之间关系的研究。 4 西华大学硕士学位论文 关于粗糙集的发展趋势，本文列举如下【1 7 】： ( 1 ) 粗糙逻辑，基于概念的粗糙真值研究将是一个很重要的课题： ( 2 ) 粗糙关系理论尤其是粗糙函数的研究在很多应用领域是极其重 要的； ( 3 ) 大型数据库的知识约简； ( 4 ) 大型信息表的分解。 1 3 形式概念分析研究现状 与粗糙集同一年提出的另一个重要理论就是概念格( c o n c e p tl a t t i c e s ) ，概 念格同样可以挖掘出一些人们可以理解的关联规则，这些规则同样符合人类的 经验，同样适合在管理决策中应用 1 8 2 4 1 。因此2 0 多年来，概念格同样得到 了迅速的发展。 形式概念分析理论是一种基于概念和概念层次的数学化表达的应用数学的 一个分支。因此，在应用形式概念分析理论时，需要用数学的思维方式进行概 念数据分析和知识的处理。形式概念分析中的“形式”一词表示我们正在处理 数学领域的工作，通过与这些工作相联系的结构化的概念的联系，发现可理解 的、有意义的知识。 形式概念分析理论是基于数学中的偏序理论( p a r t i a l o r d e r i n g t h e o r y ) 的， 特别是基于完备格的理论。 基于形式概念分析的研究主要有概念的建格，对于一个形式背景来说，找 出所有概念并建格是一个n p h a r d 问题。 1 4 本文主要工作及创新点 1 4 1 本文主要工作 1 、在查阅相关课题文献、概述粗糙集理论的基础上，研究目前常用的属性 约简方法并针对启发式方法，比较属性重要度度量的优劣； 西华大学硕士学位论文 2 、研究协调决策信息系统的知识约简，并提出一种求解知识约简次优解的 方法； 3 、基于二元辨识矩阵理论，研究不协调决策信息系统的知识约简； 4 、对于二值形式背景来说，研究属性或对象删减后概念的变化情况。 1 4 2 本文主要创新点 l 、本文将二元辨识矩阵运用到不协调决策信息系统的知识约简上； 2 、目前信息系统的属性约简或决策信息系统的知识约简，其结果大多不是 很令人满意。本文将蚁群算法和二元辨识矩阵相结合，提出了一种新的方法， 通过此方法可以尽可能多的约去冗余属性： 3 、给出不协调决策信息系统中一些性质及其证明； 4 、对于一个二值形式背景，本文讨论了删除属性或对象后概念的变化情况。 基于此类讨论，我们可咀对形式背景进行动态分析。 1 5 论文结构 本文剩下的章节将组织如下： 第二章：介绍粗糙集理论以及形式概念分析的背景知识； 第三章：介绍一般信息系统在此基础上讨论一般信息系统的属性约简，给 出一些定理及其证明； 第四章：讨论协调决策信息系统的知识约简，然后利用蚁群算法来进行属 性约简； 第五章：讨论不协调决策信息系统的知识约简。将二元辨识矩阵运用到不 协调决策信息系统的知识约简上； 第六章：讨论一个形式背景删除属性或对象后概念的变化情况。 6 西华大学硕士学位论文 2 粗糙集以及形式概念分析的背景知识介绍 2 1 粗糙集理论背景知识 2 1 1 经典集与等价关系 在管理决策中，我们面对的是一些研究的对象、研究的方案或者收集到的 案例，它们是管理决策的基础，通常称研究的对象全体、方案全体或案例全体 为论域，一般地记论域为【1 5 】： u = x l ，x 2 ，) 。 其中x i 表示某个决策对象、决策方案或案例。扩中的一部分称为子集，一般用 x ，y ，z 表示c ，中子集。若x i 属于x ，记作x 。x ，否则记作工，x 。对于【，中 任意两个子集x ，y ，若而肖时必有x ，y ，称x 含于y ，或y 包含x ，并记 作x y 。若j g y ，x y ，称j 为y 的真子集，这时记为j c y 。对于u 中 任意两个子集爿，y ，有运算： x u y = x i i t x 或j f y ) ， j u y = i x , j 五x 且x i y ) ， x = x = x ii 工) ， x y = x n y c 。 “u ”称为并运算，“n ”称为交运算，“”或“c ”称为补运算。在u 中有两 个特殊子集合，“毋”表示不含u 中任何元素，称为空集；“u ”表示包含u 中 任意元素，称为全集。对于u 中任意子集x ，均有庐x e u 。 易证，集合的运算满足以下性质： ( 1 ) 交换律：x u y = y u x ，x n y = y n x ； ( 2 ) 结合律：( x u y ) u z = x u ( r u z ) ， ( x n y ) n z = x n ( y n z ) ； ( 3 ) 互补律：u x 。= u ，x n x = ； ( 4 ) 对偶律：( x u y ) = 盖n y c , ( x n y ) 。= x 。u y 。 定义2 1 1 1 5 若o k ) 为u 的子集，且置矿( ，尼) ，一n z i = 矿( f j ) ， u ：x ；= u ，则称 x 。l i t ) 为u 的划分。 西华大学硕士学位论文 划分即分类，即将研究对象分成不同类，这些类之间互不相交，且任何对 象均包含于某一类中。比如对于小轿车可以用不同颜色来分类，也可用不同的 性能来分类，可以用价格来分类，也可以用生产地区分类。有了不同的分类才 可能有针对性的决策。 定义2 2 1 1 5 设矗u o u ，称r 为u 上的关系。当( x , y ) r 时，称j ，y 有关系r ，当( x ，y ) 芒r 时，称x ，y 无关系r 。 管理决策就是研究事物之间的相互关系，通过关系才能产生决策行为。比 如以成绩优劣关系选择优秀学生，通过咖啡与糖的关系决策超市的存储量等。 关系包含了分类，也包含了优劣比较。 定义2 3 1 1 5 1 u 上的关系r 称为等价关系，若满足以下性质： ( 1 ) 自反性：，x i ) r ( u ) ； ( 2 ) 对称性：( x i ，工，) r 时，o ，x f ) r0 j ，x u ) ； ( 3 ) 传递性：( x 。，工，) r ，( 名，x t ) r ，贝0 ( x i 工 ) r ( x i ，x ，x k u ) 定理2 1 1 5 1 u 上的关系r 必然产生u 上的一个划分，【，上的一个划分由 u 上的一个等价关系r 产生。【，上的等价关系与u 上的划分一一对应。 2 1 2 粗糙集及其近似 等价关系可以将对象集分类，从认知的角度来看，人们需要通过分类去认 识那些不能用分类精确表示的对象集，这种集合称为粗糙集。 定义2 4 【l 】设u 是对象集，月是u 上的等价关系。 ( 1 ) 称( u ，r ) 为近似空间，由( 【，r ) 产生的等价关系为 u r = 一】。l x i u ) ， 其中 x i 】r = x j l ( x ix ) r ) 。 ( 2 ) 对于任意x u ，记4 星( x ) = x i | 】。x ， r ( j ) = x fl 【x f 】月n x 矿) ， 称墨( ) 为x 的下近似，g ( x ) 为x 的上近似。 ( 3 ) 若曼( x ) = r ( x ) ，称x 为可定义的集合，否则称x 为粗糙集。 西华大学硕士学位论文 定理2 2 1 1 5 设( u ，尺) 为近似空间，对于x u ，记 型( x ) = u 【耳k1 k 。x ) ， r ( z ) = u 【一】。| 【t 。n x ) ， 则有 型( x ) = 曼( x ) ，r ( x ) = r ( x ) 定理2 3 1 5 设( 【，r ) 为近似空间，下近似与上近似具有以下性质： ( 1 ) 型u ) = 胄( u ) = u ，星( 妒) = r ( ) = 疵 ( 2 ) 豇x ) s x s 月( z ) ； ( 3 ) g ( xr q y ) = 墨( z ) n 墨( y ) ，r ( x u 】，) = r ( x ) u r ( j ，) ； ( 4 ) 墨( z ) 一r ( z ) ，r 卜工) 一墨( z ) 。 【注】一般情况下，下面公式不成立： ( 1 ) _ g ( x u y ) = 星( x ) u g ( r ) ， ( 2 ) g ( x l q y ) = r ( x ) u 尺( y ) 。 定义2 5 【l 】设( ur ) 为近似空间，对于x 称 b n ( x ) ：承舯一尉舯 为x 的边界。 定理2 3 1 1 5 1 设( 【，尺) 为近似空间，对于x 仉y 阢记 圣。匕y ) = x | 工】 z u y ， 叫。s n ( x ) ， 卅 b ( y ) 。 则 墨( x u y ) = 曼( x ) u 墨( y ) u 兰( x ，】，) 。 定理2 4 1 5 设( u ，r ) 为近似空间，对于x 己，y 至u ，记 z ( 五y ) = 缸i 工】。b ( 爿) ， 卅l 。b n ( y ) ，( 卅。n x ) n ( 【x 】。n y ) = 声 。 则 r ( x i qy ) = r ( x ) n r ( 3 一z ( x ，y ) 。 2 1 3 信包系统 定义2 6 1 1 5 称( u ，a ，f ) 是一个信息系统，其中u 为对象集，即 u = 一，x 2 ，x m ) ， 西华大学硕士学位论文 【，中的每个元素蕾“n ) 称为一个对象。一为属性集，即 a = 口i ，2 ，a ， ， a 中的每个元素口，( z 所) 称为一个属性。f 为u 与一之间的关系集，即 f = 石：【，j 巧“兰m ) ， 其中_ 为口，( f 兰m ) 的值域。 【注】：本论文中提到的信息系统除非特别强调是决策信息系统外都是指一般 信息系统。 信息系统是数据库的抽象描述。在信息系统中的关系集f 是非常重要的， 它是对象集与属性集之间的纽带，也是知识发现的信息基础。f a x ，) - t v 表达了 对象膏，具有属性a t = v 的值。属性西的取值可以是有限离散值，也可以是连续 数值，可以是语言值，也可以是图像和声音。对于不同取值域k ，知识发现的 方式也不同 1 5 】。 作为数据库的抽象的信息系统在实际生活中大量存在。一般来讲，数据库 是非常庞大的，人们很难从数据库直接看到内在的规律。因此有必要通过数学 模型和数学工具，找到存在于庞大的数据库中的潜在规律。因此知识发现问题 就是数据库压缩问题，同时也是排除数据库中的干扰问题。通过数据库压缩和 干扰的排除，人们得到了决策知识，这样的知识才可能在实际应用中发挥作用 1 5 。 定理2 5 1 1 5 设( u ，a ，f ) 是一个信息系统，对于任意bc - a ，记 r 。= ( t ，a ，) l f t ( x i ) = 五o f ) ( a f 口) ) ， 则r 。是u 上的等价关系。记 x i 】口= x 州x i ) 工，) r 日) ， 则u r 。= t 】。1 x 。u 是u 上的划分。 定理2 6 1 2 设( u ，a ，f ) 是一个信息系统，尺。( b a ) 具有以下性质： ( 1 ) 当b i b 2 a 时，r 尺口2 r 肌； ( 2 ) r 口= n m r 。 其中r = r 。u r 。具有以下性质： ( 1 ) 当旦b 2 a 时， 】 口：【x a ； ( 2 ) 【x i 】。= n 。【 。 其中【x a 。= k 。 1 0 西华大学硕士学位论文 2 1 4 信息系统的属性约简 信息系统中的是属性并不是同等重要的，属性约简是指可以找到一个较小 的属性集b a ，使得可用a 描述的对象集合必然可用口描述，从而消除冗余 属性。属性约简简化了分类的标准，同时也使人们更加深入地认识分类的实质。 定义2 7 1 2 设( u ，a ，f ) 是一个信息系统，对于占a ，若r 。= r ，称口是 划分协调集。若口是划分协调集，而b 的任何真子集均不是划分协调集，则称雪 为划分约简集。 若r 口= r 。，则u r 口= u r ，从而用属性日对【，的分类与用属性爿对【，的 分类完全相同。于是用划分协调集b 或划分约简集口可以描述由a 描述的对象 集。 由于r 。r 。总成立，从而月。= r 。等价于r 。 定义2 8 1 2 5 设( u ，a ，f ) 是一个信息系统，记 u r 。= k 。l 硼， d ( 【x i 】。，【x ， 。) = a ，af a x ，) f a x ，) ) 。 称d ( k 。 工， 。) 为 - 。与 x ，】。的划分辨识集，称 。 d = ( d ( x f 】，h 山) 1 x 山 j 山u r 。) 为信息系统的划分辨识矩阵。 辨识矩阵是辨识集的全体，辨识集中的元素用于区分不同等价类的各种属 性。 定理2 7 1 2 设，4 ，) 是一个信息系统，对于任意x 。，工，x 。u ，划分辨识 集有以下性质： ( 1 ) d ( x ，】，【x ，】。) = 妒； ( 2 ) d ( k 】，h 山) = d ( 【z 【，l ) ； ( 3 ) d ( 工， x ，】) d ( j ，】。，i x i 】。) u d ( 【 ， x 一) 。 定理2 8 2 5 设d 是信息系统( u ，a ，f ) 的划分辨识矩阵，则b 为划分协调 集当且仅当对于任意 x i 】。n i x ， 。= ，有 b n d ( 】， j ， ) 。 西华大学硕士学位论文 2 1 5 信息系统的属性特征 信息系统中的不同属性对于划分的作用是不同的，有的属性对于划分是必 不可少的，有的属性在划分中是可以被其他属性代替的，有的属性对于划分是 根本不需要的。因此，我们需要研究对划分起不同作用的属性，给出相应的特 征【1 5 】。 定理2 9 1 1 5 设( 【，a ，f ) 是一个信息系统，则划分约简集必存在。 定义2 9 1 5 设，a ，f ) 是一个信息系统，风( 七，) 为所有划分约简集， 记 c = n i 。b k ，k = u t ；，毋一c ，i = a u t 。& 。 口c 时称a 为划分核心，c 称为划分核心集；口k 时称a 为划分相对必要属 性，k 称为划分相对必要属性集：a i 时称a 为划分不必要属性，称为划分 不必要属性集。 定理2 1 0 1 2 5 设( u ，a ，f ) 是一个信息系统，则以下命题等价： ( 1 ) a 是划分核心； ( 2 ) 存在t ，工，u ，_ d ( 【x ，】【x ) = 如) ； ( 3 ) r 。i r j 。 定理2 h 1 5 设( u ，a ，f ) 是一个信息系统，贝1 j a 为划分不必要属性当且仅 当r ( a ) r 。，其中 r ( d ) = u r 口一i 矗口r ，b a 。 定理2 1 z 1 5 设( u ，a ，f ) 是一个信息系统，则有以下结论： ( 1 ) 口是划分核心当且仅当r “。i r 。； ( 2 ) a 是划分相对必要属性当且仅当r h 。l = r ，且尺( ) ! 心； ( 3 ) d 是划分不必要属性当且仅当r ( a ) r 。 2 1 6 决策信息系统 定义2 1 0 1 1 5 1 设( u ，4 ，f ) 是一个信息系统，d ：u 一，圪取有限值，称 ( u ，一，f ，d ) 为决策信息系统，记 r j = ( j ，x 川正( _ ) = a ( x ) ( d ，一) ， 西华大学硕士学位论文 凡= ，x 川d ( x 。) = e ( x j ) ) 。 若r 心，称( u ，爿，f ，d ) 为协调决策信息系统。 定义2 1 1 1 1 5 设( u ，爿，f ，d ) 为协调决策信息系统，若存在b a ，使得 r 。r 。，称b 为决策协调集。若b 为决策协调集，且口的任何真子集都不是 决策协调集，称占为协调决策信息系统的决策约简集。 定义2 ，1 2 1 1 5 1 设( u ，a ，f ，d ) 为协调决策信息系统，记 u r = _ h u ) ， u r d = i x i 】dk u ， 见c k ，。，c 工，。，= # 2 彳i 石“z 譬 s 昌之i 2 称见( h 】。， x ，】。) 为【z ， 。与 x ， 。的决策辨识集，称 d d = ( d d ( z f 】，【工，】) i x i ，【石，】u r j ) 为决策信息系统的决策辨识矩阵。 定理2 1 3 1 5 设( u ，a ，f ，d ) 为协调决策信息系统，对于任意x j ，z ， u ， 决策辨识集具有以下性质： ( 1 ) d d ( 】。， 】。) = ； ( 2 ) 仍( k 】。，b 儿) = 或( p ，k 】。) ； ( 3 ) d 。( i x 山，【x 山) d d ( i x 。 。，i x 。 。) u 见( i x 。】。，旺 ) 。 定理2 1 4 1 1 5 1 设( u ，4 ，f ，d ) 为协调决策信息系统，则占为决策协调集当且 仅当对于任意d , t ( k 】。， x j l ) ，有 b n 见( z i 】。， 工，】) 庐。 定义2 1 3 1 5 设( u ，a ，f ，d ) 为协调决策信息系统，反( 七r ) 为所有决策约 简集，记 c = n 。；，b ：，k = u 。；，反一c ，= a - t 3 。；，b ：。 a c 时称a 为决策核心，c 称为决策核心集；n k 时称口为决策相对必要属 性，k 称为决策相对必要属性集；a e ，时称口为决策不必要属性，称为决策 不必要属性集。 定理2 1 5 1 2 5 设( u ，一，d ) 为协调决策信息系统，则以下命题等价： ( 1 ) a 是决策核心： 西华大学硕士学位论文 ( 2 ) 存在t ，x ，u ，b ( 】， x 儿) = a ) ； ( 3 ) r , i - l a i ! r d 。 定理2 1 6 1 5 设( u ，a ，f ，d ) 为协调决策信息系统，则a 为决策不必要属性 当且仅当r ( 口) r 。u r 。，其中 f ( 4 ) = u r 川。 l r 口r d ，b a 。 定理2 1 7 1 1 5 设( u ，a ，f ，d ) 为协调决策信息系统，则有以下结论： ( 1 ) a 是决策核心当且仅当r “。，! 岛： ( 2 ) a 是决策相对必要属性当且仅当r 川。l 髓，且r ( 日) ! 量r 。u 心； a 是决策不必要属性当且仅当r 。似) 胄。u 凡。 2 1 7 不协调决策信息系统 在管理决策中，我们大量面对的是不协调决策信息系统，因此针对这种信 息系统研究决策问题，更具有实践意义。在研究不协调决策信息系统时，我们 遇到的不再是包含关系，而是集合之间的包含程度，为此引进包含度的概念。 定义2 1 4 1 2 6 设u 为有限论域，对于任意x ，y u ，称o ( r x ) 为包含度， 若满足以下条件： ( 1 ) 0 d ( y x ) 1 ； ( 2 ) 当x y 时y ，d ( y x ) = 1 ； ( 3 ) 当x 互y z 时，d ( x z ) d ( x y ) 。 哪饼，= 晋，刚省，= 饼。 显然( 1 ) 式表达的是包含度。 定义2 1 5 1 2 7 设( u ，a ，f ，