1.引言
學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的同學(xué)對(duì)二叉樹(shù)應(yīng)該不陌生：二叉樹(shù)是一個(gè)連通的無(wú)環(huán)圖，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。如下圖(一)就是一個(gè)深度k=3的二叉樹(shù)。
（圖一） （圖二）
二元決策樹(shù)與此類似。不過(guò)二元決策樹(shù)是基于屬性做一系列二元(是/否)決策。每次決策從下面的兩種決策中選擇一種，然后又會(huì)引出另外兩種決策，依次類推直到葉子節(jié)點(diǎn):即最終的結(jié)果。也可以理解為是對(duì)二叉樹(shù)的遍歷，或者很多層的if-else嵌套。
這里需要特別說(shuō)明的是：二元決策樹(shù)中的深度算法與二叉樹(shù)中的深度算法是不一樣的。二叉樹(shù)的深度是指有多少層，而二元決策樹(shù)的深度是指經(jīng)過(guò)多少層計(jì)算。以上圖(一)為例，二叉樹(shù)的深度k=3，而在二元決策樹(shù)中深度k=2。
圖二就是一個(gè)二元決策樹(shù)的例子，其中最關(guān)鍵的是如何選擇切割點(diǎn)：即X[0]<=-0.075中的-0.0751是如何選擇出來(lái)的？
2.二元決策樹(shù)切割點(diǎn)的選擇
切割點(diǎn)的選擇是二元決策樹(shù)最核心的部分，其基本思路是：遍歷所有數(shù)據(jù)，嘗試每個(gè)數(shù)據(jù)作為分割點(diǎn)，并計(jì)算此時(shí)左右兩側(cè)的數(shù)據(jù)的離差平方和，并從中找到最小值，然后找到離差平方和最小時(shí)對(duì)應(yīng)的數(shù)據(jù)，它就是最佳分割點(diǎn)。下面通過(guò)具體的代碼講解這一過(guò)程：
import numpyimport matplotlib.pyplot as plot#建立一個(gè)100數(shù)據(jù)的測(cè)試集nPoints = 100#x的取值范圍：-0.5～+0.5的nPoints等分xPlot = [-0.5+1/nPoints*i for i in range(nPoints + 1)]#y值：在x的取值上加一定的隨機(jī)值或者叫噪音數(shù)據(jù)#設(shè)置隨機(jī)數(shù)算法生成數(shù)據(jù)時(shí)的開(kāi)始值，保證隨機(jī)生成的數(shù)值一致numpy.random.seed(1)##隨機(jī)生成寬度為0.1的標(biāo)準(zhǔn)正態(tài)分布的數(shù)值##上面的設(shè)置是為了保證numpy.random這步生成的數(shù)據(jù)一致y = [s + numpy.random.normal(scale=0.1) for s in xPlot]#離差平方和列表sumSSE = []for i in range(1, len(xPlot)): #以xPlot[i]為界，分成左側(cè)數(shù)據(jù)和右側(cè)數(shù)據(jù)
lhList = list(xPlot[0:i])
rhList = list(xPlot[i:len(xPlot)]) #計(jì)算每側(cè)的平均值
lhAvg = sum(lhList) / len(lhList)
rhAvg = sum(rhList) / len(rhList) #計(jì)算每側(cè)的離差平方和
lhSse = sum([(s - lhAvg) * (s - lhAvg) for s in lhList])
rhSse = sum([(s - rhAvg) * (s - rhAvg) for s in rhList]) #統(tǒng)計(jì)總的離差平方和，即誤差和
sumSSE.append(lhSse + rhSse)##找到最小的誤差和minSse = min(sumSSE)##產(chǎn)生最小誤差和時(shí)對(duì)應(yīng)的數(shù)據(jù)索引idxMin = sumSSE.index(minSse)##打印切割點(diǎn)數(shù)據(jù)及切割點(diǎn)位置print("切割點(diǎn)位置："+str(idxMin)) ##49print("切割點(diǎn)數(shù)據(jù)："+str(xPlot[idxMin]))##-0.010000000000000009##繪制離差平方和隨切割點(diǎn)變化而變化的曲線plot.plot(range(1, len(xPlot)), sumSSE)
plot.xlabel('Split Point Index')
plot.ylabel('Sum Squared Error')
plot.show()
3.使用二元決策樹(shù)擬合數(shù)據(jù)
這里使用sklearn.tree.DecisionTreeRegressor函數(shù)。下面只顯示了主要代碼，數(shù)據(jù)生成部分同上：
from sklearn import treefrom sklearn.tree import DecisionTreeRegressor##使用二元決策樹(shù)擬合數(shù)據(jù):深度為1##說(shuō)明numpy.array(xPlot).reshape(1, -1)：這是傳入?yún)?shù)的需要：list->narraysimpleTree = DecisionTreeRegressor(max_depth=1)
simpleTree.fit(numpy.array(xPlot).reshape(-1,1), numpy.array(y).reshape(-1,1))##讀取訓(xùn)練后的預(yù)測(cè)數(shù)據(jù)y_pred = simpleTree.predict(numpy.array(xPlot).reshape(-1,1))##繪圖plot.figure()
plot.plot(xPlot, y, label='True y')
plot.plot(xPlot, y_pred, label='Tree Prediction ', linestyle='--')
plot.legend(bbox_to_anchor=(1,0.2))
plot.axis('tight')
plot.xlabel('x')
plot.ylabel('y')
plot.show()
結(jié)果如下圖：
（圖三）
當(dāng)深度依次為2（圖四）、深度為6（圖5）時(shí)的結(jié)果：
（圖四） （圖五）
4.二元決策樹(shù)的過(guò)度擬合
二元決策樹(shù)同普通最小二乘法一樣，都存在擬合過(guò)度的情況，如圖五所示，幾乎看不到預(yù)測(cè)值的曲線，這就是擬合過(guò)度了。判斷是否擬合過(guò)度有兩種方法：
1）觀察結(jié)果圖。這個(gè)很好理解，就是直接看繪制的對(duì)比圖。
2）比較決策樹(shù)終止節(jié)點(diǎn)的數(shù)目與數(shù)據(jù)的規(guī)模。生產(chǎn)圖五的曲線的深度是6(最深會(huì)有7層)，即會(huì)有26=64個(gè)節(jié)點(diǎn)，而數(shù)據(jù)集中一共才有100個(gè)數(shù)據(jù)，也就是說(shuō)有很多節(jié)點(diǎn)是只包括一個(gè)數(shù)據(jù)的。
5.二元決策樹(shù)深度的選擇
一般是通過(guò)不同深度二元決策樹(shù)的交叉驗(yàn)證(前面已講過(guò)原理)來(lái)確定最佳深度的，基本思路：
1）確定深度列表：
2）設(shè)置采用幾折交叉驗(yàn)證
3）計(jì)算每折交叉驗(yàn)證時(shí)的樣本外數(shù)據(jù)的均方誤差
4）繪圖，觀察結(jié)果
下面就通過(guò)深度分別為1～7的10折交叉驗(yàn)證來(lái)檢驗(yàn)下最佳深度。
import numpy
import matplotlib.pyplot as plotfrom sklearn import treefrom sklearn.tree import DecisionTreeRegressor#建立一個(gè)100數(shù)據(jù)的測(cè)試集nPoints = 100#x的取值范圍：-0.5～+0.5的nPoints等分xPlot = [-0.5+1/nPoints*i for i in range(nPoints + 1)]#y值：在x的取值上加一定的隨機(jī)值或者叫噪音數(shù)據(jù)#設(shè)置隨機(jī)數(shù)算法生成數(shù)據(jù)時(shí)的開(kāi)始值，保證隨機(jī)生成的數(shù)值一致numpy.random.seed(1)##隨機(jī)生成寬度為0.1的標(biāo)準(zhǔn)正態(tài)分布的數(shù)值##上面的設(shè)置是為了保證numpy.random這步生成的數(shù)據(jù)一致y = [s + numpy.random.normal(scale=0.1) for s in xPlot]##測(cè)試數(shù)據(jù)的長(zhǎng)度nrow = len(xPlot)##設(shè)置二元決策樹(shù)的深度列表depthList = [1, 2, 3, 4, 5, 6, 7]##每個(gè)深度下的離差平方和xvalMSE = []##設(shè)置n折交叉驗(yàn)證nxval = 10##外層循環(huán)：深度循環(huán)for iDepth in depthList: ##每個(gè)深度下的樣本外均方誤差
oosErrors =0 ##內(nèi)層循環(huán)：交叉驗(yàn)證循環(huán)
for ixval in range(nxval+1): #定義訓(xùn)練集和測(cè)試集標(biāo)簽
xTrain = [] #訓(xùn)練集
xTest = [] #測(cè)試集
yTrain = [] #訓(xùn)練集標(biāo)簽
yTest = [] #測(cè)試集標(biāo)簽
for a in range(nrow): ##如果采用a%ixval==0的方式寫(xiě)，會(huì)有除數(shù)為0的錯(cuò)誤
if a%nxval != ixval%nxval:
xTrain.append(xPlot[a])
yTrain.append(y[a]) else :
xTest.append(xPlot[a])
yTest.append(y[a])
##深度為max_depth=iDepth的訓(xùn)練
treeModel = DecisionTreeRegressor(max_depth=iDepth) ##轉(zhuǎn)換參數(shù)類型
treeModel.fit(numpy.array(xTrain).reshape(-1, 1), numpy.array(yTrain).reshape(-1, 1)) ##讀取預(yù)測(cè)值：使用測(cè)試集獲取樣本外誤差
treePrediction = treeModel.predict(numpy.array(xTest).reshape(-1, 1)) ##離差列表：使用測(cè)試標(biāo)簽獲取樣本外誤差
error = [yTest[r] - treePrediction[r] for r in range(len(yTest))] ##每個(gè)深度下的樣本外均方誤差和
oosErrors += sum([e * e for e in error])
#計(jì)算每個(gè)深度下的樣本外平均離差平方和
mse = oosErrors/nrow ##添加到離差平方和列表 xvalMSE.append(mse)
##繪圖---樣本外離差和的平方平均值隨深度變化的曲線plot.plot(depthList, xvalMSE)
plot.axis('tight')
plot.xlabel('Tree Depth')
plot.ylabel('Mean Squared Error')
plot.show()
結(jié)果如圖：
（圖六）
從圖中可以看出，當(dāng)深度為3時(shí)的效果最好，下面我們把深度調(diào)成3，觀察結(jié)果(為了效果調(diào)整了上面代碼的顏色值)：
（圖七）
http://www.cnblogs.com/lc1217/p/6739612.html
延伸閱讀
- 學(xué)習(xí)、實(shí)踐。再學(xué)習(xí)，再實(shí)踐 2023-04-15
- 從0到0.5，堅(jiān)持學(xué)習(xí) 2022-09-08
- 來(lái)萬(wàn)碼學(xué)習(xí)，是我最正確的選擇 2022-09-07
- 友誼之樹(shù)上將垂下豐碩的果實(shí) 2022-07-13
- 沉舟側(cè)畔千帆過(guò)，病樹(shù)前頭萬(wàn)木春 】 2022-07-13
- 學(xué)習(xí)與實(shí)踐 2022-06-24
- 友誼之樹(shù)上將垂下豐碩的果實(shí) 2022-02-07
- 沉舟側(cè)畔千帆過(guò)，病樹(shù)前頭萬(wàn)木春 2022-02-07
- 學(xué)習(xí)——工作——再學(xué)習(xí) 2021-06-01
- 不斷學(xué)習(xí)，才能不斷進(jìn)步 2021-05-19
學(xué)習(xí)、實(shí)踐。再學(xué)習(xí)，再實(shí)踐