第9章 樹回歸

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>

預(yù)測(cè)數(shù)值型數(shù)據(jù)回歸首頁(yè)

樹回歸 概述

我們本章介紹 CART(Classification And Regression Trees彬檀， 分類回歸樹) 的樹構(gòu)建算法剧蚣。該算法既可以用于分類還可以用于回歸。

樹回歸 場(chǎng)景

我們?cè)诘?8 章中介紹了線性回歸的一些強(qiáng)大的方法筑辨，但這些方法創(chuàng)建的模型需要擬合所有的樣本點(diǎn)（局部加權(quán)線性回歸除外）服傍。當(dāng)數(shù)據(jù)擁有眾多特征并且特征之間關(guān)系十分復(fù)雜時(shí)蒸甜，構(gòu)建全局模型的想法就顯得太難了，也略顯笨拙睛竣。而且晰房，實(shí)際生活中很多問(wèn)題都是非線性的，不可能使用全局線性模型來(lái)擬合任何數(shù)據(jù)射沟。

一種可行的方法是將數(shù)據(jù)集切分成很多份易建模的數(shù)據(jù)殊者，然后利用我們的線性回歸技術(shù)來(lái)建模。如果首次切分后仍然難以擬合線性模型就繼續(xù)切分验夯。在這種切分方式下猖吴，樹回歸和回歸法就相當(dāng)有用。

除了我們?cè)?第3章 中介紹的 決策樹算法挥转，我們介紹一個(gè)新的叫做 CART(Classification And Regression Trees, 分類回歸樹) 的樹構(gòu)建算法海蔽。該算法既可以用于分類還可以用于回歸。

1绑谣、樹回歸 原理

1.1党窜、樹回歸 原理概述

為成功構(gòu)建以分段常數(shù)為葉節(jié)點(diǎn)的樹，需要度量出數(shù)據(jù)的一致性借宵。第3章使用樹進(jìn)行分類幌衣，會(huì)在給定節(jié)點(diǎn)時(shí)計(jì)算數(shù)據(jù)的混亂度。那么如何計(jì)算連續(xù)型數(shù)值的混亂度呢壤玫？

在這里豁护，計(jì)算連續(xù)型數(shù)值的混亂度是非常簡(jiǎn)單的。首先計(jì)算所有數(shù)據(jù)的均值垦细，然后計(jì)算每條數(shù)據(jù)的值到均值的差值择镇。為了對(duì)正負(fù)差值同等看待，一般使用絕對(duì)值或平方值來(lái)代替上述差值括改。

上述做法有點(diǎn)類似于前面介紹過(guò)的統(tǒng)計(jì)學(xué)中常用的方差計(jì)算腻豌。唯一不同就是，方差是平方誤差的均值(均方差)嘱能，而這里需要的是平方誤差的總值(總方差)吝梅。總方差可以通過(guò)均方差乘以數(shù)據(jù)集中樣本點(diǎn)的個(gè)數(shù)來(lái)得到惹骂。

1.2苏携、樹構(gòu)建算法 比較

我們?cè)?第3章 中使用的樹構(gòu)建算法是 ID3 。ID3 的做法是每次選取當(dāng)前最佳的特征來(lái)分割數(shù)據(jù)对粪，并按照該特征的所有可能取值來(lái)切分右冻。也就是說(shuō)装蓬，如果一個(gè)特征有 4 種取值，那么數(shù)據(jù)將被切分成 4 份纱扭。一旦按照某特征切分后牍帚，該特征在之后的算法執(zhí)行過(guò)程中將不會(huì)再起作用，所以有觀點(diǎn)認(rèn)為這種切分方式過(guò)于迅速乳蛾。另外一種方法是二分切分法暗赶，即每次把數(shù)據(jù)集切分成兩份。如果數(shù)據(jù)的某特征值等于切分所要求的值肃叶，那么這些數(shù)據(jù)就進(jìn)入樹的左子樹蹂随，反之則進(jìn)入樹的右子樹。

除了切分過(guò)于迅速外因惭， ID3 算法還存在另一個(gè)問(wèn)題岳锁，它不能直接處理連續(xù)型特征。只有事先將連續(xù)型特征轉(zhuǎn)換成離散型蹦魔，才能在 ID3 算法中使用浸锨。但這種轉(zhuǎn)換過(guò)程會(huì)破壞連續(xù)型變量的內(nèi)在性質(zhì)。而使用二元切分法則易于對(duì)樹構(gòu)造過(guò)程進(jìn)行調(diào)整以處理連續(xù)型特征版姑。具體的處理方法是: 如果特征值大于給定值就走左子樹柱搜，否則就走右子樹。另外剥险，二分切分法也節(jié)省了樹的構(gòu)建時(shí)間聪蘸，但這點(diǎn)意義也不是特別大，因?yàn)檫@些樹構(gòu)建一般是離線完成表制，時(shí)間并非需要重點(diǎn)關(guān)注的因素健爬。

CART 是十分著名且廣泛記載的樹構(gòu)建算法，它使用二元切分來(lái)處理連續(xù)型變量么介。對(duì) CART 稍作修改就可以處理回歸問(wèn)題娜遵。第 3 章中使用香農(nóng)熵來(lái)度量集合的無(wú)組織程度。如果選用其他方法來(lái)代替香農(nóng)熵壤短，就可以使用樹構(gòu)建算法來(lái)完成回歸设拟。

