基于相似矩阵的折半属性约简算法.doc

基于相似矩阵的折半属性约简算法.doc1 基于相似矩阵的折半属性约简算法摘要针对大多数属性约简算法时间复杂度比较高的问题, 利用粗糙集理论提出了一种新的解决办法, 该方法基于相似矩阵概念, 利用属性在相似矩阵中出现的频率给出了属性重要性的计算公式, 以此作为启发式知识来约间决策表中的冗余属性, 并将折半查询的思想运用到算法中以加快约简的速度。实验表明该算法是简单有效的。关键词粗糙集;相似矩阵;折半属性约简中图分类号: TP18 文献标识码: A 文章编号: 1671-7597 ( 2013 ) 16-0051-01 粗糙集理论是一种能有效地分析不精确、不一致、不完整等各种不完备信息、揭示潜在规律的处理不确定性和模糊性数据的工具。属性约简是粗糙集理论研究的核心内容之一, 到目前为止, 已经提出了多种改进型的属性约简算法。本文提出了一种新的属性约简算法,在文中给出了相似矩阵的定义, 从另一个角度来计算属性的重要性,并且将折半查找的思想运用到算法中,加快了筛选候选属性的速度。 1 基于相似矩阵的折半属性约简算法 算法的基本思想 2 可辨识矩阵主要是从对象与对象之间的差别来研究属性约简。 相似矩阵的定义 cij= {a∈C| xi(a) =xj (a)}, xi(d)≠ xj(d); cij=| ,其他 Cij 代表两个对象之间的相似点,也就是不能辨别对象的属性集。根据相似矩阵的定义, 得到下面的结论: 属性在相似矩阵中出现的次数越多, 在相似矩阵中的项长度越短, 则代表该属性在反映对象相似性上起的作用越大, 因此在区别对象时, 重要性就越小。根据上述观点, 本文基于相似矩阵的属性频率给出了属性重要性的计算公式: F(a)=- 其中,当 a 时, =0 ;否则=1。 card ()表示包含属性的个数。推论 1 :当且仅当 card () =card (c) -1 时, C- 属于核属性。 折半约简概述现在很多约简算法都是从 R=核( core (c)) 开始, 判断 R 是否为一个约简, 是则终止, 否则根据属性的重要性定义, 将重要性最大的一个加入到R 中,再次测试是否为约简,若是则终止,否则,继续上述过程。 算法过程描述 3 本文提出具体过程描述: 输入:一致决策表 S=(U,C∪D,V,F) ,其中 C= {a1 , a2,…, an} 输出:决策表的约简集合 R Step 1 :决策表 S 转换为相应的相似矩阵 M ,求出核属性 core (C), 并计算剩余属性的属性重要度, 然后将剩余属性根据重要度由大到小进行排序,放进数组 Z. Step 2 :初试化 R=core (c) ,如果= ,则执行步骤 step4 ,否则执行步骤 step3 。 Step 3 :初试化 min=1 ; max=card (C) -card ( core (C)) while ( true ){ Tempt=R ; // 保存改变前的 R Mid=min+max/2 ; 将数组 z 中第 min 个到第 mid 个加入到 R 中, 计算; If(<){ If( max-mid<=1 ){①将数组 z 中第 max 个加入 R 中; 4 ②退出循环; // 退出位置一} else { min=mid+1 ; }} Else if(=){ If( max-mid<=1