《機器學習》周志華習題4.4答案

本文主要程式碼來源於《機器學習實戰》作者:Peter harrington 一書的內容

並參考了Will-Lin的部落格:機器學習演算法的Python實現 (3):CART決策樹與剪枝處理

並對程式碼進行了一些整理和註釋,繪了幾張圖,勉強湊出本篇。

4.4試程式設計實現基於基尼指數進行劃分選擇的決策樹演算法,併為表4.2中資料生成預剪枝、後剪枝決策樹,並與未剪枝決策樹進行比較。

資料:表4.2

編號,色澤,根蒂,敲聲,紋理,臍部,觸感,好瓜
1,青綠,蜷縮,濁響,清晰,凹陷,硬滑,是
2,烏黑,蜷縮,沉悶,清晰,凹陷,硬滑,是
3,烏黑,蜷縮,濁響,清晰,凹陷,硬滑,是
6,青綠,稍蜷,濁響,清晰,稍凹,軟粘,是
7,烏黑,稍蜷,濁響,稍糊,稍凹,軟粘,是
10,青綠,硬挺,清脆,清晰,平坦,軟粘,否
14,淺白,稍蜷,沉悶,稍糊,凹陷,硬滑,否
15,烏黑,稍蜷,濁響,清晰,稍凹,軟粘,否
16,淺白,蜷縮,濁響,模糊,平坦,硬滑,否
17,青綠,蜷縮,沉悶,稍糊,稍凹,硬滑,否
4,青綠,蜷縮,沉悶,清晰,凹陷,硬滑,是
-------------------------------------
5,淺白,蜷縮,濁響,清晰,凹陷,硬滑,是
8,烏黑,稍蜷,濁響,清晰,稍凹,硬滑,是
9,烏黑,稍蜷,沉悶,稍糊,稍凹,硬滑,否
11,淺白,硬挺,清脆,模糊,平坦,硬滑,否
12,淺白,蜷縮,濁響,模糊,平坦,軟粘,否
13,青綠,稍蜷,濁響,稍糊,凹陷,硬滑,否

說明:
1、什麼是gini指數在此不做論述,google一下即可。

2、和作者不同之處:書上說的是用前10個樣本作為訓練集,後面7個樣本作為驗證集,但是我在寫程式碼的時候發現如果用前面十個資料作為訓練集的話生成的未剪枝決策樹如下圖所示,並與書本的結果不同。
前10個訓練樣本生成的決策樹

3、為了保持和書上作圖一致,本文所使用的訓練集是{1,2,3,6,7,10,14,15,16,17,4},驗證集是{4,5,8,9,11,12,13}。

4、因為表格4.2是去掉了數值型的資料,而題4.3使用的是表4.3的資料,為了也能適用數值型資料,並沒有將這部分內容去除,事實上這些程式碼是不會被執行的,每次會根據判斷的結果的資料型別進行計算。
未剪枝、預剪枝和後剪枝對應只需要修改一下主函式中的mode引數即可,
分別為 unpro:未剪枝 prev:預剪枝 post:後剪枝

程式碼:

