CART（決策分類樹）原理和實(shí)現(xiàn)

CART（決策分類樹）原理和實(shí)現(xiàn)前面我們了解了決策樹和adaboost的決策樹墩的原理和實(shí)現(xiàn)，在adaboost我們看到，用簡單的決策樹墩的效果也很不錯(cuò)，但是對于更多特征的樣本來說，可能需要很多數(shù)量的決策樹墩或許我們可以考慮使用更加高級的弱分類器，下面我們看下CART（ClassificationAndRegressionTree）的原理和實(shí)現(xiàn)吧CART也是決策樹的一種，不過是滿二叉樹，CART可以是強(qiáng)分類器，就跟決策樹一樣，但是我們可以指定CART的深度，使之成為比較弱的分類器CART生成的過程和決策樹類似，也是采用遞歸劃分的，不過也存在很多的不同之處數(shù)據(jù)集：第一列為樣本名稱，最后一列為類別，中間為特征humanconstanthairtruefalsefalsefalsetruefalsemammalpythoncold_bloodscalefalsetruefalsefalsefalsetruereptilesalmoncold_bloodscalefalsetruefalsetruefalsefalsefishwhaleconstanthairtruefalsefalsetruefalsefalsemammalfrogcold_bloodnonefalsetruefalsesometimetruetrueamphibiouslizardcold_bloodscalefalsetruefalsefalsetruefalsereptilebatconstanthairtruefalsetruefalsetruefalsemammalcatconstantskintruefalsefalsefalsetruefalsemammalsharkcold_bloodscaletruefalsefalsetruefalsefalsefishturtlecold_bloodscalefalsetruefalsesometimetruefalsereptilepigconstantbristletruefalsefalsefalsetruetruemammaleelcold_bloodscalefalsetruefalsetruefalsefalsefishsalamandercold_bloodnonefalsetruefalsesometimetruetrueamphibious

特征名稱如下["temperature","cover","viviparity","egg","fly","water","leg","hibernate"]

1：數(shù)據(jù)集劃分評分CART使用gini系數(shù)來衡量數(shù)據(jù)集的劃分效果而不是香農(nóng)熵（借用下面的一張圖）defcalGini(dataSet):numEntries=len(dataSet)labelCounts={}forfeatVecindataSet:currentLabel=featVec[-1]ifcurrentLabelnotinlabelCounts.keys():labelCounts[currentLabel]=0labelCounts[currentLabel]+=1gini=1forlabelinlabelCounts.keys():prop=float(labelCounts[label])/numEntriesgini-=prop*propreturngini

2：數(shù)據(jù)集劃分決策樹是遍歷每一個(gè)特征的特征值，每個(gè)特征值得到一個(gè)劃分，然后計(jì)算每個(gè)特征的信息增益從而找到最優(yōu)的特征；CART每一個(gè)分支都是二分的，當(dāng)特征值大于兩個(gè)的時(shí)候，需要考慮特征值的組合得到兩個(gè)“超級特征值”作為CART的分支；當(dāng)然我們也可以偷懶，每次只取多個(gè)特征值的一個(gè)，挑出最優(yōu)的一個(gè)和剩下的分別作為一個(gè)分支，但無疑這得到的cart不是最優(yōu)的#傳入的是一個(gè)特征值的列表，返回特征值二分的結(jié)果deffeaturesplit(features):count=len(features)#特征值的個(gè)數(shù)ifcount<2:print"pleasechecksample'sfeatures,onlyonefeaturevalue"return-1#由于需要返回二分結(jié)果，所以每個(gè)分支至少需要一個(gè)特征值，所以要從所有的特征組合中選取1個(gè)以上的組合#itertools的combinations函數(shù)可以返回一個(gè)列表選多少個(gè)元素的組合結(jié)果，例如combinations(list,2)返回的列表元素選2個(gè)的組合#我們需要選擇1-（count-1）的組合featureIndex=range(count)featureIndex.pop(0)combinationsList=[]resList=[]#遍歷所有的組合foriinfeatureIndex:temp_combination=list(combinations(features,len(features[0:i])))combinationsList.extend(temp_combination)combiLen=len(combinationsList)#每次組合的順序都是一致的，并且也是對稱的，所以我們?nèi)∈孜步M合集合#zip函數(shù)提供了兩個(gè)列表對應(yīng)位置組合的功能resList=zip(combinationsList[0:combiLen/2],combinationsList[combiLen-1:combiLen/2-1:-1])returnresList

