1、Decision tree learn report4.1.基本流程決策樹是一類常見的機器學習方法。從給定的訓練數據集學得一個模型用以對新示例進行分類，某種問題的“決策”或“判定”過程。決策樹一個根結點（包含樣本全集）對應一個屬性測試內部結點對應一個屬性測試葉結點對應決策結果4.1.(1)決策樹目的：產生一顆泛化能力強，即處理未見示例能力強的決策樹決策樹的生成是一個遞歸的過程，在基本算法中，有三種情形會導致遞歸返回： 當前結點包含的樣本全屬于同一類別，無需劃分1 當前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分2 當前結點包含的樣本集合為空，不能劃分34.2.劃分選擇決策樹學習的關鍵

2、：如何選擇最優化分屬性隨著劃分過程不斷進行，我們希望決策樹的分支結點所包含的樣本盡可能屬于同一類別，即結點的“純度”（purity）越來越高。4.2(1)信息熵信息熵（information entropy）是度量樣本集合純度最常用的一種指標。假定當前樣本集合D中第k類樣本所占的比例為 (k=1,2, ),則D的信息熵定義為：Ent(D)的值越小，則D的純度越高。kpy21()logkypkkEnt Dp 4.2(2)信息熵計算信息熵時約定：若p=0,則 Ent(D)的最小值為0，最大值為 例：假設D中有8個樣本，且有k=8，則 2log0pp2logy18kp82111()log88kEnt

3、 D 4.2(3)信息增益假定離散屬性a有V個可能的取值 ，若使用a來對樣本集D進行劃分，則會產生V個分支結點，其中第v個分支結點包含了D中所有在屬性a上取值為 的樣本，記為 。根據不同分支結點包含的樣本數不同，給分支結點賦予權重： 即樣本數越多的分支結點的影響越大。12,.,Va aavavD/vDD4.2(4)信息增益屬性a對樣本集D進行劃分所獲得的“信息增益”（information gain）信息增益越大，則意味著使用屬性a來進行劃分所獲得的“純度提升”越大。因此，可用信息增益來進行決策樹的劃分屬性選擇。1( , )()()vVvvDGain D aEnt DEnt DD編號編號色澤色

4、澤根蒂根蒂敲聲敲聲紋理紋理臍部臍部觸感觸感好瓜好瓜1青綠蜷縮濁響清晰凹陷硬滑是2烏黑蜷縮沉悶清晰凹陷硬滑是3烏黑蜷縮濁響清晰凹陷硬滑是4青綠蜷縮沉悶清晰凹陷硬滑是5淺白蜷縮濁響清晰凹陷硬滑是6青綠稍蜷濁響清晰稍凹軟粘是7烏黑稍蜷濁響稍糊稍凹軟粘是8烏黑稍蜷濁響清晰稍凹硬滑是9烏黑稍蜷沉悶稍糊稍凹硬滑否10青綠硬挺清脆清晰平坦軟粘否11淺白硬挺清脆模糊平坦硬滑否12淺白蜷縮濁響模糊平坦軟粘否13青綠稍蜷濁響稍糊凹陷硬滑否14淺白稍蜷沉悶稍糊凹陷硬滑否15烏黑稍蜷濁響清晰稍凹軟粘否16淺白蜷縮濁響模糊平坦硬滑否17青綠蜷縮沉悶稍糊稍凹硬滑否4.2(5)信息增益以上表為例,該數據集包含17個訓練樣例

5、，用以學習一顆能預測沒剖開的瓜是不是好瓜的決策樹.顯然 .在決策樹開始學習時,根結點包含D中的所有樣例,其中正例占 ,反例占 .根據(1)式可算出根結點的信息熵為：2y 1817p 2917p 222218899( )log(loglog)0.99817171717kkkEnt Dpp4.2(6)然后我們要計算出當前屬性集合色澤,根蒂,敲聲,紋理,臍部,觸感中每個屬性的信息增益.以色澤為例,它有三個可能的取值：青綠,烏黑,淺白.對D進行劃分,則可得到3個子集,分別為： (色澤=青綠), (色澤=烏黑), (色澤=淺白).D1=1,4,6,10,13,17D2=2,3,7,8,9,15D3=5,

