python決策樹id3算法_機器學習(2) 決策樹python實作（ID3算法）

本文基于李航老師的《統計學習方法》，和Peter Harrington的《機器學習實戰》

決策樹可以說是對KNN的線性搜尋方法的一個改進(其實KNN算法有一個改進的kd tree算法。也是借用了樹的這種資料結構來加快搜尋效率)。

決策權的理論基礎可以參見李航老師的《統計學習方法》第四章的内容。說一下比較重要的點:1.特征選擇 2.樹的建立 3.樹的修剪(由于ID3算法比較古老并沒有涉及到樹的修剪，後來的學習筆記CART和C4.5會涉及到樹的修剪)

1.特征選擇

選取合适的特征作為(根)樹節點。這裡涉及到資訊論裡面的資訊熵和條件資訊熵的概念。我對資訊熵的了解就是資訊的混亂程度，是以如果資訊熵(記為H(D))越大，說明還資訊的内容越混亂，資訊的不确定性就越高。條件資訊熵(記作H(D|A))和條件機率的意思差不多，含義為在某一資訊特征A确定的情況下資料集D資訊熵。那麼資訊增益g(D,A)定義為：g(D,A)=H(D)-H(D|A)。那麼資訊增益表示啥意思呢？其實從定義可以看出，資訊增益表示為由于特征A使得資料集D的分類的不确定性的減少程度。顯然資訊增益的大小是依賴與特征的，一般資訊增益越大，表示該特征的分類效果就越好。

注：資訊熵公式

條件熵

(ai 為特征A的所有取值)

資訊增益：g(D,A)=H(D)-H(D|A)

2.樹的建立

樹的承載方式有很多種，可以建構結點類來添加和删除結點。這裡面使用python裡面的字典來建構和存儲樹結構。具體的方法見後面的代碼分析。

3.樹的修剪

一般按照資訊增益建構成的樹，對于訓練集的表示效果非常好。但是對于測試集的表現确很差。這種情況出現的原因是因為在樹的訓練過程中出現了過拟合現象。是以算法需要對樹的樹枝進行修剪。來減輕過拟合的影響(ID3算法沒有涉及到樹枝的修剪)

——————————————————代碼段分析————————————

首先post出資料集的格式：【特征1，特征2，……，類型】(特征表述用0，1，2等标量來表示)

calcShannonEnt函數是用來計算資訊熵的：注意這是對類别進行計算資訊熵，不是對特征

def calcShannonEnt(dataset): # 計算資訊熵

num_of_Entries = 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.keys():

prob = labelCounts[key] / num_of_Entries

shannonEnt -= prob * log2(prob)

return shannonEnt

splitDataSet函數是用來劃分資料的：為什麼要劃分？這是為了我們計算條件資訊熵。想想條件資訊熵的定義【在某一特征确定的情況下，計算資料集的分類的資訊熵】

是以在進行條件資訊熵計算時，對于某一個特征A，其所有的取值(a1,a2,a3……)都要被劃分為在自己特征取值已經确定情況下(例如A=a1)的子集。

def splitDataSet(dataset, axis, value): # 根據特征劃分資料axis表示特征， value表示特征的取值

subDataSet = []

for featVec in dataset:

if featVec[axis] == value:

reduce_featVec = featVec[0:axis]

reduce_featVec.extend(featVec[axis+1:])

subDataSet.append(reduce_featVec)

return subDataSet

chooseBestFeatureToSplit函數是用來劃分資料集的。函數傳回最佳的劃分特征

def chooseBestFeatureToSplit(dataset): #選取最佳的特征來劃分資料

num_of_feature = len(dataset[0])-1

baseEntropy = calcShannonEnt(dataset) # 計算資料集D的分類資訊熵

best_info_gain = 0.0

bestLabel_index = -1

for i in range(num_of_feature):

feature_vec = [each[i] for each in dataset]

uniqueVals = set(feature_vec) #確定特征取值的唯一性

newEntroy = 0.0

for value in uniqueVals: #開始計算特征确定情況下的條件資訊熵

subdataset = splitDataSet(dataset, i, value)

prob = len(subdataset) / float(len(dataset))

newEntroy += prob * calcShannonEnt(subdataset)

info_gain = baseEntropy - newEntroy #資訊增益

if info_gain > best_info_gain:

best_info_gain = info_gain

bestLabel_index = i

return bestLabel_index #最後傳回最佳特征

majorityVote函數是起多數表決的作用的。如果一個樹分類到最後一個子節點的時候，但是這個時候子節點中的資料類别還不是全部一樣的，這個時候就要用多數表決方法來強制分類。

#多數表決函數

def majorityVote(classlist):

classcount = {}

for each in classlist:

if each not in classcount.keys():

classcount[each] = 0

classcount[each] += 1

sorted_classcount = sorted(classcount.items(), key=operator.itemgetter(1), reverse=True) #按字典中value進行排序，逆序排列

return sorted_classcount[0][0] #輸出“得票”最多得分類

