決策樹

前言

參考了大佬的博客：博客地址

適合分析離散數據，若是連續數據需要轉換成離散數據再做分析(比如圖中的年齡)

結構

決策樹由節點和有向邊組成；節點可分為內部節點和葉節點

• 內部節點:特征
• 葉節點:類別
• 有向邊:特征的取值范圍

在用決策樹進行分類時，首先從根結點出發，對實例在該結點的對應屬性進行測試，接著會根據測試結果，將實例分配到其子結點；然后，在子結點繼續執行這一流程，如此遞歸地對實例進行測試并分配，直至到達葉結點；最終，該實例將被分類到葉結點所指示的結果中

在決策樹中，若把每個內部結點視為一個條件，每對結點之間的有向邊視為一個選項，則從根結點到葉結點的每一條路徑都可以看做是一個規則，而葉結點則對應著在指定規則下的結論。這樣的規則具有互斥性和完備性，從根結點到葉結點的每一條路徑代表了一類實例，并且這個實例只能在這條路徑上。從這個角度來看，決策樹相當于是一個 if-then 的規則集合，因此它具有非常好的可解釋性

熵

作用

表示隨機變量的不確定度；對于決策樹的節點來說，理想狀態是節點特征對樣本進行分類后，能最大程度降低樣本的熵;可以這樣理解，構建決策樹就是對特征進行層次選取，而衡量特征選取的合理指標，就是熵

定義

$$\begin{gathered} 對于在有限范圍內的離散隨機變量X,概率分布為: \\ P(X=x_i)=p_i,i=1,2,\dots ,n \end{gathered}$$

我們假設一個樣本中有k個類別，比如不同顏色的球

$$\begin{gathered} k=4 \\ {p}_{blue}=\frac{2}{7},p_{yellow}=\frac{2}{7},p_{red}=\frac{2}{7},p_{green}=\frac{1}{7} \end{gathered}$$
則離散隨機變量X的熵定義為
$$\begin{gathered} H(X)=?\sum _{i=1}^k{p}_{i}log{p}_i=?\sum _{i=1}^k\frac{|C_i|}{|D|}log\frac{|C_i|}{|D|} \\ {C}_i表示第i類樣本,D表示整個數據集 \end{gathered}$$
則X的熵僅與其分布有關，而與取值無關，H(X)也可以寫成H§
$$p_i\in [0,1],log{p}_i\in (?\infty ,0],?log{p}_i\in [0,+\infty )$$
當k很大時，H(X)也會變得很大

條件熵

引入

以天氣為例，晴天為A類，陰天為B類，雨天為C類；他們都有k=2個類別，即是/否
$$\begin{gathered} H(X_A)=?\sum _{i=1}^2{p}_{i}log{p}_i=?(\frac{1}{2}log\frac{1}{2}+\frac{1}{2}log\frac{1}{2})=log2 \\ H(X_B)=?\sum _{i=1}^2{p}_{i}log{p}_i=?(1log1+log0)=0 \\ H(X_C)=?\sum _{i=1}^2{p}_{i}log{p}_i=?(0log0+1log1)=0 \end{gathered}$$
整體天氣系統的熵
$$\begin{gathered} P(X_A)=\frac{8}{14},P(X_B)=\frac{3}{14},P(X_C)=\frac{3}{14} \\ H(X_{天氣})=\frac{8}{14}\times H(X_A)+\frac{3}{14}\times H(X_B)+\frac{3}{14}\times H(X_C)=\frac{4}{7}log2 \end{gathered}$$

定義

上面的例子其實就是在求條件熵
$$\begin{gathered} 概率統計中條件概率公式:P(A|B)=\frac{P(AB)}{P(B)} \\ 對于隨機變量(X,Y),其聯合分布P(X=x_i,Y=y_j)=p_{ij} \end{gathered}$$

$$\begin{gathered} H(Y|X)=\sum _{i=1}^k{p}_{i}H(Y|X=x_i) \\ H(Y|X):在X條件下的熵 \\ {p}_i:P(X=x_i) \end{gathered}$$

劃分選擇

信息增益

ID3算法選用的評估標準
$$\begin{gathered} g(D,X)=H(D)?H(D|X) \\ H(D|X)=\sum _{i=1}^k\frac{|C_i|}{|D|}H(X=x_i) \\ g(D,X)為信息增益，表示特征X使數據集D不確定性的減少程度 \end{gathered}$$

選擇根節點

將使信息增益G(D,X)最大的特征X作為根節點

信息增益率

C4.5算法選用的評估標準

為什么引入信息增益率?