6、11,12,14,16所以1D2D3D13 6p 23 6p 14 6p 22 6p 11 5p 24 5p 1223333()(loglog)1.0006666Ent D 2224422()(loglog)0.9186666Ent D 321144()(loglog)0.7225555Ent D 4.2(7)于是，我們可以算出屬性”色澤”的信息增益為：Gain(D,色澤)類似的，可以算出： Gain(D,根蒂)=0.143 Gain(D,敲聲)=0.141 Gain(D,紋理)=0.381 Gain(D,臍部)=0.289 Gain(D,觸感)=0.00631( )()6650.998 (1

7、.0000.9180.722)1717170.109vvvDEnt DEnt DD4.2(8)顯然,屬于“紋理”的信息增益最大,于是它被選為劃分屬性.然后,決策樹學習算法將對每個分支結點做進一步劃分.可用屬性集合色澤,根蒂,敲聲,臍部,觸感基于各結點的集合樣例計算出各屬性的信息增益.紋理1,2,3,4,5,6,8,10,157,9,13,14,1711,12,16清晰稍糊模糊4.2(9)基于D1(紋理=清晰)=1,2,3,4,5,6,8,10,15計算出的各屬性的信息增益為：Gain(D1,色澤)=0.043 Gain(D1,根蒂)=0.458Gain(D1,敲聲)=0.331 Gain(D1

8、,臍部)=0.458Gain(D1,觸感)=0.458根蒂、臍部、觸感3個屬性均取得最大的信息增益，可任選之一作為劃分屬性.類似的,對每個分支結點進行上述操作,最終得到的決策樹如下：4.2(10)決策樹：根蒂=？觸感=？紋理色澤=？觸感=？壞瓜壞瓜好瓜壞瓜好瓜好瓜好瓜好瓜壞瓜清晰稍糊模糊軟粘硬滑蜷縮硬挺稍蜷青綠淺白烏黑硬滑軟粘4.2.2增益率信息增益準則對可取值數目較多的屬性有所偏好,例如“編號”,它的信息增益為0.998,遠大于其他屬性,“編號”將產生17支分支,每個分支結點僅包含一個樣本,這些分支結點的純度達到最大.然而,這樣的決策樹顯然不具有泛化能力,無法對新樣本進行有效的預測.C4.5

9、決策樹算法Quinlan,1993不直接使用信息增益,而是用“增益率”(gain ratio)來選擇最優劃分屬性.4.2.2(1)增益率：屬性a可能取值數目越多(即V越大),則IV(a)的值通常會越大增益率準則對可取值數目較少的屬性有所偏好,因此,C4.5算法并不是直接選擇增益率最大的候選劃分屬性,而是使用了一個啟發式Quinlan,1993:先從候選劃分屬性中找出信息增益高于平均水平的屬性,再從中選擇增益率最高的.( , )_( )Gain D aGainratioIV a21( )logvvVvDDIV aDD 屬性a的固有值4.2.3基尼指數(Gini index)CART決策樹Brei

10、man et al.,1984使用“基尼指數”來選擇劃分屬性.數據集D的純度可用基尼值來度量：1()ykkkkkGini Dp p211ykkpGini(D)反應了從數據集D中隨機抽取兩個樣本,其類別標記不一致的概率.Gini(D)越小,則數據集D的純度越高4.2.3(1)屬性a的基尼指數定義為：于是,我們在候選屬性集合A中,選擇那個使得劃分后基尼指數最小的屬性作為最優劃分屬性.1_(, )()vVvvDGiniindex D aGini DD4.3剪枝處理剪枝(ppruning)是決策樹學習算法對付“過擬合”的主要手段.基本策略：預剪枝(prepruning) 后剪枝(post-prunin

11、g)在決策樹生成過程中,對每個結點在劃分前先進性估計,若當前結點的劃分不能帶來決策樹泛化性能提升,則停止劃分并將當前結點標記為葉結點.先從訓練集生成一棵完整的決策樹,然后自底向上地對非葉結點進行考察,若將該結點對應的子樹替換為葉結點能帶來泛化能力提升,則將該子樹替換為葉結點4.3(1)隨機劃分出兩部分：Train:1,2,3,6,7,10,14,15,16,17Test:4,5,8,9,11,12,13臍部=？色澤=？根蒂=？色澤=？紋理=？壞瓜好瓜壞瓜好瓜壞瓜好瓜好瓜好瓜好瓜好瓜壞瓜凹陷稍凹平坦青綠烏黑淺白稍蜷蜷縮硬挺青綠烏黑淺白稍糊清晰模糊4,13511,12984.3.1預剪枝基于信息增