回歸樹與分類樹的思路類似，但是葉節(jié)點(diǎn)的數(shù)據(jù)類型不是離散型久脯，而是連續(xù)型纳胧。

1.2.1、附加 各常見(jiàn)樹構(gòu)造算法的劃分分支方式

還有一點(diǎn)要說(shuō)明帘撰，構(gòu)建決策樹算法跑慕，常用到的是三個(gè)方法: ID3, C4.5, CART.
三種方法區(qū)別是劃分樹的分支的方式:

1. ID3 是信息增益分支
2. C4.5 是信息增益率分支
3. CART 是 GINI 系數(shù)分支

工程上總的來(lái)說(shuō):

CART 和 C4.5 之間主要差異在于分類結(jié)果上，CART 可以回歸分析也可以分類摧找，C4.5 只能做分類核行；C4.5 子節(jié)點(diǎn)是可以多分的牢硅，而 CART 是無(wú)數(shù)個(gè)二叉子節(jié)點(diǎn)；

以此拓展出以 CART 為基礎(chǔ)的 “樹群” Random forest 芝雪， 以 回歸樹 為基礎(chǔ)的 “樹群” GBDT 唤衫。

1.3、樹回歸 工作原理

1绵脯、找到數(shù)據(jù)集切分的最佳位置，函數(shù) chooseBestSplit() 偽代碼大致如下:

對(duì)每個(gè)特征:
    對(duì)每個(gè)特征值: 
        將數(shù)據(jù)集切分成兩份（小于該特征值的數(shù)據(jù)樣本放在左子樹休里，否則放在右子樹）
        計(jì)算切分的誤差
        如果當(dāng)前誤差小于當(dāng)前最小誤差蛆挫，那么將當(dāng)前切分設(shè)定為最佳切分并更新最小誤差
返回最佳切分的特征和閾值

2、樹構(gòu)建算法妙黍，函數(shù) createTree() 偽代碼大致如下:

找到最佳的待切分特征:
    如果該節(jié)點(diǎn)不能再分悴侵，將該節(jié)點(diǎn)存為葉節(jié)點(diǎn)
    執(zhí)行二元切分
    在右子樹調(diào)用 createTree() 方法
    在左子樹調(diào)用 createTree() 方法

1.4、樹回歸 開發(fā)流程

(1) 收集數(shù)據(jù)：采用任意方法收集數(shù)據(jù)拭嫁。
(2) 準(zhǔn)備數(shù)據(jù)：需要數(shù)值型數(shù)據(jù)可免，標(biāo)稱型數(shù)據(jù)應(yīng)該映射成二值型數(shù)據(jù)。
(3) 分析數(shù)據(jù)：繪出數(shù)據(jù)的二維可視化顯示結(jié)果做粤，以字典方式生成樹浇借。
(4) 訓(xùn)練算法：大部分時(shí)間都花費(fèi)在葉節(jié)點(diǎn)樹模型的構(gòu)建上。
(5) 測(cè)試算法：使用測(cè)試數(shù)據(jù)上的R^2值來(lái)分析模型的效果怕品。
(6) 使用算法：使用訓(xùn)練處的樹做預(yù)測(cè)妇垢，預(yù)測(cè)結(jié)果還可以用來(lái)做很多事情。

1.5肉康、樹回歸 算法特點(diǎn)

優(yōu)點(diǎn)：可以對(duì)復(fù)雜和非線性的數(shù)據(jù)建模闯估。
缺點(diǎn)：結(jié)果不易理解。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型數(shù)據(jù)吼和。

1.6涨薪、回歸樹 項(xiàng)目案例

1.6.1、項(xiàng)目概述

在簡(jiǎn)單數(shù)據(jù)集上生成一棵回歸樹炫乓。

1.6.2刚夺、開發(fā)流程

收集數(shù)據(jù)：采用任意方法收集數(shù)據(jù)
準(zhǔn)備數(shù)據(jù)：需要數(shù)值型數(shù)據(jù)，標(biāo)稱型數(shù)據(jù)應(yīng)該映射成二值型數(shù)據(jù)
分析數(shù)據(jù)：繪出數(shù)據(jù)的二維可視化顯示結(jié)果末捣，以字典方式生成樹
訓(xùn)練算法：大部分時(shí)間都花費(fèi)在葉節(jié)點(diǎn)樹模型的構(gòu)建上
測(cè)試算法：使用測(cè)試數(shù)據(jù)上的R^2值來(lái)分析模型的效果
使用算法：使用訓(xùn)練出的樹做預(yù)測(cè)光督，預(yù)測(cè)結(jié)果還可以用來(lái)做很多事情

收集數(shù)據(jù)：采用任意方法收集數(shù)據(jù)

data1.txt 文件中存儲(chǔ)的數(shù)據(jù)格式如下:

0.036098    0.155096
0.993349    1.077553
0.530897    0.893462
0.712386    0.564858
0.343554    -0.371700
0.098016    -0.332760

準(zhǔn)備數(shù)據(jù)：需要數(shù)值型數(shù)據(jù)，標(biāo)稱型數(shù)據(jù)應(yīng)該映射成二值型數(shù)據(jù)

分析數(shù)據(jù)：繪出數(shù)據(jù)的二維可視化顯示結(jié)果塔粒，以字典方式生成樹

基于 CART 算法構(gòu)建回歸樹的簡(jiǎn)單數(shù)據(jù)集

