用余弦相似度修正評分的協同過濾推薦算法*

張瑞典，錢曉東

(蘭州交通大學經濟管理學院，甘肅 蘭州 730070)

1 引言

在互聯網高速發展的時代，信息處于一個爆炸增長的狀態，為緩解信息過載問題，互聯網會為用戶推薦各種信息，比如淘寶商品，今日頭條的新聞，愛奇藝的電影電視等等。由于信息量太大，需要針對不同用戶選擇其需要或者感興趣的項目進行推薦，既不會使用戶厭煩，又可高效地為用戶推薦有用的項目。

根據評分計算用戶相似性[1]，并依據相似性進行項目推薦[2]是目前常用的協同過濾推薦[3]手段。而在評分時，由于某些不合理因素可能導致少量用戶對項目做出與自身意志不相符的評分，比如因一時情緒導致評分的極端化，這類評分會使相似度計算出現較大偏差，從而引起推薦結果出現明顯誤差。

事實上，用戶的評分是由用戶的多種有關評分特征最終決定的，就是說如果影響某用戶對某項目評分的所有相關信息一定，那么該用戶對該項目的評分就如同基因決定生物性狀一樣確定。然而，由于無法全面收集用戶有關評分的特征信息，因此在實際操作中，都是依據同一用戶對大量不同項目所做評分來衡量其評分特征，以不同用戶對同一組(多個)項目做出的評分來衡量相互之間的相似度。但是，評分是離散數據，不能準確反映用戶的特征和不同用戶間的相似度，因此需要結合用戶具體的特征，以達到提高反映準確度的目的。這種將評分與多種特征相結合的方法，可在一定程度上修正不合理評分帶來的相似度偏差，這也是大多數文獻所采用的方法。比如，文獻[4]利用用戶文本評論特征來修正可信度不高的評分數據，并將其與用戶偏好相結合來增加評分的可信度與區分度；文獻[5]采用多層次的推薦策略，將用戶的評分相似度[6]、興趣相似度[7]、特征相似度[5]進行動態融合，來挖掘目標用戶的相似用戶集合。這2種方法都能削弱不合理評分對用戶相似度計算的影響，但效果均不明顯。

為了更大程度地減小不合理評分帶來的影響，本文采用評分矩陣的多種維度進行余弦相似度[8]比較的方法修正不合理評分。用不同用戶對高相似度的多個項目所做評分構成的評分向量計算余弦相似度，首先將評分向量按元素個數均分為多組，分別求取對應的余弦相似度，如果某組余弦相似度過小，表明該組存在不合理評分，再對帶不合理評分的數組進行降維分組，如此往復，最終可確定不合理評分；再對第1次分組的不帶不合理評分的各組余弦相似度求取平均值，將其作為帶不合理評分數組的余弦相似度，從而計算出1個評分來取代所確定的不合理評分。

修正評分后，結合皮爾遜相似度[9]、模糊偏好相似度[10]和Jaccard相似度[11]計算用戶相似度，以推薦評分[12]與實際評分間的平均絕對偏差(MAE)[13]、準確率(Precision)[9]和覆蓋率(Coverage)[14]來衡量推薦性能。利用MovieLens數據庫[15]和Bookcrossing[16]數據庫進行實驗，結果表明：用余弦相似度修正評分的協同過濾算法相比未修正評分前的算法具有更高的推薦精度，其推薦評分MAE明顯下降。此外，本文算法與對照算法在MAE、Precision、Coverage指標上的仿真實驗均表明，本文算法具有更好的推薦效果。

2 評分修正可行性分析及修正方案

2.1 相似項目評分的余弦相似度的分析

若存在A1，A2，…，AT共T個用戶，分別對2個項目C1和C2做出評分。表1所示為對應評分情況，rtd表示At對Cd做出的評分。

Table 1 T users’ ratings for 2 items表1 T個用戶對2個項目的評分

如果C1和C2的理想相似度高，則兩者的余弦相似度高：

(1)

事實上，sim(C1,C2)cos≤1，當且僅當rt1∝rt2時取等號。設l為比例系數，則在式(1)成立的情況下，有rt2≈lrt1成立。

