廖天星,王 玲

0 引言

隨著數據信息量的增多,為了幫助用戶快速找到想要的信息,推薦系統(tǒng)作為處理數據過載問題的有效手段應運而生,并且被廣泛地應用在各大個性化網站上,例如亞馬遜網站、豆瓣網站等。在電子商務中,個性化的推薦系統(tǒng)已成為當下最強大和最流行的工具之一,并為商業(yè)帶來了巨大的價值[1]。

在推薦系統(tǒng)中,協(xié)同過濾推薦系統(tǒng)作為一種成功的推薦系統(tǒng)被廣泛地應用[2]。當前,協(xié)同過濾(Collaborative Filtering, CF)推薦算法分為基于記錄(memory-based)的協(xié)同過濾算法[3]和基于模型(model-based)的協(xié)同過濾算法[4],而基于內存的協(xié)同過濾又分為基于用戶的協(xié)同過濾(User-Based Collaborative Filtering, UBCF)和基于項目的協(xié)同過濾(Item-Based Collaborative Filtering, IBCF)[5-6]?，F在主流的基于用戶的協(xié)同過濾算法是K-最近鄰(K-Nearest Neighbors, KNN)算法,它的基本思想是尋找與目標用戶最相近的k個鄰居,使用鄰居的評分來預測目標用戶的評分。基于項目的主流協(xié)同過濾算法是Slope One[7],它的基本思想是分析其他項目與目標項目之間的平均評分差異來預測出目標項目的評分。由于這些推薦算法在預測精度上存在提升的空間，本文提出了高精度M2_KSP算法。該算法將KNN用于用戶的分類方法變?yōu)橛糜陧椖康姆诸惙椒?將針對Slope One算法忽略項目間關聯的問題提出的Slope One加權算法用于設計新的評分預測方法。

M2_KSP算法是一種基于項目的協(xié)同過濾推薦算法,該算法的提出首先是通過對KNN算法的研究,發(fā)現傳統(tǒng)的相似度計算方法如曼哈頓距離、余弦距離等都太過于依賴用戶的評分,忽略了項目屬性[8]的問題,為解決此問題設計了在算法中融入能夠代表項目屬性的標簽[9]來計算項目間相似度的方法,即M2相似性。然后為了降低評分預測時的計算量,設計使用M2相似性來獲得k個鄰近項目。最后在參考Slope One加權算法思想下又設計了新的評分預測方法,并基于這k個鄰近項目用戶的評分預測出目標用戶的評分。M2_KSP算法根據KNN算法和Slope One加權算法的理論思想而設計,結合了這兩個算法各自的優(yōu)點,在減少數據計算量的同時又確保了預測評分方法的簡單性。

為了驗證本文算法的準確度,進行了與基于曼哈頓距離的KNN算法等協(xié)同過濾推薦算法的對比實驗。實驗數據使用了著名的MovieLens數據集,采用Leave-One-Out方法[10]和推薦系統(tǒng)評價指標平均絕對誤差(Mean Absolute Error, MAE)和均方根誤差(Root Mean Square Error, RMSE)來評價算法的性能。實驗結果表明,本文M2_KSP算法具有較高的預測準確度和很好的算法穩(wěn)定性。

1 相關工作

1.1 基于項目的協(xié)同過濾算法

基于項目的協(xié)同過濾(IBCF)算法的運算方式一般為:首先使用Leave-One-Out交叉驗證方法將數據集劃分為訓練集和測試集,然后基于訓練集數據采用相似性度量方法找到目標項目的相似項目,接著利用相似性作為評分預測算法的權重預測出測試集的評分,最后使用推薦算法評價指標評價算法的質量。這種推薦算法的評分預測都是基于用戶評分矩陣的基礎之上,可見用戶的評分矩陣對推薦算法而言比較重要,故本文將所有項目M={m0,m1,…,m(m-1)}所對應的全部用戶U={u0,u1,…,u(n-1)}的評分排列組合成用戶項目評分矩陣R,如式(1)所示：

R:U×M

(1)

為使得表示更加明了,這里將矩陣表示為R=(Ri, j)n×m,Ri, j表示用戶i對項目j的評分。根據項目的評分規(guī)則,有0≤Ri, j≤5,表1是用戶評分矩陣的一個示例。

表1 用戶評分矩陣示例

表1中,M={m0,m1,m2,m3}表示不同的項目,U={u0,u1,u2}表示不同的用戶,Ri, j={2,5,0,3,0,3,2,1,3,4,1,2}。如果Ri, j=0,表示用戶i未對項目j評分。