基于 CART 算法構(gòu)建回歸樹的簡(jiǎn)單數(shù)據(jù)集

用于測(cè)試回歸樹的分段常數(shù)數(shù)據(jù)集

用于測(cè)試回歸樹的分段常數(shù)數(shù)據(jù)集

訓(xùn)練算法: 構(gòu)造樹的數(shù)據(jù)結(jié)構(gòu)

def binSplitDataSet(dataSet, feature, value):
    """binSplitDataSet(將數(shù)據(jù)集结借，按照f(shuō)eature列的value進(jìn)行 二元切分)
        Description：在給定特征和特征值的情況下，該函數(shù)通過(guò)數(shù)組過(guò)濾方式將上述數(shù)據(jù)集合切分得到兩個(gè)子集并返回卒茬。
    Args:
        dataMat 數(shù)據(jù)集
        feature 待切分的特征列
        value 特征列要比較的值
    Returns:
        mat0 小于等于 value 的數(shù)據(jù)集在左邊
        mat1 大于 value 的數(shù)據(jù)集在右邊
    Raises:
    """
    # # 測(cè)試案例
    # print 'dataSet[:, feature]=', dataSet[:, feature]
    # print 'nonzero(dataSet[:, feature] > value)[0]=', nonzero(dataSet[:, feature] > value)[0]
    # print 'nonzero(dataSet[:, feature] <= value)[0]=', nonzero(dataSet[:, feature] <= value)[0]

    # dataSet[:, feature] 取去每一行中船老，第1列的值(從0開始算)
    # nonzero(dataSet[:, feature] > value)  返回結(jié)果為true行的index下標(biāo)
    mat0 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :]
    mat1 = dataSet[nonzero(dataSet[:, feature] > value)[0], :]
    return mat0, mat1


# 1.用最佳方式切分?jǐn)?shù)據(jù)集
# 2.生成相應(yīng)的葉節(jié)點(diǎn)
def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
    """chooseBestSplit(用最佳方式切分?jǐn)?shù)據(jù)集 和 生成相應(yīng)的葉節(jié)點(diǎn))

    Args:
        dataSet   加載的原始數(shù)據(jù)集
        leafType  建立葉子點(diǎn)的函數(shù)
        errType   誤差計(jì)算函數(shù)(求總方差)
        ops       [容許誤差下降值咖熟，切分的最少樣本數(shù)]。
    Returns:
        bestIndex feature的index坐標(biāo)
        bestValue 切分的最優(yōu)值
    Raises:
    """

    # ops=(1,4)柳畔，非常重要馍管，因?yàn)樗鼪Q定了決策樹劃分停止的threshold值，被稱為預(yù)剪枝（prepruning）薪韩，其實(shí)也就是用于控制函數(shù)的停止時(shí)機(jī)确沸。
    # 之所以這樣說(shuō)，是因?yàn)樗乐箾Q策樹的過(guò)擬合俘陷，所以當(dāng)誤差的下降值小于tolS罗捎，或劃分后的集合size小于tolN時(shí)，選擇停止繼續(xù)劃分拉盾。
    # 最小誤差下降值桨菜，劃分后的誤差減小小于這個(gè)差值，就不用繼續(xù)劃分
    tolS = ops[0]
    # 劃分最小 size 小于捉偏，就不繼續(xù)劃分了
    tolN = ops[1]
    # 如果結(jié)果集(最后一列為1個(gè)變量)倒得，就返回退出
    # .T 對(duì)數(shù)據(jù)集進(jìn)行轉(zhuǎn)置
    # .tolist()[0] 轉(zhuǎn)化為數(shù)組并取第0列
    if len(set(dataSet[:, -1].T.tolist()[0])) == 1: # 如果集合size為1，不用繼續(xù)劃分夭禽。
        #  exit cond 1
        return None, leafType(dataSet)
    # 計(jì)算行列值
    m, n = shape(dataSet)
    # 無(wú)分類誤差的總方差和
    # the choice of the best feature is driven by Reduction in RSS error from mean
    S = errType(dataSet)
    # inf 正無(wú)窮大
    bestS, bestIndex, bestValue = inf, 0, 0
    # 循環(huán)處理每一列對(duì)應(yīng)的feature值
    for featIndex in range(n-1): # 對(duì)于每個(gè)特征
        # [0]表示這一列的[所有行]霞掺，不要[0]就是一個(gè)array[[所有行]]
        for splitVal in set(dataSet[:, featIndex].T.tolist()[0]):
            # 對(duì)該列進(jìn)行分組，然后組內(nèi)的成員的val值進(jìn)行 二元切分
            mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
            # 判斷二元切分的方式的元素?cái)?shù)量是否符合預(yù)期
            if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):
                continue
            newS = errType(mat0) + errType(mat1)
            # 如果二元切分讹躯，算出來(lái)的誤差在可接受范圍內(nèi)根悼，那么就記錄切分點(diǎn)，并記錄最小誤差
            # 如果劃分后誤差小于 bestS蜀撑，則說(shuō)明找到了新的bestS
            if newS < bestS:
                bestIndex = featIndex
                bestValue = splitVal
                bestS = newS
    # 判斷二元切分的方式的元素誤差是否符合預(yù)期
    # if the decrease (S-bestS) is less than a threshold don't do the split
    if (S - bestS) < tolS:
        return None, leafType(dataSet)
    mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
    # 對(duì)整體的成員進(jìn)行判斷挤巡，是否符合預(yù)期
    # 如果集合的 size 小于 tolN 
    if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): # 當(dāng)最佳劃分后，集合過(guò)小酷麦，也不劃分矿卑，產(chǎn)生葉節(jié)點(diǎn)
        return None, leafType(dataSet)
    return bestIndex, bestValue


