python學智能算法（八）|決策樹

【1】引言

前序學習進程中，已經對KNN鄰近算法有了探索，相關文章鏈接為：

python學智能算法（七）|KNN鄰近算法-CSDN博客

但KNN鄰近算法有一個特點是：它在分類的時候，不能知曉每個類別內事物的具體面貌，只能獲得類別，停留在事物的表面。

為了進一步探索事物的內在特征，就需要學習新的算法。

本篇文章就是在KNN的基礎上學習新算法：決策樹。

【2】原理分析

在學習決策樹執之前，需要先了解香農熵。

本科學控制課，老師講到香農熵，那時候啥也不懂，以為就是個普通公式，多年以后，看到這三個字難免感慨當年太過幼稚。

【2.1】香農熵

香農熵比較簡單，從數學層面上看就是對數求和。

這是香農熵的求解代碼：

import numpy as np
from math import log #引入log()函數求對數# 定義一個嵌套列表
def creatDataset():# dataset是一個嵌套列表dataset=[[1,1,'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no']]# lables也是一個列表labels=['no surfacing','flippers']return dataset,labels# calcShannonEnt是具體的香農熵求解函數
def calcShannonEnt(dataset):# numEntries獲得了dataset列表的行數numEntries=len(dataset)# labelcounts是一個空的字典labelcounts={}# for函數的意義是，對于dataset里面的每一行都會執行循環操作for feature in dataset:# currentlabel 取到了feature的最后一個元素currentlabel=feature[-1]# 由于labelcounts是一個空字典，labelcounts.keys()在第一次運行的時候不會指向任何標簽，所以會被直接添加# currentlabel是每一行dataset的最后一列，也就是最后一個元素# if函數實際上進行了同類項合并工作if currentlabel not in labelcounts.keys():# 給以currentlabel為標簽的項目賦值0labelcounts[currentlabel]=0# 只要currentlabel和labelcounts.keys()存儲的元素一致，就給以currentlabel為標簽的項目賦值加1labelcounts[currentlabel]+=1# 定義香農熵的初始值=0ShannonEnt=0.0# 由于labelcounts是字典，所以可以用key訪問字典的項目for key in labelcounts:# 計算值為浮點數# 用key指向的項目對應的數量比上總數prob=float(labelcounts[key])/numEntries# 香農熵就是頻數乘以以2為底的頻數的對數，然后還要取負值# 取負值是因為，頻數小于1，所以對數小于0，一旦取負值就獲得了正數ShannonEnt-=prob*log(prob,2)return ShannonEnt
dataset,labels=creatDataset()
ShannonEnt=calcShannonEnt(dataset)
print('ShannonEnt=',ShannonEnt)

整體代碼非常簡單，總結起來就是一個公式：

代碼中需要注意的是：dataset是一個嵌套列表，labelcounts是一個字典。

【2.2】數據集劃分

數據集劃分，目的是找出某些關鍵特征后，將其刪除。

# 定義一個嵌套列表
def creatDataset():# dataset是一個嵌套列表dataset=[[1,1,'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no']]# lables也是一個列表labels=['no surfacing','flippers']return dataset,labels# splitdataset把一些列因素直接刪除后輸出
def splitdataset(dataset, axis, value):# 創建一個新的列表retdataset = []# 對于dataset的每一行for featvec in dataset:# if第axis列的數據剛好和value相等if featvec[axis] == value:# reducedfeature先獲取索引從第0個到axis-1的元素，一共axis個reducedfeatvec = featvec[:axis]# reducedfeature繼續獲取索引從第axis+1開始的所有元素# reducedfeature后面再獲取從第axis+2個開始一直到最后一個元素reducedfeatvec.extend(featvec[axis + 1:])# retdataset存儲了reducedfeature# retdataset中剛好沒有位置索引為axis的元素# retdataset中剛好沒有第axis+1個元素retdataset.append(reducedfeatvec)return retdatasetdataset, labels = creatDataset()
retdataset = splitdataset(dataset, 0,1)
retdataset1 = splitdataset(dataset, 1,1)
retdataset2 = splitdataset(dataset, 1,0)
print("retdataset:", retdataset)
print("retdataset1:", retdataset1)
print("retdataset2:", retdataset2)

