決策樹算法總結(jié)

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

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

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

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

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

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

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

8、= -sub1 / total * Iog(sub1 / total) -sub2 / total * Iog(sub2 / total)#index:特征序號#value:特征值#該方法表示將index對應(yīng)特征的值為value的集合返回，返回集合中不包含index對應(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)分裂項def chooseBestFeature(dataSet):#特征個數(shù)featureNum = len (dataSet 0) -1#計算整體樣本的熵值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所表示的特征，開始分裂數(shù)據(jù)集for value in uniqueFeatureValu

11、es:#當(dāng)i屬性等于value時的分裂結(jié)果subDataSet = spliteDataSet(dataSet, i, value)print (subDataSet)#計算占比p = float (len (subDataSet) / float (len (dataSet)n ewE ntropy += p * en tropy(subDataSet)splite info += -p * log(p,2)#計算信息增益in foGai n = baseE ntropy - n ewE ntropy#計算信息增益率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ù)值的特征需要做排序等處理，計算比較耗時2. 只能用于分類使用于是有了 CART算法CART算法：也是基于ID3算法優(yōu)化而來，支持分類和回歸，使用基尼系數(shù)（分類 樹）或者均方差（回歸樹）替代熵的作用，減少運算難度。使用二叉樹代替多叉 樹建模，降低復(fù)雜度?；嵯禂?shù)的計算：

13、EC/均方差的計算：計算舉例，假設(shè)有如下數(shù)據(jù)源看電視時間婚姻情況職業(yè)年齡3未婚學(xué)生124未婚學(xué)生182已婚老師265已婚上班族472.5已婚上班族363.5未婚老師294已婚學(xué)生21如果將婚否作為標(biāo)簽，該問題是一個分類問題，所以使用基尼系數(shù)假設(shè)使用職業(yè)作為特征分支，對于看電視和年齡，都是連續(xù)數(shù)據(jù)，需要按照C4.5的算法排序后處理，這里先分析簡單的按照職業(yè)開始劃分。又因為，CART算法的建模是二叉樹，所以，針對職業(yè)來說，有以下組合，學(xué)生|非學(xué)生，老師|非老師，上班族|非上班族，到底怎么劃分，就要通過基尼系數(shù)來 判斷了。尹*| 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-捋強是上瞧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è)來劃分，那么首先應(yīng)該按照上班族 |非上班族劃分如果將年齡作為標(biāo)簽，該問題是一個回歸問題，所以使用均方差同樣，先考慮使用職業(yè)來劃分野己臨|I?払做1aU-r卷:爆I1r技廠2&$山i弄1L駢|421- I鮭己鼻U稗!5*12-*X?加A31mea n =開方(12 * 12 + 18 * 18 + 21 * 21 -3 * 17 * 17) + 開方(26 * 26 + 47 * 47 + 36 *

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

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

18、序列2. 找到最優(yōu)子樹，作為我們的決策樹(交叉驗證等)舉例:t1是根節(jié)點t2, t3 , t4 , t5是非葉子節(jié)點t6, t7 , t8 , t9 , t10, t11 是葉子節(jié)點首先我們計算所有非葉子節(jié)點誤差率增益值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 顆子樹

19、：T0 = t4（0.0125），t5（0.05），t2（0.0292），t3（0.0375）比較發(fā)現(xiàn)可以將t4裁剪掉得到第2顆子樹t5: 0.05t3: 0.0375t2: (10/60 * 60/80 -4/50 * 50/80 -0 - 0) / (3 -1) = 0.0375此時t2與t3相同，那么裁剪葉子節(jié)點較多的，因此t2被裁剪得到第3顆樹然后對上面3顆子樹進(jìn)行驗證，找到效果最后的作為剪枝之后的決策樹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)于頭文件，其實現(xiàn)在_tree.pyd中，pyd是加密文件，無 法查看。從github上下載源碼中有_tree.pyx相當(dāng)于c文件，因此可以查看。.pxd:相當(dāng)于.h.pyx:相當(dāng)于.c.pyd:相當(dāng)于dlltree.Decisio nTreeClassifier()創(chuàng)建分類決策樹對象Decisi on TreeClassifie 繼承 BaseDecisi on Treeclf.fit(iris.data, iris.target)建樹DecisionTreeClassifier直接使用了父類 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ù)的校驗之類的工作# 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é)點的準(zhǔn)則，CLF表示分類使用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)對于這些準(zhǔn)則的計算，在_criterion.Gini或者其他文件中實現(xiàn)，使用Cpython實現(xiàn)的。以Gini的計算為