在生活中我們經常會用到決策樹算法，最簡單的就是二叉樹了；相信大家也會又同樣的困擾，手機經常收到各種短信，其中不乏很多垃圾短信、此時只要設置這類短信為垃圾短信手機就會自動進行屏蔽、減少被騷擾的次數，同時正常短信又不會被阻攔。類似這種就是決策樹的工作原理，決策樹的一個重要任務是為了理解數據中所含的信息，可以使用決策樹不熟悉的數據集合，并從中體取一系列規則，這些機器根據數據集創建規則的過程，就是機器學習的過程。

決策樹優缺點：

優點：計算復雜度不高，輸出結果易于理解、即對模型的輸出結果的可解釋性要高；對中間值的缺失不敏感，可以處理不相關數據；

缺點：可能會產生過擬合現象；

決策樹的構建：

輸入：數據集

輸出：構建好的決策樹(訓練集)

def 創建決策樹：

??if(數據集中所有樣本分類一致)：

????創建攜帶類標簽的葉子節點

else：

????尋找劃分數據集最好的特征

????根據最好特征劃分數據集

????for每個劃分的數據集：

????創建決策子樹(遞歸完成)

決策樹的關鍵在于當前數據集上選擇哪個特征屬性作為劃分的條件(能夠將本來無序的數據集最大程度的劃分為有序的子集)，度量最佳分類屬性特征的“最佳性”可用非純度進行衡量；如果一個數據集只有一種分類結果，則該數據集一致性好、能夠提供的信息也最少：只有一種情況；如果數據集有很多分類，則該數據集的一致性不好，能夠提供的信息也較多：至少確定不只一種。組織雜亂數據的一種方法就是使用信息論度量信息，在劃分數據前后信息發生的變化稱為信息增益、這里描述集合信息的度量方式稱為香農熵或者簡稱熵。(該名字來源于克勞德.香農、二十實際最聰明的人之一)。熵定義為信息的期望值，為了計算熵、我們需要計算所有類別的可能值所包含的信息期望。

熵計算公式：

明確決策樹分類選擇特征的依據后，先梳理下決策樹的流程都有哪些：

1、收集數據：一切可以使用的方法、只要不違法；

2、準備數據：樹構造算法只適用于標準型數據，因此數據值必須離散化；

3、分析數據：可以使用任何方法，數據構建完成后，需看下是否達到了我們的預期；

4、訓練算法：構建樹的數據結構；

5、測試算法：使用構建好的樹計算正確率，越高當然越好(也可能過擬合、不能過份高了)；

6、使用算法。

為了后面更好的理解決策樹，利用如下數據我們先套用下公式，直觀的計算一下什么是信息熵、什么是信息增益，以及如何選擇一個特征作為當前數據的劃分條件；以便后面更好的擼代碼。

經典的樣例數據：

Day	天氣	溫度	濕度	風	決定
1	晴	熱	高	弱	N
2	晴	熱	高	強	N
3	陰	熱	高	弱	Y
4	雨	中	高	弱	Y
5	雨	涼	正常	弱	Y
6	雨	涼	正常	強	N
7	陰	涼	正常	強	Y
8	晴	中	高	弱	N
9	晴	涼	正常	弱	Y
10	雨	中	正常	弱	Y
11	晴	中	正常	強	Y
12	陰	中	高	強	Y
13	陰	熱	正常	弱	Y
14	雨	中	高	強	N

根據信息熵的公式，此數據比較簡單、我們可以手工計算一下各個特征的信息增益，從而知道ID3算法具體選擇哪個特征作為分類的依據和算法的一個計算過程。

先列一下公式、參照公式帶入計算，減小手工計算誤差：

計算數據集(D)的經驗熵：

一個特征(A)對數據集(D)的經驗條件熵：

那么相對特征(A)此時的信息增益計算公式為：

以上4個特征中：天氣(晴、陰雨)/溫度(熱、適中、涼)/濕度(高、正常)/風(強弱)，推算過程中我們選擇濕度或風、這兩個特征值分布均只含兩個值，計算過程的時候相對要簡單一點。

第一步：計算該數據集的經驗熵，該數據集共有14條數據：9條決定為Y、5條決定為N；則p(Y)=9/14、p(N)=5/14。此時代入公式：

第二步：選擇風這個特征計算該特征相對數據集的經驗熵，從數據可以看出風共有兩個值：強和弱。

其中為強風的數據分布如下、共有6條數據，其中決定為Y和N的分別是3條，此時p(Y)=3/6、p(N)=3/6。

Day	天氣	溫度	濕度	風	決定
2	晴	熱	高	強	N
6	雨	涼	正常	強	N
7	陰	涼	正常	強	Y
11	晴	中	正常	強	Y
12	陰	中	高	強	Y
14	雨	中	高	強	N

代入公式：

其中為若風的數據分布如下、共有8條數據，其中決定為Y有6條、N有2條，此時p(Y)=6/8、p(N)=2/8。

Day	天氣	溫度	濕度	風	決定
1	晴	熱	高	弱	N
3	陰	熱	高	弱	Y
4	雨	中	高	弱	Y
5	雨	涼	正常	弱	Y
8	晴	中	高	弱	N
9	晴	涼	正常	弱	Y
10	雨	中	正常	弱	Y
13	陰	熱	正常	弱	Y

