融合協同過濾的CatBoost推薦算法

唐 震，黃 剛，華雯麗

(南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，江蘇 南京 210023)

0 引 言

隨著信息技術和互聯網環境的不斷發展，網絡用戶的不斷增加，人們進入了大數據的信息時代。電子商務市場和社交媒體的逐漸壯大是信息和數據急速增長的主要原因，網絡數據的快速增長在豐富互聯網生活的同時產生大量無用的數據，這些冗余信息給人們的生活帶來了不便。用戶對信息的反應速度無法跟上信息的傳輸及更新速度，用戶會對信息的選擇產生偏差，這導致了信息利用率的下降，這種類型的問題稱為信息過載[1]。解決信息過載的方法一般有兩種，其中一種為搜索引擎，利用用戶指定的關鍵字，通過關鍵詞檢索被動地過濾出用戶感興趣的信息，速度快但并不能突出用戶的個體需求。另一個便是推薦系統，推薦系統通過提供信息過濾機制來幫助用戶處理信息過載問題，能夠更好地滿足用戶個性化需求。

推薦系統大致可分為三類：基于內容的推薦[2]、協同過濾[3]推薦方法和混合推薦方法[4]。基于內容的推薦是根據物品的相關信息，用戶相關信息以及用戶相關行為構建模型找出用戶喜愛的物品。協同過濾通過用戶反饋信息進行推薦，有兩種常用類型：基于用戶的協同過濾(UCF)和基于項目的協同過濾(ICF)。混合推薦方法將不同的推薦算法過程或結果進行結合得出最終的推薦結果，組合后能夠彌補單個推薦算法的缺點。

協同過濾算法是目前研究最多、應用最廣泛的經典推薦算法。該算法實現簡單，適用性強，推薦效果較好。但隨著互聯網數據的幾何式增長，協同過濾推薦系統出現了很多問題，由于協同過濾需要利用用戶評分矩陣，所以當項目用戶過多時，部分評分缺失，計算相似度困難。面對新用戶，沒有足夠的歷史數據，無法計算目標用戶的相似用戶群，給推薦帶來了障礙，這是推薦系統中經典的冷啟動問題[5]。并且當數據量過大，推薦系統難以避免的會出現推薦速度慢，推薦準確度低的問題。

解決冷啟動問題一般通過利用用戶的注冊信息，用戶上下文信息，基于熱門數據的推薦等方法。Koren Y等人[6]提出了基于矩陣分解的系統過濾算法，矩陣分解的一個優點是它允許合并額外的信息。當沒有明確的反饋時，推薦系統可以使用隱式反饋來推斷用戶偏好，隱式反饋通過觀察用戶行為來間接反映用戶的偏好。張峰等人[7]提出了使用BP神經網絡緩解協同過濾推薦算法的冷啟動問題，根據用戶評分向量交集大小選擇候選最近鄰居集,采用BP神經網絡預測用戶對項的評分,減小候選最近鄰數據集的稀疏性，解決了冷啟動問題。

推薦系統準確度問題通過混合推薦算法、先進的評分預測算法等加以解決。Cheng-Che Lu和VS-Tseng[8]提出基于內容、基于情感的協同過濾推薦算法，該方法通過對用戶選擇的反饋，適應用戶興趣的變化，進而推薦出自己喜歡的、更有趣的物品，并進行即時連續推薦。

文中提出了一種融合協同過濾算法和CatBoost[9]的推薦算法，該算法旨在提高推薦系統模型的準確度，實現個性化推薦，提高用戶的滿意度，并在一定程度上緩解推薦系統冷啟動問題。算法思路：通過協同過濾算法構建用戶相似度矩陣，根據預測評分公式計算出用戶對未評分物品的預測評分，由此得到候選集，再利用CatBoost算法對整體數據集進行訓練，對候選集進行預測評分，最后將兩個預測評分進行加權融合，得到最終的預測評分從而實現對用戶的推薦。由于利用CatBoost算法進行數據集訓練利用到的特征較多，可以更好地實現用戶個性化推薦，與協同過濾算法進行加權融合后得到的結果更加準確。對于新用戶或者歷史交互記錄缺少的用戶，直接用CatBoost算法進行預測并推薦，可以有效緩解用戶的冷啟動問題。

