程 飛，賈彩燕

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044）

1 引言

目前，很多大型的電子商務(wù)網(wǎng)站為了獲得更好的經(jīng)濟(jì)效益，通常會(huì)給用戶推薦合適的資源，以提高用戶的使用滿意度，如Amazon、Ebay、Alibaba、Yahoo等網(wǎng)站都使用了各種形式的推薦系統(tǒng)。在一些商業(yè)公司的贊助下，許多計(jì)算機(jī)研究機(jī)構(gòu)也舉辦了一些相關(guān)的競賽，如ACM KDD CUP 2011 Contest、Netflix Prize Competition（2009 年）等。隨著用戶數(shù)量、用戶信息量、網(wǎng)絡(luò)資源數(shù)量的增多，推薦系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)面臨更大的挑戰(zhàn)[1]。

為了實(shí)現(xiàn)推薦的功能，系統(tǒng)需要根據(jù)已有用戶對資源的評價(jià)，來預(yù)測用戶對未評價(jià)資源的喜愛程度。目前主要有兩類方法來解決這樣的問題：基于鄰居[2，3]（Neighborhood Approach）的方法和基于潛在因子模型[4～6]（Latent Factor Models）的方法。

基于鄰居的方法比較直觀，容易理解。這類方法使用統(tǒng)計(jì)技術(shù)尋找與目標(biāo)用戶有相同或相似興趣偏好的鄰居，根據(jù)鄰居用戶的評分來預(yù)測目標(biāo)用戶對資源的評分值，選取預(yù)測評分最高的前N 個(gè)資源作為推薦集反饋給目標(biāo)用戶。它的中心思想是有相同興趣或偏好的用戶往往會(huì)對同樣的資源感興趣，這也非常符合人們的心理。這類方法的核心是要準(zhǔn)確計(jì)算目標(biāo)用戶的鄰居，也就是用戶相似性，所以也稱為基于用戶（User-Based）的協(xié)同過濾方法。類似地，可以考慮資源之間的相似性，使用目標(biāo)用戶評價(jià)過的資源集合來預(yù)測用戶可能感興趣的其它資源，這類方法稱為基于資源（Item-Based）的協(xié)同過濾方法。

基于潛在因子模型的方法將用戶和資源的特征同時(shí)映射到相同的潛在因子空間（Latent Factor Space），以使得它們可以直接比較。這類方法假設(shè)用戶對資源的評分是多項(xiàng)特征的加權(quán)和。例如，當(dāng)評價(jià)的資源是電影時(shí)，特征可以是電影的分類，是喜劇或是文藝劇；也可以是電影所適合的觀眾級別，兒童電影或是大眾電影等。但是，在這類模型中，這樣的特征并非都是可解釋的，也就是說特征不是人為指定的，而是通過機(jī)器學(xué)習(xí)的方法所得到的潛在特征。這類方法中，比較典型的算法有MFITR[7]、SVD[8]、SVD＋＋[9]等。

鄰居模型的方法有效地計(jì)算局部的近鄰關(guān)系，用與目標(biāo)用戶最相近的鄰居的行為來估計(jì)預(yù)測用戶的行為，計(jì)算復(fù)雜度低，直觀易理解，能較好地反映用戶行為。但是，它沒有考慮到全局的用戶關(guān)系，效果往往不如因子分解模型好。本文提出一種改進(jìn)的相似性度量方法，更好地體現(xiàn)用戶之間的關(guān)系，以減小評分的誤差，提高推薦的精度。

2 基于用戶的協(xié)同過濾推薦算法

Sarwar[10，11]等人將基于用戶的協(xié)同過濾推薦算法分為三個(gè)階段：表示（Representation）、鄰居用戶形成（Neighborhood Formation）和推薦生成（Recommendation Generation）。

2.1 表示

協(xié)同過濾算法通常采用用戶-項(xiàng)目評分矩陣R（m，n）表示用戶評分信息，如表1所示。R（m，n）是一個(gè)m×n階矩陣，其中，m 行表示m 個(gè)用戶，n列表示n個(gè)資源，Rij表示用戶i 對資源j 的評分值。用戶對資源的評分可以采用二進(jìn)制，例如1表示喜歡，0表示不喜歡。同樣可以是5分制、10分制或其他度量方式的評分，評分的高低代表用戶對資源的喜愛程度的高低。表1是用戶對資源的評分矩陣。