# assume dataSet is NumPy Mat so we can array filtering
# 假設(shè) dataSet 是 NumPy Mat 類型的，那么我們可以進(jìn)行 array 過(guò)濾
def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
    """createTree(獲取回歸樹)
        Description：遞歸函數(shù)：如果構(gòu)建的是回歸樹沃饶，該模型是一個(gè)常數(shù)母廷，如果是模型樹，其模型師一個(gè)線性方程糊肤。
    Args:
        dataSet      加載的原始數(shù)據(jù)集
        leafType     建立葉子點(diǎn)的函數(shù)
        errType      誤差計(jì)算函數(shù)
        ops=(1, 4)   [容許誤差下降值琴昆，切分的最少樣本數(shù)]
    Returns:
        retTree    決策樹最后的結(jié)果
    """
    # 選擇最好的切分方式： feature索引值，最優(yōu)切分值
    # choose the best split
    feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
    # if the splitting hit a stop condition return val
    # 如果 splitting 達(dá)到一個(gè)停止條件馆揉，那么返回 val
    if feat is None:
        return val
    retTree = {}
    retTree['spInd'] = feat
    retTree['spVal'] = val
    # 大于在右邊业舍，小于在左邊，分為2個(gè)數(shù)據(jù)集
    lSet, rSet = binSplitDataSet(dataSet, feat, val)
    # 遞歸的進(jìn)行調(diào)用，在左右子樹中繼續(xù)遞歸生成樹
    retTree['left'] = createTree(lSet, leafType, errType, ops)
    retTree['right'] = createTree(rSet, leafType, errType, ops)
    return retTree

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/9.RegTrees/regTrees.py

測(cè)試算法：使用測(cè)試數(shù)據(jù)上的R^2值來(lái)分析模型的效果

使用算法：使用訓(xùn)練出的樹做預(yù)測(cè)舷暮，預(yù)測(cè)結(jié)果還可以用來(lái)做很多事情

2态罪、樹剪枝

一棵樹如果節(jié)點(diǎn)過(guò)多，表明該模型可能對(duì)數(shù)據(jù)進(jìn)行了 “過(guò)擬合”下面。

通過(guò)降低決策樹的復(fù)雜度來(lái)避免過(guò)擬合的過(guò)程稱為 剪枝（pruning）复颈。在函數(shù) chooseBestSplit() 中提前終止條件，實(shí)際上是在進(jìn)行一種所謂的 預(yù)剪枝（prepruning）操作沥割。另一個(gè)形式的剪枝需要使用測(cè)試集和訓(xùn)練集耗啦，稱作 后剪枝（postpruning）。

2.1机杜、預(yù)剪枝(prepruning)

顧名思義帜讲，預(yù)剪枝就是及早的停止樹增長(zhǎng)，在構(gòu)造決策樹的同時(shí)進(jìn)行剪枝叉庐。

所有決策樹的構(gòu)建方法，都是在無(wú)法進(jìn)一步降低熵的情況下才會(huì)停止創(chuàng)建分支的過(guò)程会喝，為了避免過(guò)擬合陡叠，可以設(shè)定一個(gè)閾值，熵減小的數(shù)量小于這個(gè)閾值肢执，即使還可以繼續(xù)降低熵枉阵，也停止繼續(xù)創(chuàng)建分支。但是這種方法實(shí)際中的效果并不好预茄。

2.2兴溜、后剪枝(postpruning)

決策樹構(gòu)造完成后進(jìn)行剪枝。剪枝的過(guò)程是對(duì)擁有同樣父節(jié)點(diǎn)的一組節(jié)點(diǎn)進(jìn)行檢查耻陕，判斷如果將其合并拙徽，熵的增加量是否小于某一閾值。如果確實(shí)小诗宣，則這一組節(jié)點(diǎn)可以合并一個(gè)節(jié)點(diǎn)膘怕，其中包含了所有可能的結(jié)果。合并也被稱作 塌陷處理 召庞，在回歸樹中一般采用取需要合并的所有子樹的平均值岛心。后剪枝是目前最普遍的做法。

后剪枝 prune() 的偽代碼如下:

基于已有的樹切分測(cè)試數(shù)據(jù):
    如果存在任一子集是一棵樹篮灼，則在該子集遞歸剪枝過(guò)程
    計(jì)算將當(dāng)前兩個(gè)葉節(jié)點(diǎn)合并后的誤差
    計(jì)算不合并的誤差
    如果合并會(huì)降低誤差的話忘古，就將葉節(jié)點(diǎn)合并

2.3、剪枝 代碼

回歸樹剪枝函數(shù)

# 判斷節(jié)點(diǎn)是否是一個(gè)字典
def isTree(obj):
    """
    Desc:
        測(cè)試輸入變量是否是一棵樹,即是否是一個(gè)字典
    Args:
        obj -- 輸入變量
    Returns:
        返回布爾類型的結(jié)果诅诱。如果 obj 是一個(gè)字典髓堪，返回true，否則返回 false
    """
    return (type(obj).__name__ == 'dict')


