決策樹(shù)算法總結(jié)

1、決策樹(shù)研發(fā)二部武漢中原電子信息有限公司文件狀態(tài)：文件標(biāo)識(shí)： 草稿當(dāng)前版本：1.0 正式發(fā)布作者：張宏超正在修改完成日期：2019年3月8日目錄1. 算法介紹11.1. 分支節(jié)點(diǎn)選取 11.2. 構(gòu)建樹(shù)31.3. 剪枝102. sk-learn 中的使用 123. sk-learn中源碼分析 131. 算法介紹決策樹(shù)算法是機(jī)器學(xué)習(xí)中的經(jīng)典算法之一，既可以作為分類(lèi)算法，也可以作為回歸算法。決策樹(shù)算法又被發(fā)展出很多不同的版本，按照時(shí)間上分，目前主要 包括，ID3、C4.5和CART版本算法。其中ID3版本的決策樹(shù)算法是最早出現(xiàn)的， 可以用來(lái)做分類(lèi)算法。C4.5是針對(duì)ID3的不足出現(xiàn)的優(yōu)化版本，也用來(lái)

2、做分類(lèi)。 CART也是針對(duì)ID3優(yōu)化出現(xiàn)的，既可以做分類(lèi)，可以做回歸。決策樹(shù)算法的本質(zhì)其實(shí)很類(lèi)似我們的if-elseif-else語(yǔ)句，通過(guò)條件作為分支依 據(jù)，最終的數(shù)學(xué)模型就是一顆樹(shù)。不過(guò)在決策樹(shù)算法中我們需要重點(diǎn)考慮選取分 支條件的理由，以及誰(shuí)先判斷誰(shuí)后判斷，包括最后對(duì)過(guò)擬合的處理，也就是剪枝。 這是我們之前寫(xiě)if語(yǔ)句時(shí)不會(huì)考慮的問(wèn)題。決策樹(shù)算法主要分為以下3個(gè)步驟：1. 分支節(jié)點(diǎn)選取2. 構(gòu)建樹(shù)3. 剪枝1.1. 分支節(jié)點(diǎn)選取分支節(jié)點(diǎn)選取，也就是尋找分支節(jié)點(diǎn)的最優(yōu)解。既然要尋找最優(yōu)，那么必須 要有一個(gè)衡量標(biāo)準(zhǔn)，也就是需要量化這個(gè)優(yōu)劣性。常用的衡量指標(biāo)有熵和基尼系 數(shù)。熵：熵用來(lái)表示信息的

3、混亂程度，值越大表示越混亂，包含的信息量也就越 多。比如，A班有10個(gè)男生1個(gè)女生，B班有5個(gè)男生5個(gè)女生，那么B班的熵 值就比A班大，也就是B班信息越混亂。Entropy = -V p ”基尼系數(shù)：同上，也可以作為信息混亂程度的衡量指標(biāo)。Gini = 1 - p：l-L有了量化指標(biāo)后，就可以衡量使用某個(gè)分支條件前后，信息混亂程 度的收斂效果了。使用分支前的混亂程度，減去分支后的混亂程度， 結(jié)果越大，表示效果越好。#計(jì)算熵值def entropy(dataSet):tNum = len (dataSet)print (tNum)#用來(lái)保存標(biāo)簽對(duì)應(yīng)的個(gè)數(shù)的，比如，男：6,女：5labels =

4、for node in dataSet:curL = node-1#獲取標(biāo)簽if curL not in labels.keys():labelscurL =0#如果沒(méi)有記錄過(guò)該種標(biāo)簽，就記錄并初始化為0labelscurL +=1#將標(biāo)簽記錄個(gè)數(shù)加1#此時(shí)labels中保存了所有標(biāo)簽和對(duì)應(yīng)的個(gè)數(shù)res =0#計(jì)算公式為-p*logp，p為標(biāo)簽出現(xiàn)概率for node in labels:p = float (labels no de) / tNumres -= p * log(p,2)return res#計(jì)算基尼系數(shù)def gini(dataSet):tNum = len (dataSet

5、)print (tNum)#用來(lái)保存標(biāo)簽對(duì)應(yīng)的個(gè)數(shù)的，比如，男：6,女：5labels = for node in dataSet:curL = node-1# 獲取標(biāo)簽if curL not in labels.keys():labelscurL =0 #如果沒(méi)有記錄過(guò)該種標(biāo)簽，就記錄并初始化為0labelscurL +=1#將標(biāo)簽記錄個(gè)數(shù)加1# 此時(shí)labels中保存了所有標(biāo)簽和對(duì)應(yīng)的個(gè)數(shù)res =1#計(jì)算公式為-p*logp , p為標(biāo)簽出現(xiàn)概率for node in labels:p = float (labels no de)/ tNumres -= p * preturn res1

