树回归源码分析（1）
生活随笔
收集整理的這篇文章主要介紹了
树回归源码分析（1）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
線性回歸包含了強大的方法，但是需要擬合所有的數據集（局部加權線性回歸除外），但是當數據特征復雜時，構建全局模型就難了，況且實際生活很多問題都是非線性的，不可能使用全局線性模型來擬合所有的數據。
現有可以將數據集切分成很多易建模的數據，然后再利用線性回歸技術建模，以就得到了CART——Classification And Regression Tree（分類回歸樹）的樹構建算法，該算法既可以用于分類還可以用于回歸。
二元切分法：即每次把數據集切成兩份。如果數據的某特征值等于切分所要求的值，那么這些數據就進人樹的左子樹，反之則進人樹的右子樹。
使用二元切分法則易于對樹構建過程進行調整以處理連續型特征。具體的處理方法是：如果特征值大于給定值就走左子樹，否則就走右子樹。
CART算法只做二元切分，所以這里可以固定樹的數據結構。樹包含左鍵和右鍵，可以存儲另一棵子樹或者單個值。字典還包含特征和特征值這兩個鍵，它們給出切分算法所有的特征和特征值。
1. CART算法用于回歸
幾點要明確的地方：
- ID3算法會在給定節點時計算數據的混亂度，而連續數值的混亂度的度量用方差（平方誤差的均值），這里用總方差（平方誤差的總值），總方差可以通過均方差乘以數據集中的樣本點的個數來得到。
- 源代碼有錯誤的地方，解決方法：源代碼錯誤修正
運行結果：
mat0: [[ 0. 1. 0. 0.]] mat1: [[ 1. 0. 0. 0.][ 0. 0. 1. 0.][ 0. 0. 0. 1.]] featIndex,splitVal: 0 and 0.302001 featIndex,splitVal: 0 and 0.55299 featIndex,splitVal: 0 and 0.378595 featIndex,splitVal: 0 and 0.406649 featIndex,splitVal: 0 and 0.475976 featIndex,splitVal: 0 and 0.48813 feat, val : 0 and 0.48813 featIndex,splitVal: 0 and 0.936783 featIndex,splitVal: 0 and 0.727098 featIndex,splitVal: 0 and 0.72312 featIndex,splitVal: 0 and 0.645762 featIndex,splitVal: 0 and 0.648675 featIndex,splitVal: 0 and 0.625336 featIndex,splitVal: 0 and 0.622398 featIndex,splitVal: 0 and 0.620599 back from here 2 .. feat, val : None and 1.01809676724 back creatTree.. featIndex,splitVal: 0 and 0.302001 featIndex,splitVal: 0 and 0.347837 featIndex,splitVal: 0 and 0.346986 featIndex,splitVal: 0 and 0.188218 featIndex,splitVal: 0 and 0.048014 featIndex,splitVal: 0 and 0.343479 back from here 2 .. feat, val : None and -0.0446502857143 back creatTree.. {'spInd': 0, 'spVal': 0.48813, 'right': -0.044650285714285719, 'left': 1.0180967672413792}可以由運行結果看出代碼的具體運行過程：
- 葉節點是相應的目標數據集的均值
- 注意幾個切分停止得條件和返回葉節點
2. 樹剪枝
通過降低決策樹的復雜度來避免過擬合的過程稱為剪枝，在上面的提前終止條件實際是一種預剪枝的操作。另一種是使用測試集和訓練集，稱為后剪枝。
- 樹構建算法其實對輸入的tolS和tolN非常敏感，也就是對提前終止的人為輸入參數，其中tolS對誤差的數量級十分敏感，所以需要我們手動調節參數，但是通過不斷修改停止條件來得到合理的結果并不是很好的辦法，甚至有時候我們不確定到底我們需要什么樣的結果，于是有了通過測試集來對樹進行剪枝，也就避免了用戶指定參數。
后剪枝
函數prune（）的偽代碼如下：
基于已有的樹切分測試數據：
- 如果存在任一子集是一棵樹，則在該子集遞歸剪枝過程
- 計算將當前兩個葉節點合并后的誤差
- 計算不合并的誤差
- 如果合并會降低誤差的話，就將葉節點合并
運行結果：
merging merging merging merging merging merging merging merging merging merging merging merging merging ... 'spVal': 0.965969, 'right': {'spInd': 0, 'spVal': 0.956951, 'right': 111.2013225, 'left': {'spInd': 0, 'spVal': 0.958512, 'right': 135.83701300000001, 'left': {'spInd': 0, 'spVal': 0.960398, 'right': 123.559747, 'left': 112.386764}}}, 'left': 92.523991499999994}}}}可以看出大量的節點已經被剪枝掉了，雖然看著還是那么多的節點，但是確實已經減少了很多了，一般情況下為了尋求最佳模型可以同時使用預剪枝和后剪枝兩種技術。
注意：
- 其中的塌陷處理，自上而下的遍歷樹到葉節點為止，如果找到兩個葉節點則計算它們的平均值，返回整個樹的平均值。
- 注意其中的遞歸調用剪枝處理，對數據結構的理解有所要求。
3. 模型樹
簡單來說就是把原來的葉節點由常數值變為分段線性函數，所謂的分段線性就是指模型由多個線性片段組成。也就是在某些情況下，分段線性要比很多節點組成的一顆大樹更容易解釋。
- 模型樹的可解釋性優于回歸樹的，另外模型樹也具有更高的預測準確度。
- 前面用于回歸樹的誤差計算方法這里不能再用。稍加變化，對于給定的數據集，應該先用線性的模型來對它進行擬合，然后計算真實的目標值與模型預測值間的差值。最后將這些差值的平方求和就得到了所需的誤差。
在CART算法用于回歸代碼中加入下面的函數，并且把主函數改為如下：
# 模型樹的葉節點生成函數 def linearSolve(dataSet): m,n = shape(dataSet)X = mat(ones((m,n))); Y = mat(ones((m,1))) X[:,1:n] = dataSet[:,0:n-1]; Y = dataSet[:,-1] # 將數據集格式化成目標變量和自變量 xTx = X.T*Xif linalg.det(xTx) == 0.0: # 這個矩陣是奇異的，不能求逆raise NameError('This matrix is singular, cannot do inverse,\n\try increasing the second value of ops')ws = xTx.I * (X.T * Y) # 線性回歸的系數return ws,X,Ydef modelLeaf(dataSet): # 生成葉節點模型ws,X,Y = linearSolve(dataSet)return ws # 返回回歸系數def modelErr(dataSet):ws,X,Y = linearSolve(dataSet)yHat = X * wsreturn sum(power(Y - yHat,2)) # 在給定數據集上計算誤差，返回平方誤差# 主函數# 模型樹 myMat2=mat(loadDataSet('exp2.txt')) modelTree=createTree(myMat2, modelLeaf,modelErr,(1,10)) print '模型樹：',modelTree運行結果：
模型樹： {'spInd': 0, 'spVal': 0.285477, 'right': matrix([[ 3.46877936],[ 1.18521743]]), 'left': matrix([[ 1.69855694e-03],[ 1.19647739e+01]])}由運行的結果可以看出：
分段線性生成的模型：
y=3.468+1.18521743x
y=0.0016985+11.96477x
而數據是由模型：
y=3.5+1.0x
y=0.0+12x再加上高斯噪聲生成的。
兩個模型已經非常接近了。
4. 樹回歸的比較
模型樹、回歸樹以及第8章里的其他模型，哪一種模型更好呢？一個比較客觀的方法是計算相關系數，也稱為R2值。該相關系數可以通過調用Numpy庫中的命令corrcoef(yHat,y,rowvar)來求解。
# -*- coding: utf-8 -*- """ Created on Fri Nov 03 10:35:00 2017""" from numpy import *# 加載數據函數 def loadDataSet(fileName): dataMat = [] fr = open(fileName)for line in fr.readlines():curLine = line.strip().split('\t') # 讀取以tab鍵為分割符的文件fltLine = map(float,curLine) # 將每行映射為浮點數dataMat.append(fltLine) # 把所有的數據保存到一起return dataMat# 二元切分數據集 def binSplitDataSet(dataSet, feature, value): # 三個參數：數據集合，待切分的特征，和該特征的某個值mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:] # 數組過濾，mat0是特征數列中大于value的所有樣本行mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:] # 得到和feature相對應的滿足要求的樣本return mat0,mat1 # 返回兩個子集，分別是針對某特征列劃分的不同樣本集# 生成葉節點 def regLeaf(dataSet): return mean(dataSet[:,-1]) # 在回歸樹種返回目標變量的均值# 誤差估計函數，計算連續值的混亂度 def regErr(dataSet): # var()均方差函數，要返回總方差，所以要用均方差乘以數據集中的樣本個數return var(dataSet[:,-1]) * shape(dataSet)[0] # 用最佳方式切分數據集和生成相應的葉節點。leafType，errType是對函數的引用 def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):tolS = ops[0]; tolN = ops[1] # tolS容許的誤差下降值，tolN切分的最少樣本數if len(set(dataSet[:,-1].T.tolist()[0])) == 1: # 如果特征數目只剩一個,就不再切分，直接返回print 'back from here 1 ..'return None, leafType(dataSet)m,n = shape(dataSet) # 當前數據集的大小S = errType(dataSet) # 計算誤差，s用于和新切分誤差對比bestS = inf; bestIndex = 0; bestValue = 0 for featIndex in range(n-1): # 遍歷所有的特征，除了最后一個for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]): # 針對每個特征，在所有樣本中查看不同的特征值 mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal) # 將數據集切分兩份 if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): # 切分的最少樣本數 continue newS = errType(mat0) + errType(mat1) # 計算切分的總方差 if newS < bestS: print 'featIndex,splitVal:',featIndex,'and', splitValbestIndex = featIndex # 如果新的總方差小于當前的方差，則返回特征索引和切分特征值bestValue = splitValbestS = newS if (S - bestS) < tolS: # 如果容錯的誤差下降值變化不大，就停止切分，直接創造葉節點print 'back from here 2 ..'return None, leafType(dataSet) mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): # 如果切分的數據集很小則退出直接創造葉節點print 'back from here 3 ..'return None, leafType(dataSet)return bestIndex,bestValue # 如果所有的提前終止條件都不滿足，就返回切分特征和特征值# 找到數據的最佳二元切分方式 def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)): # ops是一個包含樹構建所需的參數元組# 把數據集分成兩部分，如果滿足停止條件返回None和某類模型的值# 滿足停止條件：feat是None，val是某類模型的值feat, val = chooseBestSplit(dataSet, leafType, errType, ops)print 'feat, val :',feat, 'and',valif feat == None:print 'back creatTree..'return val # 回歸樹：模型是常數，模型樹：模型是線性方程 retTree = {} retTree['spInd'] = featretTree['spVal'] = vallSet, rSet = binSplitDataSet(dataSet, feat, val) # 不滿足停止條件時，lSet, rSet是兩個數據集retTree['left'] = createTree(lSet, leafType, errType, ops) # 遞歸調用createTree()函數retTree['right'] = createTree(rSet, leafType, errType, ops)return retTree # 模型樹的葉節點生成函數 def linearSolve(dataSet): m,n = shape(dataSet)X = mat(ones((m,n))); Y = mat(ones((m,1))) X[:,1:n] = dataSet[:,0:n-1]; Y = dataSet[:,-1] # 將數據集格式化成目標變量和自變量 xTx = X.T*Xif linalg.det(xTx) == 0.0: # 這個矩陣是奇異的，不能求逆raise NameError('This matrix is singular, cannot do inverse,\n\try increasing the second value of ops')ws = xTx.I * (X.T * Y) # 線性回歸的系數return ws,X,Y# 生成葉節點模型,返回回歸系數 def modelLeaf(dataSet): ws,X,Y = linearSolve(dataSet)return ws # 在給定數據集上計算誤差，返回平方誤差 def modelErr(dataSet):ws,X,Y = linearSolve(dataSet)yHat = X * wsreturn sum(power(Y - yHat,2)) def isTree(obj):return (type(obj).__name__=='dict')# 對回歸樹節點進行預測 def regTreeEval(model, inDat):return float(model) # 返回樹預測的值# 對模型樹節點預測 def modelTreeEval(model, inDat):n = shape(inDat)[1] # 格式化處理X = mat(ones((1,n+1))) # 在原數據矩陣上增加第0列X[:,1:n+1]=inDatreturn float(X*model)# 自頂向下的遍歷整棵樹，直到命中葉節點為止 def treeForeCast(tree, inData, modelEval=regTreeEval):if not isTree(tree): # 判斷是否是樹字典，如果不是就返回return modelEval(tree, inData)if inData[tree['spInd']] > tree['spVal']:if isTree(tree['left']): return treeForeCast(tree['left'], inData, modelEval)else: return modelEval(tree['left'], inData)else:if isTree(tree['right']): return treeForeCast(tree['right'], inData, modelEval)else: return modelEval(tree['right'], inData)def createForeCast(tree, testData, modelEval=regTreeEval):m=len(testData)yHat = mat(zeros((m,1)))for i in range(m):yHat[i,0] = treeForeCast(tree, mat(testData[i]), modelEval)return yHat# 利用訓練數據構造回歸樹 trainMat=mat(loadDataSet('bikeSpeedVsIq_train.txt')) testMat=mat(loadDataSet('bikeSpeedVsIq_test.txt')) myTree=createTree(trainMat,ops=(1,20)) # 利用訓練數據構造回歸樹 yHat=createForeCast(myTree, testMat[:,0]) coefficient_regtree=corrcoef(yHat,testMat[:,1],rowvar=0)[0,1]# 利用訓練數據構造模型樹 myTree=createTree(trainMat,modelLeaf,modelErr,ops=(1,20)) # 利用訓練數據構造回歸樹 yHat=createForeCast(myTree, testMat[:,0],modelTreeEval) coefficient_modeltree=corrcoef(yHat,testMat[:,1],rowvar=0)[0,1]print 'regtree coefficient：',coefficient_regtree print 'modeltree coefficient：',coefficient_modeltree運行結果：
... regtree coefficient： 0.964085231822 modeltree coefficient： 0.976041219138我們知道，R2的值越接近1.0越好，所以從上面的結果可以看出模型樹的結果比回歸樹的要好，而線性回歸的效果還不如回歸樹。
總結
以上是生活随笔為你收集整理的树回归源码分析（1）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 机器学习实战_09_树回归_源代码错误修
- 下一篇： 温柔的谎言杨桃（说一说温柔的谎言杨桃的简