看完這篇--決策樹，80%都懂了

1. 什麼是決策樹 1.1 決策樹的基本思想其實用一下圖檔能更好的了解LR模型和決策樹模型算法的根本差別，我們可以思考一下一個決策問題：是否去...

1. 什麼是決策樹

1.1 決策樹的基本思想

其實用一下圖檔能更好的了解LR模型和決策樹模型算法的根本差別，我們可以思考一下一個決策問題：是否去相親，一個女孩的母親要給這個女海介紹對象。

大家都看得很明白了吧！LR模型是一股腦兒的把所有特征塞入學習，而決策樹更像是程式設計語言中的if-else一樣，去做條件判斷，這就是根本性的差別。

1.2 “樹”的成長過程

決策樹基于“樹”結構進行決策的，這時我們就要面臨兩個問題：

“樹”怎麼長。
這顆“樹”長到什麼時候停。

弄懂了這兩個問題，那麼這個模型就已經建立起來了，決策樹的總體流程是“分而治之”的思想，一是自根至葉的遞歸過程，一是在每個中間節點尋找一個“劃分”屬性，相當于就是一個特征屬性了。接下來我們來逐個解決以上兩個問題。

這顆“樹”長到什麼時候停

目前結點包含的樣本全屬于同一類别，無需劃分；例如：樣本當中都是決定去相親的，屬于同一類别，就是不管特征如何改變都不會影響結果，這種就不需要劃分了。
目前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分；例如：所有的樣本特征都是一樣的，就造成無法劃分了，訓練集太單一。
目前結點包含的樣本集合為空，不能劃分。

1.3 "樹"怎麼長

在生活當中，我們都會碰到很多需要做出決策的地方，例如：吃飯地點、數位産品購買、旅遊地區等，你會發現在這些選擇當中都是依賴于大部分人做出的選擇，也就是跟随大衆的選擇。其實在決策樹當中也是一樣的，當大部分的樣本都是同一類的時候，那麼就已經做出了決策。

我們可以把大衆的選擇抽象化，這就引入了一個概念就是純度，想想也是如此，大衆選擇就意味着純度越高。好，在深入一點，就涉及到一句話：資訊熵越低，純度越高。我相信大家或多或少都聽說過“熵”這個概念，資訊熵通俗來說就是用來度量包含的“資訊量”，如果樣本的屬性都是一樣的，就會讓人覺得這包含的資訊很單一，沒有差異化，相反樣本的屬性都不一樣，那麼包含的資訊量就很多了。

一到這裡就頭疼了，因為馬上要引入資訊熵的公式，其實也很簡單：

Pk表示的是：目前樣本集合D中第k類樣本所占的比例為Pk。

資訊增益

廢話不多說直接上公式：

看不懂的先不管，簡單一句話就是：劃分前的資訊熵--劃分後的資訊熵。表示的是向純度方向邁出的“步長”。

好了，有了前面的知識，我們就可以開始“樹”的生長了。

1.3.1 ID3算法

解釋：在根節點處計算資訊熵，然後根據屬性依次劃分并計算其節點的資訊熵，用根節點資訊熵--屬性節點的資訊熵=資訊增益，根據資訊增益進行降序排列，排在前面的就是第一個劃分屬性，其後依次類推，這就得到了決策樹的形狀，也就是怎麼“長”了。

如果不了解的，可以檢視我分享的圖檔示例，結合我說的，包你看懂：

第一張圖.jpg
第二張圖.jpg
第三張圖.jpg
第四張圖.jpg

不過，資訊增益有一個問題：對可取值數目較多的屬性有所偏好，例如：考慮将“編号”作為一個屬性。為了解決這個問題，引出了另一個算法C4.5。

1.3.2 C4.5

為了解決資訊增益的問題，引入一個資訊增益率：

其中：

屬性a的可能取值數目越多(即V越大)，則IV(a)的值通常就越大。資訊增益比本質：是在資訊增益的基礎之上乘上一個懲罰參數。特征個數較多時，懲罰參數較小；特征個數較少時，懲罰參數較大。不過有一個缺點：

缺點：資訊增益率偏向取值較少的特征。

使用資訊增益率：基于以上缺點，并不是直接選擇資訊增益率最大的特征，而是現在候選特征中找出資訊增益高于平均水準的特征，然後在這些特征中再選擇資訊增益率最高的特征。

1.3.3 CART算法

數學家真實聰明，想到了另外一個表示純度的方法，叫做基尼指數(讨厭的公式)：

表示在樣本集合中一個随機選中的樣本被分錯的機率。舉例來說，現在一個袋子裡有3種顔色的球若幹個，伸手進去掏出2個球，顔色不一樣的機率，這下明白了吧。Gini(D)越小，資料集D的純度越高。

舉個例子

假設現在有特征 “學曆”，此特征有三個特征取值： “大學”，“碩士”， “博士”，

