西瓜書注解第4章決策樹

1、學習（西瓜書）注解（第 4 章 決策樹）前言經(jīng)常聽人說所著的學習（以下統(tǒng)稱為西瓜書）是一本入門，是一本性質的教科書。在該書第十次印刷之際，周在“如何使用本書”中也提到“這是一本入門級教科書”。然而，本人讀起來卻感覺該書遠不止“”“入門”那么簡單，書中的很多公式需要思考良久方能推導，很多概念需要反復咀嚼才能消化。邊想著是不是應該將學習時遇到的一些知識難點的出來，以幫助的人入門。的確也隨手做過一些筆記，但由于懷疑這僅是的個別現(xiàn)象，畢竟讀書期間，思考的是如何使用單片機、DSP、ARM、FGPA 等，而這些基本是不需要推導任何公式的，因此作罷。偶然間在周的新浪看到如下：此時方知，可能“讀不懂”并不是個

2、別現(xiàn)象。因此決定寫一本“西瓜書注解”或者稱為“西瓜書讀書筆記”，對研讀西瓜書時遇到的“臺階”進行解釋和推導，以幫助的人能夠更快地進入到這個領域。另外，近期越來越強地，扎扎實實地推導一些基礎算法的公式，無論是對于理解算法本身機理還是進行學術研究，都是非常有必要的。會根據(jù)個人學習進度和研究需要按章發(fā)布，不知道能不能堅持寫完，加油！畢竟也是一名初學者，所以可能一些概念解釋并整、一些公式推導并不優(yōu)美，甚至會存在錯誤，這是不可避免的，不接受漫罵，但歡迎將問題反饋給我，共同學習進步?。ňW(wǎng)盤：）第 4 章目錄第 4 章 決策樹14.14.2基本流程1劃分選擇41、式(4.1)的解釋42、式(4.2)的解釋4

3、3、式(4.4)的解釋44、式(4.5)的推導4剪枝處理54.34.4連續(xù)與值61、式(4.8)的解釋62、式(4.12)的解釋6多變量決策樹61、圖 4.10 的解釋62、圖 4.11 的解釋63、圖 4.14 的解釋7本章小節(jié)84.54.6學習（西瓜書）注解第 4 章 決策樹正如前言所述，從本章至第 10 章，介紹一些經(jīng)典而常用的學習方法。這些方法大部分為分類方法，也穿插了少量回歸算法（例如 6.5 節(jié)的支持向量回歸）；大部分為監(jiān)督學習方法，少量為無監(jiān)督學習方法（第 9 章的聚類和第 10 章的降維）。4.1 基本流程作章的開篇，首先要明白決策樹在做什么。正如圖 4.1 所示的決策過程，決

4、策樹就是不斷根據(jù)某屬性進行劃分的過程（注意：每次決策時考慮范圍是在上次決策結果的限定范圍之內(nèi)的），即“IfElseifElse”的決定過程。但是，劃分到什么時候，就停止劃分呢？這就是圖 4.2 中的三個“return”代表的遞歸返回。以下解釋圖 4.2 中的三種遞歸返回（可參考表 4.1 西瓜數(shù)據(jù)集 2.0）：首先，應該明白決策樹的基本流程是根據(jù)某種原則（即圖 4.2 第 8 行）每次選擇一個屬性按屬性的取值（例如西瓜的“觸感”包括硬滑和軟粘）進行劃分（將所有“觸感”為硬滑西瓜的分到一起，將所有“觸感”為軟粘的西到一起；根據(jù)該屬性劃分后，產(chǎn)生的各子集內(nèi)部樣本在該屬性上的取值分別相同），依此再對

5、各劃特殊情況：集進行遞歸劃分。然而有幾種(I) 劃分期望得到的結果是各子集只包含同一類別的樣本，例如好瓜（或壞瓜），若遞歸劃分過程中某子集已經(jīng)只含有某一類別的樣本（例如只含好瓜），那么此時劃分的目的已經(jīng)達到了，無需再進行劃分，此即為遞歸返回的情形(1)；(II) 遞歸劃分時每次選擇一個屬性，并且劃分依據(jù)屬性不能重復使用，例如本次根據(jù)“觸感”對當前樣本子集 進行劃分，那么后面對該子集 劃分成的子集（及子集的子集）再次進行遞歸劃分時不能再使用“觸感”（圖 4.2 第 14 行的表示從候選依據(jù)屬性中將當前使用的依據(jù)屬性去除，這是因為根據(jù)某屬性劃分之后，產(chǎn)生的各個子集在該屬性上的取值相同）；但樣本的屬