綜上所述，同一用戶對相似項目的評分大約成正比。

求第e個用戶和第f個用戶相似度：

(2)

而當re2≈lre1，rf2≈lrf1時則有：

(3)

因此，不同用戶對相似度高的項目所做評分的余弦相似度也高。顯然，當被評分的相似項目數大于2時，依然符合此規律。

2.2 不合理評分的確定

若存在2個用戶A和B，他們均對相同的項目組做了評分，且在這些項目組中存在各類相似項目，抽取某類高相似度鄰居項目N(N為小于或等于該類相似項目所有個數的最大可被10 整除的數，以便多次分組)個，即A的評分向量為RA=(rA1,rA2,…，rAN)，B的評分向量為RB=(rB1,rB2,…，rBN),將這N個項目分為n組，每組m個分數，則有：

N=mn

(4)

規定A和B的第n組的評分向量為：

(5)

單獨計算每組相似度，由于所有項目相似度較高，在合理情況下，根據式(3)的結論有：

(6)

如果某組出現了不合理評分，則該組與其它組的相似度會出現較大的差異，其余弦相似度則會遠小于1。為了給出更具體的判斷標準，人為設定Δsim(A,B)cos，如果：

(7)

則認為RAn或RBn中存在不合理評分;否則,均不存在。

為了在A，B的評分向量中找出不合理評分，需要在不同維度下計算A，B間的余弦相似度。

首先，分別在A,B的各組評分向量中自行對比相似度，以確定不合理評分出現在哪個用戶的評分向量中。假設第x組評分向量的相似度低于下限，選擇余弦相似度最大的1組(設為第y組)評分向量，如果：

(8)

則認為A的第x組存在不合理評分。如果：

(9)

則認為B的第x組存在不合理評分。

然后，將帶有不合理評分的向量和另外1個用戶對應序號的評分向量提取出來繼續分組。將第x組分為s組，每組q個分數，則有：

m=sq

(10)

又規定A和B第x組再分組的第s組的評分向量為：

(11)

單獨計算每組相似度，重復式(6)～式(12)的操作，直到所提取到的評分向量元素個數為質數。每次分組降維后，需要與分組前的相似度對比正常相似度，因為正常情況下應該有：

(12)

且均應在[1-Δsim(A,B)cos,1]。需要注意的是，所分組數與每組元素個數之間的數值差盡可能小，既保證高維向量計算相似度的準確性，又保證有足夠的組進行對比。

最后，將質數個元素的評分向量分為每2個元素1組，且前組的第2個元素作為后1個組的第1個元素。若哪組包含不合理評分，則對應組的相似度與最后1次分組前的相似度相差較大。比如，rAz為不合理評分，則：

(13)

至此，不合理評分已被確定。

2.3 不合理評分的修正

(14)

其中，i為第i組分組。

不合理評分的修正可以推廣到多個不合理評分的修正。即求所有合理評分向量的相似度均值，并將其作為不合理評分向量的相似度，最終按余弦相似度計算的逆過程修正所有不合理評分。另外，式(8)和式(9)中所描述的判定方法只能判定出與合理評分相差最大的不合理評分，并不能說明另1個用戶未做出不合理評分，因此確定不合理評分并修正后，需要將2個評分向量重復式(4)～式(14)的步驟，才能確定并修正2個用戶的不合理評分。

3 基于評分矩陣修正的協同過濾推薦

采用第2節中所述的方法將所有不合理評分修正一遍后，再利用修正后的評分矩陣計算用戶相似度。假設有u個用戶對v個項目做出了評分，評分矩陣表示為Ruv，rjk表示第j個用戶對第k個項目做出的評分。如果未評分，則將對應的評分記為0。

(15)

本文以模糊化的混合評分相似度作為用戶評分的相似度，以此來衡量不同用戶的相似度。此相似度為3部分的乘積：皮爾遜相似度×平均模糊偏好相似度×Jaccard相似度。第j個用戶Aj和第h個用戶Ah的皮爾遜相似度為[12]：

(16)

定義1設U為一論域，給定1個映射μE:U→[0,1],x→μE(x)∈[0,1]，可確定1個模糊集E，映射μE稱為模糊集E的隸屬函數，μE(x)稱為x對E的隸屬度。

