资源描述：
《论文格式参考(一种基于粗糙集的启发式属性约简算法)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、一种基于粗糙集的启发式属性约简算法学号班级姓名摘要：对现有丿［发式属性约简算法进行分析，应用反例说明一般启发式算法求得的相对约简屮仍存在冗余属性的不足。针对这一问题，提出一种改进的启发式属性约简算法。该算法以条件信息爛作为启发信息，在算法中加入消除冗余的二次约简过程，并给岀一些特殊情况下的处理方法。最后通过实例分析，验证了改进的算法具有较好的约简效果。关键词：粗糙集；条件爛；属性约简；启发式算法；核0引言在海量信息系统中，其屈性和实例数量非常巨大，其中的屈性并不是同等重要的，甚至有的属性是兀余的，这就使属性约简变的非常必要。属性约简在保持信息系统分类和决策
2、能力不变的前提下，可以通过其较好地剔除兀余属性，并形成精简的规则库以帮助人们做出正确且简洁的决策。属性约简是粗糙集理论(RoughSetTheory)研究的核心内容之一。Wong.S.K.M和Ziarko.W己经从计算复杂性的角度证明了寻找最小约简是NP问题。解决这类问题的方法一般采用启发式算法，即在算法屮加入启发信息，缩小搜索空间，最终得到一个最优或近似最优的解。苗夺谦山等利用属性的互信息作为启发信息来构造启发式算法，但该启发式算法对于求取相对约简是不完备的，即最后求得的相对约简中仍有冗余属性存在的可能。本文通过对文献［1］启发式属性约简算法的研究，提出
3、了二次约简的概念，对属性集进行二次约简，以消除初次约简后仍可能存在的冗余屈性；并以条件爛作为启发信息，构造了一种新的启发式属性约简算法。理论分析与实验结果表明，该算法是正确、有效的。1粗糙集相关理论在决策表中，人们关心的是哪些条件属性对于决策更重要，本文利用条件嫡的大小作为属性重要性的度量；本节给出它的基本概念，及判断冗余属性的判定定理。定义1信息系统信息系统(InformadonSystem)可由四元组S=(U,Q,V,f)表示。其中U是对象集合，即论域；Q是属性集合；V二IJ匕，V,,是属性q的值域；f是一个信息函数，即对VxGU,qwQ,有f(y)G
4、决策信息系统是信息系统的子集，其属性集Q二CUD,C为条件属性集、D为决策属性集。定义2⑶条件嫡设U为一个论域，P、Q为U上的两个等价关系族，可以认为U上任一属性集合是定义在U上的子集组成的&-代数上的一个随机变量，其概率分布可通过如下方法來确定。设P、Q在U上导出的划分分别为X、Y：X={Xi,X2・・％}；Y={YhY2-Yj；则P、Q在U的子集组成的6-代数上定义的概率分布为：[X：p]=X
5、x2..0XJp(X2)•乙1W)[Y：p]=其中p(X/)=
6、X/
7、/
8、U
9、,y=l,2—n；P(Y./)=
10、Yy
11、/
12、u
13、,j=l,2—/»；符号
14、E
15、表示
16、集合E的基数。知识(属性集合)Q相对于知识(属性集合)P的条件燔定义为：H(Q丨P)=-工P(X辽p(YjXJ10g3(XIxJ)•/=!z=l其中p(Yj
17、X/)=
18、YynX/
19、/
20、X/
21、,>1,2…III.条件爛H(Q
22、PU{a})的值越小，说明在已知属性集P的条件下，属性a对于属性集Q越重要。定理⑶设U为一个论域，P是U上的一个条件属性集合，D是决策属性集，且论域U是在P上相对于D一致的，则P中的一个属性a是P相对于决策属性集D冗余的充分必要条件为H(D
23、P)=H(D
24、P—{a})o2文献［1］算法的讨论2・1算法的描述与不足该算法是一种基于互信息
25、的知识相对约简算法，从条件属性集C相对于决策属性集D的核开始，利用互信息作为启发信息逐步增加不可缺少的属性，从而得到C相对D的一个相对约简。下面是该算法的具体步骤：算法1stepl计算决策表T中条件屈性C与决策屈性D的互信息I(C,D)；step2计算C相对于D的核Co=CORE。(C)；一般来说，I(Co，D)<1(C,D)；有时Co=0,则I(C(),D)=0；step3令B=C(),对条件属性集C-B重复：①对每个属性peC—B,计算条件互信息I(p,D
26、B)；②选择使条件互信息I(p,D
27、B)最大的屈性，记作p(若同时有多个属性达到最大值，则从屮选
28、取一个与B的属性值组合数最少的属性作为p)；并且BUBU{p}；③若I(B,D)=1(C,D),则终止；否则，转①；step4最后得到的B就是C相对于D的一个约简。上述算法通过互信息作为启发信息來缩小搜索空间，提高了算法的效率，最终得到一个最优或近似最优解°但是该算法存在一些不足之处：如(1)通过该算法求得的相对约简中可能还存在一些冗余属性，下面将会通过反例来加以说明；(2)在step2+求得C相对于D的核Co=COREd(C),没有先对I(C(),D)与I(C,D)的值进行比较。若相等则程序应该结束，输出相对约简B二Co,否则才进入下一步。该算法的这些不
29、足之处将在算法2中得到改进。2.2反例表1关于消化道疾病的医疗诊断