得到特征的劃分結(jié)果之后，我們使用二分后的特征值劃分?jǐn)?shù)據(jù)集defsplitDataSet(dataSet,axis,values):retDataSet=[]forfeatVecindataSet:forvalueinvalues:iffeatVec[axis]==value:reducedFeatVec=featVec[:axis]#剔除樣本集reducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)returnretDataSet遍歷每個(gè)特征的每個(gè)二分特征值，得到最好的特征以及二分特征值#返回最好的特征以及二分特征值defchooseBestFeatureToSplit(dataSet):numFeatures=len(dataSet[0])-1#bestGiniGain=1.0;bestFeature=-1;bestBinarySplit=()foriinrange(numFeatures):#遍歷特征featList=[example[i]forexampleindataSet]#得到特征列uniqueVals=list(set(featList))#從特征列獲取該特征的特征值的set集合#三個(gè)特征值的二分結(jié)果：#[(('young',),('old','middle')),(('old',),('young','middle')),(('middle',),('young','old'))]forsplitinfeaturesplit(uniqueVals):GiniGain=0.0iflen(split)==1:continue(left,right)=split#對于每一個(gè)可能的二分結(jié)果計(jì)算gini增益#左增益left_subDataSet=splitDataSet(dataSet,i,left)left_prob=len(left_subDataSet)/float(len(dataSet))GiniGain+=left_prob*calGini(left_subDataSet)#右增益right_subDataSet=splitDataSet(dataSet,i,right)right_prob=len(right_subDataSet)/float(len(dataSet))GiniGain+=right_prob*calGini(right_subDataSet)if(GiniGain<=bestGiniGain):#比較是否是最好的結(jié)果bestGiniGain=GiniGain#記錄最好的結(jié)果和最好的特征bestFeature=ibestBinarySplit=(left,right)returnbestFeature,bestBinarySplit

所有特征用完時(shí)多數(shù)表決程序defmajorityCnt(classList):classCount={}forvoteinclassList:ifvotenotinclassCount.keys():classCount[vote]=0classCount[vote]+=1sortedClassCount=sorted(classCount.iteritems(),key=mgetter(1),reverse=True)returnsortedClassCount[0][0]現(xiàn)在來生成cart吧

defcreateTree(dataSet,labels):classList=[example[-1]forexampleindataSet]#printdataSetifclassList.count(classList[0])==len(classList):returnclassList[0]#所有的類別都一樣，就不用再劃分了iflen(dataSet)==1:#如果沒有繼續(xù)可以劃分的特征，就多數(shù)表決決定分支的類別#print"here"returnmajorityCnt(classList)bestFeat,bestBinarySplit=chooseBestFeatureToSplit(dataSet)#printbestFeat,bestBinarySplit,labelsbestFeatLabel=labels[bestFeat]ifbestFeat==-1:returnmajorityCnt(classList)myTree={bestFeatLabel:{}}featValues=[example[bestFeat]forexampleindataSet]uniqueVals=list(set(featValues))forvalueinbestBinarySplit:subLabels=labels[:]##拷貝防止其他地方修改iflen(value)<2:del(subLabels[bestFeat])myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)returnmyTree

看下效果，左邊是cart，右邊是決策樹，（根節(jié)點(diǎn)用cover和temperature是一樣的，為了對比決策樹，此時(shí)我選了cover），第三個(gè)圖是temperature作為根節(jié)點(diǎn)的cart上面的代碼是不考慮特征繼續(xù)使用的，也就是每個(gè)特征只使用一次；但是我們發(fā)現(xiàn)有些有些分支里面特征值個(gè)數(shù)多余兩個(gè)的，其實(shí)我們應(yīng)該讓這些特征繼續(xù)參與下一次的劃分可以發(fā)現(xiàn)，temperature作為根節(jié)點(diǎn)的cart沒有變化，而cover作為根節(jié)點(diǎn)的cart深度變淺了，并且cover特征出現(xiàn)了兩次（或者說效果變好了）

下面是有變化的代碼特征值多余兩個(gè)的分支保留特征值defsplitDataSet(dataSet,axis,values):retDataSet=[]iflen(values)<2:forfeatVecindataSet:iffeatVec[axis]==values[0]:#如果特征值只有一個(gè)，不抽取當(dāng)選特征reducedFeatVec=featVec[:axis]reducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)else:forfeatVecindataSet:forvalueinvalues:iffeatVec[axis]==value:#如果特征值多于一個(gè)，選取當(dāng)前特征retDataSet.append(featVec)returnretDataSet

createTree函數(shù)for循環(huán)判斷是否需要移除當(dāng)前最優(yōu)特征forvalueinbestBinarySplit:iflen(value)<2:del(labels[bestFeat])subLab