當使用“學曆”這個特征對樣本集合D進行劃分時，劃分值分别有三個，因而有三種劃分的可能集合，劃分後的子集如下：

1.劃分點： “大學”，劃分後的子集合： {大學}，{碩士，博士}

2.劃分點： “碩士”，劃分後的子集合： {碩士}，{大學，博士}

3.劃分點： “碩士”，劃分後的子集合： {博士}，{大學，碩士}}

對于上述的每一種劃分，都可以計算出基于劃分特征= 某個特征值将樣本集合D劃分為兩個子集的純度：

因而對于一個具有多個取值（超過2個）的特征，需要計算以每一個取值作為劃分點，對樣本D劃分之後子集的純度Gini(D,Ai)，(其中Ai 表示特征A的可能取值)

然後從所有的可能劃分的Gini(D,Ai)中找出Gini指數最小的劃分，這個劃分的劃分點，便是使用特征A對樣本集合D進行劃分的最佳劃分點。到此就可以長成一棵“大樹”了。

1.3.4 三種不同的決策樹

ID3：取值多的屬性，更容易使資料更純，其資訊增益更大。

訓練得到的是一棵龐大且深度淺的樹：不合理。
C4.5：采用資訊增益率替代資訊增益。
CART：以基尼系數替代熵，最小化不純度，而不是最大化資訊增益。

2. 樹形結構為什麼不需要歸一化?

因為數值縮放不影響分裂點位置，對樹模型的結構不造成影響。

按照特征值進行排序的，排序的順序不變，那麼所屬的分支以及分裂點就不會有不同。而且，樹模型是不能進行梯度下降的，因為建構樹模型（回歸樹）尋找最優點時是通過尋找最優分裂點完成的，是以樹模型是階躍的，階躍點是不可導的，并且求導沒意義，也就不需要歸一化。

既然樹形結構（如決策樹、RF）不需要歸一化，那為何非樹形結構比如Adaboost、SVM、LR、Knn、KMeans之類則需要歸一化。

對于線性模型，特征值差别很大時，運用梯度下降的時候，損失等高線是橢圓形，需要進行多次疊代才能到達最優點。

但是如果進行了歸一化，那麼等高線就是圓形的，促使SGD往原點疊代，進而導緻需要的疊代次數較少。

3. 分類決策樹和回歸決策樹的差別

Classification And Regression Tree(CART)是決策樹的一種，CART算法既可以用于建立分類樹（Classification Tree），也可以用于建立回歸樹（Regression Tree），兩者在建樹的過程稍有差異。

回歸樹：

CART回歸樹是假設樹為二叉樹，通過不斷将特征進行分裂。比如目前樹結點是基于第j個特征值進行分裂的，設該特征值小于s的樣本劃分為左子樹，大于s的樣本劃分為右子樹。

\[R_1(j,s)=\{x|x^{(j)}\leq s\} and R_2(j,s)=\{x|x^{(j)}>s\}

而CART回歸樹實質上就是在該特征次元對樣本空間進行劃分，而這種空間劃分的優化是一種NP難問題，是以，在決策樹模型中是使用啟發式方法解決。典型CART回歸樹産生的目标函數為：

\[\sum_{x_i\in R_m}(y_i-f(x_i))^2

是以，當我們為了求解最優的切分特征j和最優的切分點s，就轉化為求解這麼一個目标函數：

\[min_{j,s}[min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]

是以我們隻要周遊所有特征的的所有切分點，就能找到最優的切分特征和切分點。最終得到一棵回歸樹。

參考文章：經典算法詳解--CART分類決策樹、回歸樹和模型樹

4. 決策樹如何剪枝

決策樹的剪枝基本政策有預剪枝 (Pre-Pruning) 和後剪枝 (Post-Pruning)。

預剪枝：其中的核心思想就是，在每一次實際對結點進行進一步劃分之前，先采用驗證集的資料來驗證如果劃分是否能提高劃分的準确性。如果不能，就把結點标記為葉結點并退出進一步劃分；如果可以就繼續遞歸生成節點。
後剪枝：後剪枝則是先從訓練集生成一顆完整的決策樹，然後自底向上地對非葉結點進行考察，若将該結點對應的子樹替換為葉結點能帶來泛化性能提升，則将該子樹替換為葉結點。

參考文章：決策樹及決策樹生成與剪枝

5. 代碼實作

GitHub：https://github.com/NLP-LOVE/ML-NLP/blob/master/Machine%20Learning/3.Desition%20Tree/DecisionTree.ipynb

【機器學習通俗易懂系列文章】

作者：@mantchs

GitHub：https://github.com/NLP-LOVE/ML-NLP

歡迎大家加入讨論！共同完善此項目！qq群号：【541954936】

看完這篇--決策樹，80%都懂了 - mantch

posted on

2019-07-07 10:06

mantch

閱讀(7011)

評論(2)

編輯

舉報