• • 第九章 樹回歸
    • 9.1 CART（Classification And Regression Trees）算法用于回歸
      • 9.1.1 用CART算法選擇最佳分類特征
      • 9.1.2 利用所選的兩個變量創建回歸樹
    • 9.2 樹剪枝
      • 9.2.1 預剪枝
      • 9.2.2 后剪枝
    • 9.3 模型樹
    • 9.3 總結

第九章 樹回歸

第三章使用決策樹進行分類，其不斷將數據切分為小數據，直到目標變量完全相同，或者數據不能再分為止，決策樹是一種貪心算法，要在給定的時間內做出最佳選擇，但并不關心能否達到全局最優。

9.1 CART（Classification And Regression Trees）算法用于回歸

CART算法：
CART算法正好適用于連續型特征。CART算法使用二元切分法來處理連續型變量。而使用二元切分法則易于對樹構建過程進行調整以處理連續型特征。具體的處理方法是：如果特征值大于給定值就走左子樹，否則就走右子樹。

CART算法有兩步：

• 決策樹生成：遞歸地構建二叉決策樹的過程，基于訓練數據集生成決策樹，生成的決策樹要盡量大；自上而下從根開始建立節點，在每個節點處要選擇一個最好的屬性來分裂，使得子節點中的訓練集盡量的純。不同的算法使用不同的指標來定義”最好”：
• 決策樹剪枝：用驗證數據集對已生成的樹進行剪枝并選擇最優子樹，這時損失函數最小作為剪枝的標準。
  決策樹剪枝我們先不管，我們看下決策樹生成。

在決策樹的文章中，我們先根據信息熵的計算找到最佳特征切分數據集構建決策樹。CART算法的決策樹生成也是如此，實現過程如下：

• 使用CART算法選擇特征
• 根據特征切分數據集合
• 構建樹

根據特征切分數據集合。編寫代碼如下：

import numpy as npdef binSplitDataSet(dataSet, feature, value):"""根據特征切分數據集合:param dataSet: 數據集合:param feature: 帶切分的特征:param value: 該特征的值:return:mat0：切分的數據集合0mat1：切分的數據集合1"""# np.nonzero(a)，返回數組a中非零元素的索引值數組# np.nonzero(dataSet[:, feature] > value)[0]=1，# 下面一行代碼表示mat0=dataSet[1,:]即第一行所有列mat0 = dataSet[np.nonzero(dataSet[:, feature] > value)[0], :]# np.nonzero(dataSet[:, feature] <= value)[0]，表示取第一列中小于0.5的數的索引值，# 下面代碼表示mat0=dataSet[1,:]即第二、三、四行所有列mat1 = dataSet[np.nonzero(dataSet[:, feature] <= value)[0], :]return mat0, mat1if __name__ == '__main__':testMat = np.mat(np.eye(4))mat0, mat1 = binSplitDataSet(testMat, 1, 0.5)print('原始集合：\n', testMat)print('mat0:\n', mat0)print('mat1:\n', mat1)

結果：

根據是否大于0.5的規則進行切分

9.1.1 用CART算法選擇最佳分類特征

防止過擬合：

• tolS：控制誤差變化限制
• tolN：切分特征最少樣本數

上述兩個參數是為了防止過擬合，提前設置終止條件，實際上是在進行一種所謂的預剪枝。

一、數據集可視化代碼：

數據集：ex00.txt

import matplotlib.pyplot as plt import numpy as npdef loadDataSet(fileName):"""函數說明:加載數據Parameters:fileName - 文件名Returns:dataMat - 數據矩陣"""dataMat = []fr = open(fileName)for line in fr.readlines():curLine = line.strip().split('\t')fltLine = list(map(float, curLine)) #轉化為float類型dataMat.append(fltLine)return dataMatdef plotDataSet(filename):"""函數說明:繪制數據集Parameters:filename - 文件名Returns:無"""dataMat = loadDataSet(filename) #加載數據集n = len(dataMat) #數據個數xcord = []; ycord = [] #樣本點for i in range(n):xcord.append(dataMat[i][0]); ycord.append(dataMat[i][1]) #樣本點fig = plt.figure()ax = fig.add_subplot(111) #添加subplotax.scatter(xcord, ycord, s = 20, c = 'blue',alpha = .5) #繪制樣本點plt.title('DataSet') #繪制titleplt.xlabel('X')plt.show()if __name__ == '__main__':filename = 'ex00.txt'plotDataSet(filename)