12、益準則,我們選擇“臍部”來對train進行劃分,并產生3個分支.預剪枝要對劃分后的泛化性能進行估計：臍部=？好瓜好瓜壞瓜凹陷稍凹平坦驗證集精度劃分前：42.9%劃分后：71.4%預剪枝決策：劃分驗證集精度色澤=？劃分前：71.4% 劃分后：57.1%預剪枝決策：禁止劃分驗證集精度根蒂=? 劃分前：71.4% 劃分后：71.4%預剪枝決策：禁止劃分4,5,138,911,12僅有一層劃分的決策樹，亦稱為“決策樹樁”4.3.1(1)劃分后：1,2,3,14 10,16 6,7,15,17其中4,5,8,11,12被分類正確,驗證集精度為 42.9%色澤劃分后：好瓜4(1),13(0),壞瓜5(1)

13、根蒂劃分后：好瓜8(1),9(0)5100% 71.4%74.3.1(2)預剪枝使得決策樹的很多分支都沒有“展開”,這不僅降低了過擬合的風險,還顯著減少了決策樹的訓練時間開銷和預測試時間開銷.另一方面,有些分支的當前劃分雖不能提升泛化性能、甚至可能導致泛化性能暫時下降,但在其基礎上進行的后續劃分卻有可能導致性能顯著提高.預剪枝基于“貪心”本質禁止這些分支展開,給預剪枝決策樹帶來了欠擬合的風險.4.3.2后剪枝后剪枝先從訓練集生成一棵完整的決策樹基于train :1,2,3,6,7,10,14,15,16,17得到決策樹臍部=？根蒂=？色澤=？好瓜壞瓜好瓜好瓜好瓜壞瓜壞瓜凹陷稍凹平坦稍蜷蜷縮硬挺

14、青綠烏黑淺白原分支“色澤=？”驗證集精度剪枝錢：57.1%剪枝后：71.4%后剪枝決策：剪枝原分支“紋理=？”驗證集精度剪枝錢：42.9%剪枝后：57.1%后剪枝決策：剪枝4.3.2(1)后剪枝決策樹通常比預剪枝決策樹保留了更多的分支,一般情況下,后剪枝決策樹的欠擬合風險很小,泛化性能往往優于預剪枝決策樹.但后剪枝過程是在生成完全決策樹之后進行的,并且要自底向上地對樹中的所有非葉結點進行逐一考察.因此其訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要大得多.4.4連續與缺失值現實學習任務中常會遇到連續屬性.連續屬性的可取值數目不再有限,因此,不能直接根據連續屬性的可取值來對結點進行劃分.連續屬性離

15、散化技術：二分法(bi-partitiom)4.4.1連續值處理給定樣本集合D和連續屬性a,假定a在D上出現了n個不同的取值,將這些值從小到大排序,記為 .基于劃分點t可將D分為子集 和 ,其中 包含哪些在屬性a上取值不大于t的樣本,而 則包含那些在屬性a上取值大于t的樣本.顯然,對于相鄰的屬性 與 來說,t在區間中取任意值所產生的劃分結果相同.12,.,na aatDtDtDtDia1ia1,iia a4.1.1(1)對屬性a,我們考察包含n-1個元素的候選劃分點:即把中位點作為候選劃分點.像離散屬性值一樣來考察這些劃分點,選取最優劃分點進行樣本集合的劃分：1|112iiaaaTin( ,

16、)max( , , )at TGain D aGain D a t , max()()attt TDEnt DEnt DD 4.1.1(2)其中Gain(D,a,t)是樣本集D基于劃分點t二分后的信息增益.于是,我們可選擇使Gain(D,a,t)最大化的劃分點.(密度，含糖率)123456780.6970.7740.6340.6080.5560.4030.4810.4370.4600.3760.2640.3180.2150.2370.1490.211910111213141516170.6660.2430.2450.3430.6390.6570.3600.5930.7190.0910.2670