評分模糊化隸屬函數如圖1所示。其定義式為：

(17)

Figure 1 Fuzzy membership function of rating圖1 評分模糊隸屬函數

根據式(17)，可求出某用戶對某項目的模糊偏好向量θ=(μlike,μdislike)。利用模糊偏好計算不同用戶間的偏好相似度，用ps(Aj,Ah)表示用戶Aj和用戶Ah間的平均偏好相似度[17,18]：

(18)

(19)

dis(θjc-θhc)=

(20)

Jaccard相似度定義為2個集合的交集與并集的比。已知用戶Aj的評分項目集合Ij和用戶Ah的評分項目集合Ih，則用戶Aj，Ah的Jaccard相似度為[19]：

(21)

所以，用戶Aj，Ah的評分相似度為：

sim(Aj,Ah)=simpcc(Aj,Ah)×

ps(Aj,Ah)×J(Aj,Ah)

(22)

為某目標用戶推薦項目，先根據用戶的相似度，尋找到目標用戶在某一范圍內的鄰居，然后基于評分的預測公式計算出該目標用戶的推薦評分，然后依據推薦評分決定是否為用戶推薦某項目，或決定推薦某類項目的概率。選定某一目標用戶，選出與其相似度較大的固定數量用戶構成最近鄰居集合L。最近鄰居為用戶Aj關于項目Ck所推薦的評分為[20]：

(23)

4 算法步驟

為了明確基于變維相似度修正評分的協同過濾推薦算法的實現過程，給出相應的算法步驟。該算法步驟主要由2個部分組成：不合理評分確定和修正過程，相似度計算與評分推薦過程。

步驟1不合理評分確定和修正過程

輸入：RA,RB。

輸出：修正評分。

begin

1.functionPartition(RA,RB)

2. 提取RA的維數N;

3.forn← 0toNstep 1do

4.form← 0tonstep 1do

5.ifN=mnthen

6.sum[n][m] ←m+n;/*sum[n][m]為m與n的和*/

7.endif

8.endfor

9.endfor

10.ifsum[n][m] = min(sum[n][m])then/*min(sum[n][m])為sum[n][m]的最小值*/

11.RA=[RA1,RA2,…,RAn];//將RA分為n組

12.RB=[RB1,RB2,…,RBn];//將RB分為n組

13.endif

14.fori← 1tonstep 1do

15.sim(Ai,Bi)cos← cos(RAi,RBi);

16.ifsim(Ai,Bi)cos≥ 1-Δsim(Ai,Bi)costhen

17. 不做處理;

18.else

19. 按式(8)和式(9)的方法確定不合理評分所在數組;

20.RAx←RAi;

21.RBx←RBi;

22.endif

23.endfor

24.returnRAx,RBx;

25.endfunction

26.Partition(RA,RB);

27.while(1)do

28.Partition(RAx,RBx);

29.ifN為質數then

30.break;

31.endwhile

32.按式(13)最終確定不合理評分；

33.按式(14)修正不合理評分；

endbegin

步驟2相似度計算與評分推薦過程

輸入：Ruv,L。

輸出：推薦評分Pjk。

begin

1.forrjk∈Ijdo

2.sum(rj)←sum(rj)+rjk;//對用戶Aj的評分求和

3.endfor

5.forrjk∈Ihdo

6.sum(rh)←sum(rh)+rhk;/*對用戶Ah的評分求和*/

7.endfor

9.forrj∈Ijdo

10.forrh∈Ihdo

11. 按式(16)計算出皮爾遜相似度simpcc(Aj,Ah);

12. 按式(17)～式(20)計算出模糊偏好平均相似度ps(Aj,Ah);

13. 按式(21)計算出Jaccard相似度J(Aj,Ah);

14.sim(Aj,Ah)=simpcc(Aj,Ah) *ps(Aj,Ah) *J(Aj,Ah);

15.endfor

16.endfor

17.forCk∈{C1,C2,…,Cv}do

18.forAh∈Ldo

19. 按式(23)計算出用戶Aj對應項目Ck的推薦評分Pjk;

