c4.5剪枝java代碼的簡單介紹

決策樹（Decision Tree）

決策樹是一種非參數(shù)有監(jiān)督的機器學習方法，可以用于解決回歸問題和分類問題。通過學習已有的數(shù)據(jù)，計算得出一系列推斷規(guī)則來預(yù)測目標變量的值，并用類似流程圖的形式進行展示。決策樹模型可以進行可視化，具有很強的可解釋性，算法容易理解，以決策樹為基礎(chǔ)的各種集成算法在很多領(lǐng)域都有廣泛的應(yīng)用。

成都創(chuàng)新互聯(lián)總部坐落于成都市區(qū)，致力網(wǎng)站建設(shè)服務(wù)有成都網(wǎng)站建設(shè)、做網(wǎng)站、網(wǎng)絡(luò)營銷策劃、網(wǎng)頁設(shè)計、網(wǎng)站維護、公眾號搭建、小程序定制開發(fā)、軟件開發(fā)等為企業(yè)提供一整套的信息化建設(shè)解決方案。創(chuàng)造真正意義上的網(wǎng)站建設(shè)，為互聯(lián)網(wǎng)品牌在互動行銷領(lǐng)域創(chuàng)造價值而不懈努力！

熵的概念最早起源于物理學，用于度量一個熱力學系統(tǒng)的無序程度。在信息論里面，信息熵代表著一個事件或一個變量等所含有的信息量。在信息世界，熵越高，則能傳輸越多的信息，熵越低，則意味著傳輸?shù)男畔⒃缴佟?/p>

發(fā)生概率低的事件比發(fā)生概率高的事件具有更大的不確定性，需要更多的信息去描述他們，信息熵更高。

我們可以用計算事件發(fā)生的概率來計算事件的信息，又稱“香農(nóng)信息”（ Shannon Information ）。一個離散事件x的信息可以表示為：

h(x) = -log(p(x))

p() 代表事件x發(fā)生的概率， log() 為以二為底的對數(shù)函數(shù)，即一個事件的信息量就是這個事件發(fā)生的概率的負對數(shù)。選擇以二為底的對數(shù)函數(shù)代表計算信息的單位是二進制。因為概率p(x)小于1，所以負號就保證了信息熵永遠不為負數(shù)。當事件的概率為1時，也就是當某事件百分之百發(fā)生時，信息為0。

熵（ entropy ），又稱“香農(nóng)熵”（ Shannon entropy ），表示一個隨機變量的分布所需要的平均比特數(shù)。一個隨機變量的信息熵可以表示為：

H(x) = -sum(each k in K p(k)log(p(k)))

K表示變量x所可能具有的所有狀態(tài)（所有事件），將發(fā)生特定事件的概率和該事件的信息相乘，最后加和，即可得到該變量的信息熵?？梢岳斫鉃椋畔㈧鼐褪瞧骄园l(fā)生一個事件我們得到的信息量大小。所以數(shù)學上，信息熵其實是事件信息量的期望。

當組成該隨機變量的一個事件的概率為1時信息熵最小，為0，即該事件必然發(fā)生。當組成該隨機變量的所有事件發(fā)生的概率相等時，信息熵最大，即完全不能判斷那一個事件更容易發(fā)生，不確定性最大。

當一個事件主導(dǎo)時，比如偏態(tài)分布（ Skewed Probability Distribution ），不確定性減小，信息熵較低（low entropy）；當所有事件發(fā)生概率相同時，比如均衡分布（ Balanced Probability Distribution ），不確定性極大，信息熵較高（high entropy）。

由以上的香農(nóng)信息公式可知，信息熵主要有三條性質(zhì)：

- 單調(diào)性。發(fā)生概率越高的事件，其所攜帶的信息熵越低。比如一個真理的不確定性是極低的，那么它所攜帶的信息熵就極低。

- 非負性。信息熵不能為負。單純從邏輯層面理解，如果得知了某個信息后，卻增加了不確定性，這也是不合邏輯的。

- 可加性。即多隨機事件同時發(fā)生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和。

若兩事件A和B同時發(fā)生，兩個事件相互獨立。 p(X=A,Y=B) = p(X = A)*p(Y=B) , 那么信息熵為 H(A,B) = H(A) + H(B) 。但若兩事件不相互獨立，那么 H(A,B) = H(A) + H(B) - I(A,B) 。其中 I(A,B) 是互信息（ mutual information，MI ），即一個隨機變量包含另一個隨機變量信息量的度量。即已知X的情況下，Y的分布是否會改變。

可以理解為，兩個隨機變量的互信息度量了兩個變量間相互依賴的程度。X 和 Y的互信息可以表示為：

I(X;Y) = H(X) - H(X|Y)

H(X)是X的信息熵，H(X|Y)是已知Y的情況下，X的信息熵。結(jié)果的單位是比特。

簡單來說，互信息的性質(zhì)為：

- I(X;Y)=0 互信息永遠不可能為負

- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是對稱的

-當X，Y獨立的時候， I(X;Y) = 0 互信息值越大，兩變量相關(guān)性越強。

-當X，Y知道一個就能推斷另一個的時候， I(X;Y) = H(Y) = H(X)