1 相關工作

1.1 協同過濾算法

協同過濾算法(collaborative filtering recommendation)仍然是目前最為流行、使用最為廣泛的推薦算法。該算法的整體推薦效果在很多場景中不亞于新研究出來的其他推薦算法，并且相比較其他算法，協同過濾推薦算法的性能最為穩定。協同過濾算法通過系統提供的用戶項反饋來產生推薦，目的是在反饋信息中查找推薦信息，不需要關于用戶或項目的額外數據，可以作為推薦系統候選生成器。

基于用戶的協作過濾通過分析用戶的歷史行為數據，然后根據不同用戶對相同物品的評分或偏好程度來評測用戶之間的相似性，對有相同偏好的用戶進行物品推薦。基于項目的協同過濾通過對不同物品的評分來預測項目之間的相似性，再根據用戶歷史行為數據，得到用戶喜歡的物品，通過項目相似性矩陣找到相似度最高的物品，從而推薦給用戶。

基于用戶的協同過濾和基于項目的協同過濾的核心思想是在整個數據空間尋找用戶或項目的前k個最近鄰，都需要進行相似度計算。相似度計算的常用方法有余弦相似度、皮爾森(Pearson)相關系數法、歐幾里得距離法、杰卡德相似系數法等。

余弦相似度計算公式如下:

(1)

其中，I為所有項目的集合，i為項目集合中的單個項目，Ru,i為用戶u對項目i的真實評分，Rv,i為用戶v對項目i的真實評分。

皮爾森相關系數計算公式為：

sim(u,v)=

歐幾里得距離公式為：

(3)

杰卡德系數為：

(4)

(5)

在協同過濾算法中加入熱門商品懲罰項和時間衰減因子可以提高個性化推薦的準確度。懲罰熱門物品的原因是如果一個物品過于熱門，會有很多用戶對其進行評分，但這并不能說明這些用戶有著相同的興趣，所以對熱門物品增加一個懲罰項，減少熱門物品對用戶相似度的影響。

熱門商品懲罰項計算公式為：

(6)

其中，N(i)表示對物品i進行過評分的所有用戶。

由于用戶最近的行為更能表達用戶的當前興趣，所以在計算用戶相似度時可以增加時間衰減函數。時間衰減函數為：

(7)

其中，tui表示用戶u對物品i產生行為的時間，tvi表示用戶v對物品i產生行為的時間。通過對相似度計算方法的改進，得到優化后的余弦相似度公式：

sim(u,v)=

(8)

1.2 CatBoost

CatBoost全稱為Gradient Boosting(梯度提升)+Categorical Features(類別型特征)，是一種對決策樹進行梯度增強的算法，屬于集成學習算法的一種。它由Yandex公司的研究人員和工程師開發，用于Yandex和其他公司的搜索、推薦系統、個人助理、自動駕駛汽車、天氣預報和許多其他任務[10]。

Gradient Boosting方法是Boosting方法的一種，Boosting模型是通過最小化損失函數得到最優模型，是一個迭代的過程，每一次新的訓練的目的是改進前一次訓練的效果。Gradient Boosting的主要思想是每次都在前一次模型損失函數的負梯度方向建立新的模型使得損失函數能夠不斷下降[11]。Gradient Boosting方法適用于異質化數據,梯度提升方法比神經網絡的入門門檻更低，使用起來也更簡單。近年來，不少學者嘗試將集成學習算法運用到推薦系統中，崔巖等[12]提出融合協同過濾和XGBoost的推薦算法，提高了推薦的準確性；李智彬[13]提出融合SVD與LightGBM的音樂推薦算法，解決推薦系統冷啟動問題。作為最新的集成學習算法由于對CatBoost算法的相關研究較少，還沒有學者將其運用在推薦算法中。