結果：

二、利用該數據集測試CART算法代碼

#-*- coding:utf-8 -*- import numpy as npdef loadDataSet(fileName):"""函數說明:加載數據Parameters:fileName - 文件名Returns:dataMat - 數據矩陣"""dataMat = []fr = open(fileName)for line in fr.readlines():curLine = line.strip().split('\t')fltLine = list(map(float, curLine)) #轉化為float類型dataMat.append(fltLine)return dataMatdef binSplitDataSet(dataSet, feature, value):"""函數說明:根據特征切分數據集合Parameters:dataSet - 數據集合feature - 帶切分的特征value - 該特征的值Returns:mat0 - 切分的數據集合0mat1 - 切分的數據集合1"""mat0 = dataSet[np.nonzero(dataSet[:,feature] > value)[0],:]mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]return mat0, mat1 def regLeaf(dataSet):"""函數說明:生成葉結點Parameters:dataSet - 數據集合Returns:目標變量的均值"""return np.mean(dataSet[:,-1]) def regErr(dataSet):"""函數說明:誤差估計函數Parameters:dataSet - 數據集合Returns:目標變量的總方差"""return np.var(dataSet[:,-1]) * np.shape(dataSet)[0]def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops = (1,4)):"""函數說明:找到數據的最佳二元切分方式函數Parameters:dataSet - 數據集合leafType - 生成葉結點regErr - 誤差估計函數ops - 用戶定義的參數構成的元組Returns:bestIndex - 最佳切分特征bestValue - 最佳特征值"""import types#tolS允許的誤差下降值,tolN切分的最少樣本數tolS = ops[0]; tolN = ops[1]#如果當前所有值相等,則退出。(根據set的特性)if len(set(dataSet[:,-1].T.tolist()[0])) == 1:return None, leafType(dataSet)#統計數據集合的行m和列nm, n = np.shape(dataSet)#默認最后一個特征為最佳切分特征,計算其誤差估計S = errType(dataSet)#分別為最佳誤差,最佳特征切分的索引值,最佳特征值bestS = float('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)#如果數據少于tolN,則退出if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue#計算誤差估計newS = errType(mat0) + errType(mat1)#如果誤差估計更小,則更新特征索引值和特征值if newS < bestS:bestIndex = featIndexbestValue = splitValbestS = newS#如果誤差減少不大則退出if (S - bestS) < tolS:return None, leafType(dataSet)#根據最佳的切分特征和特征值切分數據集合mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)#如果切分出的數據集很小則退出if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):return None, leafType(dataSet)#返回最佳切分特征和特征值return bestIndex, bestValueif __name__ == '__main__':myDat = loadDataSet('ex00.txt')myMat = np.mat(myDat)feat, val = chooseBestSplit(myMat, regLeaf, regErr, (1, 4))print(feat)print(val)

結果：

0 0.48813

分析：

切分的最佳特征為第一列特征，最佳切分特征值為0.48813

選擇標準：選取使得誤差最小化的特征

9.1.2 利用所選的兩個變量創建回歸樹

