Decision Tree

基本思想在于每次分裂節(jié)點時選取一個特征使得劃分后得到的數(shù)據(jù)集盡可能純蜓陌。

劃分標準

信息增益(Information Gain)

信息增益 = 未劃分數(shù)據(jù)集的信息熵 - 劃分后子數(shù)據(jù)集的信息熵的數(shù)學期望值觅彰。
事件 $x_i$ 的信息量 $=-logP(x_i)$ ，信息熵就是信息量的期望值钮热，記作 $H(x)$ 填抬，即 $H(x)=-\sum_{i=1}^{n}P(x_i)logP(x_i)$ 。
假設未劃分數(shù)據(jù)集中共有 $C$ 類霉旗，劃分為了 $K$ 份痴奏，則 $\begin{aligned} Gain&=H-\overline{H_{splited}} \\ &=(-\sum_{i=1}^{C}P(i)logP(i))-\sum_{i=1}^K P(D_i)H(D_i))\\ &=(-\sum_{i=1}^{C}P(i)logP(i))-\sum_{i=1}^K \frac{len(D_i)}{len(D)} H(D_i)) \end{aligned}$

增益比率(Gain Ratio)

按照信息增益來選擇特征時總是會傾向于選擇分支多的特征屬性，這樣子能夠使得劃分后每個子集的信息熵最小厌秒。比如读拆，給每一個數(shù)據(jù)添加一個獨一無二的id值特征，則按照id值進行分類是獲得信息增益最大的鸵闪。這樣子檐晕，每個子集的信息熵為0，但是這樣的分類毫無任何意義蚌讼，無任何泛化能力辟灰。為了克服信息增益的弱泛化能力的缺陷，引入了分裂信息篡石，即
$SplitInfo=-\sum_{i=1}^K \frac{len(D_i)}{len(D)} P(\frac{len(D_i)}{len(D)})$
可以看出來芥喇，數(shù)據(jù)分得越多，分裂信息也就越大凰萨。那么继控，
$GainRatio=\frac{Gain}{SplitInfo}$
為防止 $SplitInfo$ 趨于0，有時需要在分母上添加一個平滑函數(shù)胖眷。分母由 $SplitInfo$ 變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=SplitInfo%2B%5Coverline%7BSplitInfo%7D" alt="SplitInfo+\overline{SplitInfo}" mathimg="1">武通，即加上了所有可能的分裂信息的均值。

基尼系數(shù)(Gini Index)

直觀的說珊搀，基尼系數(shù)表示的是隨機從節(jié)點中抽取兩個樣本冶忱，其對應的類別不一樣的概率。
$I_G(D)=1-\sum_{i=1}^{C}P(i)^2$
$I_G^{Splited}(D)=\sum_{j=1}^{K}P(D_j)I_G(D_j)$
$\Delta I_G^{Splited}(D)=I_G(D)-I_G^{Splited}(D)$

常用的決策樹類型

ID3
使用信息增益作為屬性選擇標準境析。
需離散屬性囚枪。如果是連續(xù)屬性派诬，將數(shù)據(jù)集 $D$ 中元素按照此屬性進行排序，則每2個相鄰元素的中間點可以看成是潛在分裂點眶拉。從第一個潛在分裂點開始千埃，分裂 $D$ 并計算2個集合的期望信息，具有最小期望信息的點稱為這個屬性的最佳分裂點忆植，其信息期望作為此屬性的信息期望放可。ID3缺點在于其傾向于選擇分支數(shù)量較多的特征變量，可能導致訓練得到一個龐大且深度淺的樹朝刊；另外耀里，輸入變量必須是分類變量，連續(xù)變量需要離散化拾氓。
C4.5
使用增益比率作為屬性選擇標準冯挎。
CART
分類：最小化基尼系數(shù)的均值，眾數(shù)作為最終結果咙鞍；
回歸：最小化平方差誤差的均值房官，取均值作為最終結果。
只能形成二叉樹续滋。

分裂相關性質(zhì)

樹分裂的終止條件

遍歷完所有屬性翰守、新劃分的數(shù)據(jù)集中只有一個類別。

分裂屬性

屬性是離散值且不要求生成二叉決策樹疲酌，此時用屬性的每一個劃分作為一個分支蜡峰；
屬性是離散值且要求生成二叉決策樹，此時使用屬性劃分的一個子集進行測試朗恳，按是否屬于這兩個子集分成了2個分支湿颅；
屬性是連續(xù)值，此時確定一個值作為分裂點粥诫，按照值是否大于這個分裂點生成兩個分支油航。

