當(dāng)數(shù)據(jù)擁有眾多特征并且特征之間關(guān)系十分復(fù)雜時(shí)，構(gòu)建全局模型的想法就顯得太難了蹄咖。實(shí)際生活中很多問(wèn)題都是非線性的，不可能使用全局性模型來(lái)擬合任何數(shù)據(jù)钢拧。
一種可行的方法就是將數(shù)據(jù)集切分成很多易建模的數(shù)據(jù)青扔，然后再利用線性回歸技術(shù)來(lái)建模锅纺。本章介紹一種新的叫做CART的樹(shù)構(gòu)建算法，該算法可用于分類也可用于回歸。
復(fù)雜數(shù)據(jù)的局部性建模
樹(shù)構(gòu)建算法：
- ID3 每次選取當(dāng)前最佳的特征來(lái)分割數(shù)據(jù)，并按照該特征的所有可能取值來(lái)切分拗秘。如果一個(gè)特征有4個(gè)取值，那么數(shù)據(jù)將被切分成4份祈惶。一旦按某特征切分后雕旨，該特征在之后的算法執(zhí)行中將不會(huì)再起作用扮匠。
- 二分法 每次把數(shù)據(jù)切成兩份。如果特征值大于給定值就走左子樹(shù)奸腺，否則就走右子樹(shù)餐禁。
CART使用二元切分來(lái)處理連續(xù)型變量。對(duì)CART稍作修改就可以處理回歸問(wèn)題突照。
在樹(shù)的構(gòu)建過(guò)程中，需要解決多種類型數(shù)據(jù)的存儲(chǔ)問(wèn)題氧吐。這里使用字典來(lái)存儲(chǔ)樹(shù)的數(shù)據(jù)結(jié)構(gòu)讹蘑，字典包括1、待切分的特征 2筑舅、待切分的特征值座慰。 3、右子樹(shù)翠拣。當(dāng)不再需要切分的時(shí)候也可以是單個(gè)值版仔。4、左子樹(shù)误墓。 與右子樹(shù)類似蛮粮。
'''
創(chuàng)建樹(shù)節(jié)點(diǎn)
'''
class treeNode():
def __init__(self,feat,val,right,left):
self.featureToSplitOn = feat
self.valueOfSpit = val
self.rightBranch = right
self.leftBranch = left
'''
加載數(shù)據(jù)
'''
def loadDataSet(fileName):
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
fltLine = list(map(float,curLine))
dataMat.append(fltLine)
return dataMat
'''
構(gòu)建樹(shù)
dataSet 數(shù)據(jù)集
leafType 建立葉子節(jié)點(diǎn)的函數(shù)
errType 代表誤差計(jì)算函數(shù)
ops 代表樹(shù)構(gòu)建所需其他參數(shù)的元組
'''
def createTree(dataSet,leafType = regLeaf,errType = regErr,ops=(1,4)):
feat,val = chooseBestSplit(dataSet,leafType,errType,ops)
if feat == None:return val
retTree = {}
retTree['spInd'] = feat
retTree['spVal'] = val
lSet,rSet = bindSplitDataSet(dataSet,feat,val)
retTree['left'] = createTree(lSet,leafType,errType,ops)
retTree['right'] = createTree(rSet,leafType,errType,ops)
return retTree
'''
負(fù)責(zé)生成葉子節(jié)點(diǎn) 當(dāng)chooseBestSplit確定不再對(duì)數(shù)據(jù)進(jìn)行切分時(shí)，調(diào)用子方法得到葉子節(jié)點(diǎn)
該函數(shù)就是目標(biāo)變量的均值
'''
def regLeaf(dataSet):
return mean(dataSet[:,-1])
'''
在給定數(shù)據(jù)上計(jì)算目標(biāo)變量的平均誤差
'''
def regErr(dataSet):
return var(dataSet[:,-1]) * shape(dataSet)[0]
'''
三個(gè)參數(shù) 分別為數(shù)據(jù)集合谜慌，待切分的特征和該特診的某個(gè)值
'''
def bindSplitDataSet(dataSet,feature,value):
mats0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:]
mats1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:]
mat0 = [];mat1 = []
if len(mats0) > 1:mat0 = mats0
if len(mats1) > 1:mat1 = mats1
return mat0,mat1
'''
找到最佳二元切分
dataSet 數(shù)據(jù)集
leafType 建立葉子節(jié)點(diǎn)的函數(shù)
errType 代表誤差計(jì)算函數(shù)
ops 代表樹(shù)構(gòu)建所需其他參數(shù)的元組
'''
def chooseBestSplit(dataSet,leafType=regLeaf,errType = regErr,ops=(1,4)):
#ops的兩個(gè)值 用于控制函數(shù)的退出機(jī)制
#tolS容許的誤差下降值
#tolN切分的最好樣本
tolS = ops[0];tolN = ops[1]
#如果所有值相等則退出 如果該數(shù)目為1 就不需要再切分了
if len(set(dataSet[:,-1].T.tolist()[0])) == 1:
return None,leafType(dataSet)
m,n = shape(dataSet)
S = errType(dataSet)
bestS = inf; bestIndx = 0; bestValue = 0
# 在所有可能的特征和可能取值上遍歷
#最佳的切分就是切分后能達(dá)到最低誤差的切分
for featIndex in range(n-1):
#書(shū)中源代碼有錯(cuò)誤然想。
for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]):
mat0,mat1 = bindSplitDataSet(dataSet,featIndex,splitVal)
if(shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):continue
newS = errType(mat0) + errType(mat1)
if newS < bestS:
bestIndx = featIndex
bestValue = splitVal
bestS = newS
#如果誤差減少不大則退出
if(S - bestS) < tolS:
return None,leafType(dataSet)
mat0,mat1 = bindSplitDataSet(dataSet,bestIndx,bestValue)
#如果切分的數(shù)據(jù)小則退出
if(shape(mat0)[0] < tolN) or (shape(mat1)[0]<tolN):
return None,leafType(dataSet)
return bestIndx,bestValue
if __name__ == '__main__':
myDat = loadDataSet('eex00.txt')
myMat = mat(myDat)
retTree = createTree(myMat)
print(retTree)
>>> {'left': 1.0180967672413792, 'spVal': 0.48813, 'spInd': 0, 'right': -0.044650285714285719}
if __name__ == '__main__':
myDat = loadDataSet('regTreesex0.txt')
myMat = mat(myDat)
retTree = createTree(myMat)
print(retTree)
>>> {'right': {'right': -0.023838155555555553, 'left': 1.0289583666666666, 'spInd': 1, 'spVal': 0.197834},
'left': {'right': 1.980035071428571, 'left': {'right': 2.9836209534883724, 'left': 3.9871631999999999, 'spInd': 1, 'spVal': 0.797583}, 'spInd': 1, 'spVal': 0.582002}, 'spInd': 1, 'spVal': 0.39435}
