????決策樹類似于數(shù)據(jù)結(jié)構(gòu)中樹地分類思想，經(jīng)常用于分類問題，關(guān)鍵在于信息熵的處理。

? ?整個(gè)算法的過程是一個(gè)遞歸調(diào)用的過程，?訓(xùn)練集就是包含全部訓(xùn)練數(shù)據(jù)樣本，屬性集就是針對(duì)數(shù)據(jù)樣本進(jìn)行特征劃分的判斷條件，類別指的是最后的分類結(jié)果，在算法的過程中一般選取樣本數(shù)據(jù)最多的類作為結(jié)果類別輸出，例如第12行。

????在屬性集A中，已經(jīng)完成劃分了的屬性，將從候選集中扔出，不再參與信息熵的計(jì)算。

????整個(gè)算法最關(guān)鍵的步驟就是第八行：選擇最優(yōu)秀的劃分屬性a*，這個(gè)劃分的選擇分別對(duì)應(yīng)了不同的算法。

????

????在上式中，y表示最終分類的個(gè)數(shù)，pk就是第k類數(shù)據(jù)樣本所占的比例。Ent越小，說明數(shù)據(jù)D的純度越高。

????Dv指的是根據(jù)屬性V分割后所包含的樣本信息，D指的是分割之前的樣本信息，每次劃分完成之后，D就是新的小范圍的樣本了，再計(jì)算同一屬性的信息增益也得重新計(jì)算量，因?yàn)镈發(fā)生了變化。第二輪每個(gè)部分的屬性劃分就不再相同了，因?yàn)槊總€(gè)部分的樣本信息不同，D發(fā)生了改變，信息增益的計(jì)算也就不一樣了。遞歸的思想。

????增益率就是C4.5算法所采用的

????V表示一個(gè)屬性劃分中的選項(xiàng)個(gè)數(shù)，比如顏色包括紅色、黑色、綠色等。一般情況下V越大Ⅳ（a)也就越大，所以增益率可能對(duì)于劃分選項(xiàng)個(gè)數(shù)少的屬性有偏好，C4.5并未完全采用增益率，先從候選屬性當(dāng)中找出信息增益高于平均值的屬性，然后再從中選擇增益率最高的。

????剪枝算法

????剪枝算法是針對(duì)過擬合現(xiàn)象提出來的，因?yàn)闆Q策樹算法是針對(duì)特征屬性進(jìn)行學(xué)習(xí)，可能會(huì)對(duì)訓(xùn)練樣本的特征學(xué)習(xí)過好，導(dǎo)致模型的泛化能力變差。

????剪枝算法中的泛化能力的評(píng)估是在測試集樣本上的準(zhǔn)確率來代替的。

????預(yù)剪枝算法是在劃分之前進(jìn)行計(jì)算判斷，此次劃分對(duì)于模型的泛化能力能否得到提升，如果不能則將此節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn)，不再進(jìn)行劃分，從當(dāng)前分支的樣本數(shù)據(jù)中選擇類別屬性最多的那一個(gè)類作為結(jié)果輸出。

????后剪枝算法則是在決策樹成型之后對(duì)于分支節(jié)點(diǎn)自底向上進(jìn)行篩選，如果發(fā)現(xiàn)將此節(jié)點(diǎn)替換為葉子節(jié)點(diǎn)后可以提升模型的泛化能力，則取消此屬性劃分，將其替換為葉子節(jié)點(diǎn)，并從葉子節(jié)點(diǎn)中選擇數(shù)量最多的那個(gè)類別作為結(jié)果輸出。

????預(yù)剪枝算法會(huì)導(dǎo)致很多分支未展開，屬性劃分沒有用上，降低了過擬合的風(fēng)險(xiǎn)并減少了訓(xùn)練時(shí)間，但是會(huì)帶來欠擬合的風(fēng)險(xiǎn)，模型的性能受限。后剪枝算法會(huì)比預(yù)剪枝算法保留更多的分支，泛化性能也比較好，由于在決策樹構(gòu)建完成后再自底向上的遞歸遍歷，會(huì)使得訓(xùn)練成本顯著提升。

????有很多基礎(chǔ)的算法，比如多變量決策和缺失值決策，在遇到相應(yīng)的實(shí)際問題時(shí)可以進(jìn)一步地去考慮。