決策樹

說明

本部落格為本人學習過程中的筆記記錄，加上一些思路總結，可能比較瑣碎，希望閱讀者見諒。

簡介

​ 決策樹，作為衆多樹模型的基礎，以它來作為另一個的開篇最合适不過。其核心思想就是從資料中學出一套分類規則，這樣的分類規則有多種（意味着決策樹不唯一），我們的目的，是找到那個在局部和全局上都表現不錯的：局部（從資料中學到的分類效果很好，誤差小），全局（未知資料中分類效果也很好，魯棒性好）。

俯視圖

決策樹，顧名思義，就是 決策/ 樹。但實際過程中卻是反過來的：

1. ​ 從資料中學 出一顆樹。
2. ​ 剪枝（樹模型都很容易過拟和，減枝可以緩和這種現象）
3. ​ 用學到的樹分類。

一些概念

上面這張圖可以視作一個決策樹，它一共有兩個比較重要的元素：

1. 非葉子節點（包含根節點，也叫決策點，每個節點都表示**選擇的不同特征**，這個特征用來将樣本分類）
        2. 葉子節點（每個節點表示我分出來的類，當然，不同節點可以表示同一類，但是每個節點裡的樣本是互斥的）
           

特征選擇

這小節就是針對上面1中加粗的部分進行解釋，如何進行特征選擇？

熵

嚴格來說，屬于資訊論的東西，舉一個實際例子，假設我原始樣本的标簽是A[0,0,0,1,1,1,0,0,1,1],經過我樣本的某個特征，我的樣本可以分成B[0,0,0,1], C[1,1,0,0,1,1],我怎樣以數學的方式衡量這個選擇的好壞？？

​ 化學裡叫混亂程度，在這裡，表面了解：屬于同一類樣本占比越多，混亂程度越低，熵越小。我可以用熵的計算公式得到熵，那上面的分布可以變為： 熵A,熵B,熵C,而怎樣衡量選擇的好壞，做差就好了 熵A - （熵B + 熵C）,這個式子的結果還有個名字，資訊增益。是以綜上，熵充當了什麼成分不言而喻。

下面是它的計算公式，其中的機率均通過統計得到，如A中0的機率，怎麼算應該知道吧…：

目标明确

​ 希望您知道目标函數的含義，對于一顆決策樹，當然也是要有個目标函數來衡量的，而衡量的思想：随着樹深度的增加,熵在快速減小。換句人聽的懂的，就是從根節點開始，從上往下的非葉子節點，我都盡可能的讓那些使熵迅速減少的特征位于前面，即如果用資訊增益衡量的話，使資訊增益大的特征排在前面。

​ 最後我怎樣衡量建構的樹呢？（隻考慮局部最優）

其中t是葉子節點，Nt是目前葉子節點裡的樣本個數，H(T)是目前葉子節點的熵。

特征選擇舉例

假如我們有如下的資料：前四列是 特征，最後一列是标簽。

​ 最開始的根節點處的特征選哪個？可以通過如下操作：

​ 分别計算每一個特征分類後的熵，計算資訊增益，選擇最大的特征，作為根節點的特征。此過程遞歸，就是剩下特征的操作。

不同衡量标準

1. ID3（一個算法）:資訊增益。
2. C4.5:資訊增益率。
3. CART: （分類）Gini系數 （回歸）MSE

​ 以上是版本的更疊下，不同的衡量标準，其實目的用法一樣，隻是計算公式不一樣，當然，考慮的細節也有差異。

遞歸算法

談談遞歸

1. 遞歸程式更加簡潔，更容易理清意思/也不容易理清意思。

 2. 遞歸程式本質可以了解為棧，先進後出。

 3. 遞歸并不是一個為性能優化而生的程式思想，相反，在很多情況下，其對性能的消耗是巨大的。

 4. 遞歸思想的本質是大問題化為數個解決方案相同的小問題。

 5. 學遞歸有這麼一個現象，你可能看得懂，但是有時候自己就是寫不出來，恭喜你，你其實還沒有了解遞歸的本質，練的不夠多。巧了——我也是.....  
           

遞歸算法要求。遞歸算法所展現的“重複”一般有三個要求：

​ (1) 是每次調用在規模上都有所縮小（通常是減半）；

　　(2) 是相鄰兩次重複之間有緊密的聯系，前一次要為後一次做準備（通常前一次的輸出就作為後一次的輸入）；

　　(3) 是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用将會成為死循環而不能正常結束。

斐波納契數列

代碼

if (n <= 1) /* base case */
  return n;
else /* recursive caseS */
  return f(n-1) + f(n-2);
           

代碼結果可視化

見到的遞歸最好的可視化是樹形結構的呈現形式，所有的葉子節點表示走不下去了，也就是所謂的出口，所有的非葉子節點都對最後的結果計算沒有意義。上面那個可視化的圖，真的好美妙。 具體可視化網址見參考小節。

決策樹生成

決策樹的生成對應最開始說的“局部”，也是上面說過的，這是一個遞歸過程。

IE3

減枝

預減枝

​ 預剪枝就是在樹的建構過程（隻用到訓練集），設定一個門檻值（樣本個數小于預定門檻值或GINI指數小于預定門檻值），使得當在目前分裂節點中分裂前和分裂後的誤差超過這個門檻值則分列，否則不進行分裂操作。

​ 看了看預減枝的代碼，但是有個問題，測試集這樣驗證有問題，因為沒有用到樹的結構資訊，隻是單純用了這個節點，測試集也隻是單純用了兩列。想象一下，我從根節點到中間某個節點，一定是經過好幾個節點特征分過的，此時到這個節點的樣本數量肯定少了，但是預剪枝裡，卻是沒有這個過程噢，隻是單純用測試集合所有樣本去驗證這個節點，感覺并不好。。。

​ 當然，本來預剪枝就沒後剪枝好，這裡隻是單純看了代碼吐槽下，下面給出看到代碼的關鍵邏輯代碼。

感謝大佬提供代碼參考：

https://github.com/appleyuchi/Decision_Tree_Prune/tree/master/ID3-REP-post_prune-Python-draw

# 篩選條件
# 如果 繼續分後的錯誤率 < 不分的錯誤率
if testing_feat(bestFeatLabel, dataSet, test_data, labels_copy) < testingMajor(majorityCnt(classList),test_data)
           

#這個用于預剪枝，目的：測試目前分了節點後在測試集上的錯誤率

def testing_feat(feat, train_data, test_data, labels):
    print"train_data=",json.dumps(train_data,ensure_ascii=False)
    class_list = [example[-1] for example in train_data]
    bestFeatIndex = labels.index(feat)
    train_data = [example[bestFeatIndex] for example in train_data]
    test_data = [(example[bestFeatIndex], example[-1]) for example in test_data]
    all_feat = set(train_data)
    error = 0.0
    for value in all_feat:
        class_feat = [class_list[i] for i in range(len(class_list)) if train_data[i] == value]
        major = majorityCnt(class_feat)
        for data in test_data:
            if data[0] == value and data[1] != major:
                error += 1.0
    # print 'myTree %d' % error
    return error
           

後減枝

文字參考：https://blog.csdn.net/t15600624671/article/details/78895267

代碼參考：https://github.com/appleyuchi/Decision_Tree_Prune/tree/master/ID3-REP-post_prune-Python-draw

（1）後剪枝是在用訓練集建構好一顆決策樹後，利用測試集進行的操作。

（2）在回歸樹一般用總方差計算誤差（即用葉子節點的值減去所有葉子節點的均值）。

​ 後剪枝的算法包括：

