文章目錄
- 1.ID3及C4.5算法基礎
-
- 1.1 計算香農熵
- 1.2 按照給定特征劃分資料集
- 1.3 選擇最優特征
- 1.4 多數表決實作
- 2.基于ID3、C4.5生成算法建立決策樹
- 3.使用決策樹進行分類
- 4.存儲決策樹
通過 決策樹原理及相關概念細節我們知道，決策樹的學習算法主要包括3個步驟：特征選擇、決策樹生成算法、決策樹剪枝，我們按照這個思路來一一實作相關功能。
本文的實作目前主要涉及特征選擇、ID3及C4.5算法。剪枝及CART算法暫未涉及，後期補上。
1.ID3及C4.5算法基礎
前面文章我們提到過，ID3與C4.5的主要差別是特征選擇準則的不同：
- ID3：資訊增益
- C4.5：資訊增益比
1.1 計算香農熵
不管是這兩者的哪一種，都涉及到資訊增益的計算，而計算資訊增益的基礎又是計算香農熵。是以我們先來實作計算香農熵的代碼。
from math import log
import operator
# 計算給定資料集的香農熵
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 -= prob * log(prob,2) # 以2為底求對數
return shannonEnt
然後建立書中的資料集，并計算該資料集的香農熵：
# 建立自己的資料集
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing','flippers']
return dataSet, labels
myDat,labels=createDataSet()
myDat # [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
calcShannonEnt(myDat) # 0.9709505944546686
1.2 按照給定特征劃分資料集
# 按照給定特征劃分資料集
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
測試：
splitDataSet(myDat,0,1) # [[1, 'yes'], [1, 'yes'], [0, 'no']]
1.3 選擇最優特征
# 選擇最好的資料集劃分方式
# 選擇最好的資料集劃分方式
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 # ID3
# infoGain = baseEntropy - newEntropy # C4.5
# 計算最好的資訊增益
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
1.4 多數表決實作
在ID3、C4.5算法的停止條件之一是：沒有特征可以選擇時停止算法，但如果這時該結點類标簽依然不是唯一的，此時我們需要決定如何定義該葉子結點。在這種情況下，通常采用多數表決的方法決定該葉子結點的分類。
# 多數表決實作
def majorityCnt(classList):
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)
# Python3中不再支援iteritems()，将iteritems()改成items()
return sortedClassCount[0][0]
對于“多數表決實作”函數的注釋：
-
1.dict.items()
作用：是可以将字典中的所有項，以清單方式傳回。因為字典是無序的，是以用items方法傳回字典的所有項，也是沒有順序的。
-
2.operator.itemgetter()
operator子產品提供的itemgetter函數用于擷取對象的哪些維的資料，參數為一些序号.
-
3.sorted()函數，排序
list.sort()是對已經存在的清單進行操作，進而可以改變進行操作的清單；
sorted傳回的是一個新的list，而不是在原來的基礎上進行的操作
2.基于ID3、C4.5生成算法建立決策樹
這裡主要介紹基于ID3生成算法建立決策樹，C4.5隻需要在ID3生成決策樹代碼上将chooseBestFeatureToSplit(dataSet)函數中infoGain = baseEntropy - newEntropy換成infoGain = baseEntropy - newEntropy即可 。
# 建立樹的函數代碼
def creatTree(dataSet,labels):
classList = [example[-1] for example in dataSet]
labels2 = labels[:]
# 類别完全相同則停止繼續劃分
if classList.count(classList[0]) == len(classList):
return classList[0]
# 周遊完所有特征時傳回出現次數最多的類别
if len(dataSet[0]) == 1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels2[bestFeat]
myTree = {bestFeatLabel:{}}
del (labels2[bestFeat])
# 得到清單包含的(標明為最佳特征的)所有屬性值
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels2[:] # 複制類标簽
# 遞歸
myTree[bestFeatLabel][value] = creatTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
對于“creatTree”函數的注釋：
-
1.list.count(obj)
統計某個元素在清單中出現的次數
-
2.del,list.remove(),list.pop()
del:根據索引位置來删除單個值或指定範圍内的值；
list.remove():删除單個元素，删除首個符合條件的元素，按值删除，傳回值為空;
list.pop():删除索引位置元素，無參情況下删除最後一個元素，傳回删除的元素值;
測試：
myTree = creatTree(myDat, labels)
myTree # {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
3.使用決策樹進行分類
# 使用決策樹的分類函數
def classify(inputTree, featLabels, testVec):
firstStr = list(inputTree.keys())[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex] == key:
if type(secondDict[key]).__name__=='dict':
#if isinstance(secondDict[key], dict): 這個也可以
classLabel = classify(secondDict[key],featLabels,testVec)
else:
classLabel = secondDict[key]
return classLabel
對于“classify”的注釋：
-
1.type(a).name == ‘dict’:
可判斷a的類型是否類型為dict，list tuple 這些也适用
-
2.也可以用isinstance(變量名，類型)判斷類型：
判斷該變量是否是該類型，或者是否是該類和該類的父類類型；
小注： type(變量名)：擷取該變量名的類型,結合==判斷該變量的類型是否等于目标類型(等号右邊value值) 比如：a類繼承b類,執行個體c=a() isinstance(c,a)和isinstance(c,b)都是True type(c)的value值是a，a是不等于b的，是以a==b為False即：type(c)==b為False -
3.==和is
==：變量名的value值是否相等
is：變量名的id(位址)是否相等（數字類型的value值相等則id相等）
測試：
classify(myTree, labels, [1,0]) # 'no'
classify(myTree, labels, [1,1]) # 'yes'
4.存儲決策樹
import pickle
# 使用pickle子產品存儲決策樹
def storeTree(inputTree, filename):
with open(filename, 'wb') as f:
pickle.dump(inputTree, f)
# 加載決策樹
def grabTree(filename):
with open(filename, 'rb') as f:
return pickle.load(f)
測試：
storeTree(myTree,'classifierStorage.txt')
grabTree('classifierStorage.txt') # {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
參考資料：
《機器學習實戰》第三章
![簡單文檔分類——樸素貝葉斯算法樸素貝葉斯算法簡單文檔分類執行個體步驟總結樸素貝葉斯分類調用(sklearn)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)