魯權(quán)，王如龍，張錦，丁怡

湖南大學(xué)信息科學(xué)與工程學(xué)院，長沙 410082

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

魯權(quán)，王如龍，張錦，丁怡

湖南大學(xué)信息科學(xué)與工程學(xué)院，長沙 410082

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，α是學(xué)習(xí)速率（Learning Rate），它的取值需要通過反復(fù)實驗獲得。

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

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

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

將矩陣分解模型融合隱形反饋信息進(jìn)行擴(kuò)展，將評分預(yù)測公式改寫為：

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

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

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

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

3 實驗結(jié)果及評估

3.1 Netflix數(shù)據(jù)集

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

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

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

在對模型進(jìn)行訓(xùn)練之前，將探測集從訓(xùn)練集中剝離，在剩下的數(shù)據(jù)集上訓(xùn)練出來的模型在探測集上進(jìn)行預(yù)測評估。

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

3.2 結(jié)果與討論

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

本文采用alpha=0.007，lambda1=0.005，lambda2=0.015進(jìn)行實驗。在訓(xùn)練集上迭代次數(shù)選用15次。學(xué)習(xí)速率參數(shù)按每次迭代縮減為0.9倍的速度遞減?？刂凄徲蚍秶膮?shù)，即隱特征個數(shù)k，通過實驗證明k值越大，實驗精度越高，因此需要在算法精度與計算代價之間取得平衡。

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

圖1 不同k值各模型在Netflix數(shù)據(jù)集下測試的RMSE值

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

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

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

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

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

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

4 總結(jié)

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

[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]曾小波，魏祖寬，金在弘.協(xié)同過濾系統(tǒng)的矩陣稀疏性問題的研究[J].計算機應(yīng)用，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ìn)的增量奇異值分解協(xié)同過濾算法[J].計算機工程與應(yīng)用，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）

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

推薦系統(tǒng)；協(xié)同過濾；隱語義模型；均方根誤差

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）；國家自然科學(xué)基金（No.60901080）。

魯權(quán)（1986—），男，碩士研究生，研究領(lǐng)域為數(shù)據(jù)挖掘，機器學(xué)習(xí)；王如龍（1954—），男，教授，碩士生導(dǎo)師，研究方向為企業(yè)信息化，軟件工程，IT項目管理；張錦（1979—），通訊作者，男，博士，副教授，研究方向為軟件工程，IT項目管理，人工智能，服務(wù)科學(xué)；丁怡（1987—），女，碩士研究生，研究方向為物流信息技術(shù)，企業(yè)信息化。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