Table 1 User-item score matrix R（m，n）表1 用戶-資源評分矩陣R（m，n）

2.2 鄰居用戶形成

鄰居用戶的形成是基于用戶的協(xié)同過濾推薦算法中最為關(guān)鍵的步驟。對于目標(biāo)用戶u，我們需要搜索出與它最相近的用戶集合U＝｛u1，u2，…，uk，…，uk｝，u?U 且u與U 中用戶uk之間的相似性sim（u，uk）（1≤k≤K）由大到小排序。

用戶相似性度量[12]方法主要有余弦相似性[13]（Cosine Similarity）和皮爾遜相關(guān)系數(shù)[13]（Pearson Correlation Coefficient）等。

（1）余弦相似性。

其中，Iuv＝ ｛i∈I｜Rui≠?and Rvi≠?｝（I表示全部項(xiàng)目空間）表示用戶u、v 的共同評分資源集合，向量u、v分別表示用戶u、v在Iuv上的評分，Rui、Rvi分別表示用戶u、v對資源i的評分。

（2）皮爾遜相關(guān)系數(shù)。

2.3 推薦生成

其中，Iu＝｛j∈I｜Ruj≠?｝。

此時(shí)，給目標(biāo)用戶u 推薦資源時(shí)，可以按照它對資源評分的高低排序，推薦前N 個(gè)資源，即top-N 推薦，這就完成了整個(gè)推薦過程。

3 改進(jìn)的用戶相似性度量方法

使用余弦相似性和皮爾遜相關(guān)系數(shù)的相似性計(jì)算兩個(gè)用戶之間相似性時(shí)，都是先尋找兩個(gè)用戶共同評分的項(xiàng)集，而忽略了用戶未評分的項(xiàng)集，這樣就容易導(dǎo)致尋找到的用戶鄰居不夠準(zhǔn)確，尤其是在評分?jǐn)?shù)據(jù)稀疏的情況下。本文根據(jù)Jaccard相似性的思想，提出一種改進(jìn)的用戶相似性度量方法。

其中，｜Iu∩Iv｜表示用戶u和用戶v 都評價(jià)過的資源的個(gè)數(shù)，｜Iu∪Iv｜表示用戶u和用戶v 評價(jià)的資源并集的個(gè)數(shù)。式（4）考慮了用戶評價(jià)資源對相似性的影響，但未考慮到用戶對資源的評分值，也就是說只要用戶對資源評分，不管分值的高低，對相似度的計(jì)算都無影響。故對式（4）進(jìn)一步改進(jìn)，提出加權(quán)的Jaccard相似性方法。

又考慮到用戶之間存在差異性，每個(gè)用戶有自己的評價(jià)標(biāo)準(zhǔn)，有的用戶評分普遍較高，而有的用戶評分普遍較低。因此，在計(jì)算相似性時(shí)，對式（5）中的分子做進(jìn)一步調(diào)整：

4 實(shí)驗(yàn)結(jié)果

4.1 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)取自于英國Glosgow 大學(xué)計(jì)算機(jī)系從last.fm 網(wǎng)站（www.last.fm）搜集的數(shù)據(jù)，稱為Last.FM 數(shù)據(jù)集。該網(wǎng)站是一個(gè)提供音樂點(diǎn)播的網(wǎng)站，有非常大的用戶群體。該數(shù)據(jù)集包含3 148個(gè)用戶對30 520首音樂的點(diǎn)擊次數(shù)，每個(gè)用戶平均點(diǎn)擊超過200首音樂。用戶對音樂的點(diǎn)擊次數(shù)可以看作為用戶對音樂的喜愛程度，即點(diǎn)擊次數(shù)越高，音樂受喜愛程度越高。對Last.FM 數(shù)據(jù)集，隨機(jī)抽取1／6的數(shù)據(jù)作為測試數(shù)據(jù)，其余的作為訓(xùn)練數(shù)據(jù)。

4.2 評分?jǐn)?shù)據(jù)標(biāo)準(zhǔn)化