CatBoost是一種能夠很好地處理類別型特征的梯度提升算法庫。根據官方測評結果[14]，CatBoost在準確率方面比同類型的XGBoost以及LightGBM表現更加優秀，該測評結果是在部分數據集上進行的實驗，在大多數實驗對比中，CatBoost都有著較為不錯的訓練速度與準確率。

CatBoost相比其他梯度提升算法具有兩大優勢：第一，不需要人為地處理類別型特征，CatBoost算法可以直接使用類別特征進行模型訓練，CatBoost使用獨特的方法處理類別特征[15]。首先對樣本進行隨機排序，然后針對類別型特征中的某個取值，每個樣本的該特征轉為數值型時都是基于排在該樣本之前的類別標簽取均值，同時加入了優先級和優先級的權重系數。并且可以將類別特征進行組合，利用特征之間的聯系，這極大地豐富了特征維度。定義編碼值的公式為：

(9)

類別特征的任何組合都可以視為新特征。例如，假設任務是電影推薦，有兩個特征：用戶ID和電影類型，某些用戶喜歡戰爭類的電影。在將用戶ID和電影類型轉換為數字特征時，會丟失此信息。將用戶ID與電影類型兩種特征進行組合解決了這個問題，并提供了一個新的特征。

在數據集中，特征組合數與特征數為指數關系，對于特征較多的數據集不可能在算法中考慮所有組合，這樣會增加計算量。CatBoost在決策樹的新一輪拆分時，以貪婪的方式對特征進行組合[16]：對于樹中的第一個拆分不考慮組合。在下一個分割節點選擇時，CatBoost將所有組合特征和分類特征與數據集中的所有分類特征組合在一起。組合值會動態轉換為數字，通過計算它的TS(target statistics)值作為新的特征值參與樹模型構建。CatBoost通過以下方式生成數字和類別特征的組合：在決策樹中，所有的拆分都被作為具有兩個值的類別特征，采用與類別特征相同的組合方式進行組合使用。

CatBoost相對于其他梯度提升算法的第二個優勢：在選擇生成樹結構時，計算葉子節點的算法可以避免過擬合。傳統的GBDT算法存在由于梯度估計偏差引起的過擬合問題，預測偏差是由一種特殊類型的目標泄漏引起的。CatBoost提出使用Ordered boosting[16]的方法來解決預測偏差從而得到梯度步長的無偏估計。Ordered boosting算法首先會生成一個長度為n的序列，對每個樣本xi訓練出一個單獨的模型Mi，使得Mi是僅利用了序列中的前i個樣本，不包含xi的訓練集得到的訓練模型。利用Mj-1訓練模型得到第j個樣本的梯度估計。

CatBoost同時具有CPU和GPU實現。GPU的實現允許更快的訓練，同時還具有快速的CPU評分實現。對于數值密集型特征的訓練，最重要的就是找到最佳分割，這是GBDT算法最主要的計算負擔。CatBoost使用對稱決策樹作為基礎學習者，并將特征離散化為固定數量的箱(bins)，以減少內存使用量，在訓練模型時可以設置最大箱數[17]。

2 融合協同過濾與CatBoost算法的推薦模型

2.1 算法思想

本模型融合CatBoost與協同過濾的算法為用戶進行推薦，形成新的算法模型UCF-CB。由于傳統的協同過濾算法根據用戶評分信息計算用戶對評分物品的預測評分從而進行推薦，隨著網絡信息的發展，用戶以及物品的信息不斷增加，協同過濾難以滿足用戶的個性化需求。融合CatBoost的協同過濾算法可以更全面地對用戶及物品信息進行分析，得到更為準確的預測評分，提高用戶的滿意度。本算法的協同過濾算法模塊，利用優化后的余弦相似度公式計算出目標用戶的相似用戶群，并對相似性進行排序，通過預測評分公式得到召回集并對召回集進行排序得到候選集。再利用CatBoost算法對數據集進行訓練，對候選集進行二次評分并將兩次評分結果進行融合，通過對參數以及權值的更新，達到提高算法準確度的目的，最后利用Top-N生成推薦列表。

