決策樹算法總結(jié)

決策樹算法總結(jié)優(yōu)點(diǎn)：計(jì)算復(fù)雜度不高，輸出結(jié)果易于理解，對(duì)中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。缺點(diǎn)：可能會(huì)產(chǎn)生過度匹配問題。適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型。算法工作原理：為了找到?jīng)Q定性特征值，劃分出最好的結(jié)果，我們必須評(píng)估每個(gè)特征。完成測(cè)試后，原始數(shù)據(jù)集被劃分為幾個(gè)數(shù)據(jù)子集。這些數(shù)據(jù)子集會(huì)分布在第一個(gè)決策點(diǎn)的所有分支上。如果某個(gè)數(shù)據(jù)分支下的數(shù)據(jù)屬于同一類型，則當(dāng)前無(wú)需進(jìn)一步對(duì)數(shù)據(jù)集進(jìn)行分割。如果數(shù)據(jù)子集內(nèi)的數(shù)據(jù)不屬于同一類型，則需要重復(fù)劃分?jǐn)?shù)據(jù)子集的過程。如果劃分?jǐn)?shù)據(jù)子集的算法和劃分原始數(shù)據(jù)集的方法相同，直到所有具有相同類型的數(shù)據(jù)均在一個(gè)數(shù)據(jù)子集內(nèi)。偽代碼（函數(shù)createBrabch（））： Ifsoreturn類標(biāo)簽； else 尋找劃分?jǐn)?shù)據(jù)集的最好特征 劃分?jǐn)?shù)據(jù)集 創(chuàng)建分支節(jié)點(diǎn) for每個(gè)劃分的子集 調(diào)用函數(shù)createBrabch并增加返回結(jié)果到分支節(jié)點(diǎn)中 return分支節(jié)點(diǎn)構(gòu)建過程（使用Python語(yǔ)言）：一．在構(gòu)造決策樹時(shí)，我們需要解決的第一個(gè)問題： 當(dāng)前數(shù)據(jù)集上哪個(gè)特征在劃分?jǐn)?shù)據(jù)分類時(shí)起決定性作用為了解決這個(gè)問題，我們先引入幾個(gè)概念：信息：如果待分類的事務(wù)可能劃分在多個(gè)分類之中，則符號(hào)的信息定義為其中是選擇該分類的概率。香農(nóng)熵（簡(jiǎn)稱為熵）：信息的期望值。為了計(jì)算熵，我們需要計(jì)算所有類別所有可能的值包含的信息期望值，通過下面公式可以得到其中n是分類的數(shù)目。信息增益：數(shù)據(jù)集劃分前后信息發(fā)生的變化。程序清單1： 計(jì)算給定數(shù)據(jù)的香農(nóng)熵defcalcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} forfeatVecindataSet: currentLabel=featVec[-1] ifcurrentLabelnotinlabelCounts.keys(): labelCounts[currentLabel]=0 labelCounts[currentLabel]+=1 shannonEnt=0.0 forkeyinlabelCounts: prob=float(labelCounts[key])/numEntries shannonEnt-=prob*log(prob,2) returnshannonEnt二．在學(xué)習(xí)了如何度量數(shù)據(jù)集的無(wú)序程度后，還要?jiǎng)澐謹(jǐn)?shù)據(jù)集，度量劃分?jǐn)?shù)據(jù)集的熵，以便確定當(dāng)前是否正確地劃分了數(shù)據(jù)集。我們將對(duì)每個(gè)特征劃分?jǐn)?shù)據(jù)集的結(jié)果計(jì)算一次信息熵，然后判斷哪個(gè)特征劃分?jǐn)?shù)據(jù)集是最好的劃分方式。程序清單2: 按照給定特征劃分?jǐn)?shù)據(jù)集defsplitDataSet(dataSet,axis,value): retDataSet=[] forfeatVecindataSet: iffeatVec[axis]==value: reducedFeatVec=featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) returnretDataSet三個(gè)輸入?yún)?shù)分別為：待劃分?jǐn)?shù)據(jù)集，劃分?jǐn)?shù)據(jù)集的特征，特征的返回值。注意：extend()和append()方法的使用。程序清單3： 選擇最好的數(shù)據(jù)集劃分方式defchooseBestFeatureToSplit(dataSet): numFeatures=len(dataSet[0])-1 baseEntropy=calcShannonEnt(dataSet) bestInfoGain=0.0 bestFeature=-1 foriinrange(numFeatures): featList=[example[i]forexampleindataSet] uniqueVals=set(featList) newEntropy=0.0 forvalueinuniqueVals: subDataSet=splitDataSet(dataSet,i,value) prob=len(subDataSet)/float(len(dataSet)) newEntropy+=prob*calcShannonEnt(subDataSet) infoGain=baseEntropy-newEntropy if(infoGain>bestInfoGain): bestInfoGain=infoGain bestFeature=i returnbestFeature遍歷整個(gè)數(shù)據(jù)集，循環(huán)計(jì)算香農(nóng)熵和splitDataSet()函數(shù)，找到最好的特征劃分方式。三．學(xué)習(xí)了從數(shù)據(jù)集構(gòu)造決策樹算法所需的子功能模塊后，開始構(gòu)建決策遞歸樹，其工作原理如下：得到原始數(shù)據(jù)，然后基于最好的屬性值劃分?jǐn)?shù)據(jù)集，由于特征值可能有多余兩個(gè)，因此可能存在大于兩個(gè)分支的數(shù)據(jù)集劃分。第一次劃分后，數(shù)據(jù)將被傳遞到樹分支下一個(gè)節(jié)點(diǎn)，在這個(gè)節(jié)點(diǎn)上，我們可以再次劃分?jǐn)?shù)據(jù)。因此我們可以采用遞歸的原則處理數(shù)據(jù)集。 遞歸結(jié)束的條件是：遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，或者每個(gè)分支下的所有實(shí)例都具有相同的分類。如果所有實(shí)例具有相同的分類，則得到一個(gè)葉子節(jié)點(diǎn)或者終止塊。任何到達(dá)葉子節(jié)點(diǎn)的數(shù)據(jù)必然屬于葉子節(jié)點(diǎn)的分類。程序清單4： 選擇出現(xiàn)次數(shù)最多的分類defmajorityCnt(classList): classCount={} forvoteinclassList: ifvotenotinclassCount.keys(): classCount[vote]=0 classCount[vote]+=1 sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True) returnsortedClassCount[0][0]程序清單5： 創(chuàng)建決策樹defcreateTree(dataSet,labels): classList=[example[-1]forexampleindataSet] ifclassList.count(classList[0])==len(classList): print'classListaresame' returnclassList[0] iflen(dataSet[0])==1: print'nofeature' returnmajorityCnt(classList) bestFeat=chooseBestFeatureToSplit(dataSet) bestFeatLabel=labels[bestFeat] myTree={bestFeatLabel:{}} del(labels[bestFeat]) featValues=[example[bestFeat]forexampleindataSet] uniqueVals=set(featValues) forvalueinuniqueVals: subLabels=labels[:] myTree[bestFeatL