優(yōu)缺點

優(yōu)點：
- 分類規(guī)則清晰，結果容易理解怀浆。
- 計算量相對較小劝堪，實現(xiàn)速度快。
- 非線性揉稚，非參數(shù)方法，誰跑效果都相對一樣熬粗。
- 不需要預選變量搀玖，可處理異常值、缺失值（使用替代分支）驻呐、不同量綱值等數(shù)據(jù)類型灌诅。
- 同時可以處理分類變量和數(shù)值變量芳来。但是可能決策樹對于連續(xù)變量的劃分并不合理，可以提前離散化猜拾。
- 相對于Logistic Regression即舌，可以處理多輸出的問題。
- 另外挎袜，決策樹不需要做變量篩選顽聂，會自動篩選《⒁牵可以做特征選擇紊搪、特征組合。
缺點：
- 最大的缺點就是很容易過擬合全景，導致實際預測的效果并不高耀石。
- 泛化能力太差，對于沒有出現(xiàn)過的值幾乎沒有辦法爸黄。
- 若數(shù)據(jù)集類別不平衡滞伟，生成的樹會存在偏見。
- 不是很穩(wěn)定炕贵，數(shù)據(jù)變一點梆奈，樹就會發(fā)生變化。對異常值過于敏感鲁驶，很容易導致樹的結構發(fā)生巨大的變化鉴裹。
- 不適合處理高維稀疏數(shù)據(jù)，不適合處理特征關聯(lián)性較強的數(shù)據(jù)钥弯。

Random Forest

random forest是decision tree的bagging径荔，并且在bagging的基礎上更進一步。其核心思想就是雙隨機過程脆霎，隨機有放回樣本采樣（行采樣）和隨機無放回特征采樣（列采樣）总处。列采樣又分為全局列采樣，即采后建樹睛蛛；局部列采樣鹦马，每次節(jié)點分裂時采樣。

基本流程

樣本的隨機
從樣本集中使用bootstrap隨機選擇 $N$ 個樣本忆肾。常 $N=\sqrt{N_{樣本數(shù)}}$ 荸频。
特征的隨機
從所有屬性中隨機選擇 $K$ 個屬性，選擇最佳分割方式作為節(jié)點建立decision tree客冈。常 $K=\sqrt{N_{屬性數(shù)}}$ 旭从。
重復上述過程 $m$ 次，建立了 $m$ 棵樹。
$m$ 棵樹投票表決和悦，分類概率總和退疫，可以平衡不平衡數(shù)據(jù)集的誤差，回歸平均值鸽素。

優(yōu)缺點

優(yōu)點
- 在當前的很多數(shù)據(jù)集上褒繁，相對其他算法有著很大的優(yōu)勢，表現(xiàn)良好馍忽。
- 能夠處理很高維度的數(shù)據(jù)棒坏，并且不用做特征選擇。
- 在訓練完后舵匾，它能夠給出哪些特征比較重要俊抵。
- 在創(chuàng)建隨機森林的時候，對泛化誤差使用的是無偏估計坐梯，模型泛化能力強徽诲，一定程度上能夠避免過擬合。
- 訓練速度快吵血，容易做成并行化方法谎替。
- 在訓練過程中，能夠檢測到特征間的相互影響蹋辅。
- 實現(xiàn)比較簡單钱贯。
- 對于不平衡的數(shù)據(jù)集來說，它可以平衡誤差侦另。
- 如果有很大一部分的特征遺失秩命，仍可以維持準確度。
缺點:
- 已經(jīng)證明了在某些噪音較大的分類或回歸問題上會過擬合褒傅。
- 對于有不同取值的屬性的數(shù)據(jù)弃锐，取值劃分較多的屬性會對隨機森林產(chǎn)生更大的影響，所以隨機森林在這種數(shù)據(jù)上產(chǎn)出的屬性權值是不可信的殿托。

Random Forest用于特征選擇

特征選擇的目標有兩個霹菊，一是找到與因變量高度相關的特征變量；二是選出數(shù)目較少的特征變量并且能夠充分預測因變量的結果支竹。

特征重要性