creatTree函數用來建立樹狀結構。這個函數需要被自己遞歸調用，是以很友善就會完成樹得建造。(遞歸得使用一定要注意設定遞歸的終止條件，不然會陷入無限遞歸【血淚得教訓

：(】)

def creatTree(dataset, label): # 建立樹

t_label = label[:] # 注意！ 傳進來得label是個全局量，是以最好不要對它進行直接修改。一般拷貝它得一個副本

classlist = [each[-1] for each in dataset]

# 設定樹的終止條件(有兩個。其一是當類集合中都是同一種類的時候，其二是當劃分到葉節點時，類的集合中的種類不全是相同的，這時要強制性的進行暴力分類)

if classlist.count(classlist[0]) == len(classlist):

return classlist[0]

if len(dataset) == 1:

return majorityVote(classlist)

best_feature_index = chooseBestFeatureToSplit(dataset)

best_feature = t_label[best_feature_index]

myTree = {best_feature: {}} #樹的基本架構

del(t_label[best_feature_index])

feature_vec = [each[best_feature_index] for each in dataset]

uniqueValues = set(feature_vec)

for value in uniqueValues:

sublabel = t_label[:]

myTree[best_feature][value] = creatTree(splitDataSet(dataset, best_feature_index, value), sublabel) #遞歸的調用createTree來建立樹

return myTree

classify函數起到分類作用。

def classify(mytree, feat_label, testvec): #測試、分類函數

firstStr = list(mytree.keys())[0]

secondDict = mytree[firstStr]

feat_index = feat_label.index(firstStr) #用index來尋找特定的label的值

for key in secondDict.keys():

if testvec[feat_index] == key:

if isinstance(secondDict[key], dict):

classLabel = classify(secondDict[key], feat_label, testvec) #遞歸調用來判别檢索分類

else:

classLabel = secondDict[key]

return classLabel

storeTree函數和loadTree函數起存儲和調用得作用[這兩個函數出現是為了效率的提高。因為樹的建立是一個緩慢的過程，即便我們這邊隻用了六組資料都需要運作幾秒鐘，是以為了避免每次運作時都要重複的進行樹的建立。我們用pickle子產品函數來對樹進行腌制( pickle的翻譯就是腌制的意思)]

def storeTree(mytree, filename):#“腌制”樹

fw = open(filename, 'wb') #注意，這裡面要用二進制進行寫入

pickle.dump(mytree, fw)

fw.close() #檔案打開别忘了關閉

def loadTree(filename):#“取出樹”

fr = open(filename, 'rb') #二進制寫入就要二進制讀取

return pickle.load(fr)

————————————————完整代碼post——————————————

from math import log2

import operator

import pickle

def creatDataset(): # 資料集的形成

dataset = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

labels = ['no surfacing', 'flippers']

return dataset, labels

def calcShannonEnt(dataset): # 計算資訊熵

num_of_Entries = 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.keys():

prob = labelCounts[key] / num_of_Entries

shannonEnt -= prob * log2(prob)

return shannonEnt

def splitDataSet(dataset, axis, value): # 根據特征劃分資料axis表示特征， value表示特征的取值

subDataSet = []

for featVec in dataset:

if featVec[axis] == value:

reduce_featVec = featVec[0:axis]

reduce_featVec.extend(featVec[axis+1:])

subDataSet.append(reduce_featVec)

return subDataSet

# 選擇最佳的劃分資料集的特征(ID3的資訊增益法)(C4.5)

def chooseBestFeatureToSplit(dataset):

num_of_feature = len(dataset[0])-1

baseEntropy = calcShannonEnt(dataset)

best_info_gain = 0.0

bestLabel_index = -1

for i in range(num_of_feature):

feature_vec = [each[i] for each in dataset]

uniqueVals = set(feature_vec)

newEntroy = 0.0

for value in uniqueVals:

subdataset = splitDataSet(dataset, i, value)

prob = len(subdataset) / float(len(dataset))

newEntroy += prob * calcShannonEnt(subdataset)

info_gain = baseEntropy - newEntroy

if info_gain > best_info_gain:

best_info_gain = info_gain

bestLabel_index = i

return bestLabel_index

#多數表決函數

def majorityVote(classlist):

classcount = {}

for each in classlist:

if each not in classcount.keys():

classcount[each] = 0

classcount[each] += 1

sorted_classcount = sorted(classcount.items(), key=operator.itemgetter(1), reverse=True)

return sorted_classcount[0][0]

#樹的建立

def creatTree(dataset, label):

t_label = label[:]

classlist = [each[-1] for each in dataset]

# 設定樹的終止條件

if classlist.count(classlist[0]) == len(classlist):

return classlist[0]

if len(dataset) == 1:

return majorityVote(classlist)

best_feature_index = chooseBestFeatureToSplit(dataset)

best_feature = t_label[best_feature_index]

myTree = {best_feature: {}}

del(t_label[best_feature_index])

feature_vec = [each[best_feature_index] for each in dataset]

uniqueValues = set(feature_vec)

for value in uniqueValues:

sublabel = t_label[:]

myTree[best_feature][value] = creatTree(splitDataSet(dataset, best_feature_index, value), sublabel) #遞歸調用createTree來建立樹

return myTree

#判别函數

def classify(mytree, feat_label, testvec):

firstStr = list(mytree.keys())[0]

secondDict = mytree[firstStr]

feat_index = feat_label.index(firstStr)

for key in secondDict.keys():

if testvec[feat_index] == key:

if isinstance(secondDict[key], dict):

classLabel = classify(secondDict[key], feat_label, testvec)

else:

classLabel = secondDict[key]

return classLabel #這塊可能會存在隐藏的bug[系統提示，實際中操作還沒遇到]

#腌制樹

def storeTree(mytree, filename):

fw = open(filename, 'wb')

pickle.dump(mytree, fw)

fw.close()

#取出樹

def loadTree(filename):

fr = open(filename, 'rb')

return pickle.load(fr)

if __name__ == "__main__":

filepath = 'D:/pycharm/PyCharm Community Edition 2018.2.4/Practice/decision tree/storaged_Tree'

#注意我是已經腌制好樹了。如果想要在自己的編譯器上可以使用。需要先調用storeTree函數，後來再通過filepath來調用loadTree函數來引用建立的樹！！！

dataSet, Labels = creatDataset()

Tree = loadTree(filepath)

re = classify(Tree, Labels, [1, 1])

print(re)

#文本的儲存一般不會用到pickle。具體pickle的用法可以參考pickle的手冊