機器學習第一課：決策樹學習概述與實現

選自HEARTBEAT，作者：Ishan Sharma，機器之心編譯。

基於樹的學習演算法在數據科學競賽中相當常見。這些演算法給預測模型賦予了準確性、穩定性以及易解釋性。其中，決策樹演算法也是引人關注的「隨機森林」演算法的基礎構造模塊。本文介紹了決策樹的概念和簡單實現，使用生動的示例幫助理解，希望能夠對你有所幫助。

從 Kaggle 到課堂，機器學習第一課就是決策樹。之所以關注決策樹，是因為與其他 ML 方法相比，決策樹的數學複雜度不高，同時能為分類問題提供足夠的精度。

對於 ML 的入門者來說，決策樹很容易上手。本教程將介紹：

• 決策樹是什麼
• 如何構建決策樹
• 使用 Python 構建決策樹

決策樹是什麼

我們跳過正式定義，從概念上了解一下決策樹。試想你坐在辦公室里，感覺自己餓了，想出去吃點東西，但是午餐要下午 1 點才開始。那麼你怎麼辦呢？當然，你會看一下時間，然後決定能否出去。你可以按照以下邏輯進行思考：

我們剛剛搭了一個決策樹！這是一個簡單的版本，但我們可以通過加入天氣、成本等因素構建一個更為複雜的決策樹。如果你想和你的朋友 Jon Snow 去一家中餐館吃午飯，決策邏輯可以這樣表示：

這也是一個決策樹。從頂部開始，循著描述當前狀況的路線一路向下，直到做出決定。

注意事項

我們把場景切換到計算機世界。我們剛剛畫的每一個框叫做一個節點。最上面的節點叫做根節點，下面每層的節點叫做葉節點，可以把它想成現實世界中的一棵樹，但是根朝上。

每個節點測試我們的世界（數據集）中的某個屬性，從節點引出的每個分支對應於該屬性的值。給定一棵決策樹，決策過程如下：

1. 從根節點開始
2. 觀察根節點屬性的值
3. 按照與觀察值對應的路徑往下走
4. 重複以上步驟，直至到達葉節點，這樣就能做出決策

如何構建決策樹？

構建決策樹不需要從頭開始（除非你是一個像我一樣的學生）。儘管如此，這也是一個很好的學習經驗，你將學到一些有趣的概念。

構建決策樹最常用的演算法是 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/

1. 創建新文件夾。
2. 從 GitHub 下載 data.csv（https://github.com/ishansharma/decision_trees_tutorial/blob/master/data.csv）。
3. 你可能需要安裝 Scipy、Scikit-Learn 和 Pandas，如果沒有安裝的話。我推薦使用虛擬環境，參見：http://docs.python-guide.org/en/latest/dev/virtualenvs/。從終端運行以下命令行，安裝 Pandas 和 Scikit-Learn：

pip install scikit-learnpip install scipypip install pandas

4. 安裝後，創建新文件 decision_tree.py，並將以下兩行添加進去：

from pandas import read_csvfrom sklearn import tree

5. 使用 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.Class

12. 差不多完成了。我們現在已經準備好訓練決策樹了。添加以下兩行在我們的數據上訓練決策樹：

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]。

繼續研究

經過以上學習，你應該對決策樹有所了解，同時學會了簡單的實現。如果希望進一步探索，你可以參考這些資源：

1. Scikit-Learn 上的決策樹頁面，討論在更大的數據集和其他度量下分割數據：http://scikit-learn.org/stable/modules/tree.html
2. Kaggle 上的機器學習教程，一個深度教程，教你參與 Kaggle 競賽，並構建一個住房數據的決策樹模型：https://www.kaggle.com/learn/machine-learning
3. Saving your Scikit Models：本教程中，每次運行都會訓練一遍模型。這在小數據集中還可以接受，但對於更大的數據集來說最好是一次訓練，隨後僅使用。這個教程可以教你如何保存自己的模型：http://scikit-learn.org/stable/modules/model_persistence.html
4. 將訓練好的模型轉換為 Core ML：如果你為另一個數據集訓練了自己的決策樹，並希望在 iOS 設備上運行，那麼你就需要將已訓練模型轉換為 Core ML 框架版本：https://developer.apple.com/documentation/coreml/converting_trained_models_to_core_ml

原文鏈接：https://heartbeat.fritz.ai/introduction-to-decision-tree-learning-cd604f85e236

推薦閱讀：