17、.0570.0090.1610.1980.3700.0420.1034.1.1(3)對于密度,該屬性有16個候選劃分點：T=0.244,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746根據(6)式可計算出其信息增益為0.262,對應劃分點0.381222218899()log(loglog)0.99817171717kkkEnt Dpp 2222 , 11413()( log )(log)1717ttkkkkkkDMEnt DppppD 22138855130(lo

18、glog)0.736(0.764)1713131313174.1.1(4)所以,由(6)式得Ent(D)-M=0.262類似的,對于含糖率也可計算出信息增益為0.349.須注意是,與離散是尋根不同,若當前結點劃分屬性為連續屬性,該屬性還可作為其后代結點的劃分屬性.個屬性的信息增益Gain(D,色澤)=0.109 Gain(D,根蒂)=0.143Gain(D,敲聲)=0.141 Gain(D,紋理)=0.381Gain(D,臍部)=0.289 Gain(D,觸感)=0.006Gain(D,密度)=0.262 Gain(D,含糖率)=0.3494.4.2缺失值處理現實中往往會遇見不完整樣本,即樣本

19、的某些屬性值缺失.如果放棄不完整樣本,僅使用無缺失值的樣本來學習,顯然是對數據信息的極大浪費.我們需要解決的問題：如何在屬性值缺失的情況下進行劃分屬性選擇？給定劃分屬性,若樣本在該屬性上的值缺失,如何對樣本進行劃分？4.2.2(1)問題一給定訓練集D和屬性a,令 表示D中在屬性a上沒有缺失值的樣本子集.對于(1)可以用 來判斷屬性a的優劣.假定屬性a有V個可取值 ,令 表示 中在屬性a上取值為 的樣本子集, 表示 中屬于第k類(k=1,2, )的樣本子集,顯然有DD12,.,Va aavDDvakDDy1ykkDD1VvvDD4.2.2(2)我們為每個樣本x賦予一個權重 ,并定義：xwxx D

20、xx Dwwkxx Dkxx Dwpwvxx Dvxx Dwrw(1)ky(1)vVP表示無缺失值樣本所占的比例表示無缺失值樣本中第k類所占的比例表示無缺失值樣本中在屬性a上取值a(v)的樣本所占比例4.2.2(3)顯然,基于上述定義,我們可以將信息增益的計算式推廣：11ykkp11Vvvr( , )( , )Gain D aGain D a1()()VvvvEnt Dr Ent D4.2.2(4)問題二若樣本x在屬性a上的取值已知,則將x劃入與其值對應的子結點,且樣本權值在子結點中保持為w(x).若樣本x在屬性a上的取值未知,則將x同時劃入所有子結點,且樣本權值在與屬性值a(v)對應的子結點

21、中調整為 ;(就是讓同一個樣本以不同的概率劃入到不同的子結點中去)C4.5算法使用了上述解決方案Quinlan,1993vxr w4.2.2(5)以屬性色澤為例,根結點包含17個樣例.各樣例的權值為1.該屬性上的無缺失值的樣例子集 包含2,3,4,6,7,8,9,10,11,12,14,15,16,17(14) 的信息熵為：令 分別表示“色澤”上取值為“青綠”“烏黑”“淺白”的樣本子集.有DD221()log.0.985kkkEnt Dpp 123,D DD1()1.000Ent D2()0.918Ent D3()0.000Ent D4.2.2(6)樣本子集D()上屬性a(色澤)的信息增益為：于是,樣本集D上屬性a(色澤)的信息增益為：31( ,)()()0.306vvvGain D sezeEnt Dr Ent D( ,)( ,)0.2