基尼系數(shù)
特征重要性=
其中旋廷，特征出現(xiàn)的節(jié)點的集合記作，特征出現(xiàn)的節(jié)點的集合記作礼搁，random forest中樹的棵數(shù)記作饶碘，將屬性集合記作。
- 存在的問題：
  對于存在關聯(lián)的多個特征馒吴，其中任意一個都可以作為指示器或者說是優(yōu)秀特征扎运，并且一旦其中的某個特征被選中之后卑雁，其他特征的重要度就會急劇下降，因為不純度已經(jīng)被選中的那個特征降下來了绪囱，其他的特征就很難再降低那么多的不純度了。這樣一來莹捡，只有先被選中的那個特征重要度很高鬼吵，其他關聯(lián)特征的重要度往往較低。在理解數(shù)據(jù)時篮赢，就會造成誤解齿椅，導致錯誤地認為先被選中的特征是很重要的，而其余的特征是不重要的启泣，但實際上這些特征對響應變量的作用是十分接近的涣脚。
  特征隨機選擇方法稍微緩解了這個問題，但是總的來說并沒有完全解決寥茫。
OOB error
將OOB數(shù)據(jù)代入訓練好的RF中去計算結果遣蚀，對比實際類別得ERROR1；對每個特征隨機添加一定的噪聲或者將當前特征隨機打散纱耻，再次代入RF去計算得ERROR2芭梯；計算ERROR1與ERROR2之間的差值，差值越大弄喘，說明對應的特征越重要玖喘。

常用的步驟

初步估計與排序

對隨機森林中的特征變量按照特征重要性降序排序。
確定刪除比例蘑志，從當前特征變量中剔除相應比例的不重要的特征累奈，從而得到一個新的特征集。
用新的特征集建立新的隨機森林急但，并計算特征集中每個特征的重要性澎媒，降序排序。
重復上述過程至剩下 $m$ 個特征羊始。

根據(jù)1中得到的每個特征集及基于其建立的RF旱幼，計算OOB error，選擇OOB error最小的特征集作為最后選定的特征集突委。

Adaptive Boosting(AdaBoost)

"boosting"意為通過將一些表現(xiàn)一般柏卤，可能僅僅略好于隨機猜測的模型通過特定方法進行組合后來獲得一個表現(xiàn)較好的模型。
"adaptive"意為在訓練過程中匀油，每個新的模型都會基于前一個模型的表現(xiàn)結果進行調(diào)整缘缚。
$y\in \{-1,+1\}$
$g_t \leftarrow \arg\min_{h\in H}(\sum_{n=1}^{N}u_n^t[y_n \neq h(x_n)])$
$g_{t+1} \leftarrow \arg\min_{h\in H}(\sum_{n=1}^{N}u_n^{t+1}[y_n \neq h(x_n)])$
如果 $g_t$ 在 $u^{t+1}$ 下表現(xiàn)得不好，那么返回的 $g_{t+1}$ 就不會是 $g_t$ 敌蚜，便可以認為 $g_{t+1}$ 和 $g_t$ 不同桥滨。
因此，構建 $u^{t+1}$ 使得在 $u^{t+1}$ 下 $g_t$ 的表現(xiàn)近似于隨機猜，即
$\frac{\sum_{n=1}^N u_n^{t+1}[y_n\neq g_t(x_n)]}{\sum_{n=1}^N u_n^{t+1}}=\frac{1}{2}$
即 $\sum_{n=1}^N u_n^{t+1}[y_n=g_t(x_n)]=\sum_{n=1}^N u_n^{t+1}[y_n\neq g_t(x_n)]$ 齐媒。
因此蒲每，分正確的 $u_n^{t+1}=u_n^t*g_t在u_n^t下的分類錯誤率$ ，分錯誤的 $u_n^{t+1}=u_n^t*g_t在u_n^t下的分類正確率$ 喻括。
記 $g_t$ 在 $u_n^t$ 下的分類錯誤率為 $\epsilon$ 邀杏，即 $\epsilon=\frac{\sum_{n=1}^N u_n^{t}[y_n\neq g_t(x_n)]}{\sum_{n=1}^N u_n^{t}}$
定義縮放因子 $\diamondsuit_t$ ，即 $\diamondsuit_t=\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}$
那么唬血，
$incorrect\leftarrow incorrect*\diamondsuit_t, correct\leftarrow correct/\diamondsuit_t$
可解釋為放大錯誤點望蜡，縮小正確點。
因此拷恨，AdaBoost算法流程總結如下：

初始化：
$u^1=[\frac{1}{N},\frac{1}{N},\cdots,\frac{1}{N}]^T$
for t = 1,2,...,T
1. 獲得 $g_t$ ：
  $g_t \leftarrow \arg \min_{h\in H}(\sum_{n=1}^{N}u_n^t[y_n \neq h(x_n)])$