6、性是有限的，因此劃分次數(shù)不超過屬性個數(shù)；若所有屬性均已被作為劃分依據(jù)，此時子集中仍含有多類樣本（例如仍然同時含有好瓜和壞瓜），但是因已無屬性可用作劃分依據(jù)（即子集中樣本在各屬性上取值均相同，但卻無法達到子集只包含同一類別的樣本），此時只能少數(shù)服從多數(shù)，以此子集中樣本數(shù)最多的類為標記，此即為遞歸返回的情形(2)的；(III) 每遞歸一次，候選的屬性個數(shù)就減少一個；假設現(xiàn)在還剩一個屬性可用（比如“觸感”），而且子集中仍含有多類樣本（例如仍然同時含有好瓜和壞瓜），由于只剩一個屬性可用，我們也只能在這個屬性上劃分，但是子集所有樣本在該屬性上的取值都相同（例如“觸感”都是硬滑），這就尷尬了，沒辦法劃分了

7、（大家的“觸感”都一樣，怎么劃分？其實剩個屬性也類似的，劃分就是根據(jù)屬性的不同取值將當前樣本集合分為多個子集，若當前樣本集合在任何候選屬性上的取值相同，則無法劃分），此時也只能少數(shù)服從多數(shù)，以此子集中樣本數(shù)最多的類為標記，此即為遞歸返回的情形(2)的“ 中樣本在 上取值相同”；(IV) 根據(jù)某屬性進行劃分時，若該屬性多個屬性值中的某個屬性值不包含任何樣本（這可能是訓練集的樣本不夠充分造成的），例如對當前子集 以“紋理”屬性來劃分，“紋理”共有三個值：清晰、稍糊、模糊，但發(fā)現(xiàn)當前子集 中并無樣本“紋理”屬性取值為模糊（即子集 中樣本或為清晰，或為稍糊），此時對于取值為清晰的子集和取值為稍糊的子集

8、繼續(xù)遞歸，而對于取值為模糊的分支，因為無樣本落入，將其標記為，其類別標記為 中1第 4 章 決策樹樣本最多的類（即把父結點的樣本分布作為當前結點的先驗分布）；注意，此分支必須保留， 因為測試時，可能會有樣本落入該分支。此即遞歸返回的情形(3)。如此用文字敘述還是比較抽象，接下來使用在表 4.1 西瓜數(shù)據(jù)集 2.0 上基于信息增益生成的圖 4.4 決策樹來具體說明：(I) 根據(jù)“紋理”屬性劃分后，發(fā)現(xiàn)“紋理”為模糊的 3 個樣本全部是壞瓜，即遞歸返回的情形(1)：當前結點包含的樣本全屬于同一類別，無需劃分；編號色澤敲聲紋理臍部觸感好瓜同理，接下來對“紋理”為清晰的樣本，再次根據(jù)“”屬性劃分后，發(fā)

9、現(xiàn)“”為蜷縮的樣本全部是好瓜，“”為硬挺的樣本全部是壞瓜，即遞歸返回的情形(1)；此時只有“編號”為稍蜷的樣本同時含有好瓜和壞瓜，因此需要繼續(xù)進行劃分：色澤敲聲紋理臍部觸感好瓜(II)接下來對“”為稍蜷的樣本，再次根據(jù)“色澤”屬性進行劃分后，發(fā)現(xiàn)“色澤”為青綠的樣本全部是好瓜，即遞歸返回的情形(1)；發(fā)現(xiàn)沒有“色澤”為淺白的樣本，即遞歸返回情形(3)：當前結點包含的樣本集合為空，不能劃分；因此同樣把當前結點標記為葉結點，將其類別設定為其父結點所含樣本最多的類別，即好瓜（如下表所示，其父結點包含三個樣本，其中兩個為好瓜，一個不是好瓜）：21 青綠蜷縮濁響清晰凹陷硬滑是2 烏黑蜷縮沉悶清晰凹陷硬滑

10、是3 烏黑蜷縮濁響清晰凹陷硬滑是4 青綠蜷縮沉悶清晰凹陷硬滑是5 淺白蜷縮濁響清晰凹陷硬滑是6青綠稍蜷濁響清晰稍凹軟粘是8烏黑稍蜷濁響清晰稍凹硬滑是15烏黑稍蜷濁響清晰稍凹軟粘否10青綠硬挺清脆清晰平坦軟粘否1 青綠蜷縮濁響清晰凹陷硬滑是2 烏黑蜷縮沉悶清晰凹陷硬滑是3 烏黑蜷縮濁響清晰凹陷硬滑是4 青綠蜷縮沉悶清晰凹陷硬滑是5 淺白蜷縮濁響清晰凹陷硬滑是6 青綠稍蜷濁響清晰稍凹軟粘是8烏黑稍蜷濁響清晰稍凹硬滑是10青綠硬挺清脆清晰平坦軟粘否15烏黑稍蜷濁響清晰稍凹軟粘否7烏黑稍蜷濁響稍糊稍凹軟粘是9烏黑稍蜷沉悶稍糊稍凹硬滑否13 青綠稍蜷濁響稍糊凹陷硬滑否14 淺白稍蜷沉悶稍糊凹陷硬滑否17