import numpy as npdef loadDataSet(fileName):"""函數說明:加載數據Parameters:fileName - 文件名Returns:dataMat - 數據矩陣"""dataMat = []fr = open(fileName)for line in fr.readlines():curLine = line.strip().split('\t')fltLine = list(map(float, curLine)) #轉化為float類型dataMat.append(fltLine)return dataMatdef binSplitDataSet(dataSet, feature, value):"""函數說明:根據特征切分數據集合Parameters:dataSet - 數據集合feature - 帶切分的特征value - 該特征的值Returns:mat0 - 切分的數據集合0mat1 - 切分的數據集合1Website:http://www.cuijiahua.com/Modify:2017-12-12"""mat0 = dataSet[np.nonzero(dataSet[:,feature] > value)[0],:]mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]return mat0, mat1def regLeaf(dataSet):"""函數說明:生成葉結點Parameters:dataSet - 數據集合Returns:目標變量的均值"""return np.mean(dataSet[:,-1])def regErr(dataSet):"""函數說明:誤差估計函數Parameters:dataSet - 數據集合Returns:目標變量的總方差"""return np.var(dataSet[:,-1]) * np.shape(dataSet)[0]def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops = (1,4)):"""函數說明:找到數據的最佳二元切分方式函數Parameters:dataSet - 數據集合leafType - 生成葉結點regErr - 誤差估計函數ops - 用戶定義的參數構成的元組Returns:bestIndex - 最佳切分特征bestValue - 最佳特征值"""import types#tolS允許的誤差下降值,tolN切分的最少樣本數tolS = ops[0]; tolN = ops[1]#如果當前所有值相等,則退出。(根據set的特性)if len(set(dataSet[:,-1].T.tolist()[0])) == 1:return None, leafType(dataSet)#統計數據集合的行m和列nm, n = np.shape(dataSet)#默認最后一個特征為最佳切分特征,計算其誤差估計S = errType(dataSet)#分別為最佳誤差,最佳特征切分的索引值,最佳特征值bestS = float('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)#如果數據少于tolN,則退出if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue#計算誤差估計newS = errType(mat0) + errType(mat1)#如果誤差估計更小,則更新特征索引值和特征值if newS < bestS:bestIndex = featIndexbestValue = splitValbestS = newS#如果誤差減少不大則退出if (S - bestS) < tolS:return None, leafType(dataSet)#根據最佳的切分特征和特征值切分數據集合mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)#如果切分出的數據集很小則退出if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):return None, leafType(dataSet)#返回最佳切分特征和特征值return bestIndex, bestValuedef createTree(dataSet, leafType = regLeaf, errType = regErr, ops = (1, 4)):"""函數說明:樹構建函數Parameters:dataSet - 數據集合leafType - 建立葉結點的函數errType - 誤差計算函數ops - 包含樹構建所有其他參數的元組Returns:retTree - 構建的回歸樹"""#選擇最佳切分特征和特征值feat, val = chooseBestSplit(dataSet, leafType, errType, ops)#r如果沒有特征,則返回特征值if feat == None: return val#回歸樹retTree = {}retTree['spInd'] = featretTree['spVal'] = val#分成左數據集和右數據集lSet, rSet = binSplitDataSet(dataSet, feat, val)#創建左子樹和右子樹retTree['left'] = createTree(lSet, leafType, errType, ops)retTree['right'] = createTree(rSet, leafType, errType, ops)return retTree if __name__ == '__main__':myDat = loadDataSet('ex00.txt')myMat = np.mat(myDat)print(createTree(myMat))

結果：

{'spVal': 0.48813, 'right': -0.044650285714285719, 'spInd': 0, 'left': 1.0180967672413792}

分析：

該樹只有兩個葉結點。

利用復雜數據進行實驗：
數據集：ex0.txt

import matplotlib.pyplot as plt import numpy as npdef loadDataSet(fileName):"""函數說明:加載數據Parameters:fileName - 文件名Returns:dataMat - 數據矩陣"""dataMat = []fr = open(fileName)for line in fr.readlines():curLine = line.strip().split('\t')fltLine = list(map(float, curLine)) #轉化為float類型dataMat.append(fltLine)return dataMatdef plotDataSet(filename):"""函數說明:繪制數據集Parameters:filename - 文件名Returns:無"""dataMat = loadDataSet(filename) #加載數據集n = len(dataMat) #數據個數xcord = []; ycord = [] #樣本點for i in range(n):xcord.append(dataMat[i][1]); ycord.append(dataMat[i][2]) #樣本點fig = plt.figure()ax = fig.add_subplot(111) #添加subplotax.scatter(xcord, ycord, s = 20, c = 'blue',alpha = .5) #繪制樣本點plt.title('DataSet') #繪制titleplt.xlabel('X')plt.show()if __name__ == '__main__':filename = 'ex0.txt'plotDataSet(filename)