代入公式：

風這個特征的經驗熵計算就完成了，強風和弱風在整個數據集中的占比分別為：

p(強)=6/14、p(弱)=8/14；代入公式則風這個特征的條件熵為：

風這個特征的信息增益為：

以此類推：

從中可以看出天氣的新增增益為0.246、高于其他三個特征的增益，這也是為什么天氣作為第一個分類依據的特征、在樹的根節點上。

參照《機器學習實踐》構建一顆決策樹、python代碼如下：

from math import logimport?operatordef calcShannonEnt(dataSet): # 計算數據的熵(entropy) numEntries = len(dataSet) # 數據條數 labelCounts = {} for featVec in dataSet: currentLabel = featVec[-1] # 每行數據的最后一個字(類別) if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 # 統計有多少個類以及每個類的數量 shannonEnt = 0 for key in labelCounts: prob = float(labelCounts[key]) / numEntries # 計算單個類的熵值 shannonEnt -= prob * log(prob, 2) # 累加每個類的熵值????return?shannonEntdef createDataSet1(): # 創造示例數據 dataSet = [['黑', '是', '男'], ['白', '否', '男'], ['黑', '是', '男'], ['白', '否', '女'], ['黑', '是', '女'], ['黑', '否', '女'], ['白', '否', '女'], ['白', '否', '女']] labels = ['a', 'b'] return dataSet, labels#待劃分的數據集、劃分數據集的特征、需要返回的特征值def splitDataSet(dataSet, axis,value): # 按某個特征分類后的數據，例如value = 長，axis為頭發axis = 0 retDataSet = [] # retDataSet返回的是數據中，所有頭發為長的記錄 for featVec in dataSet: if featVec[axis] == value: # 每次會將這個feature刪除掉 reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis + 1:]) retDataSet.append(reducedFeatVec) return retDataSetdef chooseBestFeatureToSplit(dataSet): # 選擇最優的分類特征 numFeatures = len(dataSet[0]) - 1 baseEntropy = calcShannonEnt(dataSet) # 原始的熵 bestInfoGain = 0 bestFeature = -1 # (1)遍歷每個特征 for i in range(numFeatures): featList = [example[i] for example in dataSet] uniqueVals = set(featList) newEntropy = 0 # (2)對單個特征中每個唯一值都進行子樹的切分，然后計算這個的信息增益，然后累加每個分裂條件的信息增益，為newEntropy for value in uniqueVals: subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet) / float(len(dataSet)) newEntropy += prob * calcShannonEnt(subDataSet) # 按特征分類后的熵 infoGain = baseEntropy - newEntropy # 原始熵與按特征分類后的熵的差值 if (infoGain > bestInfoGain): # 若按某特征劃分后，熵值減少的最大，則次特征為最優分類特征 bestInfoGain = infoGain bestFeature = i????return?bestFeaturedef majorityCnt(classList): #按分類后類別數量排序，比如：最后分類為2男1女，則判定為男； classCount = {} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]# 決策樹核心邏輯：遞歸，深度優先遍歷創建子樹def createTree(dataSet, labels): #print(dataSet) classList = [example[-1] for example in dataSet] # 類別：男或女 if classList.count(classList[0]) == len(classList): return classList[0] if len(dataSet[0]) == 1: # 當只剩最優一個feature時，因為每次分裂會刪除一個特征 return majorityCnt(classList) # (1) 選擇最優分裂特征 bestFeat = chooseBestFeatureToSplit(dataSet) #選擇最優特征 bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel: {}} #分類結果以字典形式保存 del (labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) # (2) 遍歷分裂特征的每個唯一值，分裂產生子樹 for value in uniqueVals: # 將每個label都往子樹傳遞，labels一直可能會被選用 subLabels = labels[:] # 對基于best feature這個feature內每個唯一值切分為不同的子樹，然后返回子樹的結果。每個子樹切分能多個分支 # 遞歸調用，每層的切分為每個特征的唯一值 # (3) 對最佳分裂特征的每個值，分別創建子樹 myTree[bestFeatLabel][value] = createTree( splitDataSet(dataSet, bestFeat, value), subLabels) return myTreeif __name__ == '__main__': dataSet, labels = createDataSet1() # 創造示列數據 print(createTree(dataSet, labels)) # 輸出決策樹模型結果為了更直觀展示決策樹及各節點的信息熵，用sklearn工具基于鳶尾花數據集展示一顆完整的決策樹結構。from sklearn.datasets import load_irisfrom sklearn import treeimport osimport pydot # need installprint(os.getcwd())clf = tree.DecisionTreeClassifier(criterion="entropy", max_features="log2",max_depth = 10) #giniiris = load_iris()clf = clf.fit(iris.data, iris.target)tree.export_graphviz(clf, out_file='tree.dot')(graph, ) = pydot.graph_from_dot_file('tree.dot')graph.write_png('tree.png')

對應的決策樹結構如下：

ID3是基于信息增益作為分類依據的監督學習算法，它有一個明顯的缺點是該算法會傾向選擇有較多屬性值的特征作為分類依據，鑒于ID3算法缺點后面又衍生出來C4.5和CART算法、具體后面再詳細介紹和分享總結。

總結

以上是生活随笔為你收集整理的python机器学习算法.mobi_机器学习之ID3算法详解及python代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。