# coding: utf-8
from numpy import *
import pandas as pd
import codecs
import operator
import copy
import json
from treePlotter import *
'''
輸入:給定資料集   輸出:Gini指數
'''
def calcGini(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: #the the number of unique elements and their occurance
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel]  = 1
Gini = 1.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
Gini -= prob * prob #log base 2
return Gini
'''
輸入:資料集,劃分特徵,劃分特徵的取值         輸出:劃分完畢後的資料子集
這個函式的作用是對資料集進行劃分,對屬性axis值為value的那部分資料進行挑選(注:此處得到的子集特徵數比劃分前少1,少了那個用來劃分的資料)
'''
def splitDataSet(dataSet,axis,value):
returnMat = []
for data in dataSet:
if data[axis]==value:
returnMat.append(data[:axis] data[axis 1:])
return returnMat
'''
與上述函式類似,區別在於上述函式是用來處理離散特徵值而這裡是處理連續特徵值
對連續變數劃分資料集,direction規定劃分的方向,
決定是劃分出小於value的資料樣本還是大於value的資料樣本集
'''
def splitContinuousDataSet(dataSet, axis, value, direction):
retDataSet = []
for featVec in dataSet:
if direction == 0:
if featVec[axis] > value:
#原來的錯誤的
#retDataSet.append(featVec[:axis]   featVec[axis   1:])
#更正之後的
retDataSet.append(featVec)
else:
if featVec[axis] <= value:
#原來的錯誤的
#retDataSet.append(featVec[:axis]   featVec[axis   1:])
#更正之後的
retDataSet.append(featVec)
return retDataSet
'''
決策樹演算法中比較核心的地方,究竟是用何種方式來決定最佳劃分?
使用資訊增益作為劃分標準的決策樹稱為ID3
使用資訊增益比作為劃分標準的決策樹稱為C4.5
本題為資訊增益的ID3樹
從輸入的訓練樣本集中,計算劃分之前的熵,找到當前有多少個特徵,遍歷每一個特徵計算資訊增益,找到這些特徵中能帶來資訊增益最大的那一個特徵。
這裡用分了兩種情況,離散屬性和連續屬性
1、離散屬性,在遍歷特徵時,遍歷訓練樣本中該特徵所出現過的所有離散值,假設有n種取值,那麼對這n種我們分別計算每一種的熵,最後將這些熵加起來
就是劃分之後的資訊熵
2、連續屬性,對於連續值就稍微麻煩一點,首先需要確定劃分點,用二分的方法確定(連續值取值數-1)個切分點。遍歷每種切分情況,對於每種切分,
計算新的資訊熵,從而計算增益,找到最大的增益。
假設從所有離散和連續屬性中已經找到了能帶來最大增益的屬性劃分,這個時候是離散屬性很好辦,直接用原有訓練集中的屬性值作為劃分的值就行,但是連續
屬性我們只是得到了一個切分點,這是不夠的,我們還需要對資料進行二值處理。
'''
def chooseBestFeatureToSplit(dataSet, labels):
numFeatures = len(dataSet[0]) - 1
bestGini = 10000.0
bestFeature = -1
bestSplitDict = {}
for i in range(numFeatures):
# 對連續型特徵進行處理 ,i代表第i個特徵,featList是每次選取一個特徵之後這個特徵的所有樣本對應的資料
featList = [example[i] for example in dataSet]
# 因為特徵分為連續值和離散值特徵,對這兩種特徵需要分開進行處理。
if type(featList[0]).__name__ == 'float' or type(featList[0]).__name__ == 'int':
# 產生n-1個候選劃分點
sortfeatList = sorted(featList)
splitList = []
for j in range(len(sortfeatList) - 1):
splitList.append((sortfeatList[j]   sortfeatList[j   1]) / 2.0)
bestSplitGini = 10000
# 求用第j個候選劃分點劃分時,得到的資訊熵,並記錄最佳劃分點
for value in splitList:
newGini = 0.0
subDataSet0 = splitContinuousDataSet(dataSet, i, value, 0)
subDataSet1 = splitContinuousDataSet(dataSet, i, value, 1)
prob0 = len(subDataSet0) / float(len(dataSet))
newGini  = prob0 * calcGini(subDataSet0)
prob1 = len(subDataSet1) / float(len(dataSet))
newGini  = prob1 * calcGini(subDataSet1)
if newGini < bestSplitGini:
bestSplitGini = newGini
bestSplit = value
# 用字典記錄當前特徵的最佳劃分點
bestSplitDict[labels[i]] = bestSplit
newGini = bestSplitGini
else:
uniqueVals = set(featList)
newGini = 0.0
# 計算該特徵下每種劃分的資訊熵,選取第i個特徵的值為value的子集
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newGini  = prob * calcGini(subDataSet)
if newGini < bestGini:
bestGini = newGini
bestFeature = i
# 若當前節點的最佳劃分特徵為連續特徵,則將其以之前記錄的劃分點為界進行二值化處理
# 即是否小於等於bestSplitValue
if type(dataSet[0][bestFeature]).__name__ == 'float' or type(dataSet[0][bestFeature]).__name__ == 'int':
bestSplitValue = bestSplitDict[labels[bestFeature]]
labels[bestFeature] = labels[bestFeature]   '<='   str(bestSplitValue)
for i in range(shape(dataSet)[0]):
if dataSet[i][bestFeature] <= bestSplitValue:
dataSet[i][bestFeature] = 1
else:
dataSet[i][bestFeature] = 0
return bestFeature
'''
輸入:類別列表     輸出:類別列表中多數的類,即多數表決
這個函式的作用是返回字典中出現次數最多的value對應的key,也就是輸入list中出現最多的那個值
'''
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]
# 由於在Tree中,連續值特徵的名稱以及改為了feature <= value的形式
# 因此對於這類特徵,需要利用正規表示式進行分割,獲得特徵名以及分割閾值
def classify(inputTree, featLabels, testVec):
firstStr = inputTree.keys()[0]
if u'<=' in firstStr:
featvalue = float(firstStr.split(u"<=")[1])
featkey = firstStr.split(u"<=")[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(featkey)
if testVec[featIndex] <= featvalue:
judge = 1
else:
judge = 0
for key in secondDict.keys():
if judge == int(key):
if type(secondDict[key]).__name__ == 'dict':
classLabel = classify(secondDict[key], featLabels, testVec)
else:
classLabel = secondDict[key]
else:
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex] == key:
if type(secondDict[key]).__name__ == 'dict':
classLabel = classify(secondDict[key], featLabels, testVec)
else:
classLabel = secondDict[key]
return classLabel
def testing(myTree, data_test, labels):
error = 0.0
for i in range(len(data_test)):
if classify(myTree, labels, data_test[i]) != data_test[i][-1]:
error  = 1
# print 'myTree %d' % error
return float(error)
def testing_feat(feat,train_data,test_data,labels):
class_list = [example[-1] for example in train_data]
bestFeatIndex = labels.index(feat)
train_data = [example[bestFeatIndex] for example in train_data]
test_data = [(example[bestFeatIndex],example[-1]) for example in test_data]
all_feat = set(train_data)
error = 0.0
for value in all_feat:
class_feat = [ class_list[i] for i in range(len(class_list)) if train_data[i]==value]
major = majorityCnt(class_feat)
for data in test_data:
if data[0]==value and data[1]!=major:
error =1.0
# print 'myTree %d' % error
return error
def testingMajor(major, data_test):
error = 0.0
for i in range(len(data_test)):
if major != data_test[i][-1]:
error  = 1
# print 'major %d' % error
return float(error)
# #後剪枝
# def postPruningTree(inputTree,dataSet,data_test,labels):
#     firstStr=inputTree.keys()[0]
#     secondDict=inputTree[firstStr]
#     classList=[example[-1] for example in dataSet]
#     featkey=copy.deepcopy(firstStr)
#     if u'<=' in firstStr:
#         featkey=firstStr.split(u'<=')[0]
#         featvalue=float(firstStr.split(u'<=')[1])
#     labelIndex=labels.index(featkey)
#     temp_labels=copy.deepcopy(labels)
#     del(labels[labelIndex])
#     for key in secondDict.keys():
#         if type(secondDict[key]).__name__=='dict':
#             if type(dataSet[0][labelIndex]).__name__=='unicode':
#                 inputTree[firstStr][key]=postPruningTree(secondDict[key],\
#                  splitDataSet(dataSet,labelIndex,key),splitDataSet(data_test,labelIndex,key),copy.deepcopy(labels))
#             else:
#                 inputTree[firstStr][key]=postPruningTree(secondDict[key],\
#                 splitContinuousDataSet(dataSet,labelIndex,featvalue,key),\
#                 splitContinuousDataSet(data_test,labelIndex,featvalue,key),\
#                 copy.deepcopy(labels))
#     if testing(inputTree,data_test,temp_labels)<=testingMajor(majorityCnt(classList),data_test):
#         return inputTree
#     return majorityCnt(classList)
'''
主程式,遞迴產生決策樹。
params:
dataSet:用於構建樹的資料集,最開始就是data_full,然後隨著劃分的進行越來越小,第一次劃分之前是17個瓜的資料在根節點,然後選擇第一個bestFeat是紋理
紋理的取值有清晰、模糊、稍糊三種,將瓜分成了清晰(9個),稍糊(5個),模糊(3個),這個時候應該將劃分的類別減少1以便於下次劃分
labels:還剩下的用於劃分的類別
data_full:全部的資料
label_full:全部的類別
既然是遞迴的構造樹,當然就需要終止條件,終止條件有三個:
1、當前節點包含的樣本全部屬於同一類別;-----------------註釋1就是這種情形
2、當前屬性集為空,即所有可以用來劃分的屬性全部用完了,這個時候當前節點還存在不同的類別沒有分開,這個時候我們需要將當前節點作為葉子節點,
同時根據此時剩下的樣本中的多數類(無論幾類取數量最多的類)-------------------------註釋2就是這種情形
3、當前節點所包含的樣本集合為空。比如在某個節點,我們還有10個西瓜,用大小作為特徵來劃分,分為大中小三類,10個西瓜8大2小,因為訓練集生成
樹的時候不包含大小為中的樣本,那麼劃分出來的決策樹在碰到大小為中的西瓜(視為未登入的樣本)就會將父節點的8大2小作為先驗同時將該中西瓜的
大小屬性視作大來處理。
'''
def createTree(dataSet,labels,data_full,labels_full,test_data,mode="unpro"):
classList=[example[-1] for example in dataSet]
if classList.count(classList[0])==len(classList):  #註釋1
return classList[0]
if len(dataSet[0])==1:                             #註釋2
return majorityCnt(classList)
#平凡情況,每次找到最佳劃分的特徵
labels_copy = copy.deepcopy(labels)
bestFeat=chooseBestFeatureToSplit(dataSet,labels)
bestFeatLabel=labels[bestFeat]
if mode=="unpro" or mode=="post":
myTree = {bestFeatLabel: {}}
elif mode=="prev":
if testing_feat(bestFeatLabel,dataSet,test_data,labels_copy)<testingMajor(majorityCnt(classList), test_data):
myTree = {bestFeatLabel: {}}
else:
return majorityCnt(classList)
featValues=[example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
'''
剛開始很奇怪為什麼要加一個uniqueValFull,後來思考下覺得應該是在某次劃分,比如在根節點劃分紋理的時候,將資料分成了清晰、模糊、稍糊三塊
,假設之後在模糊這一子資料集中,下一劃分屬性是觸感,而這個資料集中只有軟粘屬性的西瓜,這樣建立的決策樹在當前節點劃分時就只有軟粘這一屬性了,
事實上訓練樣本中還有硬滑這一屬性,這樣就造成了樹的缺失,因此用到uniqueValFull之後就能將訓練樣本中有的屬性值都囊括。
如果在某個分支每找到一個屬性,就在其中去掉一個,最後如果還有剩餘的根據父節點投票決定。
但是即便這樣,如果訓練集中沒有出現觸感屬性值為“一般”的西瓜,但是分類時候遇到這樣的測試樣本,那麼應該用父節點的多數類作為預測結果輸出。
'''
if type(dataSet[0][bestFeat]).__name__ == 'unicode':
currentlabel = labels_full.index(labels[bestFeat])
featValuesFull = [example[currentlabel] for example in data_full]
uniqueValsFull = set(featValuesFull)
del(labels[bestFeat])
'''
針對bestFeat的每個取值,劃分出一個子樹。對於紋理,樹應該是{"紋理":{?}},顯然?處是紋理的不同取值,有清晰模糊和稍糊三種,對於每一種情況,
都去建立一個自己的樹,大概長這樣{"紋理":{"模糊":{0},"稍糊":{1},"清晰":{2}}},對於0\1\2這三棵樹,每次建樹的訓練樣本都是值為value特徵數減少1
的子集。
'''
for value in uniqueVals:
subLabels = labels[:]
if type(dataSet[0][bestFeat]).__name__ == 'unicode':
uniqueValsFull.remove(value)
myTree[bestFeatLabel][value] = createTree(splitDataSet \
(dataSet, bestFeat, value), subLabels, data_full, labels_full,splitDataSet \
(test_data, bestFeat, value),mode=mode)
if type(dataSet[0][bestFeat]).__name__ == 'unicode':
for value in uniqueValsFull:
myTree[bestFeatLabel][value] = majorityCnt(classList)
if mode=="post":
if testing(myTree, test_data, labels_copy) > testingMajor(majorityCnt(classList), test_data):
return majorityCnt(classList)
return myTree
# 讀入csv檔案資料
def load_data(file_name):
file = codecs.open(file_name, "r", 'utf-8')
filedata = [line.strip('\n').split(',') for line in file]
filedata = [[float(i) if '.' in i else i for i in row] for row in filedata]  # change decimal from string to float
train_data = [row[1:] for row in filedata[1:12]]
test_data = [row[1:] for row in filedata[11:]]
labels = []
for label in filedata[0][1:-1]:
labels.append(unicode(label))
return train_data,test_data,labels
if __name__=="__main__":
train_data,test_data,labels = load_data("data/西瓜資料集2.0.csv")
data_full = train_data[:]
labels_full = labels[:]
'''
為了程式碼的簡潔,將預剪枝,後剪枝和未剪枝三種模式用一個引數mode傳入建樹的過程
post代表後剪枝,prev代表預剪枝,unpro代表不剪枝
'''
mode="unpro"
myTree = createTree(train_data,labels, data_full, labels_full,test_data,mode = mode)
# myTree = postPruningTree(myTree,train_data,test_data,labels_full)
createPlot(myTree)
print json.dumps(myTree, ensure_ascii=False, indent=4)

結果繪圖:

未剪枝決策樹:

未剪枝決策樹

預剪枝決策樹:

預剪枝決策樹

後剪枝決策樹:

後剪枝決策樹

總結:

書上原文後剪枝採用的是隻要效能不下降就不剪枝,事實上一般都是效能不提高就不剪枝。這裡面的區別在於效能相等的情況下書上不剪而一般都會剪枝。因為根據奧卡姆剃刀原則,“若無必要,勿增實體”(Non sunt multiplicanda entia sine necessitate)。