概述

上一篇講述了《機器學習 | 算法筆記(三)- 支持向量機算法以及代碼實現》，本篇講述機器學習算法決策樹，內容包括模型介紹及代碼實現。

決策樹

決策樹(Decision Tree)在機器學習中也是比較常見的一種算法，屬于監督學習中的一種。看字面意思應該也比較容易理解，相比其他算法比如支持向量機(SVM)或神經網絡，似乎決策樹感覺“親切”許多。

優點：計算復雜度不高，輸出結果易于理解，對中間值的缺失值不敏感，可以處理不相關特征數據。

缺點：可能會產生過度匹配的問題。

使用數據類型：數值型和標稱型。

劃分數據集的大原則是：將無序的數據變得更加有序。

我們可以使用多種方法劃分數據集，但是每種方法都有各自的優缺點。于是我們這么想，如果我們能測量數據的復雜度，對比按不同特征分類后的數據復雜度，若按某一特征分類后復雜度減少的更多，那么這個特征即為最佳分類特征。

下面，我們就對以下表格中的西瓜樣本構建決策樹模型。

Claude Shannon 定義了熵(entropy)和信息增益(information gain)。

用熵來表示信息的復雜度，熵越大，則信息越復雜。

信息熵(information entropy)

樣本集合D中第k類樣本所占的比例(k=1,2,...,|Y|)，|Y|為樣本分類的個數，則D的信息熵為：

Ent(D)的值越小，則D的純度越高。直觀理解一下：假設樣本集合有2個分類，每類樣本的比例為1/2，Ent(D)=1；只有一個分類，Ent(D)= 0，顯然后者比前者的純度高。

在西瓜樣本集中，共有17個樣本，其中正樣本8個，負樣本9個，樣本集的信息熵為：

信息增益(information gain)

使用屬性a對樣本集D進行劃分所獲得的“信息增益”的計算方法是，用樣本集的總信息熵減去屬性a的每個分支的信息熵與權重(該分支的樣本數除以總樣本數)的乘積，通常，信息增益越大，意味著用屬性a進行劃分所獲得的“純度提升”越大。因此，優先選擇信息增益最大的屬性來劃分。

同理也可以計算出其他幾個屬性的信息增益，選擇信息增益最大的屬性作為根節點來進行劃分，然后再對每個分支做進一步劃分。

用python構造決策樹基本流程

決策樹學習基本算法

ID3算法與決策樹的流程

(1)數據準備：需要對數值型數據進行離散化

(2)ID3算法構建決策樹：

• 如果數據集類別完全相同，則停止劃分
• 否則，繼續劃分決策樹：
  計算信息熵和信息增益來選擇最好的數據集劃分方法；劃分數據集創建分支節點：對每個分支進行判定是否類別相同，如果相同停止劃分，不同按照上述方法進行劃分。

通常一棵決策樹包含一個根節點、若干個分支節點和若干個葉子節點，葉子節點對應決策結果(如好瓜或壞瓜)，根節點和分支節點對應一個屬性測試(如色澤=？)，每個結點包含的樣本集合根據屬性測試的結果劃分到子節點中。

我們對整個訓練集選擇的最優劃分屬性就是根節點，第一次劃分后，數據被向下傳遞到樹分支的下一個節點，再這個節點我們可以再次劃分數據，構建決策樹是一個遞歸的過程，而遞歸結束的條件是：所有屬性都被遍歷完，或者每個分支下的所有樣本都屬于同一類。

還有一種情況就是當劃分到一個節點，該節點對應的屬性取值都相同，而樣本的類別卻不同，這時就把當前節點標記為葉節點，并將其類別設為所含樣本較多的類別。例如：當劃分到某一分支時，節點中有3個樣本，其最優劃分屬性為色澤，而色澤的取值只有一個“淺白”，3個樣本中有2個好瓜，這時我們就把這個節點標記為葉節點“好瓜”。

代碼實現

數據集：https://download.csdn.net/download/li1873997/12671852

trees.py

