（计算机软件与理论专业论文）基于粗糙集理论的连续值属性离散化方法研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重迭邮电太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者盘名：衣f 掰 签字日期： z 吖年j 月珏日 学位论文版权使用授权书 本学位论文作者完全了解重庆邮电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重麽邮皇太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：磊嗽 导师签名： 调f 耻 签字日期： 可年j 月) 2 日 签字日期：函岬年歹月z z 日 重庆邮电大学硕士论文摘要 摘要 粗糙集理论是一种新的处理模糊和不确定知识的软计算工具。它能有 效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现 隐含的知识，揭示潜在的规律。近年来，粗糙集理论在机器学习、数据挖 掘等多个领域得到广泛应用。 粗糙集理论主要包括属性值离散化、属性核计算、属性约简和值约简 等几个部分。由于粗糙集以不可分辨关系为基础，属性核计算、属性约简 和值约简这三个部分处理的数据必须是离散型数据，而且离散化的结果将 直接影响后续工作。因此，探索基于粗糙集理论的离散化方法是非常必要 的。 属性值离散化技术在粗糙集理论中起着重要作用。有效的离散化方法 可以在减小数据规模的同时，在一定程度上能净化用于分类学习的数据以 及规范数据的表达形式，从而进一步提高机器学习算法的效率，降低挖掘 过程的复杂度，并可改进算法的可移植性。研究表明，在离散化后的数据 集上运用机器学习算法获取的知识往往具有更高的精度，且得到的规则也 具有更简洁的形式，更易于理解和使用。本文以提高离散化方法的效率和 降低算法的时间代价为目的，以粗糙集中数据的处理过程为主线，通过分 析候选断点的自身分布特点，结合聚类、信息熵等相关技术，对基于粗糙 集理论的离散化方法进行了研究。本文主要工作如下： 1 ) 提出了基于断点辨别力的离散化算法。通过分析候选断点与决策 类之间的相关性，定义了候选断点对决策类的辨别力，并以此作为断点重 要性的度量，实现连续值属性的离散化。实验结果表明，该算法比同类方 法有更好的识别率。 2 ) 提出了基于聚类与信息熵的离散化算法。首先对x 均值聚类算法 进行了改进，提出逐级均值动态聚类算法；然后使用逐级均值动态聚类算 法分别对单个属性的候选断点按其信息熵进行聚类分析，生成新的数目规 模更小的候选断点集，最后用基于信息熵的离散化算法完成断点的最终选 取并对连续值属性进行离散化。实验结果表明，该算法在识别率相当的情 况下比传统的离散化方法的时间代价更低。 关键字：粗糙集，离散化，连续值属性，逐级均值动态聚类，信息熵 重庆邮电大学硕士论文 a b s t r a c t r 0 u g h t 廿l e o 巧i se m e r g i i 培硒a 鹏ws o rc o m p u t i n gt o o lf o rd e a l i i l g 谢t l lf i l z 巧 觚d l c e r t a i l ld a t a ni sv e 巧e 伍c i e n tt 0 锄矗1 y 抚觚dp r o c e s si m p 代c i s e 舡l di m p e r f e c t d a 舡i tc 觚f m dp o t e n t i a lk n o w l e d g c 粕dn l l em 吼纰i l l 碥c e n ty e 盯s ，i tl l a sb e e n s t u d i e d 锄da p p l i e di 1 1m 锄yf i e l d ss u c h 弱m l l i n el e a n l i n g ，d a l am i i i i r 培锄de t c r o u g hs e ti sc o m p o s e do fc o m i m l o u sa 伯j b u t ev a l u e sm s c 托缸z a t i o l l ，砌b l 鹏 心d u c t i o n ，v a l u e 托d l i c t i o n a t h i b l i t cc o r ec o m p u t i i l g 觚de t c d i s c r e t i z a t i o nd i r e c u y 胡e c t st l l e 托砌t so ff o l l o w u p d i s c 删o ni s 姐i m p o r t 锄t 托s e 嬲 hi s s 鹏o fr o u g h tb a s e dd a 嚏a m i i l i i l g d i s c r e t i z a t i o nt e c l l n i q 佻p l a y s 觚i m p o n a n tr o l ei n u g l ls e tn l e o e 疏c t i v e d i s c 础z a t i o nm e m o d sc a nr e d u c et h e 加s c a l e ，p u r i 矽d a 惚f o rn l ec l 弱s i f i c a t i o ns t u d y t 0s o m ee x t e n t ，勰w e l l 舔n o m a l i 弱d a ：t ao nm ee x p 他s s i o no ft l l ef o m ，、：l l i c ht l l e 糟b y 如r m e ri n l p 哟i v et t 圮e 伍c i e n c yo fm l l i n el 翩m i i l ga l g o r i t l l m s ，r e d u c et h ec o m p l e x i 哆o f m ep r o c e s so fe x c a v a t i o i l 锄di m p r o v et l l ep o r 油i l 时o fa l g 嘶t l l m ni ss h o w nt h a t a f t | 盱t b ed i s c r e t i z a t i o no f 咖t s ，m m n el e 觚n i n g a l g o f i m m sc o l n do b 曲 k n o w l e 起e 诵t l lh i g h e rp r e c i s i o i l ，锄dn l em l e sg e n e m l e dc o l n db em 0 心c o n c i s e 觚db e e 弱i e rt 0b eu n d e r 咖1 0 d i i lo r d c rt oi m p r o v ee 伍c i e n c yo fd i s c 叫i z a l i o nm e t l l o d s 觚d 他d u c em e 缸ec o m p l e 嫡劬c l u s t e r i n g 觚di i l f 0 n n a _ t i o ne n l r o p y 觚do t l l e r 托l a t e d t e c h n o l o g i e sw e 坞l 塔e di l lt l l i sp a p e r t h em a j o rc t r i b u t i o n so ft l l i st i 圮s i sa 聆嬲 f o l l o w s ： 1 ) a m s c r e t i z a ：t i o na l g 耐也mf 0 rc o n t i m l 0 吣v a l u e sb 嬲e do nd i s c r i m i l l l a b i l i 锣o f c 鹏i sp r 0 岬d f 戤l y ，t h ed i s c r i m i m b i l 蚵o fc 讹i sd e f i 鹏db ya i 谢归n g 也e 陀l e v 趾c eo fi i l i t i a lc a n d i d a _ t ec u tp o i n t s 锄de a c hd e c i s i o nc l 弱s ，觚d 仃e a t e di t 弱a m e 硒u 他m e n to fi m p o r t a n c e s e c o n d l y ，r c s u l tc u tp o i n t ss e ti so b t a i l 心dt l l r o u g ht l l e d i s c 妇i 腿b i l i t ) ro fc u t s ，觚dw 嬲璐e dt 0f i i l i s hd i s c r e t i 动t i o no fc o m i i l ：u o 璐砌b u t e s s i m l l l a t i o ne x p e r i m e n tr e s u l t ss h o wm a tt l l e p 1 0 p o s e dm e m o dh 勰b e t t 盯c o r 托c t 托c o 鲥t i o nm t e 也a n0 t h e rs i m i l 盯m e t l l o d s 2 ) ad i s c r e t i z a t i o na l g o r i n l mb 船e do nc l 蜮e r i i l g 觚di l l f 0 衄a t i o ne n t r o p yi s p r o p o s e d f i r s u y ，r a i l l 【i n gm e a 璐d y m m i cc l l l s t e r i n gm 劬o dw 舔l l s e dt o 锄a l y z e i i l f l 0 珊a t i o ne n 们p yo fe a c hc a n d i d a t ep o i 吣，觚da wc 锄d i d a t ep o m s tw 硒 g e n e r a t e d s e c o n d l y ，曲锄a t i o ne n 仃o p yd i s c r e t i z a t i o na l g o 删：l l nw 硒u s e dt 0 l e c tc u t 重庆邮电大学硕士论文 p o i n t s 厅o mt 1 1 ec 锄l d i d a t ep o i n t ss c t s i l n u l a t i o ne x p c r i m e n tr e s u l t ss h o w 也a t 也e m c t h o di l a sl v l e rt i i i l ec o m p l e x i t ) r 吐l a n 位l d i t i o n a lm e t l l o d s k e yw o r d s ：r o u 曲s e t ，d i s c r e t i z a t i o n ，c o n t i n u o u s 砌h l t cv a l u e s ，豫】r 止i i l gm e 趾s 由，i l 锄i cc l u s t e r i n g ，i n f o 珊a t i o ne n b o p y i 重庆邮电大学硕士论文 目录 目录 摘j j i e i a b s t r a c t i i 第一章绪论l 1 1 粗糙集理论研究现状l 1 2 离散化问题研究现状2 1 3 论文选题的目的与意义3 1 4 本文的主要研究内容和组织结构。4 第二章粗糙集理论基础6 2 1 粗糙集理论的基本概念6 2 1 1 知识和决策表信息系统6 2 1 2 等价关系与不可分辨关系7 2 1 3 集合的上、下近似集和边界7 2 1 4 近似精度8 2 2 属性核、属性约简、值约简1 0 2 3 相容度1 2 2 4d 、结1 3 第三章基于粗糙集理论的离散化技术1 4 3 1 离散化问题的描述1 4 3 2 典型离散化过程1 4 3 3 基于粗糙集理论的数据离散化方法1 5 3 4 典型的粗糙集离散化算法1 6 3 4 1 基于布尔逻辑运算的离散化方法1 6 3 4 2 贪心算法及其改进算法1 7 3 4 3 基于属性重要性的离散化算法1 7 3 4 4 基于信息熵的离散化算法18 3 4 5 基于聚类的离散化算法。1 8 3 5 小结19 第四章基于断点辨别力的离散化算法2 0 4 1 引言2 0 4 2 基于断点辨别力的离散化算法2 0 重庆邮电大学硕士论文 目录 4 2 1 断点辨别力2 1 4 2 2 基于断点辨别力的离散化算法2 2 4 2 3 算法复杂度分析2 3 4 3 仿真实验结果及分析2 3 4 4d 、结2 6 第五章基于聚类与信息熵的离散化算法2 7 5 1 引言2 7 5 2 逐级均值动态聚类算法。2 8 5 2 1k 均值聚类算法2 8 5 2 2 逐级均值动态聚类算法。2 9 5 3 基于聚类与信息熵的离散化算法3 0 5 4 算法复杂度分析。3 6 5 5 仿真实验结果及分析3 6 5 64 、结。4 0 第六章总结及未来工作4 l 6 1 总结。：41 6 2 未来的工作4 l 致谢4 3 攻硕期间从事的科研工作及取得的研究成果4 4 参考文献4 5 v 熏焉霉雾蓊霹嚣熏熏蓊曩黔霉嚣熏琴黧瑟瑟露瑟瑟辫爨臻雾褥弑蘸穗瓣雾鬻翠鬻麓菘镊尊蒸囊爱? 慧鬻嘉黑礴鬻糍“ 重庆邮电大学硕士论文第一章绪论 第一章绪论 1 1 粗糙集理论研究现状 粗糙集理论是一种处理模糊和不确定知识的软计算工具。2 0 世纪7 0 年代，波兰学者zp a w l a k 教授和一些波兰科学院、波兰华沙大学的逻辑学 家们，一起从事关于信息系统逻辑特性的研究，粗糙集理论l l ，2 】就是在这些 研究的基础上产生的。zp a w l a k 教授在1 9 8 2 年发表了经典论文r o u g hs e t s ， 宣告了粗糙集理论的诞生。此后，粗糙集理论引起了许多数学家、逻辑学 家和计算机研究人员的兴趣，他们在粗糙集的理论和应用方面作了大量的 研究工作。1 9 9 1 年zp a w l a k 教授的专著和1 9 9 2 年应用专集的出版，对这 一时期理论和实践工作的成果作了较好的总结，同时促进了粗糙集在各个 领域的应用。1 9 9 5 年召开的第4 届模糊理论与技术国际研讨会上，针对粗 糙集与模糊集合的基本观点与相互关系展开了激烈的讨论，较大地促进了 粗糙集的研究。1 9 9 6 年在日本东京召开了第5 届国际粗糙集研讨会，这是 第一次在亚洲地区范围召开的粗糙集研讨会。1 9 9 9 年1 1 月在日本召开了 。第7 届粗糙集、模糊集、数据挖掘和粒度计算的国际学术研讨会一，阐 述了当前粗糙集、模糊集的研究现状和发展趋势，提出将着重在软计算、 数据库、人工智能和近似推理等理论和应用方面发展。2 0 0 6 年，第1 届粗 糙集与知识技术国际会议在中国重庆邮电大学召开。2 0 0 8 年5 月，国际知 识技术论坛在中国重庆邮电大学召开，包括波兰学者as k o w r o n 教授、国 际粗糙集协会主席、加拿大学者wz i a r k o 教授、中国科学院院士陆汝钎教 授等在内的近百名专家参加了会议，会议交流和研讨了知识技术领域的最 新进展和发展趋势。目前，在许多关于人工智能、模糊理论、信息管理与 知识发现等国际学术会议上经常可以看到许多涉及粗糙集的论文。 中国学者也积极投身于粗糙集理论的研究。19 9 3 年国家自然科学基金 首次对数据库中知识发现领域的研究项目给予资助。2 0 0 1 年5 月，在重庆 邮电大学举办了“第l 届中国r o u 曲集与软计算学术研讨会 ，邀请了创 始人zp a w l a k 教授做大会报告，随后每年的研讨会在规模和质量上均呈良 好的增长趋势。2 0 0 2 年1 0 月，在苏州大学举办了“第2 届中国r o u g h 集与软计算学术研讨会 。2 0 0 3 年5 月，在重庆邮电大学同时举办了“第 3 届中国r o u g h 集与软计算学术研讨会和“第9 届粗糙集、模糊集、数 重庆邮电大学硕士论文第一章绪论 据挖掘和粒度计算的国际会议 。同时，在2 0 0 3 年还成立了中国人工智能 学会粗糙集与软计算专委会，粗糙集的研究队伍也更加壮大，研究成果在 深度和广度上有了更大的发展。2 0 0 8 年8 月第8 届中国粗糙集与软计算学 术会议、第2 届中国w e b 智能学术研讨会和第2 届中国粒计算学术研讨会 在河南省新乡市召开。这些会议的举办有力地推动了中国粗糙集理论的应 用研究和深入发展。目前，中国学者在粗糙集理论的研究上已经达到国际 同行的先进水平，并且形成了一支较强的研究队伍。 经过近些年的研究和发展，粗糙集已经从理论上日趋完善，且已经被 证实在实践中是非常有用的。目前，粗糙集已经在机器学习、数据挖掘、 决策支持与分析、人工智能等许多领域得到了广泛的应用。由于粗糙集理 论对不确定性的描述是相对客观的，它无需任何先验知识，能在保留关键 信息的前提下对数据进行兼并求得知识的最小表达，获取已证实的规则知 识。因此，粗糙集理论在处理不确定性问题上相对于其它理论工具具有不 可替代的优越性，是知识获取的一个重要工具。 1 2 离散化问题研究现状 数据离散化是数据预处理中不可缺少的环节。以前，在机器学习领域 中，离散化处理通常被当作一种边缘性的辅助工作而没有受到应有的重 视，然而现实世界的许多应用中常常涉及连续值属性，目前许多的机器学 习算法却要求所处理的属性取离散值。因此，人们认识到为了能够处理这 些现实问题，必需对连续值属性进行离散化【3 ，4 】处理，使其转变为离散型。 从2 0 世纪9 0 年代初期，随着知识发现和数据挖掘的迅速发展，数据离散 化技术开始受到机器学习界的关注，并逐步吸收了统计学、信息论等领域 的研究成果。此后，离散化问题得到了较为广泛和深入地研究【5 喝】，多种 离散化算法被提出来【9 l 。但是，离散化技术并不是各学科可以完全通用的， 实际上它在不同领域中有自己独特的要求和处理方式，例如基于粗糙集的 离散化技术要求离散化前后需保证信息系统原有的分辨关系【l 们。 目前国际上针对粗糙集理论中的离散化问题也进行了相应的研究，并 取得了一些有价值的研究成果【以3 1 ，这些成果大致可以分为两类。第一类 方法基本上是很少甚至完全不考虑粗糙集理论的特殊性，即不把分辨关系 是否改变作为指标而仅考虑数据本身的规律，这样做有可能得到较少的离 散化断点集合，其结果却往往不能保证信息系统原有的分辨关系，因而离 熏黑黧燕雾鞣蒸震露罴露熏焉器鬻焉暴蘸瑟瑟瑟琵弱夏爱墨甓聚瑟琴餮蓊蓊黧器甏嚣嚣器魏麓震鬻鬻熏辫鬟篱粼影 ；矿1 瑚、瓴磷* 。锄融，一o p f r f 础。片：甜# # # 一t 仇，# 钳* ， 、“1 ，霹捌删，o f ，u t ”；“锦，v 舶d n z 7 ，“怖# 一? 一一水4 “7 懈，”+ 。j p * _ | | 一。，一惭”5 n 。哗 重庆邮电大学硕士论文第一章绪论 散化效果并不突出；第二类方法则充分考虑了粗糙集理论的特殊要求，即 对连续值属性离散化时应在保证信息系统原有的分辨关系的条件下选择 最少的断点，采取了结合方法来解决离散化问题，其结果能够保证信息系 统的分辨关系。其中，第一类算法都是从不同角度提出的粗糙集离散化算 法，如文献【1 4 】给出了一种将多项超曲面与支持向量机方法相结合的离散 化方法；文献【15 】提出了一种基于云模型的离散化方法；文献【1 6 】将模糊性 引进到离散化中；文献【17 】则讨论了离散化中的信息粒度；文献【l8 】提出了 基于聚类的离散化方法；文献【1 9 2 l 】则在对c h i 2 算法修正拓展的基础上 给出了基于分割区间合并的离散化算法。第二类方法中比较有影响的是a s k o w r o n 等人提出的粗糙集与布尔逻辑方法【2 2 1 ，该方法具有完备性，但是 其算法复杂度是指数级的，无法在实际问题中应用；文献【2 3 2 7 】提出贪 心算法并在此基础上提出了几种改进算法，这些算法都是基于断点对实例 的可分性，属于局部寻优搜索算法；文献【1 0 】提出了基于属性重要性的算 法；文献【2 8 】提出了基于信息熵的离散化算法；而文献【2 9 、3 0 】则采用遗传 算法搜索最佳离散化断点集合，属于整体搜索算法。 1 3 论文选题的目的与意义 对任何知识发现系统来说，都涉及到数据的预处理问题，不同领域的 数据由不同的方法获得。但所取得的数据不一定就适合直接用于挖掘操 作，尤其在知识发现中，数据预处理是非常重要的环节，包括数据采样、 属性选择、数据清洗和数据转换。其中数据转换主要是进行连续值属性的 离散化，使采样得到的数据转换成适合需求格式的过程。这是非常关键的 一环，只有合理、有效的离散化结果，后续的工作才是有效的，否则一切 都失去了意义。 数据离散化问题以前只是作为一种边缘工作，往往被忽略，直到近年 来随着知识发现和数据挖掘的迅速发展才引起了人们的关注。一般离散化 方法，只是简单地将连续值属性中数据划分成一些区间来为学习算法进行 离散化，而不考虑离散化如何影响到学习过程的执行，这类离散化方法可 能对后续的知识发现任务造成不可忽略的灾难，因为它可能会导致一些关 键信息的丢失，从而使得到的规则欠缺甚至不正确。 粗糙集理论主要包括属性值离散化、属性核计算、属性约简和值约简 等几个部分。由于粗糙集以不可分辨关系为基础，属性核计算、属性约简、 重庆邮电大学硕士论文第一章绪论 值约简这三个部分处理的数据必须是离散型数据，且离散化的结果将直接 影响后续工作。 从图1 1 的知识获取过程可以看出属性值离散化是粗糙集理论的重要 组成部分。基于粗糙集理论的离散化方法要求在保证离散化结果性能的前 提下防止对属性空间的过分细化，用尽可能少的断点将属性空间划分成尽 可能少的子空间。有效的离散化方法可以在减小数据规模的同时，在一定 程度上净化用于分类学习的数据以及规范数据的表达形式，从而进一步提 高机器学习算法的效率，降低挖掘过程的复杂度，并可改进算法的可移植 性，研究表明，在离散化的数据集上运用机器学习算法获取的知识往往具 有更高的精度，且得到的规则也具有更简洁的形式，更易于理解和使用。 r、 、一一一一离散化 属性 值 数据源等数据 约简 约 、一一一， 预处理 简 图1 1 基于粗糙集的知识获取过程 因此，属性值离散化问题是粗糙集理论中一类重要的研究课题，国内 外许多学者都对此方面予以了关注。探索基于粗糙集理论的离散化方法， 具有重要的现实意义。 1 4 本文的主要研究内容和组织结构 粗糙集研究课题有着广泛的应用前景，可应用于机器学习、数据挖掘 等多个领域，如何采用高效的离散化方法对连续值属性进行预处理，这在 粗糙集理论中不可缺少。目前，基于粗糙集的离散化方法还不能满足现实 数据的需要，因此，本文对基于粗糙集的离散化相关技术、方法进行了改 进、提高： 1 ) 提出了基于断点辨别力的离散化算法。通过分析候选断点与决策 类之间的相关性，定义了候选断点对决策类的辨别力，并以此作为断点重 要性的度量，实现连续值属性的离散化。实验结果表明，该算法比同类方 法有更好的识别率。 2 ) 提出了基于聚类与信息熵的离散化算法。使用逐级均值动态聚类 方法对每个属性的候选断点按信息熵进行聚类分析，并生成新的候选断点 4 重庆邮电大学硕士论文 第一章绪论 集，再用基于信息熵的离散化算法完成断点的选取并对连续值属性进行离 散化。实验结果表明，该离散化算法在识别率相当的情况下比传统的离散 化方法的时间代价更小。 本文按以下顺序组织内容。 第一章概述了粗糙集理论和离散化问题的研究现状，阐述了基于粗糙 集理论的离散化方法课题的研究意义及本文研究的主要工作。 第二章介绍了粗糙集理论的相关概念及本文所用到的理论。 第三章对离散化问题进行了简单的描述，概述了典型的离散化过程和 基于粗糙集理论的连续值属性离散化的特征，对几种典型的基于粗糙集的 离散化算法作了介绍。 第四章分析了候选断点与决策类之间的相关性，提出了基于断点辨别 力的离散化算法并对该算法进行了仿真试验。 第五章介绍了基于聚类的离散化算法和基于信息熵的离散化算法的 差异性，对k 均值聚类算法进行了改进，提出了基于聚类与信息熵的离散 化算法并对该算法进行了仿真试验。 第六章对本论文的工作做了总结，同时对该课题未来研究方向作了展 望。 重庆邮电大学硕士论文 第二章粗糙集理论基础 第二章粗糙集理论基础 2 1 粗糙集理论的基本概念 2 1 1 知识和决策表信息系统 。知识一这个概念在不同的范畴内有多种不同的含义。在粗糙集理论 中，。知识力被认为是一种分类能力。人们的行为是基于分辨现实的或抽 象的对象的能力，如在远古时代，人们为了生存必须能分辨出哪种食物可 以食用；医生给病人诊断，必须辨别出患者得的是哪一种病。这些根据事 物的特征差别将其进行分门别类的能力均可以看作是某种“知识一的体现。 定义2 1 给定对象论域u ，对于任何子集x u ，称之为u 中的概念 或范畴。为了规范起见，认为空集也是一个概念，并且u 中任何概念簇称 为关于u 的抽象知识，简称知识。 例如，给定一玩具积木集合u = 毛，毛，毛，毛，毛，毛) ，子集“，毛，而 构 成按颜色分类的“红色一知识，子集k ，为，毛) 构成按体积分类的“大的一 知识。 粗糙集理论中用决策表信息系统来描述论域中的对象。决策表是一张 二维表格，每一行描述一个对象，每一列描述对象的一种属性。属性分为 条件属性和决策属性，论域中的对象根据条件属性的不同，被划分到具有 不同决策属性的决策类。 定义2 2 一个决策表信息系统( 简称决策表) s = ，其中， u 是对象的集合，也称为论域，r = c u d 是属性集合，子集c 和d 分别称 为条件属性集和决策属性集，d f 2 j ，y = uk 是属性值的集合，形表示 ，e 冠 属性，e 天的属性值范围，即属性，的值域，厂：u 尺寸y 是一个信息函数， 它指定c 厂中每一个对象x 的属性值。 决策表信息系统是一类特殊而重要的知识表达系统，它指当满足某些 条件时，决策应当进行。多数涉及决策的问题都可以用决策表的形式来表 示，这一工具在决策应用中起着重要的作用。 6 重庆邮电大学硕士论文第二章粗糙集理论基础 2 1 2 等价关系与不可分辨关系 设u 是一个论域，r 是u 上的一个等价关系。蚴表示u 上由r 导出 的所有等价类。【x 】。表示包含元素x 的尺等价类，x u 。一个知识库就是 一个关系系统k = u ，丹，其中u 是论域，尸是u 上的一个等价关系簇。 如果qs 尸且q o ，则n q ( q 的所有等价关系的交) 也是一个等价关系， 记作l n d ( q ) 。 定义2 3 肛( u 尸) 、k l = ( u q ) 是两个知识库。如果z d ( 尸) = 删d ( q ) ，则 称x 和k l ( 或q 和p ) 是等价的，记作k 兰k ( 或p 兰q ) 。 分类过程中，相差不大的个体被归于同一类，它们的关系就是不可 分辨关系。不可分辨关系是粗糙集理论的基石，揭示了论域中知识的颗粒 结构，也是定义其他概念的基础。 定义2 4 不可分辨关系是实例由属性集p 表达时，在论域u 中的等价 关系。如属性集尸cr ，对象x ，l ，互u ，当且仅当月x 砂胡z 砂时，x 和】， 是不可分辨的，即 办胁( p ) = ( x ，y ) 【，i v 口p ，( x ，口) = 厂( 】，口) ( 2 1 ) 2 1 3 集合的上、下近似集和边界 定义2 5 给定知识表达系统s = ，对于每个子集x u 和 不可分辨关系曰，x 的上近似集和下近似集分别可以由占的基本集定义如 下： 罡( r ) = u ri ( r ui 删b ) 人r x ) ) ， 曰一( x ) = u zl ( z ul 刃v d ( 曰) 人r 厂、x 彩) ) ， ( 2 2 ) 其中，u l 删d ( 曰) = x l ( x u 州州6 ( 6 ( 功= 6 ( y ) ) ) 是不可分辨关系丑对u 的划分，也是论域u 的b 基本集的集合。 上近似集和下近似集的概念也可以通过集合来定义： 罡( x ) = 红l u 【x 】口x ) ) ， b 一( x ) = xi ( x u 【x 】口厂、x a ) ) ( 2 3 ) 即当且仅当【地s 置x 昱( ；当且仅当b kr 、x 曩x 伊。 定义2 6 集合巩( = 伊罡( 幻称为x 的b 边界；尸d 仞= b 一仞 称为x 的b 正域；嘁( = 【厂噩( 称为x 的曰负域。 罡( x ) 是根据知识口( 属性子集b ) ，u 中所有一定能归入集合x 的元 素构成的集合，即所有包含于x 的基本集k 的并。b 一( x ) 是根据知识b ， 重庆邮电大学硕士论文 第二章粗糙集理论基础 u 中所有一定能和可能能归入集合x 的元素构成的集合，即所有与x 的交 不为空集的基本集z 的并。肼。( x ) 是根据知识b ，u 中既不能肯定归入集 合x ，又不能肯定归入集合x 的元素构成的集合。正域尸傩日( x ) 是根据知 识b ，u 中所有一定能归入集合x 的元素构成的集合。负域脚。( x ) 是根 据知识曰，u 中所有不能确定一定归入集合x 的元素的集合。边界域 励( x ) 是某种意义上论域的不确定域，边界域中的元素既不能肯定地属 于集合x ，又不能肯定地属于z 。图2 1 为粗糙集概念的示意图。 图2 1 粗糙集概念的示意图 有了边界域的定义，就可以得到上近似集、下近似集、正域、边界域 之间的如下关系： 矿( 朋= m 叉( 幻u 巩( 幻 = 罡( x ) u 剧( x ) = u 厦( x ) ( 2 4 ) 这几个集合的基数之间存在如下关系： iu b 以( x ) i - lul - ib 一( x ) 罡( x ) l ( 2 5 ) 2 1 4 近似精度 集合的不确定性是由于边界域的存在而引起的，集合的边界域越大， 其精确性越低，为更准确地表达这一点，引入精度的概念。 定义2 7 假定集合z 是论域u 上的一个关于知识尺的粗糙集，定义其 只精度( 在不发生混淆的情况下，也简称精度) 为： 呔( x ) = i r ( x ) i l r 一( x ) i ( 2 6 ) 重庆邮电大学硕士论文 第二章粗糙集理论基础 定义其尺粗糙度为： 最( r ) = l d 尺( x ) ( 2 7 ) 由此可见，粗糙集x 的精度是一个区间【0 ，l 】上的实数，它定义了粗糙 集x 的可定义程度，即集合x 的确定度。x 的粗糙度与精度恰恰相反，表 示的是集合x 的知识的不完全程度。 下面，通过一个实例对粗糙集的基本概念进行说明。 例2 1 表2 1 给出一个决策表，其中 l ，2 ，6 是对象集合， p r i c e ，m i l - e a g e ，s i z c ，m 觚- s p e e d ) 是条件属性集合，d 是决策属性。 表2 1 决策表 c a rp r i c e m i l e a g e s i z e m a x s p e e d d l h i g h h i g h f u l l l o w g 0 0 d 2l o w h i 曲 f u l ll 0 wg 0 0 d 3 h i g h l o w c o m p a c th i g h p 0 0 r 4 h i g hh i g h f u l l h i g h g o o d 5l o w h i g h f u l l h i g h e x c e l 6l 0 w h i g h f u l ll 0 wg o o d 对于属性子集曰= p r i c e ，m a ) 【s p e e d ，计算曰对论域u 的划分： u ia d ( 曰) = 蜀，岛，马，皿 ， 其中置= l ，岛= 2 ，6 ，马= 3 ，4 ，蜀= 5 。 对于决策属性集d = 讲，计算d 对论域u 的划分： u i 刷d ( d ) = 4 ，砬，b ， 其中q = l ，2 ，4 ，6 ，d 2 = 3 ) ，d 3 = 5 ) 。 显然，集合4 是一个br o u g h 集。下面分别计算d l 的上、下近似集、 正域、边界域、精度和r o u g h 度。 因为qn 置= 垦= 1 ) ，d ln 忍= 岛= 2 ，6 ，d ln 忍= 4 ) f 2 j ，qr 、日= 囝， 所以可得： 曰一( d 1 ) = 马u 岛u 马= l ，2 ，3 ，4 ，6 ，噩( 4 ) = 丑u 呸= 1 ，2 ，6 ) ， p 呱( q ) = 噩( q ) = l ，2 ，6 ) ，引( q ) = 岛= 3 ，4 ) ， 如( q ) = 尻( q ) i i 口一( b ) i - 3 5 ，弓( d 1 ) = l 一九( q ) = 2 5 。 9 磊麓。善筹漱露藏嚣篓笔? 鼍；：袈冀：鼍：翟；i l 等转锰翁“嘉了；蠢z ：j ? i 孑氲兰二；管；= 备毫氦端莓i ：j 芸j 五品嚣f 姑；巍萁霸荔西篇再撅i 巍矗e 露+ fa i 盂* 0 ，磊抻。* 墨。 “t 。、4 口嘶* 。i ；口一- * * 玻_ 。搏。一，；? 瓣母掳m ”。妒嘣掘释砖一”罅。“拍；吼，i 婶；m 重庆邮电大学硕士论文第二章粗糙集理论基础 2 2 属性核、属性约简、值约简 粗糙集理论的一个基本方向是研究条件属性的一些特殊子集。由这些 子集所得到的分类信息和决策规则完全等同于用所有的条件属性所得到 的分类和决策，这样的子集称为约简。为了获得简洁的分类知识和决策规 则，知识约简是必需的，在粗糙集理论中，知识约简分为属性约简和属性 值约简。 定义2 8 设u 是一个论域，尸是定义在u 上的一个等价关系簇，r 尸。 如果刷d ( p r ) ) = 优d ( 尸) ，则称关系足在尸中是绝对不必要的( 多余的) ； 否则，称灭在尸中是绝对必要的。 绝对不必要的关系在知识库中是多余的，如果将它们从知识库中去 掉，不会改变该知识库的分类能力。相反，若知识库中去掉一个绝对必要 的关系，则一定改变知识库的分类能力。 定义2 9 设u 是一个论域，尸是定义在u 上的一个等价关系簇，灭尸； 如果每个关系足p 在尸中都是绝对必要的，则称关系簇p 是独立的；否则， 称尸是相互依赖的。 定义2 1 0 设u 是一个论域，尸是定义在u 上的一个等价关系簇。尸中 所有绝对必要关系组成的集合称为关系簇尸的绝对核，记作僦( p ) 。 定义2 1 1 设u 是一个论域，尸和q 是定义在u 上的两个等价关系簇且 q 互p 。如果 1 ) 剧d ( q ) = 刷d ( 尸) ， 2 ) q 是独立的， 则称q 是尸的一个绝对约简。 在讨论决策表信息系统约简的时候，一个条件属性么就对应着一个等 价关系( 也称不分明关系或不可分辨关系) ，即在条件属性彳上取值的相等 关系，它对论域u 形成一个划分u 彳。决策表的所有条件属性形成条件属 性集合尸对论域u 的划分u 尸，同时，决策属性d = d 也对论域形成一个 划分u d 。这两个划分形成了条件属性和决策属性在对论域样本分类上的 知识。属性约简的目标就是要从条件属性集合中发现部分必要的条件属 性，使得根据这部分条件属性形成的相对于决策属性的分类和所有条件属 性所形成的相对于决策属性的分类一致，即和所有条件属性相对于决策属 性d 有相同的分类能力。这就是相对约简的概念。 定义2 1 2 设( ，是一个论域，尸和q 是定义在u 上的两个等价关系簇。 q 的尸正域记为尸晖( q ) ，定义为 l o 重庆邮电大学硕士论文第二章粗糙集理论基础 尸d 昂( q ) = u 罡( x ) ( 2 8 ) x 我| q 定义2 1 3 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇。 如果p 啤( q ) = 尸啦p ， ) ( q ) ，则称，为户中相对于q 可省略的( 不必要的) ， 简称p 中q 可省略的；否则，称，为p 中相对于q 不可省略的( 必要的) 。 定义2 1 4 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇。 若尸中的每一个，都是尸中q 不可省略的，则称尸为( 相对于) q 独立的。 定义2 1 5 设u 是一个论域，尸和q 是定义在u 上的两个等价关系簇， 若尸的q 独立子集sc ，有p 呱( q ) = 户啤( 9 ，则称s 为尸的q 约简。 定义2 1 6 设u 是一个论域，尸和q 是定义在u 上的两个等价关系簇， 尸的所有q 不可省略原始关系簇称为尸的q 核，记为c i 呱( 尸) 。 定理2 1 设u 是一个论域，尸和q 是定义在u 上的两个等价关系簇， 蛾( 尸) 为尸的所有q 约简关系簇，c l ，峨( p ) 为尸的q 核，则 c 呱( 尸) = n 蛾( 尸) - ( 2 9 ) 定义2 1 7 设f 是属性集d 导出的分类，c 是条件属性集合，d = d ) 是 决策属性集合，且占c c 。则对于任意属性口c 曰的重要性脏f ( 口，b ，d ) 定 义为 妍( 口，曰，d ) = u 。l ( f ) 一( f ) ( 2 1 0 ) 核与属性重要性都是r o u g h 集理论中重要的基本概念。由定理2 1 可 以知道，核包含在所有的约简中，即可以解释为当属性约简时它是不能消 去的属性集合，所以它可以作为属性约简时启发式算法的计算基础。属性 重要性的度量是根据论域中的样例来得到的，不依赖于人的先验知识，可 以作为选择属性时的主要依据。下面通过实例对决策表的约简问题加以说 明。 例2 2 以表2 1 所示的决策表为例，求决策表的相对属性约简。 令d = d 为决策属性集，c = p r i c e ，m i l e a g e ，s i 跫，m a x - s p e e d 为条件属性 集，分析决策表可得： a = “1 ) ， 2 ， 3 ， ， 封， 5 ) ，尸n 鞋( 功= u 。 因此，论域u 是c 上相对于d 一致的，这说明该决策表是完全确定的 决策表，决策表中不包含不一致信息。 刃v d ( c 、 p r i c e ) = 1 ，2 ，6 ) ， 3 ) ， 4 ，5 ， a r d ( c m i l e a g e ) = “1 )