基于KNN-GBDT的混合協同過濾推薦算法

王永貴，李倩玉

遼寧工程技術大學 軟件學院，遼寧 葫蘆島125105

隨著互聯網技術的迅速發展和網絡資源的日益豐富，隨之而來的海量信息超載和信息迷航等問題使得推薦系統應運而生，成為電子商務中不可缺少的工具。推薦系統作為一種可以向用戶提供個性化推薦的系統，目前已被廣泛應用于電子商務中用來挖掘用戶日常行為數據中的隱藏商業價值。據電子商務統計，推薦系統對網上商品銷售的貢獻率為20%～30%。其中，協同過濾[1]是推薦系統中研究最多、應用最廣的個性化推薦技術，其主要特點在于不依賴商品的內容，而是完全依賴于一組用戶表示的偏好[2]。通常，協同過濾主要分為兩大類，包括基于內存[3]的協同過濾和基于模型[4]的協同過濾。前者通過計算用戶和物品之間的相關性，為目標用戶推薦相似的物品；后者通過研究用戶的歷史數據，進行優化得到統計模型后推薦，而且大多數模型是機器學習模型和語言模型，如Bayes[5]、LDA[6]等。由于最近鄰關系模型使用簡潔方便，推薦結果直接明了，因此大多數推薦系統都采用基于最近鄰關系模型的協同過濾。其中，K-最近鄰模型（KNN[7]）是在最近鄰關系模型中使用頻率最高的一個模型。

Zhang 等人[8]提出了一種KNN 和SVM 混合的協同過濾推薦算法，但因為推薦系統中數據的極端稀疏性問題，SVM分類器的分類精度并不準確。傳統的KNN算法沒有考慮到數據的稀疏性問題，時間復雜度高，而且只對兩個及以上用戶評分的物品進行分析，容易忽略一些用戶的潛在信息，導致推薦精度低。此外，采用基于單分類[9]的推薦算法預測目標用戶[10]的評分時，容易陷入“單指標最優”的困境。Bellkor 使用多級集成學習技術，即通過組合多種不同的推薦算法來提升推薦準確度獲得了2009 年Netflix 推薦算法大賽的冠軍。Freund[11]是最早將Boosting 集成學習框架應用到信息檢索領域的人，但其提出的理論只能解決小規模樣本集問題[12]。方育柯等人通過大規模數據實驗說明Boosting 集成學習法用于推薦系統的可行性[13]。

針對存在的問題，本文結合KNN 和Boosting 算法的功能特點，提出一種基于KNN-GBDT 的混合協同過濾推薦算法。其主要貢獻可概括如下：

（1）在相似度計算公式中引入只有單個用戶評價的物品權重，以發現更多目標用戶和物品之間的潛在信息。在相關計算中，先使用奇異值分解（SVD[14]）法來減少向量的維數，縮短計算時間。

（2）采用GBDT 算法作為基本框架，利用多分類器通過集成多組推薦結果預測評分，最后為目標用戶推薦預測評分高的物品。

（3）在MovieLens 數據集上進行大量實驗，證明本文算法優于其他基于單分類的推薦算法，提升了推薦精度，有效解決了數據集稀疏性問題。

1 理論基礎

1.1 KNN算法

KNN算法的工作原理是在計算用戶（物品）相似度的基礎上，來尋找相應的K 近鄰集合，然后根據最近鄰集合預測目標用戶對物品的評分并進行推薦。

KNN協同過濾算法流程如下：

（1）相似度計算

一般而言，相似度計算分為基于用戶的相似度計算和基于物品的相似度計算，常用的方法分別為Person相關性和余弦相似度。假設總共有n 個用戶的集合U={U1,U2,…,Un} 和m 個物品的集合I={I1,I2,…,Im} 。根據用戶-物品矩陣H ∈Rn×m，計算每個用戶（物品）與另外所有用戶（物品）的相似度。

其中，ru、rv分別表示用戶u 和用戶v 的評分向量；ru,i表示用戶u 對物品i 的評分，rv,i表示用戶v 對物品i的評分。

②余弦相似度（Cosine）

當用余弦公式計算用戶（物品）之間的相似度時，將每一個用戶（物品）看成一個n 維的向量，再利用上述公式進行計算。

（2）K 個最近鄰的選擇

