机器学习系列之手把手教你实现一个决策树
https://www.ibm.com/developerworks/cn/analytics/library/machine-learning-hands-on4-decision-tree/index.html?ca=drs-
決策樹簡介
在前面三篇文章中，分別介紹了支持向量機，?FP-growth?和樸素貝葉斯。其中支持向量機和樸素貝葉斯是分類模塊中的經典算法。本文將介紹分類中的另一種常用算法，決策樹 (decision tree)。決策樹算法又分很多種，常用的有?ID3，C4.5 和 CART 決策樹。其中 ID3 和 C4.5 決策樹更傾向于處理類別型的離散屬性值，對于連續型屬性值，則需要額外利用連續屬性離散化技術將其劃分成離散型屬性值。而 CART 決策樹，即分類回歸樹，直接支持連續型屬性值。由于篇幅限制 CART 樹會放在下一篇文章進行介紹，本文主要詳細介紹 ID3 和 C4.5 決策樹。
決策樹利用了樹型結構進行決策，是經典的 if-then 結構。葉節點存儲類別，內部節點代表特征或屬性。注意本文中提到的特征和屬性是同一個概念。為了讓讀者有一個感性的認識，請看圖1所示決策樹。
圖1. 決策樹示例
圖1所示決策樹用來將數據分為兩類，是蘋果和非蘋果。如圖中所示，圓的和紅的，就是蘋果。不圓的不是蘋果。圓的但不紅的不是蘋果。
本文將著重介紹?ID3?和?C4.5?兩種決策樹。決策樹需要選擇最優特征劃分數據集。這兩種決策樹的不同之處是劃分數據集的最優特征選擇方法不同。用最優特征劃分數據會使得數據集趨于更純，即數據集的類別數更單一，這樣的數據會更有序。衡量數據的混亂程度就必須提到信息和信息熵的概念。
待分類的事物可能劃分在多個類別中，則符號 Xi 的信息是:
可知?P(Xi) 越大，則 I(Xi) 越小，即 Xi 的概率越大，則 Xi 包含的信息越少。
我們都知道物理中的熵用來衡量混亂程度，熵越大說明越混亂，熵越小說明越單一。同樣，信息熵用來衡量信息中的混亂程度。用所有類別所有可能值包含的信息期望值表示信息熵，計算方法如下：
ID3 決策樹利用了信息增益來選擇最優特征，用這種方法選擇的特征是使得信息熵增益最大的特征。而 C4.5 決策樹利用了信息增益比來選擇最優特征。用這種方法選擇的特征是使得信息增益比最大的特征。
為什么要提出信息增益比呢？這是因為只考慮信息增益來劃分數據集是有缺陷的。這種缺陷體現在信息增益對選擇屬性取值多的特征更有利。因為按屬性取值多的特征劃分數據集后，劃分后的各個子數據集的類別更單一，即更趨于有序，這就使得劃分后的信息熵更小，那么信息增益就會更大。信息增益比可以很好的解決這個問題。信息增益比通過引入類似懲罰因子的概念，對屬性取值多的特征會有一定懲罰。
決策樹原理
選擇最優特征
決策樹通過不斷選擇最優特征劃分數據集，對劃分后的子數據集不斷迭代得選擇最優特征劃分，直到所有的數據集屬于同一個類別，或者沒有特征可以選擇為止。選擇最優特征的算法有很多種，ID3 決策樹用信息增益選擇最優特征，C4.5 決策樹用信息增益比選擇最優特征。
信息增益 - 用于 ID3 決策樹
信息增益，顧名思義就是原數據集的信息熵比劃分后數據集的信息熵大的程度。信息增益越大，說明劃分后的數據集信息熵更小，即該數據集類別更趨于一致。
特征 A 對數據集 D 的信息增益 g(D,A)?為 D 的信息熵與按特征 A 進行劃分后 D 的信息熵之差，即
其中，
信息增益比 – 用于 C4.5 決策樹
信息增益比為了避免傾向于選擇屬性值多的特征作為最優特征這個問題，在信息增益的基礎上引入了類似懲罰因子的概念。
特征 A 對數據集 D 的信息增益比gg(D,A)?為信息增益 g(D,A) 與數據集 D 關于特征 A 的取值的熵 HA(D) 的比值，即
其中,
其中，n 是特征 A 取值的個數。HA(D) 就類似懲罰因子，對于屬性值多的特征，雖然信息增益 g(D,A) 會比較大，但是數據集 D 關于特征 A 的取值的熵 HA(D) 會比較大，因而兩者的比值信息增益比 gg(D,A) 會比較小。
除了可以使用信息增益和信息增益比來選擇最優劃分特征之外，基尼指數也可以用來實現這個目的。基尼指數主要用于 CART 樹(即分類回歸樹)的分類樹中的特征選擇。關于基尼指數的詳細內容會在下一篇文章介紹。
用 ID3 決策樹進行分類
本節主要介紹用 ID3 決策樹進行分類。為了便于理解，用表1所示數據集進行詳細說明。利用 C4.5 決策樹進行分類的過程會在下節介紹。
表 1. 示例數據集
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
| 1 | 0 | 0 |
ID3 決策樹選擇最優特征
表1數據集的信息熵為:
-1/5 * log(1/5) - 4/5 * log(4/5) = 0.217
3/5 * H(D1) + 2/5 * H(D0)
= 3/5 * [-1/3 * log(1/3) – 2/3 * log(2/3)] + 2/5 * [-2/2 * log(2/2)]
= 0.166
則信息增益為：0.217 – 0.166 = 0.051
2/5 * H(D1) + 3/5 * H(D0)
= 2/5 * [-1/2 * log(1/2) – 1/2 * log(1/2)] + 3/5 * [-3/3 * log(3/3)]
= 0.120
則信息增益為：0.217 – 0.120 =0.097
綜上所述，由于按特征"紅的"比按特征"圓的"劃分的信息增益大，所以特征"紅的"為最優劃分特征。
按最優特征劃分數據集
按特征"紅的"劃分數據集后，有兩種情況，第一種為如果是紅的:0,則分類:0; 第二種為如果是紅的:1, 則得到如下數據子集 {圓的:1,分類：1; 圓的:0, 分類:0}
接下來需要對數據子集{圓的:1,分類：1; 圓的:0, 分類:0}繼續劃分。由于剩下一個特征，故按特征"圓的"劃分數據子集。劃分后，如果是圓的:1，則分類:1；如果是圓的:0, 則分類:0。
返回的決策樹用字典表示為：
{'紅的': {0: '類別0', 1: {'圓的': {0: '類別0', 1: '類別1'}}}}
用 C4.5 決策樹進行分類
為了讓讀者對 ID3 和 C4.5 決策樹的不同之處有更好的理解，本節介紹用 C4.5 決策樹進行分類。為了便于理解，仍然使用表1所示數據集進行說明。
C4.5 決策樹選擇最優特征
表1數據集的信息熵為:
-1/5 * log(1/5) - 4/5 * log(4/5) = 0.217
1.按特征"圓的"劃分數據集，則信息熵為：
3/5 * H(D1) + 2/5 * H(D0)
= 3/5 * [-1/3 * log(1/3) – 2/3 * log(2/3)] + 2/5 * [-2/2 * log(2/2)]
= 0.166
則信息增益為：0.217 – 0.166 = 0.051
數據集關于特征"圓的"的取值的熵為:
-3/5 * log(3/5) – 2/5 * log(2/5) = 0.29
則信息增益比為0.051 / 0.29 = 0.176
2.按特征"紅的"劃分數據集，則信息熵為：
2/5 * H(D1) + 3/5 * H(D0)
= 2/5 * [-1/2 * log(1/2) – 1/2 * log(1/2)] + 3/5 * [-3/3*log(3/3)]
= 0.120
則信息增益為：0.217 – 0.120 =0.097
數據集關于特征"紅的"的取值的熵為：
-2/5 * log(2/5) – 3/5 * log(3/5) = 0.29
則信息增益比為 0.097 / 0.29 = 0.334
綜上所述，由于按特征"紅的"比按特征"圓的"劃分的信息增益比大，所以特征"紅的"為最優劃分特征。
按最優特征劃分數據集
C4.5 決策樹按最優特征劃分數據集方法與上節 ID3 決策樹方法相同。
實現步驟: 自己動手實現 ID3 和 C4.5 決策樹
本節將介紹如何自己動手實現一個 ID3 和 C4.5 決策樹。由上文的介紹我們已經知道，ID3 決策樹利用信息增益選擇最優劃分特征，從而使劃分后的數據集更加有序。而 C4.5 決策樹利用信息增益比選擇最優劃分特征。兩者除了選擇最優劃分特征的算法不同之外，其余代碼可以共用。
清單 1. 計算熵
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def calcEntropy(dataSet): totalNum = len(dataSet) labelNum = {} entropy = 0 for data in dataSet: ???label = data[-1] if label in labelNum: ???labelNum[label] += 1 else: ???labelNum[label] = 1 for key in labelNum: ???p = labelNum[key] / totalNum entropy -= p * log2(p) return entropy |
清單1用來計算信息熵。先統計不同類別出現的次數，然后除以數據集大小就可得到不同類別的出現頻率 p。最后代入信息熵的計算公式即可計算熵。
清單 2. ID3 決策樹選擇最優特征
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def chooseBestFeatureID3(dataSet, labels): bestFeature = 0 initialEntropy = calcEntropy(dataSet) biggestEntropyG = 0 for i in range(len(labels)): ???currentEntropy = 0 feature = [data[i] for data in dataSet] subSet = splitDataSetByFeature(i, dataSet) totalN = len(feature) for key in subSet: ???prob = len(subSet[key]) / totalN currentEntropy += prob * calcEntropy(subSet[key]) entropyGain = initialEntropy - currentEntropy if(biggestEntropyG < entropyGain): ????biggestEntropyG = entropyGain bestFeature = i return bestFeature |
清單2用于 ID3 決策樹選擇最優特征。選擇時需要利用信息熵增益。首先計算數據集的初始信息熵，然后循環計算按不同的特征劃分后的數據集的信息熵，前一個信息熵減去后一個信息熵的差值就是信息增益。選擇信息增益最大的那個特征作為最優特征。
清單 3. 按特征劃分數據集
| 1 2 3 4 5 6 7 8 9 10 | def splitDataSetByFeature(i, dataSet): subSet = {} feature = [data[i] for data in dataSet] for j in range(len(feature)): ???if feature[j] not in subSet: subSet[feature[j]] = [] splittedDataSet = dataSet[j][:i] splittedDataSet.extend(dataSet[j][i + 1:]) subSet[feature[j]].append(splittedDataSet) return subSet |
清單3用來按數據集的某個特征劃分數據集。先統計該特征的取值，然后按不同取值劃分數據集。注意劃分后的數據集中將不再包含該特征。
清單 4. 結束條件
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def checkIsOneCateg(newDataSet): flag = False categoryList = [data[-1] for data in newDataSet] category = set(categoryList) if(len(category) == 1): ???flag = True return flag def majorityCateg(newDataSet): categCount = {} categList = [data[-1] for data in newDataSet] for c in categList: ???if c not in categCount: ???????categCount[c] = 1 ???else: ???????categCount[c] += 1 sortedCateg = sorted(categCount.items(), key = lambda x:x[1], reverse = ???True) return sortedCateg[0][0] |
清單4是 ID3 決策樹的兩個結束條件的函數。出現兩種條件則需要結束對數據集的劃分。其一，劃分后的數據集屬于同一類別；其二，沒有特征值可繼續劃分。
清單 5. 創建決策樹
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def createDecisionTreeID3(decisionTree, dataSet, labels): bestFeature = chooseBestFeatureID3(dataSet, labels) decisionTree[labels[bestFeature]] = {} currentLabel = labels[bestFeature] subSet = splitDataSetByFeature(bestFeature, dataSet) del(labels[bestFeature]) newLabels = labels[:] for key in subSet: ???newDataSet = subSet[key] flag = checkIsOneCateg(newDataSet) if(flag == True): ???decisionTree[currentLabel][key] = newDataSet[0][-1] else: ???if (len(newDataSet[0]) == 1): #無特征值可劃分 ???????decisionTree[currentLabel][key] = majorityCateg(newDataSet) ???else: ???????decisionTree[currentLabel][key] = {} createDecisionTreeID3(decisionTree[currentLabel][key], newDataSet, ???newLabels) |
清單5用來遞歸創建決策樹。首先選擇最優劃分特征，然后按最優特征劃分數據集。對于劃分后的數據集，先判斷是否達到結束條件，如果是，則返回類別，并停止對數據子集的劃分；如果不是，則繼續遞歸構建決策樹。
清單 6. 將測試數據分類
| 1 2 3 4 5 6 7 | def classifyTestData(decisionTree, testData): result1 = decisionTree['round'][testData[0]] if(type(result1) == str): ???category = result1 else: ???category = decisionTree['round'][testData[0]]['red'][testData[1]] return category |
清單6用來對測試數據分類。如果到達葉節點，則返回該分類；否則，繼續嘗試其他特征，直到到達葉節點為止，然后返回該分類。
清單 7. C4.5 決策樹選擇最優特征
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def chooseBestFeatureC45(dataSet, labels): bestFeature = 0 initialEntropy = calcEntropy(dataSet) biggestEntropyGR = 0 for i in range(len(labels)): ???currentEntropy = 0 feature = [data[i] for data in dataSet] entropyFeature = calcEntropyForFeature(feature) subSet = splitDataSetByFeature(i, dataSet) totalN = len(feature) for key in subSet: ???prob = len(subSet[key]) / totalN currentEntropy += prob * calcEntropy(subSet[key]) entropyGain = initialEntropy - currentEntropy entropyGainRatio = entropyGain / entropyFeature if(biggestEntropyGR < entropyGainRatio): biggestEntropyGR = entropyGainRatio bestFeature = i return bestFeature |
清單7用于 C4.5 決策樹選擇最優特征。選擇時需要選信息增益比最大的特征作為最優特征。首先計算數據集的初始信息熵，然后循環計算按不同的特征劃分后的數據集的信息熵，前一個信息熵減去后一個信息熵的差值就是信息增益。信息增益除以數據集關于某特征取值的熵就是信息增益比。最后將信息增益比最大的那個特征作為最優特征。
代碼下載 (code downloads)
本文所有 ID3 和 C4.5 決策樹實現代碼可在文末下載。
本文數據集簡介
圖2. 數據集樣例
數據集是關于判斷某水果是否為蘋果的6條數據。數據集前兩列分別代表兩個特征，分別是圓的和紅的。數據集第三列代表類別。拿第一條數據為例，指的是圓的和紅的水果是蘋果。
應用示例: 應用實現的決策樹解決實際問題
清單 8. 用決策樹解決實際問題
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | if __name__ == '__main__': ???dataSetID3, labelsID3 = createDataSet() testData1 = [0, 1] testData2 = [1, 1] bestFeatureID3 = chooseBestFeatureID3(dataSetID3, labelsID3) decisionTreeID3 = {} createDecisionTreeID3(decisionTreeID3, dataSetID3, labelsID3) print("ID3 decision tree: ", decisionTreeID3) category1ID3 = classifyTestData(decisionTreeID3, testData1) print(testData1 , ", classified as by ID3: " , category1ID3) category2ID3 = classifyTestData(decisionTreeID3, testData2) print(testData2 , ", classified as by ID3: " , category2ID3) dataSetC45, labelsC45 = createDataSet() bestFeatureC45 = chooseBestFeatureC45(dataSetC45, labelsC45) decisionTreeC45 = {} createDecisionTreeC45(decisionTreeC45, dataSetC45, labelsC45) print("C4.5 decision tree: ", decisionTreeC45) category1C45 = classifyTestData(decisionTreeC45, testData1) print(testData1 , ", classified as by C4.5: " , category1C45) category2C45 = classifyTestData(decisionTreeC45, testData2) print(testData2 , ", classified as by C4.5: " , category2C45) |
清單8用上一節實現的 ID3 和 C4.5 決策樹解決實際問題。先創建數據集，然后選擇最優劃分特征，接著創建決策樹。該清單中有兩條測試數據，分別是[0, 1]和[1, 1]，代表非圓的和紅的、圓的和紅的兩條數據。
運行結果：
ID3 decision tree: {'round': {0: 'no', 1: {'red': {0: 'no', 1: 'yes'}}}}
[0, 1] , classified as by ID3: no
[1, 1] , classified as by ID3: yes
C4.5 decision tree: {'round': {0: 'no', 1: {'red': {0: 'no', 1: 'yes'}}}}
[0, 1] , classified as by C4.5: no
[1, 1] , classified as by C4.5: yes
ID3 和 C4.5 兩種決策樹的測試結果都表明，非圓的和紅的水果不是蘋果，圓的和紅的水果是蘋果。
總結
本文首先介紹了ID3和C4.5兩種決策樹的優缺點、信息及信息熵的衡量方式，接著從選擇最優特征、信息增益、信息增益比三方面詳細深入地講解了決策樹的原理。接著用例子介紹ID3和C4.5決策樹的分類過程。然后通過代碼樣例，介紹了自己動手實現ID3和C4.5決策樹的思路。最后，利用蘋果數據展示了如何應用ID3和C4.5決策樹解決實際問題。決策樹具有很強的可解釋性。但是在實際應用中，決策樹往往面臨著過擬合的問題。為了避免過擬合問題就需要考慮剪枝技術。剪枝的過程會將不重要的結點刪除，具體技術請閱讀文末參考資源。ID3.0和C4.5很簡單實用，但是它們也有缺點，那就是不直接支持數值型數據，需要借助連續屬性離散化技術將連續的數值型數據離散化。盡管這個方法可行，但是對于特征劃分多的情況，ID3.0和C4.5仍然存在問題。而CART樹(即分類回歸樹)可以很好地解決這些問題，其中分類樹利用基尼指數來劃分數據集，而回歸樹利用平方誤差最小化準則劃分數據集。關于分類回歸樹的內容會在下一篇中介紹，歡迎讀者繼續關注。
參考資源
本文用到的參考文獻如下：
- 參考李航著《統計學習方法》，了解信息增益、信息增益比、樹剪枝、分類回歸樹的概念。
- 參考Peter Harrington著《機器學習實戰》，了解決策樹代碼框架。
- 參考周志華著《機器學習》，了解連續屬性離散化技術。
轉載于:https://www.cnblogs.com/davidwang456/articles/8927010.html
總結
以上是生活随笔為你收集整理的机器学习系列之手把手教你实现一个决策树的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 机器学习系列之手把手教你实现一个 nai
- 下一篇： 机器学习系列之手把手教你实现一个分类回归