（系统理论专业论文）粗糙集理论在决策支持系统中的应用研究.pdf

独创性声明及论文使用授权说明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得亡东技盔 垣范堂院或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 = 匕 恩。 本人完全了解广东技术师范学院有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。同意亡塞撞盔垣范 邋将本人的学位论文提交清华大学中国学术期刊( 光盘版) 电子杂志社 全文出版和编入c n k i 中国知识资源总库，传播学位论文的全部或部分 内容。 d 公开 口保密( 午一月) ( 保密的学位论文在解密后应遵 守此协议) 学位论文作者签名：查兰垒导师签名：直暨重 签字日期：圣里堕篁：兰墨签字日期：z 竺也羔! 塑 摘要 当今是知识大爆炸的时代，如何从海量数据中提取有效信息，进行决策分析至关重 要。决策支持系统是建立在管理科学、运筹学、计算机技术等学科的基础上，综合利用 大量数据、结合不同模型，利用智能作用的人一机计算机系统，为决策者提供科学决策 的系统。粗糙集理论是一种处理模糊和不精确问题的新型数学工具，其理论方法应用到 决策支持系统中处理信息的功能日益显著。 本文介绍了决策支持系统的功能、结构等以及粗糙集理论的基本理论知识，并且提 出了基于粗糙集理论的决策支持系统模型。该模型利用粗糙集理论与算法对决策表的进 行化简处理，从而为决策支持系统提供决策辅助。 本文对粗糙集理论算法进行改进，并将其应用到决策支持系统中。重点对基于差别 矩阵的决策表属性约简算法和基于邻域粗糙集模型的前向贪心数值属性约简算法进行 改进，其思路是利用属性重要度和边界区域作为启发运算因子，从相对刃核出发，将其 扩展为一个最佳属性约简，且减少了搜索空间。同时本文证明改进算法的合理性，并且 与原先算法进行分析对比，结合毕业论文成绩评定表和汽车数据库表进行实例分析，计 算结果表明，在获得相同的结果下，改进算法可以使计算量减少，提高计算效率，进而 验证了基于粗糙集的决策支持系统模型和改进算法的可行性、有效性。 关键词粗糙集；决策支持系统；信息系统；决策表；属性重要度 a b s t r a c t t o d a yi s t h ee r ao fk n o w l e d g ee x p l o s i o n , i ti s v i t a lt h a th o wt oe x t r a c te f f e c t i v e i n f o r r m t i o nf r o mt h el m s so fd a t aa n dm a k ed e c i s i o na n a l y s t s d e c i s i o ns u p p o r ts y s t e mi sa s y s t e mw h i c hp r o v i d ess c i e m i f i cd e c i s i o n - m a k i n gf o rp o l i c yt i n k e r sw i t hu s i n gi a r g ea m o u n t s o fd a t a ，c o m b i n i n gd i f f e r e n tm o d e l s ，u t i l i z i n gi n t e l l i g e n tl r n n m a c h i n ec o m p u t e rs y s t e m ，o n t h eb a s i so f m a n a g e m e n ts c i e n c e ，o p c r a t i o m lr e s e a r c ha n dc o m p u t e rt e c h n o l o g ya n ds o0 1 1 r o u g hs e t st h e o r yi san g wk i n do fm a t h e m a t i c a lt o o l sd e a l i n gw i t hf u z z ya n di n a c c u r a c i e s p r o b l e m s ，a n di t sf u c t i o no fd e a l i n gw i t hi n f o r r m t i o ni sb e c o m i n gi n c r e a s i n g l ys i g n i f i c a n ti n t h et h e o r e ti c alm e t h o d s 印p l i e d t h et h e s i si n t r o d u c e st h ef u n c ti o n , s t r u c t u r eo ft h ed e c i s i o ns u p p o r ts y s t e ma n d e l e m e n t a lt h e o r e t i c a l k n o w l e d g e o ft h er o u g hs e t st h e o r y ，a n d p u t sf o r w a r dd e c i s i o n s u p p o r ts y s t e mr m d e lw h i c hi sb a s e do nr o u g hs e t st h e o r y t h em o d e ls i m p l i f yt r e a t sw i t h t h ed e c i s i o nt a b l eb yu s i n gr o u g hs e t st h e o r ya n da l g o ri t h m s ，s oa st op r o v i d ed e c i s i o n a s s i s t an tf o rd e c i s i o ns u p p o r ts y s t e m t h er o u g hs e t s t h e o r ya l g o r i t h m sa r ei m p r o v e da n da p p l i e dt od e c i s i o ns u p p o r t s y s t e r m i nt h et h e s i s f o c u so ni m p r o v i n gt h eh e u r i s t i ca t t r i b u t er e d u c t i o na l g o r i t h mb a s e d o nd i s c e r n i b i l i t ym a t r i xa r daf o r w a r d - o r e e d yn u m e r i c a la t t r i b u t er e d u c t i o na l g o r i t h mb a s e d o nn e i g h b o r h o o d b a s e dr o u g hs e t t h ei m p r o v e m e mo f r o u g hs e t st h e o r ya l g o r i t h m sm a i n l y m a k e s 戳o fa 心i b u t e - i m p o r t a n c ea n dt h eb o r d e rm g i o na sah e u r i s ti c o p e r a t i o nf a c t o r , s t a n i i l gw i t ht h er e h t i v ed n u c l e a ra n dt h e ne x p e n di n gt ot h e t h er e h t i v ed n u c l e a r ，a n d r e d mi n gt h es e a r c hs p a c e a tt h e m 薯t i m e ，t e s t i f i e st h er a t i o m l i t yo f t i ni m p r o v e da l g o r i t h m b ya n a l y z i n ga n dc o m p a r i n gw i t ht h eo r i g i n a la l g o r i t h m t h et h e s i sd o e sm a n yc a s e s c o m b i n e dw i t hg r a d u a t i o nt h e s i sa c c o m p l i s h m e n te v a l m t i o nt a b l ea n da u t o m o t i v ed a t a b a s e ， a n d 此i 塔r e s u l t sd e r n o n s t r a t e dt h a tt h ei m p r o v e da l g o r i t h mc a l lr e d u c ec a l e u h t i n gq u a n t i t y a n di m p r o v ec o m p u t a t i o m le f f i c i e n c y ，a n dv e r k f yt h ef e a s i b i l i t ya n de f f e c t i v e n e s so ft h e d e c i s i o ns u p p o r ts y s t e mm o d e la n dt h ei m p r o v e da l g o r i t h m k e yw o r d sr o u g hs e t ；d e c i s i o ns u p p o r ts y s t e m ；i n f o r n 舱t i o ns y s t e m ；d e c i s i o nt a b l e ； a t t r i b u t e - i m p o r t a n c e i i 目录 摘要i a b s t r a c t ii 目录1 i i 第一章绪论1 1 1 课题研究的背景和意义1 1 2 粗糙集理论的研究现状综述2 1 2 1 研究方法3 1 2 2 粗糙集模型扩展4 1 2 3 粗糙集理论与其他理论的结合5 1 3 本文的主要研究内容6 第二章决策支持系统与粗糙集理论概述7 2 1d s s 眵 主墨。7 2 1 1d s s 白勺刃哆成。7 2 1 2d s s 的任务与功能8 2 1 3d s s 的体系结构9 2 1ad s s 研究模型与方法1 0 2 2 粗糙集基本理论一一l l 2 2 1 知识与分类1 2 2 2 2 粗糙集的基本定义及其性质1 3 2 2 3 粗糙集的数字特征。1 5 2 2 aj i 玎鼋 乡勺简1 6 2 2 5 信息i 毛示。l8 2 3 基于粗糙集的决策支持系统1 9 2 3 1 决策表转换处理。2 0 2 3 2 简化决宝惫表。2 1 2 3 3 规划化简一2 2 2 3 a 基于粗糙集的决策支持系统模型2 3 2 。4 本章，j 、宝占一。2 4 第三章知识约简算法2 5 3 1 基于粗糙集理论的决策表的属性约简算法。2 5 3 1 1 决策表的盲目删除属性约简算法2 5 3 12 基于p a w l a k 属性重要度的决策表的属性约简算法。2 6 3 1 - 3 基于s k o w r o n 差别矩阵的决策表的属性约简算法一2 7 3 1 4 基于差别矩阵和逻辑运算的属性约简算法与改进2 8 3 1 5 基于互信息的属性约简算法一一2 9 3 2 基于邻域粗糙集模型的属性约简算法一3 0 3 2 1 邻域粗糙集模型的基本概念3 0 3 2 2 基于邻域粗糙集模型的前向贪心数值属性约简3 3 3 3 决宝受表的值约简。3 3 3 3 1 决策表值约简的重要概念3 3 3 3 2 决策表盲目删除值约简算法3 4 3 3 3 决策表启发式值约简算法一3 4 1 1 1 3 4 爿区章j 、结。3 5 第四章算法改进与实例分析3 6 4 1 基于差别矩阵的决策表属性约简算法的改进3 6 4 1 1 基于差别矩阵改进算法分析c t r 一3 8 4 2 基于邻域粗糙集模型的前向贪心数值属性约简算法的改进4 0 4 2 1 基于r o u g hs e t 的毕业论文质量决策分析4 2 4 2 2 2 基于前向贪心数值属性约简算法及其改进的实例分析一一4 8 4 3 本章d 、结。一。5 l 第五章结论5 2 参考文献5 4 致谢5 8 攻读学位期间进行的相关工作5 9 i v 第一章绪论 第一章绪论 当今社会是信息化社会的时代，随着经济和社会的快速发展，计算机、网络、通讯 等信息技术的突飞猛进的发展，使得人们在各个领域获取的数据和信息量急剧膨胀( 信 息爆炸) ，同时由于人为、环境等因素的影响，进一步使得海量数据和信息的不确定性 更加显著，数据信息之间的关系变得尤为复杂( 复杂系统) 。而手工处理数据已经不能 满足人们的需求，因其分析获取有效数据的能力十分有限，所以从海量信息和数据中辨 识真假信息、保证信息的安全以及信息形式的统一等变得尤为重要。为了实现由计算机 自动组织和协调处理大规模数据，帮助人们及时发现有效的知识，从而达到更高层次的 辅助决策能力，决策支持系统( d e c i s i o ns u p p o r ts y s t e m d s s ) 应运而生。 1 1 课题研究的背景和意义 2 0 世纪7 0 年代初期，s c o t tm o r t o n 教授最先提出了d s s 的重要概念，将其定义为 一种交互式的基于计算机的系统，该系统能够帮助决策者使用数据和模型解决非结构化 的问题。经过后人的不断的扩展和完善，该定义最终概括为：d s s 是以管理科学、运筹 学、控制论和行为科学为基础，以计算机技术、模拟技术和信息技术为手段，面对半结 构化的决策问题，支持决策活动的具有智能作用的人机计算机系统。它能为决策者提 供决策所需要的数据、信息和背景资料，帮助明确决策目标和进行问题的识别，建立或 修改决策模型，提供各种备选方案，并对各种方案进行评价和优选，通过人机对话进 行分析、比较和判断，为正确决策提供有益帮助。 2 0 世纪9 0 年代中期从人工智能、机器学习中发展起来的数据挖掘技术从数据库和 数据仓库中挖掘知识，并将其放入d s s 的知识库中，进行知识推理以达到定性分析辅 助决策的目的。把数据仓库、o l a p 、数据挖掘、模型库结合起来形成的综合决策支持 系统，是更高形式的决策支持系统，是现今d s s 的发展方向。其中数据仓库能够实现 对决策主体数据的存储和综合，o l a p 实现多维数据分析，数据挖掘用以挖掘数据库和 数据仓库中的知识，模型库实现多个广义模型的组合辅助决策，集成的综合决策支持系 统，将互相补充、互相依赖，发挥各自的辅助决策优势，实现更有效的辅助决策。 决策支持系统中首先要处理海量的数据存在不确定性问题，有概率论方法、模糊集 方法和证据理论方法等方法来处理该问题，但这些方法需要提供处理数据集合之外的任 广东技术师范学院硕士学位论文 何先验信息【l l 。粗糙集理论与方法正是在这种情况下逐步建立发展起来的，它在处理不 确定性问题同其他理论的显著区别在于无须提供所处理数据之外的任何先验信息。它已 经成为一种新型的数学工具，并且粗糙集理论与模糊集合论、概率论和证据理论之间相 互结合，相互互补，提高处理问题的能力。 将粗糙集理论应用的决策支持系统( d s s ) q a ，提高了其处理问题的能力。而粗糙集 理论的核心内容之一是知识约简( r e d u c t i o no f k n o w l e d g e ) ，它主要处理的是信息系统或 决策表中给出的所有知识是否必要，即在保持原始信息系统或决策表的分类能力不变的 前提下，删除知识表达系统中冗余知识。这样一方面节省资源( 存储空间) ；另一方面， 便于人们做出正确预测分析与决策。知识约简包括属性约简和属性值约简，所谓属性约 简是指在保持数据库分类或决策能力不变的条件下，删除其中不必要的、不重要的或不 相关的属性。属性值约简则是在属性约简的基础上，再进一步对不重要的属性值进行删 减处理，从而得到规则提取，因此这两者操作是相互联系紧密结合的，属性约简是前提 基础，属性值约简属性约简的必然趋势。对于一个知识库，其对应的决策表可能存在多 个属性约简。因为知识约简的目的是导出关于决策表的决策规则，约简中属性的多少直 接影响着决策规则的繁简。 属性约简过程中往往得到的多个约简结果，但事实上，我们所需要的是最佳相对 约筒( 简称最佳约简) ，所谓最佳约简是指一个标准约简，即约简后得到的属性数最少， 或最终得到的规则最简，或全部数据约简量最大1 2 。然而，s k mw o n g 和w z a r k o 已 经证明了找出决策表的最小约简是n p 难完全问题，导致n p 难完全问题的主要原因是 属性的组合爆炸问题。因此，寻求高效的属性约简算法人们热门研究的方向之一。 1 2 粗糙集理论的研究现状综述 粗糙集理论是波兰科学院z p a w h k 院士于1 9 8 2 年提出的一种关于数据分析和推理 的理论。它把那些无法确认的个体都归于边界线区域，这个区域被定义为上近似和下近 似之差集，由于上近似和下近似都可以通过等价关系给出确定的数学描述，所以含糊元 素数目可以被计算出来，从而真假二值之间的含糊程度可以计算 3 1 。最初关于粗糙集理 论的研究主要集中在东欧国家，但是并没有引起重视。直到1 9 9 0 年前后，由于粗糙集 理论在数据挖掘、决策分析、模式识别、机器学习和智能控制等方面的成功应用，才得 到国际人工智能与模式识别研究学者的广泛关注，并开始注重其应用研究。1 9 9 1 年， 2 第一章绪论 z p a w h k 的专著r 0 u g hs e t s - - t h e o r e t i c a la s p e c si fr e a s o n i n ga b o u td a t a ) ) 【4 1 问世，标志 着粗糙集理论与应用的研究进入了活跃时期。粗糙集理论由其独特的方法、新颖的思想， 从而使其业已成为一种智能信息处理技术并且得以广泛应用。目前，有3 个有关粗糙集 的系列国际会议，即r s c t c 、r s f d g r c 和r s k t 。1 9 9 2 年，在波兰召开了关于粗糙集 理论的第一届国际学术会议1 9 9 5 年，a c m c o m m u n i c a t i o n 将粗糙集列为新浮现的计算 机科学研究课题。目前粗糙集理论现已成为人工智能和信息科学最为活跃的研究领域之 一，且对于认知科学也十分重要。在许多应用领域已得到了发展，如医学、管理学、金 融学、气象学、图像处理、语音识别、字符识别和决策分析等众多领域1 5 】。1 9 9 8 ，2 0 0 0 和2 0 0 2 年，分别召开了三届r s c t c ( r o u g h s e t sa n dc u r r e n tt r e n d si nc o m p u t i n g ) 国际 会议，表明粗糙集的研究已步入发展期。 中国国内在这方面也取得了很大的成果，1 9 9 3 年国家自然科学基金首次对数据库中 知识发现领域的研究项日给予资助。1 9 9 7 年苗夺谦完成了国内第一篇关于粗糙集理论的 博士学位论文粗糙集理论及其在机器学习中的应用研究，对粗糙集理论的知识表示、 知识约简算法以及在机器学习中的应用进行了较为系统的研究。2 0 0 1 年5 月，在重庆邮 电学院举办了首届中国粗糙集和软计算学术研讨会( c r s s c 2 0 0 1 ) ，2 0 0 3 年5 月，在重 庆邮电学院同时举办第三届中国粗糙集和软计算学术研讨会和第九届粗糙集、模糊集、 数据挖掘与粒度计算国际学术会议( r s f d g 疋2 0 0 3 ) 。随着粗糙集理论研究的逐步深入 发展以及在决策支持系统中的成功应用，粗糙集理论本身的研究和应用也成为热点研究 领域。 1 2 1 研究方法 从近似空间中导出上、下近似集是粗糙集理论与应用的核心基础，经典粗糙集模型 中不分明关系是一种等价关系，各个条件设置要求很高，因此推广定义上、下近似集成 为研究粗糙集理论的一个重点【6 】。 推广粗糙集理论的常用研究方法有构造化方法和公理化方法，其中构造化方法的主 要思路就是通过直接使用二元关系的概念来定义粗糙集的近似集，从而导出粗糙集代数 系统，即以论域上的二元关系、划分、覆盖、邻域系统、布尔子代数等作为基本要素， 进而定义粗糙近似算子，从而导出粗糙集代数系统。构造化方法所研究的问题源于实际 例子，因此其所建立的模型具有很强的应用价值，但不能深刻体现近似算子的公理的性 3 广东技术师范学院硕士学位论文 质，从而对其从公理化的角度研究得以发展。公理化方法的基本要素是一对满足某些公 理的一元集合算子，近似算子的某些公理能保证有一些特殊类型的二元关系的存在，然 后再去找二元关系使得由该二元关系及其生成的近似空间按构造化方法导出的近似算 子恰好就是给定的由公理化方法定义的集合算子；反过来，由二元关系通过构造性方法 导出的近似算子一定满足某些公理。 事实上，有两种形式来描述粗糙集，一个是从集合的观点来进行，一个是从算子的 观点来进行那么，从不同观点采用不同的研究方法就得到粗糙集的各种扩展模型扩 展模型的研究以及基于其上的应用研究已经成为新的研究热点。 有关构造化方法研究粗糙集理论的成果相对较多，而公理化方法的研究始于文献川， 其给出的公理组不独立，文献隅，9 1 对其进行了改进和进一步的深化补充。有关公理化研究 主要集中在极小化和独立性问题上，并且在这方面也取得了一定的成果 1 0 - 1 2 ，但还有待 于进一步的研究。 1 2 2 粗糙集模型扩展 粗糙集理论的一个重要的研究方向是粗糙集模型扩展，对其扩展模型包含有上下近 似的扩展定义、元素、粒、子系统、论域、关系、集合或近似空间等多个方面的一些扩 展模型，这些模型常常以交叉、相关、综合形式出现。 通过对上下近似定义的扩展，使得粗糙集理论中上下近似有不同的表达方式，进一 步可以衍生出粗糙集理论中的边界域、正域、负域等基本定义，定义的给出以及结合其 他理论为扩展粗糙集模型奠定了理论基础。 基于元素的扩展模型中，利用非等价关系扩展元素的粗糙集定义，用集合的观点分 析，如将元素z 的等价类看作是等价类a 办的一个邻域，从而得到基于邻域的粗糙集模 型【1 3 1 4 】。同时利用非等价关系来扩展基于元素的粗糙集定义可以得到，容差关系、相似 关系、量化容差关系、限制容差关系和特征关系等等。从算子的观点看，模态逻辑中的 必然性算子和可能性算子与粗糙集模型中的近似算子相结合，从而得到模态逻辑的公理 化系统，同时也是一个粗糙集代数系统f 1 5 1 6 1 。 从等价类的角度讨论粗糙集便可得到基于粒的粗糙集定义，在经典的粗糙集粒计算 模型中，划分就是一个基本粒。扩展划分的概念，就可以得到基于粒的扩展粗糙集模型 文献【1 2 】对覆盖广义粗糙集理论进行了深入的研究，扩展粗糙集模型利用到不同的粒度结 4 第一章绪论 构，如何利用非等价关系来扩展粒度概念以及从简单的单层结构到复杂的层次结构等加 以研究。还有一些文献对覆盖约简问题、覆盖冠以粗糙集模型以及不同类型的扩展覆盖 粗糙集模型及其关系f 1 7 】等作了探讨。该扩展主要结合了覆盖和形式概念分析理论，在这 方面未来的研究方向将是如何结合其他粒计算工具来扩展粗糙集理论。 扩展基于子系统的粗糙集模型，对于定义上下近似用到的是两个子系统，一个用于 定义上近似，另一个定义下近c a r s 。粗糙集理论结合拓扑、闭系统、布尔代数、格、偏 序等来来扩展深化之，设计出合适的子系统，使得粗糙集理论应用更加广泛化。 在经典的p a w h k 粗糙集模型中考虑的论域常常是当且仅当一个，文献【1 9 1 首次将粗 糙集模型推广成为两个不同但先关联的论域，从而出现对双论域模型的研究。同时一些 文献对双论域模型加以推广，并且应用到不确定性推理中，结合相关理论从多论域角度 研究粗糙集也是一个新的研究领域。 概率型的粗糙集模型在粗糙隶属度函数的基础上加以讨论。文献【2 0 】提出决策粗糙集 理论，从而了集合的上下近似的定义，分析发现有决策粗糙集导出了许多概率型粗糙集 模型，因此这些概率型粗糙集模型可视为决策粗糙集的特例。该方面的研究主要集中在 概率型上下近似集和正、负、边界区域特征；概率型规则的语义解释；概率型粗糙集属 性的约简理论等方面。 1 2 3 粗糙集理论与其他理论的结合 随着对粗糙集理论的不断深入研究，也暴露出其处理问题的局限性以及不可通用 性，因此为了更好的发挥粗糙集理论的功能常常使其结合其他理论来研究，实现优势互 补，共同推动理论的发展与应用。 粗糙集与d c m p s t e rs l 】a f e r 证据理论( 简称d - s 证据理论) 在处理不确定性的问题方 面，产生和研究的方法虽然不同，但有某种相容性，粗糙集理论是为开发规则的机器自 动生成而提出的，而d - s 证据理论主要用于证据推理。相关文献对两者的关系以及很强 的互补性等作以介绍，从代数学意义上来讲，任何具有概率特性的信任函数都可以有相 应的扩展粗糙集模型。 粗糙集理论与模糊集理论在处理不确定性和不精确性问题方面有效的推广了经典 集合论，由于两者的互补性，从而有学者提出了模糊粗糙集和粗糙模糊集的概念，并且 结合概率粗糙集模型进行了推广，应用模糊粗糙集进行属性约简和决策规则的获取以及 5 ，“东技术师范学院硕士学位论文 对各种扩展模型的实际应用作以探索。 其次，粗糙集理论和形式概念分析、知识空间以及粒计算相结合，在相关领域的研 究和应用都取得了一定的成果和突破，从而，从理论上推动了该学科的发展。 1 3 本文的主要研究内容 本文重点研究了粗糙集理论的属性约简算法以及值约简算法，并且将改进算法应用 到基于粗糙集的决策支持系统模型中。 本章系统阐述了决策支持以及粗糙集理论研究背景、现状及研究意义、方法等。 第二章首先介绍了决策支持系统的任务、功能、体系结构等基本相关概念；其次又 重点阐述了粗糙集理论的基本定义和理论，其中有知识和概念、不可分辨关系、集合的 上、下近似、近似精度、粗糙度、信息系统决策表等概念，为下面的算法分析研究奠定 了基础；最后提出了基于粗糙集的决策支持系统模型。 第三章是关于知识约简算法分析、对比与总结。分别对决策表的盲目删除属性约简 算法、基于p a w l a k 属性重要度的决策表的属性约简算法、基于差别矩阵的决策表的属 性约简算法、基于互信息的属性约简算法进行了详细阐述以及算法分析，最后又介绍了 决策表的值约简算法和规则提取。 第四章主要是我做的工作，对相关算法进行改进，并分析证明了算法的可行性以及 有效性。重点对基于差别矩阵的决策表属性约简算法进行深入研究并在此基础上利用合 适的属性重要度作为启发因子对该算法做了改进，分析其复杂度并证明了算法的合理 性。其次，又重点研究了基于邻域粗糙集模型的算法，该模型是利用拓扑空间中的球形 邻域的概念，对原有经典粗糙集理论的拓广，有效的处理了属性值是数值型数据的决策 表的属性约简问题，在此基础上对该算法进行了改进，优化了算法；同时，分别对毕业 论文成绩评定表和汽车数据库实例分析，运用基于差别矩阵的决策表的属性约简改进算 法和邻域粗糙集模型的改进算法，实例计算结果验证了属性约简算法的优越性，并得出 决策规则和做出预测分析。 第五章对全文进行系统回顾和总结，综述自己的研究工作，并且提出自己的不足及 其今后进一步研究学习的方向。 6 d s s 0 在不断的研究和吸收信息处理其他领域的发展成果，研究决策分析和决策制 定过程中所特有的某些问题，并不断地将其形式化、规范化，逐步用系统来取代人的部 分工作，以全面支持人更高层次的研究和更进一步的决策。目前，d s s 随着决策理论、 人工智能、运筹学、计算机网络。管理科学的发展而在理论与实践上都取得了长足的进 步，正朝着智能化、群体化决策化的方向发展。 2 1d s s 概述 2 1 1d s s 的形成 2 0 世纪7 0 年代，计算机技术在企业管理领域的应用重点逐渐转移到了信息处理和 决策支持上，有管理信息系统( m a m g e r m n ti n f o r m a t i o ns y s t e m s m i s ) 发展为决策支持系 统。决策支持系统则把管理信息系统和模型辅助决策系统结合起来，将m i s 的数据处理 与模型的数值计算融为一体，提高了辅助决策的能力。 ( 1 ) 管理信息系统 随着计算机在数据处理领域的成功应用，2 0 世纪6 0 7 0 年代兴起了管理信息系统的 研究和应用的热潮。管理信息系统是在数据处理系统( d a t ap r o c e s s i n gs y s t e m s d p s ) 的 基础上，采用管理科学的方法和现代信息技术，对管理信息进行收集、存储、维护、加 工、传递和利用，实现广泛的业务规划、管理运行、调控和预测的信息系统。它是由大 容量数据库支持、以数据处理为基础的计算机应用系统。由于管理信息系统是从系统的 观点出发，把分散的信息组织成一个比较完善的信息系统，从而提高了信息处理的效率， 也提高管理水平。 管理信息系统的主要功能是事务处理，并且包含了多个数据处理系统，为结构化决 策服务，具有系统一切特征，是实际管理系统的一部分，同时管理信息系统是以数据库 系统为基础建立起来的。它具备事务处理、数据库的更新和维护、产生各类报表、查询 处理、用户与系统的交互作用等功能。由此可见管理信息系统m i s 开发主要是利用数据 库语言编制程序，数据库语言的主要功能是对数据进行输入、修改、查询等。因此，开 发出的管理息系统在模型辅助决策上存在不足，它只能以数据和信息的形式辅助决策。 ( 2 ) 模型辅助决策系统 7 广东技术师范学院硕士学位论文 模型的工作有两类：一是建立模型；二是使用模型。 首先建立模型是各个领域的专家学者通过大量的观察实验分析，得到规律性模型或 相近的数学模型，以及从事物变化规律中抽象出他们的数学模型。其次，建立模型后就 是使用该模型，即求解模型的算法，通常通过计算机数值计算来完成，求出精确求解或 者近似求解。模型算法一般都可以通过计算机语言编程实现，实际的决策者利用计算机 在模型程序上运行，获得结果得到辅助决策信息。 ( 3 ) 决策支持系统 2 0 世纪8 0 年代决策支持系统迅速发展起来并成为新兴的计算机学科，其实质上是 在管理信息系统和运筹学的基础上发展起来的。前者主要是大量数据的处理，后者是运 用单模型辅助决策。随着科技发展，出现多模型来解决一个复杂系统。为了实现由计算 机自动组织和协调多模型的运行，对大量数据库中数据的存取和处理，达到更高层次的 辅助决策能力，决策支持系统应运而生。决策支持系统的新特点是增加了模型库和模型 库管理系统，它把众多的模型有效地组织和存储起来，并且建立了模型库和数据库的有 机结合。它们的有机集成，既具有数据处理功能，又具有数值计算功能。当今社会，面 对海量的数据信息，从中发现识别出高效有价值的信息变得至关重要，而决策支持系统 的产生就很好的解决了这方面的问题。 2 1 2d s s 的任务与功能 d s s 的主要任务包括以下几个方面，分析和识别问题；描述和表达决策问题以及决 策知识；形成候选的决策方案( 目标、规则、方法和途径等) 、构造决策问题的求解模 型；建立评价决策问题的各种准则；多方案、多目标、多准则情况下的比较和优化、综 合分析等。 为了完成d s s 的任务，辅助管理者做好决策工作，d s s 应具备如下功能，整理并 及时提供本系统与本决策有关的各种数据以及系统之外的其他相关数据；及时收集与系 统有关的各项活动的反馈信息和数据；能够用一定的方式存储于所研究的决策问题有关 的各种模型；能够存储及提供常用的数学与运筹学的方法；能够灵活的运用模型与方法 对数据进行加工、汇总、分析、预测，以便用户随时得到所需要的综合信息与预测信息； 提供方便的人机对话接口和图形输出功能，不仅能够随即查询所要求的数据，而且能 够回答假设或虚拟之类的问题；数据挖掘、数据分析，利用决策系统的分析工具揭示已 3 第二章决策支持系统与粗糙集理论概述 有数据间的关系和隐藏着的规律性，也能够反过来预测它的发展趋势，或者在一定条件 下会出现的结果；生成d s s 数据分析图表以及相关报表等功能。 2 1 3d s s 的体系结构 d s s 的体系结构是指构成d s s 的各组成部分的排列、组织和互相结合的方式。d s s 框架可以分为两大类：一类是s p r a g u e 型的基于x 库的框架结构，另一类是b o m z e k 型 的基于知识的框架结构。前者以各种库及其管理系统作为d s s 的核心，后者则以问题 子系统作为系统的主要部分。 ( 1 ) 基于x 库的体系结构 s p r a g u e 提出的两库系统有三个部分组成，它们分别是数据库及其管理系统、模型 库及其管理系统和对话系统。其中数据库系统负责存储和管理d s s 使用的各种数据并 实现不同的数据源间的相互转换；模型库存放预定的标准模型，支持模型的管理和各种 分析与运算；对话系统负责接受用户的请求，并向用户提供决策结果。 基于x 库的结构模式为d s s 提供了支持内核，而且随着各库的增加，使d s s 的功 能由定量计算扩大到定量计算与定性分析相结合，方便了对模型的管理，也使人机界 面变得更友好，对d s s 发展产生了很大的推动作用。然而，基于x 库d s s 结构模式并 没有反映出d s s 不同于其他计算机信息系统的特点，如决策者是d s s 的主体，人机协 同操作等，因此具有一定的局限性。 ( 2 ) 基于知识的d s s 体系结构 基于知识的d s s 体系结构模式由语言子系统( l s ) 、知识库子系统( k s ) 和问题处 理子系统( p p s ) 三部分组成。如图2 1 所示： 图2 - l 基于知识的d s s 结构 9 广东技术师范学院硕士学位论文 语言子系统是用户与系统联系的工具，用户的问题通过语言子系统来描述和响应。 知识库子系统是d s s 能够解决用户问题的智囊，主要包括一个综合性的知识库，其中存 放的是有关问题的各种知识。问题处理子系统是d s s 的核心部分，它完成系统的动态的 过程，即接受用户的问题，运用知识库子系统的知识，实现用户问题的求解过程。 d s s 的各个子系统之间有着非常紧密的联系，良好的结构应使个组成部分有机地结 合起来，在实际简历d s s 时，可以由上述两种基本结构通过分解或增加某些部件而演变 出多种形式。 ( 3 ) 基于数据仓库的综合决策支持系统 2 0 世纪9 0 年代后，d s s 进入了一个以数据仓库和o l a p 技术及数据挖掘技术的研究 热潮，使得d s s 的的发展出现了崭新的舞台。现阶段开发的综合决策支持系统是以数据 仓库技术为基础，以联机分析处理和数据挖掘工具为手段进行实施的一整套解决方案。 一般决策所需的数据总是与一些维数和不同的级别的统计和计算有关。决策的主要内容 是以多维数据为核心的多维数据分析，数据仓库的多维特征克服了数据库的数据组织性 差、利用率低的缺点，满足决策支持系统对数据的分析要求。总之，基于数据仓库的综 合决策支持系统的研究重点是如何利用数据仓库及相关技术来发现有效知识并且和用 户进行交互，克服了传统决策支持系统获取知识的瓶颈，为决策支持提供了更加有效的 数据支持。 2 1 4d s s 研究模型与方法 决策支持系统中处理的数据大都具有不确定性、不完整性以及非结构化的。因此模 型库中的模型一般都采用有效地处理数据的方法，例如有粗糙集、神经网络、遗传算法、 统计方法等方法，这些方法都有一定的适用范围和特点，并且都得到了一定的实际应用 粗糙集理论与方法是针对不确定性问题提出的，其特点是不需要预先给定的某些特 征或属性的数量描述，而是直接从给定的问题的描述集合出发，通过不可分辨关系和不 可分辨类确定给定问题的近似域，从而找出该问题的内在规律。基本思想是将数据库中 的属性分为条件属性和决策属性，对数据库中的元组根据各个属性的不同的属性值分成 相应的子集，然后对条件属性划分的子集与结论属性划分的子集的上下近似关系生成判 定规则。由于粗糙集方法中的决策表可以被视为关系型数据库中的关系表，因此其伸缩 1 0 第二章决策支持系统与粗糙集理论概述 性、鲁棒性和抗噪音能力都较强，知识的可理解性和开放性较好；比较适用于符号信息。 粗糙集理论还具有和其他理论方法的很强的互补性，多方法的融合将会是粗糙集理论的 应用大显威力。 神经网络方法是模仿生物神经网络功能的一中经验模型方法。神经网络是有若干简 单元件及其层次组织，以大规模并行连接方式构造而成的网络，按照生物神经网络类似 的方式处理输入的信息，对输入信号有功能强大的反映和处理能力。该方法的优点是不 需要主管知识的支持，具有自稳定性，鲁棒性、抗噪音能力和精确性较好。但其伸缩性 较差以及结果的可理解性和开放性都不理想。 遗传算法采用了自然进化模型，如选择、交叉、变异、迁移等。它从初始种群出发， 计算每个个体的适应度函数，第一代就产生了。若不满足优化准则，开始产生新一代的 计算。为了产生下一代，按照适应度选择个体，父代要求基因交叉而产生子代。所有的 子代按一定该类变异，然后子代的适应度有被重新计算。子代被插入到种群将父代取而 代之，构成新的一代，循环执行直到满足优化准则为止。遗传算法与传统的优化方法( 枚 举，启发式等) 相比较，以生物进化为原型，具有很好的收敛性，在计算精度要求时， 计算时间少，鲁棒性高等都是它的优点。遗传算法已经不能很好的解决大规模计算量问 题，它很容易陷入“早熟”。常用混合遗传算法，合作型协同进化算法等来替代。 统计模型的方法中概率统计技术主要是针对结构化的数据，其优点是训练样本不必 几何可分，对噪音和畸变不敏感等，但是需要用户提供先验概率和条件概率分布形式， 其性能受主观知识的影响较大。其抗噪音能力强，可伸缩性、精确性、鲁棒性和开放性 都较好，能够处理不完全的数据；可发现隐藏在数据中的因果模型，可很容易地结合领 域知识；其缺点在于模型的复杂度随网络中节点的增加而呈指数级增长，