之前簡(jiǎn)單介紹過(guò)決策樹(shù)，這篇文章簡(jiǎn)單介紹一下GBDT(Gradient Boosting Decision Tree).
Gradient Boosting
決策樹(shù)是一種基本的分類與回歸方法。決策樹(shù)模型具有分類速度快，模型容易可視化的解釋，但是同時(shí)是也有容易發(fā)生過(guò)擬合，雖然有剪枝，但也是差強(qiáng)人意。
提升方法（boosting）在分類問(wèn)題中，它通過(guò)改變訓(xùn)練樣本的權(quán)重（增加分錯(cuò)樣本的權(quán)重，減小分隊(duì)樣本的的權(quán)重），學(xué)習(xí)多個(gè)分類器，并將這些分類器線性組合，提高分類器性能。
于是決策樹(shù)與boosting結(jié)合產(chǎn)生許多算法，主要有提升樹(shù)、GBDT等。
Gradient Boosting是一種Boosting方法，主要思想是：每一次建立模型是在之前建立模型損失函數(shù)的梯度下降方向。損失函數(shù)是評(píng)價(jià)模型性能(一般為擬合程度+正則項(xiàng))，認(rèn)為損失函數(shù)越小，性能越好。讓損失函數(shù)持續(xù)下降，就能使模型不斷改進(jìn)提升性能，最好的方法就是使損失函數(shù)沿著梯度方向下降。
Gradient Boosting是一個(gè)框架，里面可以套入不同很多的算法
Gradient Boosting Decision Tree
每一次建立樹(shù)模型是在之前建立模型損失函數(shù)的梯度下降方向。即利用了損失函數(shù)的負(fù)梯度在當(dāng)前模型的值作為回歸問(wèn)題提升樹(shù)算法的殘差近似值，去擬合一個(gè)回歸樹(shù)。
決策樹(shù)的子類
class DecisionTree(object):
"""Super class of RegressionTree and ClassificationTree.
def __init__(self, min_samples_split=2, min_impurity=1e-7,
max_depth=float("inf"), loss=None):
self.root = None # Root node in dec. tree
# Minimum n of samples to justify split
self.min_samples_split = min_samples_split
# The minimum impurity to justify split
self.min_impurity = min_impurity
# The maximum depth to grow the tree to
self.max_depth = max_depth
# Function to calculate impurity (classif.=>info gain, regr=>variance reduct.)
# 切割樹(shù)的方法，gini，方差等
self._impurity_calculation = None
# Function to determine prediction of y at leaf
# 樹(shù)節(jié)點(diǎn)取值的方法，分類樹(shù)：選取出現(xiàn)最多次數(shù)的值，回歸樹(shù)：取所有值的平均值
self._leaf_value_calculation = None
# If y is one-hot encoded (multi-dim) or not (one-dim)
self.one_dim = None
# If Gradient Boost
self.loss = loss
上面代碼中有兩個(gè)重要變量。impurity_calculation和leaf_value_calculation。
前者代表切割樹(shù)的分類標(biāo)準(zhǔn)是什么。分類樹(shù)就是基尼系數(shù)，回歸樹(shù)就是最小平方殘差。
后者代表計(jì)算節(jié)點(diǎn)值的方法。分類樹(shù)則切割數(shù)據(jù)集中數(shù)量最多的種類，回歸樹(shù)則計(jì)算切割數(shù)據(jù)集中所有的平均值。
classification Tree:
class ClassificationTree(DecisionTree):
def _calculate_information_gain(self, y, y1, y2):
# 交叉墑
# Calculate information gain
p = len(y1) / len(y)
entropy = calculate_entropy(y)
info_gain = entropy - p * \
calculate_entropy(y1) - (1 - p) * \
calculate_entropy(y2)
# print("info_gain",info_gain)
return info_gain
def _majority_vote(self, y):
# 計(jì)算節(jié)點(diǎn)，出現(xiàn)最多
most_common = None
max_count = 0
for label in np.unique(y):
# Count number of occurences of samples with label
count = len(y[y == label])
if count > max_count:
most_common = label
max_count = count
# print("most_common :",most_common)
return most_common
def fit(self, X, y):
self._impurity_calculation = self._calculate_information_gain
self._leaf_value_calculation = self._majority_vote
super(ClassificationTree, self).fit(X, y)
RegressionTree:
class RegressionTree(DecisionTree):
def _calculate_variance_reduction(self, y, y1, y2):
# 平方殘差
var_tot = calculate_variance(y)
var_1 = calculate_variance(y1)
var_2 = calculate_variance(y2)
frac_1 = len(y1) / len(y)
frac_2 = len(y2) / len(y)
# Calculate the variance reduction
variance_reduction = var_tot - (frac_1 * var_1 + frac_2 * var_2)
return sum(variance_reduction)
def _mean_of_y(self, y):
# 平均值
value = np.mean(y, axis=0)
return value if len(value) > 1 else value[0]
def fit(self, X, y):
self._impurity_calculation = self._calculate_variance_reduction
self._leaf_value_calculation = self._mean_of_y
super(RegressionTree, self).fit(X, y)
GDBT應(yīng)用--回歸和分類
分類：每棵樹(shù)擬合當(dāng)前整個(gè)模型的損失函數(shù)的負(fù)梯度，構(gòu)建新的樹(shù)加到當(dāng)前模型中形成新模型，下一棵樹(shù)擬合新模型的損失函數(shù)的負(fù)梯度。
回歸：每一棵樹(shù)擬合當(dāng)前整個(gè)模型的殘差，構(gòu)建新的樹(shù)加到當(dāng)前模型中形成新模型，下一棵樹(shù)擬合新模型的損失函數(shù)的負(fù)梯度。
GBDT的原理
如何在不改變?cè)心Ｐ偷慕Y(jié)構(gòu)上提升模型的擬合能力
假設(shè)存在樣本集(x1, y1), (x2, y2)....， 然后用一個(gè)模型f(x)去擬合數(shù)據(jù)，使的平方損失函數(shù):
最小。
但是發(fā)現(xiàn)雖然擬合效果很好，但是仍有差距。
既然不能更改原來(lái)模型的參數(shù)，意味著要在原來(lái)模型的基礎(chǔ)上做改善，直觀就是建議一個(gè)新的模型fx來(lái)擬合Fx為完全擬合真是樣本的殘差， 即y-F(x)。
對(duì)于每個(gè)樣本得到的擬合樣本集變?yōu)椋?br> (x1, y1 - F(x1)), (x2, y2 - F(x2)), (x3, y3 - F(x3)),..., (xn, yn - F(xn))
GBDT構(gòu)建新的特征
特征決定模型上屆。如果能夠?qū)?shù)據(jù)表達(dá)成為線性可分的數(shù)據(jù)，那么使用簡(jiǎn)單的線性模型可以得到更好的效果。GBDT構(gòu)建新的特征也是使特征更好的表達(dá)數(shù)據(jù)。
在預(yù)測(cè)Facebook廣告點(diǎn)擊中，使用一種將決策樹(shù)與邏輯回歸結(jié)合在一起的模型，其優(yōu)于其他方法，超過(guò)3％。
主要思想：GBDT每棵樹(shù)的路徑直接作為L(zhǎng)R輸入特征使用。
用已有特征訓(xùn)練GBDT模型，然后利用GBDT模型學(xué)習(xí)到的樹(shù)來(lái)構(gòu)造新特征，最后把這些新特征加入原有特征一起訓(xùn)練模型。構(gòu)造的新特征向量是取值0/1的，向量的每個(gè)元素對(duì)應(yīng)于GBDT模型中樹(shù)的葉子結(jié)點(diǎn)。當(dāng)一個(gè)樣本點(diǎn)通過(guò)某棵樹(shù)最終落在這棵樹(shù)的一個(gè)葉子結(jié)點(diǎn)上，那么在新特征向量中這個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的元素值為1，而這棵樹(shù)的其他葉子結(jié)點(diǎn)對(duì)應(yīng)的元素值為0。新特征向量的長(zhǎng)度等于GBDT模型里所有樹(shù)包含的葉子結(jié)點(diǎn)數(shù)之和。
例子1：上圖有兩棵樹(shù)，左樹(shù)有三個(gè)葉子節(jié)點(diǎn)，右樹(shù)有兩個(gè)葉子節(jié)點(diǎn)，最終的特征即為五維的向量。對(duì)于輸入x，假設(shè)他落在左樹(shù)第一個(gè)節(jié)點(diǎn)，編碼[1,0,0]，落在右樹(shù)第二個(gè)節(jié)點(diǎn)則編碼[0,1]，所以整體的編碼為[1,0,0,0,1]，這類編碼作為特征，輸入到線性分類模型（LR or FM）中進(jìn)行分類。
上面簡(jiǎn)單介紹了原理，筆者也是不太懂。后續(xù)學(xué)到再補(bǔ)充。
代碼這里就不做實(shí)現(xiàn)，有需要請(qǐng)查看sklearn的工具包。
參考資料：
GBDT原理及利用GBDT構(gòu)造新的特征-Python實(shí)現(xiàn)
機(jī)器學(xué)習(xí)-一文理解GBDT的原理-20171001
GBDT的python源碼實(shí)現(xiàn)
