基于離散量和用戶興趣貼近度的協同過濾推薦算法

,,,

(西北農林科技大學 信息工程學院,西安 710000)

0 概述

協同過濾推薦算法的關鍵步驟是計算用戶或項目之間的相似度[1]。傳統的相似度計算方法有余弦相似度、相關相似度以及修正的余弦相似度等[2-4]。傳統相似度計算方法計算的相似度結果存在諸多問題,目前,研究者從多個方面對相似度計算進行了改進[5-7]。如文獻[8]借用Sigmoid函數對相似度計算進行了改進,從一定程度上提高了準確率;文獻[9]在文獻[8]的基礎上從用戶評分相似度、興趣的傾向相似度、置信度等方面對相似度計算方法進行了改進,提出了基于用戶屬性和評分的協同過濾算法(Collaborative Filtering Recommendation Algorithm Based on User Attributes and Scores,US-CF),但相似度計算結果仍存在很多問題。在評分數據豐富的情況下,傳統相似度計算方法能夠較為準確地計算出目標間的相似度[10]。然而在實際推薦過程中可用的評分數據稀少,使得系統難以搜尋到目標用戶真正的鄰居,產生了數據稀疏性問題[11-12]。部分學者采用數據填補技術降低評分數據的稀疏性,但存在信息失真或者填充值不可靠的問題[13-15]。另外在用戶評分數據極端稀疏和用戶間共同評分項較少的情況下,余弦相似度不能區分平行評分向量之間的相似度,相關相似度以及修正的余弦相似度出現無法衡量部分用戶間興趣相似程度的現象,導致推薦過程中得到的相似用戶不準確,進而影響推薦系統的推薦質量[16-17]。

為了解決以上問題,本文提出一種基于離散量和用戶興趣貼近度的協同過濾算法(Collaborative Filtering Recommendation Algorithm Based Discrete Contents and User Interests Appropinquity Degree,DA-CF)。在該算法中,通過利用離散量相關的性質以及用戶興趣貼近度設計一種新的用戶相似度計算方法。

1 傳統相似度計算問題分析

傳統的相似度計算方法有余弦相似度(Cosine,COS)、修正余弦相似度(Adjusted Cosine,ACOS)、Pearson相似度(Pearson Correlation Coefficient,PCC)等[5]。計算用戶相似度是基于用戶的協同過濾的關鍵步驟,其計算結果的好壞,直接影響推薦精度[18]。以上的傳統相似度計算方法均存在缺點,以下的例子說明傳統方法的缺陷。如表1是用戶項目評分表,為計算方便,采用了9個用戶對4個項目的評分值,其中用戶用{u1,u2,…,u9}表示,項目用{i1,i2,i3,i4}表示,“—”表示未評分項目,在實例計算中用0替代。

表1 用戶項目評分

本文中利用矩陣S=(sij)n×n表示相似度計算結果,其中,n={1,2,…,9},sij表示用戶ui和uj之間的相似度。以余弦相似度方法、修正余弦相似度方法、Pearson相似度方法、US-CF算法[9]為例,分析目前的相似度計算方法存在的問題,4種算法的相似度計算結果分別對應于矩陣SCOS、SACOS、SPCC和SUSCF。

分析以上計算結果,可知傳統相似度計算存在以下問題:

1)相似度無法計算。由結果矩陣SPCC和SUSCF可知,PCC和US-CF方法計算相似度時,均出現了無法計算的現象(NaN),原因在于當公式分母計算結果為0時,此2種方法計算失效。在數據量極其稀疏時,此情況經常出現。

2)相似度失真。u1的評分向量為(4,3,5,4),u3為(4,3,3,4),兩者均評價了較多的項目,并且有75%的項目評價分數完全一樣,具有較大的相似度。而在結果矩陣SACOS和SPCC中得到的相似度為0,同時SUSCF中得到的相似度也較低。

