決策樹-ID3
從一副圖開始學起
在上圖中,最上面的節點叫做根節點,下面每層的節點叫做葉節點,可以把它想成現實世界中的一棵樹,但是根朝上。
每個節點測試我們的數據集中的某個屬性,從節點引出的每個分支對應於該屬性的值。給定一棵決策樹,決策過程如下:
- 從根節點開始
- 觀察根節點屬性的值
- 按照與觀察值對應的路徑往下走
- 重複以上步驟,直至到達葉節點,這樣就能做出決策
信息增益與信息熵
熵的含義是指一組樣本的不確定性。這是一種常用的選擇最佳屬性的方法。
- 計算一個系統的熵:
公式中各個字母的含義:
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.
推薦閱讀: