王永貴，李倩玉

遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島125105

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

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

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

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

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

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

1 理論基礎(chǔ)

1.1 KNN算法

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

KNN協(xié)同過濾算法流程如下：

（1）相似度計算

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

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

②余弦相似度（Cosine）

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

（2）K 個最近鄰的選擇

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

（3）預(yù)測評分

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

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

1.2 Boosting集成學(xué)習(xí)技術(shù)

Booosting 算法是一種集成學(xué)習(xí)法，多級集成學(xué)習(xí)技術(shù)即通過集成多個不同的相似度計算方法來提升最終的推薦準(zhǔn)確度。單個推薦算法容易陷入“單指標(biāo)最優(yōu)”的困境，而多級集成學(xué)習(xí)技術(shù)則因為這種能力，在很多領(lǐng)域都顯示出了強大的優(yōu)越性與實用性[15]。

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

2 本文算法

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

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

圖1 算法流程圖

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

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

2.1.1 用戶相似度計算方法

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

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

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

2.1.2 物品相似度計算方法

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

2.2 Boosting集成過程

推薦系統(tǒng)的Boosting 集成過程：U 代表用戶集合，I 代表物品集合，Y 中1表示目標(biāo)用戶購買過該物品，0則表示目標(biāo)用戶沒購買過該物品，算法最后計算的結(jié)果會將0 值變?yōu)榉? 值，最后系統(tǒng)會篩選出得分較大的物品，并將其推薦給用戶。

2.3 GBDT算法描述

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

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

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

3 實驗設(shè)計

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

3.1 實驗準(zhǔn)備

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

表1 實驗數(shù)據(jù)集描述

3.2 評價指標(biāo)

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

3.3 參數(shù)設(shè)置

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

3.4 實驗結(jié)果與分析

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

（1）最佳參數(shù)K的影響

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

圖2 在不同K 值下推薦結(jié)果的召回率和準(zhǔn)確率

（2）不同數(shù)據(jù)集下的召回率

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

圖3 數(shù)據(jù)集MovieLens100k的召回率

圖4 數(shù)據(jù)集MovieLens1M的召回率

（3）不同數(shù)據(jù)集下的F1

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

圖5 數(shù)據(jù)集MovieLens100k的F1

圖6 數(shù)據(jù)集MovieLens1M的F1

（4）算法運行時間

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

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

4 結(jié)束語

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

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