xgboost代價函數(shù)里加入正則項，是否優(yōu)于cart的剪枝”。其實陳天奇大神的slides里面也是有提到的，我當一下搬運工。
決策樹的學習過程就是為了找出最優(yōu)的決策樹，然而從函數(shù)空間里所有的決策樹中找出最優(yōu)的決策樹是NP-C問題，所以常采用啟發(fā)式（Heuristic）的方法，如CART里面的優(yōu)化GINI指數(shù)、剪枝、控制樹的深度。這些啟發(fā)式方法的背后往往隱含了一個目標函數(shù)，這也是大部分人經(jīng)常忽視掉的。xgboost的目標函數(shù)如下：
Xgboost的目標函數(shù)
其中正則項控制著模型的復雜度，包括了葉子節(jié)點數(shù)目T和leaf score的L2模的平方：
正則項
那這個跟剪枝有什么關系呢？？？
跳過一系列推導，我們直接來看xgboost中樹節(jié)點分裂時所采用的公式：
這個公式形式上跟ID3算法（采用entropy計算增益） 、CART算法（采用gini指數(shù)計算增益） 是一致的，都是用分裂后的某種值 減去 分裂前的某種值，從而得到增益。為了限制樹的生長，我們可以加入閾值，當增益大于閾值時才讓節(jié)點分裂，上式中的gamma即閾值，它是正則項里葉子節(jié)點數(shù)T的系數(shù)，所以xgboost在優(yōu)化目標函數(shù)的同時相當于做了預剪枝。另外，上式中還有一個系數(shù)lambda，是正則項里leaf score的L2模平方的系數(shù)，對leaf score做了平滑，也起到了防止過擬合的作用，這個是傳統(tǒng)GBDT里不具備的特性。
