當(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)建算法，該算法可用于分類(lèi)也可用于回歸。

復(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ò)程中，需要解決多種類(lèi)型數(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ù)類(lèi)似。

'''
創(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}