3)相似度虛高。u4的評分向量為(4,2,0,0),u7為(2,1,0,0),雖然兩者具有兩項共同評分項,但u4評分值較高,對i1、i2有較大興趣,而u7評分較低,對i1、i2有較低興趣,在矩陣SCOS和SPCC中均得到相似度為1,在SACOS中得到的相似度同樣很高。

4)相似度難以區分的現象。結果矩陣SCOS、SACOS、SPCC和SUSCF中均出現了部分相同或十分相近的數值,導致相似度無法區分。由3)中分析知,u4對i1、i2有較大興趣,而u7對兩者的興趣較低,即u4和u7興趣不同。而在SCOS中,u1和u4、u1和u7的相似度相同,均為0.606,若根據用戶u1的興趣為u4和u7進行推薦時,很可能會將用戶興趣較低的項目推薦給用戶,從而導致推薦質量下降。

5)相似度計算忽略了共同評分項數以及相同評分值項數對興趣的影響。用戶評分項目越多,共同評分項越多,并且具有相同評分項數越多,可以認為具有較高的相似度[13]。基于此,u1和u3的相似度應該最高,但矩陣SUSCF中u2和u4的相似度高于u1和u3的相似度,而SPCC中u2和u4以及SCOS中u4和u7的相似度均高達1。

6)相似度計算忽略評分偏好對興趣度的影響。u5的評分向量為(5,5,0,0),u7為(2,1,0,0),u5對項目1和2的傾向度明顯大于u7,但矩陣SCOS和SACOS均得到較大的結果,分別為0.949和0.948。SPCC中對此情況計算無效,SUSCF中反而呈現出極低的相似度0.033。

以上問題導致了計算相似度時準確度不高,最終導致傳統推薦算法的推薦結果不理想,若要解決相似度計算出現的種種問題,則需更深入地挖掘用戶評分中所隱藏的興趣信息,本文提出一種新的相似度計算方法,用于改進傳統協同過濾算法。

2 改進的協同過濾算法原理

離散量考慮的是全部個體的總信息量,在離散量的基礎上建立信息相似系數測度,可以得到更為全面的相似度信息,但是往往會忽略個體間的差異信息,貼近度更偏重于信息組成顆粒間的差異程度,體現了個體間的差異性,能夠彌補離散量構建信息相似系數測度的不足。本節從全信息量的角度深入挖掘評分與用戶興趣間的關系,揭示用戶評分之間的相似度,利用離散量相關理論來對相似度計算進行改進,同時利用用戶興趣貼近度對相似度進行加權處理,最終得到較為準確合理的相似度計算結果。

2.1 基于離散量的相似度計算方法

Shannon把“熵”從物理學領域引入到信息學領域,將信息中排除冗余后的平均信息量稱為“信息熵”,并利用概率論與邏輯方法推導出信息熵的計算公式[19-21]。用X表示信源,該信源發出的信號用xi表示,相應地發出各信號的先驗概率為p(xi),其中i=1,2,…,n,則對該信源的信息熵H(X)定義為式(1),其中使用以2為底的對數函數,熵的量綱為比特。

(1)

與Shannon信息量相平行,本文中將引入離散量(Discrete Contents,DC)及其基本性質。對于狀態空間X={x1,x2,…,xr},在總和N=n1+n2+…+nr的條件下,xi分別出現ni次,其中i=1,2,…,r,則認為狀態空間構成一個離散源[22-24],表示為式(2)。

(2)

從信息論的角度上,度量離散性的量稱為離散量,記為D(n1,n2,…,nr)。

定義1對于離散源(式(2)),離散量定義[23-24]:

(3)

根據式(3),可以引申出式(4)和式(5)。

(4)

(5)

由式(4)可以看出,D(X)和N有關系,刻畫了N約束下ni的離散性。而式(5)表示了離散量和信息熵之間的關系,用H(X)和D(X)分析同一事物,沒有絕對的相關性。根據信息熵的定義可以看出,H(X)表示信源X中每個個體所攜帶的平均信息量,而式(5)可以看出,離散量D(X)表示信源X中全部個體的全信息量。由式(5)可知,離散量同樣具有信息熵的性質,即具有非負性、可加性、等倍增性以及和的離散量不小于各離散量之和等性質[24]。