1.2 KNN算法

對于預測目標用戶的評分,可以通過KNN協(xié)同過濾推薦算法預測該用戶對目標項目的評分。由于KNN算法的理念是以用戶為中心,尋找用戶與用戶之間的距離,根據距離的大小來尋找鄰近的用戶,以鄰近的用戶都會有相近的評分為原理來預測評分,所以KNN算法的核心是定義用戶間相似度。這種方法對用戶進行了分類,使用參數k確定用戶鄰居的數量,通過設置閾值來過濾掉相似度低的用戶,其中為了衡量用戶間相似度,可以使用歐氏距離和余弦距離[11]計算用戶間的距離,距離越近越相似。KNN算法預測評分的計算方法如式(2)所示:

(2)

1.3 Slope One加權算法

用于推薦系統(tǒng)的Slope One算法是基于項目之間相互存在的評分差異,不考慮項目之間的相似性直接根據評分的平均差異來預測用戶的評分。Slope one算法以其簡單性和不錯的推薦質量被普遍地應用,當前一部分人針對Slope One算法忽略項目間的內在關聯[12]提出了一種改進方法,將項目所占的權重引入Slope One算法中,即為Slope One加權算法[13]。在推薦系統(tǒng)中應用該算法預測目標用戶的評分,其計算表達式如式(3)所示:

(3)

2 本文算法

本文M2_KSP算法是一種基于項目的協(xié)同過濾算法,符合一般的基于項目的協(xié)同過濾算法通常的運算方式。該算法首先針對例如傳統(tǒng)曼哈頓距離計算方法完全依賴用戶評分表而忽略項目屬性的問題,重新定義了項目相似度計算方法,提出將項目的標簽融入計算中；然后為了獲得較好的相似度計算效果又提出了通過閾值獲得重要標簽的方法；最后使用該相似度作為算法的權重來更好地預測出用戶的評分。

2.1 項目的標簽

針對大多數推薦算法的相似度計算都是基于用戶的評分而忽略了項目的屬性,本文引入了項目的標簽來定義項目相似度。標簽可以概括性地描述一個項目,相當于使用離散的語言將項目的特點分離出來。本文使用項目的標簽集建立項目標簽矩陣。將項目M={m0,m1,…,m(m-1)}和其所擁有的所有標簽T={t0,t1,…,t(n-1)}排列組合成該項目標簽數量矩陣L,如式(4)所示:

L:T×M

(4)

為使得表示更加明了,這里將矩陣表示為L=(Li, j)n×m,項目j對應標簽i的數量表示為Li, j。表2是項目標簽矩陣的一個示例。

表2 項目標簽數量矩陣示例

如表2所示,M={m0,m1,m2,m3}表示不同的項目,T={t0,t1,t2}表示不同的標簽,Li, j={13,2,0,18,0,16,25,1,21,1,11,1}。如果Li, j=0,表示項目j不含標簽i。

2.2 M2相似性

傳統(tǒng)的相似性計算方法強調根據用戶的評分相似可以發(fā)現用戶間相似的偏好,但是由于忽略了項目的屬性則不能更好地刻畫項目間的相似性,所以本文提出用代表項目屬性的標簽來定義新的項目間相似性計算方法,即M2相似性。M2相似性依據越相似的項目之間總是具有越多相同的特征屬性的理論,這個理論類比于相似的用戶間具有更多相同的偏好,這樣在理論上可以找到相似的項目。依據理論首先將式(4)中每個標簽都看作為物品的一種屬性,那么這里的特征屬性是指項目具有的重要標簽,可以通過設置標簽重要度閾值找到重要標簽。為了衡量項目中每個標簽的重要程度,采用了常用于評估文件中字詞重要性的加權技術,即詞頻-逆文檔頻率(Term Frequency-Inverse Document Frequency, TF-IDF)方法[14],該方法的計算表達式如式(5)所示:

(5)

其中:Wt為目標項目i中標簽t的重要度;Li,t為目標項目i中標簽t的數量;Si為目標項目i中所有標簽的數量總和;I表示整個項目的數量。

為了量化兩個項目間的相似性，本文提出將目標項目所有重要標簽與另一個項目的重要標簽分別對應相乘累和的方法，計算所得值越大相似度越高，反之則越低。M2相似性具體計算過程為首先通過標簽的重要度找到目標項目的重要標簽,然后將目標項目與其他項目按照重要標簽的數量比例對應相乘,同時并乘上該標簽的重要度數值。故本文提出的M2相似性定義方法不同于傳統(tǒng)相似性如曼哈頓距離、余弦距離的計算方法,并且有助于下文提及的評分預測算法更快速地預測出目標用戶的評分。該相似性的計算公式如式(6)所示:

(6)

其中:Mi, j2為目標項目i和其他項目j之間的相似性;q為重要標簽數;Lj,t為其他項目j中標簽t的數量;Sj為其他項目j中所有標簽的數量總和。

2.3 動態(tài)K鄰近項目

參考KNN算法用于預測用戶評分的思想,此處用來尋找k個鄰近的項目,這樣做的好處是使用這k個鄰近項目用戶的評分來預測出目標用戶的評分,可以減少評分預測算法的計算量。首先根據式(6)定義的M2相似性方法計算出項目間的相似性,然后使用Rank排序方法對相似度排序即可找到每個項目M={m0,m1,…,m(m-1)}的前k個最鄰近項目,在表3中列舉了項目m0的兩個鄰近項目。

表3 項目 m0 的兩個鄰近項目示例

如表3所示,k=2,目標項目m0的最鄰近兩個項目為m2、m3。

2.4 評分預測算法

基于這k個鄰近項目的用戶評分,使用參考Slope One加權算法設計的新評分預測算法預測用戶評分的方法本文稱為M2_KSP算法。M2_KSP算法不同于Slope One加權算法,Slope One加權算法采用項目間的加權平均評分差異來預測評分,側重于計算目標項目與單個項目之間加權平均評分的差異；而本文M2_KSP算法則側重于計算目標項目與所有鄰近項目整體的加權平均評分的差異。本文算法的計算過程為：首先計算目標項目平均評分,然后計算出與鄰近項目整體加權平均評分的差值,最后將這個差值加到目標用戶的平均評分上,由此預測出目標用戶的評分。M2_KSP算法的時間復雜度為O(n+m)，相對于Slope One加權算法以及KNN算法的時間復雜度更低,其評分預測方法的表達式如式(7)所示:

(7)

表4 目標項目 m0 的評分矩陣

本文所提出的融合項目標簽相似性的協(xié)同過濾推薦算法(M2_KSP)的運算步驟如下所示：

輸入 標簽矩陣L和評分矩陣R,鄰近項目數k,目標用戶i,目標項目j。

1) 根據式(6)生成項目間的相似性矩陣F;

2) 根據F矩陣形成k個鄰近項目評分矩陣;

3) 初始化csum=0;c=0;sum=0;s=0;bsum=0;b=0;

4) fora=0 ton-1

5)csum+=ra, j;c++;

6)

7) end fora

8) forf=0 tom-1

9)sum+=ri, f;s++;

10)

11) end forf

12) forb=0 tok-1

13) if(ri,b<1E-6)

14) continue;

15) end if

16)

17) end forb

18)

19)

3 實驗與分析

3.1 實驗的數據