20.endfor

21.endfor

endbegin

步驟1中，第1～25行先對評分向量進行分組，再建立確定不合理評分所在數組的確定函數，通過該函數可將評分向量降維分為多個分向量，并在分向量中找出帶有不合理評分的向量；第26～33行反復調用所建函數并最終確定和修正不合理評分。步驟2中，第1～4行求取用戶Aj的評分均值，第5～8行求取用戶Ah的評分均值，第9～16行計算用戶Aj與Ah的評分相似度，第17～21行計算用戶Aj對應項目Ck的推薦評分。

5 實驗及結果分析

5.1 數據集及仿真環境的介紹

基于2個不同類別的經典數據庫MovieLens 100K和Bookcrossing進行實驗，前者是電影評分系統，用戶在觀影后根據自身的喜好度對影片進行打分，評分值為1～5分，包括電影信息和用戶屬性信息。其中，電影信息包括電影ID、title、genres；用戶的屬性信息包括用戶ID、性別、年齡、職業、郵政編碼。后者是書籍評價系統，由Ziegler等人使用爬蟲程序從BookCrossing圖書社區采集的，包括隱式和顯式的評分信息，評分為1～10分。這2個數據集的具體參數如表2所示。

Table 2 Specific parameters of the datasets表2 數據集的具體參數

本文仿真環境的計算機配置為：Windows 10 操作系統，8 GB 內存，Intel(R)Core(TM)i7-6700HQ，CPU為主頻2.60 GHz，實驗基于IDEA開發平臺，采用scala進行開發。

5.2 評價指標和對照算法的選取

在推薦系統中，不同的評價指標反映算法不同層面的性能，為了驗證本文所提算法的有效性，實驗采用平均絕對偏差(MAE)、準確率(Precision)和覆蓋率(Coverage)進行分析。

假設目標用戶對候選項目Ck的推薦評分為Pk，實際評分為rk，候選項目個數為M，則MAE的表達式[21]為：

(24)

MAE的值越小，表明預測誤差越小，推薦結果越準確。

假設Lj為用戶Aj的推薦列表商品集合，Fj為用戶Aj喜歡的商品集合，則準確率的表達式為：

(25)

Precision表示的是推薦列表中有多少比例的物品出現在測試集里的商品評分記錄中，準確率的值越大，表明推薦精度越高。

假設系統中的項目共有V個，被推薦的項目為VR個，則覆蓋率的表達式為：

(26)

覆蓋率越高，說明用戶推薦列表中的商品越多，則整體多樣性越高。

將經典的以余弦相似度為基礎的協同過濾推薦算法(Cosine-CF)、文獻[5]提出的多層次混合協同過濾USICCF(User Score and Interest and Characteristic Cooperative Filtering)推薦算法作為本文基于余弦相似度修正評分的協同過濾ARCSCF(Adjusted Rating by Cosine Similarity Collaborative Filtering)推薦算法的對照算法。由于Cosine-CF算法僅從用戶間的評分進行相似度的計算；USICCF算法基于用戶的評分、興趣與人口統計特征衡量相似度，借助用戶的其他特征能在一定程度上修正不合理評分帶來的相似度衡量誤差；而ARCSCF算法在利用余弦相似度修正不合理評分的基礎上，采用模糊化的混合評分相似度進行相似鄰居用戶的提取。故本文選擇Cosine-CF和USICCF算法作為本文算法的對照算法，以便更好地反映本文算法利用余弦相似度修正不合理評分的有效性。

5.3 實驗結果及分析

在實際操作中，為有效選取高相似度的項目組，本文通過對比項目參數進行相似度評估。如MovieLens 100K數據集中的電影類型、年代、時長、出品地、清晰度、音質、特效、所用語言、主角等級等，將各類參數量化成項目特征向量。在量化項目參數時，可采取分類或分段的數字對應法，比如類型，類型甲對應數字“0”，類型乙對應數字“1”，類型丙對應數字“2”等；又比如年代，70年代對應數字“0”，80年代對應數字“1”，90年代對應數字“2”等。量化后，求取這些特征向量的余弦相似度，當余弦相似度達到90%以上時，視為高相似度。同理，在選取Bookcrossing數據庫中的高相似度書籍時也采用上述方法。