在本文的推薦系統中,假設用戶U和用戶V對項目集合的評分矩陣分別為矩陣U和V:

(6)

(7)

評分矩陣公式式(6)和式(7)從空間角度可以理解為評分向量,從信息論角度可以理解為離散評分源。根據離散量的性質——和的離散量不小于各離散量之和,可以得到評分數據的離散增量:

Δ(U,V)=D(U+V)-D(U)-D(V)

(8)

評分數據的離散增量同樣具有非負性和對稱性,是一種半角度的距離測度或者稱為廣義距離測度,它從信息量的角度刻畫了2個離散評分源之間的相似度,稱為信息系數測度[24]。信息系數測度越小,表示2個離散評分源之間越相似,否則越相異。根據離散量可加性以及等倍增性,還可以將評分數據的離散增量表示為:

(9)

當評分數據ni或mi之一等于0時,D(ni,mi)=0,由此可得:

0≤Δ(U,V)≤D(M,N)

(10)

由式(9)和式(10)聯合可以得到如下關系:

(11)

(12)

由式(11)可以得到評分數據的相似信息系數,用于度量2個用戶之間的相似程度,本文使用的相似度計算方法表示為式(12),I1即為基于離散量的相似度計算方法,利用該式計算出來的相似度結果如矩陣SI:

SI=

由結果矩陣SI可以看出,基于離散量的相似度計算方法充分挖掘評分項之間的關系,得到了初步的相似度計算結果,但由于式(12)只考慮了評分項目之間的關系,忽略了用戶之間的興趣傾向與共同偏好,在一定程度上放大了用戶間的相似程度,為此,將使用用戶興趣貼近度進行修正。

2.2 用戶興趣貼近度的修正方法

2.1節從全信息量的角度刻畫了用戶評分信息間的貼近程度,給出了基于離散量的相似度度量方法(式(12)),該方法深入地挖掘和分析了用戶評分間的信息關系,但以上方法未關注用戶興趣偏好問題。用戶評分項目越多,共同評分項越多,并且具有相同評分項數越多,可認為具有較高的相似度[13]?；诖思僭O,本節提出用戶興趣貼近度的概念,見定義2。

定義2設項目集合I={i1,i2,…,in},u和v是I上的評分集合,則稱:

(13)

為u與v的用戶興趣貼近度。其中,α稱為可信度因子,見式(14),可信度因子用來表示用戶之間共同評分項目與所有評分項目的關系,表示用戶之間實際興趣貼近關系。其中,Cu,v表示用戶u和v的共同評分項目集合,|Cu,v|表示共同評分項目數,ru,i表示用戶u對項目i的評分,Iu表示用戶u的評分集合,評分范圍為整數1～5。

(14)

由式(14)可知,0≤α≤1。當用戶u與用戶v沒有共同評分項時,α=0。當用戶u與用戶v的共同評分項集合與兩者的所有評分項集合完全一致時,α=1。

當α=1時,可信度因子調節失效,針對此特殊情況,用戶興趣貼近度參考海明貼近度[23]的形式,將其改進為評分環境下的海明貼近度公式,如式(15)的形式,其中,Iu,v表示用戶u和v共同評分項目集合。

(15)

2.3 融合離散量和興趣貼近度的相似度計算方法

經過2.1節和2.2節的分析,本節得到融合離散量和用戶興趣貼近度的相似度計算方法。在計算過程中分用戶間的可信度因子α≠1和α=1,本文所提出的相似度計算方法如下:

(16)

最終,經過式(13)和式(15)修正后的相似度計算結果如矩陣SSIM所示,其中0值表示相似度為0,例如u2和u8、u2和u9都沒有公共項,因此相似度為0,屬正常計算結果。從結果矩陣中可以看出,本文算法計算的相似度計算結果能準確合理地體現用戶間的相似度,解決了以上提到的6個問題以及其他潛在問題,提高了用戶之間相似度的區分性,從而為推薦系統解決了核心的相似度計算問題,有利于后續的評分預測和個性化推薦。