2.2 算法描述

本算法包括通過協同過濾產生召回集，利用CatBoost進行模型訓練并對召回集的物品進行二次評分，生成推薦三個階段。算法流程如圖1所示。

圖1 算法流程

三個階段具體實現步驟為：

階段1：生成召回集D。

輸入：用戶歷史評分數據。

輸出：用戶召回集D。

算法步驟：

(1)將數據集進行劃分，70%的數據作為訓練集，30%的數據作為測試集。

(2)在訓練集中計算用戶之間的相似度，采用加入熱門商品懲罰項和時間衰減因子的優化算法復雜度的余弦相似度公式(8)進行相似度計算，并構建相似度矩陣。

(3)選取前k個目標用戶近鄰，利用式(5)計算目標用戶對未評分項目的預測評分。

(4)對預測評分進行排序，組成召回集D。

階段2：CatBoost模型訓練。

輸入：用戶歷史交互數據，用戶特征數據，物品特征數據。

輸出：訓練好的CatBoost模型。

算法步驟：

(1)整合輸入數據，提取特征，生成訓練集。

(2)對部分特征進行優化處理，利用CatBoost對訓練集進行模型訓練。

(3)優化模型，使用GridSearchCV對模型進行調參。

(4)得到優化后的模型，保存模型。

階段3：產生推薦列表。

輸入：協同過濾召回集D，協同過濾一次預測評分數據，CatBoost模型。

輸出：用戶推薦列表。

(1)在召回集中，選取每位用戶評分最高的前k個物品，形成候選集。

(2)利用訓練好的CatBoost模型對候選集進行二次評分預測，與協同過濾一次評分進行加權，得到最終的預測評分，將項目最終得分進行排序。

(3)利用Top-N產生推薦列表反饋給目標用戶。

3 實驗結果與分析

3.1 實驗數據集

文中采用的數據集是MovieLens-1m數據集，MovieLens-1M數據集含有來自6 040名用戶對3 952部電影的100余萬條評分數據。分為三個表：用戶評分信息、用戶信息、電影信息。其中用戶信息包括用戶id，用戶性別，用戶年齡，用戶職業和壓縮編碼，其中年齡1對應1～18歲(不包含18歲)，18表示18～24歲，25表示25～34歲，35表示35～44歲，45表示45～49歲，50表示50～55歲，56表示大于等于56歲，部分用戶信息如表1所示。電影信息包括電影id、電影名稱、電影類型，部分電影信息如表2所示。評分數據由6 040名用戶對3 952部電影的評分組成，一共1 000 209條數據，包括用戶和電影ID，得分值以及交互信息產生的時間戳，部分評分信息如表3所示。

表1 用戶信息

表2 電影信息

表3 評分信息

表1中的Zip-code為壓縮編碼，Occupation為用戶職業編號。

表2中Genres為電影類型特征，由符號|隔開，整個數據集共有18個類別特征。

Timestamp為用戶打分的時間戳，用戶評分范圍為1～5，沒有0分選擇。

3.2 數據預處理

如果使用原始數據集進行集成模型訓練，可利用到的特征僅有Gender，Age，Occupation，Genres四類。特征太少會導致模型訓練出來的效果較差，所以需要從原始數據中提取出更多特征，提高數據集特征的維度。

首先處理Genres中的電影類型特征，將特征逐一提取出來，構造18*N的特征矩陣，其中N為評分數據總條數，18為特征總數。將矩陣逐列添加到評分信息文件中，列名為電影類型的名稱。

從Title中提取出電影的相關上映時間，將上映時間加入到評分信息中，再從用戶打分的時間戳中提取出用戶打分的年份，將用戶對電影的評分年份也作為一個特征，最后刪除掉無用的信息，Zip-code，Title，Timestamp，Genres，得到最終的訓練數據集。

3.3 評價標準

文中提出的算法會得到用戶對于未評分物品的預測評分，所以使用均方誤差(mean squared error，MSE)作為預測評分準確度指標。計算公式如下：

