基於樹的學習演算法在資料科學競賽中相當常見。 這些演算法給預測模型賦予了準確性、穩定性以及易解釋性。 其中， 決策樹演算法也是引人關注的「隨機森林」演算法的基礎構造模組。 本文介紹了決策樹的概念和簡單實現， 使用生動的示例幫助理解， 希望能夠對你有所幫助。
從 Kaggle 到課堂， 機器學習第一課就是決策樹。 之所以關注決策樹， 是因為與其他 ML 方法相比， 決策樹的數學複雜度不高， 同時能為分類問題提供足夠的精度。
對於 ML 的入門者來說， 決策樹很容易上手。 本教程將介紹：
決策樹是什麼
如何構建決策樹
使用 Python 構建決策樹
決策樹是什麼
我們跳過正式定義， 從概念上瞭解一下決策樹。 試想你坐在辦公室裡， 感覺自己餓了， 想出去吃點東西， 但是午餐要下午 1 點才開始。 那麼你怎麼辦呢？當然， 你會看一下時間， 然後決定能否出去。 你可以按照以下邏輯進行思考：
我們剛剛搭了一個決策樹！這是一個簡單的版本， 但我們可以通過加入天氣、成本等因素構建一個更為複雜的決策樹。 如果你想和你的朋友 Jon Snow 去一家中餐館吃午飯， 決策邏輯可以這樣表示：
這也是一個決策樹。 從頂部開始， 循著描述當前狀況的路線一路向下， 直到做出決定。
注意事項
我們把場景切換到電腦世界。 我們剛剛畫的每一個框叫做一個節點。 最上面的節點叫做根節點， 下面每層的節點叫做葉節點， 可以把它想成現實世界中的一棵樹， 但是根朝上。
每個節點測試我們的世界（資料集）中的某個屬性，
從根節點開始
觀察根節點屬性的值
按照與觀察值對應的路徑往下走
重複以上步驟， 直至到達葉節點， 這樣就能做出決策
如何構建決策樹？
構建決策樹不需要從頭開始（除非你是一個像我一樣的學生）。 儘管如此， 這也是一個很好的學習經驗， 你將學到一些有趣的概念。
構建決策樹最常用的演算法是 ID3， 該演算法非常簡單。 以下是演算法偽代碼：
ID3 (Examples, Target_Attribute, Attributes) Create a root node for the tree If all examples are positive, Return the single-node tree Root, with label = +. If all examples are negative, Return the single-node tree Root, with label = -. If Atributes list is empty, then Return the single node tree Root, with label = most common value of the target attribute in the examples. Otherwise Begin A ← The Attribute that best classifies examples. Decision Tree attribute for Root = A. For each possible value, vi, of A, Add a new tree branch below Root, corresponding to the test A = vi. Let Examples(vi) be the subset of examples that have the value vi for A If Examples(vi) is empty Then below this new branch add a leaf node with label = most common target value in the examples Else below this new branch add the subtree ID3 (Examples(vi), Target_Attribute, Attributes – {A}) End Return Root你將注意到這樣一個細節：在迴圈開始之後， 演算法必須選擇一個屬性， 為樣本分類選出最佳方案。 那麼演算法會怎麼做呢？為了理解這一點， 我們必須深入瞭解一些數學知識。
資訊增益和熵
資訊增益是選擇最佳屬性常用且容易上手的方法之一。 它使用另一種叫做熵的屬性計算出來。
熵是物理學和數學中的概念， 指系統的隨機性或混亂度。 在資訊理論中， 它指的是一組樣本的混亂度。
我們通過一個例子來說明：你有兩個裝滿巧克力的袋子。 巧克力有紅的也有藍的。 你想通過計算巧克力的數量來測量袋子的熵。 所以你坐下來開始數。 2 分鐘後， 你發現第一袋有 50 塊巧克力。 其中 25 塊是紅色的， 25 塊是藍色的。 第二袋也有 50 塊巧克力， 都是藍色的。
在這種情況下， 第一個袋子的熵是 1， 因為裡面的巧克力呈均勻分佈。 第二個袋子的熵為零， 因為裡面的巧克力沒有隨機性。
我們用下面這個公式計算一個系統的熵：
在這個公式中，c 代表類別或屬性的總數，p_i 代表屬於第 i 類的樣本數量。是不是有點懵？我們通過例子瞭解一下：
讓我們回到剛剛的巧克力袋子。我們有兩個類別：紅色（R）和藍色（B）。第一個袋子裡有 25 塊紅色巧克力。巧克力總數是 50。因此，p_i=25/50。藍色類別也是這樣處理。把這些值代入熵方程，我們得到以下結果：
解方程，結果如下：
如果想驗證結果或嘗試其他例子，請移步 Wolfram Alpha：http://www.wolframalpha.com/input/?i=-(25%2F50)log2(25%2F50)+-+(25%2F50)log2(25%2F50)。
繼續計算第二個袋子的熵，裡面有 50 塊紅色巧克力，0 塊藍色巧克力。得到的熵是 0。
如果你理解這個概念，太好了！我們現在轉到資訊增益。
資訊增益
資訊增益是由基於給定屬性的樣本分割導致的熵下降。從數學角度上看，資訊增益的定義為：
S 代表整個樣本集，A 代表我們想要分割的屬性。|S| 代表樣本數量，|Sv| 表示屬性 A 當前值的樣本數量。
仍然很複雜，是不是？那我們舉個例子，看看它的工作流程。
構建決策樹
首先，給巧克力的例子添加一些細節。我們已經知道袋 1 中有 25 塊紅色巧克力、25 塊藍色巧克力。現在，我們還要考慮巧克力的品牌。紅色巧克力中，有 15 塊是士力架，10 塊是 Kit Kat 牌。藍色巧克力中，20 塊是 Kit Kat 牌，5 塊是士力架。假設我們只想吃紅色的士力架。那麼這裡，紅色士力架（15）是正例，其他的巧克力（如紅色 Kit Kat 和藍色士力架）都是負例。
現在，與我們的類別（吃／不吃）相關的資料集的熵是：
現在我們來回顧一下，我們有 50 塊巧克力。如果只看屬性「顏色」，則我們有 25 個紅色的、25 個藍色的。如果看屬性「品牌」，則我們有 20 塊士力架、30 塊 Kit Kat 巧克力。
為了構建決策樹，我們需要選擇其中一個屬性作為根節點。我們想要選擇具備最高資訊增益的屬性。現在我們來計算這些屬性的資訊增益。
顏色相關的資訊增益是：
我們剛才計算了與類別相關的巧克力的熵，是 0.8812。如果我們想吃 15 塊士力架而不是 10 塊 Kit Kat，則紅色巧克力的熵是：
如果我們不想吃藍色巧克力，則熵為 0。
我們的資訊增益計算就變成了：
如果我們分割顏色，則資訊增益是 0.3958。
現在我們來看下品牌。如果我們想吃 15 塊士力架（共有 20 塊），不想吃 Kit Kat。則士力架的熵是：
如果我們不吃 Kit Kat，則熵為 0。信息增益為：
品牌分割的信息增益是 0.5567。
由於品牌的資訊增益較大，我們將基於品牌進行分割。下一級，我們只要左邊的顏色。我們可以輕鬆地根據顏色進行分割，無需進行任何計算。決策樹如下：
誰能想到吃塊巧克力這麼難呢？
現在你應該瞭解決策樹的運行原理了。
使用 Python 3 實現決策樹
現在我們繼續為巧克力資料集構建決策樹。
代碼和資料位址：https://github.com/ishansharma/decision_trees_tutorial/
創建新資料夾。
從 GitHub 下載 data.csv（https://github.com/ishansharma/decision_trees_tutorial/blob/master/data.csv）。
你可能需要安裝 Scipy、Scikit-Learn 和 Pandas，如果沒有安裝的話。我推薦使用虛擬環境，參見：http://docs.python-guide.org/en/latest/dev/virtualenvs/。從終端運行以下命令列，安裝 Pandas 和 Scikit-Learn：
pip install scikit-learnpip install scipypip install pandas4. 安裝後，創建新檔 decision_tree.py，並將以下兩行添加進去：
from pandas import read_csvfrom sklearn import tree5. 使用 Pandas 載入資料：
data = read_csv("data.csv")6. Pandas 可以處理大型資料集，且具備大量視覺化功能。它在使用 Python 的大資料流程程中廣泛使用，因此使用 Pandas 是個好主意。在 Pandas 中你可以使用 head() 方法快速查看載入資料：
print(data.head())下圖顯示了資料的前 5 行。
7. 我使用 Class 列來確定我們是否想吃巧克力。1 代表吃，0 代表不吃。
8. 接下來，我們需要對資料執行一些預處理。Scikit-Learn 預設不支援文本標籤，因此我們使用 Pandas 將文本標籤轉換成數位。只需要添加以下兩行：
data['Color'] = data['Color'].map({'Red': 0, 'Blue': 1})data['Brand'] = data['Brand'].map({'Snickers': 0, 'Kit Kat': 1})9. 剛才我們改變了 Color 屬性，用 0 代表紅色，1 代表藍色。類似地，在 Brand 列中，我們用 0 替代士力架，用 1 替換 Kit Kat。
10. 如果你使用 head() 查看資料集，你將看到品牌和顏色的值已經變成了整數：
11. 最後，按慣例用 X 表示訓練屬性，Y 表示輸出類別，因此我們執行以下命令：
predictors = ['Color', 'Brand']X = data[predictors]Y = data.Class12. 差不多完成了。我們現在已經準備好訓練決策樹了。添加以下兩行在我們的資料上訓練決策樹：
decisionTreeClassifier = tree.DecisionTreeClassifier(criterion="entropy")dTree = decisionTreeClassifier.fit(X, Y)13. 完成了嗎？我們對決策樹進行快速視覺化。添加下列行，並運行程式：
dotData = tree.export_graphviz(dTree, out_file=None)print(dotData)14. 輸出如下：
15. 複製輸出，訪問 WebGraphviz (http://www.webgraphviz.com/) 並粘貼輸出，點擊 Generate Graph。你講看到一個與上文決策樹類似的決策樹：
16. 這顆樹有點難懂，因為有很多額外資訊，不過你可以看到它先基於列 1（Brand）進行分割，再基於列 2（Color）進行分割。
一旦構建處這顆樹，那麼未來的預測就很簡單了。我們來看一下我們是否想吃藍色的 Kit Kat 巧克力。
將以下行添加至 decision_tree.py 文件的末尾：
print(dTree.predict([[1, 1]]))輸出為 [0]，意味著分類是不吃。如果你嘗試紅色士力架（print(dTree.predict([[0, 0]]))），則輸出是 [1]。
繼續研究
經過以上學習，你應該對決策樹有所瞭解，同時學會了簡單的實現。如果希望進一步探索，你可以參考這些資源：
Scikit-Learn 上的決策樹頁面，討論在更大的資料集和其他度量下分割資料：http://scikit-learn.org/stable/modules/tree.html
Kaggle 上的機器學習教程，一個深度教程，教你參與 Kaggle 競賽，並構建一個住房資料的決策樹模型：https://www.kaggle.com/learn/machine-learning
Saving your Scikit Models：本教程中，每次運行都會訓練一遍模型。這在小資料集中還可以接受，但對於更大的資料集來說最好是一次訓練，隨後僅使用。這個教程可以教你如何保存自己的模型：http://scikit-learn.org/stable/modules/model_persistence.html
將訓練好的模型轉換為 Core ML：如果你為另一個資料集訓練了自己的決策樹，並希望在 iOS 設備上運行，那麼你就需要將已訓練模型轉換為 Core ML 框架版本：https://developer.apple.com/documentation/coreml/converting_trained_models_to_core_ml
在這個公式中，c 代表類別或屬性的總數，p_i 代表屬於第 i 類的樣本數量。是不是有點懵？我們通過例子瞭解一下：
讓我們回到剛剛的巧克力袋子。我們有兩個類別：紅色（R）和藍色（B）。第一個袋子裡有 25 塊紅色巧克力。巧克力總數是 50。因此，p_i=25/50。藍色類別也是這樣處理。把這些值代入熵方程，我們得到以下結果：
解方程，結果如下：
如果想驗證結果或嘗試其他例子，請移步 Wolfram Alpha：http://www.wolframalpha.com/input/?i=-(25%2F50)log2(25%2F50)+-+(25%2F50)log2(25%2F50)。
繼續計算第二個袋子的熵，裡面有 50 塊紅色巧克力，0 塊藍色巧克力。得到的熵是 0。
如果你理解這個概念，太好了！我們現在轉到資訊增益。
資訊增益
資訊增益是由基於給定屬性的樣本分割導致的熵下降。從數學角度上看，資訊增益的定義為：
S 代表整個樣本集，A 代表我們想要分割的屬性。|S| 代表樣本數量，|Sv| 表示屬性 A 當前值的樣本數量。
仍然很複雜，是不是？那我們舉個例子，看看它的工作流程。
構建決策樹
首先，給巧克力的例子添加一些細節。我們已經知道袋 1 中有 25 塊紅色巧克力、25 塊藍色巧克力。現在，我們還要考慮巧克力的品牌。紅色巧克力中，有 15 塊是士力架，10 塊是 Kit Kat 牌。藍色巧克力中，20 塊是 Kit Kat 牌，5 塊是士力架。假設我們只想吃紅色的士力架。那麼這裡，紅色士力架（15）是正例，其他的巧克力（如紅色 Kit Kat 和藍色士力架）都是負例。
現在，與我們的類別（吃／不吃）相關的資料集的熵是：
現在我們來回顧一下，我們有 50 塊巧克力。如果只看屬性「顏色」，則我們有 25 個紅色的、25 個藍色的。如果看屬性「品牌」，則我們有 20 塊士力架、30 塊 Kit Kat 巧克力。
為了構建決策樹，我們需要選擇其中一個屬性作為根節點。我們想要選擇具備最高資訊增益的屬性。現在我們來計算這些屬性的資訊增益。
顏色相關的資訊增益是：
我們剛才計算了與類別相關的巧克力的熵，是 0.8812。如果我們想吃 15 塊士力架而不是 10 塊 Kit Kat，則紅色巧克力的熵是：
如果我們不想吃藍色巧克力，則熵為 0。
我們的資訊增益計算就變成了：
如果我們分割顏色，則資訊增益是 0.3958。
現在我們來看下品牌。如果我們想吃 15 塊士力架（共有 20 塊），不想吃 Kit Kat。則士力架的熵是：
如果我們不吃 Kit Kat，則熵為 0。信息增益為：
品牌分割的信息增益是 0.5567。
由於品牌的資訊增益較大，我們將基於品牌進行分割。下一級，我們只要左邊的顏色。我們可以輕鬆地根據顏色進行分割，無需進行任何計算。決策樹如下：
誰能想到吃塊巧克力這麼難呢？
現在你應該瞭解決策樹的運行原理了。
使用 Python 3 實現決策樹
現在我們繼續為巧克力資料集構建決策樹。
代碼和資料位址：https://github.com/ishansharma/decision_trees_tutorial/
創建新資料夾。
從 GitHub 下載 data.csv（https://github.com/ishansharma/decision_trees_tutorial/blob/master/data.csv）。
你可能需要安裝 Scipy、Scikit-Learn 和 Pandas，如果沒有安裝的話。我推薦使用虛擬環境，參見：http://docs.python-guide.org/en/latest/dev/virtualenvs/。從終端運行以下命令列，安裝 Pandas 和 Scikit-Learn：
pip install scikit-learnpip install scipypip install pandas4. 安裝後，創建新檔 decision_tree.py，並將以下兩行添加進去：
from pandas import read_csvfrom sklearn import tree5. 使用 Pandas 載入資料：
data = read_csv("data.csv")6. Pandas 可以處理大型資料集，且具備大量視覺化功能。它在使用 Python 的大資料流程程中廣泛使用，因此使用 Pandas 是個好主意。在 Pandas 中你可以使用 head() 方法快速查看載入資料：
print(data.head())下圖顯示了資料的前 5 行。
7. 我使用 Class 列來確定我們是否想吃巧克力。1 代表吃，0 代表不吃。
8. 接下來，我們需要對資料執行一些預處理。Scikit-Learn 預設不支援文本標籤，因此我們使用 Pandas 將文本標籤轉換成數位。只需要添加以下兩行：
data['Color'] = data['Color'].map({'Red': 0, 'Blue': 1})data['Brand'] = data['Brand'].map({'Snickers': 0, 'Kit Kat': 1})9. 剛才我們改變了 Color 屬性，用 0 代表紅色，1 代表藍色。類似地，在 Brand 列中，我們用 0 替代士力架，用 1 替換 Kit Kat。
10. 如果你使用 head() 查看資料集，你將看到品牌和顏色的值已經變成了整數：
11. 最後，按慣例用 X 表示訓練屬性，Y 表示輸出類別，因此我們執行以下命令：
predictors = ['Color', 'Brand']X = data[predictors]Y = data.Class12. 差不多完成了。我們現在已經準備好訓練決策樹了。添加以下兩行在我們的資料上訓練決策樹：
decisionTreeClassifier = tree.DecisionTreeClassifier(criterion="entropy")dTree = decisionTreeClassifier.fit(X, Y)13. 完成了嗎？我們對決策樹進行快速視覺化。添加下列行，並運行程式：
dotData = tree.export_graphviz(dTree, out_file=None)print(dotData)14. 輸出如下：
15. 複製輸出，訪問 WebGraphviz (http://www.webgraphviz.com/) 並粘貼輸出，點擊 Generate Graph。你講看到一個與上文決策樹類似的決策樹：
16. 這顆樹有點難懂，因為有很多額外資訊，不過你可以看到它先基於列 1（Brand）進行分割，再基於列 2（Color）進行分割。
一旦構建處這顆樹，那麼未來的預測就很簡單了。我們來看一下我們是否想吃藍色的 Kit Kat 巧克力。
將以下行添加至 decision_tree.py 文件的末尾：
print(dTree.predict([[1, 1]]))輸出為 [0]，意味著分類是不吃。如果你嘗試紅色士力架（print(dTree.predict([[0, 0]]))），則輸出是 [1]。
繼續研究
經過以上學習，你應該對決策樹有所瞭解，同時學會了簡單的實現。如果希望進一步探索，你可以參考這些資源：
Scikit-Learn 上的決策樹頁面，討論在更大的資料集和其他度量下分割資料：http://scikit-learn.org/stable/modules/tree.html
Kaggle 上的機器學習教程，一個深度教程，教你參與 Kaggle 競賽，並構建一個住房資料的決策樹模型：https://www.kaggle.com/learn/machine-learning
Saving your Scikit Models：本教程中，每次運行都會訓練一遍模型。這在小資料集中還可以接受，但對於更大的資料集來說最好是一次訓練，隨後僅使用。這個教程可以教你如何保存自己的模型：http://scikit-learn.org/stable/modules/model_persistence.html
將訓練好的模型轉換為 Core ML：如果你為另一個資料集訓練了自己的決策樹，並希望在 iOS 設備上運行，那麼你就需要將已訓練模型轉換為 Core ML 框架版本：https://developer.apple.com/documentation/coreml/converting_trained_models_to_core_ml