# 計(jì)算左右枝丫的均值
def getMean(tree):
    """
    Desc:
        從上往下遍歷樹直到葉節(jié)點(diǎn)為止，如果找到兩個(gè)葉節(jié)點(diǎn)則計(jì)算它們的平均值旦袋。
        對(duì) tree 進(jìn)行塌陷處理骤菠，即返回樹平均值。
    Args:
        tree -- 輸入的樹
    Returns:
        返回 tree 節(jié)點(diǎn)的平均值
    """
    if isTree(tree['right']):
        tree['right'] = getMean(tree['right'])
    if isTree(tree['left']):
        tree['left'] = getMean(tree['left'])
    return (tree['left']+tree['right'])/2.0


# 檢查是否適合合并分枝
def prune(tree, testData):
    """
    Desc:
        從上而下找到葉節(jié)點(diǎn)疤孕，用測(cè)試數(shù)據(jù)集來(lái)判斷將這些葉節(jié)點(diǎn)合并是否能降低測(cè)試誤差
    Args:
        tree -- 待剪枝的樹
        testData -- 剪枝所需要的測(cè)試數(shù)據(jù) testData 
    Returns:
        tree -- 剪枝完成的樹
    """
    # 判斷是否測(cè)試數(shù)據(jù)集沒(méi)有數(shù)據(jù)商乎，如果沒(méi)有，就直接返回tree本身的均值
    if shape(testData)[0] == 0:
        return getMean(tree)

    # 判斷分枝是否是dict字典祭阀，如果是就將測(cè)試數(shù)據(jù)集進(jìn)行切分
    if (isTree(tree['right']) or isTree(tree['left'])):
        lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
    # 如果是左邊分枝是字典鹉戚，就傳入左邊的數(shù)據(jù)集和左邊的分枝，進(jìn)行遞歸
    if isTree(tree['left']):
        tree['left'] = prune(tree['left'], lSet)
    # 如果是右邊分枝是字典专控，就傳入左邊的數(shù)據(jù)集和左邊的分枝抹凳，進(jìn)行遞歸
    if isTree(tree['right']):
        tree['right'] = prune(tree['right'], rSet)

    # 上面的一系列操作本質(zhì)上就是將測(cè)試數(shù)據(jù)集按照訓(xùn)練完成的樹拆分好，對(duì)應(yīng)的值放到對(duì)應(yīng)的節(jié)點(diǎn)

    # 如果左右兩邊同時(shí)都不是dict字典伦腐，也就是左右兩邊都是葉節(jié)點(diǎn)赢底，而不是子樹了，那么分割測(cè)試數(shù)據(jù)集柏蘑。
    # 1. 如果正確 
    #   * 那么計(jì)算一下總方差 和 該結(jié)果集的本身不分枝的總方差比較
    #   * 如果 合并的總方差 < 不合并的總方差幸冻，那么就進(jìn)行合并
    # 注意返回的結(jié)果： 如果可以合并，原來(lái)的dict就變?yōu)榱?數(shù)值
    if not isTree(tree['left']) and not isTree(tree['right']):
        lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
        # power(x, y)表示x的y次方
        errorNoMerge = sum(power(lSet[:, -1] - tree['left'], 2)) + sum(power(rSet[:, -1] - tree['right'], 2))
        treeMean = (tree['left'] + tree['right'])/2.0
        errorMerge = sum(power(testData[:, -1] - treeMean, 2))
        # 如果 合并的總方差 < 不合并的總方差咳焚，那么就進(jìn)行合并
        if errorMerge < errorNoMerge:
            print "merging"
            return treeMean
        else:
            return tree
    else:
        return tree

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/9.RegTrees/regTrees.py

3洽损、模型樹

3.1、模型樹 簡(jiǎn)介

用樹來(lái)對(duì)數(shù)據(jù)建模革半，除了把葉節(jié)點(diǎn)簡(jiǎn)單地設(shè)定為常數(shù)值之外碑定，還有一種方法是把葉節(jié)點(diǎn)設(shè)定為分段線性函數(shù)，這里所謂的 分段線性（piecewise linear） 是指模型由多個(gè)線性片段組成又官。

我們看一下圖 9-4 中的數(shù)據(jù)延刘，如果使用兩條直線擬合是否比使用一組常數(shù)來(lái)建模好呢？答案顯而易見(jiàn)六敬》萌ⅲ可以設(shè)計(jì)兩條分別從 0.0~0.3、從 0.3~1.0 的直線觉阅，于是就可以得到兩個(gè)線性模型崖疤。因?yàn)閿?shù)據(jù)集里的一部分?jǐn)?shù)據(jù)（0.0_{0.3）以某個(gè)線性模型建模，而另一部分?jǐn)?shù)據(jù)（0.3}1.0）則以另一個(gè)線性模型建模典勇，因此我們說(shuō)采用了所謂的分段線性模型劫哼。

決策樹相比于其他機(jī)器學(xué)習(xí)算法的優(yōu)勢(shì)之一在于結(jié)果更易理解。很顯然割笙，兩條直線比很多節(jié)點(diǎn)組成一棵大樹更容易解釋权烧。模型樹的可解釋性是它優(yōu)于回歸樹的特點(diǎn)之一眯亦。另外，模型樹也具有更高的預(yù)測(cè)準(zhǔn)確度般码。

