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

選自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 實現決策樹

現在我們繼續為巧克力數據集構建決策樹。

代碼和數據地址:github.com/ishansharma/

  1. 創建新文件夾。
  2. 從 GitHub 下載 data.csv(github.com/ishansharma/)。
  3. 你可能需要安裝 Scipy、Scikit-Learn 和 Pandas,如果沒有安裝的話。我推薦使用虛擬環境,參見:docs.python-guide.org/e。從終端運行以下命令行,安裝 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 (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 上的決策樹頁面,討論在更大的數據集和其他度量下分割數據:scikit-learn.org/stable
  2. Kaggle 上的機器學習教程,一個深度教程,教你參與 Kaggle 競賽,並構建一個住房數據的決策樹模型:kaggle.com/learn/machin
  3. Saving your Scikit Models:本教程中,每次運行都會訓練一遍模型。這在小數據集中還可以接受,但對於更大的數據集來說最好是一次訓練,隨後僅使用。這個教程可以教你如何保存自己的模型:scikit-learn.org/stable
  4. 將訓練好的模型轉換為 Core ML:如果你為另一個數據集訓練了自己的決策樹,並希望在 iOS 設備上運行,那麼你就需要將已訓練模型轉換為 Core ML 框架版本:developer.apple.com/doc

原文鏈接:heartbeat.fritz.ai/intr

推薦閱讀:

艾米機器人能做什麼
不忘初心,牢記使命!
從alpha go擊潰柯潔所想到的
活久見啊!一個虛擬網紅,黑了另一個虛擬網紅的ins賬號...

TAG:機器學習 | 決策樹 | 人工智慧 |