（计算机应用技术专业论文）基于模糊扩张矩阵多类问题的最优特征子集抽取.pdf

摘要 摘要 特征子集选取是一种在模式识别和分类问题中应用非常广泛的有效方法，目的是在 分类和模式识别问题中通过减少特征空间的维数，降低计算复杂度，提高分类识别的计算 速度和分类准确率。最优模糊值特征子集选取o f f s s ( o p t i m a lf u z z y v a l u e df e a t u r e s u b s e ts e l e c t i o n ) 适用于数据库中示例只分为正反两类的特征子集选取问题，而不适用 于多类的特征子集选取闯题。本文采用两种方法对o f f s s 算法进行了改进，使其可以 适用于包含多个类的示例集，即多类最优模糊值特征子集选取m o f f s s ( m u l t i c l a s s o p t i m a lf u z z y 。v a l u e df e a t u r es u b s e ts e l e c t i o n ) ，并且，在选取第一个最优特征的时候引入 了信息熵的方法，降低了算法的计算复杂度。最后，利用选取的特征子集构造模糊决策 树，实验数据说明这两种改进算法是简便可行的。 关键词特征子集选取；模糊值特征；信息熵；相似度；模糊扩张矩阵 a b s t r a c t f e a t u r es u b s e ts e l e c t i o ni so d eo f t h ew i d e l yu s e da n d p r a c t i c a lm e t h o d sf o rc l a s s i f i c a t i o n a n dp a t t e mr e c o g n i t i o n ，w h i c ha i m st or e d u c et h ec o m p u t a t i o n a lc o m p l e x i t y ，i m p r o v et h e s p e e do fc o m p u t a t i o n ，c l a s s i f i c a t i o na c c u r a c yi nc l a s s i f i c a t i o na n dr e c o g n i t i o np r o b l e r ab v r e d u c i n gt h ed i m e n s i o n l i t yo ff e a t u r e s o p t i m a lf u z z y v a l u e df e a t u r es u b s e ts e l e c t i o f o f f s s ) m e t h o dh a sb e e ne f f i c i e n tf o rf e a t u r es u b s e ts e l e c t i o no ft w o c l a s sp r o b l e m ，w h i c hc a nb e c l a s s i f i e di n t o p o s i t i v ea n dn e g a t i v ec l a s s e s h o w e v e r , i ti sn o ts u i t a b l ef o rm u l t i c l a s s p r o b l e m ，i e m u l t i c l a s so p t i m a lf u z z y v a l u e df e a t u r es u b s e ts e l e c t i o n ( m o f f s s ) i nt h i s p a p e r , o f f s sa l g o r i t h mi se x t e n d e dt of o rm u l t i c l a s sp r o b l e mb yt w ot e c h n i q u e sw h e r et h e i n f o r m a t i o n e n t r o p yi s u s e dt or e d u c e c o m p u t a t i o n a lc o m p l e x i t y t h ef e a s i b i l i t ya n d s i m p l i c i t yo ft h et w oi m p r o v e da l g o r i t h m ss r ed e m o n s t r a t e db ya p p l y i n gt h ef e a t u r es u b s e t s e l e c t e dt of u z z yd e e i s i o nt r e ei n d u c t i o n k e y w o r d sf e 邺es u b s e ts e l e c t i o n ；f u z z y 。v a l u e df e a t u r e ；i n f o r m a t i o ne n t r o p y ；f u z z y e x t e n s i o nm a t r i x i i 河北大学 学位论文原创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 入已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作者签名：遂! ：苤日期：丝年生月竺日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 l 、保密口，在年月日解密后适用本授权声明。 2 、不保密压y 。 ( 请在以上相应方格内打“”) 作者签名： 导师签名： 镀d 、莫 日期：型! ! ! 年月竺二日 e l 期：迎年月些二日 第1 章绪论 第1 章绪论 1 1 特征子集选取的研究现状 特征子集选取问题一直是机器学习、模式识别和数据挖掘等领域研究的重要内容 【1 。3 1 。近几年来，随着计算机运算速度的加快和存储能力的增强，使得所能获取的数据 以几何级数增长，并且随着数据量的增大，数据的冗余信息也随之增多，如何从海量的 数据中获取有用的知识，成为上述诸领域急需解决的问题。然而日前的机器学习和数据 挖掘算法处理这种大规模数据还相当低效，有时甚至相当困难，这就需要一个行之有效 的方法来减少不必要的特征和噪音数据，以求减少数据量。因为冗余特征的存在，可能 会降低机器学习，数据挖掘等算法的性能。特征子集选取正是解决这一问题的有效手段 1 4 1 。特征子集选取是指从给定的特征集合中选取一个特征子集，使其能够一致地描述给 定的示例集合。 特征子集选取问题是指从一个大的候选特征集合中，选取一个能够很好一致描述示 例的特征子集。特征子集越小其元素就越具有代表性。从直觉上说，似乎描述示例的 特征越多，对示例的描述就越详细，于是对示例的认识也就越清晰，就越有利于挖掘相 关领域内潜在的特征和规律，但事实并非如此，这是因为i s ： 1 许多机器学习算法都未能很好地解决高维度数据库的学习问题，这些算法随着学习 对象维度的增加，其学习过程的时间和空间开销也急剧增加，甚至最终会严重影响 学习结果的性能6 1 。实际上很多算法都难以处理维度较高的数据库。 2 对一个社会生产或社会生活中实际应用的数据库而言，往往其中的许多特征都是和 最终预测样本的分类值无关的或冗余的，从这个意义上说，系统中过多的特征只会 掩盖数据之间的内在联系，增加了数据挖掘过程的难度和时间，空间的开销。因此， 数据库中过多描述示例的特征必然影响机器学习，数据挖掘的结果和性能a 特征子集选择将有助于解决这一问题，用特征子集来描述样本不但可以缩减学习系 统的规模，而且能够有效地从系统中剔除冗余信息，从而凸显系统中数据之间潜在的相 河北大学工学硕士学位论文 互联系，最终能够提高数据挖掘结果的应用性能和应用精度，所以如何选择最优的特征 子集来一致的描述样本，长期以来是机器学习领域的关键难题之一。 当前特征子集选取问题的研究主要集中在统计方面，例如：p c a ( p r i n c i p l e c o m p o n e n ta n a l y s i s ) 方法【8 l ，l d a ( l i n b a rd i s c r i m i n a n ta n a l y s i s ) ? y 法t g ，这些方法试图 通过特征融合创造新的特征来减少输入数据的维数，主要缺点是构造的新特征没有实际 意义。最近二十年已经有了关联特征子集的选择方法，b l u m ! ”1 给出了相关特征选取的 较好方法。 基于全属性评估标准的o f e i ( o v e r a l lf e a t u r ee v a l u a t i o ni n d e x ) 神经模糊方法 1 1 - 1 4 ， 这种方法把每一类视做一个模糊子集，根据分类信息熵定义一个特征子集的评估标准， 从而得到一个近似解。但是这种方存在只能达到局部最优，并且存在收敛速度较慢的缺 点。 另一种方法是基于神经网络输出敏感性的，它对每个特征使用特征质量评估标准 f q i ( f e a t u r eq u a l i t yi n d e x ) ，根据评估值抽取特征。应用的方法根据评估标准而确定。 z u r a d a 在文献 t s 中，e n g e l b r e c h t 在文献 1 6 】中，使用输出偏导对敏感性进行度量方 法，并利用泰勒近似展开计算其值。文献 1 7 1 8 也都分别提出了不同的评估标准。基 于交互信息的特征抽取m i f s ( m u a l a li n f o r m a t i o n - b a s e df e a t u r es e l e c t o r ) l 。1 是一种被广 泛接受的特征子集选择方法，这种方法主要考虑特征之间的相关性，从而选出高度不相 关的特征。 1 9 6 5 年，la z a d e h 就提出了模糊集8 1 1 理论，对于数据特征值中有一定偏序关系 的语言术语如“大”，“中”，“小”，不能简单的认为是三个无关的符号值，而应作为模 糊符弓值来进行处理，1 9 9 1 年，文献 2 2 1 提出示例学习的扩张矩阵理论，并在随后给出 了基于扩张矩阵的虽优特征子集选取方法o ”。【2 4 将扩张矩阵理论进行了扩展提出了模 糊扩张矩阵的概念，随后2 0 0 3 年，文献 2 5 1 提出了基于模糊扩张矩阵的最优模糊值特征 子集抽取方法，利用示例集在最优特征子集土的重叠度来度量其性能。这种针对模糊值 特征的特征子集选取被认为是特征子集抽取领域的一种重要方法。 1 2 多类最优模糊值特征子集选取的提出和意义 在很多实际的数据库中往往有这样的特征值它没有具体的数值定义，例如人的身体 在很多实际的数据库中往往有这样的特征值它没有具体的数值定义，例如人的身体 第1 章绪论 状况特征值可为“优秀”，“良好”，“较差”等，如果将这些具有一定偏序关系的特征值 视为毫无关联的符号值，就会丢失数据库给出的很多有用信息，因此本文将其视为具有 一定偏序关系的模糊符号值，这样的特征称为模糊值特征。 o f f s s 方法是基于模糊扩张矩阵的最优模糊值特征子集选取方法，基本思想是寻找 最小的可以一致描述示例集的特征子集。从实验数据看出，与其他特征子集选取方法 o f e i ，f q i ，m i f s 方法相比较，利用o f f s s 算法选取的特征子集构造决策树的训练精 度和测试精度都较高，但它也有不足之处，其缺点是 1 ) 它只能处理数据库中只划分为两类的示例集合，但是很多实际数据库中的示例 是包含多个类。 2 ) 当数据库具有海量数据时，需要构造的扩张矩阵较大，计算复杂度较高。 针对以上的问题，本文基于模糊扩张矩阵理论，对o f f s s 启发式算法进行了扩展， 提出两种启发式算法使其可以处理多类问题。当示例集中包含多个类，并且特征值是模 糊符号值的时候，可以利用改进的o f f s s 算法进行特征子集选取。我们称这种对多类 问题的特征子集选取算法为多类最优模糊值特征子集选取m o f f s s ( m u l t i - c l a s so p t i m a l f u z z y - v a l u e df e a t u r es u b s e ts e l e c t i o n ) ，并且，对第一个最优特征子集的选取我们引入 了信息熵 2 6 - 2 7 1 的概念，从而降低了构造模糊扩张矩阵的复杂度。基于以上的改进使得多 类最优模糊值特征子集选取能够处理更多的实际问题。 1 3 主要研究内容 本文的主要研究内容是多类模糊值特征子集选取问题，对o f f s s 方法进行了改进， 使其能够处理包含多个类的示例集，本文的主要研究内容如下： 第1 章主要叙述了国内外在本方向的研究现状，以及本课题研究的目的和意义。提 出了基于模糊扩张矩阵的多类最优特征子集选取启发式算法，使其能够处理数据库中示 例集可分为多类的问题。 第2 章对关于两类的最优模糊值特征子集选取o f f s s 进行了介绍，给出了两个特 征值之间相似度度量的概念及公式，引入模糊扩张矩阵等的定义及构造方法，最后给出 了o f f s s 的启发式算法。 河北大学工学硕士学位论文 第3 章在o f f s s 的基础上给出了m o f f s s 的相关定义，并且提出了两种m o f f s s 启发式算法。并且应用了信息熵的方法来选取第一个最优特征，从而不必构造完全的扩 张矩阵，降低了计算的复杂度。 第4 章应用两种m o f f s s 启发式算法进行实验，对两种方法产生的不同的实验结 果进行了分析，并给出了一些改进方法。 第5 章是本文的工作总结。通过对前几章的分析给出了本文方法的优点以及不足之 处。 第2 章最优模糊值特征子集选取o f f s s 第2 章最优模糊值特征子集选取o f f s s 2 io f f s s 概述 所有的特征子集选择方法都有两个主要的关键点，一是特征子集性能的评估方法， 另一个是根据定义的度量方式最优特征子集的搜索方法。这里围绕这两个关键点对 o f f s s 进行简单的介绍。 2 1 1 特征值的相似性度量 在给出o f f s s 问题的严格定义前，先给出在本文中要用到的相关定义，首先给出 特征值相似性度量的定义。 示例集内的一个示例用特征属性，类属性来描述。例如某天的气象信息作为一个示 例，描述它的特征属性为天气情况、湿度、温度、有无风，特征属性的取值如天气情况 = s u n n y ，o v e r c a s t ，r a i n ) 。类属性取值为天气好，坏，类值一 好，坏) 。因此气象信 息的示例集可以分为好，坏两类。一个示例集如表1 所示， 表t 示例集 由表1 可知，示例集e 共有6 个示例，每个示例e 包含4 个特征属性，1 个类属性， 其中特征属性e 仁 一，b ，c ，d ，每个特征属性可取具有偏序关系的语言术语，例如特征 a 的取值可表示为，a = s m a l l , m i d , b i g 。类属性c 的取值可表示为：c 毛 p o s it i r e , n e g a t i r e ，可以看出示例集e 被分为了两类。特征值的相似性度量如下： 定义l 【2 4 1 ：设为一个给定的论域，x x ，a ，b 为两个模糊符号值，爿( x ) ，b ( x ) 为 河北大学工学硕士学位论文 = j | e e e ! ! ! = ! e _ e ! 目! ! ! 自l e ! 目, m l l 目_ e ! ! ! ! l e ! | ! ! l - e ! ! ! 目_ e ! ! ! 自! l e ! ! ! _ 目! ! ! 目 其隶属度， 彳( z ) ，曰( x ) 【o ，1 ，则爿，口之间的相似性度量公式记为 s m ( a ，b ) = m a x ，。? ( r n i n ( a ( x ) ，曰( x ) ) ) 2 以表1 的示例集为例进行说明，特征属性为f s = a ，b ，c ，d l ，每个特征取3 个具有 一定偏序关系的模糊符号值s m a l l ，m i d , b i g 。他们的隶属函数如图1 所示， 隶 属 度 1o 0 5 00 图1 三个模糊符号值的隶属度 根据定义的相似度度量公式可知s m ( s m a l l , s m a l l ) = s m ( m i d , m i d ) = s m ( b i g , b i g ) = 1 。 s m ( s m a i l , m i d ) 2 s m ( m i d , b i g ) 2 0 2 5 ，s m ( s m a l i , b f g ) = 0 。 在很多参考文献中有关于两个特征值之间的相似性度量方法 2 8 - 3 2 】，本文利用的是定 义l 中给出的相似性度量方法，这种方法较适用于具有一定偏序关系的模糊符号值特征。 2 1 2o f f s s 定义 本节给o f f s s 的严格定义，给定一组示例集合e 包含正负两类示例，正例集记为 尸，负例集记为j v 。示例集的特征集合为f s = ( 一，乃， 。每一个特征月( 1 f 坍) 称为模糊值特征，每一个示例p 都包含m 个特征，记为p = ( v t ，v ? 一，v m ) ，其中旷g ( 蜀) 是示例e 第i 个特征e 的特征值。s = 只，f 、，b 为一个给定的特征子集 ( s f s ，珂s m ) 。对任一正例胁，任负例在某一特征e 的相似度记为 s m = s m ( p 。( f ) ，( 一) ) 。 上一节已经给出了两个属性值之间的相似性度量公式，则一个正例和一个负例的相 似性度量可定义为， 定义2 【州：设s 为一个给定的特征子集( s f s ) ，p e 为一个正例( p 。e p ) ，为一个 负例( ke ) ，在特征子集s 上，胁，的相似性度量为： 6 第2 章最优模糊值特征子集选取o f f s s i i i i i i s m ( p , is ，is ) = e ；s s m ( 见( 巧) ，也( 鼻) ) 其中 表示取最小值，则对整个特征空问来说，s m ( p 。，r l 。) = s m ( p 。l 船，他i f s ) 。 则根据定义l ，定义2 包含正负两类的示例集的重叠度可定义如下， 定义3 ：对给定的组特征子集s ( s f s ) ，正例集p 与负例集的重叠度定义 为： o v ( p ，n 1 s ) = v 凡。只v 。s m ( p , l s ，怫j s ) 其中v 表示取大。o v 表示重叠度。 由表1 可得示例集在特征予集s = - f e a t u r a ，b ) 的重叠度为 o v ( p ，nj 4 ，b ) ) = ( 0 a 1 ) v ( 1 a o 2 5 ) v ( 1 a o 2 5 ) v ( 0 o 2 5 ) v ( o o 2 5 ) v ( 1 0 ) v ( 1 a o ) v ( o a l ) = 0 2 5 从定义2 ，定义3 可以得出，相似度s m ( p 。is ，ks ) 的值随着特征子集s 元素个数 的增多而变小。因此重叠度o v ( e ，n l 固的值也会随着集合s 中元素个数的增多而变小。 对于一个给定的阀值t ( r o v ( p ，ni 朋) ，其中邢是整个特征集合) ，则至少存在一个 特征子集s 满足以下三个条件： 1 ) ssf s ； 2 ) o v ( e ，n i f s ) 五 3 ) l s i 能达到最小； 基于以上定义o f f s s 可描述如下： 定义4 1 2 4 l ：设p 为给定的正例集合，为给定的负例集合，f s 为全特征空间，其特 征值为模糊值。r 是给定的阎值，最优模糊值特征子集选取o f f s s 就是寻找一个特征子 集s + ( s + f s ) ，使得 s + 卜m i n s 。f s isl ：0v ( p ，nis ) t ) 因此最优模糊值特征子集选取，就是对全特征集合的幂集中的每个元素求重叠度， 也就是在全特征集合的每个特征子集上求正例，负例的重叠度，再选取使重叠度最小的 特征子集，这种全空间完全搜索被认为是n p 难问题，并且在 2 4 中已给出证明。所以 2 4 3 提出了o f f s s 的启发式算法，寻求近似于最优解的特征子集。 河北大学工学硕士学位论文 2 2o f f s s 启发式算法 基于上节给出的相似度度量公式，o f f s s 启发式算法以模糊扩张矩阵为工具，进行 特征子集选取，首先，对模糊扩张矩阵进行定义。 22 1 模糊扩张矩阵 模糊扩张矩阵是正负两类示例集内对应特征的模糊特征值进行相似度比较而构成 的，它是对应于 2 1 2 2 】中的清晰特征值构造的扩张矩阵来进行定义的。 定义5 【2 4 】：设丁为给定的阀值，殿为全特征空间，特征子集s c f s ，一个正例 e + = ( v i + ，哆，+ ) p ，一个负例p 一= ( v i 一，v 2 一，v m 一) n ，如果s m ( e + l s ，8 一l s ) t 则 称e + 和e 一在特征子集s 上关于r 一致。如果任意一个e + p 和任意一个e e n 都是r 一 致的则称正例集p ，负例集是，一致的。 从定义4 ，定义5 可以得出正例集只负例集在最优模糊值特征子集s + 上是，一 致的。 定义6 1 2 4 ：正例矿= ( v i + ，v 2 + ，v m + ) 尸对应于负例g 一= ( v l 一，v 2 一，k 一) n 的扩张矩 阵集定义为e 膳0 + ，p 一) = “，r 2 ，t o ) ，其中r i = 删( 口，丐) ， 产1 ，2 ，m 。如果 r ，t ( 1 ，m ) ，那么就称为扩张矩阵的一个i m d e r t 元素。 定义7 【2 4 】：设正例集尸= 口，e ；，p ； ，负例集n = e l - ，p i ，p ： 。一正例 e j ( 1 j k ) 对应负例集n 的扩张矩阵记为e m ( e ；，) ，正例集p 对应的负例集n 的扩 张矩阵记为e v i ( p ，) ，其中 e m ( e j ，n ) = e m ( e ，) e m ( p ，) = l l e m ( e ，) j 。 第2 章最优模糊值特征子集选取o f f s s 根据定义1 ，定义7 ，由表1 的示例集，可得p = - 1 ，2 ) ，= 3 ，4 ，5 ，6 的模糊扩张矩 阵e m ( p ，n ) 如图2 所示， o 0 0 1 0 0 1 o o o 0 0 o o o 1 0 0 1 0 0 0 0 0 1 0 0 0 2 5 o 2 5 o 2 5 o 2 5 0 0 0 o 0 0 1 o o 1 o o 0 0 0 1 0 0 0 1 2 5 o 2 5 o 2 5 0 2 5 1 0 0 图2 模糊扩张矩阵e m ( p ，) 其中根据定义6 ，定义7 ，可得k = 2 ，l = 4 ，m = 4 。 定义8 【2 4 1 ：扩张矩阵的一条路径定义为在扩张矩阵中在每一行选择一个死元素连接 构成的路径称为扩张矩阵的一条路径。 由以上定义可以得到如下定理， 定理1 1 2 4 ：设，为一给定的阀值，特征予集s = e ，e ，兄) ，p 和在特征子集s 上是，一致的，当且仅当正例集尸对应的负例集构造的模糊扩张矩阵中每一行都至少 存在一个u n d e r r 元素。 定理2 【2 4 ：设，是一个给定的阀值，e m ( p ，) 是正例集尸对应的负例集的扩张 矩阵，因此寻找最优特征子集等价于在扩张矩阵e m ( p ，) 寻找一条路径使其包含的列 的个数最少。 定理l ，定理2 在【2 4 】中有详细的证明。因此最优特征子集选取问题等价于在扩张 矩阵e m ( p ，n ) 寻找一条包含列个数最少的路径。从定义8 可得到在扩张矩阵e m ( p ，n ) 的一条路径由e m ( p ，n ) 每一行中的一个u n d e r t 元素相连接构成。因此，一条路径在 e m ( p ，v ) 的同一列中包含的u n d e r a - 元素越多，那么这条路径经过的列就越少。根据这 一思想 2 4 给出了o f f s s 启发式算法。 9 、。l；，。：。11。l 筋筋筋鹏苈肿 o n l o l l n n 河北大学工学硕士学位论文 2 - 2 2o f f s s 启发式算法描述 因为扩张矩阵的每- - y u 对应一个特征，如果一条路径包含的列最少，那么这些列对 应的特征构成最优特征子集。因此寻求最优特征子集就是在e m ( p ，n ) 中搜索一条路径， 该路径包含最少的列。o f f s s 启发式算法选取列的基本思想为：在当前的扩张矩阵中 选取包含死元素最多的一列，将该列和该列中的u n d e r t 元素对应的行删掉，剩余的行构 成新的矩阵，从中再选取u n d e r t 元素最多的列，重复上面的操作，直至矩阵中没有t m d e r t 元素为止，则删掉的列对应的特征子集即为最优特征子集。这是一种贪心算法，因此得 到的最优特征子集是近似最优解。 算法的具体过程如下： 第1 步初始化：f s 为全特征空间，s 为得到最优特征子集，初始时为空s = 声。 p 是一个给定的正例集合，是一个给定的负例集合。e m ( p ，n ) 是对于p 和的模糊 扩张矩阵。 第2 步从当前的扩张矩阵中选取包含u n d e r r 元素最多的列，如果有两列的u n d e r t 元素个数相同，则选取u n d e r t 元素总和值最小的列，该列对应的特征乃，s = sk a f ，) 。 第3 步从朋，胪，n ) 中移除第j 列中u n d e r x 元素对应的行及第- ，列，并且将构成新 的扩张矩阵e m ( p ，n ) 视为当前矩阵。 第4 步如果e m ( p ，n ) 中u n d e r r素个数小于一个给定的阀值，则认为得到的特征 子集s 即为最优特征子集，剩余的示例视为噪声；否则，转到第2 步。 以表l 的示例集为例进行说明。f s = a ，b ，c ，d ，s = 矿。 算法的第1 步，首先构造正例集p ，负例集对应的模糊扩张矩阵e m ( p ，) 如图1 所示；第2 步在e m ( p ，) 中选取含u n d e r v 元素个数最多的列第二列，即特征b ( s - - 协 ) ：第3 步将第二列，及第二列u n d e r v 元素对应的行移除，构成的新扩张矩阵 e m ( 删) 销溅溅：l ；第4 步，从新撇的删( 删腆择含列u n d e r t 元素 个数最多的列，虽然第一列和第二列的u n d e z t 元素个数相同，但是因为第一列的u n d e r t 元素之和小于第二列的u n d e r t 元素元素之和，所以第二次筛选出第一歹“对应的特征a ( 乒 b ，a ) ) 。此时e 膨( p ， r ) 为空，算法结束。则由初始e m ( p ，) 产生的路径如下： 1 0 第2 章最优模糊值特征子集选取o f f s s 02 5 02 5 1 0 0 02 5 10 0 1 0 0 02 5 00 0 实验证明，采用这种方法得到的特征子集构造决筇树，应用于数据库样本的分类时， 其训练精度、测试精度都优于其他的特征子集选取方法，并且其计算复杂度要远远低于 其他方法。 鲁 省药”巧 t 0 l 0 n c = 幔l卷毫塞 婴矽l卜旺c：卜卜 河北大学工学硕士学位论文 第3 章多类最优模糊值特征子集选取m o f f s s 3 1m o f f s s 启发式算法的相关概念 o f f s s 启发式算法采用贪心搜索方法，对于可分为两类的模糊特征值示例集的特征 选取是可行且有效的，本文对该算法进行了扩展使其可以处理多类问题。首先给出 m o f f s s 方法的相关定义，然后包含多个类的示例集对应的扩张矩阵，本文提出了全模 糊扩张矩阵的概念。 3 1 1 多类最优模糊值特征子集选取定义 对于多类最优模糊值特征子集选取，两个特征值之间的相似性度量仍然利用定义l 给出的相似性度量公式进行定义，以下是对于m o f f s s 的相关定义， 给定一组示例集合蜀弘 e l , 口：，p 。 ，e j 是示例集合占中的一个示例( 1 i ”) ，c 为类属性空间，p c l ，c 2 ，c 。) ，第，类示例集合记为g ( 1 ，茎七) ，属于白类的示例 e i 记为e 。胯 n ，乃，晶) 表示全特征空间，每一个特征f l ( 1 s i m ) 称为模糊 值特征属性。每一个示例e 都包含m 个特征，记为p = ( v j v 2 一v 拼) ，其中v 产叩( f f ) 是示 例e 第i 个特征r 的特征值。s = ( 只，e 2 ，只) 为一个给定的特征子集( s 匕f s ，蔓棚) 。 某一特征子集上两个不同类的示例的相似度定义如下： 定义9 ：设s 为一个给定的特征子集( s f s ) ，p ：为属于c i 类的一个示例 ( 口；e ，c j c ) ，p ；为属于q 类的一个示例在特征子集s 上，e ；，e ；( p g ，f - ，) 的 相似性度量为： s m ( e ；is ，p ；ls ) = a s e s m ( ( f ) ，( f ) ) 其中 表示取小，则对整个特征空间来说，s m ( e ；，p ；) = s m ( e ：i 耶，e ；l 胚) 。 与定义3 相对应，对于包含多个类的数据库，其示例集的重叠度可定义如下。 定义1 0 ：对给定的一组特征子集s ( s f s ) ，类属性空间c 内所有类的示例集合 第3 章多类最优模糊值特征子集选取m o f f s s 的重叠度定义为： p 矿瞩，g ，gf s ) c c , c j ；cv e 鲰。；。c js m ( e ：f s ，p ；f s ) 其中，p q , i 工v 表示取大。 与两类的数据库相似，从定义7 可以得出相似度s 肘0 ：is ，e ：i s ) 的值随着特征子集 s l 的增大而变小a 因此重叠度o z ( c , ，c 2 ，qi s ) 的值也会随着 s i 的增大而变小。对 于一个给定的阀值丁( ，o v ( p ，nl 弼) ，其中，s 是全特征空间) ，则至少存在这样一个 特征子集s 满足以下三个条件： 1 ) s f s ； 2 ) o v ( c i ，q ，q f s ) 孔 3 ) l s i 能达到最小； 根据以上定义，m o f f s s 的严格定义如下： 定义1 1 ：设g 为第i 类示例的集合，f s 为全特征空间，其特征值为模糊的。丁是 给定的阀值，多类最优模糊值特征子集选取m o f f s s 就是寻找一个特征子集 s ( s + f s ) ，使得 s = m i n s ：b i s i ：o v ( c i ，c 2 ，c i s ) 丁 在全特征空间的幂集中计算每个特征子集的重叠度，选取使重叠度最小的特征子 集，这种全空间的完全搜索也是：p 难问题，因为“如果问题a 是n p 难的，问题b 能 在多项式时间内约减为问题b ，则问题b 也是n p 难的” 2 4 1 。因为o f f s s 算法是n p 难 的，而m o f f s s 的计算时间复杂度是o f f s s 计算时闻复杂度的生! 篓倍，且都使用 z 枚举的方法进行搜索，所以对全特征空间的幂集进行完全搜索的m o f f s s 方法也是尸 难的。因此本文也以模糊扩张矩阵为工具，对o f f s s 启发式算法进行了改进，提出了 m o f f s s 启发式算法。 3 1 2 全模糊扩张矩阵 为区别定义7 中可划分为两类的示例集对应的模糊扩张矩阵，称包含多个类的示例 集对应的模糊扩张矩阵为全模糊扩张矩阵。定义1 2 给出了关于多类的r 一致的概念 1 3 涧北大学工学硕士学位论文 _ 自! ! ! ! ! 目_ e ! ! ! ! s 目_ | _ ! ! ! _ e e e ! 目_ e ! e ! 自- ! s ! 目i e!i!eb 定义1 2 ：t 为给定的阀值，c 为给定类属性空间，f s 为全特征空间，特征子集s 臌 示例e ；= ( v 厶v ；，吒) c l ，j = ( v f ，皑，v ：) c j ，女0 果s m ( e ；f 5 r ，口；f 5 1 ) - t 则称p ： 和p 。j 在特征子集s 上关于t 一致。如果v p ；和v p ；在特征子集s 上关于丁一致，则称 c ，和q 在特征子集s 上关于丁一致，如果v e ，c j c 在特征子集s 上关于丁一致，则 称c 在特征子集s 上关于r 一致。 定义1 3 ：记e ：和e ：对应的扩张矩阵为e m ( e ；，e ：) = ( 1 ，r 2 ，卅) ，其中 r k = s m ( v ；，v f ) 。如果乓t ( 1 蔓k m ) ，那么丘就称为扩张矩阵的一个u n d e r r 元素。 则根据定义1 2 ，定义1 3 全模糊扩张矩阵定义如下， 定义1 4 ：设示例g ：c i ，对应第类示例集的扩张矩阵记为删( 口；，c ，所有属 于第i 类的示例对应所有属于第歹类的示倒的扩张矩阵记为剧以c f ，c ) ，则类空间c 内 的所有类两两进行相似度度量对应的扩张矩阵记为e m ( c 一，c ：，q ) ，其中 e m ( p ：，c j ) ： e m ( c ，c ) = e m ( c 1 ，c 2 ，g ) = e m ( e ；，c ，) e m ( e ：，c ， e m ( c ，c 2 ) j e m ( c 。，c 3 ) i e m ( c , ，q ) i f e m ( c 女一1 ，c j 。 我们用一个具体的例子来说明全模糊扩张矩阵的构造，首先给出一组包含多个类的 示例集e ，如表2 所示 1 4 第3 章多类最优模糊值特征子集选取m o f f s s 表2 包含多类的示例集 从表可知示例集e ，共有六个示例，被分为3 类，e = ( p ，s ，其中p 包含两个示例 p = l ，2 ，另外p 3 ，4 ) ， b f 5 ，6 ) ，有4 个特征属性f s = f4 ，b ，c ，d ) ，由示例集户，墨 构造的全模糊扩张矩阵e m ( p js d e m ( p ，s ，) = o 0 0 1 0 0 1 o o 0 o o o o o 1 o o 1 o o o 0 0 0 0 0 1 0 0 1 0 0 o o o 根据定义1 2 关于7 i 一致的定义，及定义8 关于扩张矩阵中一条路径的定义，可得 到如下定理： 定理3 ：设丁为一给定的阀值，特征子集s = ( e ，e ：，f ，) ( s f s ，m ) ，c 为 类属性空间，c = ( g ，c 2 ，q ，v c 。= 俄，e ：) ，c 在特征子集s 上是f 一致的，当且仅 当全扩张矩阵中每一行中对应于s 的列至少存在一个u n d e r t 元素。 证明：令v c = p ；，e n ，c j = p ? ，p j ) ( i j ) ，c j 包含n 个示例，e 包含r 个示例 对任意的p ：c i ，e ：c ，在特征子集s 上进行相似度度量产生的扩张矩阵为 加笛筋笛筋舯筋彩哪她瞄幡蟠晒蝴晒筋舢肿筋巧舢 m c ；l o l l m n o 吼良om筋笛苈肿m肿西肿 l c ；m o o m 仉l o m l o 河北大学工学硕士学位论文 e m ( e ：，e ；) = ( ，r 2 ，r d ( i s 矗) ，j g 其中1 g h ，使得名t ，从定义7 可知， s m ( e pls ，e ；is ) = a f 。e s s m ( e 。p ( f t ) ，( f ) ) = a f _ 1 h t ( 1 ) 因此任意的8 ；c t ，j q 在特征子集s 上是t 一致的，所以c l ，g 在特征子集s 上是r 一致的，又因为g ，g 是c 内任意两个类，所以c 内所有元素在特征子集s 上 是7 t 一致的。 同理如果c 内所有类在特征子集s 上是，致的，则v g ，c j c ( f _ ，) 是，一致的， 所以c ，q 内任意两个示例e ；ee ，p ；eq 在特征子集s 上是r 一致的，即 s m ( e ；i s ，i s ) t ，根据( 1 ) 可知，j g ( 1 g a ) ，使得名t ，由定义1 1 可知名属于 e p l ，p ；产生的扩张矩阵删( p ；，e ：) = ( _ ，r d ( i s l = ) ，因此在类属性空间c 内，任意 两类通过相似度度量产生的扩张矩阵每一行至少有一个u n d e r w 元素。 由定理3 可知c 在特征子集s 上是，一致的，当且仅当全扩张矩阵中每一行中对应 于s 的列至少存在一个u n d e r x 元素。因此最优特征子集与全模糊扩张矩阵的关系定义如 下， 定理4 ：t 为给定的阀值，e m ( c l ，c 2 ，q ) 是c 类属性空间内的元素对应的全模糊 扩张矩阵，寻找最优特征子集等价于在模糊扩张矩阵e m ( c 。，c ：，c ；) 中寻找一条包含 最少列的路径。 证明：s 为特征子集8 f s ) ，根据定义9 ，定义l o 可知，如果s 是最优特征子集， 当且仅当，一、c 对应于特征子集s 是t 一致的，二、f s f 能达到最小值。 1 ) 根据定理3 ，c 内所有类在特征子集s 上是r 一致的，当且仅当全扩张矩阵 中每一行中对应于s 的列至少存在一个u n d e r r 元素，将这些u n d e r t 元素相连 构成全模糊扩张矩阵的一条路径。因此c ，c ：，c 。在这条路径上丁一致的。 从而该路径对应特征子集占对c ，c ：，c 。来说是r 一致的 2 )每一条路径中所涉及的每一列对应一个特征，因此所涉及的列的个数就等于 s l ，所以寻求最小的l s i 等价于寻找涉及列最少的一条路径。 1 6 第3 章多类最优模糊值特征子集选取m o f f s s 由1 ) ，2 ) 可知在全特征空间选取能够一致描述示例集的最优特征子集等价于在全 模糊扩张矩阵中寻找一条包含最少列的路径。 证毕。 由定理4 可知，m o f f s s 问题可以转为在e m ( c l ，c2 一，c ) 内寻找一条涉及最少列 的路径，此最少列对应的特征子集即为最优特征子集。 3 2 数据预处理方法 在启发式算法提出之前需要做一些准备工作，也就是数据的预处理工作。在实际数 据库中，示例集的特征属性值可能是离散值( 符号值) ，也可能是连续值( 实值) 。本文 对其处理分别进行了说明。 3 2 1 有偏序关系的离散值数据处理方法 数据库中属性的特征值为符号值的情况下，符号值可能是清晰无任何关系的并且对 应的特征值个数较少，对于这样的符号值，应用的相似性度量公式为， s m ( 郇) = 托髦蛐 ( 2 ) 如果某特征的特征值也为符号型数据，但是它的特征取值个数较多几乎等于示例集 的示例个数，则认为该特征属性对示例的一致性描述是无意义的，我门将其实为冗余特 征。在进行特征子集选取前将这些数据库中的这些特征删除，不予考虑。 这里重点介绍有偏序关系的符号值处理的方法，在示例集中，特征值取值为“大”， “中”，“小”等模糊术语，如果将它视为无任何关系的符号值，利用公式( 2 ) 进行相 似性度量，则s m ( 大，中) = s m ( 大，小) = 龇颤中，小) = o ，这种度量方式在利用扩张矩阵 进行特征子集选取时将会丢失大量的有用信息，因此我们将其视为具有一定偏序关系的 模糊符号值，再利用定义1 的相似性度量公式进行相似性度量。则s m ( 大，中) = o 2 5 ， s m ( 大，小) = 0 ，s m ( v p ，小) = o 2 5 。“大”和“中”的相似度，大于“中”和“小”的 相似度。 河北大学工学硕士学位论文 # 1 0 e ! ! ! _ _ ! ! ! ! 目e ! ! ! 目t ! ! ! e - i e ! ! 目l e ! ! 自s 自! e ! _ e ! ! 自_ 自! ! ! ! | ! ! ! 自_ e ! ! ! _ e ! ! 自_ e 1 3 2 1 连续值数据模糊化方法 在实际数据库中，描述示例集的特征值有很多是连续值的，对于离散值特征处理的 方法的非常简单，在上一节已经给出了处理的方法。这一节主要介绍数据库中含有连续 特征值的数据预处理方法。 针对本文定义1 给出的两个特征值相似性度量方法，将连续值数据模糊化为模糊符 号值，对连续值数据预处理的基本步骤如下， 第一步连续值数据进行模糊化【26 1 。 对一组连续值的数据，首先利用k