1、第四章 示例學(xué)習(xí)的實(shí)用化4.1 定量屬性的定性化1.2. 決策樹(shù)連續(xù)屬性值處理(二分離散法)1) 切點(diǎn)法:T類熵(class entropy)kEnt(s) = - p(ci , s) log( p(ci , s)i=1類信息熵(class information entropy)E( A,T ; s) = | s1 | Ent(s ) + | s2 | Ent(s )N1N2S1: 切點(diǎn)T左邊的例子集S2:切點(diǎn)T右邊的例子集. |s| 集合s中的例子數(shù)N=|s|2) 界點(diǎn)法:T1T2T3T4T53) 多切點(diǎn)法:TrTr+1erer+1E(Tr) - E(Tr +1 ) 2 log 2 (n

2、+1) - log 2 r n= max_diff (Tr )Emin是目前為止得到的最小信息熵,如果E(Tr)-max_diff(Tr) Emin, 則E(Tr+1) Emin Max_diff(Tr)隨著r的增加單調(diào)遞減.啟發(fā)式1: 設(shè)Emin是迄今為止得到的最小信息熵,則從Tr開(kāi)始下一個(gè)需要計(jì)算熵的切點(diǎn)是Tr+DD = max(1, E(Tr ) -Emin)max_ diff (T ) r1) D與Emin有關(guān),因此,被忽略的結(jié)點(diǎn)數(shù)與屬性被處理的順序有關(guān),如果最相關(guān)的屬性被首先處理,Emin就會(huì)被早些得到,因此,以后計(jì)算中D值就會(huì)較大,所以省略的結(jié)點(diǎn)數(shù)就多,為減少算法的運(yùn)行時(shí)間,最相關(guān)

3、的屬性應(yīng)首先被處理.2) Max_diff(Tr)是單調(diào)遞減的,所以連續(xù)屬性排序后,屬性值域的后半部分D值較高.3) 通常,如果相關(guān)屬性先被處理,對(duì)不相關(guān)屬性使用啟發(fā)式1,將是較有效的.啟發(fā)式2. 對(duì)于每個(gè)屬性Ai,Tmi是其一個(gè)切點(diǎn),把例子集分成兩個(gè)例子數(shù)相等的子集, E(Tmi)是Tmi的熵,對(duì)各屬性按E(Tmi)從小到大的順序使用啟發(fā)式1進(jìn)行離散化.3. 多區(qū)間劃分停止標(biāo)準(zhǔn)(最小描述長(zhǎng)度)Gain( A,T ; s) log 2 ( NN-1) +D(a ,T ; s)NGain( A,T ; s) =Ent(s) -E( A,T ; s)= Ent(s) - | S1N|Ent(S1)

4、 - | S2N| Ent(S)22D(A,T; s) = log(3k- 2) -kEnt(s) - k1Ent(s1) - k2Ent(s2 )K1,k2分別是T左右兩邊例子的類別數(shù)4. Bayes離散法 設(shè)有兩類W1和W2狀態(tài)先驗(yàn)概率P(wi),條件概率p(x|Wi)i=1,2p(wi| x) =p(x |2wi ) p(wi )i =1p(x |wj ) p(wj )P(Gj)=|Gj|/|sGs| P(x|Gj)=(k/mj)/A(k,x)mj=|Gj|, k=mj間長(zhǎng)度.A(k,x)以x為中心,恰好包含了k個(gè)例子的區(qū)算法1）對(duì)I=1,2,.,n;求Gi類例子的個(gè)數(shù)2) 所有例子的個(gè)數(shù)|UsGs|3) 對(duì)I=1,2,n;求P(Gi)=|Gi|/|UsGs|4) 從區(qū)間左端開(kāi)始，按某步長(zhǎng)step向右走，對(duì)于每一點(diǎn)x計(jì)算A(k,x),具體辦法是：以x為中心點(diǎn)，以step為步長(zhǎng)向兩端擴(kuò)展，直到包含k個(gè)例子為止，然后計(jì)算該點(diǎn)的P(x|Gj)=(k/mj)/A(k,x)，如果有兩個(gè)值Xs、Xs+1(Xs+1=Xs+step)， 使 得 P(Xs|Gi1)P(Gi1)=maxP(Xs|Gj)P(Gj), P(Xs+1|Gi2)P(Gi2)=maxP(Xs+1|Gj)P(Gj), j=1,2,n, i1i2, 則