资源描述：
《一种改进的基于区分矩阵的属性约简算法.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、一种改进的基于区分矩阵的属性约简算法张永平李娜（中国矿业大学计算机科学与技术学院，江苏徐州221008）摘要：以属性在区分矩阵中出现的频率作为启发，对HORAFA算法做了一些改进。引入二进制可辨识矩阵，对区分函数进行简化，求出相对核。以相对核为基础，加入属性重要性最大的属性，直到不能再加。在此基础上，加上反向消除的过程，保证了算法的完整性。关键词：粗糙集；属性约简；区分矩阵；二进制可辨识矩阵中图法分类号：TP311文献标识码：AAnewalgorithmofattributereductionbasedondiscerniblymatrixZHANGYong-pingLINa(Sc
2、hoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,221008,China)Abstract：Thepaperlearnssomethingfromthefrequencyofattributesappearedinthediscerniblymatrix,andmakesprogressontheHORAFA.Leadbinarydiscerniblymatrixin,andmakethediscerniblyfunctionmoresimplify,andthenfindthecore
3、.Thealgorithmaddsthemostimportantattributeintothecoreuntilcan’taddanymore.Thenaddaprocessofbackwardeliminationtomakesurethecompletenessofalgorithm.Keywords：Roughsets;attributereduction;discerniblymatrix;binarydiscerniblymatrix一、引言粗糙集理论是波兰数学家Z.Pawlak在20世纪80年代初首先提出的一种可以分析模糊和不确定问题的数学理论［１］，目前正在被广泛
4、应用于机器学习、决策分析、过程控制、模式识别和数据挖掘等领域。属性约简是粗糙集理论中所研究的热门问题之一，通过属性约简，可以剔除知识库中的冗余知识（属性），发现知识库中隐含的关联和规则，帮助人们做出正确简捷的决策。约简通常不是唯一的，约简中属性个数的多少直接影响着属性值的约简过程和决策规则的繁简。二、粗糙集理论的基本概念粗糙集理论的特点是不需要预先给定某些特征或属性的数量描述，而是直接从给定问题的描述集出发，通过不可分辨关系（等价关系）确定给定问题的近似域，从而找出该问题中的内在规律。下面先给出粗糙集理论中的基本概念［２］。定义2-1设S=（U,A,V,f）是一个信息系统，又设C,
5、D∈A且C∩D=,C∪D=A分别称C和D为A的条件属性集和决策属性集，如此的信息系统S称为决策表，记为T=(U,C,D,V,f)。定义2-2设S=（U,A,V,f）是一个信息系统，A中所有必要的属性组成的集合称为属性集A的核，记为core（A）。定义2-3设S=（U,A,V,f）是一个信息系统，PA，如，ind（P）=ind（A）并且P是独立的，则称P是A的一个约简（对决策表称为相对约简）。可以证明核是约简的交集。定义2-4区分矩阵[2]：给定一个信息系统S=(U,A,V,f),A=C∪D是属性集合，C，D分别是条件属性和决策属性。区分矩阵M=(mij)定义为：mij=其中a(x)
6、是元祖x在属性C上的取值，D（x）是x在决策属性D上的取值[2,3]。定义2-5二进制可辨识矩阵：设决策表为T=（U,C,D,V,f），其中U={u1,u2,……,un},C={c1,c2,……,cn},D={d}。则决策表T对应的二进制可辨识矩阵MT构造如下[2]。矩阵MT的一列对应一个条件属性，共有m列；每一行对应论域中的一个对象对（up,uq），且d(up)d(uq)，即这一对象对属于不同的决策类。MT至多有n(n-1)/2行，即每一个对象都对应一个决策类。设矩阵中某一元素m((p,q),i)所在行对应对象对(up,uq)，所在列对应条件属性ci，m((p,q),i)=二进制
7、可辨识矩阵MT直接描述了每个属性对论域中对象的分辨情况，反映了T中蕴含的知识。在MT中某个元素为1或0，表示所在的行属于不同决策类的对象up，uq，在条件属性ci下可分辨与不可分辨。定理1若二进制可辨识矩阵中某一行只有一个元素为1，其余元素为0，则元素1所在列对应某个属性，所有这样的属性构成决策表条件属性集的相对核，若没有这种行，则相对核为空。三、HORAFA算法HORAFA算法[4]利用属性在区分矩阵中出现的频率作为启发，从而对信息系统进行约简。它完全摆脱了对原来信
