融合鄰域模型與隱語義模型的推薦算法

魯權，王如龍，張錦，丁怡

湖南大學信息科學與工程學院，長沙 410082

融合鄰域模型與隱語義模型的推薦算法

魯權，王如龍，張錦，丁怡

湖南大學信息科學與工程學院，長沙 410082

1 引言

隨著互聯網的普及與電子商務的快速發展，信息的過度膨脹[1]與冗余導致人們在尋找自己所需的信息時花費大量時間。個性化推薦系統[2]能夠提供一種有效的機制，幫助用戶在縮減信息獲取過程耗費的時間代價的同時保證信息獲取的質量，因而得到越來越多研究者的關注。

協同過濾[3]是目前各個推薦系統中應用最為廣泛和成功的技術，它的基本思想是，如果兩個或多個用戶在某些信息（例如網頁或者商品）的選擇上表現出相同的興趣或給出接近的評價，那么在其他一些信息的選擇上也可能做出相同的選擇或給出接近的評價。為了構建推薦系統，協同過濾算法需要對用戶和物品因素進行比較，兩種主流的方法分別是鄰域模型和隱語義模型。

鄰域模型[4]主要刻畫物品或者用戶之間的相似度。一個基于物品的鄰域模型通過計算用戶對相似物品的評分來預測用戶對該物品的評分。這種方法不需要比較用戶與物品之間的關系，只需要關注物品之間的相似度就能做出計算。

隱語義模型[5]，例如奇異值分解（Singular Value Decomposition，SVD）[6]的基本思想是把高維向量空間模型[7]中的文檔映射到低維的潛在語義空間中。降維處理使得物品與用戶的潛在關系能夠在潛在子空間中自然的顯現出來，通過主成分分析[8]對原有數據進行簡化的同時，去除噪音和冗余，揭示隱含在復雜數據背后的簡單結構。

傳統的協同過濾算法一般采用評分這一顯性反饋[9]——項目評價矩陣進行相似度計算，然而隨著電子商務系統規模的增長，協同過濾算法面臨著兩個巨大挑戰，即數據稀疏性[10]、可擴展性[11]，而隱性反饋[12]如用戶的瀏覽記錄和頁面點擊行為數據量更大，可以彌補因為顯性反饋數據缺少帶來的不足。

本文將鄰域模型和隱語義模型結合，提出一種新的融合顯性與隱性反饋的協同過濾算法模型，稱為（Hybrid-SVD Model）。該模型能有效地將兩種反饋信息結合起來，并綜合考慮用戶與物品之間隱含關系。實驗數據表明Hybrid-SVD Model在Netflix數據集上性能優于已有的算法。

2 融合鄰域模型與隱語義模型的協同過濾推薦算法

協同過濾算法需要數值形式的評分來進行預測。雖然顯性反饋滿足這個要求，但是顯性反饋評分數量通常不足以訓練出準確的模型。另一方面，隱性反饋因為不需要額外的評分操作，在數量上比顯性反饋大很多。如果找出一種方法能夠有效地將隱性反饋信息轉化為適合的數值形式的估計值，就能夠提高使用顯性反饋信息訓練的模型準確性。對于Netflix數據集，最自然的隱性反饋信息當然是電影的租借歷史信息，然而該信息未能公開。另一個隱性反饋信息則是用戶的歷史評分行為信息，這一隱性反饋信息表明用戶偏好選擇某些電影進行評分（不管評分高或者低）。雖然這一隱性反饋信息不如其他隱性反饋信息廣泛或者獨立，但是在一般基于評分的推薦系統中普遍存在，并且能夠顯著地提高預測精度。

需要提出的是，本文提出的算法并不只針對這一特定的隱性反饋信息，為了保證一般性，每個用戶u與物品i構成兩個數據集：顯性反饋數據集R，包含用戶對物品的顯性評分信息；隱性反饋數據集N(u)，包含所有用戶對物品的隱性偏好數據。

2.1 融合隱性反饋的鄰域模型

