之前有文章介紹過決策樹（ID3）彼哼。簡單回顧一下：ID3每次選取最佳特征來分割數(shù)據(jù)摩瞎，這個(gè)最佳特征的判斷原則是通過信息增益來實(shí)現(xiàn)的。按照某種特征切分?jǐn)?shù)據(jù)后稠氮，該特征在以后切分?jǐn)?shù)據(jù)集時(shí)就不再使用，因此存在切分過于迅速的問題。ID3算法還不能處理連續(xù)性特征。
下面簡單介紹一下其他算法：

屏幕快照 2018-03-03 14.05.44.png

CART 分類回歸樹

CART是Classification And Regerssion Trees的縮寫，既能處理分類任務(wù)也能做回歸任務(wù)易遣。

image.png

CART樹的典型代表時(shí)二叉樹炮温，根據(jù)不同的條件將分類担巩。

image.png

CART樹構(gòu)建算法
與ID3決策樹的構(gòu)建方法類似先匪，直接給出CART樹的構(gòu)建過程。首先與ID3類似采用字典樹的數(shù)據(jù)結(jié)構(gòu)拟糕，包含以下4中元素：

• 待切分的特征
• 待切分的特征值
• 右子樹。當(dāng)不再需要切分的時(shí)候宠蚂，也可以是單個(gè)值
• 左子樹，類似右子樹忘嫉。

過程如下：

1. 尋找最合適的分割特征
2. 如果不能分割數(shù)據(jù)集，該數(shù)據(jù)集作為一個(gè)葉子節(jié)點(diǎn)描滔。
3. 對數(shù)據(jù)集進(jìn)行二分割
4. 對分割的數(shù)據(jù)集1重復(fù)1陪腌， 2卵洗，3 步，創(chuàng)建右子樹亏狰。
5. 對分割的數(shù)據(jù)集2重復(fù)1， 2丁逝，3 步琢感，創(chuàng)建左子樹其垄。

明顯的遞歸算法。

通過數(shù)據(jù)過濾的方式分割數(shù)據(jù)集克懊，返回兩個(gè)子集柜与。

def splitDatas(rows, value, column):
    # 根據(jù)條件分離數(shù)據(jù)集(splitDatas by value, column)
    # return 2 part（list1, list2）

    list1 = []
    list2 = []

    if isinstance(value, int) or isinstance(value, float):
        for row in rows:
            if row[column] >= value:
                list1.append(row)
            else:
                list2.append(row)
    else:
        for row in rows:
            if row[column] == value:
                list1.append(row)
            else:
                list2.append(row)
    return list1, list2

劃分?jǐn)?shù)據(jù)點(diǎn)

創(chuàng)建二進(jìn)制決策樹本質(zhì)上就是遞歸劃分輸入空間的過程。

image.png

代碼如下：

# gini()
def gini(rows):
    # 計(jì)算gini的值(Calculate GINI)

    length = len(rows)
    results = calculateDiffCount(rows)
    imp = 0.0
    for i in results:
        imp += results[i] / length * results[i] / length
    return 1 - imp

構(gòu)建樹

def buildDecisionTree(rows, evaluationFunction=gini):
    # 遞歸建立決策樹， 當(dāng)gain=0拐辽，時(shí)停止回歸
    # build decision tree bu recursive function
    # stop recursive function when gain = 0
    # return tree
    currentGain = evaluationFunction(rows)
    column_lenght = len(rows[0])
    rows_length = len(rows)

    best_gain = 0.0
    best_value = None
    best_set = None

    # choose the best gain
    for col in range(column_lenght - 1):
        col_value_set = set([x[col] for x in rows])
        for value in col_value_set:
            list1, list2 = splitDatas(rows, value, col)
            p = len(list1) / rows_length
            gain = currentGain - p * evaluationFunction(list1) - (1 - p) * evaluationFunction(list2)
            if gain > best_gain:
                best_gain = gain
                best_value = (col, value)
                best_set = (list1, list2)
    dcY = {'impurity': '%.3f' % currentGain, 'sample': '%d' % rows_length}
    #
    # stop or not stop

    if best_gain > 0:
        trueBranch = buildDecisionTree(best_set[0], evaluationFunction)
        falseBranch = buildDecisionTree(best_set[1], evaluationFunction)
        return Tree(col=best_value[0], value = best_value[1], trueBranch = trueBranch, falseBranch=falseBranch, summary=dcY)
    else:
        return Tree(results=calculateDiffCount(rows), summary=dcY, data=rows)

上面代碼的功能是先找到數(shù)據(jù)集切分的最佳位置和分割數(shù)據(jù)集。之后通過遞歸構(gòu)建出上面圖片的整棵樹舔痪。

剪枝

在決策樹的學(xué)習(xí)中痛悯，有時(shí)會造成決策樹分支過多，這是就需要去掉一些分支筒扒，降低過度擬合怯邪。通過決策樹的復(fù)雜度來避免過度擬合的過程稱為剪枝。
后剪枝需要從訓(xùn)練集生成一棵完整的決策樹花墩，然后自底向上對非葉子節(jié)點(diǎn)進(jìn)行考察悬秉。利用測試集判斷是否將該節(jié)點(diǎn)對應(yīng)的子樹替換成葉節(jié)點(diǎn)。
代碼如下：

def prune(tree, miniGain, evaluationFunction=gini):
    # 剪枝 when gain < mini Gain, 合并（merge the trueBranch and falseBranch）
    if tree.trueBranch.results == None:
        prune(tree.trueBranch, miniGain, evaluationFunction)
    if tree.falseBranch.results == None:
        prune(tree.falseBranch, miniGain, evaluationFunction)

    if tree.trueBranch.results != None and tree.falseBranch.results != None:
        len1 = len(tree.trueBranch.data)
        len2 = len(tree.falseBranch.data)
        len3 = len(tree.trueBranch.data + tree.falseBranch.data)

        p = float(len1) / (len1 + len2)

        gain = evaluationFunction(tree.trueBranch.data + tree.falseBranch.data) - p * evaluationFunction(tree.trueBranch.data) - (1 - p) * evaluationFunction(tree.falseBranch.data)

        if gain < miniGain:
            tree.data = tree.trueBranch.data + tree.falseBranch.data
            tree.results = calculateDiffCount(tree.data)
            tree.trueBranch = None
            tree.falseBranch = None

當(dāng)節(jié)點(diǎn)的gain小于給定的 mini Gain時(shí)則合并這兩個(gè)節(jié)點(diǎn).冰蘑。

最后是構(gòu)建樹的代碼：

if __name__ == '__main__':
    dataSet = loadCSV()
    decisionTree = buildDecisionTree(dataSet, evaluationFunction=gini)
    prune(decisionTree, 0.4)
    test_data = [5.9,3,4.2,1.5]
    r = classify(test_data, decisionTree)
    print(r)

可以打印decisionTree可以構(gòu)建出如如上的圖片中的決策樹和泌。
后面找一組數(shù)據(jù)測試看能否得到正確的分類。

完整代碼和數(shù)據(jù)集請查看：
github：CART

總結(jié)：

• CART決策樹
• 分割數(shù)據(jù)集
• 遞歸創(chuàng)建樹

參考文章：
CART分類回歸樹分析與python實(shí)現(xiàn)
CART決策樹(Decision Tree)的Python源碼實(shí)現(xiàn)