在數(shù)據(jù)科學中，互信息常用于特征篩選。在通信系統(tǒng)中互信息也應(yīng)用廣泛。在一個點到點的通信系統(tǒng)中，發(fā)送信號為X，通過信道后，接收端接收到的信號為Y，那么信息通過信道傳遞的信息量就是互信息 I(X,Y) 。根據(jù)這個概念，香農(nóng)推導(dǎo)出信道容量（即臨界通信傳輸速率的值）。

信息增益（ Information Gain ）是用來按照一定規(guī)則劃分數(shù)據(jù)集后，衡量信息熵減少量的指數(shù)。

那數(shù)據(jù)集的信息熵又是怎么計算的呢？比如一個常見的0,1二分類問題，我們可以計算它的熵為：

Entropy = -(p(0) * log(P(0)) + p(1)\ * log(P(1)))

當該數(shù)據(jù)集為50/50的數(shù)據(jù)集時，它的信息熵是最大的（1bit）。而10/90的數(shù)據(jù)集將會大大減少結(jié)果的不確定性，減小數(shù)據(jù)集的信息熵（約為0.469bit）。

這樣來說，信息熵可以用來表示數(shù)據(jù)集的純度（ purity ）。信息熵為0就表示該數(shù)據(jù)集只含有一個類別，純度最高。而較高的信息熵則代表較為平衡的數(shù)據(jù)集和較低的純度。

信息增益是提供了一種可以使用信息熵計算數(shù)據(jù)集經(jīng)過一定的規(guī)則（比如決策樹中的一系列規(guī)則）進行數(shù)據(jù)集分割后信息熵的變化的方法。

IG(S,a) = H(S) - H(S|a)

其中，H(s) 是原數(shù)據(jù)集S的信息熵（在做任何改變之前），H(S|a)是經(jīng)過變量a的一定分割規(guī)則。所以信息增益描述的是數(shù)據(jù)集S變換后所節(jié)省的比特數(shù)。

信息增益可以用做決策樹的分枝判斷方法。比如最常用CART樹（ Classification and Regression Tree ）中的分枝方法，只要在python中設(shè)置參數(shù) criterion 為 “entropy” 即可。

信息增益也可以用作建模前的特征篩選。在這種場景下，信息增益和互信息表達的含義相同，會被用來計算兩變量之間的獨立性。比如scikit-learn 中的函數(shù) mutual_info_classiif()

信息增益在面對類別較少的離散數(shù)據(jù)時效果較好，但是面對取值較多的特征時效果會有偏向性。因為當特征的取值較多時，根據(jù)此特征劃分得到的子集純度有更大的可能性會更高(對比與取值較少的特征)，因此劃分之后的熵更低，由于劃分前的熵是一定的，因此信息增益更大，因此信息增益比較偏向取值較多的特征。舉一個極端的例子來說，如果一個特征為身份證號，當把每一個身份證號不同的樣本都分到不同的子節(jié)點時，熵會變?yōu)?，意味著信息增益最大，從而該特征會被算法選擇。但這種分法顯然沒有任何實際意義。

這種時候，信息增益率就起到了很重要的作用。

gR(D,A)=g(D,A)/HA(D)

HA(D) 又叫做特征A的內(nèi)部信息，HA(D)其實像是一個衡量以特征AA的不同取值將數(shù)據(jù)集D分類后的不確定性的度量。如果特征A的取值越多，那么不確定性通常會更大，那么HA(D)的值也會越大，而1/HA(D)的值也會越小。這相當于是在信息增益的基礎(chǔ)上乘上了一個懲罰系數(shù)。即 gR(D,A)=g(D,A)?懲罰系數(shù) 。

在CART算法中，基尼不純度表示一個隨機選中的樣本被分錯類別的可能性，即這個樣本被選中的概率乘以它被分錯的概率。當一個節(jié)點中所有樣本均為一種時（沒有被分錯的樣本），基尼不純度達到最低值0。

舉例來說，如果有綠色和藍色兩類數(shù)據(jù)點，各占一半（藍色50%，綠色50%）。那么我們隨機分類，有以下四種情況：

-分為藍色，但實際上是綠色（?），概率25%

-分為藍色，實際上也是藍色（??），概率25%

-分為綠色，實際上也是綠色（??），概率25%

-分為綠色，但實際上是藍色（?），概率25%

那么將任意一個數(shù)據(jù)點分錯的概率為25%+25% = 50%?；岵患兌葹?.5。

在特征選擇中，我們可以選擇加入后使數(shù)據(jù)不純度減少最多的特征。

噪音數(shù)據(jù)簡單來說就是會對模型造成誤導(dǎo)的數(shù)據(jù)。分為類別噪聲（ class noise 或 label noise ）和變量噪聲（ attribute noise ）。類別噪聲指的的是被錯誤標記的錯誤數(shù)據(jù)，比如兩個相同的樣本具有不同的標簽等情況。變量噪聲指的是有問題的變量，比如缺失值、異常值和無關(guān)值等。

決策樹其實是一種圖結(jié)構(gòu)，由節(jié)點和邊構(gòu)成。

-根節(jié)點：只有出邊沒有入邊。包含樣本全集，表示一個對樣本最初的判斷。

-內(nèi)部節(jié)點：一個入邊多個出邊。表示一個特征或是屬性。每個內(nèi)部節(jié)點都是一個判斷條件，包含數(shù)據(jù)集中從根節(jié)點到該節(jié)點所有滿足條件的數(shù)據(jù)的集合。

