ch10決策樹(shù)-文庫(kù)吧
2025-08-26 22:36 本頁(yè)面
【正文】 大，如何使其變小變簡(jiǎn)單，即如何剪枝？ ? 如果落入葉節(jié)點(diǎn)的樣本不都屬于同一類，如何給該葉節(jié)點(diǎn)賦類別標(biāo)記？ 分支數(shù)目 ? 同一個(gè)節(jié)點(diǎn)分出去的分支的數(shù)目稱為 分支系數(shù) 或分支率 （ branching ratio） ? 任意決策樹(shù)都可以用分支系數(shù)為 2的決策樹(shù)（ 即二叉樹(shù) ）來(lái)表示 ? 二叉樹(shù) 是最常用的決策樹(shù)形式 分支數(shù)目 分支數(shù)目 測(cè)試的選取 ? 決策樹(shù)設(shè)計(jì)的核心問(wèn)題之一 ? 基本思想： 使后繼結(jié)點(diǎn)的數(shù)據(jù)盡可能的“純粹” ? 節(jié)點(diǎn) N的 不純度 （ impurity） i(N) ? 當(dāng) N節(jié)點(diǎn)上的所有模式都來(lái)自同一類時(shí)， i(N)=0； ? 當(dāng) N節(jié)點(diǎn)上的模式類別分布均勻時(shí)， i(N)應(yīng)很大 測(cè)試的選取 ? 常用不純度度量 ? 熵不純度 （ entropy impurity） ? Gini不純度 ? 誤分類不純度 () jjP ?? ? 屬 于 的 樣 本 個(gè) 數(shù)樣 本 總 個(gè) 數(shù)測(cè)試的選取 ? 常用不純度度量 測(cè)試的選取 ? 對(duì) N節(jié)點(diǎn)如何選擇查詢？ 使不純度下降最快的那個(gè)查詢！ ? 和 分別為左、右子節(jié)點(diǎn) ? 和 分別為左、右子節(jié)點(diǎn)的不純度 ? 是 N節(jié)點(diǎn)的模式劃分到 的比例 ? 如果采用熵不純度，則不純度下降差就是本次查詢所能提供的信息增益 （ information gain） 信息增益 ? 信息增益 （ information gain） ? ：節(jié)點(diǎn) N上樣本總個(gè)數(shù) ? ：其中屬于 類的樣本個(gè)數(shù)（ i=1,2, …, m ） ? ：屬性 A的第 j個(gè)取值（ j=1,2, …, v ） ? 該節(jié)點(diǎn)處的熵不純度 ? 屬性 A將 S劃分為 v個(gè)子集 ? 中屬于 類的樣本個(gè)數(shù)為 i?21( ) lo gmiiiSSESSS??? ?i?信息增益 ? 信息增益 （ information gain） ? 以 A作為查詢，生長(zhǎng)出 v個(gè)分支的信息熵 ? 以 A為查詢的信息增益 ? 選擇信息增益最大的屬性作為 N節(jié)點(diǎn)的查詢 21 1 1( ) ( ) l o gv v mj j ij ijjj j i jjS S S SE A E SS S S S? ? ???? ? ? ??? ? ??? ????? ? ?( ) ( ) ( )G a in A E S E A??信息增益 ? 例子 ? 訓(xùn)練集 S1: buys_puter= “yes”, S2: buys_puter= “no” 信息增益 ? 根節(jié)點(diǎn)上的熵不純度 ? age作為查詢的信息熵 229 9 5 5( ) l og l og 0. 94 014 14 14 14E roo t??? ? ? ?????1 2 22 2 3 3( ) l og l og 715 5 5 5E root??? ? ? ?????2( ) 0E ro ot ?3 2 23 3 2 2( ) l og l og 715 5 5 5E root??? ? ? ?????1 2 35 4 5( ) ( ) ( ) ( ) 14 14 14E age i root i root i root? ? ? ?信息增益 ? age作為查詢的信息增益 ? 類似可以計(jì)算出所有屬性的信息增益 ? age的信息增益最大，所以選擇 age作為根節(jié)點(diǎn)的查詢，對(duì)訓(xùn)練集進(jìn)行首次劃分 ( ) ( ) ( ) 0 .2 4 6G a in a g e E r o o t E a g e? ? ?( ) ( ) ( _ ) Gain inc omeGain st ude ntGain c re dit rat ing???信息增益率 ? 信息增益作為查詢選擇標(biāo)準(zhǔn)的缺點(diǎn)： 偏向有較多不同取值的屬性 ? 為克服這一缺點(diǎn)， J. R. Quinlan在其著名的 算法中采用 信息增益率 （ gain ratio）作為選擇標(biāo)準(zhǔn) ()_ ( )()G ain AG ain ratio AI V A?21( ) l ogv jjjSSI V ASS????? ?信息增益率 ? 例子 2225 5 4 4 5 5( ) l og l og l og 1. 57 814
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1