(10)

均方誤差可以評價數據的變化程度，MSE的值越小，預測模型的精確度越高。

3.4 實驗結果與分析

(1)Boosting類算法準確率對比。

將數據集劃分，在訓練集上使用CatBoost算法對數據進行訓練，進行參數調節，使用GridSearchCV對模型進行參數調整。將task_type參數設置為“GPU”，可以有效提高模型的運行效率。對樹的深度depth，生成樹的數量iterations，學習率learning_rate，子樣本subsample，對象采樣方法bootstrap_type，隨機子空間方法rsm等參數分別進行調參設置。最終更新depth=10iterations=1 100，learning_rate=0.15，rsm=0.1，subsample=0.66。此時得到最佳訓練模型。圖3為學習率對應的得分值，評分標準為“r2”得分值，當學習率為0.15時，模型效果最好。將調節好的模型進行保存，在測試集上對模型進行效果測試。在此數據集上，分別利用三種流行的boosting算法進行實驗，分別得到三種算法在訓練集以及測試集上的結果。由圖2的實驗結果顯示，在此數據集上CatBoost與LightGBM表現幾乎沒有差別，CatBoost在測試集上的表現略微優于LightGBM，提升了約1.5%，XGBoost算法相對來說效果較差。以上數據在一定程度上證明了CatBoost算法在推薦系統中的可行性。

圖2 Boosting算法準確性對比

圖3 CatBoost學習率得分

(2)召回集各算法準確率對比。

在2.2節算法階段1中，說明了召回集的生成過程。召回集D共有233 329條數據，占總數據量的23.3%，混合XGBoost的協同過濾算法MSE值為0.800 3，文中提出的UCF-CB算法的MSE為0.693 15。將文中算法與文獻[18]提出的Weighted KM-Slope-Vu算法以及文獻[19]提出的WSO算法進行對比(見圖4)，文中算法的MSE均小于對比算法，表明提出的推薦算法在準確性上要優于對比算法。同時相比較在測試集上的評分預測結果，UCF-XGB與UCF-CB算法在準確性上都比原始的算法要有所提升。

圖4 召回集上算法對比

(3)最終推薦結果分析。

為了最終產生推薦列表，本實驗在召回集中對每個用戶選取協同過濾評分最高的前k個物品，取k值為8，共計42 211項，重新組成候選集，用混合模型進行評分預測。按照最終評分利用Top-N算法推薦給用戶。這里的k值可以根據要求推薦的數量而定，要求更精確的推薦，可以適當減小k值，要求更廣泛的推薦，可以加大k值。

最終的混合模型UCF-CB在D1上的MSE為0.637 81，協同過濾算法的MSE為0.794 3，UCF-XGB算法的MSE為0.749 67。對比原始的協同過濾算法以及UCF-XGB有明顯的提升，文中提出的算法模型在最終的推薦集上有著較好的表現(見圖5)。

圖5 混合模型分析

4 結束語

文中提出的混合推薦算法UCF-CB，通過改進后的協同過濾算法得到用戶的召回集D，利用訓練后的CatBoost算法對召回集進行二次評分預測，與協同過濾一次評分進行加權融合，得到最終的預測評分。在實驗2中，證明了該算法的優越性。最后將召回集進行壓縮得到D1，通過UCF-CB算法進行評分預測，生成推薦列表反饋給用戶。文中將不同的算法進行混合，提高了推薦系統的準確性，通過實驗對比驗證了相比較傳統的系統過濾算法有著明顯的提高，并且利用CatBoost集成學習模型可以解決推薦系統中的冷啟動問題。同時文中提出的算法也有不足之處，由于協同過濾算法在龐大的數據集上計算量過大，運行效率較差，會導致混合算法整體的效率較低。所以，下一步的工作將研究如何提高算法模型的運行效率，將矩陣分解運用到協同過濾算法中，解決數據稀疏性，對原始數據進行降維，減少計算量，使模型的運行效率更高。