機器學習技法筆記9：決策樹

決策樹

先直接上一個決策樹的公式定義：

G(x)表示完整的大樹，即full-tree hypothesis，b(x)表示每個分支條件，即branching criteria，Gc(x)表示第c個分支下的子樹，即sub-tree。這種結構被稱為遞歸型的數據結構，即將大樹分割成不同的小樹，再將小樹繼續分割成更小的子樹。所以，決策樹可以分為兩部分：root和sub-trees。

決策樹的優點：

• 模型直觀，可解釋性，擬人性
• 演算法簡單，容易實現
• 訓練和預測時，效率較高

決策樹的缺點：

• 理論證明較少
• 結構選擇參數比較困惑
• 代表性的演算法較少

決策樹演算法

演算法思路：

• 學習設定劃分不同分支的標準和條件是什麼
• 將整體數據集D根據分支個數C和條件，劃為不同分支下的子集Dc
• 然後對每個分支下的Dc進行訓練，得到相應的機器學習模型Gc
• 將所有分支下的Gc合併到一起，組成大矩G(x)

C&RT演算法（Classification and Regression Tree）

切分邏輯：分支個數C=2，每次在一個維度上，只對一個特徵將數據一分為二，左子樹和右子樹，分別代表不同的類別。使用純凈度purifying這個概念來選擇最好的切分。purifying的核心思想就是每次切割都儘可能讓左子樹和右子樹中同類樣本佔得比例最大或者yn都很接近（regression），即錯誤率最小。比如分類問題中，如果左子樹全是正樣本，右子樹全是負樣本，那麼它的純凈度就很大，說明該分支效果很好。

為了便於計算，我們用impurity(不純)來進行考量，也即切分的impurity越小越好。impurity的量化公式如下：

演算法迭代終止條件有兩種情況，第一種情況是當前各個分支下包含的所有樣本yn都是同類的，即不純度impurity為0，表示該分支已經達到了最佳分類程度。第二種情況是該特徵下所有的xn相同，無法對其進行區分，表示沒有decision stumps。遇到這兩種情況，C&RT演算法就會停止迭代。

#todo

題圖：

1、最近幾天進度趕的有點快，導致內容理解消化的不是很好，再加上今天的決策樹的純度的打擊，現決定暫停技法課程的推進，回過頭從基石開始，到svm結束，先把已經學到的，需要消化理解的搞懂，筆記只是衍生品，主要的目的還是知識的學習理解。

2、先把筆記的位置填上，後期再續寫。

3、明天開始，從PLA開始，要搞懂數學推導和物理意義，每個部分一個新的文章。就算一章要花一周時間，也得慢下來搞。

4、go ahead，時間還來得及。2017年11月15日00:04:46

推薦閱讀：