首先需要說(shuō)一下決策樹(shù)：
三個(gè)主要步驟：特征選擇——決策樹(shù)生成——決策樹(shù)修剪
ID3和C4.5分類(lèi)樹(shù)，CART樹(shù)即可分類(lèi)也可以回歸。
在進(jìn)行特征選擇時(shí)，各個(gè)算法采用的選擇分裂準(zhǔn)則不同:
ID3算法使用信息增益準(zhǔn)則，選擇信息增益最大(互信息、熵最小)的特征作為分裂屬性。
C4.5算法使用信息增益比準(zhǔn)則，選擇信息增益比最大的特征作為分裂屬性。
CART算法使用基尼指數(shù)準(zhǔn)則，選擇基尼指數(shù)最小的特征作為分裂屬性。
但當(dāng)CART算法用于回歸的時(shí)候，用平方誤差最小化準(zhǔn)則。故又稱(chēng)為最小二乘回歸樹(shù)生成算法。
信息熵：熵越大，隨機(jī)變量的不確定性就越大，分類(lèi)能力就越低.
剪枝主要為了防止過(guò)擬合：分為預(yù)剪枝和后剪枝
預(yù)剪枝：在構(gòu)建決策樹(shù)中，提前終止決策樹(shù)生長(zhǎng)。但這種方法不常用，因?yàn)槲覀儫o(wú)法判斷什么時(shí)候終止生長(zhǎng)。
后剪枝：在決策樹(shù)構(gòu)成后剪枝。包括：PEP悲觀錯(cuò)誤剪枝；MEP最小錯(cuò)誤剪枝；CCP:代價(jià)復(fù)雜度剪枝（CART樹(shù)度量每減少一個(gè)葉節(jié)點(diǎn)所得到的平均錯(cuò)誤）；EBP:基于錯(cuò)誤的剪枝。
決策樹(shù)的優(yōu)點(diǎn)：訓(xùn)練時(shí)間復(fù)雜度較低，預(yù)測(cè)的過(guò)程比較快速，模型容易展示（容易將得到的決策樹(shù)做成圖片展示出來(lái)）等。
在工業(yè)應(yīng)用中，決策樹(shù)比較多，在kangle比賽中，基于決策樹(shù)的XBOOST效果優(yōu)異。在于決策樹(shù)特征不用歸一化，速度快，非線性，適合已加工過(guò)的高維特征。
bagging與boost:
但是，決策樹(shù)也存在一些缺點(diǎn)，容易過(guò)擬合，雖然有剪枝的操作，但是還是不夠。由多個(gè)弱決策樹(shù)分類(lèi)器，加權(quán)或投票的得到一個(gè)強(qiáng)分類(lèi)器、
組合模型（bagging 與 boost）,這些算法最終的結(jié)果是生成N(可能會(huì)有幾百棵以上）棵樹(shù)，這樣可以大大的減少單決策樹(shù)帶來(lái)的毛病。
Bootstrap是一種有放回的抽樣方法思想。兩方面：bagging和boosting
雖然都是有放回的抽樣，但二者的區(qū)別在于：Bagging采用有放回的均勻取樣，而B(niǎo)oosting根據(jù)錯(cuò)誤率來(lái)取樣（Boosting初始化時(shí)對(duì)每一個(gè)訓(xùn)練例賦相等的權(quán)重1／n，然后用該學(xué)算法對(duì)訓(xùn)練集訓(xùn)練t輪，每次訓(xùn)練后，對(duì)訓(xùn)練失敗的訓(xùn)練例賦以較大的權(quán)重），因此Boosting的分類(lèi)精度要優(yōu)于Bagging。Bagging的訓(xùn)練集的選擇是隨機(jī)的，各輪訓(xùn)練集之間相互獨(dú)立，而B(niǎo)oostlng的各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)結(jié)果有關(guān)。
boost:最初為每個(gè)樣例賦予相同的權(quán)重，通過(guò)迭代的方式，對(duì)每一次分類(lèi)錯(cuò)誤的樣例給予更高的權(quán)重。進(jìn)行N次迭代，得到N個(gè)分類(lèi)器，再將它們組合起來(lái)（加權(quán)或投票），最終得到結(jié)果 .
隨機(jī)森林是在bagging基礎(chǔ)上，有放回的采樣，隨機(jī)選取K個(gè)特征，同時(shí)獨(dú)立的建立N個(gè)決策樹(shù)，最后由投票表決的方式?jīng)Q定最后的結(jié)果。并行
GBDT(Gradient Boost Decision Tree 梯度提升決策樹(shù))，GBDT的核心就在于：每一棵樹(shù)學(xué)的是之前所有樹(shù)結(jié)論和的殘差，迭代、串行。將決策樹(shù)結(jié)果累加的得到最后的結(jié)果。故可知，GBDT基于回歸樹(shù)（CART樹(shù)）。
xgboos也是以（CART）為基學(xué)習(xí)器的GB算法，但是擴(kuò)展和改進(jìn)了GDBT。相比GBDT的優(yōu)點(diǎn)有：
（1）xgboost在代價(jià)函數(shù)里自帶加入了正則項(xiàng)，用于控制模型的復(fù)雜度。
（2）特征抽樣采樣并行（xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能進(jìn)行下一次迭代的（第t次迭代的代價(jià)函數(shù)里包含了前面t-1次迭代的預(yù)測(cè)值）。xgboost的并行是在特征粒度上的。），xgboost在進(jìn)行節(jié)點(diǎn)的分裂時(shí)，支持各個(gè)特征多線程進(jìn)行增益計(jì)算，因此算法更快，準(zhǔn)確率也相對(duì)高一些。
（3）優(yōu)化時(shí)，GBDT梯度下降一階求導(dǎo)，xgboost是二階泰勒級(jí)數(shù)展開(kāi)。
（4）傳統(tǒng)GBDT以CART作為基分類(lèi)器，xgboost還支持線性分類(lèi)器，這個(gè)時(shí)候xgboost相當(dāng)于帶L1和L2正則化項(xiàng)的邏輯斯蒂回歸（分類(lèi)問(wèn)題）或者線性回歸（回歸問(wèn)題）。
XGBOOST參數(shù)：https://www.analyticsvidhya.com/blog/2016/03/complete-guide-parameter-tuning-xgboost-with-codes-python/
Adaboost(自適應(yīng)增強(qiáng))是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類(lèi)器(弱分類(lèi)器)，然后把這些弱分類(lèi)器集合起來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類(lèi)器(強(qiáng)分類(lèi)器)。在訓(xùn)練集的不同子集上，多次調(diào)用弱學(xué)習(xí)算法，最終按加權(quán)方式聯(lián)合多次弱學(xué)習(xí)算法的預(yù)測(cè)結(jié)果就可得到最終學(xué)習(xí)結(jié)果。
與Boosting算法不同的是，adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類(lèi)器的誤差，并且最后得到的強(qiáng)分類(lèi)器的分類(lèi)精度依賴(lài)于所有弱分類(lèi)器的分類(lèi)精度，
Adaboost(Adaptive Boosting)算法，對(duì)于boosting算法，存在兩個(gè)問(wèn)題：
1. 如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類(lèi)器得以進(jìn)行；
2. 如何將訓(xùn)練得到的各個(gè)弱分類(lèi)器聯(lián)合起來(lái)形成強(qiáng)分類(lèi)器。
針對(duì)以上兩個(gè)問(wèn)題，adaboost算法進(jìn)行了調(diào)整：
1. 使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機(jī)選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點(diǎn)集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上；
2. 將弱分類(lèi)器聯(lián)合起來(lái)，使用加權(quán)的投票機(jī)制代替平均投票機(jī)制。讓分類(lèi)效果好的弱分類(lèi)器具有較大的權(quán)重，而分類(lèi)效果差的分類(lèi)器具有較小的權(quán)重。
RandomForest 與 GBDT 的區(qū)別：
相同點(diǎn)：
1.都由很多棵樹(shù)組成
2.最終的結(jié)果是由多棵樹(shù)一起決定的
不同點(diǎn)：
1.RandomForest中的樹(shù)可以是分類(lèi)樹(shù)，也可以是回歸樹(shù)，而GBDT只能由回歸樹(shù)（CART）組成，這也說(shuō)明GBDT各個(gè)樹(shù)相加是有意義的
2.RandomForest中的樹(shù)是并行生成的，而GBDT是串行生成的，GBDT中下一顆樹(shù)要去擬合前一顆樹(shù)的殘差，所以GBDT中的樹(shù)是有相關(guān)關(guān)系的，而RandomForest中的樹(shù)的相關(guān)性依賴(lài)于Boostrap生成的樣本子集的相關(guān)性
3.RandomForest 對(duì)異常值不敏感，GBDT敏感
4.RandomForest是通過(guò)降低模型方差來(lái)提高性能的，而GBDT是通過(guò)降低偏差來(lái)提高性能
GBDT 與 XGBOOST的比較：
1.傳統(tǒng)的GBDT以CART樹(shù)作為基分類(lèi)器，而XGBOOST還支持線性分類(lèi)器，此時(shí)的線性分類(lèi)器自帶正則項(xiàng)
2.傳統(tǒng)的GBDT在優(yōu)化時(shí)，只用到了loss function的一階導(dǎo)信息，而XGBOOST對(duì)loss function做了Taylor展開(kāi)，用到了二階導(dǎo)信息
3.XGBOOST在loss function中引入了正則項(xiàng)，防止過(guò)擬合，正則項(xiàng)里包含葉節(jié)點(diǎn)數(shù)以及每個(gè)葉節(jié)點(diǎn)上的score的L2的平方和
在計(jì)算劃分增益時(shí)，如果gain < gamma, 不劃分，gain> gamma，劃分，這相當(dāng)于決策樹(shù)的預(yù)剪枝。 gamma是葉節(jié)點(diǎn)個(gè)數(shù)的參數(shù)
4.XGBOOST還借用了RandomForest中的列抽樣思想，也支持在劃分節(jié)點(diǎn)時(shí)，只考慮部分屬性
（現(xiàn)狀sklearn中的GBDT也實(shí)現(xiàn)了列抽樣）
5.XGBOOST可以自動(dòng)學(xué)習(xí)出缺失值的分裂方向，論文中的default direction
（具體做法時(shí)，遍歷的嘗試將所有的缺失值分裂到所有方向{left or right}，split and default directions with max gain）
6.XGBOOST實(shí)現(xiàn)了并行化，這個(gè)并行化是特征粒度上的并行化：劃分節(jié)點(diǎn)時(shí)，每個(gè)特征并行計(jì)算，同時(shí)每個(gè)特征的劃分節(jié)點(diǎn)也是并行計(jì)算（這是加速最猛的處理）
7.XGBOOST提出了block的概念，簡(jiǎn)單的說(shuō)將排序后的特征值放在block中，以后劃分特征的時(shí)候，只需要遍歷一次即可，因?yàn)闆Q策樹(shù)在處理屬性值時(shí)，需要將屬性值先排序，這是最耗時(shí)的步驟，而block預(yù)先存儲(chǔ)了排序的特征值，在后續(xù)過(guò)程中可以重復(fù)利用這個(gè)結(jié)構(gòu)中的數(shù)據(jù)，同時(shí)，計(jì)算每個(gè)特征的劃分增益可以并行處理了
Collecting statistics for each column can be parallelized,giving us a?parallel algorithm for split finding!!
8.貪心算法在選擇最佳劃分方式時(shí)需要遍歷所有的劃分點(diǎn)子集，在數(shù)據(jù)非常大時(shí)，這會(huì)非常低效，xgboost提出了近似直方圖計(jì)算，根據(jù)數(shù)據(jù)的二階導(dǎo)信息進(jìn)行排序，提出一些候選劃分點(diǎn)子集
