姓名：唐來賓? 學號：17101223417

轉載http://mp.weixin.qq.com/s/-CSSh2ptYXmNXzYYjCkYbQ

【嵌牛導讀】本文主要介紹決策樹用于回歸問題的相關算法實現(xiàn)挚歧，其中包括回歸樹(regression tree)和模型樹(model tree)的實現(xiàn)唉擂，并介紹了預剪枝(preprune)和后剪枝(postprune)的防止樹過擬合的技術以及實現(xiàn)艇炎。最后對回歸樹和標準線性回歸進行了對比。

【嵌牛鼻子】樹回歸 決策

【嵌牛提問】如何優(yōu)化樹回歸钝的？

【嵌牛正文】前言

最近由于開始要把精力集中在課題的應用上面了涛舍，這篇總結之后算法原理的學習先告一段落王凑。本文主要介紹決策樹用于回歸問題的相關算法實現(xiàn)获雕，其中包括回歸樹(regression tree)和模型樹(model tree)的實現(xiàn)，并介紹了預剪枝(preprune)和后剪枝(postprune)的防止樹過擬合的技術以及實現(xiàn)岛马。最后對回歸樹和標準線性回歸進行了對比棉姐。

正文

在之前的文章中我總結了通過使用構建決策樹來進行類型預測。直觀來看樹結構最容易對分類問題進行處理蛛枚，通過遞歸我們在數(shù)據(jù)中選取最佳分割特征對訓練數(shù)據(jù)進行分割并進行樹分裂最終到達觸底條件獲得訓練出來決策樹谅海，可以通過可視化的方式直觀的查看訓練模型并對數(shù)據(jù)進行分類。

通常決策樹樹分裂選擇特征的方法有ID3, C4.5算法, C5.0算法和CART樹蹦浦。在《機器學習算法實踐-決策樹(Decision Tree)》中對ID3以及C4.5算法進行了介紹并使用ID3算法處理了分類問題扭吁。本文主要使用決策樹解決回歸問題，使用CART(Classification And Regression Trees)算法盲镶。

CART

CART是一種二分遞歸分割的技術侥袜，分割方法采用基于最小距離的基尼指數(shù)估計函數(shù)，將當前的樣本集分為兩個子樣本集溉贿，使得生成的的每個非葉子節(jié)點都有兩個分支枫吧。因此，CART算法生成的決策樹是結構簡潔的二叉樹宇色。

分類樹是針對目標變量是離散型變量九杂，通過二叉樹將數(shù)據(jù)進行分割成離散類的方法颁湖。而回歸樹則是針對目標變量是連續(xù)性的變量，通過選取最優(yōu)分割特征的某個值例隆，然后數(shù)據(jù)根據(jù)大于或者小于這個值進行劃分進行樹分裂最終生成回歸樹甥捺。

特征和最佳分割點的選取

在使用決策樹解決回歸問題中我們需要不斷的選取某一特征的一個值作為分割點來生成子樹。選取的標準就是使得被分割的兩部分數(shù)據(jù)能有最好的純度镀层。

對于離散型數(shù)據(jù)我們可以通過計算分割兩部分數(shù)據(jù)的基尼不純度的變化來判定最有分割點镰禾；

對于連續(xù)性變量我們通過計算最小平方殘差，也就是選擇使得分割后數(shù)據(jù)方差變得最小的特征和分割點唱逢。直觀的理解就是使得分割的兩部分數(shù)據(jù)能夠有最相近的值吴侦。

樹分裂的終止條件

有了選取分割特征和最佳分割點的方法，樹便可以依此進行分裂坞古，但是分裂的終止條件是什么呢?

節(jié)點中所有目標變量的值相同, 既然都已經是相同的值了自然沒有必要在分裂了备韧，直接返回這個值就好了.

樹的深度達到了預先指定的最大值

不純度的減小量小于預先定好的閾值,也就是之進一步的分割數(shù)據(jù)并不能更好的降低數(shù)據(jù)的不純度的時候就可以停止樹分裂了。

節(jié)點的數(shù)據(jù)量小于預先定好的閾值

回歸樹的Python實現(xiàn)

本部分使用Python實現(xiàn)簡單的回歸樹绸贡，并對給定的數(shù)據(jù)進行回歸并可視化回歸曲線和樹結構盯蝴。完整代碼詳見: https://github.com/PytLab/MLBox/tree/master/classification_and_regression_trees