6、.2. 構(gòu)建樹(shù)ID3算法：利用信息熵增益，決定選取哪個(gè)特征作為分支節(jié)點(diǎn)。分支前的總樣本 熵值-分支后的熵值總和=信息熵增益。T1的信息熵增益：1 -13/20*0.961 - 7/20*0.863 = 0.073T2的信息熵增益：1 -12/20*0.812 - 8/20*0.544 = 0.295所以使用T2作為分支特征更優(yōu)ID3算法建樹(shù)：依據(jù)前面的邏輯，遞歸尋找最優(yōu)分支節(jié)點(diǎn)，直到下面情況結(jié)束1. 葉節(jié)點(diǎn)已經(jīng)屬于同一標(biāo)簽2. 雖然葉節(jié)點(diǎn)不屬于同一標(biāo)簽，但是特征已經(jīng)用完了3. 熵小于預(yù)先設(shè)置的閾值4. 樹(shù)的深度達(dá)到了預(yù)先設(shè)置的閾值ID3算法的不足：1. 取值多的特征比取值少的特征更容易被選取。

7、2. 不包含剪枝操作，過(guò)擬合嚴(yán)重3. 特征取值必須是離散的，或者有限的區(qū)間的。于是有了改進(jìn)算法C4.5C4.5算法：基于ID3算法進(jìn)行了改進(jìn)，首先，針對(duì)ID3的不足1,采用信息增益 率取代ID3中使用信息增益而造成的偏向于選取取值較多的特征作為分裂點(diǎn)的問(wèn) 題。針對(duì)ID3的不足2,采用剪枝操作，緩解過(guò)擬合問(wèn)題。針對(duì)ID3的不足3,采 用將連續(xù)值先排列，然后逐個(gè)嘗試分裂，找到連續(xù)值中的最佳分裂點(diǎn)。信息增益率的計(jì)算：先計(jì)算信息增益，然后除以splitelnfo。spliteInfo為分裂后的 子集合的函數(shù)，假設(shè)分裂后的子集合個(gè)數(shù)為subl和sub2, total為分裂前的個(gè)數(shù)。spliteInfo

8、= -sub1 / total * Iog(sub1 / total) -sub2 / total * Iog(sub2 / total)#index:特征序號(hào)#value:特征值#該方法表示將index對(duì)應(yīng)特征的值為value的集合返回，返回集合中不包含index對(duì)應(yīng) 的特征def spliteDataSet(dataSet, index, value):n ewDataSet =for node in dataSet:if no dei ndex = value:#0,index)列的數(shù)據(jù)n ewData = no de:i ndex#index+1,最后列的數(shù)據(jù)n ewData.exte

9、 nd(no dei ndex +1:)n ewDataSet.appe nd(n ewData)returnn ewDataSet;#選擇最優(yōu)分裂項(xiàng)def chooseBestFeature(dataSet):#特征個(gè)數(shù)featureNum = len (dataSet 0) -1#計(jì)算整體樣本的熵值baseE ntropy = en tropy(dataSet)武漢中原電子信息有限公司4print ("baseEntropy = %f" %(baseEntropy)#保存最大的信息增益率maxi nfoGai nRatio =0.0bestFeatureld = -1f

10、or i in range (featureNum):#獲取特征所有可能的值featureValues =for node in dataSet:featureValues.appe nd(no dei)print (featureValues)#將特征值去除重復(fù)uniqueFeatureValues = set (featureValues)print (uniqueFeatureValues)#按照i特征分裂之后的熵值n ewE ntropy = 0.0#分裂信息splitei nfo =0.0#按照i所表示的特征，開(kāi)始分裂數(shù)據(jù)集for value in uniqueFeatureValu

11、es:#當(dāng)i屬性等于value時(shí)的分裂結(jié)果subDataSet = spliteDataSet(dataSet, i, value)print (subDataSet)#計(jì)算占比p = float (len (subDataSet) / float (len (dataSet)n ewE ntropy += p * en tropy(subDataSet)splite info += -p * log(p,2)#計(jì)算信息增益in foGai n = baseE ntropy - n ewE ntropy#計(jì)算信息增益率if splite Info =0:con ti nueinfoGainRa

12、tio = infoGain / spliteinfoif in foGa in Ratio > maxln foGa in Ratio:maxln foGa in Ratio = in foGa in RatiobestFeatureld = ireturn bestFeatureldC4.5算法的不足：1. 如果存在連續(xù)值的特征需要做排序等處理，計(jì)算比較耗時(shí)2. 只能用于分類(lèi)使用于是有了 CART算法CART算法：也是基于ID3算法優(yōu)化而來(lái)，支持分類(lèi)和回歸，使用基尼系數(shù)（分類(lèi) 樹(shù)）或者均方差（回歸樹(shù)）替代熵的作用，減少運(yùn)算難度。使用二叉樹(shù)代替多叉 樹(shù)建模，降低復(fù)雜度。基尼系數(shù)的計(jì)算：