from math import logimport operator # 此行加在文件頂部# 通過排序返回出現次數最多的類別def majorityCnt(classList): classCount = {} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]# 遞歸構建決策樹def createTree(dataSet, labels): classList = [example[-1] for example in dataSet] # 類別向量 if classList.count(classList[0]) == len(classList): # 如果只有一個類別，返回 return classList[0] if len(dataSet[0]) == 1: # 如果所有特征都被遍歷完了，返回出現次數最多的類別 return majorityCnt(classList) bestFeat = chooseBestFeatureToSplit(dataSet) # 最優劃分屬性的索引 bestFeatLabel = labels[bestFeat] # 最優劃分屬性的標簽 myTree = {bestFeatLabel: {}} del (labels[bestFeat]) # 已經選擇的特征不再參與分類 featValues = [example[bestFeat] for example in dataSet] uniqueValue = set(featValues) # 該屬性所有可能取值，也就是節點的分支 for value in uniqueValue: # 對每個分支，遞歸構建樹 subLabels = labels[:] myTree[bestFeatLabel][value] = createTree( splitDataSet(dataSet, bestFeat, value), subLabels) return myTree# 計算信息熵def calcShannonEnt(dataSet): 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.0 for key in labelCounts: # 計算信息熵 prob = float(labelCounts[key]) / numEntries shannonEnt = shannonEnt - prob * log(prob, 2) return shannonEnt# 劃分數據集，axis:按第幾個屬性劃分，value:要返回的子集對應的屬性值def splitDataSet(dataSet, axis, value): retDataSet = [] featVec = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis + 1:]) retDataSet.append(reducedFeatVec) return retDataSet# 選擇最好的數據集劃分方式def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 # 屬性的個數 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0 bestFeature = -1 for i in range(numFeatures): # 對每個屬性技術信息增益 featList = [example[i] for example in dataSet] uniqueVals = set(featList) # 該屬性的取值集合 newEntropy = 0.0 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 bestFeature# 計算信息熵def calcShannonEnt(dataSet): 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.0 for key in labelCounts: # 計算信息熵 prob = float(labelCounts[key]) / numEntries shannonEnt = shannonEnt - prob * log(prob, 2) return shannonEnt# 劃分數據集，axis:按第幾個屬性劃分，value:要返回的子集對應的屬性值def splitDataSet(dataSet, axis, value): retDataSet = [] featVec = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis + 1:]) retDataSet.append(reducedFeatVec) return retDataSet# 選擇最好的數據集劃分方式def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 # 屬性的個數 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0 bestFeature = -1 for i in range(numFeatures): # 對每個屬性技術信息增益 featList = [example[i] for example in dataSet] uniqueVals = set(featList) # 該屬性的取值集合 newEntropy = 0.0 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 bestFeature

下面使用西瓜樣本集，測試一下算法，創建一個WaterMalonTree.py文件。因為生成的樹是中文表示的，因此使用json.dumps()方法來打印結果。如果是不含中文，直接print即可。

# -*- coding: cp936 -*-import treesimport json fr = open(r'C:Python27pyDecisionTreewatermalon.txt') listWm = [inst.strip().split('') for inst in fr.readlines()]labels = ['色澤', '根蒂', '敲聲', '紋理', '臍部', '觸感']Trees = trees.createTree(listWm, labels) print json.dumps(Trees, encoding="cp936", ensure_ascii=False)

運行該文件，打印出西瓜的決策樹，它是一個字典：

{"紋理": {"模糊": "否", "清晰": {"根蒂": {"稍蜷": {"色澤": {"烏黑": {"觸感": {"軟粘": "否", "硬滑": "是"}}, "青綠": "是"}}, "蜷縮": "是", "硬挺": "否"}}, "稍糊": {"觸感": {"軟粘": "是", "硬滑": "否"}}}}

總結

決策樹是一種基于樹結構來進行決策的分類算法，我們希望從給定的訓練數據集學得一個模型(即決策樹)，用該模型對新樣本分類。決策樹可以非常直觀展現分類的過程和結果，一旦模型構建成功，對新樣本的分類效率也相當高。

最經典的決策樹算法有ID3、C4.5、CART，其中ID3算法是最早被提出的，它可以處理離散屬性樣本的分類，C4.5和CART算法則可以處理更加復雜的分類問題，本文重點介紹ID3算法。下一篇介紹通過《 數據可視化-Python實現Matplotlib繪制決策樹》。

總結

以上是生活随笔為你收集整理的python决策树 value_机器学习 | 算法笔记（四）- 决策树算法以及代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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