文 | 光大科技大數據部 何玥穎
在建模過程中，我們常常會遇到一類比較「棘手」的特徵——類別型特徵。例如在針對客戶的價值或行為進行預測時，經常需要將諸如性別、城市、學歷、婚姻狀況等信息納入考量。在對這些信息進行建模時，往往需要進行大量的前期工作。
本文要介紹一種專門針對類別型變量的算法——CatBoost，讓我們不再需要手動處理類別型變量。
一、CatBoost 算法簡介二、目標變量統計三、預測偏移四、樹模型的建立五、Python實踐案例六、總結
一、CatBoost 算法簡介
CatBoost[1]，來源於「Category」和「Boosting」，屬於 Boosting 算法的一種，由俄羅斯最大的搜尋引擎 Yandex 於 2017 年開發，與 XGBoost[2]、LightBGM[3] 一樣，都是對 GBDT算法的改進。相較於其他 Boosting 算法，CatBoost 的優勢在於能夠高效處理類別型變量、能夠有效防止過擬合且模型訓練精度高。
CatBoost 的主要特點
自動處理類別型特徵: 在使用 CatBoost 建模時，不需要對類別型特徵進行任何預處理。CatBoost 使用內置的算法，實現了在建模的過程中直接將類別型特徵轉化為數值型特徵。
特徵組合: CatBoost 在建模中還會根據特徵的內在聯繫將原有類別型特徵進行組合，豐富了特徵維度，提升了預測結果的精確性。
排序的思想: CatBoost 在處理類別型變量和進行樹模型構建時，都是基於樣本的某個隨機排序，對樣本進行加工和計算，以獲取目標變量統計值和模型梯度值的無偏估計，有效避免了預測偏移(Prediction Shift)。
二、目標變量統計
2.1 類別型變量數值轉換
類別型特徵是在金融數據分析中常見的一類特徵。所謂類別型特徵，即這類特徵不是連續的數值，而是一些用以區分類別的值的集合。這些特徵值不能直接應用於建模，需要先向數值型特徵進行轉換，將這些特徵加工成目標變量統計值 (Target Statistics)，再進行建模工作。
在一般算法中，TS 的計算往往是採用特徵值為某一類別的所有樣本對應的目標變量的期望 。假設總樣本量為 ，對於第 個樣本 的第 個特徵 ，假設該特徵類別為 ，則對於所有第 個特徵取值為 的樣本 都有：
其中 為樣本 的目標變量值， 為示性函數，即 時函數取值為 1 ，否則函數取值為0 。
然而，這種方法的主要缺陷在於類別型特徵中低頻次特徵帶來的噪聲。為了解決這一問題，Catboost 算法採用了 Greedy TS，即在公式中添加了先驗分布項：
其中 是添加的先驗項， 是大於 0 的權重係數。針對類別數較少的特徵，添加先驗項可以減少噪音。對於回歸問題，先驗項可取數據集目標變量的均值；對於二分類問題，先驗項是正例的先驗概率。
Greedy TS 依舊存在一定缺陷，因為其使用了 對 進行估計，導致 有偏。
通過抽取不包含 的部分樣本 對 進行估計可以解決 有偏的問題：
抽取部分樣本 的方法有很多，比如 Holdout TS，Leave-one-out TS 以及 Ordered TS 。Catboost算法採用的是效率更高的Ordered TS： ，即取在某一給定的樣本排序 中排在樣本 前的樣本 的集合。
我們可以看到，這裡第 項的表達為 ，其含義為在某一樣本排序 中的第 項。通過構造樣本的排序， 的估計值 等於：前 個樣本中所有第 個特徵類別為 c 的樣本對應的目標變量的平均值 。這一算法有效克服了 有偏引起的過擬合問題。
2.2 特徵組合
CatBoost 的另一個重要細節就是將所有類別型特徵進行組合，並將存在較高內在聯繫的組合特徵作為新的的特徵參與建模。例如在進行銷售預測時，可以將用戶號 (user_id) 與用戶喜歡的商品名稱或類別進行組合。
組合數量隨類別型特徵數量的增加呈指數型增長，類別型特徵較多的情況下很難將所有類別型特徵都進行組合。CatBoost採用了一種貪婪策略：在每次進行樹模型新的分割結點選擇時，將當前樹所有分割點已使用的類別型特徵（組合）與數據集中所有類別型特徵進行組合，並計算其 TS 作為新的特徵值參與樹模型構建。
三、預測偏移
3.1 梯度提升算法的基本概念
首先來說說梯度提升 (gradient boosting) 的整體迭代過程：
梯度提升算法通過對一組弱分類器 串行迭代，最終得到一個強學習器 ，以此來提高分類器的擬合精度。
假設前一輪迭代得到的強學習器是 , 損失函數是 ， ，則本輪迭代的目的是從一組函數 中找到能使本輪迭代的損失函數 ， 取到最小的 ，其中 ， 為步長或學習率 (learning rate)。式 (5) 為本輪迭代的目標函數:
一般處理最優化問題常見的做法是採用牛頓法 (Newton's Method[4])，即使用損失函數的負梯度 來擬合每一輪的損失的近似值。求解梯度公式如式 (6) :
使用最小二乘法擬合的損失函數如下:
最終得到本輪的強學習器 : 。
CatBoost 使用二叉樹 (Binary Decision Tree) 作為基分類器，在 CatBoost 中的分類器 可寫作：
其中 是第 個葉子結點包含的樣本集合， 是這些樣本集的個數，屬於葉子結點 的所有樣本 的目標變量 的取值都為 。
3.2 預測偏移的形成
所有經典的梯度提升算法都存在由有偏的點態梯度估計引起的過擬合問題。在使用訓練集 訓練模型時，公式 (7) 的實際形式如下：
由於上一輪在獲得強分類器 時，已經使用了當前樣本點 進行建模，導致使用式 (6) 擬合本輪梯度的條件分布 有偏於測試集的真實分布 ，進而影響了本輪強分類器的 的預測效果，形成預測偏移 (Prediction Shift)。
想要獲得所有樣本點 ,..., 在 輪循環中梯度 的無偏估計，理論上在訓練模型 時就不能使用其中的任何一個，這樣一來看似就沒有可以用來進行建模的樣本了。為了解決這一問題，CatBoost 提出了一種叫做 Ordered Boosting 的集成算法。
3.3 Ordered Boosting
為了獲得每一個樣本點上梯度值的無偏估計，Ordered Boosting 依舊利用了排序的核心思想。首先初始化模型 ,..., 。給定某一排序 ，在第 輪建模中：
使用排在 之前的所有樣本 ,..., 建模得到的模型 對 的目標值進行估計，並計算出殘差 (residual) ；用 來構建模型 ;最後用 來修正第 輪得到的 ，以降低下一輪預測的殘差;這一做法避免了使用當前樣本導致的誤差偏移 (residual shift) ，有效的避免了過擬合問題。
使用 Ordered Boosting 思想建樹的偽代碼如圖1：
圖1 Ordered Boosting偽代碼從代碼中可以看出，該方法在每輪循環中，針對每一個 都要訓練並優化一個模型 ，一共需要訓練 個不同的模型，大大增加了算法的時間複雜度和佔用的內存空間。同時，選定的樣本排序不同對於模型的預測結果也存在一定影響，提高了算法的不穩定性。CatBoost 在 Order Boosting 的基礎上，結合 GBDT 的基本概念對算法進行了優化。
四、樹模型的建立
CatBoost算法的核心環節在於樹結構 的建立： 。
4.1 建立新樹的基本思想
CatBoost 建模過程與其他 GBDT 算法一樣分為兩個階段：選擇樹結構 和在樹結構固定後計算葉子節點的值 。每一輪循環的輸出結果都是一個樹結構 和更新後的模型 。
在 CatBoost 構建樹的過程中，模型 用於計算葉子結點上目標變量的值。 是基於樣本排序 中前 個樣本計算出的樣本 的當前目標變量的估計值 。在每輪迭代中，從 個不同的樣本排序 中抽取一組排序 ，並基於這個排序建立一個新的樹結構 ，再依據 更新所有模型 ,..., 。在這裡， 代表對於所有樣本隨機生成的 種不同順序的序列。
4.2 兩個核心公式
：計算每個樣本點 基於樹 和排序 所屬的葉子結點（不同的排序會導致算出不同的 TS，進而影響每個樣本點所屬的葉子結點）。：基於損失函數 和當前的模型 以及目標變量 計算模型 在樣本點 上的梯度，如式 (6)， 相當於其中的 。4.3 建立新樹 步驟
隨機抽取一種樣本排序 ;基於樣本排序以及模型 ，估計每一個樣本點 的梯度值 ;對每一種可能的分割方案 ，建立樹結構 ，計算所有樣本基於 和排序 所屬的葉子結點，並計算每個葉子結點的所有樣本梯度的均值作為該葉子結點樣本的梯度的估計值 ;構造梯度值損失函數，選取使損失函數取最小值的樹結構作為本輪的樹模型 ;基於樹 ，計算每一種排序 ,..., 情況下屬於同一葉子結點的樣本 的負梯度均值，作為樣本基於樹 在該排序下的目標值 ;更新每種排序策略 對應的 ： = ，其中 。輸出 ， ;建立樹結構的偽代碼如圖2：
圖2 CatBoost樹模型偽代碼4.4 CatBoost完整建模過程
CatBoosts 輸入：
：訓練集； ：循環數； ：步長； ：損失函數； ：排序的個數；Mode ：模式其中真實排序個數為 個， ,..., 用於計算 Oredered TS，這些 TS 進一步用於分割結點的選擇，從而固定樹模型的結構。 用於計算葉子結點的值 （詳見公式 (8)）。CatBoosts 建模步驟：
設置 個不同的樣本排序方式， ,..., ；初始化用於計算葉子結點取值的模型 ,..., ；在第 次循環中，使用 建立樹結構 ，並更新 ， ；使用排序 計算 Ordered TS，並基於樹 確定每個樣本所屬的葉子結點；基於樣本排序 以及模型 ，估計每一個樣本點的梯度值；對於 上每一個葉子結點，計算葉子結點的值 ，即所有屬於該葉子點的樣本的負梯度均值；更新 ， = ，其中 ；CatBoost建模的偽代碼如圖3：
圖3 CatBoost偽代碼為了便於理解，其中的 可換成 。使用 的目的是提升模型預測速度（詳見4.6）。
4.5 對Oredered Boosting的改進
如上述偽代碼中所示，CatBoost 算法有兩種模式 (Mode) ， Plain 和 Ordered 。 Plain 與標準 GBDT 算法相似，只是在計算過程中使用內置的 Oredered TS 方法對類別型特徵進行轉化，而不需要人為對類別型特徵進行加工。Ordered 模式則是對 Ordered Boosting 的改進，即在計算梯度值時，使用了 Ordered Boosting 中對梯度進行無偏估計的方法。
算法中， ,..., 的計算方法是相同的，區別在於基於的樣本排序 不同。 CatBoost 在每次迭代都隨機抽取一個排序進行樹的建立，並對所有 同步更新，降低了 Ordered Boosting 中不同排序對於模型預測結果的影響，增強了模型的泛化能力。
4.6 快速預測
在樹的結構上， CatBoost 採用對稱樹（Oblivious Decision Tree），即在樹的同一層的節點上都採用相同的分割標準。這種對稱樹能夠有效避免過擬合，同時能夠顯著提升測試效率。
同時，在實際運算中（如圖3），為了降低運算複雜度， CatBoost 使用的是前 個樣本建立的模型 進行估計，而非之前偽代碼中的 個。這部分偽代碼詳見論文 (CatBoost: unbiased boosting with categorical features) 的附件 B。
五、Python實踐案例
CatBoost 庫[5] 既可以解決分類問題 (CatBoostClassifier) ，也可以解決回歸問題 (CatBoostRegressor) 。本文將以分類問題為例，數據採用UCI 資料庫中的 Adult 數據集[6]。
該數據集抽取自 1994 年人口普查數據，包含 14 個特徵變量和 1 個目標變量，目標是預測樣本的年收入是否大於 5 萬美金。數據集中已提供訓練集 (adult.data) 和測試集 (adult.test) 。
首先，導入 Catboost 庫、CatBoostClassifier 分類器，並讀取數據:
import numpy as npimport pandas as pdfrom catboost import CatBoostClassifier## 讀取數據train_set = pd.read_csv('adult_data.csv',na_values='?',encoding = 'gbk')test_set = pd.read_csv('adult_test.csv',na_values='?',encoding = 'gbk')查看數據train_set.shape，test_set.shape可以得知測試集包含32561個樣本，測試集包含16281條樣本 (圖4)：
圖4 train_set其中education-num使用數字編碼代替了對應的學歷，與education是一一對應的，本文在建模時就將此列刪掉了。
#將目標變量轉化為數值型train_set['salary'] = train_set['salary'].astype('category').cat.codestest_set['salary'] = test_set['salary'].astype('category').cat.codes#將數據集分為特徵變量和目標變量train_labels = train_set['salary']train_data = train_set.drop(['salary','education-num'],axis = 1)test_labels = test_set['salary']test_data = test_set.drop(['salary','education-num'],axis = 1)看一下各變量的數據類型train_data.dtypes，（如圖 5）可以看出特徵變量既有數值型，也有類別型:
圖5 特徵的數據類型可以看出，我們沒有手動處理任何類別型特徵。CatBoost 可以直接處理缺失的特徵以及類別型特徵，我們只需告知分類器哪些維度是類別維度。
##提取類別型特徵的indexcategorical_features= np.where(train_data.dtypes != np.int64)[0]##使用訓練集對模型進行擬合model = CatBoostClassifier(loss_function='Logloss')model.fit(train_data, np.ravel(train_labels), cat_features)將模型應用於測試集，檢驗模型預測效果：
result = model.predict(test_data)print('error:',1-np.mean(result==np.ravel(test_labels)))在沒有進行調參的情況下，CatBoost 分類的錯誤率為12%（在訓練集上的預測錯誤率為11%）。
六、總結
CatBoost 能夠直接處理類別型特徵，同時提升了預測精度，具有較強的泛化性及較低的時間複雜度，還能兼顧分類問題與回歸問題，是一種非常強大的算法。
對 Boosting 算法感興趣的讀者可以自己嘗試用 CatBoost 解決回歸問題，在本專題後續的文章中還會與大家分享 CatBoost 算法的調優以及 CatBoost 與其它 GBDT 算法的效果對比。
參考資料
[1] CatBoost: unbiased boosting with categorical features: https://arxiv.org/abs/1706.09516v2
[2] XGBoost: https://xgboost.readthedocs.io/en/latest/
[3] LightBGM: https://www.microsoft.com/en-us/research/project/lightgbm/
[4] 百度百科-牛頓迭代法: https://baike.baidu.com/item/%E7%89%9B%E9%A1%BF%E8%BF%AD%E4%BB%A3%E6%B3%95/10887580?fr=aladdin
[5] CatBoost: https://pypi.org/project/catboost
[6] Adult: https://archive.ics.uci.edu/ml/datasets/Adult
我們是光大科技公司的追光實驗室團隊，將不定期推出數據挖掘和算法相關的數據科學原創文章。團隊定位打造基於知識驅動的機器學習實驗室，由實踐經驗豐富的數據分析挖掘工程師和專注算法的數據科學家精心準備相關作品，志在分享結合實際業務的理論應用和算法創新，以及其中的心得體會。