首先是加載數(shù)據(jù)的部分，這里的所有測試數(shù)據(jù)我均使用的《Machine Learning in Action》中的數(shù)據(jù)听怕，格式比較規(guī)整加載方式也比較一致, 這里由于做樹回歸，自變量和因變量都放在同一個二維數(shù)組中:

defload_data(filename):

''' 加載文本文件中的數(shù)據(jù).

'''

dataset=[]

withopen(filename,'r')asf:

forlineinf:

line_data=[float(data)fordatainline.split()]

dataset.append(line_data)

returndataset

樹回歸中再找到分割特征和分割值之后需要將數(shù)據(jù)進行劃分以便構建子樹或者葉子節(jié)點:

defsplit_dataset(dataset,feat_idx,value):

''' 根據(jù)給定的特征編號和特征值對數(shù)據(jù)集進行分割

'''

ldata,rdata=[],[]

fordataindataset:

ifdata[feat_idx]

ldata.append(data)

else:

rdata.append(data)

returnldata,rdata

然后就是重要的選取最佳分割特征和分割值了虑绵，這里我們通過找到使得分割后的方差最小的分割點最為最佳分割點:

defchoose_best_feature(dataset,fleaf,ferr,opt):

''' 選取最佳分割特征和特征值

dataset: 待劃分的數(shù)據(jù)集

fleaf: 創(chuàng)建葉子節(jié)點的函數(shù)

ferr: 計算數(shù)據(jù)誤差的函數(shù)

opt: 回歸樹參數(shù).

err_tolerance: 最小誤差下降值;

n_tolerance: 數(shù)據(jù)切分最小樣本數(shù)

'''

dataset=np.array(dataset)

m,n=dataset.shape

err_tolerance,n_tolerance=opt['err_tolerance'],opt['n_tolerance']

err=ferr(dataset)

best_feat_idx,best_feat_val,best_err=0,0,float('inf')

# 遍歷所有特征

forfeat_idxinrange(n-1):

values=dataset[:,feat_idx]

# 遍歷所有特征值

forvalinvalues:

# 按照當前特征和特征值分割數(shù)據(jù)

ldata,rdata=split_dataset(dataset.tolist(),feat_idx,val)

iflen(ldata)

# 如果切分的樣本量太小

continue

# 計算誤差

new_err=ferr(ldata)+ferr(rdata)

ifnew_err

best_feat_idx=feat_idx

best_feat_val=val

best_err=new_err

# 如果誤差變化并不大歸為一類

ifabs(err-best_err)

returnNone,fleaf(dataset)

# 檢查分割樣本量是不是太小

ldata,rdata=split_dataset(dataset.tolist(),best_feat_idx,best_feat_val)

iflen(ldata)

returnNone,fleaf(dataset)

returnbest_feat_idx,best_feat_val

其中尿瞭，停止選取的條件有兩個: 一個是當分割的子數(shù)據(jù)集的大小小于一定值；一個是當選取的最佳分割點分割的數(shù)據(jù)的方差減小量小于一定的值翅睛。

fleaf是創(chuàng)建葉子節(jié)點的函數(shù)引用声搁，不同的樹結構此函數(shù)也是不同的，例如本部分的回歸樹捕发，創(chuàng)建葉子節(jié)點就是根據(jù)分割后的數(shù)據(jù)集平均值疏旨，而對于模型樹來說，此函數(shù)返回值是根據(jù)數(shù)據(jù)集得到的回歸系數(shù)扎酷。ferr是計算數(shù)據(jù)集不純度的函數(shù)檐涝，不同的樹模型該函數(shù)也會不同，對于回歸樹法挨，此函數(shù)計算數(shù)據(jù)集的方差來判定數(shù)據(jù)集的純度谁榜，而對于模型樹來說我們需要計算線性模型擬合程度也就是線性模型的殘差平方和。

然后就是最主要的回歸樹的生成函數(shù)了凡纳，樹結構肯定需要通過遞歸創(chuàng)建的窃植，選不出新的分割點的時候就觸底：

defcreate_tree(dataset,fleaf,ferr,opt=None):