-葉節(jié)點：一個入邊無出邊。表示一個類，對應(yīng)于決策結(jié)果。

決策樹的生成主要分為三個步驟：

1. 節(jié)點的分裂：當一個節(jié)點不夠純（單一分類占比不夠大或者說信息熵較大）時，則選擇將這一節(jié)點進行分裂。

2. 決策邊界的確定：選擇正確的決策邊界（ Decision Boundary ），使分出的節(jié)點盡量純，信息增益（熵減少的值）盡可能大。

3. 重復(fù)及停止生長：重復(fù)1，2步驟，直到純度為0或樹達到最大深度。為避免過擬合，決策樹算法一般需要制定樹分裂的最大深度。到達這一深度后，即使熵不等于0，樹也不會繼續(xù)進行分裂。

下面以超級知名的鳶尾花數(shù)據(jù)集舉例來說明。

這個數(shù)據(jù)集含有四個特征：花瓣的長度（ petal length ）、花瓣的寬度( petal width )、花萼的長度( sepal length )和花萼的寬度( sepal width )。預(yù)測目標是鳶尾花的種類 iris setosa, iris versicolor 和 iris virginica 。

建立決策樹模型的目標是根據(jù)特征盡可能正確地將樣本劃分到三個不同的“陣營”中。

根結(jié)點的選擇基于全部數(shù)據(jù)集，使用了貪婪算法：遍歷所有的特征，選擇可以使信息熵降到最低、基尼不純度最低的特征。

如上圖，根節(jié)點的決策邊界為' petal width = 0.8cm '。那么這個決策邊界是怎么決定的呢？

-遍歷所有可能的決策邊界（需要注意的是，所有可能的決策邊界代表的是該子集中該特征所有的值，不是以固定增幅遍歷一個區(qū)間內(nèi)的所有值！那樣很沒有必要的～）

-計算新建的兩個子集的基尼不純度。

-選擇可以使新的子集達到最小基尼不純度的分割閾值。這個“最小”可以指兩個子集的基尼不純度的和或平均值。

ID3是最早提出的決策樹算法。ID3算法的核心是在決策樹各個節(jié)點上根據(jù) 信息增益來選擇進行劃分的特征，然后遞歸地構(gòu)建決策樹。

- 缺點：

（1）沒有剪枝

（2）只能用于處理離散特征

（3）采用信息增益作為選擇最優(yōu)劃分特征的標準，然而信息增益會偏向那些取值較多的特征(例如，如果存在唯一標識屬性身份證號，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。)

C4.5 與ID3相似，但對ID3進行了改進：

-引入“悲觀剪枝”策略進行后剪枝

-信息增益率作為劃分標準

-將連續(xù)特征離散化，假設(shè) n 個樣本的連續(xù)特征 A 有 m 個取值，C4.5 將其排序并取相鄰兩樣本值的平均數(shù)共 m-1 個劃分點，分別計算以該劃分點作為二元分類點時的信息增益，并選擇信息增益最大的點作為該連續(xù)特征的二元離散分類點；

-可以處理缺失值

對于缺失值的處理可以分為兩個子問題：

（1）在特征值缺失的情況下進行劃分特征的選擇？（即如何計算特征的信息增益率）

C4.5 中對于具有缺失值特征，用沒有缺失的樣本子集所占比重來折算；

（2）選定該劃分特征，對于缺失該特征值的樣本如何處理？（即到底把這個樣本劃分到哪個結(jié)點里）

C4.5 的做法是將樣本同時劃分到所有子節(jié)點，不過要調(diào)整樣本的權(quán)重值，其實也就是以不同概率劃分到不同節(jié)點中。

（1）剪枝策略可以再優(yōu)化；

（2）C4.5 用的是多叉樹，用二叉樹效率更高；

（3）C4.5 只能用于分類；

（4）C4.5 使用的熵模型擁有大量耗時的對數(shù)運算，連續(xù)值還有排序運算；

（5）C4.5 在構(gòu)造樹的過程中，對數(shù)值屬性值需要按照其大小進行排序，從中選擇一個分割點，所以只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當訓(xùn)練集大得無法在內(nèi)存容納時，程序無法運行。

可以用于分類，也可以用于回歸問題。CART 算法使用了基尼系數(shù)取代了信息熵模型，計算復(fù)雜度更低。

CART 包含的基本過程有分裂，剪枝和樹選擇。

分裂：分裂過程是一個二叉遞歸劃分過程，其輸入和預(yù)測特征既可以是連續(xù)型的也可以是離散型的，CART 沒有停止準則，會一直生長下去；

剪枝：采用“代價復(fù)雜度”剪枝，從最大樹開始，每次選擇訓(xùn)練數(shù)據(jù)熵對整體性能貢獻最小的那個分裂節(jié)點作為下一個剪枝對象，直到只剩下根節(jié)點。CART 會產(chǎn)生一系列嵌套的剪枝樹，需要從中選出一顆最優(yōu)的決策樹；

樹選擇：用單獨的測試集評估每棵剪枝樹的預(yù)測性能（也可以用交叉驗證）。

（1）C4.5 為多叉樹，運算速度慢，CART 為二叉樹，運算速度快；

（2）C4.5 只能分類，CART 既可以分類也可以回歸；

