數(shù)據(jù)挖掘十大經(jīng)典算法之 C4.5

一雨涛、引入——決策樹（分類部分）

決策樹是一種基本的分類與回歸方法，這一節(jié)主要圍繞分類來展開。

決策樹是一種機(jī)器學(xué)習(xí)的方法职抡，它是一種樹形結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)屬性上的判斷误甚，每個(gè)分支代表一個(gè)判斷結(jié)果的輸出缚甩，最后每個(gè)葉節(jié)點(diǎn)代表一種分類結(jié)果。

決策樹是有監(jiān)督的學(xué)習(xí)窑邦，監(jiān)管學(xué)習(xí)就是給出一堆樣本擅威，每個(gè)樣本都有一組屬性和一個(gè)分類結(jié)果，也就是分類結(jié)果已知冈钦，那么通過學(xué)習(xí)這些樣本得到一個(gè)決策樹裕寨，這個(gè)決策樹能夠?qū)π碌臄?shù)據(jù)給出正確的分類。

決策樹算法作為一種分類算法派继，目標(biāo)就是將具有p維特征的n個(gè)樣本分到c個(gè)類別中去宾袜。相當(dāng)于做一個(gè)投影，c=f(n)驾窟，將樣本經(jīng)過一種變換賦予一種類別標(biāo)簽庆猫。決策樹為了達(dá)到這一目的，可以把分類的過程表示成一棵樹绅络，每次通過選擇一個(gè)特征pi來進(jìn)行分叉月培。

決策樹的幾大步驟嘁字，即：1特征的選擇 2決策樹的生成 3 決策樹的剪枝?

1、機(jī)器學(xué)習(xí)中杉畜，決策樹是一個(gè)預(yù)測模型纪蜒；它代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個(gè)節(jié)點(diǎn)表示某個(gè)對象此叠，而每個(gè)分叉路徑則代表的某個(gè)可能的屬性值纯续，而每個(gè)葉結(jié)點(diǎn)則對應(yīng)從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出灭袁，若欲有復(fù)數(shù)輸出猬错，可以建立獨(dú)立的決策樹以處理不同輸出。?

2茸歧、從數(shù)據(jù)產(chǎn)生決策樹的機(jī)器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí), ?通俗說就是決策樹倦炒。?

3、決策樹學(xué)習(xí)也是數(shù)據(jù)挖掘中一個(gè)普通的方法软瞎。在這里逢唤，每個(gè)決策樹都表述了一種樹型結(jié)構(gòu)，他由他的分支來對該類型的對象依靠屬性進(jìn)行分類涤浇。每個(gè)決策樹可以依靠對源數(shù)據(jù)庫的分割進(jìn)行數(shù)據(jù)測試智玻。這個(gè)過程可以遞歸式的對樹進(jìn)行修剪。當(dāng)不能再進(jìn)行分割或一個(gè)單獨(dú)的類可以被應(yīng)用于某一分支時(shí)芙代，遞歸過程就完成了。另外盖彭，隨機(jī)森林分類器將許多決策樹結(jié)合起來以提升分類的正確率纹烹。

決策樹是如何工作的？

1召边、決策樹一般都是自上而下的來生成的铺呵。?

2、選擇分割的方法有好幾種隧熙，但是目的都是一致的：對目標(biāo)類嘗試進(jìn)行最佳的分割片挂。?

3、從根到葉子節(jié)點(diǎn)都有一條路徑贞盯，這條路徑就是一條―規(guī)則?

4音念、決策樹可以是二叉的，也可以是多叉的躏敢。?

對每個(gè)節(jié)點(diǎn)的衡量：?

1) ? ? ? ? 通過該節(jié)點(diǎn)的記錄數(shù)?

2) ? ? ? ? 如果是葉子節(jié)點(diǎn)的話闷愤，分類的路徑?

3) ? ? ? ? 對葉子節(jié)點(diǎn)正確分類的比例。?

決策樹的生成

主要分以下兩步件余，這兩步通常通過學(xué)習(xí)已經(jīng)知道分類結(jié)果的樣本來實(shí)現(xiàn)讥脐。

1. 節(jié)點(diǎn)的分裂：一般當(dāng)一個(gè)節(jié)點(diǎn)所代表的屬性無法給出判斷時(shí)遭居，則選擇將這一節(jié)點(diǎn)分成2個(gè)

子節(jié)點(diǎn)（如不是二叉樹的情況會(huì)分成n個(gè)子節(jié)點(diǎn)）

2. 閾值的確定：選擇適當(dāng)?shù)拈撝凳沟梅诸愬e(cuò)誤率最小（Training Error）。

決策樹的損失函數(shù)（具體看下面剪枝的介紹）：

決策樹的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

一是得到的模型很容易可視化旬渠，非專家也很容易理解(至少對于較小的樹而言)俱萍。

二是算法完全不受數(shù)據(jù)縮放的影響。由于每個(gè)特征被單獨(dú)處理告丢，而且數(shù)據(jù)的劃分也不依賴于縮放枪蘑，因此決策樹算法不需要特征預(yù)處理，比如歸一化或標(biāo)準(zhǔn)化芋齿。特別是特征的尺度完全不一樣時(shí)或者二元特征和連續(xù)特征同時(shí)存在時(shí)腥寇，決策樹的效果很好。

缺點(diǎn)：

即使做了預(yù)剪枝觅捆，它也經(jīng)常會(huì)過擬合赦役，泛化性能很差。因此栅炒，在大多數(shù)應(yīng)用中掂摔，往往使用集成方法來替代單棵決策樹。

過擬合：通俗的理解就是生成的決策樹（模型）對訓(xùn)練數(shù)據(jù)集的依賴性很高赢赊，當(dāng)這樣一個(gè)完全針對某一訓(xùn)練集而生成的模型面對訓(xùn)練數(shù)據(jù)時(shí)的準(zhǔn)確度是完全可以達(dá)到100%的乙漓，但是如果面對其他測試集可能錯(cuò)誤率也會(huì)很高。

預(yù)剪枝能更好的讓模型的泛化能力更強(qiáng)释移。預(yù)剪枝的限制條件可能包括限制樹的最大深度叭披、限制葉結(jié)點(diǎn)的最大數(shù)目，或者規(guī)定一個(gè)結(jié)點(diǎn)中數(shù)據(jù)點(diǎn)的最小數(shù)目來防止繼續(xù)劃分等玩讳，這些在DecisionTreeClassifier的參數(shù)中就可以選擇涩蜘。

決策樹的剪枝

決策樹的剪枝往往通過極小化決策樹整體的損失函數(shù)或者代價(jià)函數(shù)實(shí)現(xiàn)，假設(shè)樹的葉結(jié)點(diǎn)個(gè)數(shù)為|T|熏纯，t是樹的一個(gè)葉結(jié)點(diǎn)同诫，其上有Nt個(gè)樣本，其中k類的樣本有Ntk個(gè)樟澜，k=1,2,3...K误窖，Ht(T)為葉結(jié)點(diǎn)上的經(jīng)驗(yàn)熵， $\alpha$ 參數(shù)大于0,那么決策樹損失函數(shù)可以定義為：

這里面C(T)指的是模型對訓(xùn)練數(shù)據(jù)的預(yù)測誤差秩贰，而|T|表示的就是模型的葉結(jié)點(diǎn)個(gè)數(shù)霹俺，代表了模型的復(fù)雜度， $\alpha$ 起到了控制平衡兩者之間的作用的一個(gè)角色毒费， $\alpha$ =0意味著只考慮對訓(xùn)練數(shù)據(jù)的預(yù)測誤差而不考慮結(jié)點(diǎn)個(gè)數(shù)吭服，自然會(huì)有過擬合的現(xiàn)象產(chǎn)生。

所謂的剪枝蝗罗，就是當(dāng) $\alpha$ 確定的時(shí)候艇棕，選擇損失函數(shù)最小的模型蝌戒。 $\alpha$ 確定時(shí)候，子樹越大沼琉，訓(xùn)練數(shù)據(jù)擬合程度越好北苟，但是泛化能力就越差，相反的打瘪，子樹越小友鼻，模型的復(fù)雜度就越小，對訓(xùn)練數(shù)據(jù)的擬合程度越差闺骚，但是泛化能力相對較好彩扔，損失函數(shù)同時(shí)考慮二者的影響，達(dá)到一個(gè)平衡的最優(yōu)僻爽！