數據集劃分只用了一個for循環加if判斷就能實現，劃分的原理是：對于每一行元素，如果指定列的元素和指定數據相等，就把這個相等的元素挑出去，然后把這行數據剩下的部分添加到一個新的列表里；如果指定列的元素和指定數據不相等，這一行數據會直接略過。

上述代碼運行的效果是：

retdataset: [[1, 'yes'], [1, 'yes'], [0, 'no']]
retdataset1: [[1, 'yes'], [1, 'yes'], [0, 'no'], [0, 'no']]
retdataset2: [[1, 'no']]

【2.3】特征選擇

數據集劃分后，序言按照制定的特征作為依據，判斷這個特征指向的樣本對應的香農熵。

要想理解特征選擇的意義，需要把前面的香農熵計算和數據集劃分子函數都一起寫進來：

from math import log  # 引入log()函數求對數def creatDataset():# dataset是一個嵌套列表dataset=[[1,1,'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no']]# lables也是一個列表labels=['no surfacing','flippers']return dataset,labels# calcShannonEnt是具體的香農熵求解函數
# 實際上calcShannonEnt是dataset最后一列的香農熵
def calcShannonEnt(dataset):# numEntries獲得了dataset列表的行數numEntries = len(dataset)# labelcounts是一個空的字典labelcounts = {}# for函數的意義是，對于dataset里面的每一行都會執行循環操作for feature in dataset:# currentlabel 取到了feature的最后一個元素currentlabel = feature[-1]# 由于labelcounts是一個空字典，labelcounts.keys()在第一次運行的時候不會指向任何標簽，所以會被直接添加# currentlabel是每一行dataset的最后一列，也就是最后一個元素# if函數實際上進行了同類項合并工作if currentlabel not in labelcounts.keys():# 給以currentlabel為標簽的項目賦值0labelcounts[currentlabel] = 0# 只要currentlabel和labelcounts.keys()存儲的元素一致，就給以currentlabel為標簽的項目賦值加1labelcounts[currentlabel] += 1# 定義香農熵的初始值=0ShannonEnt = 0.0# 由于labelcounts是字典，所以可以用key訪問字典的項目for key in labelcounts:# 計算值為浮點數# 用key指向的項目對應的數量比上總數prob = float(labelcounts[key]) / numEntries# 香農熵就是頻數乘以以2為底的頻數的對數，然后還要取負值# 取負值是因為，頻數小于1，所以對數小于0，一旦取負值就獲得了正數ShannonEnt -= prob * log(prob, 2)return ShannonEnt# splitdataset把一些列因素直接刪除后輸出
def splitdataset(dataset, axis, value):# 創建一個新的列表retdataset = []# 對于dataset的每一行for featvec in dataset:# if第axis列的數據剛好和value相等if featvec[axis] == value:# reducedfeature先獲取索引從第0個到axis-1的元素，一共axis個reducedfeatvec = featvec[:axis]# reducedfeature繼續獲取索引從第axis+1開始的所有元素# reducedfeature后面再獲取從第axis+2個開始一直到最后一個元素reducedfeatvec.extend(featvec[axis + 1:])# retdataset存儲了reducedfeature# retdataset中剛好沒有位置索引為axis的元素# retdataset中剛好沒有第axis+1個元素retdataset.append(reducedfeatvec)return retdataset# choosebestfeaturetosplit計算的香農熵對象元素是dataset最后一列對應的元素
def choosebestfeaturetosplit(dataset):# 對dataset第0行求長度，獲得列數，然后再減去1numfeatures = len(dataset[0]) - 1# 調用函數calcShannonEnt獲得dataset的香農熵baseentroy = calcShannonEnt(dataset)# 定義一個常數bestinfogain = 0.0# 定義一個常數bestfeature = -1# 對于numfeatures中的每一個數# numfeatures比dataset的列數少一個for i in range(numfeatures):# 對于每一行在dataset中的元素，按照列位置索引為i的形式提取# 每一行位置索引為i的元素賦值給featlist# 這個嵌套列表，因為for的存在，把dataset每一行和位置索引為i的元素賦值給featlist# featlist存儲的元素數量和dataset的函數一致# featlist作為列表沒有提前預定義，此處定義這個量和定義如何取值一起出現featlist = [example[i] for example in dataset]# set是一個內置函數，將featlist這個列表轉化為集合# 集合具有合并同類項的作用，重復的元素只會保留一個uniquevals = set(featlist)# 定義一個常數newentropy = 0.0# 對于uniquevals中的每一個值# uniquevals執行過程中，相當于把整個dataset計算獲得的uniquevals進行遍歷# value是uniquevals中的具體元素，也是列位置索引為i的dataset取到的值for value in uniquevals:# 調用splitdataset對dataset進行子集劃分# 子集劃分的列數和獲得uniquevals的列數一致，value是uniquevals的存儲值# subdataset不會是空值subdataset = splitdataset(dataset, i, value)# 獲取每一個元素的香農熵# 需要注意的是，在每一個i的取值范圍內，都會執行subdataset操作# subdataset是按照列元素進行的集合劃分# 這個prob實際上是針對列元素展開的，有多少列，就會有多少次prob計算# prob實際上代表的是subdataset行數和dataset行數的比例prob = len(subdataset) / float(len(dataset))# 更新香農熵# calcShannonEnt(subdataset)計算了subdataset的最后一列的香農熵# newtropy是prob這個比例和對應香農熵的乘積newentropy += prob * calcShannonEnt(subdataset)# 獲得香農熵的變化量# baseentroy是dataset的香農熵# newtropy是第i列元素為特征進行集合劃分之后，對新集合開展的香農熵計算和新集合數量比例的乘積infogain = baseentroy - newentropy# 如果變化量超過閾值if (infogain > bestinfogain):# 新變化=變化量bestinfogain = infogain# 給bestfeature賦值ibestfeature = ireturn bestfeaturedataset, labels = creatDataset()
ShannonEnt=calcShannonEnt(dataset)
print('ShannonEnt=',ShannonEnt)
bestfeature=choosebestfeaturetosplit(dataset)
print('bestfeature=',bestfeature)

