决策树算法及实现
在計算機科學中，樹是一種很重要的數據結構，比如我們最為熟悉的二叉查找樹（Binary Search Tree），紅黑樹（Red-Black Tree）等，通過引入樹這種數據結構，我們可以很快地縮小問題規模，實現高效的查找。
在監督學習中，面對樣本中復雜多樣的特征，選取什么樣的策略可以實現較高的學習效率和較好的分類效果一直是科學家們探索的目標。那么，樹這種結構到底可以如何用于機器學習中呢？我們先從一個游戲開始。
我們應該都玩過或者聽過這么一種游戲：游戲中，出題者寫下一個明星的名字，其他人需要猜出這個人是誰。當然，如果游戲規則僅此而已的話，幾乎是無法猜出來的，因為問題的規模太大了。為了降低游戲的難度，答題者可以向出題者問問題，而出題者必須準確回答是或者否，答題者依據回答提出下一個問題，如果能夠在指定次數內確定謎底，即為勝出。加入了問答規則之后，我們是否有可能猜出謎底呢？我們先實驗一下，現在我已經寫下了一個影視明星的名字，而你和我的問答記錄如下：
是男的嗎？Y
是亞洲人嗎？Y
是中國人嗎？N
是印度人嗎？Y
?……
雖然只有短短四個問題，但是我們已經把答案的范圍大大縮小了，那么接下，第5個問題你應該如何問呢？我相信你應該基本可以鎖定答案了，因為我看過的印度電影就那么幾部。我們將上面的信息結構化如下圖所示：
在上面的游戲中，我們針對性的提出問題，每一個問題都可以將我們的答案范圍縮小，在提問中和回答者有相同知識背景的前提下，得出答案的難度比我們想象的要小很多。
回到我們最初的問題中，如何將樹結構用于機器學習中？結合上面的圖，我們可以看出，在每一個節點，依據問題答案，可以將答案劃分為左右兩個分支，左分支代表的是Yes，右分支代表的是No，雖然為了簡化，我們只畫出了其中的一條路徑，但是也可以明顯看出這是一個樹形結構，這便是決策樹的原型。
1.決策樹算法簡介
我們面對的樣本通常具有很多個特征，正所謂對事物的判斷不能只從一個角度，那如何結合不同的特征呢？決策樹算法的思想是，先從一個特征入手，就如同我們上面的游戲中一樣，既然無法直接分類，那就先根據一個特征進行分類，雖然分類結果達不到理想效果，但是通過這次分類，我們的問題規模變小了，同時分類后的子集相比原來的樣本集更加易于分類了。然后針對上一次分類后的樣本子集，重復這個過程。在理想的情況下，經過多層的決策分類，我們將得到完全純凈的子集，也就是每一個子集中的樣本都屬于同一個分類。
比如上圖中，平面坐標中的六個點，我們無法通過其x坐標或者y坐標直接就將兩類點分開。采用決策樹算法思想：我們先依據y坐標將六個點劃分為兩個子類（如水平線所示），水平線上面的兩個點是同一個分類，但是水平線之下的四個點是不純凈的。但是沒關系，我們對這四個點進行再次分類，這次我們以x左邊分類（見圖中的豎線），通過兩層分類，我們實現了對樣本點的完全分類。這樣，我們的決策樹的偽代碼實現如下：
if?y?>?a:
????output dot
else:
????if?x?<?b:
??????????output cross
????else:
??????????output?dot
由這個分類的過程形成一個樹形的判決模型，樹的每一個非葉子節點都是一個特征分割點，葉子節點是最終的決策分類。如下圖所示：
將新樣本輸入決策樹進行判決時，就是將樣本在決策樹上自頂向下，依據決策樹的節點規則進行遍歷，最終落入的葉子節點就是該樣本所屬的分類。
2.決策樹算法流程
上面我們介紹決策樹算法的思想，可以簡單歸納為如下兩點：
每次選擇其中一個特征對樣本集進行分類
對分類后的子集遞歸進行步驟1
看起來是不是也太簡單了呢？實際上每一個步驟我們還有很多考慮的。在第一個步驟中，我們需要考慮的一個最重要的策略是，選取什么樣的特征可以實現最好的分類效果，而所謂的分類效果好壞，必然也需要一個評價的指標。在上文中，我們都用純凈來說明分類效果好，那何為純凈呢？直觀來說就是集合中樣本所屬類別比較集中，最理想的是樣本都屬于同一個分類。樣本集的純度可以用熵來進行衡量。
在信息論中，熵代表了一個系統的混亂程度，熵越大，說明我們的數據集純度越低，當我們的數據集都是同一個類別的時候，熵為0，熵的計算公式如下：
其中，P(xi)表示概率，b在此處取2。比如拋硬幣的時候，正面的概率就是1/2，反面的概率也是1/2，那么這個過程的熵為：
可見，由于拋硬幣是一個完全隨機事件，其結果正面和反面是等概率的，所以具有很高的熵。假如我們觀察的是硬幣最終飛行的方向，那么硬幣最后往下落的概率是1，往天上飛的概率是0，帶入上面的公式中，可以得到這個過程的熵為0，所以，熵越小，結果的可預測性就越強。在決策樹的生成過程中，我們的目標就是要劃分后的子集中其熵最小，這樣后續的的迭代中，就更容易對其進行分類。
既然是遞歸過程，那么就需要制定遞歸的停止規則。在兩種情況下我們停止進一步對子集進行劃分，其一是劃分已經達到可以理想效果了，另外一種就是進一步劃分收效甚微，不值得再繼續了。用專業術語總結終止條件有以下幾個：
子集的熵達到閾值
子集規模夠小
進一步劃分的增益小于閾值
其中，條件3中的增益代表的是一次劃分對數據純度的提升效果，也就是劃分以后，熵減少越多，說明增益越大，那么這次劃分也就越有價值，增益的計算公式如下：
Gain
上述公式可以理解為：計算這次劃分之后兩個子集的熵之和相對劃分之前的熵減少了多少，需要注意的是，計算子集的熵之和需要乘上各個子集的權重，權重的計算方法是子集的規模占分割前父集的比重，比如劃分前熵為e，劃分為子集A和B，大小分別為m和n，熵分別為e1和e2，那么增益就是e - m/(m + n) * e1 - n/(m + n) * e2。
3. 決策樹算法實現
有了上述概念，我們就可以開始開始決策樹的訓練了，訓練過程分為：
選取特征，分割樣本集
計算增益，如果增益夠大，將分割后的樣本集作為決策樹的子節點，否則停止分割
遞歸執行上兩步
上述步驟是依照ID3的算法思想（依據信息增益進行特征選取和分裂），除此之外還有C4.5以及CART等決策樹算法。
算法框架如下：
class?DecisionTree(object):
????def fit(self,?X,?y):
????????# 依據輸入樣本生成決策樹
????????self.root?=?self._build_tree(X,?y)
?
????def _build_tree(self,?X,?y,?current_depth=0):
????????#1. 選取最佳分割特征，生成左右節點
????????#2. 針對左右節點遞歸生成子樹
??????
????def predict_value(self,?x,?tree=None):
????????# 將輸入樣本傳入決策樹中，自頂向下進行判定
????????# 到達葉子節點即為預測值
在上述代碼中，實現決策樹的關鍵是遞歸構造子樹的過程，為了實現這個過程，我們需要做好三件事：分別是節點的定義，最佳分割特征的選擇，遞歸生成子樹。
3.1 節點定義
決策樹的目的是用于分類預測，即各個節點需要選取輸入樣本的特征，進行規則判定，最終決定樣本歸屬到哪一棵子樹，基于這個目的，決策樹的每一個節點需要包含以下幾個關鍵信息：
判決特征：當前節點針對哪一個特征進行判決
判決規則：對于二類問題，這個規則一般是一個布爾表達式
左子樹：判決為TRUE的樣本
右子樹：判決為FALSE的樣本
決策樹節點的定義代碼如下所示：
class?DecisionNode():
????
????def __init__(self,?feature_i=None,?threshold=None,
?????????????????value=None,?true_branch=None,?false_branch=None):
????????self.feature_i?=?feature_i??# 用于測試的特征對應的索引
????????self.threshold?=?threshold??# 判斷規則：>=threshold為true
????????self.value?=?value??# 如果是葉子節點，用于保存預測結果
????????self.true_branch?=?true_branch??# 左子樹
????????self.false_branch?=?false_branch??# 右子樹
3.2 特征選取
特征選取是構造決策樹最關鍵的步驟，其目的是選出能夠實現分割結果最純凈的那個特征，其操作流程的代碼如下：
# 遍歷樣本集中的所有特征，針對每一個特征計算最佳分割點
# 再選取最佳的分割特征
for?feature_i?in?range(n_features):
????# 遍歷集合中某個特征的所有取值
????for?threshold?in?unique_values:
????????# 以當前特征值作為閾值進行分割
????????Xy1,?Xy2?=?divide_on_feature(X_y,?feature_i,?threshold)
????????# 計算分割后的增益
????????gain?=?gain(y,?y1,?y2)
????????# 記錄最佳分割特征，最佳分割閾值
????????if?gain?>?largest_gain:
????????largest_gain?=?gain
????????????best_criteria?=?{
????????????????"feature_i":?feature_i,
????????????????"threshold":?threshold
????????????????}
3.3 節點分裂
節點分裂的時候有兩條處理分支，如果增益夠大，就分裂為左右子樹，如果增益很小，就停止分裂，將這個節點直接作為葉子節點。節點分裂和Gain（分割后增益）的計算可以做一個優化，在上一個步驟中，我們尋找最優分割點的時候其實就可以將最佳分裂子集和Gain計算并保存下來，將上一步中的for循環改寫為：
# 以當前特征值作為閾值進行分割
Xy1,?Xy2?=?divide_on_feature(X_y,?feature_i,?threshold)
# 計算分割后的熵
gain?=?gain(y,?y1,?y2)
# 記錄最佳分割特征，最佳分割閾值
if?gain?>?largest_gain:
????largest_gain?=?gain
????????best_criteria?=?{
????????"feature_i":?feature_i,
????????"threshold":?threshold?,
????????}
????best_sets?=?{
????????"left":?Xy1,
????????"right":?Xy2,
????????"gain":?gain
????????}
為了防止過擬合，需要設置合適的停止條件，比如設置Gain的閾值，如果Gain比較小，就沒有必要繼續進行分割，所以接下來，我們就可以依據gain來決定分割策略：
if?best_sets["gain"]?>?MIN_GAIN:
????# 對best_sets["left"]進一步構造子樹，并作為父節點的左子樹
????# 對best_sets["right"]進一步構造子樹，并作為父節點的右子樹
????...
else:
????# 直接將父節點作為葉子節點
????...
下面，我們結合一組實驗數據來學習決策樹的訓練方法。實驗數據來源于這里，下表中的數據是一組消費調查結果，我們訓練決策樹的目的，就是構造一個分類算法，使得有新的用戶數據時，我們依據訓練結果去推斷一個用戶是否購買這個商品：
| 36-55 | master’s | high | single | yes |
| 18-35 | high school | low | single | no |
| 36-55 | master’s | low | single | yes |
| 18-35 | bachelor’s | high | single | no |
| ?< 18 | high school | low | single | yes |
| 18-35 | bachelor’s | high | married | no |
| 36-55 | bachelor’s | low | married | no |
| > 55 | bachelor’s | high | single | yes |
| 36-55 | master’s | low | married | no |
| > 55 | master’s | low | married | yes |
| 36-55 | master’s | high | single | yes |
| > 55 | master’s | high | single | yes |
| 18 | high school | high | single | no |
| 36-55 | master’s | low | single | yes |
| 36-55 | high school | low | single | yes |
| ?< 18 | high school | low | married | yes |
| 18-35 | bachelor’s | high | married | no |
| > 55 | high school | high | married | yes |
| > 55 | bachelor’s | low | single | yes |
| 36-55 | high school | high | married | no |
從表中可以看出，我們一共有20組調查樣本，每一組樣本包含四個特征，分別是年齡段，學歷，收入，婚姻狀況，而最后一列是所屬分類，在這個問題中就代表是否購買了該產品。
監督學習就是在每一個樣本都有正確答案的前提下，用算法預測結果，然后根據預測情況的好壞，調整算法參數。在決策樹中，預測的過程就是依據各個特征劃分樣本集，評價預測結果的好壞標準是劃分結果的純度。
為了方便處理，我們對樣本數據進行了簡化，將年齡特征按照樣本的特點，轉化為離散的數據，比如小于18對應0，18對應1，18-35對應2，36-55對應3，大于55對應4，以此類推，同樣其他的特征也一樣最數字化處理，教育水平分別映射為0(hight school)，1(bachelor’s)，2(master’s)，收入映射為0(low)和1(hight), 婚姻狀況同樣映射為0(single), 1(married)，最終處理后的樣本，放到一個numpy矩陣中，如下所示：
X_y?=?np.array(
????????[[3,?2,?1,?0,?1],
?????????[2,?0,?0,?0,?0],
?????????[3,?2,?0,?0,?1],
?????????[2,?1,?1,?0,?0],
?????????[0,?0,?0,?0,?1],
?????????[2,?1,?1,?1,?0],
?????????[3,?1,?0,?1,?0],
?????????[4,?1,?1,?0,?1],
?????????[3,?2,?0,?1,?0],
?????????[4,?2,?0,?1,?1],
?????????[3,?2,?1,?0,?1],
?????????[4,?2,?1,?0,?1],
?????????[1,?0,?1,?0,?0],
?????????[3,?2,?0,?0,?1],
?????????[3,?0,?0,?0,?1],
?????????[0,?0,?0,?1,?1],
?????????[2,?1,?1,?1,?0],
?????????[4,?0,?1,?1,?1],
?????????[4,?1,?0,?0,?1],
?????????[3,?0,?1,?1,?0]]
????)
4. 新樣本預測
依照上面的算法構造決策樹，我們將決策樹打印出來，如下所示：
--?Classification?Tree?--
0?:?4?
???T?->?1
???F?->?3?:?1?
??????T?->?0?:?2?
????????????T?->?0
????????????F?->?1
??????F?->?0?:?3?
????????????T?->?1
????????????F?->?0?:?1?
????????????????????????T?->?0
????????????????????????F?->?1
其中，冒號前代表選擇的分割特征，冒號后面代表判別規則，二者組合起來就是一個決策樹的非葉子節點，每個非葉子節點進一步分割為分為True和False分支，對于葉子節點箭頭后面表示最終分類，0表示不購買，1表示購買。由于我們的數據做過簡化，所以上述結果不太直觀，我們將對應的特征以及判斷規則翻譯一下：
年齡?:?大于55?
???是?->?購買
???否?->?收入?:?高?
??????是?->?年齡?:?大于18?
????????????是?->?不購買
????????????否?->?購買
??????否?->?年齡?:?大于36?
????????????是?->?購買
????????????否?->?年齡?:?大于等于18?
????????????????????????是?->?不購買
????????????????????????否?->?購買
決策樹構造完之后，我們就可以用來進行新樣本的分類了。決策樹的預測過程十分容易理解，只需要將從根節點開始，按照節點定義的規則進行判決，選擇對應的子樹，并重復這個過程，直到葉子節點即可。決策樹的預測功能實現代碼如下：
def predict_value(self,?x,?tree=None):
????????# 如果當前節點是葉子節點，直接輸出其值
????????if?tree.value?is?not?None:
????????????return?tree.value
????????# 否則將x按照當前節點的規則進行判決
????????# 如果判決為true選擇左子樹，否則選擇右子樹，
????????feature_value?=?x[tree.feature_i]
????????if?feature_value?>=?tree.threshold:
????????????branch?=?tree.true_branch
????????else:
????????????branch?=?tree.false_branch
????????# 在選中的子樹上遞歸進行判斷
????????return?self.predict_value(x,?branch)
5. 總結
決策樹是一種簡單常用的分類器，通過訓練好的決策樹可以實現對未知的數據進行高效分類。從我們的例子中也可以看出，決策樹模型具有較好的可讀性和描述性，有助于輔助人工分析；此外，決策樹的分類效率高，一次構建后可以反復使用，而且每一次預測的計算次數不超過決策樹的深度。
當然，決策樹也有其缺點。對于連續的特征，比較難以處理，對于多分類問題，計算量和準確率都不理想。此外，在實際應用中，由于其最底層葉子節點是通過父節點中的單一規則生成的，所以通過手動修改樣本特征比較容易欺騙分類器，比如在攔擊郵件識別系統中，用戶可能通過修改某一個關鍵特征，就可以騙過垃圾郵件識別系統。從實現上來講，由于樹的生成采用的是遞歸，隨著樣本規模的增大，計算量以及內存消耗會變得越來越大。
此外，過擬合也是決策樹面臨的一個問題，完全訓練的決策樹(未進行剪紙，未限制Gain的閾值)能夠100%準確地預測訓練樣本，因為其是對訓練樣本的完全擬合，但是，對與訓練樣本以外的樣本，其預測效果可能會不理想，這就是過擬合。解決決策樹的過擬合，除了上文說到的通過設置Gain的閾值作為停止條件之外，通常還需要對決策樹進行剪枝，常用的剪枝策略有：
Pessimistic Error Pruning：悲觀錯誤剪枝
Minimum Error Pruning：最小誤差剪枝
Cost-Complexity Pruning：代價復雜剪枝
?Error-Based Pruning：基于錯誤的剪枝，即對每一個節點，都用一組測試數據集進行測試，如果分裂之后，能夠降低錯誤率，再繼續分裂為兩棵子樹，否則直接作為葉子節點。
Critical Value Pruning：關鍵值剪枝，這就是上文中提到的設置Gain的閾值作為停止條件。
我們以最簡單的方式展示了ID3決策樹的實現方式，如果想要了解不同類型的決策樹的差別，可以參考(https://www.quora.com/What-are-the-differences-between-ID3-C4-5-and-CART)。
另外，關于各種機器學習算法的實現，強烈推薦參考Github倉庫ML-From-Scratch，下載代碼之后，通過pip install -r requirements.txt安裝依賴庫即可運行代碼。
來源：?ZPPenny
www.jianshu.com/p/c4d0837e9439
總結
- 上一篇： 程序员必知的 Python 陷阱与缺陷列
- 下一篇： 不想再被鄙视？那就看进来！ 一文搞懂 P