基于相对熵的决策表连续属性离散化算法

《基于相对熵的决策表连续属性离散化算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果基于相对熵的决策表连续属性离散化算法摘要该文提出了一种新的决策表连续属性离散化算法.首先使用相对熵来度量条件属性的重要性,并据此对条件属性按照属性重要性从小到大排序,然后按排序后的顺序,考察每个条件属性的所有断点,将冗余的断点去掉,从而将条件属性离散化.该算法易于理解，计算简单,算法的时间复杂性为O(3kn2)。关键词　相对熵;互信息;连续属性;离散化;决策表1引言波兰科学家Pawlak提出的粗糙集(Roughset)理论[

2、1，2]是一种新型的处理模糊和不确定知识的数学工具,目前已经在人工智能、知识与数据发现、模式识别与分类、故障检测等方面得到了较为成功的应用。在运用粗糙集理论处理决策表时,要求决策表中的值用离散数据表示.如果某些条件属性或决策属性的值域为连续值(如浮点数),则在处理前必须进行离散化处理,而且即使对于离散数据,有时也需要通过将离散值进行合并(抽象)得到更高抽象层次的离散值[2]。该文形式化地描述了决策表的离散化问题,利用相对熵定义了属性的重要性度量，提出了基于相对熵的决策表离散化算法,并分析了该算法的时间复杂度，最后用例子说明该算法的离散化过程。2　基本概念应

3、用粗糙集理论实现知识获取和数据分析通常是对决策表进行处理,为此首先给出决策表的定义.课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果定义1.　一个决策表是一个由四元组T=(Ｕ,Ｒ,Ｖ,ｆ)构成的知识表达系统,其中Ｕ是对象的集合,也称为论域.Ｒ=Ｃ∪Ｄ是属性的集合,子集Ｃ和Ｄ分别被称为条件属性集和决策属性集.V=是属性的取值范围构成的集合,其中Ｖr是属性ｒ的值域.

4、ｆ:Ｕ×Ｒ→Ｖ是信息函数,它指定Ｕ中每一个对象各个属性的取值.Ｄ≠Φ.在本文讨论中假设决策属性值为离散值,连续属性变量仅出现在条件属性中,不失一般性,以下仅考虑单个决策属性的决策表。离散化问题的描述设T=(Ｕ,Ｒ,Ｖ,ｆ)是一个决策表,其中Ｕ={ｘ1,ｘ2,…,ｘｎ}为论域,Ｒ=Ｃ∪{ｄ},C={C1,C2,…,Ck}为条件属性集合

5、C

6、=k,{d}为决策属性，设决策种类的个数为r(d)。属性a的值域Va=[la,ra]上的一个断点可记为(a,c),其中a∈R,c为实数值。在Va=[la,ra]上的任意一个断点集合：Da={(a,c1a),(a,c2a),

7、…,(a,ckaa)}定义了Va上的一个分类Pa：Pa={[c0a,c1a)，[c1a,c2a)，…，[ckaa,cka+1a]}la=c0a1a2aka+1a=raVa=[c0a,c1a]∪[c1a,c2a]∪…∪[ckaa,cka+1a]断点集合Da将属性ａ的取值分成kａ+1个等价类，这里每一个cka就称为一个断点，离散化的目的就是对所有连续属性都找到适宜的断点集,因此,任意的P=定义了一个新的决策表:Tp=(U,R,Vp,fp)，fp(xa)=if(xa)∈[cia,ci+1a]课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出

8、结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果对于x∈U,i∈{0,1,2,…,Ka},即经过离散化之后,原来的决策表被新的决策表所代替,且不同的断点集将同一决策表转换成不同的新决策表。从粗糙集的观点看,离散化的实质是在保持决策表分类能力不变,即条件属性和决策属性相对关系不变的条件下,寻找合适的分割点集,对条件属性构成的空间进行划分。评价属性离散化的质量,主要看分割点的选择和多少,以及保持信息系统所表达的样本之间的“不可分辨关系”

9、。最优离散化,即为决策表寻找最小(最优)的断点集是一个NP-hard问题,为此必须寻找某种启发式算法，人们提出了许多启发式算法，可参考文献[2，3]，该文利用决策属性相对于条件属性的相对熵作为启发式算法。2.知识的信息量和相对熵下面将信息论中信息量和相对熵[4-6]的概念引入到信息系统中。定义2[5，6]设K=(U，R)是一近似空间,R在U上的划分(等价关系)为U/IND(R)={R1,R2,…,Rn},知识(属性集合)R的信息量(也称为信息熵)定义为:；其中=U-Ri,

10、Ri

11、/

12、U

13、表示等价类Ri在论域U上的可能性(概率)，

14、

15、/

16、U

17、表示Ri的余集在

18、论域U上的可能性,也即不属于Ri的概率。定义3[6]设U为论域，K