文章目錄

• CART 算法
• 1. CART 生成
• • 1.1 回歸樹生成
  • • 最小二乘回歸樹生成算法
  • 1.2 分類樹生成
  • • 基尼指數(shù)
    • CART 生成算法
• 參考文獻(xiàn)

相關(guān)文章：

機(jī)器學(xué)習(xí) | 目錄

監(jiān)督學(xué)習(xí) | ID3 決策樹原理及Python實(shí)現(xiàn)

監(jiān)督學(xué)習(xí) | ID3 & C4.5 決策樹原理

監(jiān)督學(xué)習(xí) | 決策樹之Sklearn實(shí)現(xiàn)

監(jiān)督學(xué)習(xí) | 決策樹之網(wǎng)絡(luò)搜索

本文大部分內(nèi)容搬運(yùn)自李航老師的《統(tǒng)計(jì)學(xué)習(xí)方法》^[1]，以給出決策樹算法較為完整的定義，關(guān)于決策樹算法的 Sklearn 實(shí)現(xiàn)，可以參考這篇文章。

CART 算法

分類與回歸樹（classification and regression tree, CART）模型由 Beriman 等人在 1984 年提出，是應(yīng)用廣泛的決策樹學(xué)習(xí)方法，CART 同樣由特征選擇、樹的生成及剪枝組成，既可以用于分類也可以用于回歸，以下將用于分類與回歸的樹統(tǒng)稱為決策樹。

CART 是在給定輸入隨機(jī)變量 X 條件下輸出隨機(jī)變量 Y 的條件概率分布的學(xué)習(xí)方法。CART 假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點(diǎn)特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征，將輸入空間即特征空間劃分為有限個單元，并在這些單元上確定預(yù)測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。

CART 算法由以下兩部組成：

（1）決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大；

（2）決策樹剪枝：用驗(yàn)證數(shù)據(jù)集對已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，這是用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。

1. CART 生成

決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。對回歸樹用平方誤差最小化準(zhǔn)則，對分類樹用基尼指數(shù)（Gini index）最小化準(zhǔn)則，進(jìn)行特征選擇，生成二叉樹。

1.1 回歸樹生成

假設(shè) $X$ 與 $Y$分別是輸入和輸出變量，并且 $Y$ 是連續(xù)變量，給定訓(xùn)練數(shù)據(jù)集：

$$D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$$

一個回歸樹對應(yīng)著輸入空間（即特征空間）的一個劃分以及在劃分的單元上的輸出值。假設(shè)已將輸入空間劃分為 $M$ 個單元 $R_1,R_2,...,R_M$ 并且在每個單元 $R_m$ 上有一個固定的輸出值 $C_m$，于是回歸樹模型可表示為：

$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)\text{\hspace{1em}(1)}$$

當(dāng)輸入空間的劃分確定時，可以用平方誤差 ${\sum }_{x_i\in R_m}(y_i?f(x_i){)}^2$ 來表示回歸樹對于訓(xùn)練數(shù)據(jù)的預(yù)測誤差，用平方誤差最小的準(zhǔn)則求解每個單元上的最優(yōu)輸出值。

因此，單元 $R_m$ 上的 $c_m$ 的最優(yōu)值 ${\hat{c}}_m$ 是 $R_m$ 上所有輸入實(shí)例 $x_i$ 對應(yīng)的輸出 $y_i$ 的均值，即：

$${\hat{c}}_m=ave(y_i|x_i\in R_m)\text{\hspace{1em}(2)}$$

這里采用啟發(fā)式的方法對輸入空間進(jìn)行劃分：選擇第 $j$ 個變量 $x^{(j)}$ 和它取的值 $s$，作為切分變量（splitting variable）和切分點(diǎn)（splitting point），并定義兩個區(qū)域：

$$R_1(j,s)=\{x|x^{(j)}\le s\}和R_2(j,s)=\{x|x^{(j)}>s\}\text{\hspace{1em}(3)}$$

然后尋找最優(yōu)切分變量 $j$ 和最優(yōu)切分點(diǎn) $s$：

$$\underset{j}{\min }[\underset{c_j}{\min }\sum _{x_i\in R_1(j,s)}(y_i?c_1{)}^2+\underset{c_j}{\min }\sum _{x_i\in R_2(j,s)}(y_i?c_2{)}^2]\text{\hspace{1em}(4)}$$

對固定輸入變量 $j$ 可以找到最優(yōu)切分點(diǎn) $s$。

因此有：

$${\hat{c}}_1=ave(y_i|x_i\in R_1(j,s))和{\hat{c}}_2=ave(y_i|x_i\in R_2(j,s))\text{\hspace{1em}(5)}$$

遍歷所有輸入變量，找到最優(yōu)的切分變量 $j$，構(gòu)造一個對 $(j,s)$。依次將輸入空間劃分為兩個區(qū)域。接著，最每個區(qū)域重復(fù)上述劃分過程，直到滿足停止條件為止，這樣就生成一顆回歸樹。這樣的回歸樹通常稱為最小二乘回歸樹（least squares regression tree）。

最小二乘回歸樹生成算法

輸入：訓(xùn)練數(shù)據(jù)集 $D$;

輸出：回歸樹 $f(x)$.