（3）CART 使用 Gini 系數(shù)作為變量的不純度量，減少了大量的對數(shù)運算；

（4）CART 采用代理測試來估計缺失值，而 C4.5 以不同概率劃分到不同節(jié)點中；

（5）CART 采用“基于代價復(fù)雜度剪枝”方法進行剪枝，而 C4.5 采用悲觀剪枝方法。

（1）決策樹易于理解和解釋，可以可視化分析，容易提取出規(guī)則

（2）可以同時處理分類型和數(shù)值型數(shù)據(jù)

（3）可以處理缺失值

（4）運行速度比較快（使用Gini的快于使用信息熵，因為信息熵算法有l(wèi)og）

（1）容易發(fā)生過擬合（集成算法如隨機森林可以很大程度上減少過擬合）

（2）容易忽略數(shù)據(jù)集中屬性的相互關(guān)聯(lián)；

（3）對于那些各類別樣本數(shù)量不一致的數(shù)據(jù)，在決策樹中，進行屬性劃分時，不同的判定準則會帶來不同的屬性選擇傾向。

寫在后面：這個專輯主要是本小白在機器學習算法學習過程中的一些總結(jié)筆記和心得，如有不對之處還請各位大神多多指正?。P(guān)于決策樹的剪枝還有很多沒有搞懂，之后弄明白了會再單獨出一篇總結(jié)噠）

參考資料鏈接：

用python實現(xiàn)紅酒數(shù)據(jù)集的ID3,C4.5和CART算法？

ID3算法介紹

ID3算法全稱為迭代二叉樹3代算法（Iterative Dichotomiser 3）

該算法要先進行特征選擇，再生成決策樹，其中特征選擇是基于“信息增益”最大的原則進行的。

但由于決策樹完全基于訓(xùn)練集生成的，有可能對訓(xùn)練集過于“依賴”，即產(chǎn)生過擬合現(xiàn)象。因此在生成決策樹后，需要對決策樹進行剪枝。剪枝有兩種形式，分別為前剪枝（Pre-Pruning）和后剪枝（Post-Pruning），一般采用后剪枝。

信息熵、條件熵和信息增益

信息熵：來自于香農(nóng)定理，表示信息集合所含信息的平均不確定性。信息熵越大，表示不確定性越大，所含的信息量也就越大。

設(shè)x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x

,...x

為信息集合X的n個取值，則x i x_ix

的概率：

P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n

P(X=i)=p

,i=1,2,3,...,n

信息集合X的信息熵為：

H ( X ) = ? ∑ i = 1 n p i log ? p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}

H(X)=?

i=1

∑

logp

條件熵：指已知某個隨機變量的情況下，信息集合的信息熵。

設(shè)信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y

,...y

組成的隨機變量集合Y，則隨機變量（X，Y）的聯(lián)合概率分布為

P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}

P(x=i,y=j)=p

條件熵：

H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}

H(X∣Y)=

j=1

∑

p(y

)H(X∣y

)

由

H ( X ∣ y j ) = ? ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ? p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}

H(X∣y

)=?

j=1

∑

p(y

)

i=1

∑

p(x

∣y

)logp(x

∣y

)

和貝葉斯公式：

p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)

p(x

)=p(x

∣y

)p(y

)

可以化簡條件熵的計算公式為:

H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ? p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}

H(X∣Y)=

j=1

∑

i=1

∑

p(x

)log

p(x

)

p(x

)

信息增益：信息熵-條件熵，用于衡量在知道已知隨機變量后，信息不確定性減小越大。

d ( X , Y ) = H ( X ) ? H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)

d(X,Y)=H(X)?H(X∣Y)

python代碼實現(xiàn)

import numpy as np

import math

def calShannonEnt(dataSet):

""" 計算信息熵 """

labelCountDict = {}

for d in dataSet:

label = d[-1]

if label not in labelCountDict.keys():

labelCountDict[label] = 1

else:

labelCountDict[label] += 1

entropy = 0.0

for l, c in labelCountDict.items():

p = 1.0 * c / len(dataSet)

entropy -= p * math.log(p, 2)

return entropy

def filterSubDataSet(dataSet, colIndex, value):

"""返回colIndex特征列l(wèi)abel等于value，并且過濾掉改特征列的數(shù)據(jù)集"""

subDataSetList = []

for r in dataSet:

if r[colIndex] == value:

newR = r[:colIndex]

newR = np.append(newR, (r[colIndex + 1:]))

subDataSetList.append(newR)

return np.array(subDataSetList)

def chooseFeature(dataSet):

""" 通過計算信息增益選擇最合適的特征"""

featureNum = dataSet.shape[1] - 1

entropy = calShannonEnt(dataSet)

bestInfoGain = 0.0

bestFeatureIndex = -1

for i in range(featureNum):

uniqueValues = np.unique(dataSet[:, i])

condition_entropy = 0.0

for v in uniqueValues: #計算條件熵

subDataSet = filterSubDataSet(dataSet, i, v)

p = 1.0 * len(subDataSet) / len(dataSet)

condition_entropy += p * calShannonEnt(subDataSet)

infoGain = entropy - condition_entropy #計算信息增益

if infoGain = bestInfoGain: #選擇最大信息增益

bestInfoGain = infoGain

bestFeatureIndex = i

return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):

""" 通過訓(xùn)練集生成決策樹 """

featureName = featNames[:] # 拷貝featNames，此處不能直接用賦值操作，否則新變量會指向舊變量的地址

classList = list(dataSet[:, -1])

if len(set(classList)) == 1: # 只有一個類別

return classList[0]

if dataSet.shape[1] == 1: #當所有特征屬性都利用完仍然無法判斷樣本屬于哪一類，此時歸為該數(shù)據(jù)集中數(shù)量最多的那一類

return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #選擇特征

bestFeatureName = featNames[bestFeatureIndex]

del featureName[bestFeatureIndex] #移除已選特征列

decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已選特征列所包含的類別，通過遞歸生成決策樹

for v in featureValueUnique:

copyFeatureName = featureName[:]

subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)

decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, copyFeatureName)

return decisionTree

def classify(decisionTree, featnames, featList):

""" 使用訓(xùn)練所得的決策樹進行分類 """

classLabel = None

root = decisionTree.keys()[0]

firstGenDict = decisionTree[root]

featIndex = featnames.index(root)

for k in firstGenDict.keys():

if featList[featIndex] == k:

if isinstance(firstGenDict[k], dict): #若子節(jié)點仍是樹，則遞歸查找

classLabel = classify(firstGenDict[k], featnames, featList)

else:

classLabel = firstGenDict[k]

return classLabel

下面用鳶尾花數(shù)據(jù)集對該算法進行測試。由于ID3算法只能用于標稱型數(shù)據(jù)，因此用在對連續(xù)型的數(shù)值數(shù)據(jù)上時，還需要對數(shù)據(jù)進行離散化，離散化的方法稍后說明，此處為了簡化，先使用每一種特征所有連續(xù)性數(shù)值的中值作為分界點，小于中值的標記為1，大于中值的標記為0。訓(xùn)練1000次，統(tǒng)計準確率均值。

from sklearn import datasets

from sklearn.model_selection import train_test_split

iris = datasets.load_iris()

data = np.c_[iris.data, iris.target]

scoreL = []

for i in range(1000): #對該過程進行10000次

trainData, testData = train_test_split(data) #區(qū)分測試集和訓(xùn)練集

featNames = iris.feature_names[:]

for i in range(trainData.shape[1] - 1): #對訓(xùn)練集每個特征，以中值為分界點進行離散化

splitPoint = np.mean(trainData[:, i])

featNames[i] = featNames[i]+'='+'{:.3f}'.format(splitPoint)

trainData[:, i] = [1 if x = splitPoint else 0 for x in trainData[:, i]]

testData[:, i] = [1 if x = splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)

classifyLable = [classify(decisionTree, featNames, td) for td in testData]

scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

print 'score: ', np.mean(scoreL)

輸出結(jié)果為：score: 0.7335，即準確率有73%。每次訓(xùn)練和預(yù)測的準確率分布如下：

數(shù)據(jù)離散化

然而，在上例中對特征值離散化的劃分點實際上過于“野蠻”，此處介紹一種通過信息增益最大的標準來對數(shù)據(jù)進行離散化。原理很簡單，當信息增益最大時，說明用該點劃分能最大程度降低數(shù)據(jù)集的不確定性。

具體步驟如下：

對每個特征所包含的數(shù)值型特征值排序

對相鄰兩個特征值取均值，這些均值就是待選的劃分點

用每一個待選點把該特征的特征值劃分成兩類，小于該特征點置為1，大于該特征點置為0，計算此時的條件熵，并計算出信息增益

選擇信息使信息增益最大的劃分點進行特征離散化

實現(xiàn)代碼如下：

def filterRawData(dataSet, colIndex, value, tag):

""" 用于把每個特征的連續(xù)值按照區(qū)分點分成兩類，加入tag參數(shù)，可用于標記篩選的是哪一部分數(shù)據(jù)"""

filterDataList = []

for r in dataSet:

if (tag and r[colIndex] = value) or ((not tag) and r[colIndex] value):

newR = r[:colIndex]

newR = np.append(newR, (r[colIndex + 1:]))

filterDataList.append(newR)

return np.array(filterDataList)

def dataDiscretization(dataSet, featName):

""" 對數(shù)據(jù)每個特征的數(shù)值型特征值進行離散化 """

featureNum = dataSet.shape[1] - 1

entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #對于每一個特征

uniqueValues = sorted(np.unique(dataSet[:, featIndex]))

meanPoint = []

for i in range(len(uniqueValues) - 1): # 求出相鄰兩個值的平均值

meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)

bestInfoGain = 0.0

bestMeanPoint = -1

for mp in meanPoint: #對于每個劃分點

subEntropy = 0.0 #計算該劃分點的信息熵

for tag in range(2): #分別劃分為兩類

subDataSet = filterRawData(dataSet, featIndex, mp, tag)

p = 1.0 * len(subDataSet) / len(dataSet)

subEntropy += p * calShannonEnt(subDataSet)

## 計算信息增益

infoGain = entropy - subEntropy

## 選擇最大信息增益

if infoGain = bestInfoGain:

bestInfoGain = infoGain

bestMeanPoint = mp

featName[featIndex] = featName[featIndex] + "=" + "{:.3f}".format(bestMeanPoint)

dataSet[:, featIndex] = [1 if x = bestMeanPoint else 0 for x in dataSet[:, featIndex]]

