一、CART決策樹算法簡介

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

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

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

二、基尼系數(shù)

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

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

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

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

三、CART決策樹生成算法

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

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

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

# 計算樣本屬于第1個類的概率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)只有一個特征時
 if numFeatures == 1:
  return 0
 # 初始化最佳基尼系數(shù)
 bestGini = 1
 # 初始化最優(yōu)特征
 index_of_best_feature = -1
 for i in range(numFeatures):
  # 去重，每個屬性值唯一
  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

五、運行結(jié)果

到此這篇關(guān)于Python實現(xiàn)CART決策樹算法及詳細(xì)注釋的文章就介紹到這了,更多相關(guān)Python策樹算法內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非maisonbaluchon.cn所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。