''' 遞歸創(chuàng)建樹結構

dataset: 待劃分的數(shù)據(jù)集

fleaf: 創(chuàng)建葉子節(jié)點的函數(shù)

ferr: 計算數(shù)據(jù)誤差的函數(shù)

opt: 回歸樹參數(shù).

err_tolerance: 最小誤差下降值;

n_tolerance: 數(shù)據(jù)切分最小樣本數(shù)

'''

ifoptisNone:

opt={'err_tolerance':1,'n_tolerance':4}

# 選擇最優(yōu)化分特征和特征值

feat_idx,value=choose_best_feature(dataset,fleaf,ferr,opt)

# 觸底條件

iffeat_idxisNone:

returnvalue

# 創(chuàng)建回歸樹

tree={'feat_idx':feat_idx,'feat_val':value}

# 遞歸創(chuàng)建左子樹和右子樹

ldata,rdata=split_dataset(dataset,feat_idx,value)

ltree=create_tree(ldata,fleaf,ferr,opt)

rtree=create_tree(rdata,fleaf,ferr,opt)

tree['left']=ltree

tree['right']=rtree

returntree

使用回歸樹對數(shù)據(jù)進行回歸

這里使用了現(xiàn)成的分段數(shù)據(jù)作為訓練數(shù)據(jù)生成回歸樹，本文所有使用的數(shù)據(jù)詳見: https://github.com/PytLab/MLBox/tree/master/classification_and_regression_trees

可視化數(shù)據(jù)點

dataset=load_data('ex0.txt')

dataset=np.array(dataset)

# 繪制散點

plt.scatter(dataset[:,0],dataset[:,1])

創(chuàng)建回歸樹并可視化

看到這種分段的數(shù)據(jù)荐糜，回歸樹擬合它可是最合適不過了巷怜，我們創(chuàng)建回歸樹:

tree=create_tree(dataset,fleaf,ferr,opt={'n_tolerance':4,

'err_tolerance':1})

通過Python字典表示的回歸樹結構:

{'feat_idx':0,

'feat_val':0.40015800000000001,

'left':{'feat_idx':0,

'feat_val':0.20819699999999999,

'left': -0.023838155555555553,

'right':1.0289583666666666},

'right':{'feat_idx':0,

'feat_val':0.609483,

'left':1.980035071428571,

'right':{'feat_idx':0,

'feat_val':0.81674199999999997,

'left':2.9836209534883724,

'right':3.9871631999999999}}}

這里我還是使用Graphviz來可視化回歸樹葛超，類似之前決策樹做分類的文章中的dotify函數(shù)，這里稍微修改下葉子節(jié)點的label延塑，我們便可以遞歸得到決策樹對應的dot文件, dotify函數(shù)的實現(xiàn)見:https://github.com/PytLab/MLBox/blob/master/classification_and_regression_trees/regression_tree.py#L159

然后獲取樹結構圖:

datafile='ex0.txt'

dotfile='{}.dot'.format(datafile.split('.')[0])

withopen(dotfile,'w')asf:

content=dotify(tree)

f.write(content)

生成回歸樹圖片:

dot -Tpng ex0.dot -o ex0_tree.png

其中節(jié)點上數(shù)字代表:特征編號: 特征分割值

繪制回歸樹回歸曲線

有了回歸樹绣张，我們便可以繪制回歸樹回歸曲線，看看它對于分段數(shù)據(jù)是否能有較好的回歸效果：

# 繪制回歸曲線

x=np.linspace(0,1,50)

y=[tree_predict([i],tree)foriinx]

plt.plot(x,y,c='r')

plt.show()

樹剪枝

在介紹樹剪枝之前先使用上一部分的代碼對兩組類似的數(shù)據(jù)進行回歸页畦，可視化后的數(shù)據(jù)以及回歸曲線如下(數(shù)據(jù)文件左&數(shù)據(jù)文件右):

左右兩邊的數(shù)據(jù)的分布基本相同但是使用相同的參數(shù)得到的回歸樹卻完全不同左邊的回歸樹只有兩個分支胖替，而右邊的分支則有很多，甚至有時候會為所有的數(shù)據(jù)點得到一個分支豫缨，這樣回歸樹將會非常的龐大, 如下是可視化得到的兩個回歸樹:

