決策樹-上-id3c45cart及剪枝(完整版)
【正文】 分裂子集 。 該葉節(jié)點(diǎn)持有其數(shù)據(jù)集中樣本最多的類或者其概率 分布 ? 后剪 枝 首先構(gòu)造完整的決策樹，允許決策樹過度擬合訓(xùn)練 數(shù)據(jù) ， 然 后對那些置信度不夠的結(jié)點(diǎn)的子樹用 葉結(jié) 點(diǎn)來替代 該 葉節(jié) 點(diǎn)持 有 其 子 樹的數(shù) 據(jù) 集中樣 本最多的類或者其概率分布 預(yù)剪枝 預(yù)剪枝判斷停 止樹生 長的方 法可 以歸納為以下幾種： 最 為簡單的方法就是在決策樹到達(dá)一定高 度的情況下就停止樹的生長； 到 達(dá)此結(jié)點(diǎn)的實例個數(shù)小于某一個閾值也 可停止樹的生長 ； 到達(dá)此結(jié)點(diǎn)的實例具有相同的特征向量，而不必一定屬于同一類，也可停止生長。 39。 ()iE E SE E??條 件 ：最小錯誤剪枝 MEP(Minimum Error Pruning) 基本思 路： 是 采用自底向上的方式 , 對于樹中每個非葉節(jié)點(diǎn) , 首先計算該節(jié)點(diǎn) 的誤 差E(t) . 然后 , 計算該節(jié)點(diǎn)每個分枝的誤差 , 并且加權(quán)相加 , 權(quán)為每個分枝擁有的訓(xùn)練樣本 比例 . 如果 E(t) 大 于分枝誤差期望 , 則保留該子樹 。39。 new_t可能會比 t對于訓(xùn)練數(shù)據(jù)分錯 M個，但是 new_t包含的葉節(jié)點(diǎn)數(shù)，卻比 t少 : (Leaf_s 1)個 復(fù)雜度降低了 代 價可能升高了 如 何平衡？ 令替換之后代價復(fù)雜度相等 ： 增加了 M個錯分樣本， 但是減少了 (leafs1)個 葉節(jié)點(diǎn) ( ) ( _ )* * [ (()1)1]st t ssc c t c c ne w tE E ML e af le af leMN le afafNNMs?????? ? ? ????????其 中 ， 是 用 葉 節(jié) 點(diǎn) 替 換 t 的 s 子 樹 以 后 ，增 加 的 錯 分 樣 本 數(shù) 。 C_R= CART_classification(DS_R featureList, alpha) – 將節(jié)點(diǎn) C_L和 C_R添加為 R的左右子節(jié)點(diǎn) CART 分 類 樹算法步驟示意 CART 回歸樹 樣本 ： (X, y) y為分類 = 分類樹 y為實數(shù) = 回歸樹 設(shè) t代 表樹的某個節(jié)點(diǎn)， t中的樣本集合為： {(X1,y1), (X2,y2) …}， 應(yīng)變 量為實數(shù)， N(t)是節(jié)點(diǎn) t中 的 樣本個數(shù)。這些片斷樣例（ fractional examples）的目的是計算信息增益，另外，如果有第二個缺少值的屬性必須被測試，這些 樣例可以在后繼的樹分支中被進(jìn)一步細(xì)分 。 21( ) l og ( )C=CiiiiiEn tr opy S p pi??? ?其 中 ， S 表 示 樣 本 集 ，C 表 示 樣 本 集 合 中 類 別 個 數(shù) ( 只 含 有 正 負(fù) 樣 本 ， 則 2) ，p 表 示 第 個 類 的 概 率 ，（ p 可 由 類 別 i 中 含 有 樣 本 的 個 數(shù) 除 以 總 樣 本 數(shù) 得 到 ）? 信息增益（ information gain） 是指期望信息或者信息熵的有效減少量。決策樹 上 武承羲 內(nèi)容 決策樹基礎(chǔ) 經(jīng)典決策樹 剪枝 決策樹 決策 樹： 用來表示 決策 和相應(yīng)的 決策結(jié)果 對應(yīng)關(guān)系的樹。 2122112211( , ) ( ) ( )l og ( ) ( ) ( )l og ( ) ( ) { l og ( ) }l og ( ) ( ) l og ( )FCi i vi v V ofFCCi i v j v ji v V ofF jCCi i v j v ji v V ofF jG ain S F En tr opy S Ex pe c te dE ntr opy Sp p p v En tr opy Sp p p v p pppSv p pFpV??? ? ?? ? ???? ? ?? ? ? ?? ? ? ???? ? ?? ? ?說 明 ： 設(shè) 樣 本 集 按 離 散 屬 性 的 個 不 同 的 取 值 劃 分1 , ...Vv j vS S Vp S j為 ， 共 個 子 集其 中 ， 表 示 中 第 類 的 概 率? 信息增 益率（ information gain ratio） 由劃分個數(shù)引起的偏置問題（劃分越多 =引起每個劃分內(nèi)部數(shù)據(jù)純度的變化，分塊越小，數(shù)據(jù)純度可能越高 =進(jìn)而引起偏置問題）： 設(shè)樣本集 S按離散屬性 F的 V個不同的取值劃分為， 共 V個子集 定義 Split(S, F)： 則用 F對 S進(jìn)行劃分的信息增益率為： 2| | | |( , ) * l og ( )| | | |vvvVSSSplit S F??? ?1,.., VSS( , )( , )( , )G ain S FG ainR ati o S FSplit S F?21 12( , ) l og ( lo) ) )( g(CvCiiv V ofFvjjijpG ai pv pn S F p p? ??? ? ??? ?ID3 1986年由 Quilan提出的 ID3算法 選 擇具有最 高信息增 益的屬性作為測試屬性 。 ( 用 ) 簡 單處理策略就
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1