11、青綠蜷縮沉悶稍糊稍凹硬滑否11 淺白硬挺清脆模糊平坦硬滑否12 淺白蜷縮濁響模糊平坦軟粘否16淺白蜷縮濁響模糊平坦硬滑否學習（西瓜書）注解編號色澤敲聲紋理臍部觸感好瓜(III)注意：圖 4.4 的決策樹中沒有出現(xiàn)遞歸返回情形(2)，這是因為表 4.1 的西瓜數(shù)據(jù)集2.0 樣本數(shù)太少。假設表 4.1 的數(shù)據(jù)集只包含“紋理”和“”兩個屬性，則根據(jù)“紋理”劃分之后，再對“紋理”為清晰的樣本根據(jù)“”劃分，發(fā)現(xiàn)兩個屬性都已使用，但“根蒂”為稍蜷的樣本子集中仍同時包含好瓜和壞瓜，即遞歸返回的情形(2)的：編號紋理好瓜此時將“”為稍蜷的結點標記為，并將其類別設定為該結點所含樣本最多的類別，即“好瓜”（結點包

12、含三個樣本，其中兩個為好瓜，一個不是好瓜）。(IV)對于遞歸返回情形(2)的“ 中樣本在 上取值相同”，如下表所示（純?yōu)榻忉屧撨f歸返回情形而編造的）：4.1 數(shù)據(jù)，編號紋理臍部觸感好瓜此時已根據(jù)“紋理”和“”兩個屬性進行劃分，樣本子集中仍同時包含好瓜和壞瓜，仍有“臍部”和“觸感”兩個屬性可以使用，但當前子集中的樣本在剩余的“臍部”和“觸感” 兩個屬性上的取值均相等（均為凹陷和硬滑），因此無法進行劃分，因此將該結點標記為葉結點，并將其類別設定為該結點所含樣本最多的類別，即“好瓜”（結點包含五個樣本，其中三個為好瓜，兩個不是好瓜）?？偨Y：(a)劃分期望得到的結果是各子集只包含同一類別的樣本（暫不考

13、慮 4.3 節(jié)討論的過擬合問題）；(b)使用過的屬性在后續(xù)各子集繼續(xù)劃分時不能再使用，因為各子集內(nèi)的樣本在該屬性上取值相同（僅 離散屬性，若是連續(xù)屬性，則可以重復使用，如表 4.3 中的“密度”和“含糖率”）；(c)對于遞歸返回情形(1)，雖有可用屬性但樣本類別卻已相同，可以理解為這些屬性對當前劃分不起作用；(d)對于遞歸返回情形(2)，當前子集樣本在所有屬性上取值相同，但樣本類別卻不同，可以理解為樣本集含的標記含有噪聲（特征相同的樣本，被標記的類別卻不相同，應該是標記數(shù)據(jù)時弄錯了），或應增加新特征（即當前的幾種特征屬性不足以描述樣本）；(e)決策樹并不一定是二叉樹，分枝個數(shù)等于屬性取值個數(shù)。

14、31 蜷縮清晰凹陷硬滑是2 蜷縮清晰凹陷硬滑是3 蜷縮清晰凹陷硬滑是4 蜷縮清晰凹陷硬滑否5 蜷縮清晰凹陷硬滑否1 蜷縮清晰是2 蜷縮清晰是3 蜷縮清晰是4 蜷縮清晰是5 蜷縮清晰是6稍蜷清晰是8稍蜷清晰是15稍蜷清晰否10硬挺清晰否6青綠稍蜷濁響清晰稍凹軟粘是8烏黑稍蜷濁響清晰稍凹硬滑是15烏黑稍蜷濁響清晰稍凹軟粘否第 4 章 決策樹4.2 劃分選擇指數(shù)分別對應著名的 ID3、本節(jié)介紹的三種劃分選擇方法，即信息增益、增益率、C4.5 和CART 三種決策樹學習算法。1、式(4.1)的解釋該式即為信息論中的信息熵定義公式，以下僅解釋其最大值和最小值。根據(jù)信息論的知識，當各類樣本所占比例相同時信

