怎么用Python實(shí)現(xiàn)CART決策樹(shù)算法

這篇文章主要講解了“怎么用Python實(shí)現(xiàn)CART決策樹(shù)算法”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“怎么用Python實(shí)現(xiàn)CART決策樹(shù)算法”吧！

一、CART決策樹(shù)算法簡(jiǎn)介

CART（Classification And Regression Trees 分類回歸樹(shù)）算法是一種樹(shù)構(gòu)建算法，既可以用于分類任務(wù)，又可以用于回歸。相比于 ID3 和 C4.5 只能用于離散型數(shù)據(jù)且只能用于分類任務(wù)，CART 算法的適用面要廣得多，既可用于離散型數(shù)據(jù)，又可以處理連續(xù)型數(shù)據(jù)，并且分類和回歸任務(wù)都能處理。

本文僅討論基本的CART分類決策樹(shù)構(gòu)建，不討論回歸樹(shù)和剪枝等問(wèn)題。

首先，我們要明確以下幾點(diǎn)：
1. CART算法是二分類常用的方法，由CART算法生成的決策樹(shù)是二叉樹(shù)，而 ID3 以及 C4.5 算法生成的決策樹(shù)是多叉樹(shù)，從運(yùn)行效率角度考慮，二叉樹(shù)模型會(huì)比多叉樹(shù)運(yùn)算效率高。
2. CART算法通過(guò)基尼(Gini)指數(shù)來(lái)選擇最優(yōu)特征。

二、基尼系數(shù)

基尼系數(shù)代表模型的不純度，基尼系數(shù)越小，則不純度越低，注意這和 C4.5的信息增益比的定義恰好相反。

分類問(wèn)題中，假設(shè)有K個(gè)類，樣本點(diǎn)屬于第k類的概率為pk，則概率分布的基尼系數(shù)定義為:

若CART用于二類分類問(wèn)題（不是只能用于二分類），那么概率分布的基尼系數(shù)可簡(jiǎn)化為

假設(shè)使用特征 A 將數(shù)據(jù)集 D 劃分為兩部分 D1 和 D2，此時(shí)按照特征 A 劃分的數(shù)據(jù)集的基尼系數(shù)為：

三、CART決策樹(shù)生成算法

輸入：訓(xùn)練數(shù)據(jù)集D，停止計(jì)算的條件
輸出：CART決策樹(shù)
根據(jù)訓(xùn)練數(shù)據(jù)集，從根結(jié)點(diǎn)開(kāi)始，遞歸地對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行以下操作，構(gòu)建二叉決策樹(shù)：
（1）計(jì)算現(xiàn)有特征對(duì)該數(shù)據(jù)集的基尼指數(shù)，如上面所示；
（2）選擇基尼指數(shù)最小的值對(duì)應(yīng)的特征為最優(yōu)特征，對(duì)應(yīng)的切分點(diǎn)為最優(yōu)切分點(diǎn)（若最小值對(duì)應(yīng)的特征或切分點(diǎn)有多個(gè)，隨便取一個(gè)即可）；
（3）按照最優(yōu)特征和最優(yōu)切分點(diǎn)，從現(xiàn)結(jié)點(diǎn)生成兩個(gè)子結(jié)點(diǎn)，將訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)按特征和屬性分配到兩個(gè)子結(jié)點(diǎn)中；
（4）對(duì)兩個(gè)子結(jié)點(diǎn)遞歸地調(diào)用（1）（2）（3），直至滿足停止條件。
（5）生成CART樹(shù)。
算法停止的條件：結(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閾值，或樣本集的基尼指數(shù)小于預(yù)定閾值（樣本基本屬于同一類，如完全屬于同一類則為0），或者特征集為空。
注：最優(yōu)切分點(diǎn)是將當(dāng)前樣本下分為兩類（因?yàn)槲覀円獦?gòu)造二叉樹(shù)）的必要條件。對(duì)于離散的情況，最優(yōu)切分點(diǎn)是當(dāng)前最優(yōu)特征的某個(gè)取值；對(duì)于連續(xù)的情況，最優(yōu)切分點(diǎn)可以是某個(gè)具體的數(shù)值。具體應(yīng)用時(shí)需要遍歷所有可能的最優(yōu)切分點(diǎn)取值去找到我們需要的最優(yōu)切分點(diǎn)。

四、CART算法的Python實(shí)現(xiàn)

若是二分類問(wèn)題，則函數(shù)calcGini和choose_best_feature可簡(jiǎn)化如下：

# 計(jì)算樣本屬于第1個(gè)類的概率p
def calcProbabilityEnt(dataset):
    numEntries = len(dataset)
    count = 0
    label = dataset[0][len(dataset[0]) - 1]
    for example in dataset:
        if example[-1] == label:
            count += 1
    probabilityEnt = float(count) / numEntries
    return probabilityEnt

def choose_best_feature(dataset):
    # 特征總數(shù)
    numFeatures = len(dataset[0]) - 1
    # 當(dāng)只有一個(gè)特征時(shí)
    if numFeatures == 1:
        return 0
    # 初始化最佳基尼系數(shù)
    bestGini = 1
    # 初始化最優(yōu)特征
    index_of_best_feature = -1
    for i in range(numFeatures):
        # 去重，每個(gè)屬性值唯一
        uniqueVals = set(example[i] for example in dataset)
        # 定義特征的值的基尼系數(shù)
        Gini = {}
        for value in uniqueVals:
            sub_dataset1, sub_dataset2 = split_dataset(dataset,i,value)
            prob1 = len(sub_dataset1) / float(len(dataset))
            prob2 = len(sub_dataset2) / float(len(dataset))
            probabilityEnt1 = calcProbabilityEnt(sub_dataset1)
            probabilityEnt2 = calcProbabilityEnt(sub_dataset2)
            Gini[value] = prob1 * 2 * probabilityEnt1 * (1 - probabilityEnt1) + prob2 * 2 * probabilityEnt2 * (1 - probabilityEnt2)
            if Gini[value] < bestGini:
                bestGini = Gini[value]
                index_of_best_feature = i
                best_split_point = value
    return index_of_best_feature, best_split_point

五、運(yùn)行結(jié)果

感謝各位的閱讀，以上就是“怎么用Python實(shí)現(xiàn)CART決策樹(shù)算法”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)怎么用Python實(shí)現(xiàn)CART決策樹(shù)算法這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！