加入偏置項bui=μ+bu+bi，這是考慮在實際情況下，一個評分系統有些固有屬性和用戶物品無關，而用戶也有些屬性和物品無關，物品也有些屬性和用戶無關。因此，μ為訓練集中所有記錄的評分的全局平均數，表示網站本身對用戶評分的影響。bu為用戶偏置項，表示在用戶評分習慣中和物品無關的因素，如有些用戶偏苛刻，普遍評分較低而有些用戶比較寬容，評分偏高。bi為物品偏置項，表示物品接受評分中和用戶無關的因素，例如物品本身質量

首先考慮基于鄰域的協同過濾模型，模型為如下形式：很高，因此獲得評分普遍比較高。{|j∈R(u)}為給定的物品i在給定的顯性反饋集R(u)中的插值權重。

利用隱性反饋信息，添加另外一組權重，可將公式（1）改寫為如下形式：

cij與wij類似，對于兩個物品i和j，一個用戶u對物品j的正隱性反饋信息會在模型中修正預測值rui，給出一個更高的預測值。將這些權值視為全局偏移量，而非基于用戶或者基于項目的系數，便強化了缺失評分值的影響，即用戶的預測評分不僅與其評分歷史數據相關，同時與他未評分的物品相關，特別是那些相對熱門，而用戶并未評分的物品。例如，假設一個電影評分數據集顯示那些對“指環王3”評分較高的用戶通常對“指環王1－2”的評分也相對較高，這就使得“指環王3”與“指環王1－2”之間有很高的權值。假設一個用戶沒有對“指環王1－2”進行評分，那么他對“指環王3”的預測評分會變低，因為相應的權值cij在模型中為0。

2.2 考慮鄰域影響的隱語義模型

本文工作的一個重要目標是設計一種融合鄰域模型與隱語義模型的改進協同過濾模型。從抽象的層次來看，協同過濾可以看做矩陣填充（Matrix Completion）問題：用戶對商品的評分組成一個評分矩陣，每個用戶可能僅對其中一小部分商品做過評價，因此這個矩陣通常是非常稀疏的。對于如何補全一個矩陣，歷史上有過很多研究。一個空的矩陣有很多種補全方法，這里需要找出一種對矩陣擾動最小的補全方法。一般認為，如果補全后矩陣的特征值和補全之前矩陣的特征值相差不大，則稱其擾動小。因此，最早的矩陣分解模型是從數學上的SVD（奇異值分解）開始的。然而傳統的SVD分解需要用一個簡單的方法補全稀疏評分矩陣，評分矩陣會變成一個稠密矩陣，從而使評分矩陣的存儲需要非常大的空間，這種空間需求在實際系統中時不太可接受的。同時分解算法時間復雜度也很高，特別是在稠密的大規模矩陣中非常慢。正是由于上面的兩個缺點，SVD分解算法提出后在推薦系統領域并未得到廣泛關注，直到2006年Netflix Prize開始后，Simon Funk公布了一個算法（Funk-SVD）。從矩陣分解[13]的角度，將每一個用戶u關聯一個用戶因子向量pu∈Rf，將每一個物品i關聯一個物品因子向量qi∈Rf。如果將評分矩陣R分解為兩個低維矩陣相乘：

要最小化上面的損失函數，可以利用隨機梯度下降法（Stochastic Gradient Descent）[14]。該算法是最優化理論里基礎的優化算法，它首先通過求參數的偏導數找到最速下降的方向，然后通過迭代法不斷地優化參數。

上文定義的損失函數里有兩組參數（puf和qif），最速下降法需要首先對它們分別求偏導數，可以得到：

然后，根據隨機梯度下降法，需要將參數沿最速下降方向向前推進，因此可以得到如下遞推公式：

其中，α是學習速率（Learning Rate），它的取值需要通過反復實驗獲得。

初始化P、Q矩陣的方法很多，一般是將這兩個矩陣用小范圍隨機數填充，根據多次實驗表明，隨機數需要和1/sqrt(F)成正比。