如果一棵樹的節(jié)點過多則表明該模型可能對數(shù)據(jù)進行了“過擬合”独令。那么我們需要降低決策樹的復雜度來避免過擬合，此過程就是剪枝好芭。剪枝技術又分為預剪枝和后剪枝燃箭。

預剪枝

預剪枝是在生成決策樹之前通過改變參數(shù)然后在樹生成的過程中進行的。比如在上文中我們創(chuàng)建回歸樹的函數(shù)中有個opt參數(shù)舍败，其中包含n_tolerance和err_tolerance招狸，他們可以控制何時停止樹的分裂，當增大葉子節(jié)點的最小數(shù)據(jù)量以及增大誤差容忍度邻薯，樹的分裂也會越提前的終止裙戏。當我們把誤差變化容忍度增加到2000的時候得到的回歸樹以及回歸曲線可視化如下:

后剪枝

預剪枝技術需要用于預先指定參數(shù)，但是后剪枝技術則是通過測試數(shù)據(jù)來自動進行剪枝不需要用戶干預因此是一種更理想的剪枝技術厕诡，但是我們需要寫剪枝函數(shù)來處理累榜。

后剪枝的大致思想就是我們針對一顆子樹，嘗試將其左右子樹(節(jié)點)合并灵嫌，通過測試數(shù)據(jù)計算合并前后的方差壹罚，如果合并后的方差比合并前的小，這說明可以合并此子樹寿羞。

對樹進行塌陷處理: 我們對一棵樹進行塌陷處理猖凛，就是遞歸將這棵樹進行合并返回這棵樹的平均值。

defcollapse(tree):

''' 對一棵樹進行塌陷處理, 得到給定樹結構的平均值

'''

ifnot_tree(tree):

returntree

ltree,rtree=tree['left'],tree['right']

return(collapse(ltree)+collapse(rtree))/2

后剪枝的Python實現(xiàn):

defpostprune(tree,test_data):

''' 根據(jù)測試數(shù)據(jù)對樹結構進行后剪枝

'''

ifnot_tree(tree):

returntree

# 若沒有測試數(shù)據(jù)則直接返回樹平均值

ifnottest_data:

returncollapse(tree)

ltree,rtree=tree['left'],tree['right']

ifnot_tree(ltree)andnot_tree(rtree):

# 分割數(shù)據(jù)用于測試

ldata,rdata=split_dataset(test_data,tree['feat_idx'],tree['feat_val'])

# 分別計算合并前和合并后的測試數(shù)據(jù)誤差

err_no_merge=(np.sum((np.array(ldata)-ltree)**2)+

np.sum((np.array(rdata)-rtree)**2))

err_merge=np.sum((np.array(test_data)-(ltree+rtree)/2)**2)

iferr_merge

print('merged')

return(ltree+rtree)/2

else:

returntree

tree['left']=postprune(tree['left'],test_data)

tree['right']=postprune(tree['right'],test_data)

returntree

我們看一下不對剛才的樹進行預剪枝而是使用測試數(shù)據(jù)進行后剪枝的效果:

data_test=load_data('ex2test.txt')

pruned_tree=postprune(tree,data_test)

merged

merged

merged

merged

merged

merged

merged

merged

通過輸出可以看到總共進行了8次剪枝操作绪穆，通過把剪枝前和剪枝后的樹可視化對比下看看:

樹的規(guī)模的確是減小了辨泳。

模型樹

上一部分葉子節(jié)點上放的是分割后數(shù)據(jù)的平均值并以他作為滿足條件的樣本的預測值，本部分我們將在葉子節(jié)點上放一個線性模型來做預測霞幅。也就是指我們的樹是由多個線性模型組成的漠吻，顯然會比強行用平均值來建模更有優(yōu)勢。

模型樹使用多個線性函數(shù)來做回歸比用多個平均值組成一棵大樹的模型更有可解釋性

而且線性模型的使用可以使樹的規(guī)模減小司恳，畢竟平均值的覆蓋范圍只是局部的途乃，而線性模型可以覆蓋所有具有線性關系的數(shù)據(jù)。

模型樹也具有更高的預測準確度

創(chuàng)建模型樹