在訓(xùn)練數(shù)據(jù)集所在的輸入空間中，遞歸地將每個區(qū)域劃分為兩個子區(qū)域并決定每個子區(qū)域熵的輸出值，構(gòu)建二叉決策樹；

（1）選擇最優(yōu)切分變量 $j$ 和最優(yōu)切分點(diǎn) $s$，求解：

$$\underset{j}{\min }[\underset{c_j}{\min }\sum _{x_i\in R_1(j,s)}(y_i?c_1{)}^2+\underset{c_j}{\min }\sum _{x_i\in R_2(j,s)}(y_i?c_2{)}^2]\text{\hspace{1em}(6)}$$

\quad 遍歷變量 $j$，對固定的切分變量 $j$ 掃描切分點(diǎn) $s$，選擇使上式達(dá)到最小的對 $(j,s)$；

（2）用選定的對 $(j,s)$ 劃分區(qū)域并決定相應(yīng)的輸出值：

$$R_1(j,s)=\{x|x^{(j)}\le s\}{R}_2(j,s)=\{x|x^{(j)}>s\}\text{\hspace{1em}(7)}$$

$${\hat{c}}_m=\frac{1}{N_m}\sum _{x_i\in R_m(j,s)}{y}_i,x\in R_m,m=1,2\text{\hspace{1em}(8)}$$

（3）繼續(xù)對兩個子區(qū)域調(diào)用步驟 (1)，(2)，直至滿足停止條件；

（4）將輸入空間劃分為 $M$ 個單元 $R_1,R_2,...,R_M$ ，生成決策樹：

$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)\text{\hspace{1em}(9)}$$

1.2 分類樹生成

分類樹用基尼指數(shù)選擇最優(yōu)特征，同時決定該特征的最優(yōu)二值切分點(diǎn)。

基尼指數(shù)

分類問題中，假設(shè)有 $K$ 個類，樣本點(diǎn)屬于第 $k$ 類的概率為 $p_k$，則概率分布的基尼指數(shù)定義為：

$$Gini(p)=\sum _{k=1}^K{p}_k(1?p_k)=1?\sum _{k=1}^K{p}_k^2\text{\hspace{1em}(10)}$$

對于二類分類問題，若樣本點(diǎn)屬于第 1 個類的概率是 $p$，則概率分布的基尼指數(shù)為：

$$Gini(p)=2p(1?p)\text{\hspace{1em}(11)}$$

對于給定的樣本集合 $D$，其基尼指數(shù)為：

$$Gini(D)=1?\sum _{k=1}^K(\frac{|C_k|}{|D|}{)}^2\text{\hspace{1em}(12)}$$

這里，$C_k$ 是 $D$ 中屬于第 $k$ 類的樣本子集，$K$ 是類的個數(shù)。

如果樣本集合 $D$ 根據(jù)特征 $A$ 是否取某一可能值 $\alpha$ 被分割成 $D_1$ 和 $D_2$ 來那個部分，即：

$$D_1=\{(x,y)\in D|A(x)=a\},D_2=D?D_1\text{\hspace{1em}(13)}$$

則在特征 $A$ 的條件下，集合 $D$ 的基尼指數(shù)定義為：

$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)\text{\hspace{1em}(14)}$$

基尼指數(shù) $Gini(D)$ 表示集合 $D$ 的不確定性，基尼指數(shù)值越大，樣本集合的不確定性也就越大，這一點(diǎn)與熵相似。

CART 生成算法

輸入：訓(xùn)練數(shù)據(jù)集 $D$，停止計(jì)算的條件；

輸出：CART 分類決策樹。

根據(jù)訓(xùn)練數(shù)據(jù)集，從根結(jié)點(diǎn)開始，遞歸地對每個結(jié)點(diǎn)進(jìn)行以下操作，構(gòu)建二叉決策樹：

（1）設(shè)結(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為 $D$，計(jì)算現(xiàn)有特征對該數(shù)據(jù)集的基尼指數(shù)。此時，對每一個特征 $A$，對其可能取的每個值 $a$，根據(jù)樣本點(diǎn)對 $A=a$ 的測試為“是”或“否”將 $D$ 分割成 $D_1$ 和 $D_2$兩部分，利用式 (14) 計(jì)算 $A=a$ 時的基尼指數(shù)；

（2）在所有可能的特征 $A$ 以及它們所有可能的切分點(diǎn) $a$ 中，選擇基尼指數(shù)最小的特征及其對應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)。依最優(yōu)特征與最優(yōu)切分點(diǎn)，從現(xiàn)生成兩個子結(jié)點(diǎn)，將訓(xùn)練數(shù)據(jù)集依特征分配到兩個子結(jié)點(diǎn)中去；

（3）對兩個子結(jié)點(diǎn)遞歸地調(diào)用 (1) ，(2)，直到滿足停止條件；

（4）生成 CART 決策樹。

算法停止計(jì)算的條件是結(jié)點(diǎn)中的樣本個數(shù)小于預(yù)定閾值，或樣本集的基尼指數(shù)小于預(yù)定閾值（樣本基本屬于同一類），或者沒有更多特征。

參考文獻(xiàn)

[1] 李航. 統(tǒng)計(jì)學(xué)習(xí)方法[M]. 北京: 清華大學(xué)出版社, 2012: 55-66.

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的监督学习 | CART 分类回归树原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。