首先需要說一下決策樹：
三個主要步驟：特征選擇——決策樹生成——決策樹修剪
ID3和C4.5分類樹镇眷，CART樹即可分類也可以回歸咬最。
在進(jìn)行特征選擇時(shí)翎嫡，各個算法采用的選擇分裂準(zhǔn)則不同:
ID3算法使用信息增益準(zhǔn)則，選擇信息增益最大(互信息永乌、熵最小)的特征作為分裂屬性惑申。
C4.5算法使用信息增益比準(zhǔn)則，選擇信息增益比最大的特征作為分裂屬性翅雏。
CART算法使用基尼指數(shù)準(zhǔn)則圈驼，選擇基尼指數(shù)最小的特征作為分裂屬性。
但當(dāng)CART算法用于回歸的時(shí)候望几，用平方誤差最小化準(zhǔn)則绩脆。故又稱為最小二乘回歸樹生成算法。
信息熵：熵越大橄抹，隨機(jī)變量的不確定性就越大靴迫，分類能力就越低.
剪枝主要為了防止過擬合：分為預(yù)剪枝和后剪枝
預(yù)剪枝：在構(gòu)建決策樹中，提前終止決策樹生長楼誓。但這種方法不常用玉锌，因?yàn)槲覀儫o法判斷什么時(shí)候終止生長。
后剪枝：在決策樹構(gòu)成后剪枝疟羹。包括：PEP悲觀錯誤剪枝主守；MEP最小錯誤剪枝；CCP:代價(jià)復(fù)雜度剪枝（CART樹度量每減少一個葉節(jié)點(diǎn)所得到的平均錯誤）榄融；EBP:基于錯誤的剪枝参淫。
決策樹的優(yōu)點(diǎn)：訓(xùn)練時(shí)間復(fù)雜度較低，預(yù)測的過程比較快速愧杯，模型容易展示（容易將得到的決策樹做成圖片展示出來）等涎才。
在工業(yè)應(yīng)用中，決策樹比較多民效，在kangle比賽中憔维，基于決策樹的XBOOST效果優(yōu)異涛救。在于決策樹特征不用歸一化，速度快业扒，非線性检吆，適合已加工過的高維特征。
bagging與boost:
但是程储，決策樹也存在一些缺點(diǎn)蹭沛，容易過擬合，雖然有剪枝的操作章鲤，但是還是不夠摊灭。由多個弱決策樹分類器，加權(quán)或投票的得到一個強(qiáng)分類器败徊、
組合模型（bagging 與 boost）,這些算法最終的結(jié)果是生成N(可能會有幾百棵以上）棵樹帚呼，這樣可以大大的減少單決策樹帶來的毛病。
Bootstrap是一種有放回的抽樣方法思想皱蹦。兩方面：bagging和boosting
雖然都是有放回的抽樣煤杀，但二者的區(qū)別在于：Bagging采用有放回的均勻取樣，而Boosting根據(jù)錯誤率來取樣（Boosting初始化時(shí)對每一個訓(xùn)練例賦相等的權(quán)重1／n沪哺，然后用該學(xué)算法對訓(xùn)練集訓(xùn)練t輪沈自，每次訓(xùn)練后，對訓(xùn)練失敗的訓(xùn)練例賦以較大的權(quán)重）辜妓，因此Boosting的分類精度要優(yōu)于Bagging枯途。Bagging的訓(xùn)練集的選擇是隨機(jī)的，各輪訓(xùn)練集之間相互獨(dú)立籍滴，而Boostlng的各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)結(jié)果有關(guān)酪夷。
boost:最初為每個樣例賦予相同的權(quán)重，通過迭代的方式异逐，對每一次分類錯誤的樣例給予更高的權(quán)重捶索。進(jìn)行N次迭代，得到N個分類器灰瞻，再將它們組合起來（加權(quán)或投票）腥例，最終得到結(jié)果 .
隨機(jī)森林是在bagging基礎(chǔ)上，有放回的采樣酝润，隨機(jī)選取K個特征燎竖，同時(shí)獨(dú)立的建立N個決策樹，最后由投票表決的方式?jīng)Q定最后的結(jié)果要销。并行
GBDT(Gradient Boost Decision Tree 梯度提升決策樹)构回，GBDT的核心就在于：每一棵樹學(xué)的是之前所有樹結(jié)論和的殘差，迭代、串行纤掸。將決策樹結(jié)果累加的得到最后的結(jié)果脐供。故可知，GBDT基于回歸樹（CART樹）借跪。
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ù)測值）果港。xgboost的并行是在特征粒度上的沦泌。），xgboost在進(jìn)行節(jié)點(diǎn)的分裂時(shí)辛掠，支持各個特征多線程進(jìn)行增益計(jì)算谢谦，因此算法更快，準(zhǔn)確率也相對高一些公浪。
（3）優(yōu)化時(shí)他宛，GBDT梯度下降一階求導(dǎo)，xgboost是二階泰勒級數(shù)展開欠气。
（4）傳統(tǒng)GBDT以CART作為基分類器，xgboost還支持線性分類器镜撩，這個時(shí)候xgboost相當(dāng)于帶L1和L2正則化項(xiàng)的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）预柒。
XGBOOST參數(shù)：https://www.analyticsvidhya.com/blog/2016/03/complete-guide-parameter-tuning-xgboost-with-codes-python/
Adaboost(自適應(yīng)增強(qiáng))是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)袁梗，然后把這些弱分類器集合起來宜鸯，構(gòu)成一個更強(qiáng)的最終分類器(強(qiáng)分類器)。在訓(xùn)練集的不同子集上遮怜，多次調(diào)用弱學(xué)習(xí)算法淋袖，最終按加權(quán)方式聯(lián)合多次弱學(xué)習(xí)算法的預(yù)測結(jié)果就可得到最終學(xué)習(xí)結(jié)果。
與Boosting算法不同的是锯梁，adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差即碗，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度，
Adaboost(Adaptive Boosting)算法陌凳，對于boosting算法剥懒，存在兩個問題：
1. 如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行合敦；
2. 如何將訓(xùn)練得到的各個弱分類器聯(lián)合起來形成強(qiáng)分類器初橘。
針對以上兩個問題，adaboost算法進(jìn)行了調(diào)整：
1. 使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機(jī)選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點(diǎn)集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上保檐；
2. 將弱分類器聯(lián)合起來耕蝉，使用加權(quán)的投票機(jī)制代替平均投票機(jī)制。讓分類效果好的弱分類器具有較大的權(quán)重夜只，而分類效果差的分類器具有較小的權(quán)重赔硫。
RandomForest 與 GBDT 的區(qū)別：
相同點(diǎn)：
1.都由很多棵樹組成
2.最終的結(jié)果是由多棵樹一起決定的
不同點(diǎn)：
1.RandomForest中的樹可以是分類樹，也可以是回歸樹，而GBDT只能由回歸樹（CART）組成，這也說明GBDT各個樹相加是有意義的
2.RandomForest中的樹是并行生成的套么，而GBDT是串行生成的晓猛，GBDT中下一顆樹要去擬合前一顆樹的殘差，所以GBDT中的樹是有相關(guān)關(guān)系的喻旷，而RandomForest中的樹的相關(guān)性依賴于Boostrap生成的樣本子集的相關(guān)性
3.RandomForest 對異常值不敏感，GBDT敏感
4.RandomForest是通過降低模型方差來提高性能的，而GBDT是通過降低偏差來提高性能
GBDT 與 XGBOOST的比較：
1.傳統(tǒng)的GBDT以CART樹作為基分類器耘成，而XGBOOST還支持線性分類器，此時(shí)的線性分類器自帶正則項(xiàng)
2.傳統(tǒng)的GBDT在優(yōu)化時(shí)驹闰，只用到了loss function的一階導(dǎo)信息瘪菌，而XGBOOST對loss function做了Taylor展開，用到了二階導(dǎo)信息
3.XGBOOST在loss function中引入了正則項(xiàng)嘹朗，防止過擬合师妙，正則項(xiàng)里包含葉節(jié)點(diǎn)數(shù)以及每個葉節(jié)點(diǎn)上的score的L2的平方和
在計(jì)算劃分增益時(shí)，如果gain < gamma, 不劃分屹培，gain> gamma默穴，劃分，這相當(dāng)于決策樹的預(yù)剪枝褪秀。 gamma是葉節(jié)點(diǎn)個數(shù)的參數(shù)
4.XGBOOST還借用了RandomForest中的列抽樣思想蓄诽，也支持在劃分節(jié)點(diǎn)時(shí)，只考慮部分屬性
（現(xiàn)狀sklearn中的GBDT也實(shí)現(xiàn)了列抽樣）
5.XGBOOST可以自動學(xué)習(xí)出缺失值的分裂方向媒吗，論文中的default direction
（具體做法時(shí)仑氛，遍歷的嘗試將所有的缺失值分裂到所有方向{left or right}，split and default directions with max gain）
6.XGBOOST實(shí)現(xiàn)了并行化闸英，這個并行化是特征粒度上的并行化：劃分節(jié)點(diǎn)時(shí)锯岖，每個特征并行計(jì)算，同時(shí)每個特征的劃分節(jié)點(diǎn)也是并行計(jì)算（這是加速最猛的處理）
7.XGBOOST提出了block的概念自阱，簡單的說將排序后的特征值放在block中嚎莉，以后劃分特征的時(shí)候，只需要遍歷一次即可沛豌，因?yàn)闆Q策樹在處理屬性值時(shí)趋箩，需要將屬性值先排序赃额，這是最耗時(shí)的步驟，而block預(yù)先存儲了排序的特征值叫确，在后續(xù)過程中可以重復(fù)利用這個結(jié)構(gòu)中的數(shù)據(jù)跳芳，同時(shí)，計(jì)算每個特征的劃分增益可以并行處理了
Collecting statistics for each column can be parallelized,giving us a?parallel algorithm for split finding!!
8.貪心算法在選擇最佳劃分方式時(shí)需要遍歷所有的劃分點(diǎn)子集竹勉，在數(shù)據(jù)非常大時(shí)飞盆，這會非常低效，xgboost提出了近似直方圖計(jì)算次乓，根據(jù)數(shù)據(jù)的二階導(dǎo)信息進(jìn)行排序吓歇，提出一些候選劃分點(diǎn)子集
