资源描述：
《基于粗集可辨识矩阵的属性频率约简算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、http://www.paper.edu.cn基于粗集可辨识矩阵的属性频率约简算法逄玉俊，李爽沈阳化工学院计算机科学与技术学院，沈阳（110142）E-mail：vivian830124@163.com摘要：针对目前在对信息系统进行属性约简过程中存在属性频率值相同的问题，本文在基于可辨识矩阵属性频率约简算法的基础上，引进强等价集概念，以属性在可辨识矩阵中出现的次数越多其重要性越大为启发式信息，利用强等价集中的属性是可以约简的特性，在属性频率约简过程中判断具有相同属性频率的属性是否最终包含在核属性集里，提出改进的属性频率约简算法。通过理论和实例的
2、分析证明，该算法在保持时间复杂度不变的情况下，处理具有相同属性频率的信息系统的属性约简的准确性得到提高，与原算法相比，改进后的算法可以得到一个更为精准的约简结果。关键词：粗糙集，可辨识矩阵，强等价集，属性频率中图分类号：TP3911．引言粗糙集理论是由波兰数学家Z.Pawlak在1982年提出的一种智能决策分析数学工具。它是研究不完整，不确定知识和数据的表达，学习，归纳的理论方法。粗糙集目前主要被广泛[1]的应用到数据挖掘，人工智能，模式识别，网页分类，故障诊断和专家系统等领域。属性约简是粗糙集理论中重要的核心内容之一。属性约简主要目的是保持知
3、识库分类能力不变的条件下，删除其中不相关或不重要的属性，从而简化原有的系统。虽然Wond等已经证明找出一个决策表的所有约简和最小约简是NP-hard问题，但是利用启发式信息来减小[2]搜索空间，还是能得到一个相对最优的约简。本文以基于可辨识矩阵的属性频率约简算法为基础，引入强等价集概念，以属性在可辨识矩阵中出现的次数越多其重要性越大为启发式信息。提出一种新的有效的属性约简算法，该算法可以处理当属性频率相同时，对决策表的属性约简可以高效准确的进行。2．相关概念和证明2.1决策表形式上，四元组SUA=(),,,Vf是一个知识表达系统，其中U：对象的
4、非空有限集合，称为论域；A：属性的非空有限集合；VV=∪，V是属性a的值域;f:UAV×→aAa∈a是一个信息函数，它为每个对象的每个属性赋予一个信息值，即对于所有的[3]aAxXfxaV∈∈,,,()∈a。知识表达系统也称为智能系统。通常也用SUA=(,)，来代替SUA=(),,,Vf。2.2约简和核在信息系统S中，对于PC⊆，则P在S的不可分辨关系INDP()定义为：2INDP(){(,)=∈∀xyU
5、a∈=Pax,()()}ay。INDP()把对象集U划为k个等价类，记为U/P=X,{X,XX,L,}。123k[9]定义1：设QP⊆，如果
6、Q是独立的，并且INDQ()=INDP()，则称Q是P的一个约简。-1-http://www.paper.edu.cnP中所有必要关系的集合称为P的核，用COREP()来表示。定理1：簇集P的核等于P的所有约简的交集。即COREP()=∩REDP()。2.3可辨识矩阵令决策表系统SU=<,,,,RVfRCD>=∪是属性集合，子集Pai=={
7、1,,Lm}i和Dd={}分别称为条件属性和决策属性集，Uxxx={,,,L}是论域，ax()是样本x12nijj在属性a上的取值。Cij(,)表示可辨识矩阵中第i行和第j列的元素，则可辨识矩阵C定iDD[
8、4]义为:⎧⎪{aaPaxaxdxdxkk
9、(∈∧ki)≠kj()},()i≠(j);Cij(,)=⎨D⎪⎩0,,dx()ij=dx().其中ij,1=,2,,Ln2.4强等价集[5]设aA∈，如果存在某一集合B⊆[a]，则称集合B是属于a的强等价集。定理1：A的子集B⊆A是强等价集的充分必要条件是：B被区分矩阵中2个或2个以上项同时包含，且B与区分矩阵中其它项的交为空。定理2：如果C是一个约简，B是强等价集，且{ab,}∈B，那么{ab,}不包含于C。[5]此定理可用反证法证明，证明过程如下：证明：假定C是一个约简，且有{ab,}⊆C因为{a
10、b,}∈B且B是强等价集，所以有Disa(){}=Disb(){}，于是有DisC()−={a}Disa()即INDC()−={a}INDC()，这与C是一个约简相矛盾，因此应有{ab,}不包含于C。可见，任何一个约简最多只能包含强等价集中的一个属性，简而言之，强等价集中的属性是可以约简的。3基于可辨识矩阵的属性频率约简算法3.1算法思想[6]胡可云博士提出关于属性频率有两种重要的启发式思想：（1）：属性在可辨识矩阵中出现的次数越多，该属性的重要性越大（2）：在可辨识矩阵中属性项越短，属性的重要性越大。由思想（2）可知：在可辨识矩阵中，可能会有
11、一些只有一个属性的属性项，则这个唯一的属性一定是核属性，可直接把它加入到约简集中。本文提出一种新的计算属性频率的函数：nga()ia=count∑()
