在茫茫決策樹(shù)入門帖里，強(qiáng)推這篇！
介紹
數(shù)據(jù)樣本
決策樹(shù)的算法步驟
數(shù)學(xué)表示
由上圖可以得到每個(gè)葉子節(jié)點(diǎn)都落有樣本,該決策樹(shù)是一種由根至葉的算法, 其中每個(gè)葉子節(jié)點(diǎn)需要通過(guò)貪心算法進(jìn)行劃分最優(yōu)屬性,使得每一個(gè)的”純度“更高,其中純度的度量方式有一下幾種
信息增益 "ID3"
:原先信息熵
: 給定 ?后的信息熵
以上圖為例我們可以計(jì)算當(dāng)前的信息增益為:
假設(shè):一種有8個(gè)好瓜,9個(gè)壞瓜. 則原先信息熵:
計(jì)算在給定特征下信息熵增益最大的是紋理具體計(jì)算步驟如下:
一共17個(gè)樣本, 9個(gè)清晰紋理(2個(gè)壞瓜,7個(gè)好瓜),5個(gè)稍糊(1個(gè)好瓜,4個(gè)壞瓜),3個(gè)模糊(3個(gè)壞瓜)
紋理
信息增益比 "C4.5"
由上述可以得到: Gain(D,紋理) = 0.381, 一共17個(gè)樣本, 9個(gè)清晰紋理(2個(gè)壞瓜,7個(gè)好瓜),5個(gè)稍糊(1個(gè)好瓜,4個(gè)壞瓜),3個(gè)模糊(3個(gè)壞瓜)\hspace{4cm}
紋理
紋理紋理紋理
分類回歸樹(shù) "CART"(基尼系數(shù))
由上述可以得到: 一種有8個(gè)好瓜,9個(gè)壞瓜 \ \ \ \ ?
一共17個(gè)樣本, 9個(gè)清晰紋理(2個(gè)壞瓜,7個(gè)好瓜),5個(gè)稍糊(1個(gè)好瓜,4個(gè)壞瓜),3個(gè)模糊(3個(gè)壞瓜)
紋理清晰
稍糊模糊
稍糊
紋理清晰模糊
模糊
稍糊紋理清晰
Gini_{紋理}(D)_{max} = ?Gini(稍糊\&模糊)&Gini(紋理清晰) = 0.502-0.302=0.2
假設(shè)我們對(duì)所有的特征進(jìn)行嘗試尋找全局最優(yōu)解,時(shí)間的復(fù)雜度比較高為: 2^p
信息增益的表達(dá)式用泰勒一階展開(kāi)后和Gini指數(shù)的表達(dá)式相等
將在x=1處進(jìn)行一階泰勒展開(kāi) $f(x = f(x_0)+f'(x_0)(x-x_0) = f(1)+f'(1)(x-1)=1-x$
減緩決策樹(shù)過(guò)擬合的方法:
集成模型例如:隨機(jī)森林
設(shè)置樹(shù)的最大深度
當(dāng)葉節(jié)點(diǎn)里的樣本個(gè)數(shù)少于閾值的時(shí)候停止分裂
具體閾值選擇取決于交叉驗(yàn)證的結(jié)果
決策樹(shù)缺失值處理
刪除特征
高概率估計(jì)
對(duì)含有缺失值的樣本添加權(quán)重
決策樹(shù)的不同指標(biāo)
信息增益 :ID3
增益率: C4.5
基尼指數(shù): CART
決策樹(shù)的應(yīng)用
標(biāo)準(zhǔn)差(std)作為最后的目標(biāo)函數(shù)
使用交叉熵作為最后的目標(biāo)函數(shù)
分類樹(shù)
回歸樹(shù)
決策樹(shù)集成算法(dropout 也是一種集成算法)
Bagging算法特點(diǎn)
Boosting 算法特點(diǎn)
Random forest
Adaboost
每一輪的訓(xùn)練集不變，只是訓(xùn)練集中每個(gè)樣例在分類器中的權(quán)重發(fā)生變化。而權(quán)值是根據(jù)上一輪的分類結(jié)果進(jìn)行調(diào)整。
根據(jù)錯(cuò)誤率不斷調(diào)整樣例的權(quán)值，錯(cuò)誤率越大則權(quán)重越大
每個(gè)弱分類器都有相應(yīng)的權(quán)重，對(duì)于分類誤差小的分類器會(huì)有更大的權(quán)重。
各個(gè)預(yù)測(cè)函數(shù)只能順序生成，因?yàn)楹笠粋€(gè)模型參數(shù)需要前一輪模型的結(jié)果。
訓(xùn)練集是在原始集中有放回選取的，從原始集中選出的各輪訓(xùn)練集之間是獨(dú)立的。
使用均勻取樣，每個(gè)樣例的權(quán)重相等
所有預(yù)測(cè)函數(shù)的權(quán)重相等。
各個(gè)預(yù)測(cè)函數(shù)可以并行生成
簡(jiǎn)介
推導(dǎo):
加法模型
: 是每個(gè)基函數(shù)的系數(shù)
? : 是每個(gè)基函數(shù)的參數(shù)
? : 就是一個(gè)基函數(shù)了
前向分步算法
可見(jiàn)最終分類器是一個(gè)加法模型,所以每當(dāng)增加一個(gè)基分類器時(shí)候,都會(huì)使得分類結(jié)果逼近真實(shí)
結(jié)果. 也就是說(shuō)每次計(jì)算損失點(diǎn)時(shí)候只需要考慮當(dāng)前基分類器的系數(shù)和參數(shù), 不受之前分類器點(diǎn)影響
指數(shù)損失函數(shù)
步驟
根據(jù)前向分步算法求的最小值只需求α和G即可;由于當(dāng)G和y的取指只能是-1或者+1.所以對(duì)上式子進(jìn)行改寫
``` 所以對(duì)α進(jìn)行求導(dǎo), 得出 決策樹(shù)權(quán)重α的值, 錯(cuò)誤率e的值, 抽樣權(quán)重w樣本的值, 歸一化Z的值.
構(gòu)建最終的分類器
簡(jiǎn)介
計(jì)算過(guò)程
GBDT
GBDT（Gradient Boosting Decision Tree）是一種迭代的決策樹(shù)算法，該算法由多棵決策樹(shù)組成，從名字中我們可以看出來(lái)它是屬于 Boosting 策略。GBDT 是被公認(rèn)的泛化能力較強(qiáng)的算法。
推導(dǎo):
加法模型(與上同理)
前向分步算法(與上同理)
指數(shù)損失函數(shù)(可以自定義)
最后式子寫為(也就是模型沿著負(fù)度方向優(yōu)化)
- 計(jì)算步驟
XGboost
首先XGboost是Gradient Boosting的一種高效系統(tǒng)實(shí)現(xiàn)，并不是一種單一算法。XGboost里面的基學(xué)習(xí)器除了用tree(gbtree)，也可用線性分類器(gblinear)。而GBDT則特指梯度提升決策樹(shù)算法。
將樹(shù)模型的復(fù)雜度作為正則項(xiàng)加在優(yōu)化目標(biāo)
使用到了二階導(dǎo)數(shù)使得損失函數(shù)更具有擴(kuò)展性,并且加速收斂,類似牛頓法比SGD收斂更快。一階信息描述梯度變化方向，二階信息可以描述梯度變化方向是如何變化
允許使用column(feature) sampling來(lái)防止過(guò)擬合
使用一種分裂節(jié)點(diǎn)尋找的近似算法，用于加速和減小內(nèi)存消耗
節(jié)點(diǎn)分裂算法能自動(dòng)利用特征的稀疏性
data事先排好序并以block的形式存儲(chǔ)，利于并行計(jì)算
支持分布式計(jì)算可以運(yùn)行在MPI，YARN上，得益于底層支持容錯(cuò)的分布式通信框架rabit。
相比GBDT改進(jìn)了什么
特點(diǎn)
lightGBM
LightGBM使用基于直方圖的算法。例如，它將連續(xù)的特征值分桶(buckets)裝進(jìn)離散的箱子(bins)，這是的訓(xùn)練過(guò)程中變得更快
更低的內(nèi)存占用：使用離散的箱子(bins)保存并替換連續(xù)值導(dǎo)致更少的內(nèi)存
更高的準(zhǔn)確率(相比于其他任何提升算法) : 它通過(guò)leaf-wise分裂方法產(chǎn)生比level-wise分裂方法更復(fù)雜的樹(shù)，這就是實(shí)現(xiàn)更高準(zhǔn)確率的主要因素。然而，它有時(shí)候或?qū)е逻^(guò)擬合，但是我們可以通過(guò)設(shè)置 max-depth 參數(shù)來(lái)防止過(guò)擬合的發(fā)生
大數(shù)據(jù)處理能力
支持并行學(xué)習(xí)
相比XGboost改進(jìn)了什么
catboost
catboost 處理特征為分類的神器，你用ligtbgm或者XGboost在處理具有大量分類特征的時(shí)候，獨(dú)熱編碼不好用，因?yàn)槟阋粋€(gè)特征就有上千個(gè)分類，每個(gè)都獨(dú)熱，效果特別差，好的方法是每個(gè)分類用均值編碼，這種容易過(guò)擬合，catboost 設(shè)計(jì)了一種算法驗(yàn)證改進(jìn)，避免了過(guò)擬合。因此處理分類數(shù)據(jù)應(yīng)該比lightgbm 和XGboost 強(qiáng)很多，我觀察在處理分類數(shù)據(jù)中一般會(huì)有很大提升(未調(diào)參)。
特點(diǎn)
參考
Bagging和Boosting 概念及區(qū)別
一文弄懂AdaBoost、提升樹(shù)、殘差樹(shù)、GDBT
Adaboost, GBDT 與 XGBoost 的區(qū)別``
轉(zhuǎn)載https://mp.weixin.qq.com/s/uY4FNkjRnutfoYBMrEaFfg
歡迎學(xué)習(xí)更多相關(guān)知識(shí)：
