這裡主要是說明決策樹的分類與迴歸樹最大的不同點。並且用最簡單的例子來說明 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。
只要分割後的誤差越大，這個值就會升高，最後形成誤差最小的迴歸線
參考資料¶
沒有留言:
張貼留言