return dataSet, featName

重新對數(shù)據(jù)進行離散化，并重復(fù)該步驟1000次，同時用sklearn中的DecisionTreeClassifier對相同數(shù)據(jù)進行分類，分別統(tǒng)計平均準確率。運行代碼如下:

from sklearn.tree import DecisionTreeClassifier

import matplotlib.pyplot as plt

scoreL = []

scoreL_sk = []

for i in range(1000): #對該過程進行1000次

featNames = iris.feature_names[:]

trainData, testData = train_test_split(data) #區(qū)分測試集和訓(xùn)練集

trainData_tmp = copy.copy(trainData)

testData_tmp = copy.copy(testData)

discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根據(jù)信息增益離散化

for i in range(testData.shape[1]-1): #根據(jù)測試集的區(qū)分點離散化訓(xùn)練集

splitPoint = float(discritizationFeatName[i].split('=')[-1])

testData[:, i] = [1 if x=splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)

classifyLable = [classify(decisionTree, featNames, td) for td in testData]

scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier('entropy')

clf.fit(trainData[:, :-1], trainData[:, -1])

clf.predict(testData[:, :-1])

scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print 'score: ', np.mean(scoreL)

print 'score-sk: ', np.mean(scoreL_sk)

fig = plt.figure(figsize=(10, 4))

plt.subplot(1,2,1)

pd.Series(scoreL).hist(grid=False, bins=10)

plt.subplot(1,2,2)

pd.Series(scoreL_sk).hist(grid=False, bins=10)

plt.show()

兩者準確率分別為：

score: 0.7037894736842105

score-sk: 0.7044736842105263

準確率分布如下：

兩者的結(jié)果非常一樣。

（但是。。為什么根據(jù)信息熵離散化得到的準確率比直接用均值離散化的準確率還要低??？？哇的哭出聲。。）

最后一次決策樹圖形如下：

決策樹剪枝

由于決策樹是完全依照訓(xùn)練集生成的，有可能會有過擬合現(xiàn)象，因此一般會對生成的決策樹進行剪枝。常用的是通過決策樹損失函數(shù)剪枝，決策樹損失函數(shù)表示為:

C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|

(T)=

t=1

∑

(T)+α∣T∣

其中，H t ( T ) H_t(T)H

(T)表示葉子節(jié)點t的熵值，T表示決策樹的深度。前項∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑

t=1

(T)是決策樹的經(jīng)驗損失函數(shù)當隨著T的增加，該節(jié)點被不停的劃分的時候，熵值可以達到最小，然而T的增加會使后項的值增大。決策樹損失函數(shù)要做的就是在兩者之間進行平衡，使得該值最小。

對于決策樹損失函數(shù)的理解，如何理解決策樹的損失函數(shù)? - 陶輕松的回答 - 知乎這個回答寫得挺好，可以按照答主的思路理解一下

C4.5算法

ID3算法通過信息增益來進行特征選擇會有一個比較明顯的缺點：即在選擇的過程中該算法會優(yōu)先選擇類別較多的屬性（這些屬性的不確定性小，條件熵小，因此信息增益會大），另外，ID3算法無法解決當每個特征屬性中每個分類都只有一個樣本的情況（此時每個屬性的條件熵都為0）。

C4.5算法ID3算法的改進，它不是依據(jù)信息增益進行特征選擇，而是依據(jù)信息增益率，它添加了特征分裂信息作為懲罰項。定義分裂信息：

S p l i t I n f o ( X , Y ) = ? ∑ i n ∣ X i ∣ ∣ X ∣ log ? ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}

SplitInfo(X,Y)=?

∑

∣X∣

∣X

∣

log

∣X∣

∣X

∣

則信息增益率為：

G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}

GainRatio(X,Y)=

SplitInfo(X,Y)

d(X,Y)

關(guān)于ID3和C4.5算法

在學習分類回歸決策樹算法時，看了不少的資料和博客。關(guān)于這兩個算法，ID3算法是最早的分類算法，這個算法剛出生的時候其實帶有很多缺陷：

無法處理連續(xù)性特征數(shù)據(jù)

特征選取會傾向于分類較多的特征

沒有解決過擬合的問題

沒有解決缺失值的問題

即該算法出生時是沒有帶有連續(xù)特征離散化、剪枝等步驟的。C4.5作為ID3的改進版本彌補列ID3算法不少的缺陷：

通過信息最大增益的標準離散化連續(xù)的特征數(shù)據(jù)

在選擇特征是標準從“最大信息增益”改為“最大信息增益率”

通過加入正則項系數(shù)對決策樹進行剪枝

對缺失值的處理體現(xiàn)在兩個方面：特征選擇和生成決策樹。初始條件下對每個樣本的權(quán)重置為1。

特征選擇：在選取最優(yōu)特征時，計算出每個特征的信息增益后，需要乘以一個**“非缺失值樣本權(quán)重占總樣本權(quán)重的比例”**作為系數(shù)來對比每個特征信息增益的大小

生成決策樹：在生成決策樹時，對于缺失的樣本我們按照一定比例把它歸屬到每個特征值中，比例為該特征每一個特征值占非缺失數(shù)據(jù)的比重

關(guān)于C4.5和CART回歸樹

作為ID3的改進版本，C4.5克服了許多缺陷，但是它自身還是存在不少問題：

