（计算机应用技术专业论文）变精度粗糙集模型特征研究.pdf

摘要 粗糙集理论作为智能信息处理新的研究热点，已广泛应用于众多 领域，但其自身尚存在一些局限，对噪声数据非常敏感，数据分析过 程中易丢失潜在有价值知识。针对标准粗糙集不足，将标准包含关系 扩展为多数包含关系的变精度粗糙集模型，分类过程允许一定程度噪 声数据存在，并对约简特征、约简归并、区问约简层次和属性核等方 面进行研究探讨，以发现数据间弱依赖关系，及更为泛化的数据关联 及决策规则。 深入分析变精度粗糙集模型约简特征，指出分析了约简过程存在 跳跃现象，分类质量、相对正域和决策类下近似随属性约简不再具有 单调递减特征，且打破了经典粗糙集模型中具有的等价性。针对三者 分别讨论了属性可约性，并分析了三者之间的联系。 由于包含度概念引入，变精度粗糙集模型约简归并情况比经典粗 糙集模型复杂。论文详细分析了约简过程等价类归并的各种情况，约 简归并考虑相对正域变化的同时，进一步探讨了包含度值动态变化， 为区间约简研究奠定基础。 详细讨论各种约简异常，结合变精度粗糙集模型特征，将特定包 含度值约简扩展为包含度区间约简，建立了三层区间约简体系，从分 类质量、相对正域和决策类下近似三个层次分别对约简进行区间刻 画，逐步消除了约简异常。提出的区间约简评价因子，对选择区间约 简有重要指导意义。 结合包含度区间特性提出区间核概念，完善了变精度粗糙集理论 体系。通过建立变精度粗糙集模型排序可辨识矩阵、定义并分析三种 区间特征集合，给出了求取区间核思想，并以此为基础构造了启发式 区间约简算法。 论文最后结合实践，采用u c i 数据集进行实验仿真，仿真结果进 一步阐明了相关理论成果。 关键词变精度粗糙集模型，区间约简层次，约简异常，区间核 第1 页 a b s t r a c t r o u g h s e t s t h e o r y i sah o t s p o tf o r d e a l i n g w i t h i n t e l l i g e n t i n f o r m a t i o nw h i c hh a sb e e nu s e di nm a n yd o m a i n ss u c c e s s f u l l y b u ti t h a ss o m el i m i t a t i o n s ，f o ri n s t a n c e ，i ti ss e n s i t i v ef o rd a t as e t sw h i c hh a v e n o i s ed a t a ，t h e r e f o r es o m ep o t e n t i a lu s e f u lk n o w l e d g ec a l ln o tb em i n e d i n o r d e rt oo v e r c o m et h e s el i m i t a t i o n s ，v a r i a b l ep r e c i s i o nr o u g hs e t s t h e o r ye x t e n d ss t a n d a r di n c l u s i o nr e l a t i o nt om a j o r i t yi n c l u s i o nr e l a t i o n b a s e do nt h i se x t e n d e dn o t i o n ，s o m ed e g r e eo fm i s c l a s s i f i c a t i o ni nt h e l a r g e l yc o r r e c tc l a s s i f i c a t i o ni sa l l o w e d f e a t u r e so fr e d u c t ，r e d u c t i o n m e r g e n c e ，h i b e r a r c h yo fi n t e r v a lr e d u c ta n da t t r i b u t e c o r ea r ea l s o d i s c u s s e di no r d e rt of i n dw e a kd e p e n d e n c er e l a t i o n s h i p ，m o r eg e n e r a l a s s o c i a t i o na n dd e c i s i o nr u l e s i nc l a s s i c a lr o u g hs e t s m o d e l ，q u a l i t yo fc l a s s i f i c a t i o n ，r e l a t i v e p o s i t i v er e g i 0 1 1 a n dl o w e ra p p r o x i m a t i o na r ed e c r e a s i n g a l o n gw i t h a t t r i b u t e s r e d u c i n g i n v a r i a b l e p r e c i s i o nr o u g hs e t s ，m o n o t o n i c d e c r e a s i n gp r i n c i p l e so ft h e ma r eb r o k e nb e c a u s eo fb o u n c ep h e n o m e n a , a n dt h e r ei sn oe q u i v a l e n c ea m o n gt h e m a t t r i b u t er e d u c t i o ni sd i s c u s s e d f r o m q u a l i t y o fc l a s s i f i c a t i o n ，r e l a t i v e p o s i t i v er e 西o na n dl o w e r a p p r o x i m a t i o nr e s p e c t i v e l y , a n dt h e i rr e l a t i o n sa r ea l s oa n a l y z e d r e d u c t i o n m e r g e n c e b e c o m e sm o r e c o m p l i c a t e d i nv a r i a b l e p r e c i s i o nr o u g hs e t sm o d e lb e c a u s eo fi n c l u s i o nd e g r e e a l lt y p e so fc l a s s m e r g e n c ea r ed i s c u s s e di nt h i st h e s i s t h ed y n a m i cc h a n g e so fi n c l u s i o n d e g r e e s h o u l db e a n a l y z e dw h e np o s i t i v er c g i o n i s c o n s i d e r e d , s o f o u n d a t i o no f i n t e r v a lr e d u c ti se s t a b l i s h e d r e d u c ta n o m a l i e sa r ed i s c u s s e di nd e t a i l t h ed e f l n i t i o no fr e d u c t e x t e n d sf r o ma s p e c i f i cv a l u et oar a n g eo fi n c l u s i o nd e g r e e ，c o m b i n i n g w i t l lt h ec h a r a c t e r i s t i c so fv a r i a b l ep r e c i s i o nr o u g hs e t sm o d e l r e d u c t s a r ed e f m e da n ds t u d i e df r o md i f f e r e n tl e v e l s ，v i z t h eq u a l i 何o f c l a s s i f i c a t i o n , r e l a t i v ep o s i t i v er e g i o na n dt h el o w e ra p p r o x i m a t i o no f d e c i s i o nc l a s s e s t h e r ea r ed i f f e r e n ta n o m a l i e so nd i f f e r e n tl e v e l s r e d u c t a n o m a l i e sa r ee l i m i n a t e d g r a d u a l l y w h e nd e f i n i t i o nr e s t r i c t i o n sa r e e n h a n c e d al ( i 1 1 do fm e a s u r ef u ri n t e r v a lr e d u c ti sa l s o g i v e n f o r e v a l u a t i n ga n ds e l e c t i n gi n t e r v a lr e d u c t 1 h ec o n c e p t i o no fi n t e r v a lc o r ei sa l s op u tf o r w a r di nt h i st h e s i s ， 第页 c o m b i n i n gw i t hi n t e r v a lc h a r a c t e r i s t i c ，s ov a r i a b l ep r e c i s i o nr o u g hs e t s t h e o r yi sd e v e l o p e df u r t h e r s o r td i s c e r n i b i l i t ym a t r i xi sc o n s t r u c t e da n d t h r e et y p e so fi n t e r v a ls e t sa r ed e f i n e da n da n a l y z e d ，t h u si n t e r v a lc o r e c a nb eo b t a i n e d h e u r i s t i ca l g o r i t h mf u ri n t e r v a lr e d u c tc a na l s ob e a c h i e v e d f i n a l l y , t h et h e s i su s e su c id a t a s e tf u re x p e r i m e n t ，t h er e s u l t so f e x p e r i m e n ti l l u s t r a t ec o r r e l a t i v et h e o r yf u r t h e r k e yw o r d sv a r i a b l ep r e c i s i o nr o u g hs e t s ，i n t e r v a lr e d u c th i b e r a r c h y , r e d u c ta n o m a l y , i n t e r v a lc o r e 第1 i i 页 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了论文中特别加以标注 和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究 成果，也不包含为获得中南大学或其他单位的学位或证书而使用 过的材料。与我共同工作的同志对本研究所作的贡献均已在在论 文中作了明确的说明。 作者签名：坠日期：型年月丝日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：坠导师签名：立生丛耸日期：互丝互年月笪日 硕士学位论文 第一章绪论 1 1 课题研究背景 第一章绪论 随着大规模数据库的广泛使用和i n t e m e t 的迅猛发展，庞大的信息量已渗透 到社会生活和生产的各个领域。快速增长的海量数据收集并存放在大型数据库或 w e b 页面中，没有强有力的分析工具，理解它们已经远远超出了人们的能力范 围。面对丰富数据但贫乏知识的境况，分析这些数据，发现隐含在这些数据中有 用的信息，并将信息转化为知识愈显重要。目前在分析数据方面已经提出了用于 数据挖掘的简单统计分析技术，但实用的智能数据分析技术目前仍不成熟1 1 1 。因 此，寻求一种快速、高效、智能的数据分析方法一直是数据挖掘研究者重点目标 之一。如何快速、准确的从海量数据集中发现知识、提取潜在有用信息，已成为 知识发现、数据挖掘的一个热点研究领域【2 3 - 4 1 。 粗糙集理论1 5 ，6 。7 】是由波兰数学家p a w l a kz 为开发自动规则生成系统及研 究软计算问题于1 9 8 2 年提出，它是一种新的处理不精确、不确定和不完备数据 的分析理论与方法，直到2 0 世纪8 0 年代末才逐渐引起各国学者的重视。与其他 处理不精确和不确定问题理论最显著的区别是它无需提供问题所需处理数据集 合之外的任何先验信息( 如概率论中的概率分布，模糊理论中的隶属函数或隶属 度等) ，所以对问题的描述和处理比较客观。相对其他软计算工具，粗糙集理论 表现出了强大的优势，其研究逐渐趋热，目前已广泛应用于模式识别、机器学习、 知识获取、人工智能、经济预测等众多领域【s 9 1o 1 1 l 。 实践应用及开发粗糙集模型数据挖掘软件表明经典粗糙集模型存在一些局 限【1 乞1 3 】： ( 1 ) 分类必须完全正确或确定。经典粗糙集模型中，分类建立在经典集合 论观点上，不允许分类具有不确定程度或错误。实际获得的数据，由于随机原因 或经统计得到，数据集中往往存在噪声或某种程度的不完整性。分类过程中，不 确定程度可能导致对所分析数据更深一步的理解和更好的利用； ( 2 ) 粗糙集理论基于一个前提：所考虑数据对象的论域已知并且所有从这 个模型中得到的规则仅仅适合于该模型中的对象。实际应用中需要将从实例对象 较小模型中得到的规则进行泛化，使它能够适应更大的数据集合，即能够很好的 匹配新对象。 针对经典粗糙集模型容噪能力差、规则泛化程度不高的缺陷，z i a r k ow 教授 提出变精度粗糙集模型思想【。变精度粗糙集模型通过引入分类错误率口，将集 合论中标准包含关系扩展为多数包含关系，在分类过程中允许一定程度的噪声数 硕士学位论文第一章绪论 据存在。实际应用中变精度粗糙集模型可以解决数据问弱依赖关系，从数据集中 发现更为泛化的数据关联及决策规则。众多学者对其理论作了进一步研究，其在 实际应用中也越来越广泛。 1 2 国内外研究综述 自1 8 世纪德国数学家l e i b n i zgw 倡导用通用符号语言和逻辑演算改革形 式逻辑学，到1 9 世纪德国数学家f r e g eg 等人建立命题演算和一阶谓词演算系 统，形成了数理逻辑学体系【1 4 】。这种经典逻辑学建立在二值逻辑基础上，只有 真、假之分。现实世界许多概念不能简单用二值逻辑加以描述，存在模糊现象。 z a d e hl a 于1 9 6 5 年提出模糊集理论，运用模糊集合可以描述相应的模糊概 念、刻画“亦此亦彼”现象。由于模糊集理论在处理复杂系统方面的简捷与有力， 极大地弥补了经典数学与统计数学的不足，受到广泛重视并得到大量应用，成为 软计算重要方法。但遗憾的是模糊集是不可计算的，即没有给出严格的数学公式 描述这一模糊概念，需要先前给出相应的模糊隶属度或隶属函数，具有很强主观 性。 p a w l a kz 于1 9 8 2 年提出粗糙集理论【5 1 ，为处理不精确、不确定和不完备数 据提供了新的数学理论。粗糙集理论模型建立在集合论基础上，通过分类求取正 域、导出分类规则。它将不确定个体归宿于边界区域，而该边界区域通过一对上、 下近似集合可以进行严格的数学描述。 自粗糙集理论提出以来，它已成为智能信息处理新的研究热点。1 9 9 1 年 p a w l a k z 教授的第一本关于粗糙集专著问世和1 9 9 2 年s l o w i n s k i 主编的关于粗 糙集应用与相关方法比较研究论文集的出版极大地推动了粗糙集理论的发展。 1 9 9 2 年第一届关于粗糙集理论国际学术会议在波兰召开，着重讨论了集合近似 定义的基本思想及应用。1 9 9 3 年在加拿大召开第二届国际粗糙集理论与知识发 现研讨会，推动了国际上对粗糙集理论与应用的研究。1 9 9 5 年a c m c o m m u n i c a t i o n 将其列为新浮现的计算机科学研究课题。1 9 9 6 年在日本东京召开 第五届国际粗糙集研讨会，推动了亚洲地区对粗糙集理论与应用的研究。自1 9 9 2 年以来，每年都召开以粗糙集理论为主题的国际学术研讨会，许多重要国际学术 会议也将该理论列为主要研究内容之一，这些都推进了粗糙集理论的快速发展与 完善。 国内众多学者自二十世纪末对粗糙集理论及其应用进行了广泛的研究与探 讨，并于2 0 0 1 年5 月在重庆举行了第一届中国粗糙集理论与软计算学术研讨会， 此后每年举办一次，期间发表了大量高水平学术论文，推动了国内粗糙集研究领 域的发展。 2 硕士学位论文第一章绪论 知识约简是租糙集理论的核心问题之一，也是应用租糙集理论的基础。然而， w o n gsk m 和z i a r k ow 已证明计算最小约简是n p - h a r d 问题【1 5 1 。实际问题中采 集到的数据往往存在各种误差，即经典粗糙集理论在实际应用中会面l 临噪声数 据，如果考虑噪声数据，则得到的约简不够理想或者降低了预测新对象的能力， 从而挖掘过程中可能丢失隐含在数据中潜在有价值的知识。 基本的约简算法研究广泛基于可辨识矩阵求出所有约简，但算法效率低，不 适合大数据集。h u 于1 9 9 5 年提出约简的启发式算澍1 6 】，利用属性重要度作为启 发函数，计算一个最好的或用户指定的最小约简。s t a r z y k 等人提出了强等价概 念【l ”，用于快速简化可辨识函数，可处理较大数据集。文献 1 8 1 利用可辨识矩阵 的统计信息可得到用户指定的最佳约简。这些约筒算法拥有较高的效率，但是都 针对一致性决策信息系统，未考虑噪声数据的影响。 为了增强经典粗糙集理论对噪声数据的适应能力，z i a r k ow 于1 9 9 3 年提出 变精度粗糙集理论模型【1 2 1 ，将经典集合论中标准包含关系扩展为多数包含关系， 符合现实数据要求，也反映了人们的思维习惯。变精度粗糙集模型继承了经典粗 糙集模型的所有数学特性，并对众多概念进行了扩展，经典粗糙集模型是变精度 粗糙集模型的一种特殊化。本文基于变精度粗糙集模型主要对约简特征、约简模 型和属性核等方面进行研究与探讨。 ( 1 ) 约简特征。变精度粗糙集模型由于对噪声数据的适应优势，己在众多 领域取得应用。a na 等人在文献【1 9 】中利用交精度粗糙集模型实现了水资源预 测，m a l c o l mb e ) n o n 等人在文献 2 0 1 中利用变精度粗糙集模型成功实现了对英国 公司状况预测，t e t s u y am u r a i 等人在文献 2 1 1 中基于变精度粗糙集模型实现了单 调推理，这些应用都是在寻求较优的特定声值，有时甚至需要主观给定声值，不 同的口值可能引起分析结果的巨大差异 文献 2 2 1 通过分析变精度粗糙集模型卢特性，提出声区间概念，给出分类质 量和卢区间关系描述，将卢取值从点扩展到区间范围，更好的符合了模型统计特 性，为进一步分析模型特征打下基础。 约简实质上是一个泛化的过程，随着属性约简将伴随条件等价类归并。文献 【2 3 详细讨论了经典粗糙集模型下条件等价类归并的各种情况及其对正域的影 响，同时指出归并分析反映了约简过程中一个属性能否被约简的根本原因。变精 度粗糙集模型由于包含度声引入，形成了分类质量和声区间的特定关系。约简过 程中，条件等价类的归并将引起包含度口值的动态变化，从而形成新的分类质量 和口区间关系，条件等价类的归属将被考虑，若原来的归属格局被打破，势必对 原信息系统分类能力产生影响，归并情况变的异常复杂。 文献 2 3 1 进一步指出经典粗糙集模型下，一个属性在约简某中间过程不可 3 硬士学位论文第一章绪论 约，则其在整个约简过程中都不可约，可以获得稳定的约简，即约简结果与约简 属性的顺序无关。文献【2 4 】分析了随着约简过程动态变化，变精度粗糙集模型约 简过程会出现跳跃现象，不能获得稳定的约简过程，一个属性是否可约不能由一 步中间约简过程判定，相对经典粗糙集模型其约简特征已发生新的变化。 ( 2 ) 约简模型。国内外变精度粗糙集模型约简的研究及应用【1 3 ，2 5 】大多基于 z i a r k ow 提出的约简模型，但该模型下，约简过程会产生各种约简异常，约简后 不能保持原决策信息系统的信息。m a l c o l mb e y n o n 在文献 2 6 1 q b 简要分析了 z i a k ow 约简模型产生的约简异常，给出了实例描述，提出了限定约简概念，即 约简后区间必须包含原声区问。限定约简条件过于严格，不利于获取合理约简。 并且文献【2 6 】没有透彻考虑约简过程中包含度区间变化动态性，以及这种变化对 正域的影响，进而由此产生的分类异常，导致约简后决策信息系统不能维持原系 统特征，使产生的规则失去意义。 文献【2 7 】在文献【2 6 】基础上进一步研究了z i a k ow 约简模型产生的约简异 常，分析了约简过程中区间的动态性以及声约简对正区域元素的影响，给出了 区间动态性异常和分类异常的实例说明，提出了消除约简异常的口区间约简思 想，但是没有分析出现异常的本质原因。 m a r z e n ak r y s z k i e w i c z 基于变精度粗糙集模型定义了针对单个对象、决策类 和决策表的约简【2 扪，分析了三者的联系，并说明可辨识函数最小析取范式的项 即对应一个约简，信息系统动态增加后约简的保持等价于可辨识函数的保持。但 约筒定义针对特定声值，没有结合变精度包含度卢区间特性，并且没有分析z i a r k o w 约简定义在约简过程中可能产生的约简异常及其对约简结果的影响。 米据生等人基于变精度粗糙集理论与包含度理论，引入不协调目标信息系统 的上、下分布约简概念【2 9 l ，即保持每个决策类上( 下) 近似不变的最小属性集， 并讨论了它们之阃的关系。上( 下) 分布约简只考虑特定口值，没有考虑包含度 口区间特性，没有将区间特性引入到约简定义中，并且约简定义只限于决策类级 别，没有考虑变精度粗糙集各层面的约简。 经典粗糙集模型约简过程中，随着属性数目减少，分类质量、相对正域和决 策类下近似都呈单调递减变化，且三者变化保持一致，属性约简可通过三者之一 建立统一的模型【5 ，7 1 。变精度粗糙集模型虽然继承了经典粗糙集模型数学特征。 但是但众多特性已发生变化。文献 3 0 1 分析指出变精度粗糙集模型随着属性约 简，分类质量、相对正域和决策类下近似都打破了单调递减特征，三者变化不再 保持一致，需要针对不同层面建立相应模型，同时结合口区间特性从不同角度对 约简进行描述。 ( 3 ) 属性核。属性核反映了信息系统最本质特征，可作为启发式约简基点， 4 硕士学位论文第一章绪论 缩小约简过程搜索范围。由于属性核在知识约简过程中的重要作用，许多学者对 其进行了研究，并取得了大量成果。h u 根据可辨识矩阵得出计算决策信息系统 属性核方法【3 l 】，被众多文献引用，但该方法只能适应一致性决策信息系统。叶 东毅在h u 的基础上对可辨识矩阵进行了改进【3 2 】，得出一种新的求取属性核方法， 该方法对一致性和不一致性决策信息系统均适应。王国胤从信息熵观点定义了决 策信息系统属性核1 3 3 1 ，并与代数观点下的属性核进行了比较。杨明基于改进的 可分辩矩阵提出核增量式更新算法p 卅，考虑对象动态增加情况下核的更新问题。 上述研究成果都是基于经典粗糙集理论模型，然而国内外鲜有文献对变精度 粗糙集模型属性核进行研究。z i a r k ow 教授建立了变精度粗糙集理论体系，给出 了模型的形式化描述，但相对p a w l a kz 经典粗糙集模型，交精度粗糙集模型没 有讨论的内容之一就是属性核。m a l c o l mb e y n o n 在文献【2 6 】中简单提到属性核， 但是没有深入研究，没有给出其具体描述与分析。经典粗糙集模型作为变精度粗 糙集模型特例，只在厣= l 上建立模型，可以精确定义属性核【5 一。然而变精度粗 糙集模型不同分类质量对应不同口区间，不同区间所求约简不同，且不同区间约 简没有必然联系，难以从整体约简上定义属性核，故需要针对不同区间建立相应 属性核模型。 m a r s z a l - p a s z e kb 和p a s z e kp 通过结合伊近似区域定义了信任函数和似然函 数【3 5 】，并基于伊近似区域定义了基于声的概率分布、构造了d e m p s t e r s 组合规 则，实现了证据理论和变精度粗糙集理论的结合。随后z i a r k ow 等人提出非对 称变精度粗糙集模型( j ，西【3 6 l ，将对称变精度粗糙集模型扩展为非对称变精度粗 糙集模型，给出了模型的形式化描述，非对称变精度粗糙集模型是变精度粗糙集 模型的更一般化，其模型中的众多特性尚亟待研究与探讨m a l c o l mb e y n o n 在 文献 3 7 】中讨论了非对称变精度粗糙集模型特性，定义了( 五西一依赖度和( 五功一 分类质量，通过提出的( ，曲一图可以求取( 五功一约简，并能合理选择和的值。 加拿大r e g i n a 大学基于变精度粗糙集模型开发出k d d - r 系统，采用知识发现的 决策矩阵方法，用于医学数据分析和电信市场的决策分析这些成果进一步推动 了变精度粗糙集理论的发展与完善，加快了理论成果向实际应用的转换。 粗糙集模型扩展一直是粗糙集领域重要研究方向之一，变精度粗糙集模型作 为其重要扩展，可以分析信息系统统计观点上的数据模式，解决属性间弱依赖关 系。由于引入包含度历相对经典粗糙集模型其众多特性已发生变化，研究中需 要结合包含度口特征，分析该特征对整个模型的影响。 1 3 本文主要工作及创新点 本文首先介绍经典粗糙集理论和变精度粗糙集理论相关背景及概念，并对经 5 硕士学位论文第一章绪论 典粗糙集理论和变精度粗糙集理论约简特征进行详细分析，比较两者之间的异 同：然后系统讨论变精度粗糙集模型等价类归并的各种情况及其对约简的影响， 建立了变精度粗糙集模型三层约简体系，从不同层面对约简进行区间刻画，在此 基础上对变精度租糙集模型属性核进行探讨：最后理论与实际相结合，用u c i 数据集对建立的模型及提出的相关算法进行实验佐证。 本文主要创新点如下： ( 1 ) 对经典粗糙集模型和变精度粗糙集模型约简特征进行比较研究，分析 了两者之间的区别，阐明了属性可约性在两个模型中的异同及出现的原因，从而 可以更好的理解属性约简在两个模型中的本质； ( 2 ) 分类思想是经典粗糙集理论的基础，也是变精度粗糙集理论的基础， 包含度卢引入使得约去属性后等价类归并异常复杂，其分析将揭示包含度卢区间 动态变化以及不同等价类归并对分类质量和相对正域的影响，为变精度粗糙集模 型层次区间约简研究打下坚实基础； ( 3 ) 对z i a r k ow 约简定义下出现的约简异常及其原因做了进一步分析，提 出约简跳跃观点，详细分析了约简过程中出现的各种跳跃现象，阐明了属性约简 顺序对约简结果的影响，可以更深入的理解约简过程； ( 4 ) 建立变精度粗糙集理论区间约简层次模型，从分类质量、相对正域和 决策类下近似三个层次系统的定义区间约简，分析不同层次间的联系与区别，逐 步消除了z i a r k ow 约简模型产生的约简异常，解决了数据噪声和不确定性导致 的分类不准确问题，增强了模型的容噪能力，完善了变精度粗糙集模型思想体系。 同时结合口特性，针对区间约简提出衡量指标，可根据具体精度要求选择不同约 简层次； ( 5 ) 对变精度粗糙集模型属性核进行探讨，结合卢区问特性提出卢区问核 概念，说明求取完整的口区间核不可行。通过建立变精度粗糙集模型排序可辨识 矩阵，提出三种伊区间特征集合( 伊区间可约集、肛区间或可约集、伊区间不可 约集) ，分析了声区间核和伊区间特征集合的联系，证明伊区间不可约集为卢区 间核的子集，为启发式获取变精度粗糙集模型区间约简奠定基础。 上述理论成果进一步揭示了变精度粗糙集模型本质，完善了其主体思想，提 高了模型对噪声数据处理的有效性，同时为开发基于变精度粗糙集模型的数据挖 掘工具提供了借鉴、为进一步的研究工作打好铺垫。 1 4 本文组织结构 本文共分为八章： 第一章为绪论，主要介绍研究背景、国内外研究现状，阐述了本文主要工作 6 硕士学位论文 第一章绪论 及其刨新点； 第二章主要介绍经典粗糙集模型和变精度粗糙集模型相关基本概念、特点和 应用； 第三章对经典粗糙集模型和变精度粗糙集模型约简特征进行比较研究，分析 两者之间的异同； 第四章系统讨论变精度粗糙集模型下随条件属性的减少，条件等价类归并情 况及其对约简的影响，同时与经典粗糙集模型等价类归并情况进行比较； 第五章首先分析z i a r k ow i 约简定义下出现的各种约简异常，建立变精度粗 糙集模型约简层次体系，从分类质量、相对正域和决策类下近似三个不同层次分 别建立区间约简，分析三者之间的联系及对约简异常的消除； 第六章对交精度粗糙集模型属性核进行探讨，提出伊区间核概念，利用排序 可辨识矩阵自动求取伊区间特征集合，并以此为基础启发式求取变精度粗糙集模 型区闻约简； 第七章理论与实践结合，采用u c i 数据集对相关理论成果进行实验佐证； 第八章总结与展望，对本文主要工作进行总结，同时对未来进一步工作给出 建议和展望。 由于水平有限，文中难免存在错漏和不妥之处，望各位老师及同仁批评指正， 以利改进和提高。 7 硕士学位论文第二章粗糙集理论概述 第二章粗糙集理论概述 2 1经典粗糙集理论概述 分类是推理、学习与决策中的关键问题，租糙集理论建立在分类机制基础上， 将分类理解为特定空间上等价关系，而等价关系构成对该空问的一个完备划分。 粗糙集理论将知识理解为一种对对象进行分类的能力，其主要思想是利用已知知 识库中的知识来( 近似) 刻画不精确或不确定知识。 2 1 1 经典粗糙集理论基本概念 粗糙集理论假设集合中的元素有一些附加信息( 知识一数据等) ，知识是人 们对事务分类的依据，可以用属性和相应的值来描述。比如物体集合中的元素具 有“颜色”、“形状”、“大小”三种属性，则两个同等大小红色的圆球就不可以分 辨，即在现有的知识下不能将它们细分，形成了二者间的不可分辨关系。 不可分辨关系是粗糙集的起点，它意味着由于缺乏信息，不可能通过已有信 息辨识对象。换句话说，不能将单一的元素作为处理对象，而是将不可分辨对象 族作为一个整体( 即知识的一部分) 进行处理。 定义2 1 设u 是非空有限论域，r 是u 上的二元等价关系，r 为不可分辨 关系，序x c s = ( v ，矗) 称为近似空间。v ( x ，y ) u x u ，若( t y ) r ，则称对象x 和y 在近似空间s 中是不可分辨的。 u r 是u 上由且生成的等价类全体，它构成了( ，的一个划分。u r 中的集合 称为基本集或原子集，每一个原子集都不同于其他所有的原子集。若将u 中的集 合称为概念或表示知识，则s = ( u ，五) 称为知识库，原子集表示基本概念或知识 模块。任意有限的基本集的并和空集均称为可定义集( 精确集) ，否则称为不可 定义集。可定义集在知识库中能够被精确的定义或描述，可以用已知的知识进行 表示。 粗糙集理论中的知识表示一般采用信息表或称为信息系统的形式。 定义2 ；2 信息系统s = ( u ，a ，v , p ) ，其中u 表示非空有限论域：a 表示全体 属性集；v = u f 圪? a a 是属性值的集合，圪是属性a 的值域；户：u 4 一y 是 一个信息函数，成：a 寸v ，x u ，为一单射，反映了对象x 在信息系统中的 完全信息，其中见( a ) = p ( x ，a ) ，表示对象x 在属性a 上的取值。 对于给定的信息系统，每个属性子集定义了论域上的一个等价关系： v b a ，定义：v b b ，x r , y 只( 6 ) = 岛( b ) ，也称为：工和y 在关系b 下 是不可分辨的。 8 硕士学位论文第二章租糙集理论概述 定义2 3 给定信息系统s - - ( u ，a ，v ，p 1 ，b e _ a ，唧u 关于丑的上近似集 和下近似集分别定义为： 砑= u 【工k l 【z l n x 矿 = x u i 【x l n x 矿 蹦= u 卜k i 【z l j = x u i 【x l c x ( 2 - 1 ) ( 2 - 2 ) 其中【x 】。表示在属性集曰下的划分包含x 的等价类。 鱼也称为x 关于口的正域，记为：p o s ( x 1 ，表示根据现有知识判断出肯 定属于x 的对象所组成的最大集合；b x 表示根据现有知识判断出可能属于石的 对象所组成的最小集合；x 的边界域：b n ( x 1 = b x b _ x ，表示可能属于x ， 但不能完全肯定一定属于石的对象所组成的集合，边界域刻画了分类不确定对 象；x 关于丑的负域：n e g ( x ) = u b x ，表示根据现有的知识判断出肯定不 属于x 的对象所组成的集合。显然有曰( x ) = p o s ( x ) u s u ( x ) ，即上近似集由 正域和边界域共同构成。 粗糙集理论用一组上、下近似集合对x 从两个不同方向进行逼近，集合z 是 可定义的( 精确的) 当且仅当鲋= b x ，即：s n ( x ) = ，说明x 中的对象都 能确定分类；集合x 是不可定义的当且仅当躺b x ，即：s n ( x 1 妒，说明j 中存在不确定分类对象。 可以定义如下四种租糙集的基础类型： ( 1 ) 当酗痧且b x u ，x 称为u 中粗糙可定义的； ( 2 ) 当鲋妒且b x = u ，z 称为u 中广义不可定义的： ( 3 ) 当必= 妒且b x u ，x 称为u 中狭义不可定义的； ( 4 ) 当麟= 庐且b x = u ，x 称为【，中完全不可定义的。 定义2 4 决策信息系统s = ( u ，r = c u d , v , p ) ，其中u 为非空有限论域； c = c l ，c f 为条件属性集合；d = 田为决策属性集合：矿= k ik 为属性值域， 其中昨为属性，的值域；p ：u x r - - - v 为信息函数，以( x ) 表示对象x 在属性c ， 上的取值。由条件属性和决策属性定义的不可分辨关系对【，产生不同的划分， 分别表示为u c = 白，o ，q u q ) ，u d = d i 觑，, d i 删) ，其中每一个成员g 为一个条件类，d ，为一个决策类。 其中冈表示集合z 的基。可以看出决策信息系统是信息系统的一种特殊情 况，它将属性集细分为条件属性集和决策属性集两部分。 无决策的数据分析和有决策的数据分析是粗糙集理论在数据分析中的两个 主要应用。实际中，如果获取的数据集含有多个决策属性，则可以将其转化为单 决策属性进行处理。 9 硕士学位论文第二章粗糙集理论概述 2 1 2 经典租糙集理论特点 自粗糙集理论提出以来，目前已召开多界国内外学术会议，理论研究和实践 应用均表现出了强大的生命力。粗糙集理论已成为人工智能领域一个新的学术热 点，为研究软计算问题提供了一条新的研究方向，其主要有以下特点f 2 ，3 8 l ： ( 1 ) 处理各种数据，包括不完整数据以及拥有众多变量的数据； ( 2 ) 处理数据的不精确性和模棱两可性，包括确定性和非确定性的情况： ( 3 ) 求得知识的约简，去除冗余数据； ( 4 ) 从数据中揭示出概念简单、易于操作的模式； ( 5 ) 产生精确而又易于检查和证实的规则，特别适于智能控制中规则的自 动生成。 此外，粗糙集理论在处理数据过程中不需要先验知识，如模糊隶属函数和概 率分布等，它仅利用数据本身提供的信息进行处理，对数据的描述比较客观。 粗糙集理论处理数据的主要步骤如下： ( 1 ) 对数据进行初始化。粗糙集理论为离散属性提供了一种很好的工具， 但它不能直接处理连续属性，这一缺陷大大限制了粗糙集理论的应用范围1 3 9 1 。 现有离散化方法大体分为非监督离散化和监督离散化。非监督离散化包括等宽度 和等频率离散化 4 0 ，4 1 l ；与非监督离散化相反，监督离散化方法在对属性离散化 的过程中考虑了例子的分类信息，因此，离散化效果往往优于非监督离散化。耳 前最具有代表性的监督离散化方法有自然划分法、信息熵方法【4 2 】，检验法【4 3 垮。 ( 2 ) 知识约简。知识约简包括属性约简和值约简。属性约简针对决策信息 系统本身，在保持整体分类能力不变的前提下删除多余( 冗余) 属性，而属性值约 简是对具体的单个对象( 实例) 而言，消除多余的属性值，使规则泛化。针对属 性约简，已提出许多方法，包括可辨识矩阵方法m4 钉、启发式算法4 7 肄，并 针对海量数据集提出了动态约简【4 引、并行约简方法【4 9 1 等，趋于完善。属性值约 简方面，如可辨识矩阵方法【4 4 l 、标记法【1 8 】等。 ( 3 ) 规则获取。粗糙集模型获取规则目前提出了许多方法【5 0 5 1 5 2 ，5 3 ，删， 一般均在知识约简后，针对特定的约简集进行规则获取，因而只能获取部分规则。 不能获取决策信息系统所有规则。s k o w r o n 等人己证明求得完备的规则集是一个 n p - 完全问题【5 5 1 ，求得完备规则集不可行。在经典粗糙集理论下，s k o w r o n 等人 提出了缺省规则推理方法 1 , 5 5 1 ，但是仍然没有从根本上解决n p 完全问题。目前 一些研究者提出了多重知识库的概念【5 ”，将不同约简得到的规则集进行融合， 增强规则库的适应能力。 基于粗糙集理论的数据离散化、知识约简、规则获取及其评价仍然是粗糙集 理论重要的研究内容。 1 0 硕士学位论文 第二章粗糙集理论概述 2 1 3 经典粗糙集理论扩展 粗糙集理论的研究由于其历史较短，目前仍在不断发展与完善中。经典粗糙 集理论存在一些局限，不同学者结合其他软计算理论做出了不同的扩展模型。 当知识库中的知识由于随机原因或经统计得到，即知识库中的知识很可能是 不确定的，很多学者提出了统计( 或概率) 粗糙集模型【5 7 1 ，z i a r k ow 提出的变精 度粗糙集理论模型实质上也可以归为该类模型；当知识库中的知识模块都是清晰 概念，而被描述的概念是一个模糊概念，建立了粗糙模糊集模型【5 8 l ；当知识库中 的知识模块也是模糊的，学者提出了模糊粗糙集模型【铆。 粗糙集理论处理不确定性问题虽然具有其他理论不可替代的优越性，这并不 说明粗糙集理论可以替代其他处理不确定性问题的理论相反，与其他处理不确 定性方法的理论研究相互补充、互相渗透，主要体现在它与概率统计、模糊数学、 d s 证据理论和信息论的互补上。众多学者对此进行了研究，得出了许多相应的 研究成果【曲，6 1 ，6 2 】。 粗糙集理论以其独特的优势正在赢得越来越多研究者的关注，并在各个领域 获得了广泛的应用，然而这仍然是一门极其年轻并在高速发展的学科，还存在许 多亟待解决的问题【3 ，l 明： ( 1 ) 快速、高效的约简算法。高效的约简算法是粗糙集知识发现的基础， 目前尚不存在一种非常有效的约简算法求取所有约简。 ( 2 ) 海量数据集问题。现实中的数据库已越来越大，粗糙集理论适应海量 数据集的要求虽然已经有了一些有益的探索，如采样、并行化等，但是还没有找 到一种令人满意的方法。 ( 3 ) 粗糙集w e b 检索。随着i n t c m e t 的扩展，w e b 页面的增加，如何从众 多w e b 页面中利用粗糙集理论检索出有用的知识，是今后重要的研究课题之一 ( 4 ) 多方法融合。实验表明，还没有一种数据挖掘方法在所有测试数据集 上的表现都比其他相应方法出色，将众多方法进行融合，可能进一步提高知识发 现效率。 2 2 变精度粗糙集理论概述 针对经典粗糙集理论容噪能力差、规则泛化程度不高的缺陷，z i a r k ow 教授 于1 9 9 3 年提出了变精度粗糙集理论的思想【瑚它将集合论中标准包含关系扩展 为多数包含关系，在分类过程中允许一定程度的错误分类率口存在，一方面完善 了近似空间的概念，解决属性间若弱依赖关系问题【6 2 】；另一方面从数据集中发 现更多相关数据，这些相关数据在标准粗糙集中可能被认为是不相关或无法挖 掘。变精度粗糙集理论主要任务是解决不确定关系的数据分类问题，并基于这些 硕士学位论文第二章租糙集理论概述 分类获取近似决策规则。 z i a r k ow 教授考虑的是分类错误率声，即允许的分类误差，因而声e 0 ，0 5 ) 。 a n a 等人将卢理解为分类正确率，使( 0 5 ，1 。 论文中均