由于特征向量維數f固定，因此預測的時間復雜度僅為O（1）。在用梯度方法對當前單個特征向量元素求偏導時，和其余特征向量相關的項均為0，因此回避了一般SVD算法中需要迭代或插值求解矩陣中未知元素的問題。另外也可以看出，每次迭代使用一個評分數據，整個訓練過程只需要存儲特征向量的內存空間，因此特別適合于有非常大數據集的情況。

這種算法每次迭代更新只需要很少的計算量，求解每個特征向量都是相同的時間。和批處理矩陣分解相比，數據量的多少并不影響更新計算速度。算法每次產生一個特征向量，并且保證該向量是目前為止最顯著的特征向量。這意味著每次從矩陣中提取出來的都是最重要的特征，保證了算法的精度。與其他增量方法相比，這種學習方法區別在于前者收斂于整個數據集的特征值分解，而不是目前所見數據為止的一個最優解[15]。

將矩陣分解模型融合隱形反饋信息進行擴展，將評分預測公式改寫為：

根據隨機梯度下降法，得遞推公式：

其中eui=rui-即真實評分與預測評分的差值。

從公式（11）可以看出，當|N(u)|數量較大時，即隱性反饋信息較多時，隱性反饋信息在評分預測中占主要因素；當|R(u)|數量較大時，即顯性反饋信息較多時，顯性反饋信息在評分預測中占主要因素。一個顯性信息通常要比一個隱性反饋信息有價值。而如何平衡這兩個信息的權重，則是由相關參數xj與yj在模型的迭代學習中自動獲得的。

改進后的模型有效融合了隱性反饋信息。通過融合隱性反饋信息，提供了額外的用戶偏好信息，從而改進了算法的精度。隱性反饋信息的作用，在那些提供隱性反饋信息遠高于顯性反饋信息的用戶體現得更為明顯。

3 實驗結果及評估

3.1 Netflix數據集

本文對算法的評估基于Netflix數據集，其中包括了從1998年10月到2007年8月的超過1 900 000 000個評分，這些評分來自于11 700 000多個用戶對85 000多部電影的1～5之間的評分，評分高則表示用戶喜歡這部電影。為了測試各種不同的算法，Netflix提供了兩個測試數據集。一個是探測集（Probe Set），這個集合在原1億條訓練數據集中抽取140萬條評分數據，因此在這個集合中，用戶對電影的真實評分是知道的。

另一個是測驗集（Qualifying Set），測驗集由280萬條數據組成，但是沒有提供電影評分的真實數據。兩個數據集都挑選了一些難以預測的用戶，讓人們對他們的評分進行猜測。使用均方根誤差（RMSE）作為性能評估的標準，定義如下。

對于測試集中的一對用戶和物品(u，i)，用戶u對物品i的真實評分是rui，而推薦算法預測的用戶u對物品i的評分為，那么一般可以用RMSE度量預測的精度：

在對模型進行訓練之前，將探測集從訓練集中剝離，在剩下的數據集上訓練出來的模型在探測集上進行預測評估。

實驗表明，如果包含探測集來訓練，最后得到的RMSE將比沒有包含探測集得到的結果降低0.03左右，這是一個很大的提高。因此，這種剝離探測集訓練模型的方法將更接近真實預測情況。

3.2 結果與討論

本文通過實驗對比Hybrid-SVD算法在評分預測問題中的性能。在該算法中，重要的參數有3個：隱特征的個數k、學習速率alpha和正則化參數lambda。通過實驗發現，隱特征個數k對算法性能影響最大。因此，固定學習速率alpha與正則化參數lambda，研究隱特征個數k對推薦結果性能的影響。算法參數選擇：學習速率參數alpha與正則化參數lambda通過交叉驗證決定。

本文采用alpha=0.007，lambda1=0.005，lambda2=0.015進行實驗。在訓練集上迭代次數選用15次。學習速率參數按每次迭代縮減為0.9倍的速度遞減。控制鄰域范圍的參數，即隱特征個數k，通過實驗證明k值越大，實驗精度越高，因此需要在算法精度與計算代價之間取得平衡。