模型樹和回歸樹的思想是完全一致的扔傅，只是在生成葉子節(jié)點的方法以及計算數(shù)據(jù)誤差(不純度)的方式不同耍共。在模型樹里針對一個葉子節(jié)點我們需要使用分割到的數(shù)據(jù)進行線性回歸得到線性回歸系數(shù)而不是簡單的計算數(shù)據(jù)的平均值烫饼。不純度的計算也不是簡單的計算數(shù)據(jù)的方差，而是計算線性模型的殘差平方和试读。

為了能為葉子節(jié)點計算線性模型杠纵，我們還需要實現(xiàn)一個標準線性回歸函數(shù)linear_regression, 相應模型樹的ferr和fleaf的Python實現(xiàn)

deflinear_regression(dataset):

''' 獲取標準線性回歸系數(shù)

'''

dataset=np.matrix(dataset)

# 分割數(shù)據(jù)并添加常數(shù)列

X_ori,y=dataset[:,:-1],dataset[:,-1]

X_ori,y=np.matrix(X_ori),np.matrix(y)

m,n=X_ori.shape

X=np.matrix(np.ones((m,n+1)))

X[:,1:]=X_ori

# 回歸系數(shù)

w=(X.T*X).I*X.T*y

returnw,X,y

deffleaf(dataset):

''' 計算給定數(shù)據(jù)集的線性回歸系數(shù)

'''

w,_,_=linear_regression(dataset)

returnw

defferr(dataset):

''' 對給定數(shù)據(jù)集進行回歸并計算誤差

'''

w,X,y=linear_regression(dataset)

y_prime=X*w

returnnp.var(y_prime-y)

在分段線性數(shù)據(jù)上應用模型樹

本部分使用了事先準備好的分段線性數(shù)據(jù)來構建模型樹，數(shù)據(jù)點可視化如下:

現(xiàn)在我們使用這些數(shù)據(jù)構建一個模型樹:

tree=create_tree(dataset,fleaf,ferr,opt={'err_tolerance':0.1,'n_tolerance':4})

tree

得到的樹結構：

{'feat_idx':0,

'feat_val':0.30440099999999998,

'left':matrix([[3.46877936],

[1.18521743]]),

'right':matrix([[1.69855694e-03],

[1.19647739e+01]])}

可視化:

繪制回歸曲線:

可以通過模型樹看到對于此數(shù)據(jù)只需要兩個分支钩骇，數(shù)的深度也只有2層比藻。

當x<0.304的時候，使用線性模型y=3.47+1.19x來回歸

當x>0.304的時候倘屹，使用線性模型y=0.0017+1.20x來回歸

回歸樹與線性回歸的對比

本部分我們使用標準線性回歸和回歸樹分別對同一組數(shù)據(jù)進行回歸银亲，并使用同一組測試數(shù)據(jù)計算相關系數(shù)(Correlation Coefficient)對兩種模型的回歸效果進行對比。

數(shù)據(jù)我還是使用《Machinie Learning in Action》中的現(xiàn)成數(shù)據(jù)纽匙，數(shù)據(jù)可視化如下:

現(xiàn)在我們分別使用標準線性回歸和回歸樹對該數(shù)據(jù)進行回歸务蝠，并計算模型預測值和測試樣本的相關系數(shù)R2R2(完整代碼見:https://github.com/PytLab/MLBox/blob/master/classification_and_regression_trees/compare.py)

相關系數(shù)計算:

defget_corrcoef(X,Y):

# X Y 的協(xié)方差

cov=np.mean(X*Y)-np.mean(X)*np.mean(Y)

returncov/(np.var(X)*np.var(Y))**0.5

獲得的相關系數(shù):

linear regression correlationcoefficient:0.9434684235674773

regression tree correlationcoefficient:0.9780307932704089

繪制線性回歸和樹回歸的回歸曲線(黃色會樹回歸曲線，紅色會線性回歸):

可見樹回歸方法在預測復雜數(shù)據(jù)的時候會比簡單的線性模型更有效烛缔。

總結

本文對決策樹用于連續(xù)數(shù)值的回歸預測進行了介紹馏段，并實現(xiàn)了回歸樹, 剪枝和模型樹以及相應的樹結構輸出可視化等。對于模型樹也給予了相應的Python實現(xiàn)并針對分段線性數(shù)據(jù)進行了回歸測試践瓷。最后并對回歸樹模型和簡單的標準線性回歸模型進行了對比院喜。

參考

《Machine Learning in Action》

CART分類與回歸樹的原理與實現(xiàn)