lightGBM與XGBoost的區(qū)別：(來(lái)源于：http://baijiahao.baidu.com/s?id=1588002707760744935&wfr=spider&for=pc)

切分算法(切分點(diǎn)的選取)

占用的內(nèi)存更低，只保存特征離散化后的值，而這個(gè)值一般用8位整型存儲(chǔ)就足夠了，內(nèi)存消耗可以降低為原來(lái)的1/8。

降低了計(jì)算的代價(jià)：預(yù)排序算法每遍歷一個(gè)特征值就需要計(jì)算一次分裂的增益，而直方圖算法只需要計(jì)算k次（k可以認(rèn)為是常數(shù)），時(shí)間復(fù)雜度從O(#data#feature)優(yōu)化到O(k#features)。(相當(dāng)于LightGBM犧牲了一部分切分的精確性來(lái)提高切分的效率，實(shí)際應(yīng)用中效果還不錯(cuò))

空間消耗大，需要保存數(shù)據(jù)的特征值以及特征排序的結(jié)果(比如排序后的索引，為了后續(xù)快速計(jì)算分割點(diǎn))，需要消耗兩倍于訓(xùn)練數(shù)據(jù)的內(nèi)存

時(shí)間上也有較大開銷，遍歷每個(gè)分割點(diǎn)時(shí)都需要進(jìn)行分裂增益的計(jì)算，消耗代價(jià)大

對(duì)cache優(yōu)化不友好，在預(yù)排序后，特征對(duì)梯度的訪問(wèn)是一種隨機(jī)訪問(wèn)，并且不同的特征訪問(wèn)的順序不一樣，無(wú)法對(duì)cache進(jìn)行優(yōu)化。同時(shí)，在每一層長(zhǎng)樹的時(shí)候，需要隨機(jī)訪問(wèn)一個(gè)行索引到葉子索引的數(shù)組，并且不同特征訪問(wèn)的順序也不一樣，也會(huì)造成較大的cache miss。

XGBoost使用的是pre-sorted算法（對(duì)所有特征都按照特征的數(shù)值進(jìn)行預(yù)排序，基本思想是對(duì)所有特征都按照特征的數(shù)值進(jìn)行預(yù)排序；然后在遍歷分割點(diǎn)的時(shí)候用O(#data)的代價(jià)找到一個(gè)特征上的最好分割點(diǎn)最后，找到一個(gè)特征的分割點(diǎn)后，將數(shù)據(jù)分裂成左右子節(jié)點(diǎn)。優(yōu)點(diǎn)是能夠更精確的找到數(shù)據(jù)分隔點(diǎn)；但這種做法有以下缺點(diǎn)

LightGBM使用的是histogram算法，基本思想是先把連續(xù)的浮點(diǎn)特征值離散化成k個(gè)整數(shù)，同時(shí)構(gòu)造一個(gè)寬度為k的直方圖。在遍歷數(shù)據(jù)的時(shí)候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)；優(yōu)點(diǎn)在于

決策樹生長(zhǎng)策略上：

XGBoost采用的是帶深度限制的level-wise生長(zhǎng)策略，Level-wise過(guò)一次數(shù)據(jù)可以能夠同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，不容易過(guò)擬合；但不加區(qū)分的對(duì)待同一層的葉子，帶來(lái)了很多沒必要的開銷（因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂）

LightGBM采用leaf-wise生長(zhǎng)策略，每次從當(dāng)前所有葉子中找到分裂增益最大（一般也是數(shù)據(jù)量最大）的一個(gè)葉子，然后分裂，如此循環(huán)；但會(huì)生長(zhǎng)出比較深的決策樹，產(chǎn)生過(guò)擬合（因此 LightGBM 在leaf-wise之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過(guò)擬合）。

histogram 做差加速。一個(gè)容易觀察到的現(xiàn)象：一個(gè)葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到。通常構(gòu)造直方圖，需要遍歷該葉子上的所有數(shù)據(jù)，但直方圖做差僅需遍歷直方圖的k個(gè)桶。利用這個(gè)方法，LightGBM可以在構(gòu)造一個(gè)葉子的直方圖后，可以用非常微小的代價(jià)得到它兄弟葉子的直方圖，在速度上可以提升一倍。

直接支持類別特征：LightGBM優(yōu)化了對(duì)類別特征的支持，可以直接輸入類別特征，不需要額外的0/1展開。并在決策樹算法上增加了類別特征的決策規(guī)則。

分布式訓(xùn)練方法上(并行優(yōu)化)

在特征并行算法中，通過(guò)在本地保存全部數(shù)據(jù)避免對(duì)數(shù)據(jù)切分結(jié)果的通信；

在數(shù)據(jù)并行中使用分散規(guī)約(Reduce scatter)把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器，降低通信和計(jì)算，并利用直方圖做差，進(jìn)一步減少了一半的通信量。基于投票的數(shù)據(jù)并行(Parallel Voting)則進(jìn)一步優(yōu)化數(shù)據(jù)并行中的通信代價(jià)，使通信代價(jià)變成常數(shù)級(jí)別。

特征并行的主要思想是在不同機(jī)器在不同的特征集合上分別尋找最優(yōu)的分割點(diǎn)，然后在機(jī)器間同步最優(yōu)的分割點(diǎn)。

數(shù)據(jù)并行則是讓不同的機(jī)器先在本地構(gòu)造直方圖，然后進(jìn)行全局的合并，最后在合并的直方圖上面尋找最優(yōu)分割點(diǎn)。

原始

LightGBM針對(duì)這兩種并行方法都做了優(yōu)化，

Cache命中率優(yōu)化

基于直方圖的稀疏特征優(yōu)化

DART(Dropout + GBDT)

GOSS(Gradient-based One-Side Sampling):一種新的Bagging(row subsample)方法,前若干輪(1.0f / gbdtconfig->learning_rate)不Bagging;之后Bagging時(shí), 采樣一定比例g(梯度)大的樣本

LightGBM優(yōu)點(diǎn)小結(jié)(相較于XGBoost)

速度更快

內(nèi)存消耗更低

?

?

分裂點(diǎn)尋找算法

• Basic Exact Greedy Algorithm

在每一次尋找中，枚舉所有可能的分裂點(diǎn)，然后利用score確定最佳分裂點(diǎn)。
代表的實(shí)現(xiàn)軟件有：sklearn， R的GBM， 單機(jī)版的XGBoost。
算法首先對(duì)特征進(jìn)行排序，然后依次訪問(wèn)數(shù)據(jù)，并以此數(shù)據(jù)該維特征的值作為分裂點(diǎn)，計(jì)算score。

• • 近似方法
    精確尋找不適用與分布式數(shù)據(jù)，近似方法通過(guò)特征的分布，按照百分比確定一組候選分裂點(diǎn)，通過(guò)遍歷所有的候選分裂點(diǎn)來(lái)找到最佳分裂點(diǎn)。
    兩種策略：全局策略和局部策略。在全局策略中，對(duì)每一個(gè)特征確定一個(gè)全局的候選分裂點(diǎn)集合，就不再改變；而在局部策略中，每一次分裂
    都要重選一次分裂點(diǎn)。前者需要較大的分裂集合，后者可以小一點(diǎn)。論文中對(duì)比了補(bǔ)充候選集策略與分裂點(diǎn)數(shù)目對(duì)模型的影響。
    全局策略需要更細(xì)的分裂點(diǎn)才能和局部策略差不多

總結(jié)

以上是生活随笔為你收集整理的xgboost gbdt特征点分烈点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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