在Netflix數據集上采用新鄰域模型的實驗結果如圖1所示。采用不同數值的參數k進行模型學習。從藍色曲線中可以看出算法精度隨著k值的增加單調上升，當k值從250上升到無窮（對于該數據集，無窮代表全部電影項，即k=17 770）時，RMSE從0.913 9下降至0.900 2。將隱性反饋信息從該模型剔除后重復進行實驗，結果如紅色曲線所示，可見算法精度明顯低于融合隱性反饋信息的模型，并且，隨著k值增加，這種精度差別更加明顯，即沒有融合隱性反饋信息的模型，算法精度隨k值增加提升不如融合隱性反饋的模型明顯。

圖1 不同k值各模型在Netflix數據集下測試的RMSE值

作為對比，本文提供了兩種典型的基于鄰域的模型，即基于用戶的鄰域模型（UserNgbr）和基于物品的鄰域模型（ItemNgbr）。對于每種模型，選用優化的參數，對基于用戶的鄰域模型，選用鄰居大小為20，而對于基于物品的鄰域模型，選用鄰居大小為50。實驗結果如圖1兩條曲線所示，這里k值對以上兩模型沒有影響。由實驗數據可以得出基于用戶的鄰域模型算法精度要略低于基于物品的鄰域模型。另外，從圖中還可以看出，曲線對應幾個特征向量的RMSE下降開始很快，而隨著k值的增加下降速度明顯變緩，這也從側面印證了算法每次計算出的都是最顯著的特征向量。

其次考慮學習速率alpha對算法性能的影響。采用固定隱特征個數k=40，正則化參數lambda為0.025時，算法獲得的預測誤差如表1所示，學習速率alpha從0.004降低到0.000 5的過程中，算法的均方根誤差RMSE從0.923 7降低至0.911 9，但同時迭代次數從47次增加至361次，這表明更小的學習率可以產生更低的預測誤差，但同時算法的收斂速度也變得更慢。如何平衡學習速率和算法效率之間的關系，需要選擇一個合適的速率值。

表1 固定隱特征個數k=40，正則化參數lambda為0.025時算法獲得的預測誤差

最后，在算法性能方面，本文模型需要進行預運算來估計各個參數，而單個評分的實時預測則可在0.1 ms之內完成。與運算耗費時間隨k值增加而上升，每次迭代耗費的運行時間如圖2所示，使用Intel酷睿E2160 CPU，4 GB RAM的普通PC進行運算。

圖2 新模型在不同k值下每次迭代所需時間

運算結果表明，算法在保持較高準確度的前提下，仍具有良好的性能。

4 總結

通過融合顯性反饋和隱性反饋信息改進了推薦算法。實驗數據評估結果表明，本文采用的基于Netflix數據集中的隱性反饋信息在比較有限的情況下，算法的精度仍然得到顯著提高，其性能特性比較適合處理大規模數據集。

[1]Bawden D，Robinson L.The dark side of information：overload，anxiety and other paradoxes and pathologies[J].Journal of Information Science，2009，35（2）：180-191.

[2]Sarwar B，Karypis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th International Conference on World Wide Web，2001：285-295.

[3]Su X，Khoshgoftaar T M.A survey of collaborative filtering techniques[J].Advances in Artificial Intelligence，2009，32（4）：95-101.

[4]Linden G，Smith B，York J.Amazon.com recommen-dations item-to-item collaborative filtering[J].IEEE Internet Computing，2003，7（1）：76-80.

[5]Hoff P D.Multiplicative latent factor models for description and prediction of social networks[J].Computational and Mathematical Organization Theory，2009，15（4）：261-272.

[6]Sarwar B，Karypis G，Konstan J，et al.Item-based collaborative filteringrecommendationalgorithms[C]//Proceedingsofthe 10th International Conference on World Wide Web ACM，2001：285-295.

[7]Dumais S T.Latent semantic analysis[J].Annual Review of Information Science and Technology，2004，38（1）：188-230.

[8]Abdi H，Williams L J，Valentin D，et al.STATIS and DISTATIS：optimum multitable principal component analysis and three way metric multidimensional scaling[J].Wiley Interdisciplinary Reviews：Computational Statistics，2012，4（2）：124-167.

