標籤：

機器學習之決策樹(C4.5演算法)

01-26

由於較多公式，所以我將部分內容轉為圖片進行上傳，請見諒。清晰版請訪問weizhixiaoyi.com查看，你也可以關注我公眾號『謂之小一』，後台直接向我要pdf版本，如有相關問題直接後台詢問，隨時回答。

1.決策樹簡介

我們已有如下所示數據集，特徵屬性包含天氣、溫度、濕度、風速，然後根據這些數據去分類或預測能否去打高爾夫球，針對此類問題你會怎麼解決呢。

正當你苦思冥想之時，天空之中突然飄來一張決策圖，發現這圖好像一張倒著的樹啊，於是你命名為決策樹。你發現可直接根據決策樹得到相應結果，高興的像個300斤的孩子。但下次再面臨這樣的問題時，還能夠那麼好運嘛？於是你陷入苦苦思考之中，怎樣才能得到分類決策樹呢。

2.C4.5演算法

上古之神賜予你智慧：C4.5是一系列用在機器學習和數據挖掘中分類問題的演算法，它的目標是監督學習。即給定一個數據集，其中的每一個元組都能用一組屬性值描述，每一個元組屬於一個互斥的類別中的某一類。C4.5的目標是通過學習，找到一個從屬性值到類別的映射關係，並且這個映射能夠用於對新的類別未知的實體進行分類。

C4.5是在ID3的基礎上提出的。ID3演算法用來構造決策樹。決策樹是一種類似流程圖的樹結構，其中每個內部節點（非樹葉節點）表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉節點存放一個類標號。一旦建立好決策樹，對於一個未給定類標號的元組，跟蹤一條有根節點到葉節點的路徑，該葉節點就存放著該元組的預測。上述數據集有4個屬性，屬性集合A={天氣、溫度、濕度、風速}，類別集合D={進行、取消}。我們先做一些假設

2.1信息增益

信息增益實際上是ID3演算法中用來進行屬性選擇度量的，具有較高信息增益的屬性來作為節點N的分裂屬性。該屬性使結果劃分中的元組分類所需信息量最小。

計算類別信息熵:類別信息熵表示的是所有樣本中各種類別出現的不確定之和。根據熵的概念，熵越大，不確定性就越大，把事情理解清楚所需要的信息量就越多。對D中的元組分類所需的期望信息表達式如下，同時計算出上述數據的期望信息

計算每個屬性的信息熵:每個屬性的信息熵相當於條件熵。表示的是在某種屬性的條件下，各種類別出現的不確定之和。屬性的信息熵越大，表示這個屬性中擁有的樣本類別越亂。現在假定按照屬性集合C劃分D中的元組，且屬性Ci將D劃分成v個不同的類。在該劃分之後，為了得到準確的分類還需要下式進行度量。

計算信息增益:信息增益=熵-條件熵，在這裡表示為類別信息熵-屬性信息熵。它表示的是信息不確定性減少的程度。如果一個屬性的信息增益越大，就表示用這個屬性進行樣本劃分可以更好的減少劃分後樣本的不確定性，選擇該屬性就可以更快更好的完成我們的分類目標。

但是我們假設這種情況，每個屬性中每個類別都只有一個樣本，那這樣屬性信息熵就等於0，根據信息增益就無法選擇出有效分類特徵，所以C4.5演算法選擇使用信息增益率對ID3進行改進。

2.2信息增益率

計算屬性分裂信息度量:用分裂信息度量來考慮某種屬性進行分裂時分支的數量信息和尺寸信息，我們把這些信息稱為屬性的內在信息。信息增益率用信息增益 / 內在信息表示，信息增益率會導致屬性的重要性隨著內在信息的增大而減小（也就是說，如果這個屬性本身不確定性就很大，那我就越不傾向於選取它），這樣算是對單純用信息增益有所補償。信息增益率定義如下

天氣的信息增益率最高，選擇天氣為分裂屬性。分裂之後，天氣是「陰」的條件下無其他分裂點，所以把它定義為葉子節點，選擇較亂的結點繼續分裂。重複上述過程，直到演算法完成，我們便可得到決策樹。

3.樹剪枝

決策樹創建過程中，由於數據中的雜訊和離群點，許多分支反應的是訓練數據中的異常。剪枝方法是用來處理這種過分擬合的問題，通常剪枝方法都是使用統計度量，減去最不可靠的分支。減枝方法分為先減枝和後剪枝。

3.1先剪枝

先剪枝方法通過提前停止樹的構造(比如決定在某個節點不再分裂或劃分訓練元組的自己)。但先剪枝有個視野效果缺點問題，也就是說在相同的標準下，也許當前擴展不能滿足要求，但更進一步又能滿足要求，這樣會過早停止樹的生長。先剪枝可通過以下方法

  • 當決策樹達到一定的高度就停止決策樹的生長。
  • 到達節點的實例個數小於某個閾值的時候也可以停止樹的生長，不足之處是不能處理那些數量比較小的特殊情況。
  • 計算每次擴展對系統性能的增益，如果小於某個閾值就可以停止樹的生長。

