第四章示例学习的实用化 41定量属性的定性化 等宽离散法 2.决策树连续属性值处理(二分离散法) 1)切点法 T 类熵( class entropy)
第四章 示例学习的实用化 4.1 定量属性的定性化 1. 等宽离散法 L 2. 决策树连续属性值处理(二分离散法) 1) 切点法: T 类熵(class entropy)
Ent(s)=-LP(c,, s)log( p(c, s) 类信息熵( (class information entropy) E(A,7;s)=En(s1)+2Em(s2) N S1:切点T左边的例子集S2:切点T右边的例子集.集合s中的 例子数N= 2)界点法 4
= = − k i i i Ent s p c s p c s 1 ( ) ( , )log( ( , )) 类信息熵(class information entropy) ( ) | | ( ) | | ( , ; ) 2 2 1 1 Ent s N s Ent s N s E A T s = + S1 : 切点T左边的例子集 S2 :切点T右边的例子集. |s| 集合s中的 例子数 N=|s| 2) 界点法: T1 T2 T3 T4 T5
3)多切点法 r E(T)-E(T)≤20g2(n+ D=logar maX d/(T) Emin是目前为止得到的最小信息熵,如果 E(Tr)- max dift(Tr)≥Emn则E(T+1)≥Emin Max diff(Tr)随着r的增加单调递减 启发式1:设Em是迄今为止得到的最小信息熵,则从Tr开始下 个需要计算熵的切点是T+s △=max(1 E(T-E max diff (T)
3)多切点法: er er+1 max_ ( ) 2log ( 1) log ( ) ( ) 2 2 r r 1 diff Tr n n r E T E T = + − − + Tr Tr+1 Emin是目前为止得到的最小信息熵,如果 E(Tr)-max_diff(Tr) Emin, 则E(Tr+1) Emin Max_diff(Tr )随着r的增加单调递减. 启发式1: 设Emin是迄今为止得到的最小信息熵,则从Tr开始下一 个需要计算熵的切点是Tr+ ) max_ ( ) ( ) max(1, min − = r r diff T E T E
)Δ与Emn有关,因此被忽略的结点数与属性被处理的顺序有 关,如果最相关的属性被首先处理,Emin就会被早些得到因 此,以后计算中Δ值就会较大所以省略的结点数就多为减少 算法的运行时间最相关的属性应首先被处理 2) Max diff(T是单调递减的所以连续属性排序后,属性值域 的后半部分△值较高 3)通常如果相关属性先被处理,对不相关属性使用启发式1,将 是较有效的 启发式2.对于每个属性A,Tm是其一个切点把例子集分成两个 例子数相等的子集,E(Tm)是Tm的熵,对各属性按E(Tm)从 小到大的顺序使用启发式1进行离散化 3多区间划分 停止标准(最小描述长度) Gain(a,T; s)sg2(N -1)+△(a,Ts) Gain(a, T,s)=Ent(s)-e(a, T,s)
1) 与Emin有关,因此,被忽略的结点数与属性被处理的顺序有 关,如果最相关的属性被首先处理,Emin就会被早些得到,因 此,以后计算中值就会较大,所以省略的结点数就多,为减少 算法的运行时间,最相关的属性应首先被处理. 2) Max_diff(Tr)是单调递减的,所以连续属性排序后,属性值域 的后半部分值较高. 3) 通常,如果相关属性先被处理,对不相关属性使用启发式1,将 是较有效的. 启发式2. 对于每个属性Ai,Tmi是其一个切点,把例子集分成两个 例子数相等的子集, E(Tmi )是Tmi的熵,对各属性按E(Tmi )从 小到大的顺序使用启发式1进行离散化. 3.多区间划分 停止标准(最小描述长度) N T s N N Gain A T s log ( 1) ( , ; ) ( , ; ) 2 + − Gain(A,T;s) = Ent(s) − E(A,T;s)
Ent(s) S En(S)--12En(S2) A(A, T; S)=log2 ( 3-2)-[kEnt(S)-kEnt(,)-k2Ent(s,)I K1k2分别是T左右两边例子的类别数 4. Bayes离散法 设有两类W1和W2 状态先验概率P(w条件概率p(xW)1=12 (wpw p(w Ix) ∑p(x1v,)p(v) P(G]=GjVUSGs P(XG]=(k/mj/A(k, x) m=Gj,k=m/A(kx)以x为中心恰好包含了k个例子的区 间长度
( ) | | ( ) | | ( ) 2 2 1 1 Ent S N S Ent S N S = Ent s − − ( , ; ) log (3 2) [ ( ) ( ) ( )] 2 1 1 2 2 A T s kEnt s k Ent s k Ent s k = − − − − K1 ,k2分别是T左右两边例子的类别数 4. Bayes离散法 设有两类W1和W2 状态先验概率P(wi ),条件概率p(x|Wi ) i=1,2 = = 2 1 ( | ) ( ) ( | ) ( ) ( | ) i j j i i i p x w p w p x w p w p w x P(Gj)=|Gj|/|sGs| P(x|Gj)=(k/mj)/A(k,x) mj=|Gj|, k= A(k,x)以x为中心,恰好包含了k个例子的区 间长度. mj