2. 更新 $u^t$ 得 $u^{t+1}$ ：
  $\epsilon=\frac{\sum_{n=1}^N u_n^{t}[y_n\neq g_t(x_n)]}{\sum_{n=1}^N u_n^{t}}$
  $\diamondsuit_t=\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}$
  對于 $u_n^{t+1}$ ,有
  $if\ y_n=g_t(x_n),\ u_n^{t+1}=u_n^{t}/\diamondsuit_t$
  $if\ y_n\neq g_t(x_n),\ u_n^{t+1}=u_n^{t}*\diamondsuit_t$
3. 計算 $\alpha_t$
  $\alpha_t=\ln \diamondsuit_t$
  $G_t=\sum_{\tau=1}^t\alpha_{\tau} g_{\tau}$
return $h=sign(G_T)$

Gradient Boosted Decision Tree(GBDT)

AdaBoost代價函數(shù)分析

$\begin{aligned} u_n^{t+1}&=u_n^{t}\cdot\diamondsuit_t^{-y_n g_t(x_n)}\\ &=u_n^{t}\cdot\exp(-\alpha_ty_ng_t(x_n)) \end{aligned}$
$\begin{aligned} u_n^{T+1}&=u_n^1\prod_{t=1}^{T}\exp(-\alpha_t y_n g_t (x_n))\\ &=\frac{1}{N}\exp(-y_n\sum_{t=1}^{T}\alpha_t g_t (x_n)) \end{aligned}$
$linear\ score\ s=\sum_{t=1}^{T}\alpha_t g_t(x), \ G(x)=sign(s)$
$\begin{aligned} \sum_{n=1}^N u_n^{T+1}&=\sum_{n=1}^N \frac{1}{N}\exp(-y_n\sum_{t=1}^{T}\alpha_t g_t (x_n)) \\ &=\sum_{n=1}^N \frac{1}{N}\exp(-y_n s_n) \end{aligned}$
可以看出來脖律，AdaBoost采用的是指數(shù)損失函數(shù)。每一次迭代更新模型的過程可以看成是求使得
$\min_{\eta}\ \min_{h}\frac{1}{N}\sum_{n=1}^N \exp(-y_n\sum_{\tau=1}^{t-1}\alpha_{\tau} g_{\tau} (x_n)+\eta h(x_n))$
最小的 $h$ 和 $\eta$ 腕侄，進行推導后可以發(fā)現(xiàn) $h$ 為AdaBoost中的 $g_t$ 小泉， $\eta$ 為對應的 $\alpha_t$ 。

Gradient Boosting

Gradient Boosting與base model為決策樹的結合即為GBDT模型兜挨。由于決策樹是非線性的膏孟，并且隨著深度的加深，非線性越來越強拌汇，基于決策樹的GBDT也是非線性的柒桑。
AdaBoost是Gradient Boosting的一個特例，或者說Gradient Boosting是對AdaBoost進行了推廣噪舀。
Gradient Boosting抽象地說魁淳，模型的訓練過程是對于任意可導目標函數(shù)的優(yōu)化過程。通過反復地選擇一個指向負梯度方向的函數(shù)与倡。該算法可以被看做是在函數(shù)空間里對目標函數(shù)進行了優(yōu)化界逛。Gradient Boosting在每一次模型迭代中求解使得 $\min_{\eta}\ \min_{h}\frac{1}{N}\sum_{n=1}^N err(\sum_{\tau=1}^{t-1}\alpha_{\tau} g_{\tau} (x_n)+\eta h(x_n), y_n)$ 最小的 $h$ 和 $\eta$ 作為對應的 $g_t$ 和 $\alpha_t$ 。
和AdaBoost一樣纺座，Gradient Boosting也是重復選擇一個表現(xiàn)一般的模型息拜，并且每次都基于先前模型的表現(xiàn)進行調(diào)整。不同的是净响，AdaBoost是通過提升錯分數(shù)據(jù)點的權重來定位模型的不足而Gradient Boosting是通過計算梯度來定位模型的不足少欺。因此，相比AdaBoost馋贤，Gradient Boosting可以使用更多種類的目標函數(shù)赞别。
因此，Gradient Boosting算法流程總結如下：

