AI機器學習-決策樹-python實現CART演算法

CART演算法主要通過基尼係數來做條件選擇，基尼係數的計算公式如下：

其中pk表示第k個樣本所佔的比例

屬性A劃分的子集合的基尼係數為：

其中，V表示屬性A的可能取值。

基於之前的代碼，添加基尼係數的計算方法：

#計算基尼係數

defcalcGini(dataSet):

#獲取數據集的長度

numEntries =len(dataSet)

#定義結果統計對象

resultCounts = {}

#遍曆數據集

fordataItemindataSet:

#獲取當前結果值

currentResult = dataItem[-1]

#統計結果值個數，如果沒有在集合中，統計值為0，否則+1

ifcurrentResultnot inresultCounts:

resultCounts[currentResult] =

resultCounts[currentResult] +=1

#定義基尼係數

giniBase =0.0

#遍歷結果統計集，計算基尼係數

forkeyinresultCounts:

#計算某個結果所佔的比率

prob =float(resultCounts[key])/ numEntries

#計算基尼係數

giniBase +=pow(prob,2)

print("giniBase:"+str(giniBase)+",prob:"+str(prob))

gini =1-giniBase

returngini

再添加計算屬性基尼係數的方法：

#計算以某屬性列為選擇標準的基尼係數

#輸入數據集dataSet,列索引columnIndex

defcalcAttrGini(dataSet,columnIndex):

#獲取第i列的數組信息

columnValues = [example[columnIndex]forexampleindataSet]

#獲取此列的無重複的屬性特徵值

distinctColumnValues =set(columnValues)

attrGini =0.0

fordistinctColumnValueindistinctColumnValues:

subDataSet = splitDataSet(dataSet, columnIndex, distinctColumnValue)

prob =len(subDataSet) /float(len(dataSet))

entItem = prob * calcGini(subDataSet)

print("giniItem:"+str(entItem)+",prob:"+str(prob)+",subGini:"+str(calcGini(subDataSet)))

attrGini += entItem

returnattrGini

然後添加通過基尼係數做特徵選擇，選擇基尼係數小的優先

#用CART演算法，通過信息增益率做特徵選擇，返回屬性列index

defchooseBestFeatureToSplit3(dataSet):

numFeatures =len(dataSet[]) -1#獲取數據集列數，因為要從0開始所以減1

bestGini =0.0

bestFeature = -1

#從0開始遍曆數據集列

forcolumnIndexinrange(numFeatures):

attrGini = calcAttrGini(dataSet,columnIndex)

print("columIndex:"+str(columnIndex)+"attrGini:"+str(attrGini))

ifattrGini

bestGini = attrGini

bestFeature = columnIndex

returnbestFeature

最後重構決策樹創建方法，添加CART演算法支持

ifmethod =="CART":

bestFeatColumnIndex = chooseBestFeatureToSplit3(dataSet)# CART演算法獲取最佳分支屬性列索引

最後在主方法中進行調用測試

myTree = createTree(data, label,"CART")

運行後生成的樹結構，可以發現這個樹結構與ID3演算法一致，可見CART演算法也有它的局限性

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！