13、EC/均方差的計(jì)算：計(jì)算舉例，假設(shè)有如下數(shù)據(jù)源看電視時(shí)間婚姻情況職業(yè)年齡3未婚學(xué)生124未婚學(xué)生182已婚老師265已婚上班族472.5已婚上班族363.5未婚老師294已婚學(xué)生21如果將婚否作為標(biāo)簽，該問(wèn)題是一個(gè)分類(lèi)問(wèn)題，所以使用基尼系數(shù)假設(shè)使用職業(yè)作為特征分支，對(duì)于看電視和年齡，都是連續(xù)數(shù)據(jù)，需要按照C4.5的算法排序后處理，這里先分析簡(jiǎn)單的按照職業(yè)開(kāi)始劃分。又因?yàn)椋珻ART算法的建模是二叉樹(shù)，所以，針對(duì)職業(yè)來(lái)說(shuō)，有以下組合，學(xué)生|非學(xué)生，老師|非老師，上班族|非上班族，到底怎么劃分，就要通過(guò)基尼系數(shù)來(lái) 判斷了。尹*| V基1 /125'上雜42P |tun 15-St*岳牲，昭1

14、1.*S*n.2V 1gini = 3 / 7 * (1-2 / 3 * 2 /3-1 / 3 * 1 / 3) + 4 / 7 * (13 / 4 * 3 / 4-1 / 4 * 1 / 4) = 0.4基* iff卒冏2-418*'r 8r s- nI r上販上鮒匸岳4SIVgini = 2 / 7 * (1-1 / 2 * 1 / 2屈已It1 h星.血遲艇低丨翊+如IX召.1上贓是1-1 / 2 * 1 / 2) + 5 / 7(1-2 / 5 * 2 / 5-3 / 5 * 3 / 5) = 0.49牡.犠|$=1*13-捋強(qiáng)是上瞧4?.25-8弄29*12Vgini = 2