分段線性數(shù)據(jù)

將之前的回歸樹的代碼稍作修改妻率，就可以在葉節(jié)點(diǎn)生成線性模型而不是常數(shù)值。下面將利用樹生成算法對(duì)數(shù)據(jù)進(jìn)行劃分板祝，且每份切分?jǐn)?shù)據(jù)都能很容易被線性模型所表示宫静。這個(gè)算法的關(guān)鍵在于誤差的計(jì)算。

那么為了找到最佳切分券时，應(yīng)該怎樣計(jì)算誤差呢孤里？前面用于回歸樹的誤差計(jì)算方法這里不能再用。稍加變化橘洞，對(duì)于給定的數(shù)據(jù)集捌袜，應(yīng)該先用模型來(lái)對(duì)它進(jìn)行擬合，然后計(jì)算真實(shí)的目標(biāo)值與模型預(yù)測(cè)值間的差值炸枣。最后將這些差值的平方求和就得到了所需的誤差虏等。

3.2、模型樹 代碼

模型樹的葉節(jié)點(diǎn)生成函數(shù)

# 得到模型的ws系數(shù)：f(x) = x0 + x1*featrue1+ x3*featrue2 ...
# create linear model and return coeficients
def modelLeaf(dataSet):
    """
    Desc:
        當(dāng)數(shù)據(jù)不再需要切分的時(shí)候适肠，生成葉節(jié)點(diǎn)的模型霍衫。
    Args:
        dataSet -- 輸入數(shù)據(jù)集
    Returns:
        調(diào)用 linearSolve 函數(shù)，返回得到的 回歸系數(shù)ws
    """
    ws, X, Y = linearSolve(dataSet)
    return ws


# 計(jì)算線性模型的誤差值
def modelErr(dataSet):
    """
    Desc:
        在給定數(shù)據(jù)集上計(jì)算誤差迂猴。
    Args:
        dataSet -- 輸入數(shù)據(jù)集
    Returns:
        調(diào)用 linearSolve 函數(shù)慕淡，返回 yHat 和 Y 之間的平方誤差背伴。
    """
    ws, X, Y = linearSolve(dataSet)
    yHat = X * ws
    # print corrcoef(yHat, Y, rowvar=0)
    return sum(power(Y - yHat, 2))


 # helper function used in two places
def linearSolve(dataSet):
    """
    Desc:
        將數(shù)據(jù)集格式化成目標(biāo)變量Y和自變量X沸毁，執(zhí)行簡(jiǎn)單的線性回歸，得到ws
    Args:
        dataSet -- 輸入數(shù)據(jù)
    Returns:
        ws -- 執(zhí)行線性回歸的回歸系數(shù) 
        X -- 格式化自變量X
        Y -- 格式化目標(biāo)變量Y
    """
    m, n = shape(dataSet)
    # 產(chǎn)生一個(gè)關(guān)于1的矩陣
    X = mat(ones((m, n)))
    Y = mat(ones((m, 1)))
    # X的0列為1傻寂，常數(shù)項(xiàng)息尺，用于計(jì)算平衡誤差
    X[:, 1: n] = dataSet[:, 0: n-1]
    Y = dataSet[:, -1]

    # 轉(zhuǎn)置矩陣*矩陣
    xTx = X.T * X
    # 如果矩陣的逆不存在，會(huì)造成程序異常
    if linalg.det(xTx) == 0.0:
        raise NameError('This matrix is singular, cannot do inverse,\ntry increasing the second value of ops')
    # 最小二乘法求最優(yōu)解:  w0*1+w1*x1=y
    ws = xTx.I * (X.T * Y)
    return ws, X, Y

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/9.RegTrees/regTrees.py

3.3疾掰、模型樹 運(yùn)行結(jié)果

模型樹運(yùn)行結(jié)果

4搂誉、樹回歸 項(xiàng)目案例

4.1、項(xiàng)目案例1: 樹回歸與標(biāo)準(zhǔn)回歸的比較

4.1.1静檬、項(xiàng)目概述

前面介紹了模型樹炭懊、回歸樹和一般的回歸方法，下面測(cè)試一下哪個(gè)模型最好拂檩。

這些模型將在某個(gè)數(shù)據(jù)上進(jìn)行測(cè)試侮腹，該數(shù)據(jù)涉及人的智力水平和自行車的速度的關(guān)系。當(dāng)然稻励，數(shù)據(jù)是假的父阻。

4.1.2愈涩、開發(fā)流程

收集數(shù)據(jù)：采用任意方法收集數(shù)據(jù)
準(zhǔn)備數(shù)據(jù)：需要數(shù)值型數(shù)據(jù)，標(biāo)稱型數(shù)據(jù)應(yīng)該映射成二值型數(shù)據(jù)
分析數(shù)據(jù)：繪出數(shù)據(jù)的二維可視化顯示結(jié)果加矛，以字典方式生成樹
訓(xùn)練算法：模型樹的構(gòu)建
測(cè)試算法：使用測(cè)試數(shù)據(jù)上的R^2值來(lái)分析模型的效果
使用算法：使用訓(xùn)練出的樹做預(yù)測(cè)履婉，預(yù)測(cè)結(jié)果還可以用來(lái)做很多事情

收集數(shù)據(jù): 采用任意方法收集數(shù)據(jù)