本文選擇的是GroupLens Research小組所收集的最新的帶標簽的MovieLens數據集(http://grouplens.org/datasets/movielens/),該數據集含有24 404 096個評分,668 953個標簽和40 110部電影。在本次實驗中,隨機從該數據集中選取了前1 000部電影和與之對應相關的11 102個用戶,7 951個標簽作為實驗的數據來進行實驗。本次實驗數據集的稀疏度為97.65%,實驗數據的用戶評分比例如圖1所示。

圖1 用戶評分比例

3.2 推薦算法評價指標

平均絕對誤差(Mean Absolute Error, MAE)是評價推薦算法質量的標準之一,作為推薦系統(tǒng)的評價指標被廣泛地應用于算法質量的評價[16]。本文使用MAE作為推薦算法準確性的度量,在實驗結果中MAE的值越小表示該算法的平均絕對誤差越小,即該算法的準確度越好。MAE的計算公式如式(8)所示:

(8)

推薦算法的另一個評價指標是均方根誤差(Root Mean Square Error, RMSE)[17]。本文為更準確地衡量該算法的預測效果,也使用了RMSE評價方法來衡量預測值與真實值之間的偏差。RMSE的計算公式如式(9)所示:

(9)

3.3 實驗結果與分析

在實驗過程中,首先使用Leave-One-Out交叉驗證方法將實驗的數據劃分為訓練集和測試集。為了找到最優(yōu)的標簽重要度閾值a,進行了閾值a在不同取值時對算法的準確度所造成影響的實驗,實驗結果如圖2所示。接著通過設置最優(yōu)閾值a獲得項目的重要標簽并且使用重要標簽的數量計算項目間相似度。然后,對相似度進行rank排序獲得目標項目的k個鄰近項目。最后,基于這k個鄰近項目的評分,使用新定義計算目標項目與整個鄰近項目的平均評分差異的方法預測用戶的評分。同時,為了比較該算法的預測性能,在相同的數據集上將本文提出的M2_KSP算法與其他推薦算法進行實驗。

對比算法包括：基于曼哈頓距離的KNN算法(稱為M_KNN)、使用M2相似性作為權重的Slope One加權算法(稱為M2_Slope One算法)，以及本文M2_KSP算法。M_KNN算法是使用曼哈頓距離計算相似度的KNN協(xié)同過濾推薦算法,M2_Slope One是一種使用M2相似性的Slope One加權協(xié)同過濾推薦算法,這些算法都是比較流行的協(xié)同過濾推薦算法。

在M2_KSP算法中通過設置閾值a來找到項目的重要標簽，具體方法為判斷項目的標簽重要度是否大于a,若是則表明該標簽為重要標簽。閾值選取越合理越能獲得真正重要的標簽。本文為了設置最佳閾值a進行了相關實驗,結果如圖2所示a的取值為每個標簽的權重在項目標簽權重總值中所占的比例,隨著k值的變化在a的取值從大到小的過程中,所取得的算法的平均絕對誤差值形成折線變化趨勢，且每條折線間的距離越來越靠近,當a的取值分別為0.001、0.000 5、0.000 3時這三條折線幾乎完全重合，可學習到該算法最佳的閾值范圍為0.000 3～0.001,算法的閾值設置在這個范圍內更加合理，故本文算法的最優(yōu)閾值a取值為0.000 5。

圖2 在閾值a影響下算法的平均絕對誤差

算法MAERMSEM_KNN0.7640.974M2_SlopeOne0.7270.952M2_KSP0.6880.903

由圖3和表5可知，在MAE評價標準下,隨著k的不同取值,本文提出的基于a的最優(yōu)閾值M2_KSP算法取得的最小誤差明顯比M_KNN算法的最小誤差值小很多,即M2_KSP算法的準確度明顯高于M_KNN算法,同理也略高于M2_Slope One算法。通過圖3的實驗結果表明,M2_KSP算法是一種預測準確度較好的協(xié)同過濾推薦算法。

圖3 不同算法的平均絕對誤差對比(k取10～100)

由圖4和表5可知：本文M2_KSP算法在RMSE評價標準中相對于M_KNN算法同樣具有一個相對較低的誤差值，并且在k取值大于30時，M2_KSP算法的誤差值低于M2_Slope One算法,由此再次驗證了M2_KSP算法預測精度好于M_KNN算法,同時也略優(yōu)于M2_Slope One算法。再結合圖3的實驗結果綜合得出,本文提出的M2_KSP協(xié)同過濾算法的推薦準確度是更加精準的,推薦的質量也是更加優(yōu)秀的。

圖4 不同算法的均方根誤差對比

為了觀測M2_KSP算法的穩(wěn)定性,進行了加大k取值范圍的實驗，實驗結果如圖5所示。

圖5 不同算法的平均絕對誤差對比(k取100～900)

從圖5中三種算法的誤差對比分析可知：在相同數據集下M2_KSP算法在不同的k值下的平均絕對誤差值的變化最小，并且穩(wěn)定在最小的誤差值范圍內；但是M2Slope One算法取得的MAE值變化幅度則更大、穩(wěn)定性更差；M_KNN算法取得的MAE值變化幅度最大且波動在最大的誤差值范圍內、穩(wěn)定性最差。所以本文提出的M2_KSP算法相比而言具有更好的穩(wěn)定性。綜上所述,M2_KSP算法無論是在MAE評價標準下還是在RMSE評價標準下都表現出更精確的預測評分準確度、更好的推薦質量、更優(yōu)秀的算法穩(wěn)定性,故本文提出的M2_KSP算法是一種可行有效的、具有更高準確性和更好穩(wěn)定性的協(xié)同過濾推薦算法。

4 結語

本文參考KNN算法的思想，首先依據重要標簽數量定義了項目間M2相似性,該相似性旨在尋找目標項目最鄰近的k個項目。然后基于這k個鄰近項目用戶的評分,并通過對Slope One加權算法的研究設計了M2_KSP評分預測算法。本文算法依據KNN算法思想和Slope One加權算法理論設計而成,故具有一定的理論依據,同時也結合了這兩個推薦算法各自的優(yōu)點,在減少算法計算量的同時又保證了算法的簡單性。實驗結果表明，本文算法表現出了更好的準確性,符合預期的猜想，并且還具有很好的穩(wěn)定性。總而言之,本文算法具有更精確的準確度、更優(yōu)秀的推薦質量和良好的穩(wěn)定性。從圖3～4中可知隨著k值變大,算法的誤差率逐漸降低，即評分數據量越多算法的預測準確度越高,而目前用戶評分矩陣比較稀疏,計劃未來在減小評分矩陣的稀疏度上能提出好的方案。

由于本文算法是采用Leave-One-Out交叉驗證方法,該方法在數據的樣本數量較大時需要消耗的時間較多,未來為了更好地實現實時的推薦可以考慮采用并行化計算方法來減少計算所需的時間。

參考文獻(References)

[1] RICCI F, ROKACH L, SHAPIRA B. Recommender systems: introduction and challenges[M]// RICCI F, ROKACH L, SHAPIRA B. Recommender Systems Handbook. Berlin: Springer, 2015: 1-34.

[2] BOBADILLA J, ORTEGA F, HERNANDO A, et al. Recommender systems survey[J]. Knowledge-Based Systems, 2013, 46: 109-132.

[3] JEONG B, LEE J, CHO H. Improving memory-based collaborative filtering via similarity updating and prediction modulation[J]. Information Sciences, 2010, 180(5): 602-612.

[4] ZHANG H R, MIN F, WANG S S. A random forest approach to model-based recommendation[J]. Journal of Information and Computational Science, 2014, 11(15): 5341-5348.

[5] Lü L, MEDO M, CHI H Y, et al. Recommender systems[J]. Physics Reports, 2012, 519(1): 1-49.

[6] PIRASTEH P, JUNG J J, HWANG D. Item-based collaborative filtering with attribute correlation: a case study on movie recommendation[C]// ACIIDS 2014: Proceedings of the 6th Asian Conference on Intelligent Information and Database Systems. Berlin: Springer, 2014: 245-252.

[7] BASU A, VAIDYA J, KIKUCHI H. Perturbation based privacy preserving slope one predictors for collaborative filtering[C]// IFIPTM 2012: Proceedings of the 6th IFIP WG 11.11 International Conference on Trust Management VI. Berlin: Springer, 2017, 374: 17-35.

[8] KIM H N, JI A T, HA I, et al. Collaborative filtering based on collaborative tagging for enhancing the quality of recommendation[J]. Electronic Commerce Research and Applications, 2010, 9(1): 73-83.

[9] PITSILIS G, WANG W. Harnessing the power of social bookmarking for improving tag-based recommendations [J]. Computers in Human Behavior, 2015, 50: 239-251.

[10] CAWLEY G C. Leave-one-out cross-validation based model selection criteria for weighted LS-SVMs[C]// IJCNN 2006: Proceedings of the 2006 International Joint Conference on Neural Networks. Piscataway, NJ: IEEE, 2006: 1661-1668.

[11] ZHENG M, MIN F, ZHANG H R, et al. Fast recommendations with the M-distance[J]. IEEE Access, 2016, 4: 1464-1468.

[12] 李淋淋,倪建成,于蘋蘋, 等. 基于聚類和Spark框架的加權Slope One算法[J]. 計算機應用, 2017, 37(5): 1287-1291, 1310.(LI L L, NI J C, YU P P, et al. Weighted Slope One algorithm based on clustering and Spark framework[J]. Journal of Computer Applications, 2017, 37(5): 1287-1291, 1310.)

[13] TIAN S, OU L. An improved slope one algorithm combining KNN method weighted by user similarity[C]// WAIM 2016: Proceedings of the 2016 International Conference on Web-Age Information Management. Berlin: Springer, 2016: 88-98.

[14] 李鎮(zhèn)君, 周竹榮. 基于Document Triage的TF-IDF算法的改進[J]. 計算機應用, 2015, 35(12): 3506-3510, 3514.(LI Z J, ZHOU Z R. Improvement of term frequency-inverse document frequency algorithm based on Document Triage[J]. Journal of Computer Applications, 2015, 35(12): 3506-3510, 3514.)

[15] ANIDORIFON L, SANTOSGAGO J, CAEIRORODRIGUEZ M, et al. Recommender systems[J]. Communications of the ACM, 2015, 40(3): 56-58.

[16] CREMONESI P, GARZOTTO F, NEGRO S, et al. Looking for “Good” recommendations: a comparative evaluation of recommender systems[C]// INTERACT 2011: Proceedings of the 13th IFIP TC 13 International Conference on Human-Computer Interaction, LNCS 6948. Berlin: Springer, 2017: 152-168.

This work is partially supported by the National Natural Science Foundation of China (41674141).