ExampleⅤ ersion Space S:1() G:{≤Smy,2,?,??,?>,}
How Should these be classified? S:(3 Smy,?,?,Stog,?,? G:{,} Sunny ormal Strong Cool Change) ( Rainy Cool Normal Light Warm Same) (Sunny Warm Normal Light Warm Same)
Instance, Hypotheses, and More General-Than Instances X Hypotheses H General x1 h,= Summy, Warm, High, Light, Warm, Same h= h=<Sum. ??? Cool
Version Spaces A hypothesis h is consistent with a set of training examples D of target concept c if and only if h()=c(a) for each training example 〈x,c(x)inD Consistent(h,D)≡(x,c(x)∈D)h(x)=c(x) The version space, VSH.D, with respect to hypothesis space H and training examples D is the subset of hypotheses from H consistent with all training examples in D SnD≡{h∈ H Consistent(h,D)}
第四章示例学习的实用化 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
算法 1)对I=1,2,,n;求G类例子的个数 2)所有例子的个数UsGs 3)对I=1,2,,n,求P(Gi)=Gi/UsGs 4)从区间左端开始,按某步长step向右走,对于每一点x计 算A(kx),具体办法是:以x为中心点,以sep为步长向两端 扩展,直到包含k个例子为止,然后计算该点的 P(xGj)=(k/m)/A(kx),如果有两个值Xs、X+1(X1= Xs+step, 使得P(XsGn)P(G1)=max{P(Xs(Gj)P(Gj) P(X3+1(G12)P(G2)=max{P(x*1|Gj)P(Gj)},=1,2,,n,i#i2,则 X为切分点
算法 1）对I=1,2,….,n;求Gi类例子的个数 2) 所有例子的个数|UsGs| 3) 对I=1,2,…,n;求P(Gi)=|Gi|/|UsGs| 4) 从区间左端开始，按某步长step向右走，对于每一点x计 算A(k,x),具体办法是：以x为中心点，以step为步长向两端 扩展，直到包含k个例子为止，然后计算该点的 P(x|Gj)=(k/mj)/A(k,x)，如果有两个值Xs、Xs+1(Xs+1=Xs+step)， 使得P(Xs|Gi1)P(Gi1)=max{P(Xs|Gj)P(Gj)}, P(Xs+1|Gi2)P(Gi2)=max{P(Xs+1|Gj)P(Gj)}, j=1,2,…,n, i1≠i2,则 Xs+1 为切分点