準(zhǔn)備數(shù)據(jù)：需要數(shù)值型數(shù)據(jù)，標(biāo)稱型數(shù)據(jù)應(yīng)該映射成二值型數(shù)據(jù)

數(shù)據(jù)存儲(chǔ)格式:

3.000000    46.852122
23.000000   178.676107
0.000000    86.154024
6.000000    68.707614
15.000000   139.737693

分析數(shù)據(jù)：繪出數(shù)據(jù)的二維可視化顯示結(jié)果斟览，以字典方式生成樹

騎自行車速度和智商之間的關(guān)系

訓(xùn)練算法：模型樹的構(gòu)建

用樹回歸進(jìn)行預(yù)測(cè)的代碼

# 回歸樹測(cè)試案例
# 為了和 modelTreeEval() 保持一致毁腿，保留兩個(gè)輸入?yún)?shù)
def regTreeEval(model, inDat):
    """
    Desc:
        對(duì) 回歸樹 進(jìn)行預(yù)測(cè)
    Args:
        model -- 指定模型，可選值為 回歸樹模型 或者 模型樹模型趣惠，這里為回歸樹
        inDat -- 輸入的測(cè)試數(shù)據(jù)
    Returns:
        float(model) -- 將輸入的模型數(shù)據(jù)轉(zhuǎn)換為 浮點(diǎn)數(shù) 返回
    """
    return float(model)


# 模型樹測(cè)試案例
# 對(duì)輸入數(shù)據(jù)進(jìn)行格式化處理狸棍，在原數(shù)據(jù)矩陣上增加第0列，元素的值都是1味悄，
# 也就是增加偏移值草戈，和我們之前的簡(jiǎn)單線性回歸是一個(gè)套路，增加一個(gè)偏移量
def modelTreeEval(model, inDat):
    """
    Desc:
        對(duì) 模型樹 進(jìn)行預(yù)測(cè)
    Args:
        model -- 輸入模型侍瑟，可選值為 回歸樹模型 或者 模型樹模型唐片，這里為模型樹模型
        inDat -- 輸入的測(cè)試數(shù)據(jù)
    Returns:
        float(X * model) -- 將測(cè)試數(shù)據(jù)乘以 回歸系數(shù) 得到一個(gè)預(yù)測(cè)值 ，轉(zhuǎn)化為 浮點(diǎn)數(shù) 返回
    """
    n = shape(inDat)[1]
    X = mat(ones((1, n+1)))
    X[:, 1: n+1] = inDat
    # print X, model
    return float(X * model)


# 計(jì)算預(yù)測(cè)的結(jié)果
# 在給定樹結(jié)構(gòu)的情況下涨颜，對(duì)于單個(gè)數(shù)據(jù)點(diǎn)费韭，該函數(shù)會(huì)給出一個(gè)預(yù)測(cè)值。
# modelEval是對(duì)葉節(jié)點(diǎn)進(jìn)行預(yù)測(cè)的函數(shù)引用庭瑰，指定樹的類型星持，以便在葉節(jié)點(diǎn)上調(diào)用合適的模型。
# 此函數(shù)自頂向下遍歷整棵樹弹灭，直到命中葉節(jié)點(diǎn)為止督暂，一旦到達(dá)葉節(jié)點(diǎn)，它就會(huì)在輸入數(shù)據(jù)上
# 調(diào)用modelEval()函數(shù)穷吮，該函數(shù)的默認(rèn)值為regTreeEval()
def treeForeCast(tree, inData, modelEval=regTreeEval):
    """
    Desc:
        對(duì)特定模型的樹進(jìn)行預(yù)測(cè)逻翁，可以是 回歸樹 也可以是 模型樹
    Args:
        tree -- 已經(jīng)訓(xùn)練好的樹的模型
        inData -- 輸入的測(cè)試數(shù)據(jù)
        modelEval -- 預(yù)測(cè)的樹的模型類型，可選值為 regTreeEval（回歸樹） 或 modelTreeEval（模型樹）捡鱼，默認(rèn)為回歸樹
    Returns:
        返回預(yù)測(cè)值
    """
    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)


# 預(yù)測(cè)結(jié)果
def createForeCast(tree, testData, modelEval=regTreeEval):
    """
    Desc:
        調(diào)用 treeForeCast 八回，對(duì)特定模型的樹進(jìn)行預(yù)測(cè)，可以是 回歸樹 也可以是 模型樹
    Args:
        tree -- 已經(jīng)訓(xùn)練好的樹的模型
        inData -- 輸入的測(cè)試數(shù)據(jù)
        modelEval -- 預(yù)測(cè)的樹的模型類型驾诈，可選值為 regTreeEval（回歸樹） 或 modelTreeEval（模型樹）缠诅，默認(rèn)為回歸樹
    Returns:
        返回預(yù)測(cè)值矩陣
    """
    m = len(testData)
    yHat = mat(zeros((m, 1)))
    # print yHat
    for i in range(m):
        yHat[i, 0] = treeForeCast(tree, mat(testData[i]), modelEval)
        # print "yHat==>", yHat[i, 0]
    return yHat

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/9.RegTrees/regTrees.py

測(cè)試算法：使用測(cè)試數(shù)據(jù)上的R^2值來(lái)分析模型的效果