SSIM=

2.4 協同過濾算法

根據2.3節提出的融合離散量和用戶興趣貼近度的相似度計算方法,本節利用新的相似度計算方法對協同過濾算法進行改造,則新算法的偽代碼見算法1。

算法1基于離散量和用戶興趣貼近度的協同過濾算法

輸入評分矩陣R,目標用戶u和近鄰數K

輸出目標用戶u對項目i的評分預測值Predu,i

2) for 所有用戶 u in 測試集 Trm,ndo

3) D(u),D(v) ← 計算用戶u和v的離散量,根據式(4)

4) D(u+v) ← 計算用戶u和v聯合的離散量,根據式(8)

5) D(u,v) ← 計算用戶u和v評分和的離散量,根據式(4)和式(9)

6) I1← 1-[{D(u+v)-D(u)-D(v)}/D(u,v)] %計算信息相似系數測度

二級運算放大電路主要用于將一級放大結果放大調理以滿足A/D轉換芯片輸入范圍，獲取最大的檢測精度。其電路結構如圖4所示。

7) if α≠1 then

8) σu,v(u,v) ← 計算用戶興趣貼近度,根據式(13)

9) end if

10) if α=1 then

11) σ’u,v(u,v) ← 計算用戶興趣貼近度,根據式(15)

12) end if

13) sim’’(u,v) ← I1·σu,v(u,v) or I1·σ’u,v(u,v) %計算最終的相似度結果

14) K ← u’∈N(u) %尋找活動用戶u的K近鄰

15) Predu,i← 計算目標用戶u對未評分項目i評分預測值

16) end for

17) 計算測試集中預測評分的平均絕對誤差

3 實驗結果與分析

3.1 實驗數據

實驗數據為MovieLens,是由明尼蘇達大學GroupLens小組提供的電影評分[16]。該電影數據集具有100k、1m、10m、20m等幾個不同規模的評分集合,如表2所示,該數據集可以從網站www.grouplens.org下載所得。為說明驗證本文的研究問題,采用ml-1m數據集,該數據集是在2000年,大約6 040名用戶對接近3 900部電影的1 000 209個匿名評分數據,數據稀疏等級[17]為{1-[1 000 209/(6 040×3 900)]}=0.957 5,評分范圍為整數1～5。數據集包含三方面內容,用戶信息、電影信息、評分信息。用戶信息包括用戶ID、性別、年齡、職業以及郵政編碼;電影信息包括電影ID、標題以及類別;評分信息包括用戶ID、電影ID、評分值以及時間戳。

表2 MovieLens數據集規模

3.2 實驗環境和度量標準

實驗環境為安裝Windows 10操作系統的PC機,內存16 GB,磁盤1 TB,處理器為英特爾Core i7-6700HQ。程序開發環境為Anaconda2 Spyder,Phython版本號為2.7版。

推薦系統有多種評估指標,如評分預測準確度、覆蓋率、置信度、信任度等,評分預測準確度是目前推薦系統研究中討論最多的指標,評分預測準確度的評價標準主要有均方根誤差(Root Mean Square Error,RMSE)、平均絕對誤差(Mean Absolute Error,MAE)、歸一化均方根誤差(Normalized Root Mean Square Error,NRMSE)和歸一化平均絕對誤差(Normalized Mean Absolute Error,NMAE)等。其中,MAE的應用最為廣泛,本文實驗結果選用MAE來評價。MAE可用來衡量預測的評價值同真實用戶評價值之間的接近度,MAE值越小,預測效果越好。假設用戶預測評分集合表示為P={pi|i=1,2,…,n},對應的用戶實際評分集合為Q={qi|i=1,2,…,n}[25-26]。其中,n為物品個數,則MAE計算方法如下:

(17)

3.3 實驗結果分析