在計算完基于用戶（物品）之間的相似度后，選擇與目標用戶相似程度最高的K 個用戶合并在一個集合中，這個集合就是目標用戶的K 最近鄰集合。

（3）預測評分

令目標用戶u 的最近鄰集合為N(u)，然后利用目標用戶的K 最近鄰集合中的用戶對目標用戶未評分的物品進行評分，計算公式如下：

最后，篩選出評分高的物品推薦給目標用戶。

1.2 Boosting集成學習技術

Booosting 算法是一種集成學習法，多級集成學習技術即通過集成多個不同的相似度計算方法來提升最終的推薦準確度。單個推薦算法容易陷入“單指標最優”的困境，而多級集成學習技術則因為這種能力，在很多領域都顯示出了強大的優越性與實用性[15]。

Adaboost算法是Booosting算法的最早的一種實現版本。在算法的初始化階段，為每個樣本提供一個相等的抽樣權重（一般開始時權重相等即認為均勻分布），換句話說，在開始時每個樣本都是同樣重要的。接下來在這些樣本上訓練一個分類器對樣本進行分類，由此便可以得到這個分類器的誤差率，根據它的誤差率對這個分類器賦予一個權重，賦予權重的大小由分類器的誤差率所決定，誤差越大權重越小。然后針對此次分錯的樣本增大它的抽樣權重，同時減少分對樣本的抽樣權重，這樣訓練的下一個分類器就會更加關注這些難以分離的樣本，然后再根據它的誤差率賦予權重，由此可見精度越高的分類器權重越大，就這樣進行n 次迭代，最后得到的就是由多個弱分類器加權和的強分類器。

2 本文算法

采用Boosting 集成學習法作為本文算法的基本框架，將基于KNN 的協同過濾算法作為Boosting 算法的弱分類器進行分類。

在得到用戶物品矩陣后，改進傳統的基于用戶相似度的計算式，引入了若只有單個用戶評價的物品權重，并將改進后的相似度計算式（基于用戶的皮爾遜相關性和基于物品的修正的余弦相似度）得出的多組候選最近鄰居集的預測評分作為GBDT 算法的多分類器所需的預測空間進行集成。最后，篩選出評分最高的N 個物品推薦給目標用戶。本文算法流程圖如圖1所示。

圖1 算法流程圖

2.1 改進的KNN相似度計算方法

針對傳統相似度計算方法存在的問題，本文提出了對相似度計算改進的方法。在基于用戶的皮爾遜相似度計算式中，引入了若只有單個用戶評價的物品權重；在基于物品的相似度計算式中，使用了修正的余弦相關性。

2.1.1 用戶相似度計算方法

使用U 代表用戶，I 代表物品，假設推薦系統中有n 個用戶的集合U={U1,U2,…,Un} 和m 個物品的集合I={I1,I2,…,Im} 。用戶評分數據集用R 表示，Ri,j代表用戶Ui對物品Ij的評分，這一評分體現了用戶對物品的興趣和偏好。

傳統的KNN 相似度計算方法中，只對兩個用戶共同評分的物品進行分析，如果兩個用戶共同評分的物品數量非常少，那么計算出來的這兩個用戶之間的相似度會很高。但實際上，這兩個用戶對物品的興趣相似度并不會很高。針對此問題，引入只有單個用戶評價的物品權重。改進后的用戶相似度計算式為：

式（6）和式（7）分別在式（1）和式（2）的基礎上，加入只有用戶u 和只有用戶v 評分的物品權重C1和C2。其中，Iu,v=Iu-Iv表示用戶u 已經進行評分而用戶v沒有進行評分的物品。C1表示用戶u 在Iu,v中對該物品的評分，C2表示用戶v 在Iu,v對該物品的評分。

2.1.2 物品相似度計算方法

在余弦相似度計算式中沒有考慮到不同用戶的評分尺度問題，修正的余弦相關性通過減去用戶對商品的平均評分來改善上述缺陷。對于物品p 和物品q，分別對應用戶u 和用戶v 的評分。

2.2 Boosting集成過程

推薦系統的Boosting 集成過程：U 代表用戶集合，I 代表物品集合，Y 中1表示目標用戶購買過該物品，0則表示目標用戶沒購買過該物品，算法最后計算的結果會將0 值變為非0 值，最后系統會篩選出得分較大的物品，并將其推薦給用戶。

2.3 GBDT算法描述

如前所述，本文采用基于KNN的協同過濾算法，將改進后的相似度計算式得出的多組候選最近鄰居集的預測評分作為GBDT算法的多分類器所需的預測空間，并對多組推薦結果進行集成。

GBDT算法作為AdaBoost算法的改進，由梯度提升算法和決策樹算法兩部分組成，其核心為減小殘差，即負梯度方向生成一棵決策樹以減小上一次的殘差。Boosting 思想遵循的基本原則是每一次建立模型都是建立在模型損失函數梯度下降方向。如果在建立模型的時候讓損失函數迭代下降，則就說明模型在不斷往優化的方向上改進，GBDT算法就是讓損失函數在其梯度方向上下降。決策樹算法具有時間復雜度低、預測速度快等優點，但是單個決策樹算法很容易因為過度擬合影響最終的分類結果。GBDT算法使用多分類器，創建數百棵樹，可以最大限度減小決策樹算法過度擬合的程度，而且各分類器設計簡單，訓練的進度也會相應加快。

對于有著N個樣本點(xi,yi)，計算其在候選最近鄰居集模型F(x:α,β)下的損失函數，最優的參數{α,β}就是使損失函數最小的參數。其中，α為候選最近鄰居集模型里面的參數，β為每個候選最近鄰居集模型的權重。優化參數的過程就是所謂的梯度優化的過程。假設目前已經得到了m-1 個候選最近鄰居集模型，在求第m個候選最近鄰居集模型的時候，首先對m-1 個候選最近鄰居集模型求梯度，得到最快下降方向。候選最近鄰居集模型的最終結果依賴于多個候選最近鄰居集模型結果相加。GBDT 算法多分類器集成過程如下所示：

3 實驗設計

為了驗證基于KNN-GBDT的混合協同過濾推薦算法的性能，將本文所提出的算法和LDA、CMF、SVD 等經典推薦算法進行比較，并對得到的實驗結果進行分析。LDA將項目視為一個單詞，將用戶視為一個文檔，由此以計算推薦物品的可能性。CMF通過同時分解多個矩陣來合并不同信息源。SVD 是基于特征的協同過濾算法。

3.1 實驗準備

實驗采用的是MovieLens 數據集來評價所提出算法在TopN推薦列表中的效果，其包含100 KB、1 MB、10 MB 三個規模的數據集，專門用于研究推薦技術。MovieLens 是一家電影推薦網站，該數據集由明尼蘇達大學GropLens研究小組通過此網站發布。此數據集包含943位用戶對1 682部電影的100 000條1～5分的評分數據，如表1 所示，取值越高代表用戶對電影的評價越高。為了便于實驗，對評分值進行重新標定，將1～5 的評分值轉化為0～1的評分值。

表1 實驗數據集描述

3.2 評價指標

為了更加公平地評價算法性能，隨機將數據集分成互不相交的兩部分：訓練集和測試集（比例為7∶3），進行10次劃分，分別形成10組不同的訓練集和測試集，然后使用用于評價TopN推薦列表的評價指標：召回率（Recall），準確率（Precision）和F1 來評估實驗結果。最終的算法評價是基于這10 組訓練集測試集的平均值。其中，N表示推薦列表中的物品總數，P表示目標用戶在前N項中喜歡的物品數。

3.3 參數設置

在算法中，對實驗結果有影響的參數有兩個，第一個是在KNN 推薦算法中，計算完相似度之后選擇的最佳參數K個候選最近鄰居集。第二個是TopN算法的推薦列表長度，因為考慮到推薦問題的實用性，推薦列表不適宜太長，因此推薦列表的長度設置為5、10、15、20、25。

3.4 實驗結果與分析

實驗從最佳參數K對準確率和召回率的影響，在不同數據集上的召回率和F1，以及運行時間的長短對算法進行對比評估。

（1）最佳參數K的影響