結果：

9.2 樹剪枝

一棵樹如果結點過多，表明該模型可能對數據進行了“過擬合”，如何判斷是否過擬合，前面已經介紹了使用測試集上的某種交叉驗證的方法來發現過擬合，決策樹一樣。

通過降低樹的復雜度來避免過擬合的過程稱為剪枝（pruning）。我們也已經提到，設置tolS和tolN就是一種預剪枝操作。另一種形式的剪枝需要使用測試集和訓練集，稱作后剪枝（postpruning）。本節將分析后剪枝的有效性，但首先來看一下預剪枝的不足之處。

9.2.1 預剪枝

利用ex2.txt實驗結果：

雖然和上圖很相似，但是y的數量級差了很多倍，數據分布相似，但是構建出的樹有很多葉結點。產生這個現象的原因在于，停止條件tolS對誤差的數量級十分敏感。如果在選項中花費時間并對上述誤差容忍度取平均值，或許也能得到僅有兩個葉結點組成的樹，可以看到，將參數tolS修改為10000后，構建的樹就是只有兩個葉結點。然而，顯然這個值，需要我們經過不斷測試得來，顯然通過不斷修改停止條件來得到合理結果并不是很好的辦法。事實上，我們常常甚至不確定到底需要尋找什么樣的結果。因為對于一個很多維度的數據集，你也不知道構建的樹需要多少個葉結點。

可見，預剪枝有很大的局限性。接下來，我們討論后剪枝，即利用測試集來對樹進行剪枝。由于不需要用戶指定參數，后剪枝是一個更理想化的剪枝方法。

9.2.2 后剪枝

使用后剪枝方法需要將數據集分成測試集和訓練集。首先指定參數，使得構建出的樹足夠大、足夠復雜，便于剪枝。接下來從上而下找到葉結點，用測試集來判斷這些葉結點合并是否能降低測試集誤差。如果是的話就合并。后剪枝可能不如預剪枝有效。一般地，為了尋求最佳模型可以同時使用兩種剪枝技術。

9.3 模型樹

用樹來對數據建模，除了把葉節點簡單的設定為常數值外，還有一種方法是把葉節點設定為分段線性函數，即模型由多個線性片段組成。

很顯然，兩條直線比很多節點組成的一棵大樹更容易解釋。

考慮圖9-4中的數據。如果使用兩條直線擬合是否比使用一組常數來建模好呢？答案顯而易見。可以設計兩條分別從0.0~0.3、從0.3~1.0的直線，于是就可以得到兩個線性模型。因為數據集里的一部分數據（0.0~0.3)以某個線性模型建模，而另一部分數據（0.3~1.0)則以另一個線性模型建模，因此我們說采用了所謂的分段線性模型。

模型樹的優于回歸樹的優點：

1）可解釋性
2）有更高的預測準確度

下面將利用樹生成算法對數據進行切分，且每份切分數據都能很容易被線性模型所表示。

該算法的關鍵在于誤差的計算，應該怎樣計算誤差呢？

前面用于回歸樹的誤差計算方法這里不能再用。稍加變化，對于給定的數據集，應該先用線性的模型來對它進行擬合，然后計算真實的目標值與模型預測值間的差值。最后將這些差值的平方求和就得到了所需的誤差。

9.3 總結

1）CART算法可以用于構建二元樹并處理離散型或連續型數據的切分。若使用不同的誤差準則，就可以通過CART算法構建模型樹和回歸樹。
2）一顆過擬合的樹常常十分復雜，剪枝技術的出現就是為了解決這個問題。兩種剪枝方法分別是預剪枝和后剪枝，預剪枝更有效但需要用戶定義一些參數。

總結

以上是生活随笔為你收集整理的机器学习实战（九）树回归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。