C4.5的熵運算中涉及了對數(shù)運算，在數(shù)據(jù)量大的時候效率非常低。

C4.5的剪枝過于簡單

C4.5只能用于分類運算不能用于回歸

當特征有多個特征值是C4.5生成多叉樹會使樹的深度加深

————————————————

版權(quán)聲明：本文為CSDN博主「Sarah Huang」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。

原文鏈接：

C4.5算法

C4.5是一系列用在機器學習和數(shù)據(jù)挖掘的分類問題中的算法。它的目標是監(jiān)督學習：給定一個數(shù)據(jù)集，其中的每一個元組都能用一組屬性值來描述，每一個元組屬于一個互斥的類別中的某一類。C4.5的目標是通過學習，找到一個從屬性值到類別的映射關(guān)系，并且這個映射能用于對新的類別未知的實體進行分類。

C4.5由J.Ross Quinlan在ID3的基礎(chǔ)上提出的。ID3算法用來構(gòu)造決策樹。決策樹是一種類似流程圖的樹結(jié)構(gòu)，其中每個內(nèi)部節(jié)點（非樹葉節(jié)點）表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉節(jié)點存放一個類標號。一旦建立好了決策樹，對于一個未給定類標號的元組，跟蹤一條有根節(jié)點到葉節(jié)點的路徑，該葉節(jié)點就存放著該元組的預(yù)測。決策樹的優(yōu)勢在于不需要任何領(lǐng)域知識或參數(shù)設(shè)置，適合于探測性的知識發(fā)現(xiàn)。

決策樹呈樹形結(jié)構(gòu)，在分類問題中，表示基于特征對實例進行分類的過程。學習時，利用訓(xùn)練數(shù)據(jù)，根據(jù)損失函數(shù)最小化的原則建立決策樹模型；預(yù)測時，對新的數(shù)據(jù)，利用決策模型進行分類。

決策樹是一種通過對特征屬性的分類對樣本進行分類的樹形結(jié)構(gòu)，包括有向邊以及三類節(jié)點：

上圖給出了（二叉）決策樹的示例。決策樹具有以下特點：

決策樹學習的本質(zhì)是從訓(xùn)練集中歸納出一組分類規(guī)則。但隨著分裂屬性次序的不同，所得到的決策樹也會不同。如何得到一棵決策樹既對訓(xùn)練數(shù)據(jù)有較好的擬合，又對未知數(shù)據(jù)有很好的預(yù)測呢？

首先，我們要解決兩個問題：

一般的，一顆決策樹包含一個根節(jié)點、若干個內(nèi)部結(jié)點和若干個葉結(jié)點；葉結(jié)點則對應(yīng)于一個屬性冊書；每個葉結(jié)點包含的樣本集合根據(jù)屬性測試的結(jié)果被劃分到子結(jié)點中；根結(jié)點包含樣本全集，從根結(jié)點到每個葉結(jié)點的路徑對飲過了一個判定測試序列。決策樹學習的目的是為了產(chǎn)生一顆泛化能力強的決策樹，其基本流程遵循簡單且只管的“分而治之”（divide-and-conquer）策略，如下圖所示：

顯然，決策樹的生成是一個遞歸的過程。在決策樹基本算法中，有三種情形會導(dǎo)致遞歸返回：

在第二種情形下，我們把當前結(jié)點標記為葉結(jié)點，并且將其類別設(shè)定為該結(jié)點所含樣本最多的類別；在第三種情形下，同樣把當前結(jié)點標記為葉結(jié)點，但將其類別設(shè)定為其父結(jié)點所含樣本最多類別。注意這兩種情形的處理實質(zhì)不同：情形二是在利用當前結(jié)點的后驗分布，而情形三則是把父結(jié)點的樣本分布當做當前結(jié)點的先驗分布。

決策樹學習的關(guān)鍵在于如何選擇最優(yōu)劃分屬性。一般而言，隨著劃分過程的不斷進行，我們希望決策樹的分支結(jié)點所包含的樣本盡可能屬于同一類別，即結(jié)點的“純度”越來越高。

“信息熵”（information entropy）是度量樣本集合純度最常用的一種指標。假定當前樣本集合中第k類樣本所占比例為，則的信息熵定義為

的值越小，則的純度越高。

假定離散屬性有個可能的取值 ,若使用來對樣本集合進行劃分，則會產(chǎn)生個分支結(jié)點，其中第v個分支結(jié)點包含了中所有在屬性上取值為的樣本，記為，我們根據(jù)上述公式計算出的信息熵，再考慮到不同的分支結(jié)點所包含的樣本數(shù)不同，給分支結(jié)點賦予權(quán)重，即樣本越多的分支結(jié)點影響越大，于是可以計算出用屬性對樣本集合進行劃分所獲得的"信息增益"（information gain）

一般而言，信息增益越大，則意味著使用屬性a來進行劃分所獲得的“純度提升越大”。因此，我們可用信息增益來進行決策樹的劃分屬性選擇。

實際上，信息增益準則對可取值數(shù)目較多的屬性有所偏好（如何以序號作為劃分屬性，每一個事物作為一個單獨存在的類別的時候，信息增益往往會很高，但是這樣進行劃分并沒有什么意義），為了減少這種偏好可能帶來的不利影響，著名的C4.5算法并不是直接使用信息增益，而是使用增益率（gain ratio）來選擇最優(yōu)的劃分屬性。增益率的定義為：