以信息增益作為標準時，會偏向于選擇取值較多的特征；比如給定編號與活動是否舉辦，那么1個編號一定只對應1個是/否，編號必然是最優的特征；但是編號對于類別劃分沒有幫助，所以我們需要引入一個新的概念-信息增益率
$$\begin{gathered} 信息增益率g_R(D,X)定義為其信息增益g(D,X)與數據集D在特征X上值的熵H_X(D)之比 \\ {H}_X(D)=?\sum _{i=1}^k\frac{|D_i|}{|D|}log\frac{|D_i|}{|D|} \\ |D|:整個數據集樣本數,|D_i|:第i類的樣本數 \\ {g}_R(D,X)=\frac{g(D,X)}{H_X(D)} \end{gathered}$$

為什么信息增益率能降低偏向于選擇取值較多的特征的影響？

當樣本數量|D|增加后，|Di|/|D|降低，取對數再取負以后，H_X(D)就增大，信息增益率就降低

基尼系數

CART算法選用的評估標準

基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特征越好

在分類問題中，假設有k個類別，第i個類別概率為pi，則基尼系數為
$$Gini(p)=\sum _{i=1}^k{p}_i(1?p_i)=\sum _{i=1}^k{p}_i?\sum _{i=1}^k{p}_i^2=1?\sum _{i=1}^k{p}_i^2$$
對于數據集D，假設有k個類別，第i個類別的數量為C_i,則數據集D的基尼系數為
$$Gini(D)=\sum _{i=1}^k\frac{|C_i|}{|D|}(1?\frac{|C_i|}{|D|})=1?\sum _{i=1}^k(\frac{|C_i|}{|D|}{)}^2$$
基尼系數其實表示了一個數據集中分類錯誤的平均概率
$$\begin{gathered} 如果數據集根據X的取值分為D_1,D_2,\dots ,D_k \\ Gini(D,X)=\sum _{i=1}^k\frac{|C_i|}{|D|}Gini(D_i) \\ Gini(D,X)表示數據集D根據特征X劃分后的不確定性 \end{gathered}$$
觀察公式，其實可以發現面對編號特征時，基尼系數Gini(D,X)會是0

基尼增益

和信息增益類似
$$G(D,X)=Gini(D)?Gini(D,X)$$
采用越好的特征進行劃分，得到的基尼增益也越大

基尼仍會認為編號是一個比較優的特征(面對編號特征時，基尼系數Gini(D,X)會是0)

基尼增益率

$$\begin{gathered} 基尼增益率G_R(D,X)可以表示為G(D,X)與數據集D在特征X上的取值個數之比 \\ {G}_R(D,X)=\frac{G(D,X)}{|D_X|} \end{gathered}$$

處理連續值

$$比如有長度為n的連續數據a_1,a_2,\dots ,a_n$$

對其離散化的步驟:

• 排序

• 再任取相鄰點的中位點作為劃分點
  $$\begin{gathered} ?=\frac{a_i+a_{i+1}}{2},1\le i\le n?1 \\ 一共產生n?1個中位點 \end{gathered}$$

• 對這n-1個中位點劃分出的數據集進行計算熵，熵最小的就是最優劃分點

剪枝

對于決策樹而言，如果不斷向下劃分直至葉子節點的熵為0，理論上我們區分開了所有的類別。但是這樣很容易過擬合(劃分太多次相當于太多特征導致模型太復雜)，因此我們需要進行剪枝

剪枝策略：

• 預剪枝:邊構建決策樹邊剪枝
• 后剪枝:決策樹構建完之后再剪枝

正則化/預剪枝

預剪枝策略可以通過限制決策樹深度，葉子節點個數，葉子節點含樣本數以及信息增量完成

• 限制決策樹高度

  

  設定深度限度值d，當深度達到d時，就不再構建決策樹(節點不再繼續劃分數據)，把當前節點作為葉子節點

• 限制葉子節點個數

  

  當達到預設的葉子節點值n時，即使當前節點可以再繼續往下劃分，也不繼續劃分了，而是作為葉子節點

• 限制葉子節點樣本數

  

  限制葉子節點的樣本數不小于n，如果一個節點下所有分支的葉子節點包含的樣本數都小于n，那么需要對這個分支進行剪枝

• 限制最低信息增益

  

后剪枝

衡量標準
$$\begin{gathered} L_{\alpha }=\sum _{i=1}^n(Gini(T_i)\times |T_i|)+\alpha |T_{leaf}| \\ n是葉子節點數 \\ {L}_{\alpha }表示最終損失(越小越好) \\ Gini(T)表示當前節點的基尼系數 \\ |T|表示當前節點的樣本數 \\ {T}_{leaf}表示當前節點被劃分后產生的葉子節點個數 \\ \alpha 表示偏好系數，類似于正則化參數\lambda ，越大表示對劃分葉子節點懲罰越重 \end{gathered}$$