Reduced-Error Pruning (REP,錯誤率降低剪枝）

​ 這個思路很直接，完全的決策樹不是過度拟合麼，我再搞一個測試資料集來糾正它。對于完全決策樹中的每一個非葉子節點的子樹，我們嘗試着把它替換成一個葉子節點，該葉子節點的類别我們用子樹所覆寫訓練樣本中存在最多的那個類來代替，這樣就産生了一個簡化決策樹，然後比較這兩個決策樹在測試資料集中的表現，如果簡化決策樹在測試資料集中的錯誤比較少，那麼該子樹就可以替換成葉子節點。

​ 該算法以bottom-up的方式周遊所有的子樹，直至沒有任何子樹可以替換使得測試資料集的表現得以改進時，算法就可以終止。

實作

本來以為要動态規劃了，但是找到的代碼看完讓我驚了一下，還可以這樣？？？？有點新奇啊，而且個人感覺這種做法行的通。

​ 本人将原有的後減枝代碼融到了自己的代碼裡，預減枝由于覺得不好，就沒加，下面展示關鍵代碼：

if is_post:
    # 繼續分錯誤的損失 - 部分錯誤的損失 > 門檻值
	if self.testing(myTree, test_data,test_feature_name) - self.testingMajor(self.majorityCnt(labels), test_data) > theta:
    	return self.majorityCnt(labels)
   # 實作後剪枝操作
   # 無視目前的myThree,直接傳回一個葉子節點,等效于實作了REP後剪枝
        return myTree
           

1. 這裡将原代碼的比較改為做差，與門檻值比較，更加合理點。
2. 此代碼位于生成樹的代碼内，位于最後，是不是很奇怪，不是有了完整的樹再減枝葉，其實這裡這種寫法個人感覺也似等價的，因為它的參數裡有樹結構,也就是這裡它把樹的結構考慮進去了。個人感覺很秒啊…

​ 由于粘貼代碼格式太亂，而且本身其實這裡想讓看看上面那個函數的位置，是以截一個全局的圖出來，宏觀看看。

離散化和連續化

​ 其實本來以為決策樹覺得兩天基本就完事兒了，但是由于想到所謂做戲做全套，就一直在考慮各種問題，上面所有的代碼是一個不斷優化的過程（當然本人由于自帶bug體，改bug用的時間也很長…）

​ 本人參考代碼嘗試加入支援連續化，但是實際情況下倒不是難,而是很難全面，自己實操過程中把代碼改的太過備援複雜，而且容錯性太低太低了，當然參考代碼寫的說實話也不怎麼樣，甚至本身邏輯在這裡就有問題，是以最後本人删除了連續化操作。

可視化

這裡直接使用的原代碼函數，沒有去去研究畫圖函數。

CART

分類樹

代碼refer: https://github.com/RRdmlearning/Decision-Tree

參考代碼作者對應知乎：https://zhuanlan.zhihu.com/p/32164933

​ 可能你會碰到需要額外安裝的包，本人Ubuntu16碰到了Bug，用于以下指令安裝正常：

pip install pydot>=1.2.4
sudo apt-get install graphviz
           

​ 其實分類還是那個味道，基本換湯不換藥，這裡由于換了參考代碼，其實最大的變化是資料結構上的變化，原本是字典存儲，下面這種資料結構在針對小資料集時更友善，因為很多資訊都存了下來，比單純用字典好很多。下面是其代碼：

# 樹的結構由它存儲
class Tree:
    def __init__(self, value=None, trueBranch=None, falseBranch=None, results=None, col=-1, summary=None, data=None):

        # 最優分割列
        self.col = col
        # 目前列内選擇的分割點
        self.value = value

        # 左右(是否為此值) 分支
        self.trueBranch = trueBranch
        self.falseBranch = falseBranch

        # 此節點上的分類結果（葉子節點才會設定）
        self.results = results

        # 存儲葉子節點上的資料資訊
        self.data = data

        # 類似于日志資訊,畫圖時需要
        self.summary = summary
           

———— 1.這裡個人同樣沒有深究畫圖函數，有興趣的朋友可以自己細讀。

————2.參考代碼減枝操作與李航樹上的僞代碼并不相同，也算是減枝的一種，如下面介紹

減枝

Critical Value Pruning：

　　該方法由Mingers1987年發明。

　　樹的生成過程中，會得到選擇屬性及分裂值的評估值，設定一個門檻值，所有小于此門檻值的節點都剪掉

回歸樹

​ 在處理回歸問題時，CART算法使用均方誤差MSE(Mean Squared Error)來衡量節點的不純度；MSE越大，不純度越高。

這裡沒有找到好的參考代碼，本人直接參考分類樹進行了修改，隻改了兩部分：

1. MSE替換gini篩選特征
2. 葉子節點取均值表示改葉子節點的回歸值。

個人了解的回歸樹隻需修改這兩點，若不全面請指教

上代碼

注意： 該代碼内資料無實際參考意義，隻為跑通代碼使用。

https://github.com/MaybeWeCan/DecisionTree

參考

[1] 李航 《統計機器學習》

[2] B站 唐宇迪——決策樹

視訊： https://www.bilibili.com/video/av26086646?p=3

​ 對應代碼：https://pan.baidu.com/s/19kfm9F68MNmAz-QshadFtg 密碼：l4l7

[3] 遞歸算法

​ 算法講解：https://chenqx.github.io/2014/09/29/Algorithm-Recursive-Programming/

​ 可視化網址：https://visualgo.net/zh

*注：其餘參考代碼内或文中間已經指明，感謝這些大佬的分享。