资源描述：
《属性约简中核的计算方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、属性约简中核的计算方法刘山!中国民航学院计算机系"天津(""(""#B:C,7D#D72EF,8G0H42I0H42$.4C摘要属性约简是粗糙集理论研究的主要内容之一"该文首次采用了分治策略"提出了一个新的属性约简方法"将在计算整个全域上的属性约简问题转化为计算在相应划分的子区域上属性约简问题$将原有计算核的算法复杂度为
2、%:!!""#%%&:"%"":"!文献标识码K中图分类号LM("%!"#$%&$#’(")*(+(’,)-).!’’*/0&’(1(-&%’/).2/&3,#.*N4CO230/P0O3$"N4DD0Q04RNK’N"L7,8S78(""(""%!04’*#%’#K8K33/7-230T012.37487R3F0C,78.483083?F7.F3F0T42QFE03E3F04/HE32170E$LF7EO,O0/R7/E3DH,1U,8.0E,80?K33/7-230T012.3748C03F4134,14O317U710,
3、81.48V20/$K33/7-230T012.3748O/4-D0C78C,./4.4EC7E3/,8,D,3017834K33/7-230T012.3748O/4-D0C78E2-14C,78$W/7Q78,D.,D.2D,30.4/0*K%12OD7.,3010Q/00
4、0T012.3748.4CO23,-7D73H7E7CO/4U01$5(67)*-4#/42QFE03E",33/7-230T012.3748"17U710:,81:.48V20/%引言了属性约简的可计算性!属性约简是粗糙集理论的核心问题之一!所谓属性约简就是在保持知识库分类能力不变的条件下"删除其中不相关或不(属性约简的分治算法重要的知识!在属性约简中有两个基本的概念#约简$/012.3%和对于一个知识表达系统’(*)"2"+",%"其中"属性集2!考核$.4/0%&核的重要性在于两个方面#首先它是所有约简的计虑2对)的划分
5、#781*2%9;4%"4!",,"45<则)(&47*7(%"!"算基础"因为它包含于所有约简之中’其次"核是在属性约简中,"5%"可以证明#如果存在7"-在47上是不可以约简的"则-不能消去的知识特征的集合&在)上也是不可以约简的&定理%设知识表达系统’(*)"2"+",%"其中2是属性集!属性约简的有关概念5%6合&2对)的划分分别是781*23-%9;4%"4!",,"45<和781*2%定义%令!为一族等价关系""!!"如果781$!%97819;8%"8!",,"89<"如果存在47*79%"!,"5%"使781*
6、23-%47%$!#"%则称"为!中不必要的’否则"称"为!中必要的&如果781*2%47的充分必要条件是-!.4/0*2%&对于每一个"!!都为!中必要的"则称!为独立的’否则称证明#如果对于-!.4/0*2%"则在全域)上781*23-%%!为依赖的&781*2%&则一定存在47(781*23-%47*7(%"!,"5%"使781*23-%47定义!设$"%&如果&是独立的且781$&%9781$%%"则%781*2%4"反之亦然&7称&为%的一个约简&%中所有必要关系组成的集合称为%的核"记作.4/0$%%&可以证明.4
7、/0$%%9#/01$%%"其中/01$%%表#算法举例示%的所有约简&设)9;%"!"("#")"*"&"+<"属性集29;-":";<&对于一个知识表达系统’($)"*"+",%计算条件属性*的表%核.4/0$*%需要逐一地计算对$-!*"781$*:;-<%%781$*%是’%!(#)*&+否成立&目前常用的完备算法是基于差别矩阵的约简规则,%"!%%!!"$=>4?/48%&核是差别矩阵中所有单元素组成的集合"即.4/0-"%"%"!%%$*%9;-!./!$0"1%9;-<"其中"0"1!)<&其算法的复杂度为@2/
8、/)/!&.!%""!"%%由于一个知识表达系统的@’@往往非常大"所以讨论在此算法可以验证-!.4/0*2%#由于781*2%9;;%<";!"&<";("*<";#<"基础上的改进有着十分现实的计算意义&该文讨论了在781;)"+<<"为此首先考虑#23-对)的划分#78