15、息熵最大：當樣本集合 中只含某一類樣本時信息熵最?。海ㄈ簦瑒t）由以上兩種極限，可以更好的理解式(4.1)下面一行的話：“的值越小，則 的純度越高”，若 中只包含一類樣本，則，此時純度最高。2、式(4.2)的解釋我們希望經(jīng)過依據(jù)某屬性劃分后，劃分所得各子集的純度越高越好，即各子集的信息熵越小越好（若是各子集樣本的類別相同，則所有子集的越大越好。），也就是信息增益劃分所得各子集包含的樣本個數(shù)有多有少，故以其所占比例為權重進行。3、式(4.4)的解釋為了理解該式的“固有值”的概念，可以將式(4.4)與式(4.1)比較一下。式(4.1)可重寫為：其中，為第 類樣本所占的比例。與式(4.4)的表作一下對

16、比：其中，為屬性 等于第 個屬性值的樣本所占的比例。即式(4.1)是按樣本集合 的類別標記計算的信息熵，而式(4.4)是按屬性信息熵（相當于將屬性 作為類別）?？紤]一種特殊情況：若屬性 的取值與類別標記一一對應，則中的第二項等于零，此時式(4.3)的增益率等于 1。的取值計算的，式(4.2)4、式(4.5)的推導假設數(shù)據(jù)集 中的樣例標記種類共有三類，每類樣本所占比例分別為。現(xiàn)從數(shù)4學習（西瓜書）注解據(jù)集 中隨機抽取兩個樣本，如下表所示兩個樣本類別標記正好一致的概率為（即對角線元和）：兩個樣本類別標記不一致的概率為（即“值”）：很容易證明（提公因式即可，注意）：即得式(4.5)：從一個數(shù)據(jù)集 中

17、兩個樣本，類別標記一致的概率越大表示其純度越高（即大部分樣本屬于同一類）；類別標記不一致的概率（即值）越大表示純度越差；因此選擇使各劃集的值盡可能小的屬性作為劃分屬性，指數(shù)即各子集值的平均。4.3 剪枝處理本節(jié)內(nèi)容通俗易懂，幾乎不需要什么注解。以下僅結合圖 4.5 繼續(xù)討論一下圖 4.1 中的遞歸返回條件。圖 4.5 與圖 4.4 均是基于信息增益生成的決策樹，不同在4.4 基于表 4.1，而圖 4.5 基于表 4.2 的訓練集。結點包含訓練集“臍部”為稍凹的樣本（編號 6、7、15、17），當根據(jù)“”再次進行劃分時不含有“”為硬挺的樣本（遞歸返回情形(3)），而恰巧四個樣本（編號 6、7、1

18、5、17）含兩個好瓜和兩個壞瓜，因此硬挺的類別隨機從類別好瓜和壞瓜中選擇其一；結點包含訓練集“臍部”為稍凹且“”為稍蜷的樣本（編號 6、7、15），當根據(jù)“色澤”再次進行劃分時不含有“色澤”為淺白的樣本（遞歸返回情形(3)），因此白類別標記為好瓜（編號 6、7、15 樣本中，前兩個為好瓜，最后一個為壞瓜）；淺結點包含訓練集“臍部”為稍凹、“”為稍蜷、“色澤”為烏黑的樣本（編號 7、15），當根據(jù)“紋理”再次進行劃分時不含有“紋理”為模糊的樣本（遞歸返回情形(3)），而恰巧兩個樣本（編號 7、15）含好瓜和壞瓜各一個，因此瓜和壞瓜中選擇其一；模糊的類別隨機從類別好圖 4.5 兩次隨機選擇均選為好

19、瓜，實際上表示了一種歸納偏好（1.4 節(jié)）。5第 4 章 決策樹4.4 連續(xù)與值有些分類器只能使用離散屬性，當遇到連續(xù)屬性時則需要特殊處理。專門有人研究“屬性離散化”技術，有可以參考Garcia, S., Luengo, J., Sáez, J. A., Lopez, V., & Herrera, F.(2013). A survey of discretization techniques: Taxonomy and empirical analysis in supervised learning. IEEE Transactions on Knowledge and D