5.3.1 確定最優參數

在修正不合理評分時，選取合適的Δsim(A,B)cos是一個比較關鍵的問題。由于不合理評分在總體評分中所占比例很小，所以，為整體上使評分盡可能符合用戶意志，在確定Δsim(A,B)cos時，采用修正前的rk。此時，如果Δsim(A,B)cos過大，則不能有效修正不合理評分；如果過小，則會出現過度修正，將本身合理的評分差別縮小或消除，從而使修正后的評分不能代表用戶意志，進而使MAE增大。采用MovieLens 100K數據集來確定Δsim(A,B)cos參數的最優值，實驗結果如圖2所示。

Figure 2 MAE curve of each neighbor number corresponding to different Δsim(A,B)cos values圖2 不同Δsim(A,B)cos對應各鄰居數的MAE曲線

圖2為在不同用戶鄰居數目|L|情況下不同Δsim(A,B)cos對應的MAE曲線。其中，|L|分別為20，40，60，80，100。Δsim(A,B)cos分別為0，0.04，0.08，0.12，0.16，0.2，0.24，0.28，0.32，0.36，0.4。

根據圖2，無論用戶鄰居數|L|如何變化，MAE均隨Δsim(A,B)cos從0逐漸增大，先快速減小而后緩慢增大，最后逐漸趨于平穩。表3所示為圖2對應的MAE值。

在已考察的Δsim(A,B)cos中，當Δsim(A,B)cos在0.2附近時，可使得MAE最小，故本文選取Δsim(A,B)cos=0.2。

5.3.2 分析算法的收斂性

采用MovieLens 100K和Bookcrossing數據集來驗證ARCSCF算法在收斂性上的優勢，對照算法采用修正前的評分數據集，本文算法采用修正后的評分數據集。鑒于ARCSCF算法和對照算法在MAE、Precision、Coverage上具有相似的實驗結果，因此主要考察各個算法在Precision上的收斂狀況，實驗結果如圖3所示。

Figure 3 Precision convergence curve of each algorithm under different iteration times圖3 不同迭代次數下各算法的Precision收斂曲線

圖3為在不同迭代次數情況下各算法對應的Precision收斂曲線，其中，迭代次數以200為步長從0增長到1 000。根據圖3a和圖3b可知，ARCSCF算法和對照算法的準確率都隨著迭代次數的增長而趨于收斂，并最終僅在小范圍內波動。ARCSCF算法的收斂速度相較于對照算法更快，在迭代大概100次以后基本趨于穩定，而Cosine-CF算法、USICCF算法分別在迭代大約200次，180次以后趨于平穩。這是因為ARCSCF算法在修正用戶不合理評分基礎上進行商品推薦，保證每次迭代均能尋找到與目標用戶真正相似的推薦用戶群，進而使得ARCSCF算法的收斂速度更快，能在較少的迭代次數下便可獲得較高的推薦準確率。

5.3.3 對照實驗

在鄰居數不同的情況下對評分修正前和評分修正后的MAE進行對比，從而反映本文算法對推薦準確度的影響。基于MovieLens 100K數據集考察MAE隨|L|的變化時，實際評分采用修正后的rk值，在未修正和修正后2種情況下對比不同用戶鄰居數目對應的MAE，所得曲線如圖4所示，對應具體的MAE值如表4所示。

Table 3 MAE of each neighbor number corresponding to different Δsim(A,B)cos values表3 不同Δsim(A,B)cos對應各鄰居數的MAE值

Figure 4 MAEs before and after revision when Δsim(A,B)cos=0.2圖4 Δsim(A,B)cos=0.2時修正前后對應的MAE

根據圖4和表4可以看出，評分修正后的推薦評分的MAE相比修正前的有所下降。隨著鄰居數的增多，推薦評分的MAE越來越小，且其變化越來越趨于平穩，同時評分修正前后推薦評分MAE的差距越來越明顯。這是因為隨著鄰居數增多，出現不合理評分的概率越大，對推薦精度影響越大。

Table 4 MAEs before and after revision corresponding to different neighbor numbers表4 評分修正前后不同用戶鄰居數對應的MAE值

