基于相对熵的决策表连续属性离散化算法
摘要 该文提出了一种新的决策表连续属性离散化算法.首先使用相对熵来度量条件属性的
重要性,并据此对条件属性按照属性重要性从小到大排序,然后按排序后的顺序,考察每个条
件属性的所有断点,将冗余的断点去掉,从而将条件属性离散化. 该算法易于理解， 计算 简
单, 算法的时间复杂性为 O(3kn2)。关键词 相对熵;互信息;连续属性;离散化;决策表 1 引
言 波兰 科学 家 Pawlak 提出的粗糙集(Rough set) 理论 [1，2]是一种新型的处理模糊
和不确定知识的数学工具, 目前 已经在人工智能、知识与数据发现、模式识别与分类、故
障检测等方面得到了较为成功的 应用 。 在运用粗糙集理论处理决策表时,要求决策表
中的值用离散数据表示.如果某些条件属性或决策属性的值域为连续值(如浮点数),则在处理
前必须进行离散化处理,而且即使对于离散数据,有时也需要通过将离散值进行合并(抽象)得
到更高抽象层次的离散值[2]。该文形式化地描述了决策表的离散化 问题 ,利用相对熵定义
了属性的重要性度量，提出了基于相对熵的决策表离散化算法,并 分析 了该算法的时间复
杂度，最后用例子说明该算法的离散化过程。2 基本概念 应用粗糙集理论实现知识
获取和数据分析通常是对决策表进行处理,为此首先给出决策表的定义. 定义 1. 一个决
策表是一个由四元组 T=(Ｕ,Ｒ,Ｖ,ｆ)构成的知识表达系统,其中Ｕ是对象的集合,也称为论
域.Ｒ=Ｃ∪Ｄ是属性的集合,子集Ｃ和Ｄ分别被称为条件属性集和决策属性集. V = 是属性
的取值范围构成的集合,其中Ｖr 是属性ｒ的值域.ｆ:Ｕ×Ｒ→Ｖ是信息函数,它指定Ｕ中每
一个对象各个属性的取值.Ｄ≠Φ. 在本文讨论中假设决策属性值为离散值,连续属性变
量仅出现在条件属性中,不失一般性,以下仅考虑单个决策属性的决策表。 离散化问题
的描述 设 T=(Ｕ,Ｒ,Ｖ,ｆ)是一个决策表,其中Ｕ={ｘ1,ｘ2,…,ｘｎ}为论域,Ｒ=Ｃ∪{ｄ},
C ={C1 , C2,…,Ck} 为条件属性集合|C|=k,{d}为决策属性，设决策种类的个数为 r(d)。属性
a 的值域 Va =[l a,ra]上的一个断点可记为(a,c) ,其中 a∈R,c 为实数值。在 Va=[la ,ra]上的
任意一个断点集合：Da ={(a,c1a),(a,c2a),…,(a ,ckaa)}定义了 Va 上的一个分类 Pa ：Pa
={[c0a,c1a)，[c1a,c2a)，…，[ckaa,cka+1a]}la = c0a<c1a<c2a<… < cka +1a= ra Va
=[c0a,c1a]∪[c1a,c2a]∪…∪[ckaa,cka+1a] 断点集合 Da 将属性ａ的取值分成 kａ+1 个等
价类，这里每一个 cka 就称为一个断点，离散化的目的就是对所有连续属性都找到适宜的
断点集, 因此,任意的 P = 定义了一个新的决策表: Tp=(U,R,Vp,fp)，f
p(xa)=i f(xa)∈[cia,ci+1a] 对于 x∈U,i∈{0,1,2,…,Ka},即经过离散化之后,原来的决策表
被新的决策表所代替,且不同的断点集将同一决策表转换成不同的新决策表。 从粗糙集
的观点看,离散化的实质是在保持决策表分类能力不变,即条件属性和决策属性相对关系不
变的条件下,寻找合适的分割点集,对条件属性构成的空间进行划分。评价属性离散化的质
量,主要看分割点的选择和多少,以及保持信息系统所表达的样本之间的“不可分辨关系”。最
优离散化, 即为决策表寻找最小(最优) 的断点集是一个 NP-hard 问题,为此必须寻找某种启
发式算法，人们提出了许多启发式算法，可 参考 文献 [2，3]，该文利用决策属性相对于
条件属性的相对熵作为启发式算法。 知识的信息量和相对熵 下面将信息论中信息
量和相对熵[4-6]的概念引入到信息系统中。 定义 2[5，6] 设 K=(U，R)是一近似空间
,R 在 U 上的划分(等价关系)为 U/IND(R) ={R1,R2,…,Rn}, 知识(属性集合)R 的信息量(也称
为信息熵)定义为: ； 其中 =U-Ri,|Ri|/|U|表示等价类 Ri 在论域 U 上的可能性(概率)，
||/|U|表示 Ri 的余集在论域 U 上的可能性, 也即不属于 Ri 的概率。定义 3[6] 设 U 为论域
，K1=(U，P)和 K2=(U，Q)是关于 U 的两个知识库，U/IND(P)= {X1,X2,…,Xn},
U/IND(Q)={Y1,Y2,…,Ym}, 知识(属性集合)Q 相对于知识(属性集合)P 的相对熵 E(Q|P)定义为
: P 与 Q 的互信息定义为： 定义中用“相对熵”概念,而不用“条件熵”,完全是式子中已经
没有了条件概率的意义.另外,定义中使用余集来表示,纯粹是为了定理的证明时简便,实际计
算时不必用余集. 性质 1[6] 设 U 为论域，K1=(U，P)和 K2=(U，Q)是关于 U 的两个知识库
，则有：(1) E(Q)=E(Q;P)+E(Q|P) (2) E(P)=E(P;Q)+E(P|Q) (3) E(Q;P)= E(P;Q)性质 2[6] 设
U 为论域，K1=(U，P)和 K2=(U，Q)是关于 U 的两个知识库，U/IND(P)= {X1,X2,…,Xn},
U/IND(Q)={Y1,Y2,…,Ym}, D 是 U 上的一个决策（即 U 上的一个划分）.如果 U/IND(P)
U/IND(Q)，则(1)E(D;P)≥E(D;Q) , (2)E(D|P)≤E(D|Q) 属性重要性度量 Rough 集理论
认为知识是将对象进行分类的能力，属性的重要性是建立在属性的分类能力上的, 为了衡
量属性的重要性程度, 可从表中删除这一属性,再来考察信息系统的分类会产生怎样的变化:
如果去掉属性会相应地改变分类,则说明该属性重要,反之,则说明该属性的重要性低。衡量
属性重要性程度的 方法 较多,有代数方法和信息论方法等[7]，本文利用条件属性相对于决
策属性的相对熵作为度量方法，有关相对熵的一些性质参见文献[6].定义 4 (属性重要性)
设 T =〈U,C∪D,V,f 〉是一个决策表, B C ,则对任意属性 a∈{C-B}的相对于决策属性 D 的重
要性 SGF(a,B,D)定义为: SGF(a,B,D)=E(D|B)- E(D|B∪{a})当 B =Φ 时,简记为 SGF(a,D) =E(D)-
E(D|{a})=E(D;a),则为 a 与 D 的“互信息”。上述定义表明属性 a∈C-B 关于属性集 B 对决策属
性 D 的重要性由 B 中添加{a}后所引起的相对熵的变化大小来度量。SGF(a,B,D)的值愈大,
说明属性 a∈C-B 关于属性集 B 对决策属性 D 愈重要。3 决策表连续属性的离散化
在开始之前首先介绍一下断点的概念，断点是将某个数值型属性的值按照由小到大的
顺序排序，重复的数值只计一次，两个相邻属性值的均值称为一个断点。在离散化之前需
要先生成每个条件属性的断点集。 离散化算法输入：一个决策表 T=（U,A∪{d},V, f）,
其中Ｕ={ｘ1,ｘ2,…,ｘｎ}，A={a1 ,a2,…,ak}输出：离散化的决策表。Step1: 初始化候选
断点集,令 CUT={ Ca1，Ca2，…，Cak },其中 Caj 为属性 ai 的候选断点集 Step2: 根据条件
属性的重要性由小到大对每个条件属性 ai (i=1,2,… ,k) 进行排序,在值相同的情形下,按条
件属性断点个数从多到少进行排序,属性重要性按如下步骤产生：a) 令 B=Φ 是一链表，
用来存储已排过序的属性；b) 对 A-B 中的每一个属性 p，根据定义 7 计算其重要性
SGF(p,B,D)；
