在接下來的幾章，作者主要給大家講一講決策樹分類算法，包括ID3算法，C4.5算法和CART算法。

為了感謝大家的支持，其中有一些內容都是作者在外面做培訓的內容，希望對大家的理解有所幫助。

決策樹分類模型簡介

• 決策樹算法是一種歸納分類算法，它通過對訓練集的學習，挖掘出有用的規(guī)則，用于對新集進行預測

• 決策樹算法是一種非參數(shù)學習算法。對每個輸入使用由該區(qū)域的訓練數(shù)據(jù)計算得到的對應的局部模型

• 決策樹歸納的基本算法是貪婪算法，自頂向下以遞歸的方式構造決策樹

• 在其生成過程中，分割時屬性選擇度量是關鍵。通過屬性選擇度量，選擇出最好的將樣本分類的屬性

決策樹算法的工作過程

決策樹的結構

決策樹算法以樹狀結構表示數(shù)據(jù)分類的結果。每個決策點實現(xiàn)一個具有離散輸出的測試函數(shù)，記為分支。

決策樹的結構

決策樹分類的思想類似于找對象?，F(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：

女兒：多大年紀了？ (年齡)；母親：26。

女兒：長的帥不帥？ (長相)；母親：挺帥的。

女兒：收入高不？ (收入情況)；母親：不算很高，中等情況。

女兒：是公務員不？ (是否公務員)；母親：是，在稅務局上班呢。

======>>>女兒：那好，我去見見。

找對象的決策樹分類模型

• 由決策樹的根結點到葉結點的每一條路徑構建一條規(guī)則

• 路徑上內部結點的特征對應著規(guī)則的條件，而葉結點的類對應著規(guī)則的結論

• If-then規(guī)則集合的一重要性質：互斥并且完備

決策樹分類模型學習

• 學習目標：根據(jù)給定的訓練數(shù)據(jù)集構建一個決策樹模型，使它能夠對實例進行正確的分類

• 一個與訓練數(shù)據(jù)矛盾較小的決策樹，同時具有很好的泛化能力

• 決策樹學習本質：從訓練數(shù)據(jù)集中歸納出一組分類規(guī)則

• 決策樹學習的損失函數(shù)：通常是正則化的極大似然函數(shù)。但是基于損失函數(shù)找到全局最優(yōu)決策樹是NP-完全問題

• 現(xiàn)實中決策樹學習通常采用啟發(fā)式方法，即局部最優(yōu)

• 具體做法：每次選擇Feature時，都挑選擇當前條件下最優(yōu)的那個Feature作為劃分規(guī)則，即局部最優(yōu)的Feature

• 停止條件：一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別或沒有屬性可以再用于對數(shù)據(jù)進行分割，學習停止

分類特征選擇

• 特征選擇在于選取對訓練數(shù)據(jù)具有局部最優(yōu)分類能力的特征

• 選擇特征的準則不同形成不同的分類算法

• 信息增益—ID3算法

• 信息增益比—C4.5算法

• 基尼指數(shù)—CART算法

決策樹的剪枝

• 決策樹生成算法對于訓練集是很準確的，但是會造成過擬合，所以需要通過剪枝來提高泛化能力

• 剪枝思路：就是在決策樹對訓練數(shù)據(jù)的預測誤差和樹復雜度之間找到一個權衡