為了進一步驗證本文算法的先進性，基于MovieLens 100K和Bookcrossing數據集比較ARCSCF算法和對照算法在MAE、Precision、Coverage指標上的推薦性能，同樣地，對照算法采用修正前的評分數據集，本文算法采用修正后的評分數據集。隨機地將實驗數據的80%作為訓練集和20%作為測試集，該方式可能存在一定的人為處理偏差，故進行5折交叉實驗，將5次實驗的平均值作為最終仿真結果。實驗結果如圖5～圖7所示。

Figure 5 MAE curve of each algorithm corresponding to different neighbor numbers |L|圖5 不同鄰居數|L|對應各算法的MAE曲線

Figure 6 Precision curve of each algorithm corresponding to different neighbor numbers |L|圖6 不同鄰居數|L|對應各算法的Precision曲線

Figure 7 Coverage of each algorithm corresponding to different neighbor numbers |L|圖7 不同鄰居數|L|對應各算法的Coverage值

從圖5a和圖5b可以看出，3種算法的MAE曲線在2個不同類別數據集MovieLens 100K和Bookcrossing上均呈波動下降態勢，對照算法的MAE曲線下降幅度較小，ARCSCF算法的MAE曲線下降幅度較大，ARCSCF算法的MAE指標整體取值均小于對照算法的，說明本文算法的預測精度最高。此外，在鄰居數|L|為80，100附近時，對照算法的MAE基本趨于平緩，ARCSCF算法的MAE還有下降趨勢。這是因為Cosine-CF算法僅從用戶間的評分進行相似度的衡量，但不合理評分的存在會使得相似用戶的挖掘不夠準確；USICCF算法將用戶評分與用戶特征相結合能在一定程度上弱化不合理評分的影響，但效果并不明顯；而ARCSCF算法在修正用戶不合理評分基礎上進行商品推薦，使得修正后的評分數據更符合用戶真實的偏好狀況，進而縮小相似度計算的誤差，能推薦更符合用戶真實喜好的商品，故ARCSCF算法相比對照算法能獲得更好的推薦效果。

由圖6a和圖6b可知，3種算法的Precision值在2個不同類別數據集MovieLens 100K和Bookcrossing上均隨著鄰居數|L|的增加呈現上升趨勢，Cosine-CF算法的增長幅度最小，USICCF算法次之，ARCSCF算法最大，且ARCSCF算法在Precision指標上的整體取值均高于對照算法的。同時，當鄰居數|L|在80，100附近時，對照算法均趨于平緩，而ARCSCF算法仍有上升趨勢。這是因為ARCSCF算法基于修正后的評分數據集進行協同過濾推薦，能獲得更相似的用戶群，故推薦準確率相較于對照算法來說更高。

根據圖7a和圖7b可知，ARCSCF算法相比對照算法在2個不同類別數據集MovieLens 100K和Bookcrossing上的Coverage指標有很大的提升，ARCSCF算法的覆蓋率最高，USICCF算法次之，Cosine-CF算法的最低。ARCSCF算法先對評分數據集中的不合理數據進行修正，再基于修正后的評分數據從用戶的實際消費偏好進行商品推薦，使推薦的商品能更好地貼合用戶多樣化、個性化的消費喜好，從而提高推薦的覆蓋率。

6 結束語

在眾多用戶對眾多項目做出評分的過程中，難免出現因某些原因致使部分用戶所做的少量評分與自身意志不相符的情況，即不合理評分。為了在推薦時盡可能地減小這類評分的影響，本文提出了一種基于余弦相似度的評分修正算法，采用該算法可有效修正不合理評分，將帶修正評分的評分數組用于相似度計算，進而為用戶進行項目推薦。其中，評分相似度由皮爾遜相似度、模糊偏好相似度和Jaccard相似度相乘得到。將未修正評分數組和修正后的評分數組用于協同推薦，結果表明，后者推薦評分MAE相比前者更小。此外，將本文算法與其他算法進行仿真實驗，同樣能驗證該算法的有效性，實驗結果反映出本文算法相比對照算法能獲得更好的推薦效果。