但在前面理解的基礎上，可以先記住兩條原則：

香農熵是以一行數據列表的最后一列為計算依據，開展的對數運算；
數據計劃分時，會把特征這個依據從一行數據列表中刪除。

而為了理解特征選擇子函數choosebestfeaturetosplit(dataset)，需要把這個函數分作三部分。

【2.3.1】準備部分

    # 對dataset第0行求長度，獲得列數，然后再減去1numfeatures = len(dataset[0]) - 1# 調用函數calcShannonEnt獲得dataset的香農熵baseentroy = calcShannonEnt(dataset)# 定義一個常數bestinfogain = 0.0# 定義一個常數bestfeature = -1

準備部分獲得一些備用值：

numfeatures = len(dataset[0]) - 1，對應的是dataset列表的列數-1；

baseentroy = calcShannonEnt(dataset)，是對dataset計算香農熵；

bestinfogain = 0.0和bestfeature = -1都是直接賦值。

【2.3.2】特征值提取

# 對于numfeatures中的每一個數# numfeatures比dataset的列數少一個for i in range(numfeatures):# 對于每一行在dataset中的元素，按照列位置索引為i的形式提取# 每一行位置索引為i的元素賦值給featlist# 這個嵌套列表，因為for的存在，把dataset每一行和位置索引為i的元素賦值給featlist# featlist存儲的元素數量和dataset的函數一致# featlist作為列表沒有提前預定義，此處定義這個量和定義如何取值一起出現featlist = [example[i] for example in dataset]# set是一個內置函數，將featlist這個列表轉化為集合# 集合具有合并同類項的作用，重復的元素只會保留一個uniquevals = set(featlist)# 定義一個常數newentropy = 0.0# 對于uniquevals中的每一個值# uniquevals執行過程中，相當于把整個dataset計算獲得的uniquevals進行遍歷# value是uniquevals中的具體元素，也是列位置索引為i的dataset取到的值