值得注意的是：增益率準則對可取值數(shù)目較少的屬性有所偏好，因此C4.5算法并不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發(fā)式：先從候選劃分屬性中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的

CART決策樹使用“基尼指數(shù)”來選擇劃分屬性。數(shù)據(jù)集的純度可用基尼值來度量：

直觀來說，反映了從數(shù)據(jù)集中隨機抽取兩個樣本，其類別標記不一致的概率，因此值越小，則數(shù)據(jù)集的純度就越高。屬性的基尼指數(shù)定義為：

于是，我們在候選屬性集合中，選擇那個使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性，即

銀行希望能夠通過一個人的信息（包括職業(yè)、年齡、收入、學歷）去判斷他是否有貸款的意向，從而更有針對性地完成工作。下表是銀行現(xiàn)在能夠掌握的信息，我們的目標是通過對下面的數(shù)據(jù)進行分析建立一個預(yù)測用戶貸款一下的模型。

上表中有4個客戶的屬性，如何綜合利用這些屬性去判斷用戶的貸款意向？決策樹的做法是每次選擇一個屬性進行判斷，如果不能得出結(jié)論，繼續(xù)選擇其他屬性進行判斷，直到能夠“肯定地”判斷出用戶的類型或者是上述屬性都已經(jīng)使用完畢。比如說我們要判斷一個客戶的貸款意向，我們可以先根據(jù)客戶的職業(yè)進行判斷，如果不能得出結(jié)論，再根據(jù)年齡作判斷，這樣以此類推，直到可以得出結(jié)論為止。決策樹用樹結(jié)構(gòu)實現(xiàn)上述的判斷流程，如圖所示：

以熵作為節(jié)點復(fù)雜度的統(tǒng)計量，分別求出下面例子的信息增益，圖3.1表示節(jié)點選擇屬性1進行分裂的結(jié)果，圖3.2表示節(jié)點選擇屬性2進行分裂的結(jié)果，通過計算兩個屬性分裂后的信息增益，選擇最優(yōu)的分裂屬性。

屬性一

屬性二

由于，所以屬性1是比屬性2更優(yōu)的分裂屬性，故而選擇屬性1作為分裂屬性。

由于，故而選擇屬性2作為分裂屬性。

剪枝（pruning）是決策樹學習算法對付“過擬合”的主要手段。在決策樹學習中，為了盡可能正確分類訓(xùn)練樣本，結(jié)點劃分過程將不斷重復(fù)，有事會造成決策樹分支過多，這是就可能因為訓(xùn)練樣本學得太好了，以致把訓(xùn)練集自身的一些特點黨組喲所有數(shù)據(jù)都具有的一般性質(zhì)而導(dǎo)致過擬合。因此，可通過主動去掉一些分支來降低過擬合的風險。

其中{1,2,3,6,7,10,14,15,16,17}為測試集，{4,5,8,9,11,12,13}為訓(xùn)練集。

預(yù)剪枝是要對劃分前后泛化性能進行評估。對比決策樹某節(jié)點生成前與生成后的泛化性能。

2.計算訓(xùn)練集的信息增益，得知臍部的信息增益最大，因此按照臍部進行劃分。又因為在訓(xùn)練集中，凹陷特征好瓜的占比多，因此凹陷劃分為好瓜，稍凹特征好過占比多，因此將其標記為好瓜，因此按照臍部劃分的子樹結(jié)果如下：

劃分后，對比結(jié)果如下：

由圖可知，預(yù)剪枝使得很多分支沒有展開，這不僅降低了過擬合的風險，還顯著減少了決策樹的訓(xùn)練時間開銷和測試時間。但是，有些分支雖當前不能提升泛化性。甚至可能導(dǎo)致泛化性暫時降低，但在其基礎(chǔ)上進行后續(xù)劃分卻有可能導(dǎo)致顯著提高，因此預(yù)剪枝的這種貪心本質(zhì)，給決策樹帶來了欠擬合的風險。

后剪枝表示先從訓(xùn)練集中生成一顆完整決策樹。

對比標記節(jié)點的劃分類與各數(shù)據(jù)的真實分類，計算準確率，如下表所示：

生成的決策樹，在驗證集上的準確度為3/7*100%=42.9%.

對比預(yù)剪枝與后剪枝生成的決策樹，可以看出，后剪枝通常比預(yù)剪枝保留更多的分支，其欠擬合風險很小，因此后剪枝的泛化性能往往由于預(yù)剪枝決策樹。但后剪枝過程是從底往上裁剪，因此其訓(xùn)練時間開銷比前剪枝要大。

當前題目：c4.5剪枝java代碼的簡單介紹
文章來源：http://muchs.cn/article16/doocpgg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、App設(shè)計、自適應(yīng)網(wǎng)站、手機網(wǎng)站建設(shè)、網(wǎng)站設(shè)計公司、服務(wù)器托管

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

c4.5剪枝java代碼的簡單介紹

決策樹（Decision Tree）

用python實現(xiàn)紅酒數(shù)據(jù)集的ID3,C4.5和CART算法？

C4.5算法

用python實現(xiàn)紅酒數(shù)據(jù)集的ID3,C4.5和CART算法？