首先對各種不同的相似度計算方法計算出的平均絕對誤差(MAE)進行對比,分析本文所提出的相似度計算方法的效果;然后在相同數據集上進行對比實驗,比較本文提出的新算法與傳統算法的推薦質量,并對實驗結果進行分析說明;最后在不同稀疏度的數據集上,驗證本文算法在極度稀疏的數據集上的推薦效果。

3.3.1 最優用戶鄰居數

本次實驗過程采用十折交叉驗證方法(10-fold cross validation)用來測試算法的準確性。具體操作方法是將數據集分成10份,輪流將其中9份作為訓練集,剩下的1份作為測試集,進行多次試驗后,最終取均值。此方法的優勢在于防止數據集之間的數據分布不均,同時多次驗證取均值能有效降低因隨機取樣產生的誤差。

本次實驗的目的是尋找最優鄰居數K,每次實驗將K值從5增加到100,10次實驗的MAE求均值,結果如圖1所示。從圖中可以清晰看到,本文提出的算法,在用戶鄰居數達到40附近時,計算出來的MAE值最小,因此最優用戶鄰居數選擇為40。

圖1 MAE值隨最近鄰數K的變化情況

3.3.2 不同推薦算法的推薦質量比較分析

本次實驗比較不同推薦算法的推薦質量,利用不同K值下的平均絕對誤差(MAE)進行衡量,平均絕對誤差值越小,推薦質量越好。

實驗中,傳統協同過濾算法采用不同的相似度度量標準進行近鄰計算。所使用的算法有基于余弦的協同過濾算法(COS-CF)、基于修正余弦的協同過濾算法(ACOS-CF)、基于Pearson的協同過濾算法(Pearson-CF)、文獻[9]中的算法(US-CF)以及本文提出的算法(DA-CF),實驗結果如圖2所示。

圖2 不同相似度計算方法推薦質量比較

圖2展示了各種算法在不同K值下MAE值之間的數量關系,整體而言,本文改進算法的MAE值明顯低于傳統算法。當最近鄰居數K小于30時,各種算法MAE值都較高,隨著最近鄰居數的增加,各種算法的MAE值均急劇下降,本文改進的算法相較其他算法在最近鄰居數為5時的MAE值最小,從最近鄰數從5～30的增加過程中變化幅度比其他算法小;當K值大于30后,各種算法逐漸趨于穩定,本文算法的MAE值明顯比其他算法更低,說明本文提出的算法在推薦精度方面優于其他算法,可以顯著地提高推薦系統的推薦質量。

3.3.3 數據稀疏度對算法的影響

本次實驗為比較在不同數據稀疏等級下,本文提出的算法(DA-CF)與3.3.2節中其他傳統算法性能表現。將數據集中的評分數據隨機進行刪除調整,以實現數據稀疏度的變化,根據文獻[17]的數據稀疏等級計算方法,將調整后的數據集稀疏度結果展示如表3所示。

表3 數據集各種不同的稀疏度

本文實驗結果如圖3所示,從圖中可以看出,隨著數據稀疏度的變大,所有算法的性能均變低,但變化程度不一樣,本文提出的算法(DA-CF)相對于其他算法而言,變化幅度最小,同時在各種場景下,MAE值最低,能較好地適應各種不同稀疏度的數據。由于DA-CF算法從全信息量的角度深入尋找評分與用戶興趣間的關系,因此在數據極度稀疏的情況下,也有較好的性能。

圖3 數據稀疏度對不同算法性能的影響

4 結束語

本文提出基于離散量和用戶興趣貼近度的協同過濾算法。從用戶評分全信息量和用戶興趣偏好2個方面,融合離散量和用戶興趣貼近度,進行用戶相似度計算。實驗結果表明,DA-CF算法較好地解決了常規相似度算法中存在的相似度無法計算、失真、虛高等現象,提高了系統的推薦質量,尤其在數據極端情況下,也能保持相對較好的推薦性能。在未來的研究中,可以結合更多的情境因素,緩解算法的冷啟動問題,進一步提高算法的推薦質量。

[1] 文俊浩,袁培雷,曾 駿,等.基于標簽主題的協同過濾推薦算法研究[J].計算機工程,2017,43(1):247-252.