本質(zhì)上?這樣的損失函數(shù)最小化原則就是等價(jià)與正則化的極大似然估計(jì)虫碉，利用損失函數(shù)最小化原則進(jìn)行剪枝，就是利用正則化的極大似然估計(jì)進(jìn)行模型的篩選胸梆！

二敦捧、C4.5介紹

決策樹的生成算法有ID3, C4.5、C5.0和CART（Classification And Regression Tree碰镜、分類回歸樹）等（CART的分類效果一般優(yōu)于其他決策樹兢卵，CART下一節(jié)再介紹）。不同的決策樹算法有著不同的特征選擇方案绪颖。ID3用信息增益秽荤，C4.5用信息增益率，CART用gini系數(shù)柠横。C4.5是ID3的一個(gè)改進(jìn)算法窃款。

1.?引入——熵

熵:是表示隨機(jī)變量不確定性的度量，熵的取值越大滓鸠，隨機(jī)變量的不確定性也越大。

設(shè)X是一個(gè)取有限個(gè)值的離散隨機(jī)變量第喳，其概率分布為?

P(X=xi)=pi,?i=1,2,?,n

熵計(jì)算公式:H(X)=- ∑ pi * logpi,i=1,2, ... , n

2.?ID3

ID3算法的核心是在決策樹各個(gè)子節(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征糜俗，遞歸的構(gòu)建決策樹。（【信息增益:表示特征X使得類Y的不確定性減少的程度曲饱。(分類后的專一性悠抹，希望分類后的結(jié)果是同類在一起) 】）

具體方法是：從根節(jié)點(diǎn)開始，對節(jié)點(diǎn)計(jì)算所有可能的特征的信息增益扩淀，選擇信息增益最大的特征作為節(jié)點(diǎn)的特征楔敌，由該特征的不同取值建立子節(jié)點(diǎn)；再對子節(jié)點(diǎn)遞歸調(diào)用以上方法驻谆，構(gòu)建決策樹卵凑。直到所有特征的信息增益均很小或沒有特征可以選擇為止庆聘。最后得到一個(gè)決策樹。

ID3過程：

根據(jù)信息增益(Informationgain)來選取Feature作為決策樹分裂的節(jié)點(diǎn).特征A對訓(xùn)練數(shù)據(jù)集D的信息增益定義為集合D的經(jīng)驗(yàn)熵(所謂經(jīng)驗(yàn)熵,指的是熵是由某個(gè)數(shù)據(jù)集合估計(jì)得到的)H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵?H(D∣A)?之差,記為g(D,A)勺卢。

g(D,A)=H(D)?H(D|A) ? ? ? ?實(shí)際上就是特征A和D的互信息

實(shí)例論證見：https://blog.csdn.net/Andy_shenzl/article/details/83899431?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-1#C4.5%E7%AE%97%E6%B3%95%E4%BC%98%E7%BC%BA%E7%82%B9%E5%88%86%E6%9E%90

https://blog.csdn.net/fuqiuai/article/details/79456971?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase

理論計(jì)算過程：

ID3缺點(diǎn)：

ID3采用的信息增益度量存在一個(gè)內(nèi)在偏置,它優(yōu)先選擇有較多屬性值的Feature,因?yàn)閷傩灾刀嗟腇eature會(huì)有相對較大的信息增益伙判。

越細(xì)小的分割分類錯(cuò)誤率越小，所以ID3會(huì)越分越細(xì)黑忱，比如以第一個(gè)屬性為例：設(shè)閾值小于70可將樣本分為2組宴抚，但是分錯(cuò)了1個(gè)。如果設(shè)閾值小于70甫煞，再加上閾值等于95菇曲，那么分錯(cuò)率降到了0，但是這種分割顯然只對訓(xùn)練數(shù)據(jù)有用抚吠，對于新的數(shù)據(jù)沒有意義常潮，這就是所說的過度學(xué)習(xí)（Overfitting）。