在特征值提取部分，featlist通過嵌套for循環來提取了特征，然后通過set函數做了合并同類型操作。

featlist本質上是對dataset的列數據進行了提取，然后再合并同類項。

注意newtropy在每列特征值獲得后，初始值都是0.0。

【2.3.3】特征值香農熵

        for value in uniquevals:# 調用splitdataset對dataset進行子集劃分# 子集劃分的列數和獲得uniquevals的列數一致，value是uniquevals的存儲值# subdataset不會是空值subdataset = splitdataset(dataset, i, value)# 獲取每一個元素的香農熵# 需要注意的是，在每一個i的取值范圍內，都會執行subdataset操作# subdataset是按照列元素進行的集合劃分# 這個prob實際上是針對列元素展開的，有多少列，就會有多少次prob計算# prob實際上代表的是subdataset行數和dataset行數的比例prob = len(subdataset) / float(len(dataset))# 更新香農熵# calcShannonEnt(subdataset)計算了subdataset的最后一列的香農熵# newtropy是prob這個比例和對應香農熵的乘積newentropy += prob * calcShannonEnt(subdataset)

在獲得特征值之后，以每一個特征值為依據，對取得特征值的列進行數據集劃分。

也就是在某列取得特征值，這一列的數據就會被提取出來參與數據集劃分。

對于每一個特征值對應的數據集，都要依據最后一列元素計算香農熵，然后這個香農熵還要和每個數據集行數占整個dataset行數的比例相乘。實際上，每個數據集的行數就代表了這個特征值在dataset的第i列中出現的次數。

需要注意的是，newentropy需要把第i列獲得的所有特征值對應的數據集的香農熵都算一遍再疊加在一起。

【2.3.4】特征值香農熵變化量

# 獲得香農熵的變化量# baseentroy是dataset的香農熵# newtropy是第i列元素為特征進行集合劃分之后，對新集合開展的香農熵計算和新集合數量比例的乘積infogain = baseentroy - newentropy

這一步相對來說比較簡單，用整個數據集dataset的香農熵減去特征值數據集的香農熵，獲得一個當前熵增益。

【2.3.5】最佳熵增益

        if (infogain > bestinfogain):# 新變化=變化量bestinfogain = infogain# 給bestfeature賦值ibestfeature = i

如果當前熵增益>最佳熵增益，就把當前熵增益賦值給最佳熵增益，記錄此時特征值在dataset中的列數。

總體而言，對于最佳列數的選擇，是對dataset除最后一列之外的每一列元素都進行特征值選擇，再計算香農熵后做出的選擇。

當它們偏離dataset香農熵越遠，被選中的概率越大。

【2.4】多數表決

def majoritycnt(classlist):# classcount是一個空字典classcount = {}for vote in classlist:# classlist是一個外部導入的參數# 從if條件來看，classlist也是一個字典# 對于classlist字典里的每一個鍵if vote not in classcount.keys():# 如果classlist里的鍵和clssscount里的鍵不一樣# classcount字典里的vote鍵賦值0classcount[vote] = 0# 如果classlist里的鍵和clssscount里的鍵一樣# classcount字典里的vote鍵值+1classcount[vote] += 1# Python 3中字典的iteritems()方法已被items()方法取代sortedclasscount = sorted(classcount.items(), key=operator.itemgetter(1), reverse=True)return sortedclasscount[0][0]

對于多數表決部分，相對比較簡單，整體上是一個排序的目標。