3.2後剪枝

後剪枝是由完全生長的樹剪去子樹而形成，通過刪除節點的分支並用樹葉來替換它，樹葉一般用子樹中最頻繁的類別來標記。C4.5採用悲觀剪枝法，它使用訓練集生成決策樹，然後對生成的決策樹進行剪枝，通過對比剪枝前後分類錯誤率來驗證是否進行剪枝。

把一顆子樹的分類(具有多個葉子結點)的分類用一個葉子節點替換的話，在訓練集上的誤判率肯定是上升的，但是在新數據上則不一定，於是我們需要把子樹的誤判計算加上一個經驗性的懲罰因子。對於一顆葉子節點，它覆蓋了N個樣本，其中有E個錯誤，那麼該葉子節點的錯誤率為(E+0.5)/N。這個0.5就是懲罰因子，那麼一顆子樹，他有L個葉子節點，那麼該子樹的誤判率為

這樣的話我們可以看到一顆子樹雖然有多個子節點，但由於加上懲罰因子，所以子樹的誤判率未必佔到便宜。剪枝後內部節點變成葉子節點，其誤判個數J也需要加上一個懲罰因子，變成J+0.5。那麼子樹是否可以被剪枝就取決於剪枝後的錯誤J+0.5的標準範圍內。對於樣本的誤差率e，我們可以根據經驗把它估計成各種各樣的分布模型，比如二項式分布或正態分布。

假如決策樹正確分類的樣本值為1，錯誤分類的樣本值為0，該樹錯誤分類的概率(誤判率)為e(e為分布的固有屬性，可以統計出來)，那麼樹的誤判次數就是伯努利分布，我們可以估計出概述的誤差次數均值和標準值。

把子樹替換成葉子節點後，該葉子的誤判次數也是伯努利分布，其概率誤判率為(E+0.5)/N，因此葉子節點的誤判次數均值為

使用訓練數據時，子樹總是比替換為一個葉節點後產生的誤差小，但是使用校正後有誤差計算方法卻並非如此，當子樹的誤判個數減去標準差後大於對應葉節點的誤判個數，就決定剪枝

上述條件就是剪枝的標準。當然並不一定非要減去標準差，可以給定任意的置信區間，我們設定一定的顯著性因子，就可以估算出誤判次數的上下界。

4.Sklearn實現決策樹

我們以sklearn中iris數據作為訓練集，iris屬性特徵包括花萼長度、花萼寬度、花瓣長度、花瓣寬度，類別共三類，分別為Setosa、Versicolour、Virginca。

from sklearn.datasets import load_iris
from sklearn import tree

#引入數據
iris=load_iris()
X=iris.data
y=iris.target

#訓練數據和模型,採用ID3或C4.5訓練
clf=tree.DecisionTreeClassifier(criterion=entropy)
clf=clf.fit(X,y)

#引入graphviz模塊用來導出圖,結果圖如下所示
import graphviz
dot_data=tree.export_graphviz(clf,out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True,rounded=True,
special_characters=True)

graph=graphviz.Source(dot_data)
graph.view()

5.實際使用技巧

  • 對於擁有大量特徵的數據決策樹會出現過擬合的現象。獲得一個合適的樣本比例和特徵數量十分重要，因為在高維空間中只有少量的樣本的樹是十分容易過擬合的。
  • 訓練之前平衡數據集，以防止決策樹偏向於主導類。可以通過從每個類中抽取相等數量的樣本來進行類平衡，或者優選地通過將每個類的樣本權重 (sample_weight) 的和歸一化為相同的值。
  • 考慮實現進行降維(PCA、ICA)，使決策樹能夠更好地找到具有分辨性的特徵。
  • 通過 export 功能可以可視化您的決策樹。使用 max_depth=3作為初始樹深度，讓決策樹知道如何適應您的數據，然後再增加樹的深度。
  • 填充樹的樣本數量會增加樹的每個附加級別。使用 max_depth 來控制樹的大小防止過擬合。
  • 通過使用 min_samples_split 和 min_samples_leaf 來控制葉節點上的樣本數量。當這個值很小時意味著生成的決策樹將會過擬合，然而當這個值很大時將會不利於決策樹的對樣本的學習。

    6.推廣

更多內容請關注公眾號』謂之小一』，若有疑問可在公眾號後台提問，隨時回答，歡迎關注，內容轉載請註明出處。

weixin.qq.com/r/Ty_4oDP (二維碼自動識別)


推薦閱讀：

TAG:機器學習 | 決策樹 | sklearn |