（计算机软件与理论专业论文）信息表属性约简若干问题新研究.pdf

摘要：粗糙集理论是一种能有效地分析和处理不精确、不一致、不完整等各种不确定性 信息的数据分析工具。该方法近年日益受到国际学术界的重视，已经在模式识别、机器 学习、决策支持、知识发现、故障诊断、预测建模等领域得到成功的应用。属性约简是 粗糙集方法的核心问题之一，是粗糙集理论应用的关键技术，也是知识发现的重要研究 课题，已成为一个备受关注的研究热点。有效、快速的属性约简算法是粗糙集理论应用 的基础，也是粗糙集理论规模应用的保障。本文围绕粗糙即理论的一个核心问题即属性 约简展开了三个方面的研究：信息表的属性约简、相容决策表即特殊信息表的属性约简、 不相容决策表的属性约简。 首先，在对区分能力大小研究的基础上建立了一个用于指导信息表的绝对属性约简 的粗糙集模型，同时在对区分能力和分类能力二者关系深入研究的基础上提出了决策依 赖区分精度新概念，该概念为用于指导决策表的相对属性约简的提供了一个新的判据， 同时给出了区分精度、近似精度和决策依赖区分精度在属性约简过程中相互关系的研究 结论，通过一组对比实验说明了决策依赖区分精度比近似精度对于分类能力的描述更细 致客观。 其次，借助粗糙属性向量树提出了新的求全部属性约简的算法，通过理论分析说明 了新算法的时间复杂度低于经典的基于差别矩阵求全部属性约简算法以及它的改进算 法。对比实验结果验证了本文算法在运算效率上明显高于基于差别矩阵求全部属性约简 算法的改进算法。 再次，s k o w r o n 的差别矩阵方法求不相容决策表属性约简会产生错误的结果，在一 些文献中通过改进差别矩阵定义的方法来解决这个问题，并非十分理想，因为每生成一 个差别矩阵元素前都要对两个相关对象的相容性进行判断增加了计算量，本文提出了新 的解决办法，即提出了将不相容决策表转换为相容决策表的方法。 最后，本文提出了新的简化差别矩阵算法，该算法是采用桶排序的思想构造属性桶， 而后借助这个属性桶在无需排序的情况下边生成差别矩阵元素边简化差别矩阵，有效的 加快了简化差别矩阵的速度并且最终得到有序的简化差别矩阵；同时，给出从属性所在 差别矩阵元素的权重和属性在差别矩阵中的出现的频数以及属性的吸收能力三方面度 量属性重要性的新标准，从而在新的属性重要性的度量标准和有序简化差别矩阵的基础 上产生了新的求属性约简的方法，通过理论分析说明了新的求属性约简算法的最坏时间 复杂度低于其它基于差别矩阵求属性约简算法。一组对比实验结果验证了本文的简化差 别矩阵算法与同类简化差别矩阵的算法相比是高效的，另一组对比实验结果表明本文的 属性约简算法可以很大程度上得到最小属性约简。 关键词：区分精度；决策依赖区分精度；粗糙属性向量树；属性桶；属性重要性 a b s t r a c t ：t h er o u g hs e tt h e o r y ，w h i c hi sa ne x c e l l e n td a t aa n a l y s i st o o lt oh a n d l e u n c e r t a i ni n f o r m a t i o n ，s u c ha si m p r e c i s e ，i n c o n s i s t e n t ，i n c o m p l e t ea n ds oo n ， i so n eo ft h eh a r d e s tf i e l d s i th a sr e c e i v e dm u c ha t t e n t i o no ft h er e s e a r c h e r s a r o u n dt h ew o r l d r o u g hs e tt h e o r yh a sb e e na p p li e dt om a n ya r e a ss u c c e s s f u ll y i n c l u d i n gp a t t e r nr e c o g n i t i o n ，m a c h i n el e a r n i n g ，d e c i s i o ns u p p o r t ，k n o w l e d g e d i s c o v e r y ，f a u l td i a g n o s i s ，f o r e c a s tm o d e li n ga n ds oo n a t t r i b u t i o nr e d u c t i o n i so n eo ft h eb a s i cc o n t e n t si nr o u g hs e tt h e o r y ，k e yt e c h n o l o g yo fr o u g hs e t t h e o r ya p p l i e da n di m p o r t a n tr e s e a r c hc o n t e n t si nk n o w l e d g ed i s c o v e r y ，b e c o m i n g o n eo ft h eh o t t e s tr e s e a r c hf i e l d s e f f i c i e n ta n de f f e c t i v ea l g o r i t h m sf o r a t t r i b u t i o nr e d u c t i o na r et h ef o u n d a t i o no fr o u g hs e tt h e o r ya p p li e d ，a l s ot h e g u a r a n t e eo fr o u g hs e tt h e o r ya p p li e do nal a r g es c a l e s u r r o u n d i n gt h eo n ek e y p r o b l e m so ft h er o u g hs e tt h e o r yi e a t t r i b u t er e d u c t i o n ，t h ef o l l o w i n gt h r e e w o r k sh a v e b e e nd o n e ：a t t r i b u t er e d u c ti o ni ni n f o r m a t i o n t a b l e ，a t t r i b u t e r e d u c t i o ni nc o n s i s t e n td e c i s i o nt a b l e ，a t t r i b u t er e d u c t i o ni ni n c o n s i s t e n t d e c i s i o nt a b l e ， f i r s t ，ar o u g hs e tm o d e li se s t a b l i s h e dt os u p e r v i s et h ea b s o l u t ea t t r i b u t e r e d u c t i o nf o r i n f o r m a t i o nt a b l eo nt h eb a s i so fs t u d y i n gt h es e p a r a t i n gc a p a c i t y a n dan o v e lc o n c e p t i o ni sp r o p o s e d ，w h i c hi sc a l l e dd i s c e r n i b i l i t y q u a l i t yb a s e d o nd e c i s i o n ，o nt h eb a s i so fe x p l o r i n gt h er e l a t i o n sb e t w e e nt h ea b i l i t yo f d i s c e r n i b i l i t ya n dc l a s s i f y i n g ，t h i sn o v e lc o n c e p t i o ni sa ni m p o r t a n tc r i t e r i o n w h i c hs u p e r v i s e st h er e l a t i v ea t t r i b u t er e d u c t i o nf o rd e c i s i o nt a b l e i n a d d i t i o n ，s e v e r a lr e l a t e dc o n c l u s i o n sa r ed r a w nb yt h e o r e t i c a la n a l y s e s i n s t u d y i n gd i s c e r n i b i l i t y q u a l i t y ，a p p r o x i m a t eq u a l i t ya n dd i s c e r n i b i l i t y q u a li t y b a s e do nd e c i s i o n a c o m p a r i s o ne x p e r i m e n t s h o w st h a t d i s c e r n i b i l i t y q u a l i t yb a s e do nd e c i s i o ni sf i n e rt h a na p p r o x i m a t eq u a l i t yf o r d e s c r i b i n gt h ea b i1i t yo fc l a s s i f y i n g s e c o n d ，an e wa l g o r i t h mf o ra l lt h ea t t r i b u t er e d u c t i o n si sp r o p o s e do nt h e b a s i so ft h es t r u c t u r ef o rr o u g ha t t r i b u t ev e c t o rt r e e ( r a v t ) ，t h et h e o r e t i c a l a n a l y s e ss h o wt h a tt h eti m ec o m p l e x it yo ft h en e wa l g o r it h misl e s st h a nt h a t o ft h et r a d i t i o n a la l g o r i t h mb a s e do nd i s t e r n i b l i t y m a t r i xa n di t si m p r o v e d a l g o r it h m ac o m p a r is o ne x p e r i m e n to nc o m p u t a ti o n a le f f ic ie n c yp r o v e st h a tt h is n e wa l g o r i t h mi sm o r ee f f i c i e n tt h a nt h et r a d i t i o n a la l g o r i t h ma n di t si m p r o v e d a l g o r i t h m t h i r d ，s k o w r o n sd i s c e r n i b i l i t y m a t r i xf o rc o m p u t i n ga t t r i b u t er e d u c t i o n o fa ni nc o n sis t e n td e c is i o nt a b l em a yl e a dt om is t a k e s a tp r e s e n t ，s e v e r a l m e t h o d sb ym o d i f y i n gd i s c e r n i b i l y m a t r i x sd e f i n i t i o na r en o tf u l l yr e a s o n a b l e t oi m p r o v et h i sp r o b l e mi ns o m ep a p e r s ，s oan o v e ls o l u t i o ni sp r e s e n t e di nt h i s p a p e r f i n a l l y ，a n e wa l g o r i t h mf o rt h es i m p l i f i e dd i s c e r n i b i l i t y m a t r i xi s p r o p o s e di nt b i sp a p e r t h i sa l g o r i t h mt a k e st h ei d e a o fb u c k e ts o r t st oc o n s t r u c t a t t r i b u t e b u c k e t s t h e n ，t h ee l e m e n t si nd i s c e r n i b i l i t y m a t r i xi se s t a b l i s h e d w h i l ed i s c e r n i h i l i t y m a t r i xi sb e i n gs i m p l i f i e db yu s eo ft h i sa t t r i b u t e b u c k e t s w i t h o u t b e i n g s o r t e d t h i sc a n b r i n g o nt h e s p e e d o f s i m p li f y i n g d i s c e r n i b i l i t y m a x t r i x ，a n do b t a i nt h eo r d e r e da n ds i m p l i f i e dd i s c e r n i b i l i t y m a t r i xf i n a ll y ：a tt h es a m et i m e ，an e wc r i t e r i o no fs i g n i f i c a n c eo fa t t r i b u t e s i sp u tf o r w a r db a s e do nt h et h r e ea s p e c t sw h i c ha r et h ew e i g h to fe l e m e n t c o n t a i n i n gt h ea t t r i b u t e ，t h ef r e q u e n c ea n dt h ea b s o r p t i v ea b i1i t yo f t h e a t t r i b u t ei nt h ed i s c e r n i b i l i t y m a t r i x t h e r e f o r ean e wm e t h o df o ra t t r i b u t e r e d u c t i o ni si n t r o d u c e do nt h eb a s i so ft h en o v e lc r i t e r i o no ft h es i g n i f i c a n c e o fa t t r i b u t e sa n dt h eo r d e r e d a n ds i m p l i f i e dd i s c e r n i b i l i t y m a t r i x ，t h e t h e o r e t i c a la n a l y s i sp r o v e st h a tt h ew o r s tt i m ec o m p l e x i t yo ft h en e wm e t h o d i sl e s s t h a nt h eo t h e ra l g o r i t h m sb a s e do nd i s c e r n i b i1i t y m a t r i x o n e c o m p a r a t i v ee x p e r i m e n t o n c o m p u t a t i o n a le f f i c i e n c y s h o w st h a t t h i sn e w s i m p l i f i e dd i s c e r n i b i l i t y m a t r i xa l g o r i t h m i sm o r ee f f i c i e n tt h a nt h e h o m o g e n e o u sa l g o r i t h m i na d d i t i o n ，a n o t h e rc o m p a r a t i r ee x p e r i m e n ti na t t r i b u t e r e d u c t i o nd i s p l a yt h a tt h i sm e t h o df o ra t t r i b u t er e d u c t i o nc a nl a r g e l yf i n do u t am i n i m a la t t r i b t l t er e d u c t i o n k e yw o r d s ：d i s c e r n i b i i i t yq u a ii t y ：d is c e r n i b iii t y q u a ii t yb a s e do nd e c is i o n ： r a v t ：a t t rib u t e b u c k e t s ：sig nific a n c eo fa t t r ib u t e s 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加 以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的 研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名： 日期：c 7 - 甄中 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权保 留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权辽宁师范 大学，可以将学位论文的全部或部分内容编入有芙数据库并进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后使用本授权书。 学位论文作者签名：多缸j 丞着 指导教师签名：广狮 日 期：加，千、r 。l 信息表属性约简若干问题新研究 1 绪论 1 1 引言 数据分析及数据挖掘是个重要的正在迅速发展的研究课题，波兰科学家z p a w l a k 于 1 9 8 2 年提出的粗糙集( r o u g hs e t ) 理论正是解决这一问题的新理论，它可用于处理决策信 息表中的不确定知识。而属性约简是粗糙集理论研究的核心问题，属性约简是机器学习 和数据挖掘研究和应用中的一个重要方面。尤其在知识发现领域，属性约简是知识发现 的强有力工具，特别适合于数据预处理、分类规则发现、决策和预测知识发现、数据之 间依赖关系发现、寻求最优属性约简以确保产生满意的近似分类等。 1 2 粗糙集理论的国内外发展现状 在上世纪7 0 年代，波兰科学院院士、著名数学家z p a w l a k 和波兰科学院、华沙大学 的逻辑学家们，一起从事关于信息系统逻辑特性的研究，这些研究最后导致了粗糙集理 论的产生。1 9 8 2 年，z p a w l a k 发表经典论文r o u g hs e t s ，宣告了粗糙集理论的诞生， 由于最初关于粗糙集理论的研究成果大部分是在波兰用波兰语发表的，因此当时没有引 起国际计算机科学界和数学界的重视，研究地域也仅限于东欧一些国家，直到1 9 9 0 年前 后，由于粗糙集理论在机器学习与知识发现、数据挖掘、决策支持与分析等方面的广泛 应用【l 2 j ，才逐渐引起了世界各国学者的广泛关注，1 9 9 1 年，p a w l a k 的专著r o u g h s e t s - - t h e o r e ti 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 的问世【3 j ，标志着粗糙集理论 及其应用的研究进入了活跃期。粗糙集引起了世界范围内的关注，相关的学术活动也很 频繁，包括： 1 9 9 2 年，第一届关于粗糙集理论的国际学术会议( 研讨会) 在波兰召开： 1 9 9 3 年，在加拿大召开了第二届粗糙集与知识发现国际研讨会： 1 9 9 4 年，在美国召开了第三届粗糙集与软计算国际研讨会： 1 9 9 5 年在美国召丌了题为“r o u g hs e tt h e o r y ，r s t 9 5 ”的国际会议： 1 9 9 6 年在日本召开了第四届粗糙集、模糊集与机器发现国际研讨会： 1 9 9 7 年在美国召开了第五届粗糙集与软计算国际研讨会： 1 9 9 8 年在美国召开了第六届粗糙集、数据挖掘与粒度计算国际研讨 会：同年在波兰召开了第一届粗糙集与当前的计算发展 ( t h el “i n t e r n a ti o n a lc o n f e r e n c eo nr o u g hs e t sa n dc u r r e n tt r e n d si n 信息表属性约简若干问题新研究 c o m p u t i n g ，r s c t c 9 8 ) 国际j 下式会议； 1 9 9 9 年在日本召开了第七届粗糙集、模糊集、数据挖掘与粒度一软计算国际会议 ( t h e7 ”i n t e r n a l t i o n a lc o n f e r e n c eo nr o u g hs e t s ，f u z z ys e t s ，d a t a m i n i n ga n d g r a n u l a rc o m p u t i n g ，r s f d g r c l 9 9 9 ) ： 2 0 0 0 年在加拿大召开r s c t c 2 0 0 0 会议： 2 0 0 1 年在日本召开了第八届粗糙集理论与软计算国际研讨会： 2 0 0 2 年在美国召开r s c t c 2 0 0 2 会议： 2 0 0 3 年在中国召开r s f d g r c 0 3 会议： 2 0 0 4 年在瑞典召开r s c t c 0 4 会议： 2 0 0 5 年在加拿大召开r s f d g r c 0 5 会议： 2 0 0 6 年在日本召开r s c t c 0 6 会议：同年在中国召开t h e1s ti n t e r n a ti o n a lc o n f e r e n c e o nr o u g hs e t sa n dk n o w l e d g et e c h n o l o g y ，r s k t 0 6 会议： 2 0 0 7 年在加拿大召开了r s f d g r c 0 7 与r s k t 0 7 联合会议。 目前国际上研究粗糙集的一些高校和研究机构开发了一些粗糙集的模型系统甚至 实用系统，波兰华沙大学和挪威科技大学联合开发了一个基于粗糙集理论框架的数据分 析工具包r o s e t t a ，包括了计算核和图形用户界面，r o s e t t a 实现了对数据挖掘和知识获 取的支持，包括数据的预处理、属性约简和规则产生以及对得到规则的验证和分析， r o s e t t a 设计的目的是要作为基于不可区分关系模型的通用工具，而不是为某个特点的 应用领域设计的专用系统。美国肯萨斯大学开发的一套基于粗糙集的经验学习系统 l e r s ( l e a r n i n gf r o me x a m p l e sb a s e do nr o u g hs e t s ) ，它能从大量经验数据中抽取 规则，l e r s 已被美国国家航空航天管理局( n a s a ) 的j o h n s o n 空间中心采用，作为专家系 统开发工具，为f r e e d o m 号空间站上的医疗决策服务，美国环境保护署( u s e n v i r o n m e n t a lp r o t e c t i o na g e n c y ) 资助的一个项目中也采用了l e r s ，除上述经典系统 外，粗糙集研究人员还开发了很多其他粗糙集系统，如波兰工业大学的r o s e 、挪威t r o n d a t ai n c 的r o u g he n o u g h 和加拿大r e g i n a 大学的k d d r 等。 国内各高校和研究机构从上世纪9 0 年代后期开始了对粗糙集理论的研究。到上个世 纪术基本上国内的主要计算机刊物都发表有关于粗糙集的学术论文，粗糙集理论已逐渐 引起国内学术界的关注。国内粗糙集发展历程大致为： 2 0 0 1 年5 月在重庆召开了中国第一届粗糙集与软计算学术研讨会： 2 0 0 2 年9 月在苏州召开了第二届粗糙集会议： 2 0 0 3 年5 月在重庆召丌第三届中国粗糙集会议： 2 0 0 3 年1 1 月成立中国人工智能学会粗糙集与软计算专业委员会： 2 0 0 4 年l o 月在浙江召开第四届中国粗糙集会议： 2 0 0 5 年8 月在辽宁召开第五届中国粗糙集会议： 2 信息表属性约简若干问题新研究 2 0 0 6 年1 0 月在浙江召开第六届中国粗糙集会议： 2 0 0 7 年8 月在太原召开第七届中国粗糙集会议。 1 3 属性约简的研究现状与本文的具体研究工作 属性约简的研究对像是信息表或决策表，实际上决策表是含决策属性的特殊信息 表，从而属性约简分为绝对属性约简和相对属性约简。对于相对对属性约简人们已经提 出了若干关于相对属性约简的理论模型和方法以及算法【锄l ，但是有关绝对属性约简的 方法和算法却很少，特别是它与相对属性约简之间的关系探讨得比较少，因此本文有必 要对绝对属性约简以及与相对属性约简的关系进行的深入研究。s k o w r o n 的差别矩阵方 法是求全部属性约简一个代表方法，求全部属性约简是n p h a r d l h 题【9 1 ，本文借助粗糙属 性向量树提出了新的求全部属性约简的算法，并且算法复杂度有所降低。对于相对属性 约简而言根据决策表的相容性分为相容决策表和不相容决策表属性约简的研究，对于不 相容决策表的属性约简本文提出了新的方法。 在利用差别矩阵求属性约简时，需要对差别矩阵进行简化，通常先求出决策表的属 性核，之后以核属性为启发信息约去包含核属性的差别矩阵元素来简化差别矩阵，具有 较好的时间性能，但是并不是所以决策表都含有核属性，当决策表不含核属性时其时间 性能跟经典算法的时间性能是一样的，针对这种情况学者田卫东提出了边生成差别矩阵 元素边简化差别矩阵的简化差别矩阵的方法，但是这种方法有缺陷，当生成差别矩阵元 素时每次都需要从差别矩阵的第一个元素检索是否有元素能包含于新生成的差别矩阵 元素。为此本文提出新的基于属性桶快速简化差别矩阵的算法。 在简化差别矩阵基础上进行属性约简可分为完备属性约简和启发式非完备属性约 简，完备属性约简算法可以保证一定会求出属性约简，虽然启发式非完备属性约简不能 保证一定会求出属性约简但是大有可能求出最小属性约简，本文提出了启发式非完备属 性约简算法的时间复杂度低于同类基于差别矩阵求属性约简算法的时间复杂度。一组对 比实验表明本文的算法可以很大程度上得到最小属性约简。 1 4 论文组织结构 本文就粗糙集中信息表属性约简一系列问题进行了相关的研究。 第一章绪论，简单介绍了粗糙集理论的国内外发展现状和本文的组织结构。 第二章介绍属性约简相关概念及本文提出的两个新粗糙集模型同时给出理论证明。 第三章中提出了新的基于粗糙属性向量树求全部属性约简新算法并进行了对比的 实验。 第四章针对s k o w r o n 的差别矩阵方法求不相容决策表的属性约简产生错误结果这 3 信息表属性约简若干问题新研究 个问题提出了新的解决方法，不仅给出了理论证明而且举例子进行说明。 第五章提出了基于属性桶的有序简化差别矩阵算法并进行了效率对比实验 第六章提出了新的最优属性约简方法和算法并进行了实验对比 在本文最后一章对粗糙集属性约简相关问题进行了总结和展望。 4 信息表属性约简若干问题新研究 2 介绍属性约简相关概念及本文提出的两个新粗糙集模型 2 1 引言 波兰科学家zp a w l a k 教授于1 9 8 2 年提出的粗糙集合( r o u g hs e t s ) 理论是一种处理 模糊和不确定性问题的数学工具。在知识发现、人工智能、模式识别等方面得到广泛应 用l l 。在粗糙集理论中一个重要的观点是将知识与区分事物能力对应起来，即知识就 是区分事物的能力。在论域中如果所有对象都两两被区分那么就具有很大的知识，如果 在论域中所有对象都能划分同一等价类，任何对象不能与其他对象区分开来，那么含有 的知识很少。属性约简是有效提取知识的方法。文献 1 1 对知识进行量化，证明了量化 的合理性，以量化后的区分能力即知识量作为启发函数指导属性约简。在粗糙集理论中 常用近似精度为启发函数来指导相对属性约简，其取值范围是区间 o ，1 上的实数。其 实近似精度就是相容规则数取值的归一化或者说是相容规则占整个信息表对象数的比 例。近似精度的理论意义就是对分类能力的定性和定量描述。虽然近似精度仅仅适用于 特殊信息表即决策表，也就是说近似精度无法指导不含决策属性的信息表的属性约简， 但是近似精度归一化的取值范围不仅具有明确的粗糙集理论意义而且使得计算形式简 洁统一便于粗糙集的实际应用，从而近似精度也就成为粗糙集的经典标准模型。目前知 识量没有统一的取值范围，如果仅仅凭借知识量来判定区分能力的增强和减弱，就如凭 借相容规则个数的增减来判定分类能力的增强和减弱。为此，本文提出了将知识量即区 分能力大小归一化方法，使区分能力不仅有一个定量的描述而且要有一个定性的描述。 在对区分能力大小研究的基础上建立了一个用于指导信息表的绝对属性约简的粗糙集 模型，同时在对区分能力和分类能力二者关系深入研究的基础上提出了决策依赖区分精 度新概念，该概念为用于指导决策表的相对属性约简的一个重要判据即启发函数。 2 2 粗糙集理论属性约简相关概念 设s = 姒4kd 为信息系统，其中u = 缸。，工：，z 。 是论域，a 是属性集合，v 是 属性取值集合，f 是u 刈一矿的映射。若彳= co d ，c a d = 咖，c 称为条件属性集，d 称 为决策属性集，则该信息系统称为决策表。 定义1 m 1 x ，ye u ，对于p a ，0 尸是u 上的一个等价关系，如果满足 x o p y 营( v p e p ) ( l ( x ) 一厂p ( y ) ) ，则称郎是x ，y 的一个不可分辨关系。 信息表属性约简若干问题新研究 定义2 e 1 2 】 设x u 为论域的一个子集，p c ，x 的关于p 的下近似为： p _ x 一忸e ui x l p x 其中【工】p 表示u 中在等价关系p 下的等价类元素构成的集合。 定义3 n 2 1 设u 为一个论域，p ，q 为u 上的两个等价关系簇，q 的p 正域记为p o s p ( q ) ， 定义为：p o s p ( q ) 。u 只伍) 五t = l ，o 定义4 1 2 1设p c ， 对于划分，匕，k 的p 的近似精度为： ) ，j ，；c a r d ( p _ y f ) c a r d ( u ) 口 其中，c a r d ( ) 表示集合的基数。) ，反映决策表分类能力是指导决策表属性约简经典模型。 2 3 绝对属性约简和相对属性约简的两个粗糙集模型的提出 粗糙集的属性约简等详细概念可考文献 1 2 和文献 1 3 ，知识量性质及定理可以 参看文献 1 1 ，下面仅对用到的部分内容进行说明。 在粗糙集理论中，信息系统的属性约简分为绝对约简和相对约简，即分别对应信息 表的属性约简和决策表的属性约简，信息表区别于决策表，在于信息表没有决策属性， 其实决策表是一个特殊信息表，尽管在实际应用中，由于决策分析的需要，人们更多地采 用决策表的相对属性约简的概念。但是，信息表的绝对属性约简在数据浓缩，数据挖掘， 粒度计算等方面具有重要作用。 当前，在绝对属性约简的研究中还没有一个类似近似精度那样标准模型。在实际应 用中，知识库中的对象往往是不断动态变化的，随着对象数的变化区分能力也会变化， 如果仅仅凭借知识量来判定区分能力的增强和减弱，就如凭借相容规则个数的增减来判 定分类能力的增强和减弱，显然不科学。因此非常有必要提出一个类似近似精度那样标 准模型对区分能力作定性和定量描述。 2 3 1 区分精度的提出及理论证明 定理l 1 如果某属性集合将论域u 分成m 个等价类，每个等价类有元素分 别为，z 1 ，以2 ，甩。个，那么该属性集合具有的知识量( ，1 1 ，甩2 ，以。) = n 1 ) 罗他厅f ， l c 不” 其中，w ( 1 ，1 ) 的原始意义是表示某属性集合将含有两个对象的论域划分成两个等价类， 每个等价类含有元素数目为l ，该属性集合所具有的知识量为w o ，1 ) ，可以看作知识量的 基本单位或者说就是一个常数，文献 1 1 就是将w o ，1 ) 定义为常数1 。 为了探索绝对属性约简的标准模型，本文首先利用相关线性代数1 知识对文献 1 1 中定理l 1 提出的知识量表达式进行了深入研究，提出了另外一个知识量表达式，即 6 信息表属性约简若干问题新研究 本文的定理2 。然后提出了区分精度这个新概念，即本文的定义1 。 为证明本文给出的定理2 首先证明引理1 引理2 1 啦xn j = 寺( 2 一，l 孑) l s i j s ，竹。lsim 其中n ：v n i 一 l l s ，疗 证明。n z = “+ 刀2 + ) 瓴+ 他+ n m ) = ，z 1 ，z 1 - i - n l 1 2 + n l n 州 + n 2 n l + 2 n 2 + n z n m + ” + n m n l + n m n 2 + n m n m = 2 愧xn y + 砰 l i j m l i n e x t ) = = ) ，) p = f r s t ( q ) ：) e ls e ql = 下一层头指针地址； w h il e ( q l 一 n e x t ! = n u l1 ) i f ( f x x g ( q l 一 n e x t ，q - n e x t ) = = 1 ) ) q 2 = q l 一 n e x t ， q l 一 n e x t = q l 一 n e x t 一 n e x t ：f r e e ( q 2 ) ： e l s e q l = q l 一 n e x t ：) ) q 2 = q 一 n e x t ：q 一 n e x t = q 一 n e x t 一 n e x t ：f r e e ( q 2 ) ： ) 第三步：输出所有属性约简： w h i l e ( p ! = n u l l ) 输出一属性约简； p = p 一 n e x t ： 3 4 2 算法2 自底向上遍历粗糙属性向量树算法步骤 第一步：生成( 或调用) 并存储粗糙属性向量树 第二步：遍历粗糙属性向量树同时输出所有属性约简 q 首先指向半h 糙属性向量树从最底层开始的最后一个结点 f l a y e r ( ) 表示求某一结点所在的层数， f s x 9 0 表示求两个结点是不是上层相关结点的函数，返回的函数值是l 表示这两个结点 是上层相关结点反之等于0 表示这两个结点不是上层相关结点。 p = n u l l ： 1 3 信息表属性约简若干问题新研究 w h i l e ( q ! = n u l l ) i f ( f j s ( q ) = = y ) 输出q 对应的一属性约简； p = q ：k k = f l a y e r ( p ) ： q l = 上一层结点头指针地址： w h i l e ( q l 一 n e x t ! = n u l l ) i f ( f s x g ( q ，q l 一 n e x t ) = = 1 ) q 2 = q l 一 n e x t ：q l 一 n e x t = q l 一 n e x t 一 n e x t ： f r e e ( q 2 ) ： e l s eq l = q l 一 n e x t ： ) ) q = q 一 n e x t ： k = f l a y e r ( q ) ： i f ( ( p ! = n u l l ) ( ( k k + 2 ) 。由题设知，对于任意一个乙e p o s c 缈，d ) 在【，中总有一个对像ze x lv ( x ，d ) d ) 使得，也，cu d ) = f “，cu d ) ，反之亦然， 显然在第一种情况下，m 。；m i ； 第二种情况：在u 中m 2 一 优ke p o s c ，d ) ，z fe n e g c ，d ) ，f ( z f ，d ) 乒v ( z ，d ) ，在 u 中m ：= 枷j j1 0 ，u ，f “，d ) d ，d ) = d 。根据题设可知对于任意一个 z fe n e g c ，d ) ，在u 中总有一个e x if ( x ，d ) = d ) 使得f ( z ，c ) = f ( x j ，c ) ，对于任 意一个乙e p o s c ，d ) ，在【厂中总会有一个te x if ( x ，d ) 乒d ) 与之相同，就是说在第 二种情况下在u 中任意两个对像乙p o s c ，d ) ，z ，_ n e g c 缈，d ) ，若产生差别矩阵元素， 那么在u 中有两个对像te x if ( x ，d ) d 。) ，t 缸lf ( x ，d ) = d 会生成一个与之相 同的差别矩阵元素，反之在第二种情况下若u 中生成一个差别矩阵元素，那么在u 中 总会有一个差别矩阵元素与之相同。对于任意一个z ，p o s c ，d ) ，在第二种情况下由 引理4 1 可知若在u 中有l n 个属于负域的条件等价类那么至少产生1 n 个差别矩阵元 素，引理4 2 可知任意一个乙p o s c ，d ) ，跟所有的z ，堙c 缈，d ) 会生成i n 个不同 的差别矩阵元素；显然在u 。中对于任意一个0e x if ( x 。，d