由于不同用戶對音樂點(diǎn)擊次數(shù)的差距較大，直接采用點(diǎn)擊次數(shù)作為對音樂的評分會(huì)產(chǎn)生較大誤差，故采用標(biāo)準(zhǔn)化的方法將評分范圍設(shè)定為0 至100分。考慮到用戶的差異性，即有些用戶點(diǎn)擊音樂的次數(shù)普遍比較高，而有些則正好相反。舉例而言，假如用戶u1酷愛音樂，他點(diǎn)擊同一首音樂的平均次數(shù)在200左右，而用戶u2收聽音樂的時(shí)間相對較少，點(diǎn)擊同一首音樂的平均次數(shù)在20次左右。那么，可以認(rèn)為用戶u1收聽200次音樂和用戶u2收聽20次音樂的喜愛程度相仿。本文按式（7）所示方法標(biāo)準(zhǔn)化評分?jǐn)?shù)據(jù)：

4.3 評價(jià)指標(biāo)

本文采用兩種指標(biāo)來評價(jià)實(shí)驗(yàn)結(jié)果：均方根誤差RMSE[9]（Root Mean Squared Error）和推薦精度（Precision＠N[14]）。

均方根誤差通過計(jì)算預(yù)測用戶評分與實(shí)際用戶評分之間的偏差來度量預(yù)測的精確度，RMSE越小，推薦的質(zhì)量就越高。

其中，Precision＠N 表示對于目標(biāo)用戶，推薦給用戶的資源集合，Data（test）表示測試集中實(shí)際應(yīng)該推薦給用戶的資源集合。這種評價(jià)方法反映了推薦的精度，值越大，精度越高，推薦的質(zhì)量就越好。

4.4 實(shí)驗(yàn)結(jié)果

我們分別實(shí)現(xiàn)了SVD＋＋算法和兩種基于用戶的協(xié)同過濾算法，用戶相似性分別使用式（2）和式（6）來度量。

基于用戶的協(xié)同過濾算法中，鄰居數(shù)目的選取通常會(huì)影響計(jì)算結(jié)果，鄰居數(shù)目越多，精度越高，但一般不應(yīng)超過用戶評價(jià)資源的平均數(shù)?；谟脩舻膮f(xié)同過濾算法中，各算法的RMSE 比較結(jié)果如圖1所示。

Figure 1 RMSEof two algorithms based on user similarity圖1 兩種基于用戶相似性算法的RMSE 比較

SVD＋＋算法的RMSE 為16.15。容易看出，改進(jìn)算法的預(yù)測誤差低于其它兩種算法。SVD＋＋算法的參數(shù)過多，調(diào)整較為困難，需要花費(fèi)大量時(shí)間，而且一旦訓(xùn)練數(shù)據(jù)集發(fā)生變化，參數(shù)就需要重新調(diào)整。SVD＋＋算法使用隨機(jī)梯度下降的方法來訓(xùn)練模型，梯度大小的選擇會(huì)對結(jié)果造成影響：梯度選擇過大，學(xué)習(xí)的精度不夠，預(yù)測的結(jié)果會(huì)不理想，梯度選擇過小，又很容易造成“過學(xué)習(xí)”的情況，而且訓(xùn)練的次數(shù)也會(huì)明顯增多，用時(shí)明顯增加?；谟脩舻膮f(xié)同過濾算法則無需考慮參數(shù)的調(diào)整，實(shí)現(xiàn)較為容易。就時(shí)間開銷而言，本文中改進(jìn)的用戶相似性算法考慮了用戶未評分?jǐn)?shù)據(jù)，故相比皮爾遜相似性方法計(jì)算時(shí)間會(huì)有所增長。實(shí)驗(yàn)結(jié)果表明，使用皮爾遜相關(guān)系數(shù)和本文改進(jìn)方法計(jì)算用戶相似性的總耗時(shí)分別為39分鐘和55分鐘。可見，時(shí)間開銷的增長并不是很大，仍在可接受的范圍之內(nèi)。本文合理地改進(jìn)了相似性的度量方法，使傳統(tǒng)的基于用戶的協(xié)同過濾算法也能有較低的預(yù)測誤差。