15、 / 7 * (1-1 * 1) + 5 / 7 * (1千許1 乂1上珈匸251-顯畏別【1S8!6.a雜.1扭是tfjt#-妙11單冬5 * 2 / 5) = 0.34所以，如果選擇職業(yè)來(lái)劃分，那么首先應(yīng)該按照上班族 |非上班族劃分如果將年齡作為標(biāo)簽，該問(wèn)題是一個(gè)回歸問(wèn)題，所以使用均方差同樣，先考慮使用職業(yè)來(lái)劃分野己臨|I?払做1aU-r卷:爆I1r技廠2&$山i弄1L駢|421- I鮭己鼻U稗!5*12-*X?加A31mea n =開(kāi)方(12 * 12 + 18 * 18 + 21 * 21 -3 * 17 * 17) + 開(kāi)方(26 * 26 + 47 * 47 + 36 *

16、36 + 29 * 29 -5 * 32.5 * 32.5) = 34.71其他情況略。>>II I III II I可以看到選擇分裂屬性這一步驟會(huì)比較麻煩，首先要遍歷所有特征, 找到每一個(gè)特征的最優(yōu)分裂方法，然后在選擇最優(yōu)的分裂特征。功能樹(shù)結(jié)構(gòu)特征選取連續(xù)值處理缺失值處理剪枝ID3分類(lèi)多叉信息增益不支持不支持不支持C4.5 分類(lèi)多叉信息增益率支持支持支持CART分類(lèi)/回歸 二叉基尼系數(shù)（分支持支持支持類(lèi)），均方差（回歸）1.3. 剪枝CCP(Cost Complexity Pruning 代價(jià)復(fù)雜性剪枝法(CART常用)REP( Reduced Error Pruning 錯(cuò)誤降

17、低剪枝法PEP(Pessimistic Error Pruning 悲觀錯(cuò)誤剪枝法(C4.5使用)MEP (Minimum Error Pruning)最小錯(cuò)誤剪枝法這里以CCP為例講解其原理CCP選擇節(jié)點(diǎn)表面誤差率增益值最小的非葉子節(jié)點(diǎn)，刪除該節(jié)點(diǎn)的子節(jié)點(diǎn)。若多 個(gè)非葉子節(jié)點(diǎn)的表面誤差率增益值相同，則選擇子節(jié)點(diǎn)最多的非葉子節(jié)點(diǎn)進(jìn)行裁 剪。表面誤差率增益值計(jì)算：R(t)表示非葉子節(jié)點(diǎn)的錯(cuò)誤率，比如，總樣本20，在A節(jié)點(diǎn)上a類(lèi)5個(gè)，b類(lèi)2個(gè)，所以可以認(rèn)為A節(jié)點(diǎn)代表的是a類(lèi)，那么錯(cuò)誤率就是2 / 7 * 7 / 20R(T表示葉子節(jié)點(diǎn)的錯(cuò)誤率累積和N(T表示葉子節(jié)點(diǎn)的個(gè)數(shù) 剪枝步驟：1. 構(gòu)建子樹(shù)

18、序列2. 找到最優(yōu)子樹(shù)，作為我們的決策樹(shù)(交叉驗(yàn)證等)舉例:t1是根節(jié)點(diǎn)t2, t3 , t4 , t5是非葉子節(jié)點(diǎn)t6, t7 , t8 , t9 , t10, t11 是葉子節(jié)點(diǎn)首先我們計(jì)算所有非葉子節(jié)點(diǎn)誤差率增益值t4: (4/50 * 50/80 T/45 * 45/80 -2/5 * 5/80)/ (2 T) = 0.0125t5:(4/10 * 10/80 -0 - 0) / (2 - 1) = 0.05t2:(10/60 * 60/80 -1/45 * 45/80 -2/5 * 5/80 -0 - 0) / (4 - 1) = 0.0292t3:0.0375因此得到第 1 顆子樹(shù)

19、：T0 = t4（0.0125），t5（0.05），t2（0.0292），t3（0.0375）比較發(fā)現(xiàn)可以將t4裁剪掉得到第2顆子樹(shù)t5: 0.05t3: 0.0375t2: (10/60 * 60/80 -4/50 * 50/80 -0 - 0) / (3 -1) = 0.0375此時(shí)t2與t3相同，那么裁剪葉子節(jié)點(diǎn)較多的，因此t2被裁剪得到第3顆樹(shù)然后對(duì)上面3顆子樹(shù)進(jìn)行驗(yàn)證，找到效果最后的作為剪枝之后的決策樹(shù)2. sk-learn中的使用from sklearn.datasetsimport load_irisfrom sklearn import treeimport pydotplus

20、import graphviz iris = load_iris()clf = tree.Decisi on TreeClassifier()clf.fit(iris.data, iris.target)dot_data = tree.export_graphviz(clf,out_file =None)graph = pydotplus.graph from dot data(dot data) graph.write_pdf( "iris.pdf" )3. sk-learn中源碼分析主要分析tree的相關(guān)函數(shù)代碼，使用pycharm下載sklearn包中tree文件，

21、引用了 _tree.pxd, pxd相當(dāng)于頭文件，其實(shí)現(xiàn)在_tree.pyd中，pyd是加密文件，無(wú) 法查看。從github上下載源碼中有_tree.pyx相當(dāng)于c文件，因此可以查看。.pxd:相當(dāng)于.h.pyx:相當(dāng)于.c.pyd:相當(dāng)于dlltree.Decisio nTreeClassifier()創(chuàng)建分類(lèi)決策樹(shù)對(duì)象Decisi on TreeClassifie 繼承 BaseDecisi on Treeclf.fit(iris.data, iris.target)建樹(shù)DecisionTreeClassifier直接使用了父類(lèi) BaseDecisionTree 的方法super().fi

22、t(X, y,sample_weight=sample_weight,check_ in put=check_ in put,X_idx_sorted=X_idx_sorted)查看DecisionTreeClassifier的fit，學(xué)習(xí)建樹(shù)過(guò)程代碼前面是對(duì)參數(shù)的校驗(yàn)之類(lèi)的工作# Build tree criterion = self cui匸EEion if not isinstance(criterion, Criterion):if: 皿： - - ciitex J-Qn = CKITER1A_REG self, criterion (slf , n_oututs , n_sanipl

23、e3)criterion = CRITERIA 'LF telf , criterion J (self .r_outpts * self *r classes >= mt且mm刁 L?t_2'rif ims匸wr三三(x) else 二巴Km 5 p_.ltsplitter = self,splitterif not isinatancat _splitter, £p丄ititer)jpTrEter = SPLITTERS se If, sp 1 iTtwJ；£criterion, s e 1 f . mamin samplss leaf f mir

24、_weight_leaf； randomstate t self.presort)criterion:表示選擇分裂節(jié)點(diǎn)的準(zhǔn)則，CLF表示分類(lèi)使用gini系數(shù)、熵等，REG表示回歸使用均方差等。他們的定義在criteria_clf I "rfi r;11 : _crireri on .Gini t ' r t rr.f y" : _criterion. Entropy3 CRITE Rl A_RE G "mse": _ariterion.MSEF iLdmajQ_mj= c1h ： criterion * FriedmanMSE,"m"： elite 上 ictrl.MAE)對(duì)于這些準(zhǔn)則的計(jì)算，在_criterion.Gini或者其他文件中實(shí)現(xiàn)，使用Cpython實(shí)現(xiàn)的。以Gini的計(jì)算為