初始化：
$s_1=s_2=\cdots=s_N=0$
for t = 1,2,...,T
1. $g_t \leftarrow A\{(x_n,y_n-s_n)\}$ 配乓，如果模型 $A$ 使用的是二次代價回歸函數(shù)的話仿滔；
2. 使用基于 $\{(g_t(x_n),y_n-s_n)\}$ 的單一變量線性回歸計算出 $\alpha_t$ 值惠毁；
3. 更新 $s_n\leftarrow s_n+\alpha_t g_t(x_n)$
return $G(x)=\sum_{t=1}^T\alpha_t g_t(x)$

Gradient Boosting for Regression

有一組數(shù)據(jù) $(x_1,y_1),\cdots,(x_N,y_N)$ 和一個基礎模型 $F$ ，想最小化 $F(x_i)$ 和真實值 $y_i$ 之間的二次代價函數(shù)崎页。 $\forall i \in [1,N]$ 鞠绰，稱 $h_i=y_i-F(x_i)$ 為關于 $x_i$ 的殘差，可以訓練一個回歸樹 $h$ 來擬合 $\{(x_i,y_i-F(x_i))\}$ 飒焦，這樣就得到了一個更好的模型 $F+h$ 洞豁，重復這一個過程，最終得到了一個讓人滿意的模型荒给。
這里使用回歸樹去擬合殘差，其實就是用回歸樹去擬合負梯度刁卜。當loss不為square loss時志电，殘差不一定等于負梯度！我們實際上是在通過梯度下降法對模型參數(shù)進行更新蛔趴，這樣理解的好處在于我們可以將這個算法推廣到其他的損失函數(shù)上去挑辆。回歸不一定適用平方代價孝情，平方代價的優(yōu)點在于便于理解和實現(xiàn)鱼蝉，缺點在于對于異常值的魯棒性較差。有時候會選擇其他的代價函數(shù)箫荡，如absolute loss魁亦，即 $y-F$ 或者huber loss，即
$if\ |y-F|\leq \delta,\ 則\frac{1}{2}(y-F)^2;\ if\ |y-F|> \delta,\ 則\delta(|y-F|-\frac{\delta}{2})羔挡。$
梯度下降法的思想使得我們可以非常輕易地改用不同的損失函數(shù)設計Gradient Boosting算法洁奈。另外在使用某些其他損失函數(shù)時，殘差比起負梯度更容易受到異常值的影響绞灼。

Random Forest vs GBDT

相同

隨機森林和GBDT都屬于集成算法利术，base model都是決策樹。

不同

隨機森林

隨機森林是決策樹的bagging低矮。
bagging通過重復對原訓練數(shù)據(jù)集上進行有放回地采樣生成的數(shù)據(jù)集用base model進行訓練多次印叁，然后，對于分類求眾數(shù)军掂，對于回歸求平均作為最終結果轮蜕。
可并行。
隨機森林希望單個決策樹偏差小良姆、方差大肠虽，這樣通過 $N$ 個決策樹的疊加可以減少方差，達到較好的結果玛追。 $N$ 越大税课，泛化能力越好闲延。
隨機森林里的樹可以是分類樹也可以是回歸樹。

GBDT

GBDT是決策樹的boosting韩玩。
boosting通過在原訓練數(shù)據(jù)集變化的版本上進行base model的訓練垒玲，當前base model的訓練是基于上一個base model的表現(xiàn)的，然后線性組合起這些base model找颓。
是串行合愈。
GBDT希望單個決策樹能力只要好于隨機即可，這樣通過boosting后就可以降低偏差击狮，達到較好的表現(xiàn)佛析。
樹越多，GBDT越可能過擬合彪蓬。
GBDT的核心在于累加所有樹的結果作為最終結果寸莫，而分類樹的結果顯然是沒辦法累加的，所以GBDT中的樹都是回歸樹档冬，不是分類樹膘茎。

Decision Tree兽泄、Random Forest漓概、AdaBoost、GBDT

Decision Tree病梢、Random Forest胃珍、AdaBoost、GBDT

Decision Tree

劃分標準

信息增益(Information Gain)

增益比率(Gain Ratio)

基尼系數(shù)(Gini Index)

常用的決策樹類型

分裂相關性質(zhì)

樹分裂的終止條件

分裂屬性

優(yōu)缺點

Random Forest

基本流程

優(yōu)缺點

Random Forest用于特征選擇

特征重要性

常用的步驟

Adaptive Boosting(AdaBoost)

Gradient Boosted Decision Tree(GBDT)

AdaBoost代價函數(shù)分析

Gradient Boosting

Gradient Boosting for Regression

Random Forest vs GBDT

相同

不同

隨機森林

GBDT