劉英濤：達(dá)觀數(shù)據(jù)推薦算法工程師，負(fù)責(zé)達(dá)觀數(shù)據(jù)個(gè)性化推薦系統(tǒng)的研發(fā)與優(yōu)化。
XGBoost的全稱是 eXtremeGradient Boosting，2014年2月誕生的專注于梯度提升算法的機(jī)器學(xué)習(xí)函數(shù)庫(kù)，作者為華盛頓大學(xué)研究機(jī)器學(xué)習(xí)的大?！愄炱?。他在研究中深深的體會(huì)到現(xiàn)有庫(kù)的計(jì)算速度和精度問(wèn)題，為此而著手搭建完成 xgboost 項(xiàng)目。xgboost問(wèn)世后，因其優(yōu)良的學(xué)習(xí)效果以及高效的訓(xùn)練速度而獲得廣泛的關(guān)注，并在各種算法大賽上大放光彩。
1.CART
CART(回歸樹(shù), regressiontree)是xgboost最基本的組成部分。其根據(jù)訓(xùn)練特征及訓(xùn)練數(shù)據(jù)構(gòu)建分類(lèi)樹(shù)，判定每條數(shù)據(jù)的預(yù)測(cè)結(jié)果。其中構(gòu)建樹(shù)使用gini指數(shù)計(jì)算增益，即進(jìn)行構(gòu)建樹(shù)的特征選取，gini指數(shù)公式如式(1), gini指數(shù)計(jì)算增益公式如式(2)：
表示數(shù)據(jù)集中類(lèi)別的概率，表示類(lèi)別個(gè)數(shù)。
注:此處圖的表示分類(lèi)類(lèi)別。
D表示整個(gè)數(shù)據(jù)集，
和
分別表示數(shù)據(jù)集中特征為的數(shù)據(jù)集和特征非的數(shù)據(jù)集，
表示特征為的數(shù)據(jù)集的gini指數(shù)。
以是否打網(wǎng)球?yàn)槔?只是舉個(gè)栗子):
其中，
最小，所以構(gòu)造樹(shù)首先使用溫度適中。然后分別在左右子樹(shù)中查找構(gòu)造樹(shù)的下一個(gè)條件。
本例中，使用溫度適中拆分后，是子樹(shù)剛好類(lèi)別全為是，即溫度適中時(shí)去打網(wǎng)球的概率為1。? ? ??
2.Boostingtree
一個(gè)CART往往過(guò)于簡(jiǎn)單,并不能有效地做出預(yù)測(cè)，為此，采用更進(jìn)一步的模型boosting tree，利用多棵樹(shù)來(lái)進(jìn)行組合預(yù)測(cè)。具體算法如下：
輸入：訓(xùn)練集
輸出：提升樹(shù)
步驟：
（1）初始化
（2） 對(duì)m=1,2,3……M
? ? ? ? a）計(jì)算殘差
? ? ? ? b）擬合殘差
學(xué)習(xí)一個(gè)回歸樹(shù)，得到
? ? ? ? c）更新?
（3）得到回歸提升樹(shù)：
例子詳見(jiàn)后面代碼部分。
3.xgboost
首先，定義一個(gè)目標(biāo)函數(shù)：
constant為一個(gè)常數(shù)，正則項(xiàng)
如下，
其中，T表示葉子節(jié)點(diǎn)數(shù)，
表示第j個(gè)葉子節(jié)點(diǎn)的權(quán)重。
例如下圖，葉子節(jié)點(diǎn)數(shù)為3，每個(gè)葉子節(jié)點(diǎn)的權(quán)重分別為2，0.1，-1，正則項(xiàng)計(jì)算見(jiàn)圖：
利用泰勒展開(kāi)式
,對(duì)式(3)進(jìn)行展開(kāi)：
其中，
表示
對(duì)
的一階導(dǎo)數(shù)，
表示
對(duì)
的二階導(dǎo)數(shù)。
為真實(shí)值與前一個(gè)函數(shù)計(jì)算所得殘差是已知的(我們都是在已知前一個(gè)樹(shù)的情況下計(jì)算下一顆樹(shù)的)，同時(shí)，在同一個(gè)葉子節(jié)點(diǎn)上的數(shù)的函數(shù)值是相同的，可以做合并，于是：
通過(guò)對(duì)求導(dǎo)等于0，可以得到
將
帶入得目標(biāo)函數(shù)的簡(jiǎn)化公式如下：
目標(biāo)函數(shù)簡(jiǎn)化后，可以看到xgboost的目標(biāo)函數(shù)是可以自定義的，計(jì)算時(shí)只是用到了它的一階導(dǎo)和二階導(dǎo)。得到簡(jiǎn)化公式后，下一步針對(duì)選擇的特征計(jì)算其所帶來(lái)的增益，從而選取合適的分裂特征。
提升樹(shù)例子代碼：
# !/usr/bin/env python
# -*- coding: utf-8 -*-
?
# 目標(biāo)函數(shù)為真實(shí)值與預(yù)測(cè)值的差的平方和
?
import math
?
# 數(shù)據(jù)集，只包含兩列
test_list = [[1,5.56], [2,5.7], [3,5.81], [4,6.4], [5,6.8],
????? ??????[6,7.05], [7,7.9], [8,8.7], [9,9],[10,9.05]]
?
step = 1 #eta
# 起始拆分點(diǎn)
init = 1.5
# 最大拆分次數(shù)
max_times = 10
# 允許的最大誤差
threshold = 1.0e-3
?
def train_loss(t_list):
??? sum = 0
??? for fea in t_list:
??????? sum += fea[1]
??? avg = sum * 1.0 /len(t_list)
??? sum_pow = 0
??? for fea in t_list:
??????? sum_pow +=math.pow((fea[1]-avg), 2)
??? return sum_pow, avg
?
def boosting(data_list):
??? ret_dict = {}
??? split_num = init
??? while split_num <data_list[-1][0]:
??????? pos = 0
??????? for idx, data inenumerate(data_list):
??????????? if data[0]> split_num:
??????????????? pos = idx
??????????????? break
??????? if pos > 0:
??????????? l_train_loss,l_avg = train_loss(data_list[:pos])
??????????? r_train_loss,r_avg = train_loss(data_list[pos:])
????????? ??ret_dict[split_num] = [pos,l_train_loss+r_train_loss, l_avg, r_avg]
??????? split_num += step
??? return ret_dict
?
def main():
??? ret_list = []
??? data_list =sorted(test_list, key=lambda x:x[0])
?
??? time_num = 0
??? while True:
??????? time_num += 1
??????? print ‘beforesplit:’,data_list
??????? ret_dict =boosting(data_list)
??????? t_list =sorted(ret_dict.items(), key=lambda x:x[1][1])
??????? print ‘splitnode:’,t_list[0]
???????ret_list.append([t_list[0][0], t_list[0][1][1]])
??????? if ret_list[-1][1]< threshold or time_num > max_times:
??????????? break
??????? for idx, data inenumerate(data_list):
??????????? if idx <t_list[0][1][0]:
??????????????? data[1] -=t_list[0][1][2]
??????????? else:
??????????????? data[1] -=t_list[0][1][3]
??????? print ‘after split:’,data_list
??? print ‘split node andloss:’
??? print’n’.join([“%st%s” %(str(data[0]), str(data[1])) for data inret_list])
?
if __name__ == ‘__main__’:
??? main()? ? ?
