（计算机应用技术专业论文）模糊粗糙集属性约简及多模糊决策树分类器融合.pdf

摘要 摘要 属性约简是粗糙集理论的一个重要思想，然而利用粗糙集理论进行约简，必须将连 续值转换成离散值进行处理，在某种程度这一过程会造成信息的损失。融合了模糊集与 粗糙集的模糊粗糙集能够保留连续属性值信息，使得模糊粗糙集属性约简比粗糙集属性 约简具有更高的准确性。大多数模糊粗糙集的属性约简算法都是找到最重要的属性约 简，由于这个最重要的属性约简，只包含信息系统的部分属性，会使得对未知事例分类 时，分类的错误率难以进一步降低，为了弥补这一缺陷，本文提出了一种找到多个模糊 属性子集的算法，并针对这多个属性子集，提出了一种基于模糊积分的多模糊决策树分 类器融合算法，该算法能充分利用每个模糊决策树的信息，从而可获得比单个模糊决策 树更高的分类准确率。 关键词粗糙集属性约简模糊半h 糙集模糊决策树模糊积分 a b s t r a c t a b s t r a c t i nr o u g hs e tt h ea t t r i b u t er e d u c ti st h ec r u c i a li d e a b u tb e f o r ef i n d i n ga t t r i b u t er e d u c t s w i t hr o u g hs e t ，c o n t i n u o u sv a l u e sm u s tb et r a n s f o r m e di n t oc r i s pv a l u e st oh a n d l e , t os o m e e x t e n t ，t h ei n f o r m a t i o nl o s so c c u r si nt h ep r o c e s so fd i s c r e t i z a t i o n t h ei n t e g r a t i o no ff u z z y s e t sa n dr o u g hs e t sc a np r e s e r v et h ei n f o r m a t i o no fc o n t i n u o u sv a l u e sa t t r i b u t e ，w i t hf u z z y r o u g hs e t sa t t r i b u t er e d u c tc a ng e th i g h e ra c c u r a c yt h a nw i t hr o u g hs e t s u s i n gm o s to ft h e f u z z ya t t r i b u t ea l g o r i t h m ，t h em o s ti m p o r t a n tf u z z ya t t r i b u t es u b s e t s ( r e d u c t ) c o u l db e f o u n d b e c a u s eo f o n l ys o m eo fu s e f u li n f o r m a t i o nb e i n gc o n t m n e di nt h i sa t t r i b u t er e d u c t ， t h ec l a s s i f i c a t i o ne r r o ra c c u r a c yc o u l d n tb ed e c r e a s e da n ym o r e ，i no r d e rt om a k ef u l lu s eo f t h ei n f o r m a t i o np r o v i d e db ye v e r yf u z z ya t t r i b u t er e d u c t ，i nt h i sp a p e r , w ep r e s e n tan o v e l a l g o r i t h m ，w i t ht h i sa l g o r i t h ms e v e r a lf u z z ys u b s e t c o u l db ef o u n d t ot h e s ef u z z ys u b s e t ，w e p r e s e n tam u l t i p l ef u z z yd e c i s i o nt r e s sf u s i o na l g o r i t h mb a s e do nf u z z yi n t e g r a l ，m u l t i p l e f u z z yd e c i s i o nt r e ec l a s s i f i e rf u s i o nc a nm a k ef u l lu s eo fi n f o r m a t i o np r o v i d e db ye v e r yf u z z y d e c i s i o nt r e s s ，t h ef u s i o nl e a d st oa l lh i g h e rc l a s s i f i c a t i o na c c u r a c yt h a ns i n g l ef u z z yd e c i s i o n t r e e k e y w o r d sr o u g hs e t a t t r i b u t er e d u c t f u z z yr o u g hs e tm u l t i p l ef u z z yd e c i s i o nt r e e f u z z yi n t e g r a l h 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：习堕壁孕立尘一 醐：1 年j 月一日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密西。 ( 请在以上相应方格内打“”) 保护知识产权声明 本人为申请河北大学学位所提交的题目为( 利稍嘲障篷缳砌钐钼饧b 岛) 的学位论文，是我个人酬币。乏霞，垠) 指导并搀徽蹶勰金 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人：二社迎臣z 硷卜_ 一日期：彳l 年j 月上日 作者签名：一j 貉型暨丘塑卫一 别磴轹1 辟一 日期：单年上月一上一月 日期：4 年_ l 月! 日 f 第1 章绪论 第1 章绪论 1 1 课题研究的背景 19 8 2 年波兰学者z p a w l a k 首先提出粗糙集理论( r o u g hs e tt h e o r y ) ，这是一种研 究不精确性和不确定性知识的理论。粗糙集理论能够在缺少数据先验知识的情况下，以 对观测数据的分类能力为基础，解决模糊或不确定性数据的处理，算法简单，易于操作。 粗糙集理论自问世以来，迅速发展为一门既有理论又有应用的研究领域。近几年来，粗 糙集理论在国内外有了更大的发展，取得了很多可喜的成绩。 属性约简是粗糙集理论的核心内容之一，传统基于粗糙集的约简算法，只能有效地 处理包含离散值的数据集，但是对连续属性处理能力非常有限。而现实世界中大多数的 数据集，属性值往往为连续值数据，且大多有模糊性。因此，利用粗糙集理论进行约简 处理之前，必须对连续值属性进行离散化处理，而离散化后的属性值由于没有保留属性 值在实数值上的差异，离散化的过程往往导致某种程度的信息损失。 在粗糙集理论中引入模糊思想，产生了模糊粗糙集。模糊粗糙集通过粗糙隶属函数 将模糊集的研究方法引入到粗糙集的研究中，把模糊集合中的隶属度看作是粗糙集理论 中的属性值，能更好地指导特征选取，更完整地保留原始数据的信息，从而提高了知识 获取的准确性。 模糊粗糙集属性约简是建立在模糊上、下近似集的概念的基础上的，以保证包含实 数的数据集的约简。传统的模糊粗糙集属性约简算法，一般是找到一个最重要的属性约 简，利用该属性约简产生决策规则，对未知事例进行分类。但是，由于只生成了一个属 性约简，这一个属性约简并不能全面的反映整个信息系统的信息，导致在对某些类的事 例进行分类时，错误率难以进一步下降，为了弥补这一缺陷，本课题对生成多个属性子 集进行了研究。 决策树归纳是从示例中产生规则的一种重要途径，它的典型算法称为i d 3 ，是由 o u i n l a n 与1 9 8 6 年引入的。这种学习的主要特征是首先使用某种启发式信息引导一个决 策树，然后将树中每一条从根到叶子的路径转换成一个产生式规则。模糊决策树是传统 决策树的一种推广，模糊决策树中的每一个叶结点对应一条模糊规则。这样一个模糊决 河北大学t 学硕十学彳寺论文 策树可以转化为若干个模糊规则，每一个模糊规则带有一个可信度。模糊决策树作为传 统的决策树的一种推广，在容许不精确信息方面显得更为自然。 每个属性子集可诱导出一棵决策树，利用生成的多个属性子集诱导出的多个决策树 对未知事例进行分类，可更全面的反映系统的信息，从而提高系统的分类准确率，本课 题在多个模糊决策树共同作用生成融合的结果方面进行了研究。 1 2 本课题的主要工作及意义 本课题在以下几方面展开工作并取得了一些结果。 1 、讨论了粗糙集及粗糙集属性约简。 2 、讨论了模糊粗糙集及模糊粗糙集属性约简，并提出了一种改进的生成多个模糊粗 糙集属性子集的算法。 3 、讨论了模糊决策树及多分类器融合，并提出了多模糊决策树信息融合算法。 利用生成的多个属性子集诱导出的多个决策树对未知事例进行分类，可更全面的反 映系统的信息，从而可提高系统的分类准确率。 1 3 本论文的组织 本论文共分为五章，第一章介绍了课题研究的背景、主要工作、意义以及本文的组 织结构。第二章对课题涉及的粗糙集及粗糙集属性约简进行了介绍。第三章讨论了模糊 粗糙集及模糊粗糙集属性约简，并提出了一种改进的生成多个模糊粗糙集属性子集的算 法。第四章讨论了模糊决策树、模糊测试和模糊积分，并提出了多模糊决策树多分类器 融合算法。第五章对本课题的研究进行了总结及展望。 2 第2 章粗糙集o 粗糙集属性约简 第2 章粗糙集与粗糙集属性约简 粗糙集( r s ，r o u g hs e t ) 理论是经典集合理论的拓展，是一种研究不确定知识和 数据的表达、学习、归纳的理论方法n 3 。经过2 0 多年的研究，取得了很多成果，建立了 一套比较完善的粗糙集理论体系。本节对粗糙集理论的基本思想与本文研究内容相关的 概念加以介绍。 2 1 粗糙集与近似集心- 3 t 铂 定义2 1 如果给定一个有限的非空集合u ，称为论域，设x u ，r 是u 上的等价 关系，a = ( u ，r ) 是一个近似空间，在a 上，如果x 是一些r 基本类的并集，则称x 是 r 一可定义的；否则称x 是r 一不可定义的。 定义2 2 设x c u 是任一子集，r 是u 上的等价关系，则有( x ) = u yeu r ：y cx ) r ( x ) = u y u r ：y n x 分别称为x 的r 一下近似和r 一上近似，其中囝是空集，y 是u 上按等价关系r 分成的等价类。上近似和下近似之间的差被称作x 的r 一边界集，表 u ，、 、 、 r、 r l - l _ r 略、 ； 、 、 图2 1x 的r 一卜近似和r 一上近似 示为b n 。( x ) = r ( x ) 一一r ( x ) ，p o s n = 壁( x ) 称为x 的r 的j 下域：n e g 。= u r ( x ) 称 为x 的x 的r 负域，如图2 1 所示。 由定义2 2 可知，在依据知识r 判断时，r ( x ) 由必定属于x 的对象组成的集合， r ( x ) 是由可能属于x 的对象组成的集合，b n 。( x ) 是由既不能明确判断属于x 也不能 3 河北大学t 学硕十学位论文 明确判断不属于x 的对象组成的集合，n e g 。( x ) 则是由一定不属于x 的对象组成的集合。 边界域b n 。( x ) 是某种意义上论域的不确定域，边界域中的元素既不能肯定地属于集合x ， 也不能肯定地不属于x 。 2 2 信息系统与决策表 形式上，信息系统是一个四元组s = ( u ，a ，v ，f ) ，其中 u ：对象的非空有限集合，称为论域； a ：属性的非空有限集合； v ：比，v a 是属性a 的值域； o e a f ：u a v 是一个信息函数，它为每个对象的每个属性赋予一个信息值。即va e a ， x u ，f ( x ，a ) v a 。 信息系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对应对象 的属性，对象的信息是通过指定对象的各属性值来表达。容易看出，一个属性对应一个 等价关系，一个表可以看作是定义的一族等价关系，即知识库。前面讨论的问题都可以 用属性及属性值引入的分类来表示，知识约简可转化为属性约简。 决策表是一类特殊的信息系统，一个决策表是一个知识表达系统s = ( u ，a ，v ，f ) ，其 中a = cud ，c 是条件属性集，d 是决策属性集，d a 。 2 3 粗糙集属性约简 所谓属性约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重 要的属性。基于r o u g h 集理论的知识获取，主要是通过对原始决策表的属性约简得到的。 原始决策表信息系统中的条件属性并不是同等重要的，甚至其中某些条件属性是冗余 的，这些冗余属性的存在，一方面是对资源的浪费( 需要存储空间和处理时间) ；另一 方面，也干扰人们作出j 下确而简洁的决策，因而对决策表进行属性约简是粗糙集理论的 核心内容之一随6 引。 定义2 3设r 是一个等价关系族，r r ，如果i n d i = i n d ( r 一 r ) ，则称r 在r 中是可被约去的知识；如果p = r - r ) 是独立的，则p 是r 中的一个约简。 定义2 4设r 和q 都是等价关系族，如果 尸傩肋( r ) ( n d ( q ) ) = 尸傩，d ( r 一 p ) ) ( i n d ( q ) ) 4 第2 章粗糙集与粗糙集属性约简 则称p 是r 上q 一可约去的：否则p 是r 上q 一不可约去的。 定义2 5如果r 上的每个等价关系p 都是q 一不可约去的，则称p 是q 一独立的 或p 关于q 是独立的。 定义2 6( 依赖度) 令n = ( u ，r ) 为一知识库，且p ，o c _ r ，q 以程度卢依赖p ， 表示为p 卢e ，卢= y ，( q ) = 警 p o s 。( q ) 是所有那些借用知识r 能被分类为知识q 的基本类的个体的集合；如果整体 知识r 对分类个体为知识q 的基本类是必要的，则知识r 是q 的约简；知识r 的q 约简 是知识r 的最小子集，它提供了个体到知识q 的基本类，与整体知识r 一样有相同的类； 只有一个q 约简的知识r ，就某种意义上说，它是惟一确定的，也即当分类个体为知识 q 的基本类时，利用知识r 的基本类存在惟一一种方法；在非确定的情况下，即如果知 识r 有多个q 约简，则利用知识r 分类个体为q 的基本类存在多种方法。 下面，我们将具体介绍几种决策表属性约简的算法。这里，设原始决策表的条件属 性集合为c = ( c ；ii = l ，2 n ) ，决策属性集合为d = d o 1 、基本算法 对于决策表中的每一个属性c ；，进行如下过程，直至条件属性集合不再发生变化为 止。如果删除该属性使得p o s c ： c ，) ( 9 ) = p o s 。( q ) ，则说明属性c - 是相对于决策属性d 不必要的，从决策表中删除属性c ；所在的列，并将重复的行进行合并；否则，说明属性 c 。是相对于决策属性d 必要的，不能删除。 2 、基于区分矩阵的算法 区分矩阵由s k o w r o n a 等人于1 9 9 2 年提出的阳1 ，对于决策表，其定义如下： 定义2 7 给定决策表s = ( u ，a ，v ，f ) ，其中a = c ud ，c 是条件属性集，d 是决策 属性集，区分矩阵m d = y7 ，( q ) t r u p i ) y7 。一y t ( q ) r t u n t i ly 7 b e s t = y 7 p r e v r e t u r nr 该算法实际上是一个树结构的组合搜索过程，它在每一层计算决策属性对条件属性 的依赖度，计算过程由上至下进行，生成一个搜索树，生成的搜索树如图3 1 所示： 第3 章模糊粗糙集j 模糊粗糙集属性约简 y7 。( q ) t ；一r u p i ) i + + i fy 7 r u p i ( q ) y 7 b 。 y 7 b 。t = y 7 r u p i ( q ) w = ru p i ) r w u n t i ly 7 b 。t = y7 。， f o ri 一一t o0 r e t u r nt i 该算法生成信息系统的多个属性子集。该算法生成多个属性子集的过程也是一个树 的搜索过程，搜索树如图3 2 所示。 该改进算法在传统的q u i c k r e d u c t 算法生成最后的属性约简进时进行扩展。假设利 用o u i c k r e d u c t 算法搜索属性约简时，搜索到第m 层时的属性子集为( p 。，r p m ) ，在 进行第m + l 层扩展时，扩展出来的属性子集有( p 。，p ：p m ，p 川) ， p ，p 。p 。，p 。+ ：) ( p 。，p ：r ，p 。) 传统的o u i c k r e d u c t 算法在这些所有扩展出来的属性子集中找到依赖 度最大的子集，假设为这个子集为 p 。，p 。r ，p 。) ，再利用( p 。，p 。p m ，p ；) 子集继 续进行m + 2 层的扩展，如果m + 2 层的所有属性子集依赖度不再增大，则( p 。，p 。r ，p ；) 即为找到的最终属性约简，返回( p 。，p 。- - - p 。，p ，) 。而改进后的算法是在m + l 层 ( 1 f 聊) ，对第一个( 1 尼，) ，y i - 为定义于e 上的 模糊向量，则一个模糊分割的示意图见图4 1 所所示。 图4 1 一个模糊分割示意图 t i 。，l ，k ，) 构成d 背景下的一个模糊分割。以下我们计算由第i 个属性a ，引 出的分割信息嫡。在d 的背景下，考虑一个关于分类的清晰划分 p ，n ) ，于是 ( p 厂、d ，nr 、d ) 构成d 的一个模糊分割，函数m 所表示的是模糊集所有隶属度和。记 兀( d ) = m ( d n p ) m ( d ) 厶( d ) = m ( d r 、n ) m ( d ) 分别表示在结点d 中p 类和n 类例子的相对频率。采用这些记号，模糊i d 3 算法描 述如下：给定一个判定叶子的标准6 ( 0 6 1 ) ，考虑结点d ： 步1 ：计算机矗( d ) $ h f n ( d ) ，如果有一超过5 则表示为叶子，转步4 。 步2 ：在结点d 上按照邑= ：缈，e n t r , 计算每一在父辈结点中未曾用过的属性的 分割模糊熵，筛选出最小者对应的属性作为此结点上的扩展属性，记为a ；。 步3 ：根据扩展属性a 。在结点d 上分枝，产生其儿子结点，对d 标上已展开的标志。 步4 ：是否有未展开的非叶子结点? 若有，考虑其中一个未展开的结点，转步l ；否 则，停止，输出结果，结束。 1 r 第4 章基于模糊积分的多模糊决策树分类器融合 下面举例说明模糊决策树的生成： 3 5 节中利用一种改进的模糊粗糙集属性子集算法生成了三个属性子集，这三个属 性子集对应的决策表分别为： 表4 - 1 模糊属性子集 p l ，p 2 ，p 3 ) 的决策信息表 1 9 河北大学t 学硕十学位论文 表4 - 2 模糊属性子集 p 1 ，p 2 ，p 4 的决策信息表 表4 - 3 模糊属性子集 p 2 ，p 3 ，p 4 的决策信息表 1 0 o 6 0 8 0 - 3 0 0 o 4 o 2 o 7 0 0 o 0 o 0 0 o 0 6 0 6 o 6 0 3 0 3 0 4 0 8 0 2 2 0 0 4 0 8 0 1 0 4 0 6 0 2 0 9 0 6 0 o0 70 3 0 80 20 0 0 30 70 0 0 80 20 0 第4 章基丁模糊积分的多模糊决策树分类器融合 表4 - 3 模糊属性子集 p 2 ，p 3 ，p 4 ) 的决策信息表( 续) 对于每一个决策表，都可生成对应的模糊决策树， p 2 ， 、 _ v p 2 1 p ， l p z s p 3 p 1 iq 3 ( 9 1 ) l 彳上一。 p 1 1 p 1 ， | q 】( 9 0 唧l i p 3 i i 3 j i + l - j l i垒。i。：ii)，l l l p 1 ) ，! i i ) ，ii ，。，。，【卜叫 n ，r o s 硎n ，r r n 刁 n r q f l 比i n ，r 0 1 h 。r r l i i n 。r 9 n 掣2 ( 引 图4 2 模糊决策树( 表4 1 决策信息表) 2 1 河北人学j l j 学硕十学位论文 圈匾 图4 - 3 模糊决策树( 表4 - 2 决策信息表) 图4 - 4 模糊决策树( 表4 3 决策信息表) 4 2 模糊测度和模糊积分 模糊测度是对传统测度的推广，用单调性替换了传统测度的可加性，因此模糊测度 又称为非可加测度。模糊测度在数学中的定义如下n 6 3 ： 定义4 4 设x 为非空集合，f 为由x 的子集构成的0 一代数，集函l f ，：f 一 0 ， 满 足下面的四个条件时，称为定义在f 上的模糊测度： 第4 章基丁模糊积分的彩模糊决策树分类器融合 ( 1 ) ( 归零性) l f ，( o ) = 0 ( 2 ) ( 单调性) e f ，a f ，e t a ，则l f ，( e ) l f ，( a ) 3 下连续性 e n ) cf ，e - e zc ，u 删e 一，则，7 ( e n ) 2 t f ，( u n = l 一) ) 上连续性 e ) c ，互de 23 ，i f ，( 巨) ，口己，则1 咿( e ) 2 y ( 口e ) 由模糊测度的定义可以看出，模糊测度只要求单调性，不要求可加性，模糊测度非 可加性体现为次可加性他( 彳ub ) 0 ，l f ，( x 。+ ) ) o 。则参数九的值由下面的方程唯一确定： 1 +