最佳參數K控制著模型復雜度，若K值過小，即模型會過于簡單；若K值過大，會產生數據擬合，導致算法在性能上受到較大影響。實驗利用召回率和準確率作為評判標準來測試最佳參數K的值。本文算法將K控制在0～400來測試TopN協同過濾推薦算法，并且重復實驗三次，取這三次實驗得到的平均值作為最終結果，不同K值下的準確率和召回率如圖2所示。通過圖2 表明，K值在100～300 時性能比較穩定；當K=200時，經典的TopN協同過濾推薦算法的召回率和準確率達到最高；當K＞300 后性能略微下滑。因此，基于KNN-GBDT 的混合協同過濾推薦算法取K值為200，即在協同過濾推薦算法中每一個物品的候選最近鄰居集合數目為200。

圖2 在不同K 值下推薦結果的召回率和準確率

（2）不同數據集下的召回率

圖3和圖4表示的是四種推薦算法在數據量不同的數據集上的召回率，其中橫坐標表示的是推薦列表的長度，縱坐標表示的是推薦結果的召回率，四種算法在召回率上的性能優劣如下所示：KNN+GBDT＞LDA＞SVD＞CMF。從圖3 可以看出，當推薦列表長度小于10 時，LDA 算法的召回率是高于本文所提出算法的召回率的，但隨著推薦列表長度的增加，GBDT迅速上升，此時能明顯看出，本文算法的召回率高于其他傳統推薦算法的召回率，這說明LDA算法性能并不穩定，不太適合復雜的推薦系統。如圖4所示，由于MovieLens1M中的數據量大于MovieLens100k，所以MovieLens1M 中的數據稀疏性遠低于MovieLens100k，這使得模型更容易訓練，因此MovieLens1M中算法的召回率低于MovieLens100k中算法的召回率。

圖3 數據集MovieLens100k的召回率

圖4 數據集MovieLens1M的召回率

（3）不同數據集下的F1

召回率并不是唯一的評估指標，也可以使用F1 來評估四種算法的性能。其中橫坐標表示的是推薦列表的長度，縱坐標表示的是推薦結果的F1，四種推薦算法在F1 上的性能優劣如下所示：KNN+GBDT＞SVD＞LDA＞CMF。從圖5 可以看出，當推薦列表長度小于10時，SVD 算法和本文所提出算法的F1 相差不大，但隨著推薦列表長度的增加，準確度會增加，相應F1 也會增加，此時基于多分類器的協同過濾算法明顯優于其他傳統推薦算法，這說明了GBDT不僅能夠在推薦列表頂端具有較高的準確率，同時在推薦列表的中間部分同樣具有較大的優勢。如圖6所示，由于MovieLens1M中的數據稀疏性遠低于MovieLens100k，因此MovieLens1M 中算法的F1 稍高于MovieLens100k中算法的F1。

圖5 數據集MovieLens100k的F1

圖6 數據集MovieLens1M的F1

（4）算法運行時間

實驗測試了兩種模型在不同模型復雜度下的運行時間，其中橫坐標表示的是K值，縱坐標表示的是運行時間。在不同的K值下每個模型運行五次后取平均值，實驗結果如圖7 所示。從圖7 可知，當K＞300 時，KNN+GBDT算法具有明顯的優勢，運行時間較CMF算法減少很多；當K＝700 時，兩種算法運行時間相差了2 000 s之多，可以得出KNN+GBDT算法更適合復雜的推薦系統，同時也說明了多分類器的時間效率比單分類器的時間效率高；當K＞700 時由于實驗性能較差，且運行時間較長，故不做考慮。

圖7 不同K 值下的運行時間

4 結束語

本文旨在分析如何利用多分類器提高推薦精度，提出了一種基于KNN-GBDT 的混合協同過濾推薦算法。在傳統KNN相似度計算公式中考慮了只有單個用戶評價的物品的權重，得到了目標用戶更多的潛在相關信息。采用GBDT算法預測目標用戶對物品的評分，利用多分類器對KNN算法的多組預測結果進行集成。

在實驗部分與其他傳統推薦算法進行了比較。推薦結果采用的是TopN形式，即分別統計目標用戶對未曾購買或者評價過的物品的興趣度，取排在前N位的物品形成推薦集。實驗結果表明，KNN-GBDT 算法其準確率和召回率不僅明顯優于基于單分類器的協同過濾算法，還優于其他傳統推薦算法。本文算法增加了數據預處理部分，這對于推薦算法的應用來說是一個不利因素，因此本文下一步的工作就是優化模型，改進GBDT算法，在預測目標用戶對物品的評分時考慮更多用戶和物品的特性，對分類器進行優化，提高訓練速度。