最近在學習樹一類的演算法,略有所得所以跟大家一起分享。
以下轉載自http://www.jianshu.com/p/005a4e6ac775
綜述
GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree),是一種迭代的決策樹演算法,該演算法由多棵決策樹組成,所有樹的結論累加起來做最終答案。它在被提出之初就和SVM一起被認為是泛化能力較強的演算法。
GBDT中的樹是回歸樹(不是分類樹),GBDT用來做回歸預測,調整後也可以用於分類。
GBDT的思想使其具有天然優勢可以發現多種有區分性的特徵以及特徵組合。業界中,Facebook使用其來自動發現有效的特徵、特徵組合,來作為LR模型中的特徵,以提高CTR預估(Click-Through Rate Prediction)的準確性(詳見參考文獻5、6);GBDT在淘寶的搜索及預測業務上也發揮了重要作用(詳見參考文獻7)。
一、Regression Decision Tree:回歸樹
回歸樹總體流程類似於分類樹,區別在於,回歸樹的每一個節點都會得一個預測值,以年齡為例,該預測值等於屬於這個節點的所有人年齡的平均值。分枝時窮舉每一個feature的每個閾值找最好的分割點,但衡量最好的標準不再是最大熵,而是最小化平方誤差。也就是被預測出錯的人數越多,錯的越離譜,平方誤差就越大,通過最小化平方誤差能夠找到最可靠的分枝依據。分枝直到每個葉子節點上人的年齡都唯一或者達到預設的終止條件(如葉子個數上限),若最終葉子節點上人的年齡不唯一,則以該節點上所有人的平均年齡做為該葉子節點的預測年齡。(引用自一篇博客,詳見參考文獻3)