20、ata Engineering, 25(4), 734-750.。若結合第 11 章 11.2 節(jié)至 11.4 節(jié)分別介紹的“過濾式(filter)”算法、“包裹式(wrapper)”算法、“(embedding)”算法的概念，若先使用某個屬性離散化算法對連續(xù)屬性離散化后再調用 C4.5決策樹生成算法，則是一種過濾式算法；若如 4.4.1 節(jié)所述，則應該屬于算法（并沒有以學習器的結果準確率為評價標準，而是與決策樹生成過程融為一體，因此不應該劃入包裹式算法）。類似地，有些分類器不能使用含有值的樣本，需要進行預處理。常用的值填充方法是：對于連續(xù)屬性，采用已該屬性的均值進行填充；對于離散屬性，采用屬

21、性值個數(shù)最多的樣本進行填充；這實際上假設了數(shù)據(jù)集樣本是基于同分布采樣得到的。特別地，一般值僅指特征屬性含有，若類別含有，一般會直接拋棄該樣本。當然，也可以根據(jù) 11.6 節(jié)的式(11.24)，在低秩假設下對數(shù)據(jù)集值進行填充。1、式(4.8)的解釋該式就是簡單遍歷所有可能的候選劃分點集合 ，選出使信息增益最大的劃分點。2、式(4.12)的解釋該式括號內(nèi)與式(4.2)基本一樣，區(qū)別在于式(4.2)中的改為式(4.11)的 ，在根據(jù)式(4.1)計算信息熵時第 類樣本所占的比例改為式(4.10)的 ；所有計算結束后再乘以式(4.9)的 。有(4.9) (4.10) (4.11)中的權重，初始化為 1；

22、以圖 4.9 為例，在根據(jù)“紋理”進行劃分時，除編號為 8,10 的兩個樣本在此屬性之外，其余樣本根據(jù)自身在該屬性上的取值分別劃入稍糊、清晰、模糊集，而編號為 8,10 的兩個樣本則要按比例同時劃入集；具體來說，稍糊子集包含樣本 7, 9, 13, 14, 17 共 5 個樣本，清晰子集包含樣本 1, 2,3, 4, 5, 6, 15 共 7 個樣本，模糊子集包含樣本 10, 11, 16 共 3 個樣本，總共 15 個在該屬性不含值的樣本，而此時各樣本的權重為初始化 1，因此編號為 8,10 的兩個樣本分到稍集的權重分別為 ,糊、清晰、模糊和 。4.5 多變量決策樹本節(jié)通俗易懂，只要理解了圖

23、 4.11 的“軸平行”邊界的來歷，一切就都明白了。1、圖 4.10 的解釋只想用該圖強調一下，離散屬性不可以重復使用，但連續(xù)屬性是可以重復使用的。2、圖 4.11 的解釋對應著圖 4.10 的決策樹，來看一看圖 4.11 的邊界是怎么畫出來的：在下圖中，黑色正斜杠(/)陰影部分表示已確定標記為壞瓜的樣例，紅色反斜杠()陰影部分表示已確定標記為好瓜的樣例，空白部分表示需要進一步劃分的樣例。6學習（西瓜書）注解第一次劃分條件是“含糖率0.126？”，滿足此條件的樣例直接被標記為壞瓜（如圖(a)黑色陰影部分所示），而不滿足此條件的樣例還需要進一步劃分（如圖(a)空白部分所示）；在第一次劃分的基礎上

24、對圖(a)空白部分繼續(xù)進行劃分，第二次劃分條件是“密度 0.381？”，滿足此條件的樣例直接被標記為壞瓜（如圖(b)新增黑色陰影部分所示），而不滿足此條件的樣例還需要進一步劃分（如圖(b)空白部分所示）；在第二次劃分的基礎上對圖(b)空白部分繼續(xù)進行劃分，第三次劃分條件是“含糖率 0.205？”，不滿足此條件的樣例直接標記為好瓜（如圖(c)新增紅色陰影部分所示），而滿足此條件的樣例還需進一步劃分（如圖(c)空白部分所示）；在第三次劃分的基礎上對圖(c)空白部分繼續(xù)進行劃分，第四次劃分的條件是“密度 0.560？”，滿足此條件的樣例直接標記為好瓜（如圖(d)新增紅色陰影部分所示），而不滿足此條件的樣例直接標記為壞瓜（如圖(d)新增黑色陰影部分所示）。經(jīng)過四次劃分已無空白部分，表示決策樹生成完畢。從圖(d)中可以清晰地看出好瓜與壞瓜的分類邊界。如書中所注，分類邊界的每一段都是與坐標軸平行的，其實更嚴格地說應該是分類邊界的每一段都是與坐標軸垂直的，話雖一樣，但道理不同。如圖 4.11 所示，由“含糖率0.126？” 確定的第一段邊界實際是函數(shù)“含糖率=0.126”這個常函數(shù)的圖像，而此類常函數(shù)的圖像是坐標軸“