改进的属性频率约简算法

改进的属性频率约简算法

0属性约简算法厚集理论是波兰哲学家j.pawlak在1982年提出的一种智能决策分析数学工具。它是研究不完整,不确定知识和数据的表达、学习、归纳的理论方法。粗糙集目前主要被广泛地应用与数据挖掘、人工智能、模式识别、网页分类、故障诊断和专家系统等领域。属性约简是粗糙集理论中重要的核心内容之一。属性约简主要目的是保持知识库分类能力不变的条件下,删除其中不相关或不重要的属性,从而简化原有的系统。虽然Wond等已经证明找出一个决策表的所有约简和最小约简是NP-hard问题,但是利用启发式信息减小搜索空间,还是能得到一个相对最优的约简。以基于可辨识矩阵的属性频率约简算法为基础,引入强等价集概念,以属性在可辨识矩阵中出现的次数越多,其重要性越大为启发式信息。提出一种新的有效的属性约简算法,该算法可以处理当属性频率相同时,对决策表的属性约简可以高效准确的进行。1相关概念和证明1.1aa,vb,av形式上,四元组S=(U,A,V,f)是一个知识表达系统,其中U为对象的非空有限集合,称为论域;A为属性的非空有限集合;V=a∈∪AVa,Va是属性a的值域;f为U×A※V是一个信息函数,它为每个对象的每个属性赋予一个信息值,即对于所有的a∈A,x∈X,f(x,a)∈Va。知识表达系统也称为智能系统。通常也用S=(U,A)来代替S=(U,A,V,f)。1.2q作为约简的定义在信息系统S中,对于PC,则P在S的不可分辨关系IND(P)定义为:定义1:设Q⊆P,如果Q是独立的,并且IND(Q)=IND(P),则称Q是P的一个约简。P中所有必要关系的集合称为P的核,用CORE(P)来表示。其中:i,j=1,2,…,n。1.4区分矩阵中其它项的交为空设a∈A,如果存在某一集合B⊆[a],则称集合B是属于a的强等价集。定理2:A的子集B⊆A是强等价集的充分必要条件是:B被区分矩阵中2个或2个以上项同时包含,且B与区分矩阵中其它项的交为空。定理3:如果C是一个约简,B是强等价集,且{a,b}∈B,则{a,b}不包含于C。此定理可用反证法证明,证明过程如下:证明:假定C是一个约简,且有{a,b}⊆C因为{a,b}∈B且B是强等价集,所以有Dis({a})=Dis({b}),于是有Dis(C-{a})=Dis(a)即IND(C-{a})=IND(C),这与C是一个约简相矛盾,因此应有{a,b}不包含于C。可见,任何一个约简最多只能包含强等价集中的一个属性,简而言之,强等价集中的属性是可以约简的。2基于可识别矩阵属性频率的约简化算法2.1基于价值分析的属性区分胡可云博士提出关于属性频率有两种重要的启发式思想:(1)属性在可辨识矩阵中出现的次数越多,该属性的重要性越大;(2)在可辨识矩阵中属性项越短,属性的重要性越大。由思想(2)可知:在可辨识矩阵中,可能会有一些只有1个属性的属性项,则这个惟一的属性一定是核属性,可直接把它加入到约简集中。提出一种新的计算属性频率的函数:在文献中,算法的缺陷在于不能很好地解决出现2个属性频率相同时的情况。针对这个问题,这里引入强等价集概念对属性进行区分。定理2表明强等价集中的属性对分类具有相同的重要性。利用定理3判断,当属性频率相同时是否有属性包含在强等价集中,可以保留出现在强等价集中的某个属性去掉其他属性。2.2属性频率约简的使用,在一般输入:决策表S=(U,C∪D,V,f),其中C={a1,a2,…,an};输出:决策表的约简集Red。(1)把决策表S转化成相应的可辨识矩阵M,并初始化候选约简集合Red=Ø,令counterai=0;(2)将可辨识矩阵中属性组合数为1的条件属性(核属性)直接加到约简集Red中,去掉含有核属性的属性项;(3)利用属性频率函数g(ai)对剩余属性项中的各属性计算属性频率。判断是否有属性频率相同的属性,有则转(4),否转(5);(4)对有相同属性频率的属性用定理2判断是否为强等价集,若是则在可辨识矩阵M中保留强等价集中任一属性去除其他属性。否则转(5);(5)找出属性频率最高的属性记作a1则Red=Red∪{a1},去掉可辨识矩阵中含有属性a1的属性组合;(6)判断可辨识矩阵是否为Ø,是结束,否则转(3)。显然,该算法给处理具有相同属性频率的决策表属性约简提供了较好的方法。大量数据表明遇到出现相同属性频率的情况非常多,所以该算法的实用性很广泛。与文献的算法相比,改进的基于属性频率的算法的实现对条件属性的更优的约简,其计算的主要时间花费在计算g(ai)上,为O(|C||U|2),而原算法的时间复杂度亦为O(|C||U|2),可见新的算法在保持计算的时间复杂度不变的前提下,得到更精确的约简结果。3强等价集的建立表1是一个信息系统。应用这里改进算法对该信息系统进行属性约简。式(2)为可辨识矩阵:式(3)为去掉核属性后的可辨识矩阵:表1变换成对应的可辨识矩阵,得式(1)所对应的可辨识矩阵。式(2)是在式(1)的基础上由算法第(2)步得到P为核属性直接加入到约简Red中后,去掉含有P的属性项得到化简后的新可辨识矩阵;在新的可辨识矩阵中可以得出属性B,M频率一样,g(B)=g(M)=12.33,{B,M}有可能是强等价集,此时再利用定理1求出原辨识矩阵的强等价集为{B,M},根据强等价集的定理2在可辨识矩阵中可以去掉M保留B,最后得到的约简合{P,B}。再去掉含有B的属性项,此时可辨识矩阵为则算法结束。而按照文献中的算法得到的约简集合{P,B,M},又由定理2中关于强等价集的性质中可知,含在强等价集中的属性是可以约简的,所以{P,B,M}是最后的约简结果。实例证明新算法可以实现更加有精确的数据属性约简。4属性约简的存储及约简划分由于现实信息系统的数据复杂度很高,出现相同频率属性的几率很大,所以在基于粗糙集属性频率的约简算法的基础上,引入强等价集概念,较好地解决了出现相同属性频率时属性约简的问题,具有一定的实际意义和应用价值。与原算法相比,在保持计算速度保持不变的前提下实现了对信息系统更为精确的属性约简。IND(P)={(x,y)∈U2|a∈P,a(x)=a(y)}IND(P)把对象集U划为k个等价类,记为U/P={X1,X2,…,Xk}。定理1:簇集P的核等于P的所有约简的交集。即CORE(P)=∩RED(P)。1.3属性axj令决策表系统