決策樹-ID3

從一副圖開始學起

在上圖中,最上面的節點叫做根節點,下面每層的節點叫做葉節點,可以把它想成現實世界中的一棵樹,但是根朝上。

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

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

信息增益與信息熵

熵的含義是指一組樣本的不確定性。這是一種常用的選擇最佳屬性的方法。

  • 計算一個系統的熵:

公式中各個字母的含義:

c 代表類別或者屬性的總數;

p_i 代表屬於第i類的樣本數量的比率

  • 通過一個例子來理解

你有兩個裝滿巧克力的袋子。巧克力有紅的也有藍的。你想通過計算巧克力的數量來測量袋子的熵。所以你坐下來開始數。2 分鐘後,你發現第一袋有 50 塊巧克力。其中 25 塊是紅色的,25 塊是藍色的。第二袋也有 50 塊巧克力,都是藍色的。

解答:

第一個袋子里有 25 塊紅色巧克力。巧克力總數是 50。因此,p_i=25/50。藍色類別也是這樣處理。把這些值代入熵方程,我們得到以下結果:

解算方程:

如果我們的第二個袋子,裡面有50塊紅色巧克力,0 塊藍色巧克力。那麼信息熵為0.

  • 信息增益

信息增益是由基於給定屬性的樣本分割導致的熵下降,信息增益的定義為:

S 代表整個樣本集,

A 代表我們想要分割的屬性。

|S| 代表樣本數量,

|Sv| 表示屬性

A 當前值的樣本數量。

構建決策樹

首先,給巧克力的例子添加一些細節。我們已經知道袋 1 中有 25 塊紅色巧克力、25 塊藍色巧克力。現在,我們還要考慮巧克力的品牌。紅色巧克力中,有 15 塊是士力架,10 塊是 Kit Kat 牌。藍色巧克力中,20 塊是 Kit Kat 牌,5 塊是士力架。假設我們只想吃紅色的士力架。那麼這裡,紅色士力架(15)是正例,其他的巧克力(如紅色 Kit Kat 和藍色士力架)都是負例。

現在,與我們的類別(吃/不吃)相關的數據集的熵是:

這裡我們有兩個屬性:

屬性1 - 顏色 — 其中紅色有25個,藍色25個.

屬性2 - 品牌 — 其中20個是士力架,30個是Kit Kat 巧克力.

樣本的標籤 - 吃與不吃 — 紅色士力架(吃),其他巧克力(不吃).

為了構建決策樹,我們需要選擇其中一個屬性作為根節點。我們想要選擇具備最高信息增益的屬性。現在我們來計算這些屬性的信息增益。

  • 顏色的信息增益

因為我們想要吃的是紅色的士力架,所有紅色巧克力的熵:

因為我們不吃藍色巧克力,所有熵為0.

顏色屬性的信息增益:

也就是若採用顏色劃分數據集,那麼信息增益為0.3958.

由於我們不吃KitKat,所以熵為0.信息增益為:

也就是採用品牌分割數據集的信息增益為0.5567.

由於品牌的信息增益較大,我們將基於品牌進行分割。下一級,我們只要左邊的顏色。我們可以輕鬆地根據顏色進行分割,無需進行任何計算。決策樹如下:

通過python實現ID3決策樹

from pandas import read_csvfrom sklearn import treedata = read_csv("data.csv") #使用 Pandas 載入數據#Scikit-Learn 默認不支持文本標籤,因此使用 Pandas 將文本標籤轉換成數字。 顏色: 用 0 代表紅色, 1 代表藍色。類似地。 品牌: 用 0 替代士力架, 用 1 替換 Kit Kat。data[Color] = data[Color].map({Red: 0, Blue: 1})data[Brand] = data[Brand].map({Snickers: 0, Kit Kat: 1})predictors = [Color, Brand] #訓練數據X = data[predictors] #訓練數據Y = data.Class #輸出類別#訓練決策樹decisionTreeClassifier = tree.DecisionTreeClassifier(criterion="entropy")dTree = decisionTreeClassifier.fit(X, Y)#輸出訓練結果dotData = tree.export_graphviz(dTree, out_file=None)print(dotData)#測試決策樹print(dTree.predict([[1,1]]))

我們上面的吃用標籤 — 1,不吃用標籤 — 0.

推薦閱讀:

R語言實例——基於鄰近的分類預測(KNN演算法)
筆記:簡單理解邏輯回歸(分類演算法)

TAG:SVM | 分類演算法 | 機器學習 |