各算法的精度比較結(jié)果如圖2 所示。從圖2可以看出，在對前15個(gè)資源（Precision＠15）以及前20個(gè)資源（Precision＠20）的推薦精度上，改進(jìn)的算法與其它兩種算法相比，推薦精度差別不大。但是，在對前5個(gè)資源（Precision＠5）以及前10個(gè)資源（Precision＠10）的推薦精度上，改進(jìn)算法明顯好于另兩種算法。在實(shí)際應(yīng)用中，用戶往往會(huì)關(guān)注最優(yōu)先推薦的資源，而不一定會(huì)注意到所有的資源。因此，這種推薦精度的提高，對于實(shí)際應(yīng)用更有價(jià)值。

Figure 2 Precision comparison of three algorithms圖2 各算法的推薦精度對比

5 結(jié)束語

基于潛在因子模型的算法體現(xiàn)了全局的評分效果，忽視了局部的特征。傳統(tǒng)的基于鄰居的算法更多體現(xiàn)了用戶的局部特征，更為直觀和簡單易行，但精度有待提高。前者參數(shù)過多，需要反復(fù)調(diào)整，一旦有新的用戶（或資源）加入，就需要重新訓(xùn)練整個(gè)模型，不便于增量式學(xué)習(xí)。而后者只需計(jì)算新增用戶（或資源）與其它用戶（或資源）之間的相似性就可完成增量學(xué)習(xí)。本文中的方法在傳統(tǒng)的基于用戶的協(xié)同過濾算法基礎(chǔ)上，改進(jìn)了用戶相似性的度量方法，實(shí)現(xiàn)了用戶對資源評價(jià)的預(yù)測。改進(jìn)的用戶相似性度量方法考慮了用戶差異等行為特點(diǎn)，避免了基于潛在因子模型算法的模型復(fù)雜、參數(shù)不易學(xué)習(xí)等缺點(diǎn)；同時(shí)，相比傳統(tǒng)的基于鄰居的方法，改進(jìn)后的方法在一定程度上提高了推薦質(zhì)量，有較好的實(shí)際應(yīng)用價(jià)值。

[1]Schafer J B，Konstan J A，Riedl J.E-commerce recommendation applications[J].Data Mining and Knowledge Discovery，2001，5（1-2）：115-153.

[2]Karypis G.Evaluation of item-based top-N recommendation algorithms[C]∥Proc of the 10th International Conference on Information and Knowledge Management，2001：247-254.

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

[4]Zhou Yun-hong，Wilkinson D，Schreiber R，et al.Large-scale parallel collaborative filtering for the netflix prize[C]∥Proc of the 4th International Conference on Algorithmic Aspects in Information and Management，2008：337-348.

[5]Agarwal D，Chen Bee-chung，Pang Bo-pang.Personalized recommendation of user comments via factor models[C]∥Proc of 2011 Conference on Empirical Methods in Natural Language Processing，2011：571-582.

[6]Koren Y，Sill J.OrdRec：An ordinal model for predicting personalized item rating distributions[C]∥Proc of the 5th ACM Conference on Recommender Systems，2011：117-124.

[7]Wu Yao，Yan Qiang，Bickson D，et al.Efficient multicore collaborative filtering[C]∥Proc of KDD-Cup Workshop，2011：1.

[8]Takács G，Pilász I，Németh B，et al.Matrix factorization and neighbor based algorithms for the netflix prize problem[C]∥Proc of 2008 ACM Conference on Recommender Systems，2008：267-274.

[9]Koren Y.Factorization meets the neighborhood：A multifaceted collaborative filtering model[C]∥Proc of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2008：426-434.

[10]Sarwar B.Sparsity，scalability，and distribution in recommender systems[D].Minneapolis：University of Minnesota，2001.

[11]Sarwar B，Karypis G，Konstan O，et al.Analysis of recommendation algorithms for e-commerce[C]∥Proc of the 2nd ACM Conference on Electronic Commerce，2000：158-167.

[12]Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems：A survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering，2005，17（6）：734-749.

[13]Ahn Hyung-Jun.A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem[J].Information Sciences，2008，178（1）：37-51.

[14]Xu Guan-dong，Gu Yan-hui，Zhang Yan-chun，et al.TOAST：A topic-oriented tag-based recommender system[C]∥Proc of the 12th International Conference on Web Information System Engineering，2011：158-171.