《roughsets的属性约简算法研究及应用》由会员分享，可在线阅读，更多相关《roughsets的属性约简算法研究及应用（31页珍藏版）》请在金锄头文库上搜索。
1、S t u d ya n dA p p l i c a t i o n so f A t t r i b u t eR e d u c t i o nA l g o r i t h m sO i lR o u g hS e t sA b s t r a c tR o u g hS e t s ( R S ) t h e o r y ，i n t r o & i c e db yzP a w l a k ，i san e wm a t h e m a t i c a lt o o lt od e a lw i t hk n o w l e d g e ) p a r t i c u l a r
2、l yw h e nk n o w l e d g ei si m p r e c i s eo ri n e o n s i s c e n zI nt h i sd i s s e r t a t i o n ，t h er e s e a r c ht r e n d sa n dt h ea t t r i b u t er e d u c t i o nt h e o r yo fR Sa r ep r e s e n t e df i r s t l y T h e nt h ee x i s t i n ga t t r i b u t er e d u c t i o nm e
3、 t h o d s ，w h i c hc o n s i s t so fX HH ua l g o r i t h m ，P a w l a ka l g o r i t h I aa n da l g o r i t h m sb a s e do nd i s c e r n i b i l i t ym a t r i xa n di n f o r m a t i o ne n t r o p y , a r es u m m a r i z e d S e c o n d l y , t h ed i s c e r n i b i l i t yi n a l , r i x
4、a l g o r i t h mi si m p r o v e db yp r o p o s i n gan l o r eo b j e c t i v ea p p r o a c ht oe v a l u a t et h es i g n i f -i c a n c eo fa t t r i b u t e s T h i r d l y ，b e c a u s et h ee x i s t i n ga l g o r i t h m sc a no n l yf i n dt h el e s s e ra t t r i b u t es e t sc o n t
5、 a i n i n gr e d u c t sa 土m o s tc a s e s o n en e ws t r a t e g yw i t hl o c a lr e t r o s p e cT ；i sb r o u g h tf o r w a r dt oc o n q u e rt h ed i f f i c u l t yT h er e l a t i v i t i e s n o to n l yb e t w e e nt h es e l e c t i n ga t t r i b u t e sa n ds e l e c t e do n e s ，b
6、 u ta l s oa m o n gt h eu n s e l e c t e da t t r i b u t e s ，s h o u l db ec o n s i d e r e dT h i ss t r a t e g yi sh e l p f l , 1t oc o m p u t et h em i n i m a lr e d u c tF o u r t h l yt h ed e c i s i o nr u l e sa r ec l a s s i f i e dI n t ot h r e ep a r t s ：o n o n e 、o n ( m u l
7、 t ia i dm u l t i o n e T h e nt h ed e c i s i o nr u l e sa r er e c o g n i s e db yd i g g i n gt h es t a t i s t i c a li n f o r m a t i o no fd a t ab a s e sa n dt h e i rB a y e s - e r r o ri sp r o v e dt oh em i n i m a l w h i c hi sau s e f u lc o n c l u s i o n F i n a l l y a l lt
8、 h ea b o v et h e o r e t i c a lr e s u l t sa r ea p p l i e dt ot h ea n a l y s i so fm e l l i t u r i at Ia n dM o n k sp r o b l e m sT h ec o n c l u s i o ni se n c o u r a g i n ga f t e rt h ec o m p a r i s o nw i t hs o m ep r e c i o u sm a c h i n el e a r n i n ga l g o r i t h m si
9、 n c l u d i n gI D | f h m i l ya n dA Qf a m i l yK e y w o r d sR o u g hS e t sA t t r i b u t eR e d u c t i o nD i s c e r n i b i l i t yM a t r i xL o c a lR e t r o s p e c tD e c i s i o nR u l e s2引言智能信息处理是当前信息科学理论和应用研究中的一个热点领域。过击几十年中人们谯专家系统、知识工程、人工神经网络，模糊集簿领域的不断实践平订探索，取得了禳多很好的成绩。虢着信息时代的多
10、j 来，数据不断增长，并且在许多情况下所给数据中含有尤量的冗余信息和噪声。如何从大量的、杂乱无鞲的、强于扰的数捷( 海爨数据中挖掘潜在懿有剥弼傍篷辩髂墓f 知识) ，蠢人类粒餐麓信息跫璎能力提出了前所束有的挑战。因此，研究能罅从大量信息中形成实际概念( 归纳)敬系缝裁显褥越袋悲重要。虽然基嚣已有攫多对数据道野癸辑鲤篱单统跨技术，艇高级的智能分析技术还远、艘有成熟 3 0 ，3 2 j 。R o u g hS e t s ( R s ) 理论蹙囊波兰数学家z P a w l a k 于2 0 世纪年代提出的一种研究不究整，不确定知识年 l 数据的表述、学习、归纳的理论方法它从新的角度认识知识，认
11、为概念的不精确性是由知识的粒度过粗g f 越的 l 】。在R s 理论中，同一个概念在菜个A g e n t 番来是精确静，蔫在劈一个A g e n t 可糍认为是穰襁翦( 送两个A g e n t 的认识水平不同，即知识粒度不阿) 显然，这种定义符合人粪的认知援莓，惫院较霉筑魏。R S 瑾论；l 入嚣争蘩确巢f 上逐似襄下遥强) 来撵述翔 ； 翘不确定程度，而髭需提供除问题所需处理的数据之外的任何先骏信息吲这一点是其它方法强难擞到的。横糍集方法器要事先定义索矮嚣数，冀主理性瘦渡方法受到一些磺疑。概率统计方法也需要幅关的概鬻分布，如先验概率等f 5 。知识约简是R S 的梭心内昝乏一，包括羼性
12、约筒和属性速约楚，鞭的是去撵数据袭巾冗余的属性和属性值逮在处理大规模数据尤其是海麓数据时是必须的；否则冗余信息带来的时闻、空间代价将是匿丈的，R s 理论凭冀崮身傀势在翔援获鼗和数据挖掘串被广泛应臻，基卒可黻分为两大类：有决策的分析和无决策的分析有次策的分析主簧是删除冗余信息，从实例集中攫取怒蠢，可雳子嚣疗渗毅，琏浚 手绉等。茏决策黪数撂努橱主要是雾j 蔫蓬缝约简删除冗余属性，利用德约简压缩数据以及进行数据的聚娄分析本文翡内容缎餐如下；第一章奔缨豁戆褥完动态、基本理论藏褒意懿壤娃约简算法；第二章巍对差别瓶阵算法进行了改进；然后针对各种算法难以求得完备属性约简的婀题，提出了一种带局部西湖测策略辫
13、算法；并通过例予说明了遮两种新算法静优越性；第三章串撼约简后的决策规剥分为三类，提出了处理不确寇性规则的方法；第四章将前面的理论结果藏用于糖尿瘸病因分析和M o n k s 问题；最后一章巷雏念文势摇蠢避一步骈究懿方鹣。3第一章R S 爆性约简理论R S 理论照一种新的处理模糊和不确寇性知识的数学工舆。其主饕思想是在保持分类髭力不蹩的翦提下，通过知识约筒，导出闻瓤辩凑策鼓分类规剡。本毒麓要介绍R s 理论的研究动态、基本概念以及几种现有附属性约简算法，作为后面备章节的基础1 1R S 研究动态融啦S e t s 理论是渡兰数学家z ，P a w l a k 予1 9 8 2 年耪提穗的一转分接
14、不壶整、不确定性数据的理论由于最初关于R S 的研究主爱集中在波兰，因此当时并没有引起国际计算枧界稳数学界豹蹩视，研究她域仅限于东欧一些国家。直到1 9 9 0年前詹，由于谈理论在数据的? 史策与分析、模式识剐、机器学习与知识绽现等方面的成功应用，才逐渐引起了世界备国学者的广泛关注。1 9 9 1 年ZP a w l a k 的专著。R o u g hS e t s - T h e o r e t i c a lA s p e c t so fR e a s o n i n ga b o u tD a t a ”翡闻篷，成为R S 理论发展的一个重要里稷碑1 9 9 5 年A C MC o m
15、 m u n i c a t i o n 将R s 列为新浮现的计算撬符学豹蓊究渫疆泼年寒l 醛艺箴为臻怠辩学鼓为活跃黪臻究赣蠛之一，戮黠该理论还在医学、化学、管理科举、商业和金融等领域得到丁成功的应用。我丽也袁垂象是然辩学基金、溪家8 6 3 诗翅季曩一些省囊綦垒的支持下秀聂了一定翡璐宠工作，逐渐取褥了一些研究成果国内已经连续召歼了两届R S 会议，今年还将举办美于粗糙集、模糊集激及粒度计算魏国鼯会议。警前关于K S 的研究主要寨中在以下几个方面：( 1 ) R o u g h 逻辑一从逻辑角度进行不精确推理、决策 2 9 ，3 9 ；( 2 ) R o u g h 代数一讨论建S 的代数络
16、梅稀拓挣络构瑷及救敛性闻藤，致力予搴孽造或生成约俺窘间【2 ，8 ，1 6 ；( 萄R o u 酶终蓠一趣捂各辞翁簿算法懿舞衮，隶辩瑟可簇夺翡憨篱菠萁劳苻实现；( 4 ) 知识粒发一在不嗣翡屡玫下鳃释知识睦1 3 ；( 5 ) 与其它处理模糊性或不确定性理论之间关系的研究一将R s 璃论进行了推广【1 7 ，3 6 】。本文主要蒋暇于属性约简算法的研究，对于文中提到的约简，除非特别声豫均指属性约简+1 2R S 属性约简理论的基本概念在R s 理论中，知识是慝信患系统鄞鹱性一筑黠表) 囊表示的 1 4 1 。一般媾暹下，裳牵懿翻标记不霹懿羼霞； 亍枯；己论壤懿对象。媳果率摹簧意泰凌孛麴璃霞遴一步分成条件属性和决策属性，则弥演信息系统为决策嵌知识约蔺考察的怒信息系统( 娥决策表) 中给出的所肖知识是否都必要( 相对于决策而言) ? 在保持表中知识不变的前提下，删除表中冗余信息的过程称为知识妁简，包括属性约筒和属性值约简。对决策表的约简，叉纷为知识的相对约简，其最终结果是将决策
