（计算机应用技术专业论文）基于面向对象数据库的粗糙集模型的研究.pdf

摘要 摘要 粗糙集理论不依赖于所需处理的数据集合之外的任何先验信息，它对不精确、不确 定、不完整的信息和知识具有很强的分析处理能力。2 0 世纪5 0 年代末以来，关于粗糙 集理论和应用的研究逐渐成为智能信息处理领域的热点问题。 传统的粗糙集理论在数据挖掘中的应用大多是通过结构化的方法来实现的，但是这 种方法存在着数据模型结构性不强、软件复用率低、可扩展性差等主要问题。另外，基 于粗糙集的属性约简系统大多是针对某一特定关系型数据库或格式化的数据文件而设 计的，因此很难描述复杂对象，缺乏灵活性与通用性，难以满足研究和应用的需要。 为了解决这些问题，本文将面向对象理论和粗糙集理论相结合，在传统粗糙集理论 应用的基础上引入面向对象数据库，设计了种用于属性约简的对象模型和约简模型， 并充分考虑到面向对象数据库对复杂对象具有优越的存储、检索能力，从而提出了一个 基于面向对象数据库的粗糙集模型，并深入探讨了该模型实现属性约简算法的关键技 术。实验结果表明，该模型不但能有效地对数据集进行约简，而且还具有结构简单、具 有良好的扩展性等优点。此外，本文所提出的对象模型同样适用于其它的数据挖掘系统。 具体研究工作如下： ( 1 ) 当处理大数据集时，基于主存的粗糙集属性约简算法的效率将会显著下降。针 对这一问题，本文利用数据库技术处理大数据集问题的优越性，提出了一种基于存储过 程的属性约简算法。实验结果表明，对于处理大数据集问题，该算法的效率要比基于主 存的属性约简算法的效率高，而且该算法容易实现，具有一定的实用价值。 ( 2 ) 目前大部分的属性约简算法采用结构化方法实现，但是缺乏统一的数据模型， 针对这一问题，本文采用面向对象理论来分析r o u g h 集的研究对象，设计了一种用于属 性约简的对象模型，并使用面向对象数据库d b 4 0 对此进行建模。 ( 3 ) 在传统的粗糙集理论的基础上引入面向对象数据库，提出了一种基于面向对象 数据库的粗糙集模型。 ( 4 ) 深入探讨了实现属性约简算法的关键技术，并开发了一个专业数据处理软件系 统一基于面向对象数据库的粗糙集模型的属性约简系统，用于验证上述研究成果。 关键词：面向对象数据库；粗糙集；属性约简；对象模型：d b 4 0 大连交通人学t 学硕十学位论文 a b s t r a c t r o u g hs e tt h e o r yi si n d e p e n d e n to fa n yf o r e g o i n gi n f o r m a t i o nw h i c hi se x c l u d e do f p r o c e s s e dd a t as e t s ，a n di ti san e we f f e c t i v em a t h e m a t i ct o o lt od e a lw i t ht h eu n c e r t a i n t y ， i m p r e c i s i o na n di nc o m p l e t i o n s i n c et h ee n do f19 8 0 s ，r o u g hs e th a sb e c o m eh o t s p o t g r a d u a l l yi nt h ei n t e l l e c t u a li n f o r m a t i o np r o c e s s i n gf i e l d a l t h o u g ht r a d i t i o n a lr o u g hs e tt h e o r ya p p l i c a t i o n si nd a t am i n i n ga r ea l m o s tb a s e do n s t r u c t u r e dm e t h o d ，i tc a np o s s i b l yi n v o l v ei s s u e ss u c ha sp o o rs t r u c t m a li n t e g r i t yo fd a t a m o d e l ，l o ws o f t w a r er e u s ea n dl a c ko fe x t e n s i b i l i t y m o r e o v e r ，t h es y s t e m sb a s e do nr o u g hs e t a t t r i b u t er e d u c t i o na r em o s t l yd e s i g n e df o ras p e c i f i cr e l a t i o n a ld a t a b a s eo rf o r m a t t e dd a t af i l e t h e r e f o r e ，i ti sd i f f i c u l tt od e s c r i b ec o m p l e xo b j e c t sa n dt om e e tt h en e e d so fr e s e a r c ha n d a p p l i c a t i o nb e c a u s eo ft h el a c ko ff l e x i b i l i t ya n dv e r s a t i l i t y t os o l v et h i sp r o b l e m ，t h i sp a p e rc o m b i n e so b j e c t o r i e n t e dt h e o r yw i t hr o u g hs e ta t t r i b u t e r e d u c t i o nm e t h o d o l o g yt od e s i g na no b j e c tm o d e la n da na t t r i b u t er e d u c t i o nm o d e l ，w h i c hc a n b ev i e w e da sa no b je c t - o r i e n t e da t t r i b u t er e d u c t i o nm o d e lb a s e do nr o u g hs e t t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h em o d e ln o to n l ye f f e c t i v e l yr e d u c e st h ea t t r i b u t eo fr o u g h s e t ，b u ta l s oh a st h ea d v a n t a g e so fs i m p l es t r u c t u r ea n dg o o de x t e n s i b i l i t y 。i na d d i t i o n ，t h e o b j e c tm o d e lp r o v i d e di nt h i sp a p e ri sa l s os u i t a b l ef o ro t h e rd a t am i n i n gs y s t e m s t h es p e c i f i cr e s e a r c hw o r ki sl i s t e d ： ( 1 ) t h ee f f i c i e n c yo ft h ea l g o r i t h mf o ra t t r i b u t i o nr e d u c t i o ni nr o u g hs e tb a s e do nm a i n m e m o r yw i l lb es i g n i f i c a n t l yr e d u c e dw h e nd e a l i n gw i t hl a r g e rd a t as e t s t os o l v et h i s p r o b l e m ，t h i sp a p e rp r o p o s e sa na l g o r i t h mf o ra t t r i b u t i o nr e d u c t i o nb a s e do ns t o r e dp r o c e d u r e ， u s i n gt h es u p e r i o r i t yo ft h ed a t a b a s et e c h n o l o g y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e e f f i c i e n c yo ft h ea l g o r i t h mi ss i g n i f i c a n t l yh i g h e rt h a ns o m eo t h e ra l g o r i t h m sb a s e do nt h e m a i nm e m o r yi nd e a l i n gw i t hl a r g ed a t as e t s i na d d i t i o n ，t h ea l g o r i t h mc a nb ee a s i l yr e a l i z e d ， a n dh a ss o m ep r a c t i c a lv a l u e ( 2 ) a tp r e s e n tm o s to ft h ea t t r i b u t er e d u c t i o na l g o r i t h m su s es t r u c t u r e dm e t h o d s ，b u tt h e s e m e t h o d sa r el a c ko fu n i f i e dd a t am o d e l i nv i e wo ft h i si s s u e ，t h ep a p e ra n a l y s e st h es u b j e c t s o fr o u g hs e tu s i n go b j e c t - o r i e n t e dt h e o r ya n dd e s i g n sa no b j e c tm o d e lf o rt h ea t t r i b u t e r e d u c t i o n ，m o d e l i n gi tw i t ho b j e c t - o r i e n t e dd a t a b a s ed b 4 0 ( 3 ) t h i sp a p e rp r o p o s e sar o u g hs e tm o d e lb a s e do nt h eo b j e c t o r i e n t e dd a t a b a s eo nt h e b a s i so ft h et r a d i t i o n a lr o u g hs e tt h e o r yw i t ht h ei n t r o d u c t i o no fo b j e c t o r i e n t e dd a t a b a s e s ( 4 ) at h o r o u g hd i s c u s s i o ni s g i v e nt o t h ek e yt e c h n o l o g i e st oa c h i e v et h ea t t r i b u t e r e d u c t i o na l g o r i t h m ap r o f e s s i o n a ld a t a p r o c e s s i n gs o f t w a r es y s t e m ，w h i c hi sa na t t r i b u t e n r e d u c t i o ns y s t e mo fr o u g hs e tm o d e lb a s e do no b j e c t - o r i e n t e dd a t a b a s e ，i sd e v e l o p e dt o v e r i f yt h er e s e a r c hr e s u l t sm e n t i o n e da b o v e k e yw o r d s ：0 b j e e t - o r i e n t e dd a t a b a s e ；r o u g hs e t ；a t t r i b u t er e d u c t i o n ；0 b j e c tm o d e l ： d b 4 0 绪论 绪论 粗糙集理论i l l 是波兰数学家z p a w l a r k 于19 8 2 年首先提出的一种研究不完整、不确 定知识和数据的表达、学习、归纳的分析理论，一种处理含糊和不精确性问题的新型数 学工具。粗糙集起源于对谓词逻辑创始人c f r e g e l 9 0 4 年提出的“含糊”概念的研究， 视知识为对对象分类的能力，定义了上下近似集等核心概念。由于上下近似集都可以通 过等价关系给出确定的数学公式描述，所以含糊元素数目可以被计算出来，即在真假二 值之间的含糊度可以计算，从而实现了g f r e g e 的边界思想，也克服了模糊集没有给出 含糊概念的数学公式和无法计算边界线上具体含糊元数目的缺陷。 粗糙集自提出来就一直得到模糊数学的创始人z a d e h 的重视，并给予很高的评价， 把它列入他所新提倡的软计算的基础理论之一。1 9 9 1 年z p a w l a r k 的专著( ( r o u g h s 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 ) ) 的问世，标志着粗糙集理论及其运用 的研究进入了新的阶段。1 9 9 2 年在波兰召开了关于粗糙集理论的第一届粗糙集会议， 1 9 9 5 年a c mc o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学的研究课题。2 0 0 3 年召 开了第九届国际粗糙集学术大会和第三届中国粗糙集学术研讨会。当前许多国际重要学 术会议和学术研讨班都把粗糙集理论的研究列为会议和研讨班的重要内容。 粗糙集理论自问世以来，无论是在理论或实际上都是一种新的、最重要的并且是迅 速发展的一门既有理论又有应用的研究领域。对于人工智能和认知科学尤为重要，在机 器学习、知识获取、决策分析、数据库的知识发现、专家系统、决策支持系统、模式识 别、模糊控制等各个方面的应用，粗糙集理论都为之提供了一种有效的数学方法。 粗糙集理论及其广泛应用正越来越受到重视，并且在实际中也取得了许多可喜的成 果。特别地，粗糙集方法在医学、药学、银行、商业、金融、市场研究、工程设计、气 象学、振动分析、开关函数、冲突分析、图像处理、声音识别、并发系统分析、决策分 析、字符识别及其它领域都有重要的应用。 自粗糙集理论提出以来，大致从两个方面研究粗糙集理论及其应用。一方面是对粗 糙集的理论研究，发表了粗糙集代数、粗糙集拓扑及其性质、粗糙逻辑及处理近似推理 的逻辑工具等论文1 2 , a l ；在这些论文中充分论述了粗糙集与模糊集、证据理论与粗糙集理 论之间的联系，它们也建立了粗糙集与概率逻辑、粗糙集与模态逻辑等的统一框架。另 方面，粗糙集理论的研究者们很重视它的逻辑研究，发表了一系列的粗糙逻辑方面的 论文i “l 。另外，在粗糙集方法的函数研究方面，近年来出现了不少粗糙数及粗糙隶属 函数的研究，发表了一系列关于实数粗糙离散化和实函数粗糙离散化方面的论文1 7 - 1 0 1 。 大连交通人学t 学硕+ 学位论文 粗糙集的主要思想：在保持信息系统分类能力不变的前提下，通过知识约简，导出 问题的决策或分类规则。在研究粗糙集理论及其属性约简算法的过程中，不仅需要对各 种约简算法的有效性进行验证，而且需要对算法的效率进行比较，最终将其应用于各种 实际的数据挖掘环境中。目前国际上已经研制出一些比较成熟的粗糙集工具软件，其中 具有代表性的有r o u g he n o u g h ，r o s e ，r o s e t t a ，k d d r 系统等l l l l 。r o u g he n o u g h 是由 挪威t r o l ld a t ai n c 开发的一个基于粗糙集理论的数据挖掘工具系统，支持多数p c 数据 库和电子数据表格。r o s e 系统是由波兰p o z n a n 工业大学计算科学研究所智能决策支持 系统实验室开发的一个模块化的软件系统，它实现了粗糙集理论的基本理论和规则获取 技术。r o s e t t a 是由挪威科技大学计算机与信息科学习和波兰华沙大学数学研究所合作开 发的一个基于粗糙集理论框架的表格数据分析工具包，它包括了计算属性核和图形用户 界面。 纵观上述所有粗糙集属性约简系统，我们可以找出它们的共同点： 算法大多是基于主存的； 算法基本上都是采用结构化的方法； 算法实现主要是对关系数据库或格式化的文本文件进行约简； 数据和算法模型不统一。 这在一定程度上限制了科研成果的共享与利用，导致了很多软件实用性不高，归结 起来主要有以下几点不足： 1 ) 模型结构性不强。传统的实现方法中实例和属性之间不存在结构上的依赖关系， 例如具体抽象关系、整体部分关系。 2 ) 软件复用率低、可扩充性差。大部分软件模块很难集成到其他数据挖掘系统中。 3 ) 算法执行效率低。频繁求解不可分辨关系是导致系统效率的降低的主要因素之 o 4 ) 模型难以共享。不同的属性约简算法需要建立不同的数据模型，然而模型之间 很难实现共享。 为了能更好地解决上述的问题，本文首先针对3 ) 的问题，利用数据库技术处理大数 据集问题的优越性，提出了一种基于存储过程( s t o r e dp r o c e d u r e ) 的属性约简算法。然后 针对1 ) 的问题，用面向对象理论分析粗糙集的研究对象，设计了一种用于属性约简的对 象模型。最后将面向对象理论和粗糙集属性约简方法相结合，在传统的粗糙集理论的基 础上引入面向对象数据库，提出了基于面向对象数据库的粗糙集模型，用于解决2 ) 和 4 ) 的问题。并通过开发基于面向对象数据库的粗糙集模型的知识约简系统，验证上述解 决方案的正确性和优越性。 2 绪论 本文的结构如下： 第一章介绍粗糙理论基础。着重讨论了知识的基本概念、粗糙集、约简和知识库 中的依赖、知识的表示和决策表的约简。 第二章一种基于存储过程的属性约简算法。针对属性约简算法效率低下的问题， 利用数据库技术处理大数据集问题的优越性，提出了一种基于存储过程的属性约简算 法，并通过实现证明算法的有效性。 第三章设计粗糙集的研究对象的对象模型。用面向对象理论分析粗糙集的研究对 象，设计了一种用于属性约简的对象模型，对于实现数据模型共享提供了理论基础。 第四章面向对象数据库理论。本章从关系教据库中存在的问题出发，主要讨论了 面向对象教据库的特点和实现方法，并简单介绍了一个面向对象数据库d b 4 0 。 第五章基于面向对象数据库的粗糙集模型。介绍如何在在传统的粗糙集理论的基 础上引入面向对象数据库，提出基于面向对象数据库的粗糙集模型。 第六章基于面向对象数据库的粗糙集模型的属性约简系统。依次论述了该系统的 流程、数据集、对象提取和属性约简，并通过实例分析系统的有效性。 大连交通火学t 学硕+ 学位论文 第一章粗糙集理论 粗糙集1 2 l 以不可分辨关系为基础，给出知识表达系统这一模型，利用精确的上、下 近似集逼近不精确对象，赋予知识清晰的数学意义，从而提供了用数理逻辑方法来表达、 约简、分析、推理不精确知识的新思路。 1 1 知识的定义1 1 2 l 知识理论的各个方面研究得到了逻辑学、信息工程、系统工程和人工智能工作者的 广泛重视。现己有许多理解、表述和处理知识的方法。由于当涉及到不同领域时知识具 有不同定义，与a i 相比，粗糙集理论中关于知识的理解可能更接近于认识科学。 粗糙集理论认为知识是蕴藏在人类的分类能力之中的，知识以关于对象的分类能力 为基础。这里对象是指感兴趣的所有东西，如事物、状态、抽象概念和过程等，称之为 论域u 。因此，粗糙集理论中，知识被理解成关于论域的一组划分模式。论域可以按照 不同的属性分成不同的类别，具有相同特征的知识构成基本集，其元素具有不可分辨关 系，基本集是构成知识的模块，使知识具有粒状结构与层次性。 通常我们不处理一个单独的分类而是处理论域上的一些分类族。一个论域上的分类 族，定义为一个论域上的知识库。 定义1 1 知识库的公式化定义为：k = ( u ，尺) 其中k 为知识库，u 为全体对象的集 合称为论域，r 为论域u 上的等价关系( 等价关系与分类的概念等同) ，它是一种属性或 多种属性的集合。可以根据不同的尺对u 进行不同形式的分类。知识库也被称作近似空 间。 这样，知识库表达了一个或一组智能机构的各种基本分类方式( 例如，按照颜色、 温度等等划分) ，它构成了该机构所需的定义与环境或其本身的关系的基础构件。 1 2 知识表达系统一决策表1 1 2 l 在智能系统中，常会碰到要处理的对象可能是用语言方式表达，也可能是用数据表 达；可能是精确的数据，也可能是不精确的数据，会有一些相互矛盾的信息。这些需要 通过人们智能处理的数据，它们叫做智能数据。 为了处理智能数据，我们需要知识的符号表达。知识表达系统的基本成分是研究对 象的集合，这些对象的知识是通过指定对象的基本特征( 属性) 和它们的特征值( 属性值) 来描述的，知识库和知识表达系统之间具有一一对应的关系。 定义1 2 一个知识表达系统定义为： 4 第一章韦h 糙集理论 d s = ，u 为非空有限集合，称为全域，全域u 的元素被称为对象或者 实例。彳称为属性集合。v 是属性值的集合，v 上属性a 的值域，即v = n 圪，f 指定 口e 月 u 中每一个对象的属性值，f ：u 彳专y 称为信息函数，使得对每一口a ，x u 有 f ( x ，a ) 圪。 为了提供知识的易于处理与操作的过程，就需要适当的知识表示方法。这样定义的 知识表达系统可以很方便的使用表格表达来实现。知识的表格表达可以看成是一种特殊 的形式语言，用符号表达等价关系。这样的数据表称作知识表达系统，有时也称为信息 系统。表面上看信息系统类似于关系数据库模型的表达方式，实际上这两个模型有一个 根本的区别，关系数据库模型对表中所有存储信息的意义不感兴趣，它强调的是有效数 据的结构和操作，因此包含信息的对象没有在数据表中表示出来，这一点与我们这里介 绍的方法相反，在知识表达系统中，所有的对象都明显地表达出来，并且属性值都与对 象的特征和性质的显式意义相联系。另外，在我们的模型中，强调的不是数据的结构和 操作，而是在于分析数据中存在的实际依赖性和数据简化，它更接近于统计数据模型。 粗糙集理论在其上定义了约简和核等概念，这样知识就可用数据来替代，知识处理可由 数据操纵来实现。 、 在知识表达系统数据表中，列表示属性，行表示对象，并且每行表示该对象的一条 信息，数据表可以通过观察、测量得到。在知识表达系统中，一个属性对应一个等价关 系，一个表可以看作是定义的一族等价关系。 决策表是一种重要的知识表达系统，它指定当满足某些条件时，决策( 行为) 应当怎 样进行，多数决策问题都可以用决策表形式来表达，因此在决策应用中决策表起着重要 的作用。 定义1 3 决策表可以用知识表达系统来定义： 令d s = 为一决策表知识表达系统。a = ( c ud ) ，u 为非空有限集合，称 为全域，c 为条件属性集合，d 是决策属性，a 称为属性集合，且c n d = o 。具有不 同条件属性和决策属性的知识表达系统被称作决策表。一般地，决策属性只有一个，既 d s = 。 例如表1 1 所示的决策表中，论域u = x i ，x 2 ，x 3 ，x 4 ，蚝) ，条件属性集c = 口，b ，c ) ，决 策属性d = d ) ，其中v o = 1 ，2 ) ，圪= o ，1 ，2 ) ，k = o ，2 ) ，巧= l ，2 ，3 ) 。厂( 五，a ) = 1 为一个信 息函数值。 大连交通人学r 学硕十学位论文 表1 1 一个决策表 t a b l e1 1ad e c i s i o nt a b l e u 口 b c d 五 lo2l 而 2 l0 2 毛 2l23 而 1221 屯 l203 粗糙集中对知识系统的各种定义方式为粗糙集在实际应用领域中的应用提供了方 便。本论文所有算法都是建立在粗糙集知识的定义、表示与处理的基础之上的。 1 3 粗糙集理论中的不可分辨关系1 1 2 l 在粗糙集理论中，我们通常用等价关系代替分类。 当尺为u 上的划分r = 五，而90 9 矗 表达的等价关系，( u ，r ) 称为近似空间。 定义1 4 不可分辨关系： 设信息系统s = ，在任意子集b a ，如果存在 ( x ，y ) if ( x ，a ) = f ( y ，a ) ，x y ，口脚，称为不可分辨关系，记作i n d ( b ) 。 不可分辨关系的概念是粗糙集理论的基石。 不可分辨关系是一种等价关系，它把u 划分为有限个集合，称为等价类，在每个集 合中，对象间是不可分辨的。u i n d ( b ) 是指全域u 根据等价关系b 划分的所有等价类 的集合，通常我们将u i n d ( b ) 记为u b 。对于元素x u ，它的b 等价类定义为： 【x 】8 = yi ( x ，y ) i n d ( b ) i n d ( b ) 的等价类称为知识b 的等价类，或称为知识b 的基本概念或基本范畴。如果 9 c b ，i n d ( q ) 的等价类称为知识b 的初等范畴，因此，根据属性q 定义的不可分辨 的等价关系类就是b 初等集合。初等范畴就是所有具有特定属性的物体构成的子集，而 基本范畴由一些初等范畴构成。 实际上b 一一基本范畴是论域的基本特性，该论域可称为拥有知识b ，换句话说就 是：它们是知识的基本模块，或者说是拥有知识b 的论域的基本特性。 6 第一章粗糙集理论 1 4 粗糙集的下近似、上近似、边界区和粗糙隶属函数1 1 3 l 给定知识库k = ( u ，r ) 对于每个子集x u 和一个等价关系r i n d ( k ) ，当x 能表 达成某些r 基本范畴的并时，称x 是r 可定义的，否则称x 为尺不可定义的。r 可定 义集也称作r 精确集，而r 不可定义集则被称为j i c 粗糙集。 粗糙集理论利用集合的上、下近似概念描述不确定性，即利用不可分辨关系导出论 域划分来描述论域的新的子集。 定义1 5 设s 为信息系统，x 为u 的非空子集，召a 且b a 。集合x 的b 下近 似墨( x ) 和b 上近似百( x ) 分别定义如下： 堡( x ) = ( 薯i 薯】b x )( 1 1 ) b ( x ) = ( 薯i 薯】占n x a ) ( 1 2 ) b ( x ) 是由那些根据己有知识判断肯定属于x 的对象所组成的最大的集合，即所有 包含于x 的z 并，也称为x 的正区( p o s i t i v er e g i o n ) ，记作p o s b ( x ) 。由根据己有知识判 断肯定不属于x 的对象组成的集合称为x 的负区( n e g a t i v er e g i o n ) 。记作n e g b ( x ) 。 b 一( x ) 是由所有与x 交非空的等价类的并集，是那些可能属于x 的对象组成的最小 集合。集合b n b ( x ) = 百( x ) 一旦( x ) 称为x 的b 的边界，它是根据知识b ，u 中既不能 肯定划入x 也不能肯定划入非x 的元素的集合，如果b n b ( x ) 是空集，则称x 关于b 是 清晰的( c r i s p ) ；反之如果删占( x ) 不是空集，则称集合x 是关于b 的粗糙集( r o u g hs e t ) 。 集合的不确定性是由于边界域的存在而引起的，集合的边界域越大其精确性越低，为更 准确地表达这一点，我们引入了精度的概念。对于由等价关系b 定义的近似精度为： 榔) = 舄勰 ( 1 3 ) 式中，c a r d ( c a r d i n a l i t y ) 表示集合的元素的数目，称为集合的基数或势，c a r d ( b ( x ) ) 也 可以表达为i 垦( x ) l 。显然0 d b ( x ) 1 ，如果以( x ) = l ，则称集合x 相对于召是清晰的； 以( x ) l ，则称集合x 相对于b 是粗糙的。以( x ) 可以认为是在等价关系b 下逼近集 合x 的精度。 因此，在粗糙集中不精确的数值不是事先假定的，而是通过表达知识不确定性的概 念近似计算得到的，他们反映出对象分类能力的结果。 举例说明粗糙集的概念。论域u 及等价关系r = 足，r 2 ) ，采用如下定义： u = 五，x 2 ，毛，x 4 ，x 7 ，黾，x 9 ，五o ) ， u r i = “，屯，屯， ， 黾，魄，而，x 8 ，x 9 ，x l o ) ) ， 7 大连交通人学i ：学硕十学位论文 u 是= ，x 2 ，屯， ，x 6 ，x 7 ，x s ，x 9 ，而o ) ) ， u r = 西，x 2 ，而) ， 毛) ， 黾，x 6 ，x 7 ，x s ，x 9 ，o ) ) ， 则关于集合x = 而，x 2 ，x 3 ，x 4 ，x 5 ) 的逼近为 p o s ( x ) = ，而，而，毛) ， n e g ( x ) = 黾，x 9 ，西o ) ， b n ( x ) = x 5 ，x 6 ，x 7 ， 而，x 2 ，黾，- ) 集合x 的正域，因为 一，x 2 ，黾，心) 肯定属于x ；j ( ，x 9 ，x 。o ) 肯定不属于 x ，因此为x 的负区； 黾，讫，而) 是否属于x 在等价关系尺下无法确定，构成了x 的边 界区。 1 5 粗糙集理论中的约简、核1 2 j 知识约简在信息系统分析与知识发现等领域具有重要的应用意义。知识之间的依赖 性决定知识是否可以进行约简，根据依赖性所定义的知识的重要性往往是知识约简的重 要启发式信息。 1 5 1 约简和核 定义1 6 设r 是近似空间( u ，r ) 中等价关系的一个族集，关系p r 。若 i n d ( r ) = i n d ( r 一 p ) ) ，则称关系p 在族集r 中是可缺的( d i s p e n s a b l e ) ，否则就是不可缺 的：若尺中每个关系尸都是不可缺的，则称r 是独立的( i n d e p e n d e n t ) ，否则是依赖的。 定义1 7 设q p 是独立的，并且i n d ( q ) = i n d ( p ) ，则称9 是尸的一个约简 ( r e d u c t i o n ) ，记为r e d ( p ) 。在p 中，所有不可缺的关系集合称为p 的核( c o r e ) ，表示为 c o r e ( p ) 。其中：c o r e ( p ) = n r e d ( p ) 。 1 5 2 相对约简和相对核 在应用中，一个分类相对于另一个分类的关系十分重要，因此介绍知识的相对简化 和相对核的概念。 定义1 8 设q 和尸是u 上的一个等价关系，q 的p 正区域( p - p o s i t i v er e g i o no fp ) ， 记作p o s p ( q ) ，定义为： p o s e ( q ) = u ( x ) ( 1 4 ) x u | q q 的p 正区域反映了使用分类u p 能够正确地分类u q 中的的等价类之中的所有 对象。 8 第一章粗糙集理论 定义1 9 设q 和p 是u 的一个等价关系，r p ，若： p o s e ( q ) = p o s p _ i r ( q ) ( 1 5 ) 则称r 在尸中相对于q 是多余的，否则是不可少的。如果每一个关系r 都是不可少 的，则p 相对对于q 是独立的。 定义1 1 0 设s 尸，称s 是p 的q 约简，当且仅当s 是p 的q 独立的，且 p o s e ( q ) = p o s s ( q ) ；p 的q 核等于p 的所有q 的约简的交集，即 e o s o ( e ) = f l p o s q ( e ) ( 1 6 ) 1 6 决策表约简 粗糙集理论在人工智能中的应用可以分为两大类：有决策的分析及无决策的分析。 有决策的分析主要包括：监督学习与决策分析：无决策的分析主要是：数据压缩、化简、 聚类、模式发现与机器发现等。在所有决策分析的应用中，都是利用粗糙集理论的属性 约简、值约简及核等概念，对被决策的数据进行约简和寻找对于决策最有用的信息，而 被决策的数据往往映射为二维决策表。因此决策表的简化是一个重要的研究课题。 决策表的简化就是化简决策表中的条件属性，化简后的决策表具有与化简前的决策 表相同的功能，但是化简后的决策表具有更少的条件属性。因此，决策表的简化在工程 应用中相当重要。同样的决策可以基于更少量的条件，使我们通过一些简单的手段就能 获得同样的结果。 无决策系统指的是属性集只有条件属性而没有决策属性的系统。有决策系统与无决 策系统的区别在于：有决策系统的属性集可分为两部分，一部分是条件属性，另一部分 是决策属性；而无决策系统则没有决策属性。对于简化的目的，二者也有明显的不同：无 决策系统的简化是为了得到最小属性集和核集：有决策系统的简化则是为了得到最简的 决策规则。无决策系统简化的理论依据是可分辨性准则；有决策系统的简化依据是协调性 原则。有决策系统的简化只是针对条件属性集，而决策属性集是不需简化的。本文主要 是对有决策系统的约简算法研究。 定义1 1 l ( 协调性定义) 对于决策系统中的两个对象，如果满足如下两个条件之一： 1 ) 其条件属性的取值至少有一个属性不同。 2 ) 有相同的条件属性取值时，其决策属性的取值是相同的。则称这两个对象是 协调的；否则称为不协调的。如果系统中任何一对对象都是协调的，则称该 系统是协调的。 9 人连交通大学t 学硕士学仲论文 对一决策表知识表达系统( 信息决策系统) d s = 。a = c u d ) ，u 为 非空有限集合，称为全域，c 为条件属性集合，d 是决策属性，下面是决策表属性的两 个性质： 命题1 当且仅当cjd ( 即c 依赖d ) ，决策表d s = 是相容的( 协调的) 。 命题2 对每一个决策表d s = 都可以唯一地分解成为两个决策表 d s , = 和鹎= ，其中d s , 为完全协调( 相容) ，d s z 为完 全不协调。 决策表的一般简化步骤如下： 1 列出决策对象并确定条件属性集和决策属性集。 2 属性值的离散化。 3 根据数据列出决策表。 4 消去重复的行。 5 判断决策表是否协调，如果协调转到第6 步，否则删除不协调规则。 6 进行条件属性的简化，即从决策表中消去某些列。 7 消去属性的冗余值。 8 消去冗余的决策规则，得到最简决策算法。 注意到，与知识表达系统的一般表示相比，这罩的行不表示对任何实际对象的描述。 因此重复行表示的是同样的决策，所以它可以消去。从数学的观点看，消去属性和消去 属性值是一回事。 化简后的决策表是一个“不完全”的决策表，它仅包含那些在决策时所必需的条件 属性值。 本章小结 粗糙集理论从集合论的观点出发，以观侧数据进行分类的能力为基础，运用求核和 求约简的方法，仅仅使用数据本身的内部知识，自动获取该问题的内在规律。它己经在 机器学习、决策制定、模型建立、故障诊断等方面得到较为成功的应用。 本章作为全文的基础，主要概述了粗糙集的基本理论，包括：粗糙集理论核心内容的 近似集的有关概念；粗糙集理论中的知识表达形式一决策表；粗糙集理论中的约简和核 有关概念：决策表的约简思想等。 l o 第二章一种基于存储过程( s t o r e dp r o c e d u r e ) 的属性约简算法 第二章一种基于存储过程( s t o r e dp r o c e d u r e ) 的属性约简算法 当处理大数据集时，基于主存的粗糙集属性约简算法的效率将会显著下降。针对这 一问题，本章利用数据库技术处理大数据集问题的优越性，提出了一种基于存储过程的 属性约简算法。首先，我们阐述了该算法的可行性；然后，我们利用t s q l 实现了该 算法；最后，我们给出了应用存储过程的实例。实验结果表明，对于处理大数据集问题， 该算法的效率要比基于主存的属性约简算法的效率高，而且该算法容易实现，具有一定 的实用价值。 2 1 问题提出 属性约简在分类学习及分类数据挖掘中具有重要的作用。所谓属性约简是指在保证 信息系统分类或决策能力不变的条件下，删除条件属性中的冗余属性，从而减少数据挖 掘要处理的数据集，提高数据挖掘结果的简洁性。目前大多数的属性约简算法一个共同 特点就是要先利用s k o w r o n 提出的区分矩阵i i 求出属性核心，因此如何高效地求取属性 核心及属性约简吸引了许多研究者的兴趣1 1 7 - 2 a j 。然而通过区分矩阵计算属性核心的时间 和空间复杂性都较大，且不能利用数据库查询语言的优势来实现，因此目前的属性约简 算法通常是基于主存的，然而这种算法存在以下几个主要问题：编程的工作量较大；当 所处理的数据集较大时，算法的时空代价将大大增加，制约了属性约简算法在实际中的 应用。因此，针对大数据集的实用、高效的属性约简算法仍是目前研究的一个主要难题。 针对以上问题，文献1 1 6 j 提出了一个基于数据库技术的粗糙集模型，把传统的粗糙集 方法和数据库技术结合起来，使数据库的关系运算取代粗糙集的集合操作，但在实际操 作上是相当困难的。文献i r 丌也已证明从大数据集的数据库中提取有用规则优于普通文 件。但是用属性约简算法从大规模数据中挖掘有价值的知识信息，访问数据库的操作必 不可少，如果用嵌入式数据库查询语言s q l l 2 i l 来获取数据库中的数据并在客户端执行， 最后结果再传送回服务器，这种方法客观上存在数据传输量大、运算效率低，可靠性差 等弊端；另外，当出现大批量的s q l 语句时，将造成网络延迟或网络堵塞i 捌，这样将 增加约简算法的运行时间。 为了有效的减少算法执行时间，本章利用数据库技术处理大数据集问题的优越性， 提出了一种基于存储过程1 2 2 1 ( s t o r e dp r o c e d u r e ) 的属性约简算法。利用存储过程实现属性 约简算法，只需传送存储过程名和相应的各个参数( 如表名和决策属性) ，很大程度上 减少了通信负载，这样网络上的传输开销将减少，和传统方法相比较，该算法的运行速 度更快、效率更高。特别是在大规模数据集的情况下，该算法的运行效率明显得到提高。 大连交通大学工学硕十学位论文 本章将重点介绍如何使用存储过程来实现属性约简算法，并给出了应用存储过程的实 例。实验结果表明，该算法在处理大规模数据上比基于主存的属性约简算法更有效，另 外利用存储过程可以实现属性约简算法与属性约简软件的分离，用户可以不通过属性约 简软件来直接运行属性约简算法，而且该算法容易实现，因此，该算法特别适合于处理 大规模数据集的属性约简问题。 2 2 存储过程的优点 存储过程是一组为了完成特定功能的s q l 语句集，经编译和优化后存储在数据库 服务器中，用以被客户程序执行调用。用户通过指定存储过程的名字并给出参数( 如果 该存储过程带有参数) 来执行它。采用存储过程技术具有以下优点： 存储过程能实现较快的运行速度 如果某一操作包含大量的t r a n s a c t i o ns q l 代码，那么存储过程要比批处理的执行 速度快很多，因为存储过程是预编译的，其首次运行时，查询优化器对其进行分析优 化，给出最终被存在系统表中的执行计划。而批处理的t r a n s a c t i o ns q l 语句在每次运 行时都要进行编译和优化，因此速度相对要慢一些。 存储过程能减少网络流量 客户机上调用该存储过程时，只有执行存储过程的命令在内部网络上传送，当它们 到达数据库服务器时，运行存储过程，客户端在网络上只接收返回结果或状态信息，使 得客户机与服务器的通信量降至最小，减少了网络负荷，减少延迟，提高了运行效率。 存储过程的安全可靠机制 存储过程本身有很强的安全机制，只有具有相应的系统权限才能够调用相应的存储 过程，或者只访问存储过程而不能够访问其中设计的表或视图。在存储过程的代码中可 以包含对信息和数据的合法性检查、对业务规格要求的各种完整性检查等。 存储过程使服务用户满意 存储过程可以充分利用数据视点集中的原则，使用户把注意力集中在所关心的数据 上，简化了用户的数据查询操作；同时存储过程能够自动对复杂或敏感的事务进行处理， 以保证这些表的数据完整性，当然更满足用户的需要。 2 3 基于存储过程的属性约简算法描述 2 3 1 理论基础 如果决策信息系统满足v x ，y urc ( x ) = c ( y ) ，有d ( x ) = d ( y ) ，则此决策信息系统 为相容的。否则，该决策信息系统是不相容。 1 2 第：二章一种基丁存储过程( s t o r e dp r o c e d u r e ) 的属性约简劈法 定理l ：一个决策信息系统s = ( u ，c u d ，v ，f ) ，v x u ，有zgp o s c ( d ) 一v 挈 u ( h 肿( 口) 引】肋( d ) ) 。 证明设芗u 且纠m ( c ) i n d ( d ) 。可以推出m 肿( c ) 曼旦( 】肿( d ) p o & ( p ) ) ， z p d & ( d ) 。显然，这与前提条件矛盾，所以zgp o & p ) _