R^2 判定系數(shù)就是擬合優(yōu)度判定系數(shù)，它體現(xiàn)了回歸模型中自變量的變異在因變量的變異中所占的比例乍迄。如 R^2=0.99999 表示在因變量 y 的變異中有 99.999% 是由于變量 x 引起管引。當(dāng) R^2=1 時(shí)表示，所有觀測(cè)點(diǎn)都落在擬合的直線或曲線上就乓；當(dāng) R^2=0 時(shí)汉匙，表示自變量與因變量不存在直線或曲線關(guān)系拱烁。

所以我們看出， R^2 的值越接近 1.0 越好噩翠。

使用算法：使用訓(xùn)練出的樹做預(yù)測(cè)戏自，預(yù)測(cè)結(jié)果還可以用來(lái)做很多事情

5、附加 Python 中 GUI 的使用

5.1伤锚、使用 Python 的 Tkinter 庫(kù)創(chuàng)建 GUI

如果能讓用戶不需要任何指令就可以按照他們自己的方式來(lái)分析數(shù)據(jù)擅笔，就不需要對(duì)數(shù)據(jù)做出過(guò)多解釋。其中一個(gè)能同時(shí)支持?jǐn)?shù)據(jù)呈現(xiàn)和用戶交互的方式就是構(gòu)建一個(gè)圖形用戶界面(GUI屯援，Graphical User Interface)猛们，如圖9-7所示。

GUI示例圖

5.2狞洋、用 Tkinter 創(chuàng)建 GUI

Python 有很多 GUI 框架弯淘，其中一個(gè)易于使用的 Tkinter，是隨 Python 的標(biāo)準(zhǔn)版編譯版本發(fā)布的吉懊。Tkinter 可以在 Windows庐橙、Mac OS和大多數(shù)的 Linux 平臺(tái)上使用。

5.3借嗽、集成 Matplotlib 和 Tkinter

MatPlotlib 的構(gòu)建程序包含一個(gè)前端态鳖，也就是面向用戶的一些代碼，如 plot() 和 scatter() 方法等恶导。事實(shí)上浆竭，它同時(shí)創(chuàng)建了一個(gè)后端，用于實(shí)現(xiàn)繪圖和不同應(yīng)用之間接口惨寿。

通過(guò)改變后端可以將圖像繪制在PNG邦泄、PDF、SVG等格式的文件上缤沦。下面將設(shè)置后端為 TkAgg (Agg 是一個(gè) C++ 的庫(kù)虎韵，可以從圖像創(chuàng)建光柵圖)易稠。TkAgg可以在所選GUI框架上調(diào)用Agg缸废，把 Agg 呈現(xiàn)在畫布上。我們可以在Tk的GUI上放置一個(gè)畫布驶社，并用 .grid()來(lái)調(diào)整布局企量。

5.4、用treeExplore 的GUI構(gòu)建的模型樹示例圖

取得更好預(yù)測(cè)效果的GUI示例圖

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/9.RegTrees/treeExplore.py

6亡电、樹回歸 小結(jié)

數(shù)據(jù)集中經(jīng)常包含一些復(fù)雜的相關(guān)關(guān)系届巩，使得輸入數(shù)據(jù)和目標(biāo)變量之間呈現(xiàn)非線性關(guān)系。對(duì)這些復(fù)雜的關(guān)系建模份乒，一種可行的方式是使用樹來(lái)對(duì)預(yù)測(cè)值分段恕汇，包括分段常數(shù)或分段直線腕唧。一般采用樹結(jié)構(gòu)來(lái)對(duì)這種數(shù)據(jù)建模。相應(yīng)地瘾英，若葉節(jié)點(diǎn)使用的模型是分段常數(shù)則稱為回歸樹枣接，若葉節(jié)點(diǎn)使用的模型師線性回歸方程則稱為模型樹。

CART 算法可以用于構(gòu)建二元樹并處理離散型或連續(xù)型數(shù)據(jù)的切分缺谴。若使用不同的誤差準(zhǔn)則但惶，就可以通過(guò)CART 算法構(gòu)建模型樹和回歸樹。該算法構(gòu)建出的樹會(huì)傾向于對(duì)數(shù)據(jù)過(guò)擬合湿蛔。一棵過(guò)擬合的樹常常十分復(fù)雜膀曾，剪枝技術(shù)的出現(xiàn)就是為了解決這個(gè)問(wèn)題。兩種剪枝方法分別是預(yù)剪枝（在樹的構(gòu)建過(guò)程中就進(jìn)行剪枝）和后剪枝（當(dāng)樹構(gòu)建完畢再進(jìn)行剪枝）阳啥，預(yù)剪枝更有效但需要用戶定義一些參數(shù)添谊。

Tkinter 是 Python 的一個(gè) GUI 工具包。雖然并不是唯一的包察迟，但它最常用碉钠。利用 Tkinter ，我們可以輕輕松松繪制各種部件并安排它們的位置卷拘。另外喊废，可以為 Tkinter 構(gòu)造一個(gè)特殊的部件來(lái)顯示 Matplotlib 繪出的圖。所以栗弟，Matplotlib 和 Tkinter 的集成可以構(gòu)建出更強(qiáng)大的 GUI 污筷，用戶可以以更自然的方式來(lái)探索機(jī)器學(xué)習(xí)算法的奧妙。

• 作者：片刻 小瑤
• GitHub地址: https://github.com/apachecn/MachineLearning
• 版權(quán)聲明：歡迎轉(zhuǎn)載學(xué)習(xí) => 請(qǐng)標(biāo)注信息來(lái)源于 ApacheCN