[2] 孟祥武,劉樹棟,張玉潔,等.社會化推薦系統研究[J].軟件學報,2015,26(6):1356-1372.

[3] RICCI F,ROKACH L,SHAPIRA B,et al.Recommender Systems Handbook[M].Berlin,Germany:Springer,2011.

[4] 郭 遲,劉經南,方 媛,等.位置大數據的價值提取與協同挖掘方法[J].軟件學報,2014,25(4):713-730.

[5] CHOI K,SUH Y.A New Similarity Function for Selecting Neighbors for Each Target Item in Collaborative Filtering[J].Knowledge-based Systems,2013,37(1):146-153.

[6] AHN H J.A New Similarity Measure for Collaborative Filtering to Alleviate the New User Cold-starting Problem[J].Information Sciences,2008,178(1):37-51.

[7] 時念云,葛曉偉,馬 力.基于用戶人口統計特征與信任機制的協同推薦[J].計算機工程,2016,42(6):180-184.

[8] LIU H,HU Z,MIAN A,et al.A New User Similarity Model to Improve the Accuracy of Collaborative Filtering[J].Knowledge-based Systems,2014,56(3):156-166.

[9] 丁少衡,姬東鴻,王路路.基于用戶屬性和評分的協同過濾推薦算法[J].計算機工程與設計,2015(2):487-491.

[10] 劉樹棟,孟祥武.基于位置的社會化網絡推薦系統[J].計算機學報,2015,38(2):322-336.

[11] 林耀進,張 佳,林夢雷,等.一種基于模糊信息熵的協同過濾推薦方法[J].山東大學學報(工學版),2016,46(5):13-20.

[12] 韓亞楠,曹 菡,劉亮亮.基于評分矩陣填充與用戶興趣的協同過濾推薦算法[J].計算機工程,2016,42(1):36-40.

[13] TSAI C F,HUNG C.Cluster Ensembles in Collaborative Filtering Recommendation[J].Applied Soft Computing,2012,12(4):1417-1425.

[14] 張燕平,張 順,錢付蘭,等.基于用戶聲譽的魯棒協同推薦算法[J].自動化學報,2015,41(5):1004-1012.

[15] HUETE J F,FERNNDEZ-LUNA J M,CAMPOS L M D,et al.Using Past-prediction Accuracy in Recommender Systems[J].Information Sciences,2012,199(15):78-92.

[16] 鐘 川,陳 軍.基于精確歐式局部敏感哈希的改進協同過濾推薦算法[J].計算機工程,2017,43(2):74-78.

[17] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報,2003,14(9):1621-1628.

[18] 周泓宇,梁 剛,馮 程,等.結合正反相似度的協同過濾推薦算法[J].計算機工程,2016,42(10):51-56.

[19] WANG W,ZHANG G,LU J.Collaborative Filtering with Entropy-driven User Similarity in Recommender Systems[J].International Journal of Intelligent Systems,2015,30(8):854-870.

[20] 李衛東.應用多元統計分析[M].北京:北京大學出版社,2015.

[21] 汪 濤,王永智.基于信息熵的安徽省創意產業結構均衡度分析[J].新余學院學報,2017,22(1):43-47.

[22] 王保山,邵明星,丁愛亮,等.證券市場信息熵技術指標構建與應用[J].寧波大學學報(理工版),2012,25(3):79-82.

[23] 袁志發,宋世德.多元統計分析[M].2版.北京:科學出版社,2009.

[24] 丁世飛,靳奉祥,趙相偉.現代數據分析與信息模式識別[M].北京:科學出版社,2013.

[25] 李曉艷,張子剛,張逸石.集成K-means聚類和有監督特征選擇的混合式協同過濾推薦[J].管理學報,2013,10(9):1362-1367.

[26] 劉旭東,吳旭軍,陳德人,等.基于用戶特征分解的協同過濾冷啟動解決方法[J].山東農業大學學報(自然科學版),2013,44(4):616-619.