整個函數的輸入參數其實也是列表，需要計算出列表中有多少個鍵值，然后對鍵值進行從大到小的排序即可，整個函數只返回最大值。

【2.5】獲得決策樹

def creattree(dataset, labels):# 對dataset中的最后一列取值# classlist是一個列元素列表classlist = [example[-1] for example in dataset]# 修正判斷條件的括號# classlist.count(classlist[0])獲得的是classlist列元素的第一個元素出現的次數# len(classlist)是classlist的行數，等于dataset中樣本的數量if classlist.count(classlist[0]) == len(classlist):return classlist[0]# dataset[0]代表的是列數，如果列數=1，就直接返回classlist代入majoritycnt()函數的值if len(dataset[0]) == 1:return majoritycnt(classlist)# bestfeat通過choosebestfeaturetosplit(dataset)函數取值bestfeat = choosebestfeaturetosplit(dataset)# bestfeatlabel通過labels[bestfeat]函數取值bestfeatlabel = labels[bestfeat]# mytree是一個空字典，字典的鍵為bestfeatlabel，鍵值暫時是一個空字典mytree = {bestfeatlabel: {}}# 從特征標簽中刪除bestfeaturedel (labels[bestfeat])# featvalues的取值是dataset中位置索引為bestfeat的行featvalues = [example[bestfeat] for example in dataset]# 合并同類項uniquevals = set(featvalues)# 對于每一項for value in uniquevals:# sublabels是一個lables的副本sublabels = labels[:]# 獲得決策樹mytree[bestfeatlabel][value] = creattree(splitdataset(dataset, bestfeat, value), sublabels)return mytree

獲得決策樹的部分相對復雜一些，下一篇文章對整體做結構分析，到時候詳細說明。

此時的完整代碼為：

