線性回歸包含了一些強大的方法，但這些方法建立的模型需要拟合所有的樣本點（局部權重線性回歸除外）。當資料擁有衆多特征并且特征之間關系十分複雜時，建構全局模型的想法就太難了。一種可行的辦法是将資料集切分成很多份易模組化的資料，然後利用線性回歸模組化，如果首次切分後仍然難以拟合線性模型就繼續切分，在這種切分方式下，樹結構和回歸法就很有用。
這裡介紹一種即可用于分類還可以用于回歸的CART樹建構算法。之後引入一個更加進階的模型樹算法，與回歸樹不同，該算法需要在每個葉節點上都建構出一個線性模型。
一、複雜資料的局部性模組化
決策樹是一種貪心算法，它要在給定時間内做出最佳選擇，但是并不關心能否達到全局最優。
之前使用的樹建構算法是ID3，ID3的做法是每次選取目前最佳的特征來分割資料，并按照該特征的所有可能取值來切分，一旦按某特征切分後，該特征在之後的算法執行過程中将不再起作用，這種切分算法過于迅速。另外一種方法是二進制切分法。即每次把資料集切分成兩份。如果資料的某特征值等于切分所要求的值，那麼這些資料就進入樹的左子樹，反之則進入樹的右子樹。
二進制切分法易于對樹建構過程進行調整以處理連續型特征。具體處理方法是：如果特征值大于給定值就進入左子樹，否則就進入右子樹。
二、連續和離散型特征的樹的建構
這裡使用一部字典來存儲樹的資料結構，該字典包含以下4個元素：
待切分的特征、待切分的特征值、右子樹（當不再需要切分的時候，也可以是單個值）、左子樹（與右子樹類似）
CART算法隻做二進制切分，是以這裡可以固定樹的資料結構。樹包含左鍵和右鍵，可以存儲另一顆子樹或者單個值。字典還包含特征和特征值這兩個鍵，它們給出切分算法所有的特征和特征值。
本文将建構兩種樹：第一種是回歸樹，其每個葉節點包含單個值；第二種是模型樹，其每個葉節點包含一個線性方程。
建構樹函數僞代碼：
找到最佳的切分特征：
如果該節點不能再分，将該節點存為葉節點
執行二進制切分
在右子樹調用createTree()方法
在左子樹調用createTree()方法
CART算法的實作代碼：
import numpy as np
#加載資料集
def loadDataSet(filename):
dataSet = []
fp = open(filename)
for line in fp.readlines():
curLine = line.strip().split('\t')
#将每行中的資料映射為浮點數
fltLine = list(map(float,curLine))
dataSet.append(fltLine)
return dataSet
#二值切分
def binSplitDataSet(dataSet, feature, value):
#np.nonzero()函數傳回數組中非零資料的索引值數組
#利用數組過濾得到左子樹集
#傳回左子樹集的第一個樣本，建構回歸樹時每次隻需要傳回集合中的第一條樣本
leftSet = dataSet[np.nonzero(dataSet[:,feature]>value)[],:]
#傳回左子樹矩陣
# leftSet = dataSet[np.nonzero(dataSet[:, feature] > value)[0], :][0]
# 利用數組過濾得到右子樹集
# 傳回右子樹集的第一個樣本
rightSet = dataSet[np.nonzero(dataSet[:, feature] <= value)[],:]
# 傳回右子樹矩陣
# rightSet = dataSet[np.nonzero(dataSet[:, feature] <= value)[0], :][0]
return leftSet,rightSet
三、将CART算法用于回歸
為成功建構以分段常數為葉節點的樹，需要度量出資料的一緻性，事實上，在資料集上計算混亂度是非常簡單的，首先計算所有資料的均值，然後計算每條資料的值到均值的內插補點。為了對正負值同等看待，一般使用絕對值或平方值來代替上述內插補點，上述做法有點類似于統計學中常用的方差計算。唯一不同的是，方差是平方誤差的均值（均方差），二而這裡需要的是平方誤差的總值，總方差可以通過均方差乘以資料集中樣本點的個數來得到。
1.建構樹
回歸樹的切分函數：
#因為在進行二進制劃分時，最後一次劃分的每個子集不一定就隻含有一個資料樣本，大多數情況都是子集中有多個樣本
#但是葉節點值卻隻能為一個，是以在建立葉節點時需要使用函數對葉節點值進行計算并指定，回歸樹中的葉節點值為最終子節樣本目标值的均值
#計算葉節點值的函數
def regLeaf(dataSet):
return np.mean(dataSet[:,-])
def regErr(dataSet):
#傳回此資料集中目标值列的總方差和（均方誤差和*集合樣本數）
return np.var(dataSet[:,-])*np.shape(dataSet)[]
#尋找最佳切分特征及切分值函數
def chooseBestSplit(dataSet,leafType=regLeaf,errType=regErr,ops=(,)):
#擷取參數中的誤差減少限度
tolS = ops[]
#擷取劃分子集最小樣本數量
tolN = ops[]
#資料集劃分停止條件：
#1.劃分子集中的目标值相同，則不需要繼續劃分
if (len(set(dataSet[:,-].T.tolist()[]))==):
return None,leafType(dataSet)
m,n = np.shape(dataSet)
#計算為劃分資料集的總方差和
S = errType(dataSet)
#定義最小方差和為無窮
bestS = np.inf
#初始化最佳特征索引值和最佳劃分值
bestIndex =
bestValue =
#周遊所有特征,資料集中最後一列是目标值，不是特征列
for featIndex in range(n-):
#周遊每一個特征的所有取值
#for splitValue in set(dataSet[:,featIndex]): #python2.x用法
for splitValue in set(dataSet[:,featIndex].T.A.tolist()[]): #python3.x用法
#進行二值劃分
matLeft,matRight = binSplitDataSet(dataSet,featIndex,splitValue)
#如果劃分的資料集樣本數小于指定數，則重新劃分
if ((np.shape(matLeft)[]<tolN) or (np.shape(matRight)[])<tolN):
continue
#計算劃分後的總誤差
newS = errType(matLeft)+errType(matRight)
#判斷是否為最小誤差，如果是，将相應資訊儲存
if newS < bestS:
bestIndex = featIndex
bestValue = splitValue
bestS = newS
#周遊完成之後，判斷另外兩個切分停止條件
#2.劃分後的最小劃分相對與原始誤差和的減小幅度小于1則停止劃分
if (S - bestS) < tolS:
return None,leafType(dataSet)
#3.如果根據選擇出的最佳特征和最佳劃分值劃分的子集樣本數小于一定值，則停止劃分
mat0,mat1 = binSplitDataSet(dataSet,bestIndex,bestValue)
if ((np.shape(mat0)[]<tolN) or (np.shape(mat1)[]<tolN)):
return None,leafType(dataSet)
#如果沒有在之前跳出，則說明可劃分
return bestIndex,bestValue
#建立回歸樹,輸入參數中leafType=regLeaf(指定葉節點值的函數引用),errType=regErr(指定誤差函數的引用)
#ops=(1,4)(ops[0]指定為切分誤差總和與切分後誤差總和的變化停止限度),ops[1]指定切分資料集的最小樣本數量
def createTree(dataSet,leafType=regLeaf,errType=regErr,ops=(,)):
#擷取最佳劃分特征和劃分值
feat,val = chooseBestSplit(dataSet,leafType,errType,ops)
#設定遞歸停止條件
if feat == None:
return val
#定義樹，樹的存儲結構為字典
retTree = {}
retTree['spInd'] = feat
retTree['spVal'] = val
leafSet,rightSet = binSplitDataSet(dataSet,feat,val)
#遞歸建立樹節點
retTree['left'] = createTree(leafSet,leafType,errType,ops)
retTree['right'] = createTree(rightSet,leafType,errType,ops)
return retTree
四、樹剪枝
完成回歸樹的建構後，需要某種措施來檢查建構過程是否得當。樹剪枝技術通過對決策樹剪枝來達到更好的預測效果。
通過降低決策樹的複雜度來避免過拟合的過程稱為剪枝，在函數ChooseBestSplit()中的提前終止條件，實際上是在進行一種所謂的預剪枝操作，另一種形式的剪枝是需要使用測試集和訓練集，稱作後剪枝。
1.後剪枝
使用後剪枝方法需要将資料集分為測試集和訓練集。首先指定參數，使得建構出的樹足夠大、足夠複雜，便于剪枝。接下來進而下找到葉節點，用測試集來判斷這些葉節點合并是否能降低測試誤差，如果是的話就合并。
基于已有的樹切分測試資料：
如果存在任一子集是一棵樹，則在該子集遞歸剪枝過程
計算将目前兩個葉節點合并後的誤差
計算不合并的誤差
如果合并會降低誤差的話，就将葉節點合并
回歸樹剪枝函數：
#後剪紙操作，利用訓練集建立好樹之後。根據測試資料集進行後剪枝處理
#測試輸入對象是否為樹
def isTree(obj):
#樹結構是用python中的字典存儲的，是以隻用判斷該對象類型是否為dict
return type(obj).__name__ == 'dict'
#在進行樹塌陷處理時，需要求得樹節點的平均值
def getMean(tree):
# 如果右子樹是樹的話，求得右子樹平均值,并将此值置為右子樹的值
if (isTree(tree['right'])): tree['right'] = getMean(tree['right'])
#如果左子樹是樹的話，求得左子樹平均值,并将此值置為左子樹的值
if (isTree(tree['left'])): tree['left'] = getMean(tree['left'])
#傳回該節點的平均值
return (tree['left'] + tree['right'])/
#樹剪枝函數
def prune(tree,testSet):
#如果測試集樣本數為空，則對樹進行塌陷處理，傳回樹節點的均值，剪枝到最後測試集空的情況
if (np.shape(testSet)[]==):
return getMean(tree)
#如果測試集不為空，如果左子樹或者右子樹還是樹的話，則對測試集進行切分，将切分資料傳入剪枝函數中對樹結構進行遞歸剪枝
#擷取到下一次遞歸中的測試資料集
if( isTree(tree['right'])or isTree(tree['left']) ):
lSet, rSet = binSplitDataSet(testSet,tree['spInd'],tree['spVal'])
#分别對左右子樹進行剪枝
if (isTree(tree['left'])):
tree['left'] = prune(tree['left'],lSet)
if (isTree(tree['right'])):
tree['right'] = prune(tree['right'],rSet)
#最後一次遞歸進行是否合并判斷,進入最後一次遞歸的條件是傳入樹的左右子樹不在是子樹，而是葉節點
if ((not isTree(tree['left'])) and (not isTree(tree['right']))):
#進行二值劃分
lSet, rSet = binSplitDataSet(testSet, tree['spInd'], tree['spVal'])
#計算沒有合并的誤差和
notMergeErr = sum(np.power(lSet[:,-] - tree['left'],)) + sum(np.power(rSet[:,-] - tree['right'],))
#計算合并的話節點值,已經到了葉節點，是以之間計算平均值
meanNodeNum = (tree['left'] + tree['right'])/
#計算合并後的誤差和
mergeErr = sum(np.power(testSet[:,-] - meanNodeNum,))
#如果合并後的誤差方和減少了，則合并
if mergeErr < notMergeErr:
print("merge")
return meanNodeNum
#否則，傳回該樹
else:
return tree
#最後傳回完成剪枝之後的樹
else:
return tree
五、模型樹
用樹來對資料模組化，除了把葉節點簡單地設定為常數值之外，還有一種方法是把葉節點設定為分段線性函數，這裡所謂的分段線性是指模型由多個線性片段組成。
模型樹的葉節點生成函數：
#在建立樹函數中，葉節點的模式函數和誤差計算函數參數是通過函數引用給出的，模式樹的建構過程與回歸樹的建構過程是一緻的
#隻是模式樹的節點不是數值，而是回歸函數（葉節點模式），誤差計算函數也和回歸樹中誤差計算不一樣，是以模式樹建構隻需要傳入這兩個函數的應用就可實作樹的建構
#對資料集進行标準線性回歸，傳回系數向量X矩陣和Y矩陣
def linearSlove(dataSet):
#dataSet中包含了目标值列,标準線性回歸中需要加入一列1，是為了将截距b的值加入ws向量中一起求出
#擷取資料集的行列大小
m,n = np.shape(dataSet)
#建立m*n大小的全1矩陣,這裡相當于覆寫x矩陣中的最後一列
X = np.mat(np.ones((m,n)))
Y = np.mat(np.ones((m,)))
X[:,:n] = dataSet[:,:n-]
Y = dataSet[:,-]
xtx = X.T*X
if np.linalg.det(xtx) == :
raise NameError("矩陣不可逆")
ws = xtx.I * (X.T*Y)
return ws,X,Y
#葉節點模式函數
def modelLeaf(dataSet):
ws,X,Y = linearSlove(dataSet)
#葉節點模式函數傳回回歸系數向量
return ws
#計算誤差函數
def modelErr(dataSet):
ws, X, Y = linearSlove(dataSet)
#預測
yHat = X * ws
return sum(np.power(Y - yHat,))
六、示例：樹回歸與标準回歸的比較
用樹回歸進行預測的代碼：
#回歸樹預測
def regTreeEval(model,inDat):
return float(model)
#模型樹預測,inDat是單個樣本向量
def modelTreeEval(model,inDat):
n = np.shape(inDat)[]
X = np.mat(np.ones((,n+)))
X[:,:n+] = inDat
return 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 = np.mat(np.zeros((m,)))
#周遊整個樣本集，對每個測試樣本進行預測
for i in range(m):
yHat[i,] = treeForeCast(tree,np.mat(testData[i]),modelEval)
return yHat
注：以上函數測試都在main函數中進行，main函數如下：
if __name__ == "__main__":
#造資料，對二進制劃分函數進行測試
# testMat = np.eye()
# print("testMat:\n",testMat)
# leftSet, rightSet = binSplitDataSet(testMat,,)
# print("leftSet:\n",leftSet)
# print("rightSet:\n",rightSet)
#建立回歸樹,ex00.txt檔案資料
# dataMat = loadDataSet('ex00.txt')
# dataMat = np.mat(dataMat)
# myTree_0 = createTree(dataMat)
# print("myTree_0:\n",myTree_0)
#ex0.txt檔案資料
# dataMat = loadDataSet('ex0.txt')
# dataMat = np.mat(dataMat)
# myTree_1 = createTree(dataMat)
# print("myTree_1:\n", myTree_1)
#後剪枝測試
# dataMat2 = loadDataSet('ex2.txt')
# dataMat2 = np.mat(dataMat2)
# dataMat2Test = loadDataSet('ex2test.txt')
# dataMat2Test = np.mat(dataMat2Test)
# #建構最複雜的樹結構，用來進行後剪枝操作
# myTree_2 = createTree(dataMat2,ops=(,))
# myTree_pruned = prune(myTree_2,dataMat2Test)
# print("myTree_pruned:\n",myTree_pruned)
#模型樹的建構
# dataSet = np.mat(loadDataSet('exp2.txt'))
# myTree_model = createTree(dataSet,modelLeaf,modelErr,(,))
# print("myTree_model:\n",myTree_model)
# trainSet = np.mat(loadDataSet('bikeSpeedVsIq_train.txt'))
# testSet = np.mat(loadDataSet('bikeSpeedVsIq_test.txt'))
#
# #回歸樹預測
# myTree = createTree(trainSet,ops=(,))
# #資料集中最後一列是目标值
# yHat = createForeCast(myTree,testSet[:,])
# corr = np.corrcoef(yHat,testSet[:,],rowvar=)[,]
# print("regTreeCorr:", corr)
# #進行标準線性回歸
# ws,X,Y = linearSlove(trainSet)
# print("ws:",ws)
# yHat = np.zeros((np.shape(testSet)[],))
# for i in range(np.shape(testSet)[]):
# yHat[i] = testSet[i,] * ws[,] + ws[,]
# corr = np.corrcoef(yHat,testSet[:,],rowvar=)[,]
# print("linerCorr:",corr)
#進行模型樹回歸
trainSet = np.mat(loadDataSet('bikeSpeedVsIq_train.txt'))
testSet = np.mat(loadDataSet('bikeSpeedVsIq_test.txt'))
# 回歸樹預測
myTree = createTree(trainSet,modelLeaf,modelErr,ops=(, ))
# 資料集中最後一列是目标值
yHat = createForeCast(myTree, testSet[:, ],modelTreeEval)
corr = np.corrcoef(yHat, testSet[:, ], rowvar=)[, ]
print("modelTreeCorr:", corr)
七、使用Python的Tkinter庫建立GUI及內建Matplotlib和Tkinter
使用Python來建構GUI，這裡使用易于使用的Tkinter，Tkinter的GUI由一些小部件組成。
用于建構樹管理器界面的Tkinter小部件、Matplotlib和Tkinter代碼內建
from numpy import *
from tkinter import *
import treeRegression.treeReg
import matplotlib
#将matplotlib後端設定為TkAgg
matplotlib.use('TkAgg')
#将tkinter和matplotlib關聯起來
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
from matplotlib.figure import Figure
def reDraw(tolS, tolN):
reDraw.f.clf() # 清空畫布
reDraw.a = reDraw.f.add_subplot()
if chkBtnVar.get():
if tolN < : tolN =
myTree = treeRegression.treeReg.createTree(reDraw.rawDat,treeRegression.treeReg.modelLeaf, \
treeRegression.treeReg.modelErr, (tolS, tolN))
yHat = treeRegression.treeReg.createForeCast(myTree, reDraw.testDat, \
treeRegression.treeReg.modelTreeEval)
else:
myTree = treeRegression.treeReg.createTree(reDraw.rawDat, ops=(tolS, tolN))
yHat = treeRegression.treeReg.createForeCast(myTree, reDraw.testDat)
#繪制散點圖
reDraw.a.scatter(reDraw.rawDat[:, ].tolist(), reDraw.rawDat[:, ].tolist(), s=) # use scatter for data set
#繪制連續圖
reDraw.a.plot(reDraw.testDat, yHat, linewidth=) # use plot for yHat
reDraw.canvas.show()
def getInputs():
try:
tolN = int(tolNentry.get())
except:
tolN =
print
"tolN請輸入整數值"
tolNentry.delete(, END)
tolNentry.insert(, '10')
try:
tolS = float(tolSentry.get())
except:
tolS =
print
"tolS請輸入浮點值"
tolSentry.delete(, END)
tolSentry.insert(, '1.0')
return tolN, tolS
def drawNewTree():
tolN, tolS = getInputs() # 從輸入框中獲得輸入值
reDraw(tolS, tolN)
#建立跟部件
root = Tk()
reDraw.f = Figure(figsize=(, ), dpi=) # 建立畫布
reDraw.canvas = FigureCanvasTkAgg(reDraw.f, master=root)
reDraw.canvas.show()
reDraw.canvas.get_tk_widget().grid(row=, columnspan=)
#第二行标簽
Label(root, text="tolN").grid(row=, column=)
tolNentry = Entry(root)
tolNentry.grid(row=, column=)
tolNentry.insert(, '10')
#第二行标簽
Label(root, text="tolS").grid(row=, column=)
tolSentry = Entry(root)
tolSentry.grid(row=, column=)
tolSentry.insert(, '1.0')
#按鈕
Button(root, text="ReDraw", command=drawNewTree).grid(row=, column=, rowspan=)
#複選框變量
chkBtnVar = IntVar()
chkBtn = Checkbutton(root, text="Model Tree", variable=chkBtnVar)
chkBtn.grid(row=, column=, columnspan=)
#擷取變量
reDraw.rawDat = mat(treeRegression.treeReg.loadDataSet('sine.txt'))
reDraw.testDat = arange(min(reDraw.rawDat[:, ]), max(reDraw.rawDat[:, ]), )
reDraw(, )
root.mainloop()
總結：
1.資料集中經常包含一些複雜的互相關系，使得輸入資料和目标變量之間呈現非線性關系。對這些複雜的關系模組化，一種可行的方法是使用樹來對預測值分段，包含分段函數或分段直線。一般采用樹結構來對這種資料模組化哦。如果使用的模型的葉節點是分段常數，那麼這個模型是回歸樹；如果使用的模型的葉節點是線性回歸方程，那麼這個模型是模型樹。
2.CART算法可以用于建構二進制樹并處理離散型或連續型資料的切分，若使用不同的誤差測試，就可以通過CART算法構模組化型樹和回歸樹，該算法建構出的樹會傾向于對資料過拟合，一顆過拟合的樹常常十分複雜，剪枝技術的出現就是為了解決這個問題。
![簡單文檔分類——樸素貝葉斯算法樸素貝葉斯算法簡單文檔分類執行個體步驟總結樸素貝葉斯分類調用(sklearn)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)