（电路与系统专业论文）混合粗糙集理论的非布尔属性集覆盖机[电路与系统专业优秀论文].pdf

摘要 近年来，分类器的研究是机器学习的一个热点问题。大量研究表明如今的分类器大 都分类精确但很难理解。 m a r i om a r c h a n d 和j o h ns h a w e - t a y l o r 在2 0 0 2 年提出了集覆盖机( t h es e tc o v e r i n g m a c h i n e ，s c m ) 理论。它是作为支持向量机的替代算法提出来的，其目的是获得一个具 有良好泛化性能的分类器。s c m 理论提供了控制准确性和复杂度之间恰当的权衡，对于 任意由数据构造的布尔属性的特征集，s c m 均能实现对其目标函数属性的析取或合取。 集覆盖算法表现出和其它学习机器一样的有效性并且在某些方面还优于那些学习机器。 但是由于许多信息系统的属性集合都是非布尔量的，因此这种算法不能作为处理一般的 实际学习任务而直接使用。 本文为了推广集覆盖机的应用，提出了将非布尔属性改为布尔属性的一种方法，并 对集覆盖机算法做了改进。将原本仅能处理布尔属性的集覆盖机算法拓展到了可以处理 条件属性的取值为非布尔值的情况，同时还拓展到可以处理决策属性的取值为非布尔 值，即多类的情况，打破了集覆盖机算法的局限性。通过与粗糙集知识的结合，得出了 更直观的决策规则。通过分析和处理实际数据，获得了较理想的结果，验证了算法的可 行性。 关键词：集覆盖机理论；粗糙集理论；属性约简；规则提取；样本压缩 a b s t r a c t i nr e c e n ty e a r s ，t h es t u d yo fc l a s s i f i e r si sah o t s p o ti nm a c h i n el e a r n i n g v a r i o u ss t u d i e s h a v es h o w nt h a tc l a s s i f i e r sg e n e r a t e db yc u r r e n tm e t h o d s a r ea c c u r a t eb u td i f f i c u l tt o i n t e r p r e t m a r i om a r c h a n da n dj o h ns h a w e t a y l o r p r o p o s e dt h et h e o r yo fs e tc o v e t i n gm a c h i n ei n 2 0 0 2 i tw a sp r o p o s e da sa l la l t e r n a t i v et ot h e s u p p o r tv e c t o rm a c h i n ew h e nt h eo b j e c t i v ei st o o b t a i nas p a r s ec l a s s i f i e rw i t hg o o dg e n e r a l i z a t i o n t h es e t c o v e r i n gm a c h i n ea l l o w sa t r a d e _ o f fb e t w e e na c c u r a c ya n dc o m p l e x i t y , a n di tc a nr e t u r n c o m p a c tc o n j u n c t i o n sa n d d i s j u n c t i o n so fb o o l e a na t t r i b u t e sf o ra n yf e a t u r es e t st h a ta lec o n s 缸1 l c t e d 蠡o mt h e v ，厂( x ，a ，) 矿，。 定义2 2 乜n ( 不可分辨关系) ：设属性集p ，对象x 、y u ，对于每个a p ，当 且仅当厂( x ，a ) = 厂( y ，口) 时，x 和y 是不可分辨的，即： i n d ( 尸) = ( x ，y ) u ，口p ，f ( x ，a ) = f ( y ，a ) ) 。 u i n d ( p ) 定义为与等价关系相关的知识，称为基本知识。为了简洁表示，在这 里将u i n d ( p ) ，记为u 尺，i n d ( p ) 的等价类称为知识尸的基本概念或基本范畴。 定义2 3 蚴( 一致性定义) 若决策表中的两个对象满足如下条件：( 1 ) 条件属性的 取值至少有一个不同；( 2 ) 有相同的条件属性取值时，决策属性的取值是相同的，称作 这两个对象是一致的；否则称作不一致的。若决策表中任何一对对象都是一致的，称该 决策表是一致的；否则称该决策表是不一致的。 2 粗糙集 定义2 4 ( 下近似) ：对信息系统，设x u 是一组对象，对于一个等价关系尺， 即r c 是一组条件属性。x 相对于r 的下近似是： 型x ) = 石u r ： z k x 。 定义2 5 幢玎( 上近似) ：对信息系统s ，x 相对于r 的上近似是： 贰x ) = x u r ：【x rnx 矽 。 定义2 6 瞳日( 正域) ：集合x 相对于r 的正区域就是x 的下近似，即 p o s 露( d ) 2 堡( x ) 。 定义2 7 乜门( 负域) ：集合x 相对于r 的负区域是： n e g r ( x ) 5 u r ( x ) 。 定义2 8 陉妇( 边界域) ：集合x 相对于r 的边界域是： b n d 胄( x ) 2 r ( x ) 一叁( x ) 。 定义2 9 乜妇( 省略和不可省略) ：设一等价关系为属性集合尺c ，属性，r ，当 i n d ( r ) = i n d ( r 一 ，) ) ，称厂为j r 中可省略的，否则r 为r 中不可省略。 定义2 1 0 2 1 1 ( 独立) ：当对于任意r r ，若r 不可省略，则欠为独立的。 定义2 1 1 乜妇( 依赖度) ：设一等价关系为属性集尺c ，对于属性d 以依赖度r r ( d ) 7 东北师范大学硕士学位论文 依赖于s 中4 的子集p ： 尼= ( d ) = lp o s r ( d ) l p o s 爿( d ) l 。 定义2 1 2 陋( 属性重要度) ：设属性a c ，则口的属性重要度定义为： s g f ( a ，c ，d ) 5 r r ( d ) 一r r l 。i ( d ) ， s g f ( a ，c ，d ) 表明从c 中去除a 后对分类决策的影响程度。 定义2 1 3 乜n ( 约简) ：属性子集尺c ，若： ( 1 ) p o s ( d ) = p o s c ( d ) ( 2 ) 对于尺的任意真子集尺有( 1 ) 不真。则尺称为c 的一个约简，记为r e d ( d ) 。 定义2 1 4 乜妇( 核) ：c 中所有不可省略的集合称为c 的核，即： ， c o r e ( d ) = nr e d ( d ) 。 所有约简的交集称为粗糙集的核。核这个概念的用处有两方面：首先它可以作为所 有约简的计算基础，因为核包含在所有的约简之中，并且计算可以直接进行；其次可解 释为在属性约简时它是不能消去的属性特征集合。 ( 三) 粗糙集的规则提取 数据库知识发现的最终任务是从大量数据中找出它们之间的内在联系，最后提取我 们感兴趣的决策规则。规则提取是粗糙集理论的另一个核心内容。从给定的决策表中生 成决策规则是粗糙集的主要应用之一。决策规则应用于对已知对象的分类，或对新对象 的分类进行预测乜引。 知识表达系统可用决策表来表示。决策表的简化就是化简决策表中的条件属性，使 化简后的决策表具有化简前的决策表功能，但是化简后的决策表具有更少的条件属性。 对于决策表而言，属性值的约简就是决策规则的约简。决策规则的约简是利用决策逻辑 消去每个决策规则的不必要条件，它不是整体上约简属性，而是针对每个决策规则，去 掉表达该规则时的冗余属性值，即要计算每条决策规则的核与约简。 化简决策规则中条件属性的冗余值，必须先计算决策规则中条件属性的核值，然后 再计算属性值的简化啪1 。 令u d = y 。，y ：，y 。) 表示u 上对象集合的决策类集，对每一个决策等价类， 定义决策规则类d r c ( d e c i s i o nr u l ec l a s s ) 为( d 为决策属性集，c 为条件属性集) d r c ( y ) = d x ：d e s ( 【x 】e ) jd e s ( x 】d ) i 工u 且m o y ，vy u d 各决策类的最小决策算法则通过删除决策规则类中决策规则的冗余属性值及冗余 r 东北师范大学硕士学位论文 规则来实现。 用c o r e ( y ) ，vy u d 表示决策类y 的核值属性集，c o r e ( d x ) 表示决策规则 d 。的核值属性集，则有 c o r e ( y ) c ，c o r e ( d x ) e 且c o r e ( y ) = u c o r e ( d 。) 以e d r c ( y ) 对于1 ，f ，口f ，尸= al ，a2 ，口( 力) ) ，称形如( 口1 ，1 ，1 ) 人( 口2 ，v 2 ) 人，人( 口( 刀) ，1 ，( 刀) ) 的公式为尸基本公式，简称尸公式。 任何一个蕴涵式矽_ 沙称为一个决策规则。办y 分别称为妒- - ) 吵的前件和后件。 决策规则是模式的一种特殊类型，反映了条件属性集和决策属性之间的关系。 ( 四) 结论 近年来粗糙集理论迅速发展，它在许多方面有着不可替代的优越性和广泛的应用。 粗糙集理论不仅思想新颖、方法独特，提供了一套严格处理知识发现中基本分类问题的 数学方法，而且不需要先验知识，即可发现数据中蕴涵的知识模式，在保持分类能力的 前提下，通过对属性和属性值进行知识约简，从而导出其决策规则，且获取的规则易于 理解。 9 东北师范大学硕士学位论文 ( 一) 集合覆盖问题 三、集覆盖机理论 集合问题的数学描述如下：( x ，f ) 是由一个有限集x 及x 的一个子集族f 组 成。子集族，覆盖了有限集x ，即x 中每一元素至少属于f 中的一个子集，即x = u s 。 延f 对于f 的一个子集c f ，若c 中的x 的子集覆盖了x ，且px ：u s ，则称c 覆盖了x 。 踺c 集合覆盖问题就是要找出，中覆盖x 的最小子集c + ，使得：c = m i n lcc f 且c 覆盖了xl 。集合覆盖问题是用集合s 的某些子集来表示的，这些子集彼此之间并无联 系，仅需要研究集合s 中哪些子集会以较高的概率被选作最优解的子集。 简单描述一下最小集合覆盖问题的定义嘞1 。 最小集合覆盖问题：s 是一个集合，s 。，s ：，s 。是s 的子集，且构成s 的覆 盖，即【j s ，= s ，求最小的覆盖。 1 一 f = l 由定义可以知道求最小集合覆盖的前提是集合的所有子集能构成集合的覆盖。所 以，在这样的前提下，最小集合覆盖是一定存在的。反之，如果所有的子集都不能够覆 盖，那显然也就不存在最小的集合覆盖了。 集合覆盖问题是n p h a r d 问题中应用面最广的问题之一，它在模式识别、机器学习 等领域中具有重要的应用。很多科学家对之已经做出了深刻的研究，其理论发展已经比 较成熟h 羽m 儿5 3 1 。n p 完全问题的求解一般存在两个主要障碍：一是具有很高的计算复杂度， 一般在多项式时问内不能求解；另一个是容易受局部最优解的影响，需要采用全局搜索 技术。 如果粗糙集属性约简能被化简成集合覆盖问题，那么解决和分析集合覆盖问题的思 想方法都可以用到解决粗糙集的属性约简上面来。已有文献畸朝在粗糙集的属性约简和集 合覆盖问题之间找出了一种对应关系，通过构造信息系统的相关矩阵将粗糙集的属性约 简问题与集合覆盖问题联系起来，证明了求粗糙集最小属性约简等价于求最小覆盖问 题，也就是说所求的集覆盖应该等价于粗糙集的核。从而将粗糙集的属性约简问题简化 为集合覆盖问题。这样就可以将解决集合覆盖问题的算法和思想应用到解决粗糙集属性 约简的问题中，可以进一步地理解属性约简的本质。 l o 东北师范大学硕士学位论文 ( 二) 集覆盖机理论 1 集覆盖机理论的提出 以b e l l 实验室v a p n i k 教授为首的研究小组从6 0 年代开始致力于小样本情况下的机 器学习研究工作，提出了统计学习理论，并在此基础上于9 0 年代初提出了支持向量机这 一通用学习方法口。 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 算法是基于结构风险最小化准则 ( s t r u c t u r a lr i s km i n i m i z a t i o n ，s r m ) 实现的模式分类方法。它将最大分界面分类 器思想和基于核的方法结合在一起，表现出了很好的泛化能力。支持向量机算法利用在 样本空间或者特征空间构造出最优超平面，使得超平面与不同类样本集之间的距离最 大，从而达到分类的能力。 支持向量机以其结构简单、具有全局最优性和较好的泛化能力等优点成为机器学习 领域最有影响的成果之一。从总体上讲，统计学习理论和支持向量机研究的是如何根据 有限学习样本，确定分类面，使在对未知样本进行估计时，期望风险最小。 但是，对于一个给定的属性集合，可能存在比最大边缘方法提供更好泛化能力的方 案。特别是当要学习的函数恰好仅仅依赖于一个给定的很大的属性集合的一个非常小的 子集合的时候，那么构建一个只依赖属性集合的一个小子集的简单决策函数要比找出所 有属性集合的最大边缘超平面要好得多。 m a r i om a r c h a n d 和j o h ns h a w e - t a y l o r 在2 0 0 2 年提出了一种替代支持向量机的新 的算法。他们拓展了经典的v a l i a n t 和h a u s s l e r 算法，提出了一种更适用于实际情况 的学习机器，被称为集覆盖机理论( t h es e tc o v e r i n gm a c h i n e ，s c m ) 。其基本思想是 在给定的特征空间内，构造出少数相关属性的一个简单函数，找出这些相关属性的合取 或析取来对整体数据进行分类墙1 。 s 理论是要对所有属性找出具有最大边缘的分类超平面，而s c m 是要找出最少属 性的合取或析取，这些属性可以存在一些小的训练错误。这两种机器学习算法在从训练 数据中获得信息的方法上有根本的不同。此外，在某些自然数据集中，在具有大致相同 的泛化误差的情况下，s c m 能够获得比s v m 更高的稀疏度。 对于一个给定的属性集合，v a li a n t 在1 9 8 4 年提出了一种非常简单的仅从正样本( 负 样本) 来构造关联的学习规则口别。然而得到的函数可能含有大量的属性，如果可以使属 性的数目显著减少的话，它的泛化能力将得到很大的提高。不久，h a u s s l e r 在1 9 8 8 年指 出相互独立的属性的训练问题可以等效为最小集合覆盖问题。用集覆盖贪婪算法来减少 v a l i a n t 算法中没有用到的样本的数目，这样就构成了这种找出相关属性合取或析取的 两步算法。 两步算法指的是v a l i a n t 算法和h a u s s l e r 算法，即v h 算法。该算法是研究基于 布尔属性值的目标函数属性的析取或合取的。对于任意布尔属性的特征集，s c m 算法均 能构造出一个合取或析取的函数。同时，算法还提供了一些模式选择参数来控制训练精 1 1 东北师范大学硕士学位论文 度和合取或析取大小之间的权衡。下面分别介绍v a l i a n t 算法、h a u s s l e r 算法以及s c m 算法。 2 集覆盖机基本理论 令x 表示输入空间x 的任意一个n 维向量。输入空间x 是空间r ”的任意子集，定 义一个布尔值的函数，令其能把输入空间x 映射到 0 ，1 ) 上。 集覆盖机在给定任意一个布尔属性赡( 石) 的集合日= 名( x ) i m ：。时，将返回一个日的 子集r 。给定子集r 和任意一个输入向量z ，s c m 的输出函数f ( x ) 定义如下： 巾卜v i rh i ( ，x ，； 誓警 定义3 1 - 若函数( 或属性) 能正确分类一个样本时，称这个函数( 或属性) 与该 样本一致。同理，若函数( 或属性) 能正确分类一个集合中的所有样本时，则称这个函 数( 或属性) 与该集合一致。 下面以合取情况为例介绍v a l i a n t 算法和h a u s s l e r 算法，析取情况可对称得到。 v a l i a n t 算法： 给定一个含有m 个训练样本的集合和一个属性集合日，找出与正训练样本集合一致 的属性集合cs 日。 集合c 具有下列性质：只要存在c ，使得所有人毛。曩( x ) - 与m 个训练样本一致， 则有 妊c 红( x ) 与所有聊个训练样本一致。若每个属性吩( x ) c 都与所有正训练样本一 致，则a 程c 向( x ) 就与所有的正训练样本一致。而且给定任意一个负训练样本x ，由于 c ，因此若人拓红( x ) 输出为0 ，则a 拓c 红( x ) 输出也为0 。这样人超c 忽( x ) 就与所有的负 训练样本一致。 但是这样的话i c | 可能会非常大，只有分类器包含的相关属性数目很少时，其泛化 误差才能很小。因此，为了减少相关属性的数目，首先，注意到c 中的每个属性都与所 有正训练样本和一部分负训练样本一致。 假设存在c ，使得 起。如( x ) x c 所有m 个训练样本一致，并令q 代表与属性吃一 致的所有负样本集。由于c 红( x ) 与所有负训练样本的集合一致，则u 拒c q 就等价于 1 2 东北师范大学硕士学位论文 集合。那么就说u 拒c q 就是集合的一个覆盖。因此，在c 中找出合取与n 一致的 最小的属性子集的问题，就等价于找出q 最小的合集y 的问题( u 越y q 是的一个覆 盖) ，这就是前面提到的著名的最小集合覆盖问题，又叫做n p 完全问题( g a r e ya n d j o h n s o n ，1 9 7 9 ) 。 找出最小的集合覆盖是很困难的，幸好著名的集覆盖贪婪算法有一个最坏情况界 限。如果z 表示能够覆盖的集合q 的最小个数，那么集覆盖贪婪算法将总能找到一 个集合个数最多为z 1 n ( i n i ) 的覆盖( c h v a t a l ，1 9 7 9 ，k e a m sa n dv a z i r a n i ，1 9 9 4 ) 。注意 这个界限与集合c 中的子集中属性的个数没有关系，只和l i 的对数有关。因此用这个 算法能够在集合c 中找到覆盖集合的最小数目的属性集。( 这就是集覆盖机名字的由 来) 。 集覆盖贪婪算法是一个非常简单的算法：首先选出能覆盖中最多元素的集合q ， 从n 中和q ，中移除q 中的元素，然后重复这个过程，找到基数最大的集合q h ，更新 和q ，直到n 中没有元素为止。 这就是v a l i a n t 算法，这个算法被h a u s s l e r 改进了。下面介绍h a u s s l e r 算法。 h a u s s l e r 算法： 给定训练样本集合和属性集合日，令c 为v a l i a n t 算法得到的属性集合日的子集。 用集覆盖贪婪算法找到覆盖所有负训练样本的集合c 的一个小子集r 。 只要在原始属性集合日中存在小的属性集合( 其合取与所有训练样本一致) ， 起r 啊( x ) 就与所有的训练样本一致并且包含一个小的属性集合。然而只有当属性是来自 训练数据且集合中不包含任意一对具有相同输入向量却有相反决策属性的训练样本时， 上述结论才成立。 在这些算法中做一点点的改动就可以构造出析取的情况。在v a l i a n t 算法中，只找 出了日的所有属性中与负训练样本一致的属性的集合c ，在h a u s s l e r 算法中，利用集 覆盖贪婪算法找出了覆盖所有正训练样本的属性集合c 的一个小子集r 。用上面提过的 方法可以看出只要在原始属性集合日中存在小的属性集合( 其析取与所有训练样本一 致) ，v 诞r 忍( z ) 就与所有训练样本一致。 上述v - h 两步算法并不是没有缺点的，它没有给使用者提供控制训练数据准确性和 分类器复杂度之间的权衡。事实上在处理实际问题时，在训练样本集合上产生一些错误 的较少属性的合取，比在训练数据上产生的误差为0 却有很多属性的合取泛化能力更好 【8 1 3 东北师范大学硕士学位论文 在s c m 算法中增加这种灵活性的方法是：当训练样本集合中还有少数几个样本将被 覆盖时就停止集覆盖贪婪算法。在这种情况下，s c m 将包含较少的属性并在那些尚未被 覆盖的样本上产生误差。但是这些没有被覆盖的训练样本都属于同一类：对于负样本是 合取，对于正样本是析取。一般来讲，非对称的缺失函数确实需要在两类的训练样本上 都产生误差。因此仅仅提前停止集覆盖贪婪算法是不够的，还需考虑那些v a l i a n t 算法 中未选的属性。 下面介绍集覆盖机的算法，它对合取和析取都是有效的。 s e m i 算法： 定义3 2 ：如果s c m 在构造一个合取，令尸代表正训练样本集合，代表负训练 样本集合；如果s c m 在构造一个析取，令p 代表负训练样本集合，代表正训练样本 集合。相似的，合取中的正训练样本( 或析取中的负训练样本) 叫做尸样本，而合取中 的负训练样本( 或析取中的正训练样本) 叫做样本。 因此，在两种情况下，尸都表示与v a l i a n t 算法选取的属性一致的训练样本集合的 子集；n 表示需要被集覆盖贪婪算法覆盖的样本的集合。 如果某个属性能够多覆盖几个样本的话，则允许它在p 样本上产生一些错误。因 此，对于属性h ，令q 。表示集合中的属性h 所覆盖( t g 就是正确分类) 的样本的集合； 尺。表示集合尸中属性h 分类有错误的样本的集合。可以用某个确定的惩罚参数p 来降低 集合r 。中每个样本对属性h 的有用度。定义属性h 的有用度u 。为属性h 所覆盖的集合 中样本的个数lq hl 减去被属性h 错误分类的集合p 中样本的个数lr 。i 与某个惩罚参 数p 的乘积： f i e f u 。= lq 。i _ pi 风i s c m 算法修改如下： 对比v a l i a n t 算法，需要考虑初始集合日中的所有属性，包括在集合尸上产生错误 的属性。每个属性办日都覆盖一个的子集绕，且在p 的子集r 。上产生错误。将集 覆盖贪婪算法修改如下：不再使用能覆盖中最多样本的属性，而是用具有最高有用度 u 。的属性。把q h 中的元素从和g 中移出，并把r 。中的元素从毽中移出。可以看出 更新每个集合r 。是因为如果属性h 已在集合p 中某个样本上生成错误，那么若属性g 同 样在该样本上产生错误将不会再增加额外的学习错误。重复上述过程，继续找出拥有最 大的有用度的属性j i l 并更新集合、q 、色直到n 中剩有较少元素为止( 在较早停止 的情况下) 。 1 4 东北师范大学硕士学位论文 惩罚参数p 和早停点s 是提供给使用者用来控制训练精度和函数规模之间适当权衡 能力的模式选择参数。它们的值可以由k 重交叉验证法( k f o l dc r o s s v a l i d a t i o n ) 或计算泛化误差的界限来确定。因此，提供这个复杂度一精确度之间的权衡并且允许使 用任何形式的布尔值属性包括那些由数据构造的属性就能使算法得到更好的泛化能力。 当p 和s 取有限值，且属性集合包含输入特征和它们的相反值的集合时，覆盖机的算法 就简化成了两步算法叫a l i a n t 算法和h a u s s l e r 算法。 3 s c m 算法 s c m ( s ，t ，p ，s ，h ) 输入：训练样本集合s ，计算类型t ( 合取或析取) ，惩罚参数p ，早停点j ，布尔值属 性集合日= 忽( x ) ) 2 输出：集合r h 的合取或析取函数( x ) 初值：r = 矽 1 、若t = 合取，则令p 为正训练样本的集合，为负训练样本的集合；否则，是正 训练样本集合，p 是负训练样本集合。 2 、对于每个属性忍h ，令q 为属性吩