基于相对熵的决策表连续属性离散化算法(1)..doc

基于相对熵的决策表连续属性离散化算法(1)    ,并据此对条件属性按照属性重要性从小到大排序,然后按排序后的顺序,考察每个条件属性的所有断点,将冗余的断点去掉,,计算简单,算法的时间复杂性为O(3kn2)。关键词相对熵;互信息;连续属性;离散化;决策表    1引言    波兰科学家Pawlak提出的粗糙集(Roughset)理论[1,2]是一种新型的处理模糊和不确定知识的数学工具,目前已经在人工智能、知识与数据发现、模式识别与分类、故障检测等方面得到了较为成功的应用。    在运用粗糙集理论处理决策表时,(如浮点数),则在处理前必须进行离散化处理,而且即使对于离散数据,有时也需要通过将离散值进行合并(抽象)得到更高抽象层次的离散值[2]。该文形式化地描述了决策表的离散化问题,利用相对熵定义了属性的重要性度量,提出了基于相对熵的决策表离散化算法,并分析了该算法的时间复杂度,最后用例子说明该算法的离散化过程。2 基本概念    应用粗糙集理论实现知识获取和数据分析通常是对决策表进行处理,为此首先给出决策表的定义.    定义1. 一个决策表是一个由四元组T=(U,R,V,f)构成的知识表达系统,其中U是对象的集合,=C∪D是属性的集合,=是属性的取值范围构成的集合,:U×R→V是信息函数,≠Φ.    在本文讨论中假设决策属性值为离散值,连续属性变量仅出现在条件属性中,不失一般性,以下仅考虑单个决策属性的决策表。    设T=(U,R,V,f)是一个决策表,其中U={x1,x2,…,xn}为论域,R=C∪{d},C={C1,C2,…,Ck}为条件属性集合|C|=k,{d}为决策属性,设决策种类的个数为r(d)。属性a的值域Va=[la,ra]上的一个断点可记为(a,c),其中a∈R,c为实数值。在Va=[la,ra]上的任意一个断点集合:Da={(a,c1a),(a,c2a),…,(a,ckaa)}定义了Va上的一个分类Pa:Pa={[c0a,c1a),[c1a,c2a),…,[ckaa,cka1a]}la=c0a<c1a<c2a<…<cka1a=ra    Va=[c0a,c1a]∪[c1a,c2a]∪…∪[ckaa,cka1a]    断点集合Da将属性a的取值分成ka1个等价类,这里每一个cka就称为一个断点,离散化的目的就是对所有连续属性都找到适宜的断点集,因此,任意的P=定义了一个新的决策表:    Tp=(U,R,Vp,fp),fp(xa)=if(xa)∈[cia,ci1a]    对于x∈U,i∈{0,1,2,…,Ka},即经过离散化之后,原来的决策表被新的决策表所代替,且不同的断点集将同一决策表转换成不同的新决策表。    从粗糙集的观点看,离散化的实质是在保持决策表分类能力不变,即条件属性和决策属性相对关系不变的条件下,寻找合适的分割点集,对条件属性构成的空间进行划分。评价属性离散化的质量,主要看分割