基于改进属性频度的属性约简算法

《基于改进属性频度的属性约简算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第25卷第5期电力科学与工程Vo1．25．No．52009年5月ElectricPowerScienceandEngineeringMay，2009基于改进属性频度的属性约简算法欧芳芳，马晓辉，马利芳，王翠茹(1．华北电力大学计算机科学与技术学院，河北保定071003；2．邯郸峰峰矿区供电公司，河北邯郸056200)摘要：对粗糙集理论的基本概念和相关定理进行了研究，针对目前常用的属性频度约简算法的缺陷，提出了一种改进算法；通过实例对改进算法的有效性进行了分析和验证。关键词：粗糙集；属性约简；可辨识矩阵中图分类号：TP391文献标识码：A有认知能力的主体

2、的分类能力，并用等价关系形式0引言化表示分类。定义1：1个信息系统可表示为1个4元组粗糙集n最初由波兰数学家于1982年提出，=

3、约简是粗糙集理论的核心内容之一，它要A=COD，且CAD=(2j，其中C和D分别为条件属求在保持知识库的分类和决策能力不变的条件下，性集和决策属性集，则称该信息系统为决策系统或删除不相关或不必要的属性。人们期望找到最小约决策表。简，但由于属性组合的爆炸问题，导致了属性约简定义3：对于的任何属性子集，其在上是一个NP—hard问题。目前，主要的解决办法的不可分辨关系(又称等价关系)为是引入启发信息到属性约简中，减小样本的搜索空)={)∈Ux：F(x，口)=，，口)，VaEB}(2)间，从而达到提高约简效率的目的。定义4：令P和Q为中的等价关系，Q的本文提

4、出基于可辨识矩阵的属性频度算法。该P正域为算法以可辨识矩阵中出现次数多少作为属性重要性POSp(Q)=【理(Q)(3)的判断依据，但却存在着缺陷和不足：即当达到最大频度的属性有多个时，从中任选一个添加到核属定义5：设P和Q为中的2个等价关系簇，性中得到的约简，有可能不是决策表的较优约简。且QCp，如果满足：针对这种情况，提出了一种改进算法。最后通过实(1)Ind(P)=Ind(Q)，(2)Q是独立的，则称例验证了改进算法的有效性和可行性。Q是尸的1个约简。显然可知尸可以有很多个约简，尸中所有必要关系组成的集合，称为尸的核，1粗糙集基本理论表示为：Cor

5、e(P)。定理1131tCore(P)=／Red(P)，其中Red(P)表粗集将分类与知识联系在一起，认为知识源于示P的所有约简。收稿日期：2009-01-01．作者简介：欧芳芳(1982一)，女，华北电力大学计算机科学与技术学院硕士研究生第5期欧芳芳，等基于改进属性频度的属性约简算法61可以看出，核是所有约简的计算基础，被解释核属性；第2类是除核属性之外还包含其他条件属为知识最重要部分的特征集合。在知识约简时，它性的属性组合；第3类是不包含核属性的属性组是不能消去的。合。其中第1类是矩阵中属性组合数为1的元素，定义6：设T-(cuD)为1个决策表，I

6、=FI，除该属性外没有别的属性可以区分这2个对象，是对应的可辨识矩阵定义为仁(c⋯决策表的核属性。第3类表明了仅有核属性无法区分其决策的记录。通过可辨识矩阵可以得到决策表c：J【{I∈c人(蜀)≠(而)>，)≠)f4)0，)=)的核，而后以核为基础找出该决策表的约简。目前，比较常用的属性频度算法就是：以式中f，卢1，2，⋯。决策表对应的差别矩阵为基础，通过考虑其中的全显然，可辨识矩阵是沿对角线对称的矩阵，故体属性组合，计算出所有非核属性在差别矩阵中出只需考虑其上三角或下三角即可。根据定义可知，现的次数；若某个非核属性的次数最大，则说明这当2个实例的决策

7、属性取值相同时，它们所对应可个属性在辨别2个决策不同的对象中所起的作用比辨识矩阵的元素取值为0；若不相同，它们所对应较大，所以应首先考虑把它加入到约简集合中，同的可辨识矩阵的元素的取值就是那些可以区分这2时把包含这个属性的所有属性组合删除。个对象的条件属性的集合。下面的算法1就是较常用的属性频度算法。定义7：-i~o(a)为属性a在可辨识矩阵中的算法1属性频度函数，即属性a在可辨识矩阵中出现输入，决策表；输出，约简集。的次数，故可定义为属性a的重要性，即：step1：如果包含连续的属性值，则需离散处(口)=SGF(a，R，D)(5)理，B：(2)，CD

8、，_P：(2)。定义8：设口，b为可辨识矩阵中的2个元素，step2：构造决策表的可辨识矩阵。