決策樹-上-id3c45cart及剪枝-wenkub
2023-02-12 02:49:27 本頁面
【正文】 ? ? ? ?? ? ? ???? ? ?? ? ?說 明 ： 設(shè) 樣 本 集 按 離 散 屬 性 的 個(gè) 不 同 的 取 值 劃 分1 , ...Vv j vS S Vp S j為 ， 共 個(gè) 子 集其 中 ， 表 示 中 第 類 的 概 率? 信息增 益率（ information gain ratio） 由劃分個(gè)數(shù)引起的偏置問題（劃分越多 =引起每個(gè)劃分內(nèi)部數(shù)據(jù)純度的變化，分塊越小，數(shù)據(jù)純度可能越高 =進(jìn)而引起偏置問題）： 設(shè)樣本集 S按離散屬性 F的 V個(gè)不同的取值劃分為， 共 V個(gè)子集 定義 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算法 選 擇具有最 高信息增 益的屬性作為測試屬性 。 處 理策略： 處 理缺少屬性值的一種策略是賦給它結(jié) 點(diǎn) t所 對應(yīng)的訓(xùn)練實(shí)例中該屬性的最常見 值 另 外一種更復(fù)雜的策略是 為 Fi的 每個(gè)可能值賦予一個(gè)概率。 ( 用 ) 簡 單處理策略就是丟棄這些樣本 法優(yōu) 點(diǎn) ： 產(chǎn) 生的分類規(guī)則易于理 解 準(zhǔn) 確率較高 。（或使用其他不純度） 對于連續(xù)值屬性，必須考慮所有可能的劃分點(diǎn)。節(jié)點(diǎn) t的應(yīng)變量的均值： 節(jié)點(diǎn) t內(nèi)的平方殘差最小化 (squared residuals minimization algorithm)： ()1,1()iNtii X tyyNt ??? ? () 21,( ) ( ( ) )iNtii X tSS t y y t?????CART 回歸樹 劃 分 (屬性 )F將 t劃分成左右節(jié)點(diǎn) tL和 tR， phi值： 能最 大 化上式的就是最佳的 (屬性 )劃分。這種情況可以處理數(shù)據(jù)中的數(shù)據(jù)沖突問題 ； 計(jì) 算每 次 生長 對 系統(tǒng)性能的增益，如果這個(gè)增益值小于某個(gè)閾值則不進(jìn)行生長。leaf 是 子 樹 的 葉 節(jié) 點(diǎn) 數(shù):negative α= M/(N*(Leaf_sub1))=1/(2514*3)= CCP剪枝步驟： 第 一步： 計(jì)算 完 全決策樹 T_max的每個(gè)非葉節(jié) 點(diǎn) 的 α值； 循環(huán)剪掉具有最小 α值的子樹，直到剩下根節(jié)點(diǎn) 得到一系列剪枝 (嵌套 )樹 {T_0,T_1,T_2,…T_m}，其中 T_0就是完全決策樹T_max。 39。39。 否則 , 剪裁 它 不需 要獨(dú)立的剪枝集 references 。39。39。 39。 后剪枝 降低錯(cuò)誤剪枝 REP ( Reduced Error Pruning) 悲觀錯(cuò)誤剪枝 PEP (Pessimistic Error Pruning) 基于錯(cuò)誤剪枝 EBP (ErrorBased Pruning) 代價(jià) 復(fù)雜度剪枝 CCP (CostComplexity Pruning) 最小錯(cuò)誤剪枝 MEP (Minimum Error Pruning) … 降低錯(cuò)誤剪 枝 REP( Reduced Error Pruning) Quinlan 獨(dú)立的剪枝集 D 基本思路 : 對于決策 樹 T 的每棵非葉子 樹 s, 用葉子替代這棵子樹 . 如 果 s 被葉子替代后形成的新樹關(guān)于 D 的誤差等于或小 于 s關(guān) 于 D 所產(chǎn)生的誤差 , 則用葉子替代子 樹 s 優(yōu) 點(diǎn)： 計(jì)算復(fù)雜 性低 對未知示例預(yù)測偏差較小 悲觀錯(cuò)誤剪枝 PEP( Pessimistic Error Pruning ) Quinlan 克服 REP需要 獨(dú)立剪枝集的缺點(diǎn) 誤差估計(jì)的連續(xù)性校正 自上而 下 悲 觀： 基 于訓(xùn)練集建立的樹，對訓(xùn)練集合的錯(cuò)誤率，對于未知集合來說是不可信的 設(shè)原始決策樹 T，葉節(jié)點(diǎn) z， z節(jié) 點(diǎn)訓(xùn)練實(shí)例個(gè)數(shù)為 n_z，其中錯(cuò)分個(gè)數(shù)為 e_z 定義誤差率為： 偏向性（訓(xùn)練數(shù)據(jù)） 增 加連續(xù)性校正： 相 應(yīng)的誤差數(shù)： E_z = e_z + 對 于子樹 t，誤差數(shù)： 標(biāo)準(zhǔn)錯(cuò)誤 : 剪 枝條件： /z z zpe e n? ( ) /z z zpe e n??/2t s sE e le af???其 中 ,s 是 t 的 子 樹* ( )() t t tttttE N ESE ENN??其 中 , 是 當(dāng) 前 訓(xùn) 練 數(shù) 據(jù) 量 ,E 是 對 當(dāng) 前 訓(xùn) 練 數(shù) 據(jù) 錯(cuò) 分 數(shù) ( )tttE E se EE? ? ?是 此 決 策 樹 對 訓(xùn) 練 集 的 錯(cuò) 分 數(shù)E 見 上 面 式 子符合此條件，剪掉 t 基于錯(cuò)誤剪枝 EBP(ErrorBased Pruning) Quinlan PEP的改進(jìn)（ ） 更加悲 觀 自下而上 無需獨(dú)立剪枝集 概率角度
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1