（应用数学专业论文）基于粗糙集与相关分析的属性约简.pdf

宁夏大学硕士学位论文白江：基子粗裢集与相关分析的属性约简 i 摘要 经典粗糙集理论以等价关系为基础，能有效地处理了名义数据的情况然而，实际问题中往往 会出现一些有序问题，如果忽略了这种偏序关系，就会损失状态问顺序给我们提供的有用信息 为此，g r e c o 等人提出了基于优势关系的粗糙集理论来处理有序数据的情况属性约简是粗糙集 理论的核心问题之一，也是n p 难问题然而，粗糙集理论的一个明显缺陷就是缺乏统计依据其 分析结果如果没有统计检验作保证的话，就不能认为该分析反映了总体的信息因此，我们基于 一些统计量给出了属性约简的新方法主要工作如下； 第一，引入优势关系下的粗糙集理论与方法，给出了有序信息系统、有序决策表在优势关系 下的约简概念，以及基于粗糙集理论的排序方法 第二，在粗糙集综合排序的基础上，引入非参数统计中用于检验有序尺度变量之间相关性的 秩相关系数，分别定义了属性集之间的s p e a r m a n 、k e n d a l l 秩相关系数以及k e n d a l l 协和系数， 并基于这些度量分别给出了有序信息系统与有序决策表的属性约简新方法通过数值例子说明了 该方法的可行性与有效性 第三，本文讨论了一类复杂决策表的属性约简问题首先定义了属性集之间的g a m m a 系数， 并基于此度量给出了有序决策表的约简方法，证明了g a m m a 约简与粗糙集约简之间有着密切的 联系其次，以决策表相应的列联表为基础，定义了度量，用此统计量度量了二元名义属性与 有序属性之间的相关性最后，本文采用属性分割方法，将复杂决策表分割，然后再利用这两个度 量对其分别进行约简，最终得到复杂决策表的约简结果 本文的研究成果发展了有序信息系统与有序决策表的约简方法，使得约简结果具备了统计意 义，并且与粗糙集约简之间建立了联系，是对粗糙集约简方法的一种统计拓展，同时也为其提供 了一定的统计依据 关键词：粗糙集；有序属性；优势关系；属性约简；秩相关系数；g a m m a 系数 宁夏大学硕士学位论文白江：基于褪糙集与相关分析的属性约简 a b s tr a c t t h ec l a s s i cr o u g hs e tt h e o r yw h i c hi sb a s e do ni n d i s c e r n i b i l i t yr e l a t i o nc o u l dd e a lw i t hn o m i n a l d a t ae f f e c t i v e l y h o w e v e r ，i nm a n yr e a ls i t u a t i o n s ，w eo f t e nf a c ew i t ht h ep r o b l e m st h a tt h eo r d e r i n g p r o p e r t i e so ft h ec o n s i d e r e da t t r i b u t e sp l a yac r u c i a lr o l e i fw ei g n o r et h e s eo r d e r i n gp r o p e r t i e s ，t h e u s e f u li n f o r m a t i o np r o v i d e db yt h e mw i l lb el o s t t od e a lw i t ht h i sp r o b l e m ，g r e c oe ta 1 p r o p o s e d t h ed o m i n a n c e - b a s e dr o u g hs e ta p p r o a c h a t t r i b u t er e d u c t i o ni so n eo ft h ec o r ep r o b l e mo ft h er o u g h s e tt h e o r y , i sa l s oa nn p h a r dp r o b l e m b u t t h e r ei sa no b v i o u sd i s a d v a n t a g ei nt h er o u g hs e tt h e o r y t h a ti sl a c ko fs t a t i s t i c a le v i d e n c e t h e r ei sn os t a t i s t i c a lt e s tt oc e r t i f y t h er e s u l t so b t a i n e df r o m t h e s es a m p l e sc a n tb eg e n e r a l i z e dt ot h ep o p u l a t i o n t h e r e f o r e ，w ep r e s e n ts o m en e wa t t r i b u t e r e d u c t i o nm e t h o d sb a s e do ns o m es t a t i s t i c s t h em a i nw o r ko ft h i st h e s i si s 蠲f o l l o w s f i r s t l y , t h er o u g hs e tt h e o r ya n dm e t h o db a s e do nd o m i n a n c er e l a t i o ni si n t r o d u c e d t h ed e f - i n i t i o n so fa t t r i b u t er e d u c t i o nf o ro r d e r e di n f o r m a t i o ns y s t e ma n do r d e r e dd e c i s i o nt a b l e sa r eg i v e n ， a n dt h es o r t i n gm e t h o db yr o u g hs e tt h e o r yi sp r e s e n t e d s e c o n d l y ，b a s e do nr o u g hs e ts o r t i n gm e t h o d ，r a n kc o r r e l a t i o nc o e f f i c i e n t s ，w h i c ha r eu s e dt o t e s t i n gc o r r e l a t i v i t yb e t w e e no r d i n a lv a r i a b l e si nn o n p a r a m e t r i cs t a t i s t i c s ，a r eb r o u g h ti n w er e d e f i n e s p e a r m a n ，k e n d a l lr a n kc o r r e l a t i o nc o e f f i c i e n ta n dk e n d a l lc o e f f i c i e n to fc o n c o r d a n c eb e t w e e na t - t r i b u t es e t sr e s p e c t i v e l y b a s e do nt h e s em e a s u r e s ，s o m en e wa t t r i b u t er e d u c t i o nm e t h o d sf o ro r d e r e d i n f o r m a t i o ns y s t e m sa n do r d e r e dd e c i s i o nt a b l e sa r ep r o p o s e d t h en u m e r i c a le x p e r i m e n t ss h o wt h a t o u ra p p r o a c hi sf e a s i b l ea n de f f i c i e n t f i n a l l y , w ed i s c u s st h ea t t r i b u t er e d u c t i o nf o rc o m p l e xd e c i s i o nt a b l e s w ed e f i n eg a m m a c o - e f f i c i e n tb e t w e e na t t r i b u t es e t sf i r s t l y b a s e do nt h i sm e a s u r e ，a n o t h e rn e wm e t h o do fa t t r i b u t e r e d u c t i o nf o ro r d e r e dd e c i s i o nt a b l e si sp r o p o s e d i tc a nb ep r o v e dt h a tt h e r ei sc l o s er e l a t i o n s h i p b e t w e e ng a m m ar e d u c t i o na n dr o u g hs e tr e d u c t i o n s e c o n d l y ，t h ed e f i n i t i o no fd e l t am e a s u r ei sg i v e n b a s e do nt h ec o n t i n g e n c yt a b l e s t h ec o r r e l a t i v i t yb e t w e e nb i n a r yu n o r d e r e da t t r i b u t ea n do r d e r e d a t t r i b u t ei sm e a s u r e db yt h es t a t i s t i c a lm e a s u r e f i n a l l y , t h ea t t r i b u t es u b d i v i s i o nm e t h o di su s e dt o c u ta p a r tt h ec o m p l e xd e c i s i o nt a b l e s ，t h e ne a c ho n ec a nb es e p a r a t e l yr e d u c e db yt h e s et w om e a s u r e s a sar e s u l t ，w eg e tt h er e d u c t i o no ft h ec o m p l e xd e c i s i o nt a b l e s t h er e s e a r c hr e s u l t so b t a i n e di nt h i st h e s i sd e v e l o pa t t r i b u t er e d u c t i o no fo r d e r e di n f o r m a t i o n s y s t e m sa n do r d e r e dd e c i s i o nt a b l e s t h e ym a k er e d u c t i o nr e s u l t sh a v es t a t i s t i c a ls i g n i f i c a n c e ，a n d s e tu pc o n n e c t i o n sw i t hr o u g hs e tr e d u c t i o n ，t h em e t h o dw ep r o p o s e dc a nb ev i e w e da sas t a t i s t i c a l e x t e n s i o no fr o u g hs e tr e d u c t i o nm e t h o d ，a n dt h e yp r o v i d es o m es t a t i s t i c a le v i d e n c ef o rr o u g hs e t a p p r o a c h k e yw o r d s ：r o u g hs e t ；o r d i n a la t t r i b u t e ；d o m i n a n c er e l a t i o n ；a t t r i b u t er e d u c t i o n ；r a n kc o r r e l a t i o nc o e f f i c i e n t ；g a r o m ac o e f f b c i e n t 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 研究生签名： 白江 时间：0 汐口7 年夕月0 2 口日 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交论 文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保 存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位论文的 全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 导师签名： 白止 苏2 主和瓢j 和 时间：。z 卯夕年岁月知日 时间：莎畛如钿日 f ：壑奎墅些兰缝叁笪坠垄墅丝叁壁鳖型丝量氅堕 第一章引言 1 1 研究目的及意义 随着信息技术的迅速发展，各个领域的信息与数据急剧增加，并且由于人类的参与使得数据 与信息中的不确定性更加显著，信息与数据的关系更加复杂如何从大量的、杂乱无章的、强干扰 的数据中挖掘出潜在的、新颖的、正确的、有用利用价值的知识成为数据库知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，简称k d d ) 研究领域的一个重要课题传统的统计技术及数据管理工具不 再适用于分析这样的海量数据，人们需要自动化程度更高、效率更高的数据处理方法来处理 信息系统是一个具有对象和属性关系的数据库，这种数据库通过数据隐含着知识的对象与属 性之间的关系，最终表达的知识模式是用属性来表达的，它有明确的直观意义，因此是可以理解 的由于数据表的规模性和多样性，知识表达的对象与属性的关系不是能直接观测到的，必须依 赖于一定的数学方法与计算工具，找到存在于庞大数据库中的潜在规律 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的一种处理不精确、不确定与不完全数据 的新的数学理论【l ，2 1 ，它以等价分类为基础定义了不确定性，发现信息系统中的隐含知识，进行规 则提取，已在机器学习与知识发现、数据挖掘、决策支持与分析等领域中得到了广泛的应用它的 提出为k d d 提供了一种新的方法和工具 属性约简是粗糙集理论的核心问题之一，也是n p 难问题信息系统的属性对于描述知识或 者制定决策不是同等重要的，有些甚至是冗余的冗余属性的存在，一方面是对资源的浪费；另一 方面，也会阻碍人们做出简洁的分类或决策，甚至会影响人们做出正确的判断所谓属性约简就 是根据某种特定标准选择一个或多个属性子集的过程，这一过程要求所选属性子集能够在某种意 义上代表原来的所有属性，同时尽量使数据得到最简描述，从而使数据的分析和知识发现更为有 效、迅速、简洁它不仅使概念和规则表述得清晰简明，而且使人们对概念与规则有了本质性的认 识特别对于有序属性的约简，将是本文要讨论的主要内容 然而，粗糙集方法的一个明显缺陷就是缺乏统计依据【3 】 因此在粗糙集理论中引入统计学方法 势在必行，这正在成为国内外学者的一个研究热点j a nz y t k o w 指出粗糙集中的大批量规则提取 不是基于统计证据，而是利用一些简单的指标，如条件概率和条件概率函数【4 】 他的研究指明了在 粗糙集理论中引入统计的必要性魏玲等在文献【5 】中指出，决策表中的对象是作为研究总体的样 本来进行分析的，其分析结果如果没有统计检验作保证的话，就不能认为该分析反映了总体的信 息因此，该文提出了用统计检验进行决策表分析的方法，并以决策表的相应列联表为基础，从统 计学角度给出了条件属性冗余与否的假设检验方法，基于列联表的一级规则获取方法，以及条件属 性对决策属性的相关性度量但该文单纯分析每个条件属性与决策属性的关系其局限性太大找 到合适的方法分析属性的综合作用对决策属性的影响，将是非常有意义的工作近年来，将统计方 法融入到粗糙集中去正在成为一种新的研究趋势，现已出现将关联信息、列联表、卡方统计量、统 计模型、贝叶斯理论、，多维标度等统计方法与粗糙集有机结合的众多文献，见f 6 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 变量间的相关性反映了变量之间的非线性关系，而信息系统的属性之间大多是非线性关系 因此，本文将粗糙集方法与非参数统计方法有机结合，将s p e a r m a n ，k e n d a l l 秩相关系数以及 ：；墨垄堂壁兰丝坚坠型些叁墅堡型丝垦丝堕 g a m m a 系数等分别用作属性问的相关性度量，并基于这些度量分别给出了有序信息系统、有序决 策表、以及复杂信息系统的属性约简新方法，通过数值例子说明了这些方法是有效可行的本文 的研究成果发展了有序信息系统的属性约简方法，使得约简结果具备了统计意义，是对粗糙集约 简方法的一种统计推广，同时也为其提供了一定的统计依据 1 2 研究现状及分析 1 2 1 粗糙集理论的研究现状 由于最初关于粗糙集理论的研究大部分是用波兰语发表的，因此当时并没有引起国际计算机 界和数学界的重视，研究地域也仅局限在东欧一些国家，直到2 0 世纪8 0 年代末才逐渐引起各国 学者的注意近年来，由于该理论在机器学习与知识发现、模式识别、数据挖掘、决策支持与分析 等方面的广泛应用，研究才逐渐趋热1 9 9 2 年，第一界关于粗糙集理论的国际学术会议在波兰 召开1 9 9 5 年，a c mc o m m u n i c a t i o n 将其列为新浮现的计算机科学研究课题 1 9 9 8 年， i n f o r m a t i o ns c i e n c e 还为粗糙集理论的研究出了一期专辑目前粗糙集理论已成为信息科学最为 活跃的研究领域之一 目前，对粗糙集理论研究集中在其数学性质、粗糙集拓广、粗糙集理论中的度量、与其他不确 定方法的关系和互补，以及有效算法等方面 在粗糙集理论数学性质方面的研究，主要讨论粗糙集的代数结构与拓扑结构，以及粗糙集的 收敛性等问题纯粹的数学理论与粗糙集理论的结合使得一些新的数学概念也不断出现，比如粗 糙理想f 1 3 】、粗糙半群【1 3 】等随着粗糙结构、代数结构、拓扑结构、序结构等各种结构的不断整 合，必将不断涌现出新的富有生机的数学分支 在粗糙集理论与其他处理模糊性或不确定性方法的理论研究中，主要集中在它与概率统计、 模糊数学、d _ s 证据理论和信息论的相互渗透与补充 在粗糙集推广方面的研究主要涉及变精度粗糙集模型1 1 4 1 、模糊粗糙集模型 1 5 1 和粗糙模糊集 模型【1 6 1 、基于相似关系的粗集模型【1 7 1 、基于一般关系的粗糙集模型【l 剐、概率粗糙集模型【1 9 1 、 贝叶斯粗糙集模型 2 0 】、基于优势关系的粗糙集模型【2 1 1 、不完全信息系统下的粗糙集模型【2 2 1 ，以 及对连续属性的离散化模型1 2 3 】等 在粗糙集有效算法研究方面，主要集中在导出规则的增量式算法、约简的启发式算法、粗糙 集的基本并行算法、以及与粗糙集有关的神经网络算法与遗传算法等 属性约简问题是粗糙集理论的核心问题之一，也是n p 难问题导致n p 难问题的主要原因 是属性的组合爆炸高效的约简算法是粗糙集应用于知识发现的基础目前国内外还没有一个公 认的、大家都比较满意的属性约简算法寻求一种高效的属性约简算法仍然是当前研究的热点之 一目前，国内外已缉有了不少基于基于粗糙集理论的属性约简方法，大致分为以下几种：基于辨 识矩阵的方法【2 4 1 、基于属性重要度的方法【2 翻、基于信息熵的属性约简算法1 2 同，以及各种启发 式算法1 2 7 t2 8 ，2 9 1 等 1 2 2 相关分析的理论研究 相关分析是统计学的一个重要内容变量之间的相关程度是用相关系数来度量的，最常用的 相关系数是p e a r s o n 矩相关系数，它广泛地用于回归与相关分析问题然而，该相关系数也有其局 限性。比如要求两变量必须服从正态分布，且只能反映两列变量之间的线性关系等所以有必要 引入非参数型的度量变量之间的相关程度的统计量，以及检验变量之间是否独立的非参数方法， 进而出现s p e a r m a n 秩相关系数、k e n d a l l 秩相关系数、k e n d a l l 协和系数等来度量定序变量之间 的相关性 s p e a r m a n 秩相关系数最早是由c s p e a r m a n 予1 9 0 4 年提出的一个检验统计量，该秩相关系 数可以用来描述两个变量有没有同时上升( 下降) ，或一个上升、一个下降的趋势，反映了两个变量 之间的非线性相关性同样，m g k e n d a l l 于1 9 3 8 年给出的一个检验统计量k e n d a l l 秩相关系 数也具有这样的性质它们在检验总体中相关性的存在时具有同样的功效效率( 9 1 ) ，所不同的是 s p e a r m a n 秩相关系数更容易计算以上两个秩相关系数主要是处理两个变量之间的相关性，对壬 多个变量来说，这样的检验问题称为一致性检验问题 k e n d a l l 协和系数是用来测量詹个这样的 变量之间的相关程度，它可以用来决定几个评判员之间的一致性或3 个以上变量之间的相关性 此外，有序尺度变量间的相关性也可用g o o d m a n k r u s k a l 的g a m m a 系数来度量，而有序尺 度变量和名义尺度变量间的相关性也可以通过相应的统计量来度量 1 3本文工作要点及结构安排 本文针对现实生活中存在的有序数据的情况，提出了基于粗糙集与相关分析相结合的属性约 简新方法，将统计学中用于检验相关性的统计量适当改造之后引入到有序信息系统中，作为属性 集间相关性的新度量，并基于这些度量提出了一种新的属性约简方法通过数值例子说明，这种 方法是有效可行的，可视为粗糙集约简方法的一种统计扩展，且为其提供了一定的统计依据具 体安排如下； 本文第二章主要介绍了优势关系下的粗糙集理论、约简以及排序方法，为第二、第三章的相 关分析做准备 本文第三章结合粗糙集排序方法，运用非参数统计的思想研究了有序属性的约简同题首先 介绍了s p e a r m a n 秩相关系数与k e n d a l l 秩相关系数的基本概念，并基于这两个度量分别给出了有 序信息系统与有序决策表的属性约简方法，以及相应的性质最后通过实例验证了该方法的可行 性与有效性，并分析了该方法与粗糙集约简之间的内在联系此外，对于有序决策表，我们还给出 了基于k e n d a l l 协和系数的属性约筒方法 本文第四章则考虑了既含有有序属性又含有名义属性的复杂决策表的约简问题首先介绍了 g o o d m a n - k m s k a l 的g a m m a 系数，并给出基于此系数的有序决策表约简方法；其次在列联表的基 础上定义了度量，分析了二元名义属性与有序属性间的相关性；最后通过对复杂决策表的属性 分割，我们结合这两个度量给出了复杂决策表的属性约简方法 本文第五章对第二一四章所得结论进行总结，并展望了粗糙集方法与统计结合的可能发展趋 势 宁夏大学硕士学位论文白江：基于粗糙集与相关分析的属性约简 4 第二章优势关系下的粗糙集理论与方法 经典粗糙集理论是以等价关系为基础，可用于处理名义数据然而在现实生活中往往会出现 有序数据的情况，例如学生的评价有优，良、中、差之分，岩石的基性程度可分为超基性、基性、中 性和酸性，人们的年龄可分为少年、青年、中年和老年等，经典粗糙集方法在处理这类数据时往往 捉襟见肘为此，g r 高：o ，m a t a x a z z o 及s l o w i n s k i 提出了基于优势关系的粗糙集方法( d o m i n a n c e - b a s e dr o u g hs e ta p p r o a c h 简称d r s a ) 3 例，将属性的有序性考虑进来，用优势关系代替原来的 不可分辨关系( 等价关系) ，是对经典粗糙集方法的一种推广，能较有效地处理有序数据因此， 近年来有关d r s a 的研究得到了迅速的发展，进而出现变协调的优势关系粗糙集方法( v a r i a b l e c o n s i s t e n c yd o m i n a n c e - b a s e dr o u g hs e ta p p r o a c h 简称v c d r s a ) 3 1 1 以及变精度的优势关系粗 糙集方法( v a r i a b l ep r e c i s i o nd o m i n a n c e - b a s e dr o u g hs e ta p p r o a c h 简称v p d r s a ) 3 2 等推广形 式，见文献 3 3 ，3 4 ，3 5 ，3 6 】 2 1 基本概念及性质 首先，我们给出信息系统以及决策表的定义 定义2 1 f 2 4 】 称a ，f ) 为一个信息系统，其中有限集合u 为对象集，即 = x l ，x 2 ，z n ， ，中的每个z i ( i 冬n ) ，称为一个对象而a 为属性集，即 a = a l ，a 2 ，口m ) a 中的每个q u m ) 称为一个属性 f 为u 和a 的关系集，即 f = 疗：歹m 其中厶：u 畸us 仇) ，码为属性口j 的值域 定义2 2 3 s l 若( 以a ，f ) 为一个信息系统，且巧o m ) 为有序值域，则该信息系统又被称 为有序信息系统 定义2 3 【2 4 1 称( u ，a ，f , d ，g ) 为目标信息系统或决策表，其中( 以a ，f ) 是信息系统，a 称 t 为条件属性集，d 称为目标属性集或决策属性集，即 d = d l ，如，由) g 为u 和d 的关系集，即 g = 劬：歹p ) ， 其中乃：u - w u p ) ，巧为目标属性由的值域 定义2 4 1 3 8 】若( u , a ，f ) 为有序信息系统，且w u p ) 为有序值域，则该决策表又被称为 有序决策表 定义2 5 1 3 8 设( 玑a f ) 为有序信息系统，对于b a ，令 7 冗看= ( 戤，) 矿x 矿：l l c x ) t c x j ) ( 坳l b ) 则称r 吾为有序信息系统上的优势关系 记 p t 】螽= 巧u ：扛，) 硝) = z j 【，：五 i ) 五( 巧) ( w l b ) ) k 】荟表示在属性集b 条件下，优于对象双的所有对象集合，称为x i 的优势类 易见，优势关系具有以下性质： ( 1 ) r 盖是自反和传递的，未必是对称的，因而一般不再是等价关系； ( 2 ) 当b l 岛a 时，有硒。2 月舌。2r j ； ( 3 ) 当b l 岛a 时；有【z t 】舌。陆i 】盖：2 陋f 】j ； ( 4 ) 当巧k 】荟时，有【塔k 】吾，因此k 】吾= u b 】盖：扛i 】吾) ； ( 5 ) p i l 盖= 扛j 】荟号l t ( x i ) 兰，1 0 j ) ( 口b ) ； ( 6 ) 了 五( ) ) ， ( 2 2 1 ) 则称骘全( 蹿( 嗣，巧) ：x i ，巧u ) 为有序信息系统在优势关系下的辨识矩阵 记 碥= d ；( 甄，) ：d ；0 i ，吻) o ) ， ( 2 2 2 ) 则有如下基于辨识矩阵的属性约简方法： 定理2 2 【2 4 】设( 以a ，f ) 为有序信息系统，b 是( 阢a ，f ) 在优势关系下的约简当且仅当它 满足以下条件： ( 1 ) v d 口；，b n d 口； ( 2 ) v b b ，存在d 口磊使得( b p ) ) nd = 0 有序决策表( 弘a ，f d ，g ) 是有序信息系统的一种特殊情况，简单起见，我们只考虑决策属性 集为单个属性的情况因此，对于有序决策表( 以a ，f d ) ， 9 d ) ) ，除了在条件属性集上定义优势关 系外，同样可以对决策属性定义优势关系： 磷= ( 甄，巧) ：g d ( z i ) s 驰( ) ) 则当冗j 时，称有序决策表在优势关系下是协调的，否则称为不协调的 同样，有序决策表中的众多属性也不是同等重要的，一般而言，对决策结果影响程度不同， 属性的重要性程度也不同如果去掉某个属性后，并不影响决策结果，那么这个属性是冗余的 利用粗糙集建立优势关系上的属性约简方法，将合理简化信息决策问题 定义2 8 1 2 4 1 设( 阢a ，f d ) ， 驰) ) 为有序决策表，若b a ，且满足： ( 1 ) 冗舌r 手； ( 2 ) v b b ，r 吾一d 延磷 则称口是有序决策表在优势关系下的一个约简 记 ， d 享( 瓤，) ： 0 l a ： 。 五巧”黝 。 驰 j ) ， ( 2 2 3 ) i o ， 鳓( 黝) 蚰( ) 则称( d ( z i ，奶) ：t ，jsn ) 为有序决策表在优势关系下的辨识矩阵另外，记 d 茹= d 亨( 双，) ：d 孑( 戥，q ) 谚) ( 2 2 4 ) 基于辨识矩阵，我们给出如下属性约简方法： 定理2 3 【2 4 j 设有序决策表( 阢af d ) ， 9 d ) ) 在优势关系下是协调的，则b 是 ( 以a ，只 d ) ， 驰 ) 在优势关系下的约简当且仅当它满足以下条件： ( 1 ) v d 碥，bnd o ； ( 2 ) v 6 b ，存在d 碥使得徊一 6 ) ) nd = 谚， 一般说来，有序信息系统的约简不是唯一的，如果用 b i ：isz ) 表示有序信息系统的所有约 简，则称b = n 笔l 鼠为有序信息系统的核心一般核心不一定构成约简，若核心非空，则任何约简 都包含核心。且核心中的元素是任何约简都必须有的，因而是绝对必要属性b = ub i n 鼠 = li = 1 l 是相对必要属性集，它不出现在任何约简中，但出现在某些约简中丽b ”= a ub i 是绝对不 i = 1 必要属性集，它不出现在任何约简中 2 3 优势关系下的粗糙集排序方法 粗糙集方法是在偏序关系上建立优势关系，将有序信息系统转化成优势关系模型，并通过关 系模型得到对象之间的排序 由定义2 5 知，若( 反，巧) r 吾，它等价于i ( z i ) h ( z j ) ( v a t b ) ，记为黾5 b 巧若 ( z f ) = f t ( x j ) ( v o l b ) ，记为黾一口巧( 玑5 b ) 是偏序集，那么b 是u 上的偏序关系，即满足 自反性、反对称性、和传递性若z i5 b 巧且x i b 巧不成立，即f l ( z i ) i t ( x j ) ( v a _ f b ) 且等 号不同时成立时，则记作z i 口奶，此时( 以 - i 冠日( z 七n ) ，则r b ( 1 l g l l ) 卜r b ( z j 2 ) 表示对象瓤在属性集b 条件下 综合优于对象巧根据r 口( 戤) g n ) 的大小，得到综合排序的结果记为：z i l - 巧2 卜b - z 量n 根据综合排序的结果，我们得到l 组秩，记为： t 口= ( r f ，穆，t 学) ， 其中，尹表示对象x i ( tsn ) 在属性集b 条件下排序的秩 定理2 4 【4 0 】设b 是有序信息系统( u , a ，f ) 的属性约简集，则r b ( 氟) 具有以下性质： ( 1 ) 0 r b ( x i ) 1 ； ( 2 ) 当卜8 即时，有r 8 ( z i ) r b ( 即) ； ( 3 ) r 曰( z i ) r b ( 巧) = = 争r a ( z 1 ) r a ( 町) 引入综合优势度的目的在于将对象综合排序，这与其它排序法不同点在于无需提供数据集合 之外的任何先验信息，直接从信息表出发，所以排序结果可以说是比较客观的 2 4 数值例子 例2 1 表2 1 给出信息系统( u ，a ，f ) ，其中u = z l ，2 2 ，z 3 ，x 4 ，x 5 ，z 6 ) 为对象集， a= 0 1 ，a 2 ，n 3 为属性集，f = 五：u + ，a l a 为对象与属性之间的关系集，= l ，2 ，3 ) ( 铆a ) ( 厂 a la 2a 3 z l 12 1 z 2 3 22 x 3 ll2 z 4 213 z s 3 32 z 6 323 由( 2 2 1 ) 式可得嚷2 1 在优势关系下的辨识矩阵如下 表2 2 优势关系下的辨识矩阵( 例2 1 ) u z lz 2x 3x 4x 5x 6 z lg毋 0 2 ) n 2 ) 毋0 霉2 口l ，a 3 口 o l ，口2 ) n 1 ，8 2 ) o口 z 3 口3 ) o口口 90 z 4 ( 口l ，a 3 口3 口1 ，a 3 ) 谚 0 3 0 z 5 a 0 2 ) n 1 ，a 2 口l ，口2 ) d n 2 ) z 6 d l ，a 3 a 3 a n l a 2 0 3 ) 0 由( 2 2 2 ) 式可得i 碥= f 口2 ) ， 口3 ， 口，口2 ， n l ，口3 ，a ) 对于b = a 2 ，口3 ，v d 碥，b n d o ，且存在 口3 ) 碥使得 a 2 ) n 口3 ) = o 因此由定理2 2 可得，b = 口2 ，a 3 ) 是信息系统 ( 阢a ，f ) 在优势关系下的一个约简，且约简唯一 例2 2 表2 3 给出决策表( u , a ，f ， d ， 夕d ) ，其中( 仉a ，f ) 为信息系统，a = 口l ，口2 ，口3 ) 是 条件属性集，d 为决策属性，9 d ：u - v ：；，= ( 1 ，2 ，3 ) 为决策属性d 的值域。 根据( 2 2 3 ) 式可得决策表在优势关系下的辨识矩阵，见表2 4 由( 2 2 4 ) 式， 碥= 口l ，口2 ) ， n l ，a 3 ，a 当b = 口2 ，8 3 ) 时， v d 口茹，bad 口，且 0 2 ) n n l ，n 3 ) = 宁夏大学硕士学位论文 白江：基于粗糙集与相关分析的属性约简 9 表2 3 决策表 u 口l口2a o d z l 1211 z 2 3223 z 3 ll2l z 4 2132 z 5 3323 z 6 3233 ， 表2 4 优势关系下的辨识矩阵( 例2 2 ) u z lz 2x 3x 4z 5x 6 z l 0o仍谚口0 z 2 d 1 ，n 3 毋 n l ，口2 n l ，0 2 ) 0毋 x 3 o0o9口o x 4 ( 口l ，a 3 o ( 口l ，口3 ooo 0 5 ao n l ，口2 口l ，n 2 ) 国d z 6 n l ，a 3 o a 0 1 ，a 2 oo o ， 0 3 ) n 口l n 2 ) = 口，则由定理2 3 知，属性集 口2 ，( 2 3 ) 是决策表在优势关系下的一个约简同 理可得，当b = 口- ) 时，也是该决策表的一个约简 2 5本章小结 本章回顾了优势关系下的粗糙集理论及其相关概念，详细介绍了优势关系下的粗糙集约简方 法，并给出了相应的数值例子，与将要介绍的统计约简形成对比，并引入优势关系下的粗糙集排 序方法，为下一章更好地与统计结合奠定基础 宁夏大学硕士学位论文白江：基于粗糙集与相关分析的属性约简 1 0 第三章基于秩相关系数的属性约简方法 在实际应用中人们经常要对一些变量之间的相关程度作出分析，如某种农作物的产量与施肥 量之间是否相关，人的身高与体重之间又是否相关等等可以说诸事物间的相关无处不在，无时 不有的在参数统计中，两个随机变量之间的相关性是通过相关系数来度量的，即p e a r s o n 矩相关 系数它广泛用于回归与相关分析问题，然而这个相关系数也有其局限性首先它必须满足变量 服从正态分布的假设，条件比较苛刻其次它只能用来刻画了两变量间的线性相关程度如何，而 对于非线性相关性则是鞭长莫及因此，它不能用来度量通常意义下的相关性，即两个变量同时 上升( 下降) ，或一个上升、一个下降的趋势所以有必要引入非参数型的度量变量之间相关程度的 统计量，以及检验变量之间是否相互独立的非参数统计方法这样既不受正态分布假设的限制， 又可以度量通常意义下的相关性，满足实际的需要本章将介绍s p e a r m a n 秩相关系数与k e n d a l l 秩相关系数，以及s p e a r m a n 秩相关系数的推广形式k e n d a l l 协和系数，它们都是非参数型的统计 量，可以用来度量变量之间的相关性因为信息系统中的属性可看作是统计中的变量，这也为粗 糙集方法与统计方法的结合创造了一定的前提条件 3 1s p e a r m a n 秩相关系数 首先我们提出如下假设检验问题，对于有序信息系统( 以a ，f ) ，若b a ，原假设与备择假设 分别为： h o ：属性集a 与属性集b 不相关铮日l ：属性集a 与属性集b 正相关 对于有序决策表( 以a ，f d ，g ) ，bsa 其假设为： h o ：条件属性集b 与决策属性集d 不相关聿= 今h i ：条件属性集b 与决策属性集d 正相关 在矩相关系数的基础上，s p e a r m a n 用变量的秩代替原来的样本值，提出了秩相关系数经过 适当的改造，我们将此系数重新定义如下，引入到粗糙集分析当中去 定义3 1 称r l ( a ，b ) 为属性集a 与b 的s p e a r m a n 秩相关系数，若 r l ( a ，b ) = 1 一元石善墨可， ( 3 1 1 ) 其中s = 墨。( r i 4 一r 尹) 2 ，( b a ) ，i 4 ，r 尹分别为在属性集a 和b 条件下用粗糙集方法排序后得 到的规的秩 可见，( a ，b ) 具有类似于参数统计中的相关系数的性质，如： ( 1 ) - 1 r s ( a ，b ) s1 ； ( 2 ) 当r 尹= r 尹时，r 。( a ，b ) = 1 ；当，于+ ，_ 尹= n + 1 时， r 。( a ，b ) = - 1 如果( a ，b ) = 1 ，表示有序属性集a 和b 完全正相关；n ( a ，b ) = - 1 ，表示有序属性集a 和b 完全负相关；“似，b ) = 0 ，表示有序属性集a 和b 完全不相关 宁夏大学硕士学位论文白江：基于粗糙集与相关分析的属性约筒 1 1 可以看出，此时将属性集a 、口看作是两个变量x 、y 来处理的在非参数统计方法中考 虑的是两个变量之间的相关性，现在被替换为两个属性集之间的相关性 如果排序结果中出现结( 或称为同分) 情况，即r b ( x i ) = 冠b ( ) 时，我们就用平均秩法定秩， 即让这些对象的秩都等于没有结出现时它们应有秩的平均值，重新记戤的秩为r 于+ ，f 尹如果同 分的比例不大时，它们对r | ，b ) 的影响可以忽略，仍可用( 3 1 1 ) 式计算然而，当同分的比例 较大时，r | ( a ，b ) 的计算中就必须加入一个修正因子，则r i ( a ，b ) 被修正为： 棋a b ) = 礁男， ( 3 忱) 其中， a 2 = 丛写旦一西1 厶t 丁a 3 ，；一r a i ) ， 铲= 丛号手旦一西i4 。丁b 3 j 一佃，j ) ， s + = ( r 于一r 尹) 2 ， t a 面t b ，j 分别表示r 于+ ，学( t ，歹，1 ) 的结统计量，即等于在一给定秩处同分的观察数 对于( a ，b ) 的显著性检验，如果是小样本数据，可直接查看s p e a r m a n 秩相关系数检验临 界值表，得到临界值c a 若n ( a ，b ) c a ，则拒绝原假设，称属性集a 与属性集b 在q 显著水平 上是相关的；否则，接受原假设，称属性集a 与b 在该显著性水平上不相关 定理3 1