[9]Hu Y，Koren Y，Volinsky C.Collaborative filtering for implicit feedback datasets[C]//Proceedings of the 8th IEEE International Conference on Data Mining（ICDM’08）.[S.l.]：IEEE，2008：263-272.

[10]曾小波，魏祖寬，金在弘.協同過濾系統的矩陣稀疏性問題的研究[J].計算機應用，2010，30（4）：1079-1082.

[11]Su X，Khoshgoftaar T M.A survey of collaborative filtering techniques[J].Advances in Artificial Intelligence，2009（4）.

[12]Koren Y.Factorization meets the neighborhood：a multifaceted collaborativefilteringmodel[C]//Proceedingsofthe14th ACMSIGKDDInternationalConferenceonKnowledge Discovery and Data Mining.[S.l.]：ACM，2008：426-434.

[13]Koren Y，Bell R，Volinsky C.Matrix factorization techniques for recommender systems[J].Computer，2009，42（8）：30-37.

[14]Koren Y.Factor in the neighbors：Scalable and accurate collaborative filtering[J].ACM Transactions on Knowledge Discovery from Data（TKDD），2010，4（1）：1-11.

[15]顧曄，呂紅兵.改進的增量奇異值分解協同過濾算法[J].計算機工程與應用，2011，47（11）：152-154.

LU Quan,WANG Rulong,ZHANG Jin,DING Yi

School of Information Science and Engineering,Hunan University,Changsha 410082,China

As one of the most successful approaches to building recommender systems,Collaborative Filtering（CF）uses the known preferences of a group of users to make recommendations or predictions of the unknown preferences for other users.The two successful approaches to CF are latent factor models,which directly profile both users and products,and neighborhood models, which analyze similarities between products or users.This paper introduces some innovations to both approaches.The factor and neighborhood models can now be smoothly merged,thereby building a more accurate combined model.Further accuracy improvements are achieved by extending the models to exploit both explicit and implicit feedback by the users.The methods are tested on the Netflix data,and the results are better than those previously published on that dataset.

recommender systems;Collaborative Filtering（CF）;latent factor model;Root Mean Square Error（RMSE）

作為目前構建推薦系統最成功的方法之一，協同過濾算法（CF）是利用已知的一組用戶喜好數據來預測用戶對其他物品的喜好從而做出個性化推薦的。兩種比較成功的協同過濾算法能夠直接刻畫用戶和物品因子的隱語義模型，以及分析物品或者用戶之間相似度的鄰域模型。提出了一種針對這兩種模型的改進方法，使得隱語義模型和鄰域模型能夠有效結合，從而構建出一個更精確的融合模型。在融合用戶的顯性反饋與隱性反饋信息對模型進行擴展后，又使得精確度進一步提升。在Netflix數據集上進行測試，實驗結果表明，該融合算法在Netflix數據集上的性能優于其他算法。

推薦系統；協同過濾；隱語義模型；均方根誤差

A

TP391

10.3778/j.issn.1002-8331.1303-0357

LU Quan,WANG Rulong,ZHANG Jin,et al.Recommender algorithm combined with neighborhood model and LFM. Computer Engineering and Applications,2013,49（19）：100-103.

國家科技支撐計劃項目（No.2012BAF12B20）；國家自然科學基金（No.60901080）。

魯權（1986—），男，碩士研究生，研究領域為數據挖掘，機器學習；王如龍（1954—），男，教授，碩士生導師，研究方向為企業信息化，軟件工程，IT項目管理；張錦（1979—），通訊作者，男，博士，副教授，研究方向為軟件工程，IT項目管理，人工智能，服務科學；丁怡（1987—），女，碩士研究生，研究方向為物流信息技術，企業信息化。E-mail：mail_zhangjin@163.com

2013-03-25

2013-05-20

1002-8331（2013）19-0100-04

CNKI出版日期：2013-06-08http://www.cnki.net/kcms/detail/11.2127.TP.20130608.1001.024.html