分割太細(xì)了埃跷，訓(xùn)練數(shù)據(jù)的分類可以達(dá)到0錯(cuò)誤率蕊玷，但是因?yàn)樾碌臄?shù)據(jù)和訓(xùn)練數(shù)據(jù)不同，所以面對新的數(shù)據(jù)分錯(cuò)率反倒上升了弥雹。決策樹是通過分析訓(xùn)練數(shù)據(jù)垃帅，得到數(shù)據(jù)的統(tǒng)計(jì)信息，而不是專為訓(xùn)練數(shù)據(jù)量身定做剪勿。

(信息增益反映的給定一個(gè)條件以后不確定性減少的程度,必然是分得越細(xì)的數(shù)據(jù)集確定性更高,也就是條件熵越小,信息增益越大)贸诚。

3.?C4.5算法

為了克服ID3的缺點(diǎn)，引進(jìn)C4.5算法厕吉。

避免ID3不足的一個(gè)度量就是不用信息增益來選擇Feature,而是用信息增益比率(gainratio),增益比率通過引入一個(gè)被稱作分裂信息(Splitinformation)的項(xiàng)來懲罰取值較多的Feature,分裂信息用來衡量Feature分裂數(shù)據(jù)的廣度和均勻性:

但是當(dāng)某個(gè)Di的大小跟D的大小接近的時(shí)候,SplitInformation(D,A)→0,GainRatio(D,A)→∞,為了避免這樣的屬性,可以采用啟發(fā)式的思路,只對那些信息增益比較高的屬性才應(yīng)用信息增益比率酱固。

C4.5算法主要有以下四個(gè)步驟：

Entropy(S)：計(jì)算熵；

Gain(S,A):計(jì)算信息增益头朱；

SplitInformation(S,A):計(jì)算分裂信息度量运悲；

GainRatio(S,A):計(jì)算信息增益率。

根據(jù)計(jì)算得到的信息增益率進(jìn)行選擇屬性集中的屬性作為決策樹結(jié)點(diǎn)项钮，對該結(jié)點(diǎn)進(jìn)行分裂班眯。

相比ID3,C4.5還能處理連續(xù)屬性值,具體步驟為:

? 把需要處理的樣本(對應(yīng)根節(jié)點(diǎn))或樣本子集(對應(yīng)子樹)按照連續(xù)變量的大小從小到大進(jìn)行排序。

? 假設(shè)該屬性對應(yīng)的不同的屬性值一共有N個(gè),那么總共有N?1個(gè)可能的候選分割閾值點(diǎn),每個(gè)候選的分割閾值點(diǎn)的值為上述排序后的屬性值中兩兩前后連續(xù)元素的中點(diǎn),根據(jù)這個(gè)分割點(diǎn)把原來連續(xù)的屬性分成bool屬性.實(shí)際上可以不用檢查所有N?1個(gè)分割點(diǎn)（https://blog.csdn.net/amour_yue/article/details/71325261）烁巫。

? 用信息增益比率選擇最佳劃分署隘。

C4.5算法的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

（1）通過信息增益率選擇分裂屬性，克服了ID3算法中通過信息增益傾向于選擇擁有多個(gè)屬性值的屬性作為分裂屬性的不足亚隙；?

（2）能夠處理離散型和連續(xù)型的屬性類型磁餐，即將連續(xù)型的屬性進(jìn)行離散化處理；?

（3）構(gòu)造決策樹之后進(jìn)行剪枝操作阿弃；?

（4）能夠處理具有缺失屬性值的訓(xùn)練數(shù)據(jù)诊霹；

? (5)??產(chǎn)生的分類規(guī)則易于理解羞延，準(zhǔn)確率較高。

缺點(diǎn)：?

（1）在構(gòu)造樹的過程中畅哑，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序肴楷，因而導(dǎo)致算法的計(jì)算效率較低，特別是針對含有連續(xù)屬性值的訓(xùn)練樣本時(shí)表現(xiàn)的尤為突出荠呐。?

（2）算法在選擇分裂屬性時(shí)沒有考慮到條件屬性間的相關(guān)性赛蔫，只計(jì)算數(shù)據(jù)集中每一個(gè)條件屬性與決策屬性之間的期望信息，有可能影響到屬性選擇的正確性泥张。

參考：