import numpy as np
from math import log  # 引入log()函數求對數
import operator# 定義一個嵌套列表
def creatDataset():# dataset是一個嵌套列表dataset = [[1, 1, 'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no']]# lables也是一個列表labels = ['no surfacing', 'flippers']return dataset, labels# calcShannonEnt是具體的香農熵求解函數
def calcShannonEnt(dataset):# numEntries獲得了dataset列表的行數numEntries = len(dataset)# labelcounts是一個空的字典labelcounts = {}# for函數的意義是，對于dataset里面的每一行都會執行循環操作for feature in dataset:# currentlabel 取到了feature的最后一個元素currentlabel = feature[-1]# 由于labelcounts是一個空字典，labelcounts.keys()在第一次運行的時候不會指向任何標簽，所以會被直接添加# currentlabel是每一行dataset的最后一列，也就是最后一個元素# if函數實際上進行了同類項合并工作if currentlabel not in labelcounts.keys():# 給以currentlabel為標簽的項目賦值0labelcounts[currentlabel] = 0# 只要currentlabel和labelcounts.keys()存儲的元素一致，就給以currentlabel為標簽的項目賦值加1labelcounts[currentlabel] += 1# 定義香農熵的初始值=0ShannonEnt = 0.0# 由于labelcounts是字典，所以可以用key訪問字典的項目for key in labelcounts:# 計算值為浮點數# 用key指向的項目對應的數量比上總數prob = float(labelcounts[key]) / numEntries# 香農熵就是頻數乘以以2為底的頻數的對數，然后還要取負值# 取負值是因為，頻數小于1，所以對數小于0，一旦取負值就獲得了正數ShannonEnt -= prob * log(prob, 2)return ShannonEntdataset, labels = creatDataset()
ShannonEnt = calcShannonEnt(dataset)
print('ShannonEnt=', ShannonEnt)# splitdataset把一些列因素直接刪除后輸出
def splitdataset(dataset, axis, value):# 創建一個新的列表retdataset = []# 對于dataset的每一行for featvec in dataset:# if第axis列的數據剛好和value相等if featvec[axis] == value:# reducedfeature先獲取索引從第0個到axis-1的元素，一共axis個reducedfeatvec = featvec[:axis]# reducedfeature繼續獲取索引從第axis+1開始的所有元素# reducedfeature后面再獲取從第axis+2個開始一直到最后一個元素reducedfeatvec.extend(featvec[axis + 1:])# retdataset存儲了reducedfeature# retdataset中剛好沒有位置索引為axis的元素retdataset.append(reducedfeatvec)return retdatasetdef choosebestfeaturetosplit(dataset):# 對dataset第0行求長度，獲得列數，然后再減去1numfeatures = len(dataset[0]) - 1# 調用函數calcShannonEnt獲得dataset的香農熵baseentroy = calcShannonEnt(dataset)# 定義一個常數bestinfogain = 0.0# 定義一個常數bestfeature = -1# 對于numfeatures中的每一個數# numfeatures比dataset的列數少一個for i in range(numfeatures):# 對于每一個在dataset中的元素，按照位置索引為i的形式提取featlist = [example[i] for example in dataset]# set是一個內置函數，將featlist這個列表轉化為集合# 集合具有合并同類項的作用，重復的元素只會保留一個uniquevals = set(featlist)# 定義一個常數newentropy = 0.0# 對于uniquevals中的每一個值for value in uniquevals:# 調用splitdataset進行子集劃分subdataset = splitdataset(dataset, i, value)# 獲取每一個元素的香農熵prob = len(subdataset) / float(len(dataset))# 更新香農熵newentropy += prob * calcShannonEnt(subdataset)# 獲得香農熵的變化量infogain = baseentroy - newentropy# 如果變化量查過閾值if (infogain > bestinfogain):# 新變化=變化量bestinfogain = infogain# 給bestfeature賦值ibestfeature = ireturn bestfeaturedef majoritycnt(classlist):# classcount是一個空字典classcount = {}for vote in classlist:# classlist是一個外部導入的參數# 從if條件來看，classlist也是一個字典# 對于classlist字典里的每一個鍵if vote not in classcount.keys():# 如果classlist里的鍵和clssscount里的鍵不一樣# classcount字典里的vote鍵賦值0classcount[vote] = 0# 如果classlist里的鍵和clssscount里的鍵一樣# classcount字典里的vote鍵值+1classcount[vote] += 1# Python 3中字典的iteritems()方法已被items()方法取代sortedclasscount = sorted(classcount.items(), key=operator.itemgetter(1), reverse=True)return sortedclasscount[0][0]def creattree(dataset, labels):# 對dataset中的最后一列取值# classlist是一個列元素列表classlist = [example[-1] for example in dataset]# 修正判斷條件的括號# classlist.count(classlist[0])獲得的是classlist列元素的第一個元素出現的次數# len(classlist)是classlist的行數，等于dataset中樣本的數量if classlist.count(classlist[0]) == len(classlist):return classlist[0]# dataset[0]代表的是列數，如果列數=1，就直接返回classlist代入majoritycnt()函數的值if len(dataset[0]) == 1:return majoritycnt(classlist)# bestfeat通過choosebestfeaturetosplit(dataset)函數取值bestfeat = choosebestfeaturetosplit(dataset)# bestfeatlabel通過labels[bestfeat]函數取值bestfeatlabel = labels[bestfeat]# mytree是一個空字典，字典的鍵為bestfeatlabel，鍵值暫時是一個空字典mytree = {bestfeatlabel: {}}# 從特征標簽中刪除bestfeaturedel (labels[bestfeat])# featvalues的取值是dataset中位置索引為bestfeat的行featvalues = [example[bestfeat] for example in dataset]# 合并同類項uniquevals = set(featvalues)# 對于每一項for value in uniquevals:# sublabels是一個lables的副本sublabels = labels[:]# 獲得決策樹mytree[bestfeatlabel][value] = creattree(splitdataset(dataset, bestfeat, value), sublabels)return mytree# 測試代碼
dataset, labels = creatDataset()
tree = creattree(dataset, labels.copy())
print("決策樹:", tree)