決策樹分割的差異-分類與迴歸

這裡主要是說明決策樹的分類與迴歸樹最大的不同點。並且用最簡單的例子來說明 gini index 與 minimize square error

gini index¶

假設資料集合 S 包含 n 個類別，Gini(S)的定義為 $P_j$ 為在 S中的值組屬於類別j的機率 $$Gini(S) = 1 - \sum_{j=1}^n P_j^2$$

利用屬性A分割資料集合 S 為 S1 與 S2 (二元分割)。則根據此一分割要件的吉尼係數$Gini_A(S)$為 $$Gini_A(S) = \frac{|S_1|}{|S|}Gini(S_1)+ \frac{|S_2|}{|S|}Gini(S_2)$$

不純度值的降低為:

$$\Delta Gini(A) =Gini(S) - Gini_A(S)$$

挑選擁有最大不純度的降低值、或吉尼係數$Gini_A(S)$最小的屬性作為分割屬性。

一個節點¶

用紅黑球10顆來舉例，如果紅和黑是9:1

$$Gini(S_{\{red,black\}})= 1 - \Big(\frac{9}{10}\Big)^2-\Big(\frac{1}{10}\Big)^2 = 0.18$$

如果紅和黑是4:6

$$Gini(S_{\{red,black\}})= 1 - \Big(\frac{4}{10}\Big)^2-\Big(\frac{6}{10}\Big)^2 = 0.48$$

可以發現，對於一個節點來說，Gini Index 代表了內部的不純度，也就是比例越是平均，Gini值越高

分割後的節點¶

現在將 4:6 的紅黑球(Gini = 0.48)分成兩組各5顆$S_1$與$S_2$

$S_1$紅黑的比例為3:2 $\qquad$ $S_2$紅黑的比例為1:4

$$\begin{aligned} Gini(S_{split}) &= \frac{5}{10}Gini(S_1)+ \frac{5}{10}Gini(S_2) \\ &= \frac{5}{10} \cdot 0.48 + \frac{5}{10} \cdot 0.32 \\ &= 0.4 \end{aligned}$$

然後計算 $\Delta Gini(Split)$的值 $$\Delta Gini(Split) = 0.48 - 0.4 = 0.08$$

　在決策樹上的運作方式¶

對於決策樹來說，Gini Index 是選擇分割屬性的方法，因此會比較兩種以上屬性的$\Delta Gini$，選擇降低最多的屬性

$\text{MAX}(\Delta Gini(A),\Delta Gini(B))$

minimize square error¶

定義 $x$ 和 $y$ $$\begin{aligned} x &= x_1,x_2,x_3,x_4,...x_i \\ y &= y_1,y_2,y_3,y_4,...y_i \end{aligned}$$ 首先利用特徵A分出兩個區域 $R_1$ 與 $R_2$，Loss function 為預測值和真實值的誤差 $$\begin{aligned} Los{s_{A}} &= \sum\limits_{x_i \in {R_1}} {(y_i - {c_1}} {)^2} + \sum\limits_{x_i \in {R_2}} {(y_i - {c_2}} {)^2} \end{aligned}$$

$Loss_{A}$中，$y$是$x$對應的真實值。我們的目標就是使得$Loss_{A}$最小化時的${c_1}$和${c_2}$，目標函式為：

$${\min_{c_1} \sum\limits_{x_i \in {R_1}} {{{(y_i - {c_1})}^2}} + \min_{c_2} \sum\limits_{x_i \in {R_2}} {{{(y_i - {c_2})}^2}} }$$

當式子為最小值時，$c_1$ 和 $c_2$ 分別為

$${c_1} =\frac{1}{N_1} \sum_{x_i \in R_1}^{} y_i$$ $${c_2} =\frac{1}{N_2} \sum_{x_i \in R_2}^{} y_i$$

用圖可以簡單理解，下面是 $R_1$ 和 $R_1$。以及個別代表的$c_1$ 和 $c_2$

此時的 loss function 回傳的是 3.36

接下來稍微修正一下特徵，使分割改變，loss function 回傳的值變為 7.38。

只要分割後的誤差越大，這個值就會升高，最後形成誤差最小的迴歸線

參考資料¶

最直覺的分類--決策樹 採礦貓

分类与回归树（classification and regression tree，CART）之回归 天泽28

In [ ]: