張岐山,陳露露
福州大學 經(jīng)濟與管理學院,福州350108
協(xié)同過濾作為目前應用最為廣泛的一種推薦方法[1],主要分為基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾?;谟脩舻膮f(xié)同過濾方法通過計算用戶之間的相似度,找出與目標用戶興趣相似的近鄰用戶集,從相似用戶感興趣的項目中對目標用戶進行推薦;基于項目的協(xié)同過濾指根據(jù)用戶的歷史偏好記錄計算項目之間的相似度,將相似項目推薦給當前用戶[2]。由于協(xié)同過濾算法非常流行,研究人員嘗試了不同的方法來改進它。一方面,一些學者設計了新的啟發(fā)式方法,如聚類、降維、加權預測等。另一方面,一些學者將統(tǒng)計模型、概率相關模型等與協(xié)同過濾結合起來,生成新的推薦算法。然而,這些算法也變得更加復雜或者難以實現(xiàn)。Slope One算法是那些有效且易于實現(xiàn)的算法之一。
Slope One算法是由Lemire等[3]在2005年提出的一種基于項目的協(xié)同過濾算法,與其他推薦算法相比更加高效、容易執(zhí)行。作為一種有效的協(xié)同過濾算法,Slope One算法受到了研究者的廣泛關注并加以改進。
如Wang 等人[4]利用Slope One 算法對用戶項目評分矩陣填充,再引入用戶相似度,將新變量納入算法權重,提高用戶個性化推薦質量;Zhang[5]利用Slope One算法來預測用戶尚未評級的項目,然后使用Pearson 相關系數(shù)度量目標項目的鄰居最后產生推薦,提高了協(xié)同過濾推薦系統(tǒng)的準確性;王毅等人[6]利用關鍵字之間的語義相似度度量項目之間的相似度提高了預測的準確度;Song等人[7]考慮到用戶之間的關聯(lián)會對算法精度產生影響,以余弦相似度定義用戶相似度,將用戶相似度與Weighted Slope One結合,在不增加空間復雜度的前提下提高了推薦質量;Sun 等人[8]根據(jù)用戶與目標用戶的相似度,將不同的權重附加到不同用戶給出的分數(shù)上,大大提高推薦精度;Zhao 等人[9]使用漢明距離進行聚類,結合用戶相似性和Slope One算法對聚類中的項目評分進行預測;Ni等人[10]采用Canopy-Kmeans算法對時間權重的評級矩陣進行聚類,然后進行填充來提高矩陣的密度,以減少由于數(shù)據(jù)稀疏性對推薦結果產生的影響;Hu等人[11]采用Salton系數(shù)來度量旅游景點之間的相似性關系和景點屬性相似性,與Slope One算法結合應用到旅游景點推薦系統(tǒng)中,提高了推薦結果的新穎性;Sun等人[12]根據(jù)不確定的k 近鄰矩陣中的項目相似度和活躍度,動態(tài)選擇每個項目的鄰居,僅從選定的相鄰項目生成項目之間的平均評級偏差;Cao 等人[13]將時間因素、地理因素和用戶偏好加權到Slope One 算法中,來研究時間和空間因素以及推薦系統(tǒng)中用戶興趣的變化對興趣點推薦的影響;Ye等人[14]結合Slope One算法和SVD算法來解決數(shù)據(jù)不平衡問題,將Slope One算法得到的預測數(shù)據(jù)附加到原始數(shù)據(jù)集中訓練SVD 模型,提高算法的效率;王冉等人[15]將加權二部圖與Slope One算法結合,使推薦結果更加準確多樣化;Zhao 等人[16]考慮到用戶之間以及項目之間的關聯(lián)都會對推薦結果產生影響,將用戶相似度和項目相似度加權到Slope One算法中,提高了推薦精度;Ye等人[17]還結合K 近鄰的思想,引入用戶標簽信息,將Jaccard 方法和Pearson 方法加權融合到偏差公式中來提高預測精度;龔敏等人[18]使用Slope One算法對聚類之后的稀疏矩陣進行填充,對協(xié)同過濾算法進行優(yōu)化,有效提高了算法推薦質量。
上述改進方法在一定程度上改善了推薦效果,但是目前有關相似度改進方面通常采用傳統(tǒng)的相似度計算方法,容易受到個別異常點的影響,忽略了波幅較小元素,不能充分挖掘用戶和項目之間的信息,導致數(shù)據(jù)丟失和信息失真,影響推薦的準確度。
針對以上問題,本文提出將均衡接近度灰關聯(lián)方法與Slope One算法結合起來的改進方案。具體的,本文創(chuàng)新主要體現(xiàn)在以下幾個方面:
(1)在Slope One 算法中引入用戶相似度,在計算時考慮到用戶之間相關性高低對實驗結果造成的影響,而不是粗略地將所有用戶一視同仁,避免大量無關用戶參與計算對預測評分產生干擾,提高推薦質量。
(2)采用均衡接近度灰關聯(lián)方法來度量用戶相似度。由于數(shù)據(jù)集稀疏性較大,如果利用傳統(tǒng)的相似度方法計算用戶相似度容易受到個別異常點的影響,導致數(shù)據(jù)丟失和信息失真。通過計算用戶之間均衡接近度,度量用戶整體的無差異性,不僅可以減弱局部點關聯(lián)傾向[19],還充分利用了點關聯(lián)系數(shù)提供的豐富信息考慮用戶偏好問題,有效挖掘用戶之間的潛在聯(lián)系。
均衡接近度灰關聯(lián)方法由張岐山教授[19]提出,在灰熵和灰關聯(lián)系數(shù)的基礎上,定義了基于均衡接近度的灰關聯(lián)分析方法,可以有效地應用在貧信息系統(tǒng)分析和復雜系統(tǒng)中。
設序列X=(x1,x2,…,xn),F(xiàn) 為數(shù)值映射集,稱χ為X 的像集灰關聯(lián)因子集。 F 為數(shù)值映射集,F(xiàn) ={初值化,平均值化,最大值化,最小值化,區(qū)間值化,正因字化}。 X0∈χ 為參考列,Xi∈χ 為比較列,i ∈I={1,2,…,m} ,Xo={xo(k) |k ∈K} ,Xi={xi(k) |k ∈k} ,K={1,2,…,n}。
定義1灰關聯(lián)公式如下:

其中,ζ 為分辨系數(shù),γ(x0(k),xi(k))為參考列X0與比較列Xi的灰關聯(lián)系數(shù),γ(X0,Xi)為參考列X0與比較列Xi的灰關聯(lián)度。
定義2灰關聯(lián)系數(shù)分布映射:第i 個比較列的關聯(lián)系數(shù)列用Ri表示,Ri={|γ(x0(k),xi(k)) k ∈K},則稱映射:

可得出X 的均衡度為:

定義4均衡接近度:

其中,Ba(X0,Xi)為參考列X0與比較列Xi的均衡接近度。均衡接近度是各比較列與參考列均衡接近程度的測度,均衡接近度越大,比較列與參考列的關聯(lián)性越強。
Slope One 算法(Slope One algorithm,SO)的基本思想為根據(jù)用戶-項目評分矩陣中用戶對每個項目的評分數(shù)據(jù),得到項目之間的評分差值,通過項目評分差值以及用戶的歷史評分記錄得到用戶對目標項目的近似評分值。
算法基本方法是運用線性回歸模式f(x)=x+b來預測評分,其中x為用戶u對項目的預測評分Ru,b為項目i相對于項目評分j的平均偏差,表示為devj,i,最終得到用戶u對項目j的預測評分為Puj。計算公式如下:

其中,χ為用戶集合,ui表示用戶u對項目i的評分,uj表示用戶u對項目j的評分,Sj,i(χ)表示同時對項目i,j有評分的用戶集合,Rj為用戶u的評分項目集合,(card)表示集合包含的元素數(shù)量。
例1 為了更加直觀表達Slope One 算法,下面舉個簡單的例子說明。表1為用戶-項目評分矩陣,顯示了u1、u2、u3、u4四個用戶對五個項目的評分情況,表中空格部分代表用戶對該項目沒有評分,預測u4對i5的評分。

表1 用戶-項目評分矩陣
根據(jù)式(8)分別計算i5相對i2和i3的評分偏差可得:

Slope One 算法沒有考慮到用戶評分數(shù)量的影響。在此基礎上Lemire 等[3]還提出了一種Weighted Slope One 算法(Weighted Slope One algorithm,WSO),該算法考慮了devj,i的可信度差異,計算用戶評分數(shù)對計算項目評分偏差做出的貢獻,其中Cji表示同時對項目i,j有評分的用戶數(shù)量,計算公式如下:

通過對SO、WSO 算法研究分析發(fā)現(xiàn),兩者都沒有考慮用戶相似度對算法推薦結果的影響,而在推薦系統(tǒng)中,相似性的度量至關重要,通過相似度來衡量近鄰用戶對推薦結果的貢獻使得協(xié)同作用更加精確[20]。
推薦系統(tǒng)中,傳統(tǒng)用戶相似度計算方法包括余弦相似度、Pearson 相關系數(shù)以及常用的歐式距離等。余弦相似度方法計算過程簡便但沒有考慮到由于用戶個體差異導致評分會過高或者過低;相比余弦相似度,Pearson相關系數(shù)得到的結果更加準確但沒有考慮到用戶共同評分項目數(shù)量對相似度結果產生影響。在數(shù)據(jù)稀疏時,這兩種方法得到的預測準確率都不高,而且由于評分之間的相關性導致推薦準確率下降[21]?;跉W式距離的相似度計算方法簡單且在數(shù)據(jù)稀疏情況下更適用,但沒有考慮到局部特征的偏差影響,在度量過程中容易受到奇異值影響[22]。針對以上問題,一些學者將灰色系統(tǒng)引入到推薦算法中,相比與其他相似度測量方法,均衡接近度灰關聯(lián)方法在鄧聚龍教授[23]提出的灰關聯(lián)系數(shù)方法上加以改進,既保留了灰關聯(lián)分析的優(yōu)點,同時又避免了局部異常點的影響,利用均衡接近度衡量數(shù)據(jù)點的相似程度,可以充分利用序列之間的信息,有效克服了參數(shù)敏感性對算法的影響,減少非近鄰數(shù)據(jù)的信息損失[22],緩解數(shù)據(jù)的稀疏性對推薦準確率的影響,有效提高算法的推薦質量[24]。
通過以上分析,針對Slope One 算法未考慮用戶相似度以及協(xié)同過濾算法中傳統(tǒng)的相似性計算方法不準確的問題[25],本文提出利用均衡接近度度量用戶相似度的新思路,來充分挖掘用戶之間的信息,使算法能夠在貧信息系統(tǒng)中有效緩解由于數(shù)據(jù)稀疏導致的推薦準確度降低問題。
不同用戶的評分在預測中具有不同的重要性,通過目標用戶與相關用戶的均衡接近度度量用戶之間的相關性,均衡接近度越大,說明用戶關聯(lián)性越強,代表他們對目標項目有相同興趣的可能性越大。具體步驟如下:
(1)對于目標用戶u和相關用戶v,以及評分項目(i1,i2,…,in),根據(jù)公式(1)計算用戶u 與用戶v 在第i 個項目上的灰關聯(lián)因數(shù),通過公式(2)對各項目的灰關聯(lián)因數(shù)求均值得到用戶之間的灰關聯(lián)度。根據(jù)文獻[20],分辨系數(shù)ζ 為0.5 時,關聯(lián)度可以更好地體現(xiàn)序列的整體性。因此本文ζ 取值為0.5。
(2)對公式(1)和公式(2)得到的值,通過公式(3)得到用戶u、v 在各個項目上的灰關聯(lián)系數(shù)分布映射。
(3)通過公式(4)和公式(5)計算得到用戶u、v 在各個項目上的灰關聯(lián)系數(shù)熵和灰熵的最大值。
(4)通過公式(6)得到用戶u 和用戶v 的均衡度。
(5)公式(7)使用公式(2)和公式(6)計算得到的均衡度和灰關聯(lián)度結果,最終得到用戶u 和用戶v 的均衡接近度。
與傳統(tǒng)用戶相似度計算方法相比,均衡接近度灰關聯(lián)方法在計算灰關聯(lián)系數(shù)時,采用兩級最大差與最小差能夠充分利用灰關聯(lián)因子序列間多個比較序列之間點的相關信息,同時分辨系數(shù)的選擇可以削弱比較序列中異常值對關聯(lián)空間的影響,使關聯(lián)度更好地體現(xiàn)了序列的整體性;此外,傳統(tǒng)的相似度方法計算用戶相似度時可分辨性不高,具體表現(xiàn)為對于不同用戶的評分向量與目標用戶進行相似度計算時,可能得到相同的相似度,而灰關聯(lián)度是由離散的關聯(lián)系數(shù)平均值組成,所以在一定程度上可以提高用戶間相似度的可分辨性。
為了防止因相似用戶較少而將均衡接近度為0 的用戶納入計算,本文在選擇相似用戶時對用戶相似性設置了閾值,只有當目標用戶的近鄰用戶大于這個閾值時,才將其作為近鄰用戶參與計算。
根據(jù)前面敘述的利用均衡接近度衡量用戶之間相關性,在Slope One 模型基礎上,將均衡接近度灰關聯(lián)的概念融入到Slope One 算法中,將公式(7)計算得到的用戶之間的均衡接近度結合到公式(9)中對預測公式進行改進,得到改進的基于均衡接近度灰關聯(lián)的Slope One推薦算法(Grey Based Slope One algorithm,GBSO),計算過程如式(11)所示。其中simuv為用戶u與共同評價過項目i,j 的前K 個相似用戶v 的均衡接近度值。

基于均衡接近度灰關聯(lián)的Slope One 算法的具體步驟如下:
算法基于均衡接近度灰關聯(lián)的Slope One 算法偽代碼
輸入:目標用戶u 及其評分項目集合I={i1,i2,…,in},待評分項目j ,用戶-項目評分矩陣Rm×n(分為訓練集和測試集),鄰居用戶個數(shù)K 。
輸出:目標用戶u 對評分項目j 的預測評分Puj。

用戶項目評分矩陣中,多個用戶對同一項目進行評分,那么該項目的所有評分用戶之間會存在著關聯(lián)性,評分用戶之間必然存在某種關聯(lián)因素,這就形成了一種灰色系統(tǒng)。灰關聯(lián)分析是對灰色系統(tǒng)進行整體分析和預測的基礎,利用均衡接近度灰關聯(lián)方法度量用戶相似度,可以根據(jù)灰色系統(tǒng)中各因子之間發(fā)展趨勢的相似程度,來衡量因子之間的近似程度,從而把系統(tǒng)內部有關因子之間的各種關系都展現(xiàn)出來,將存在不確定性的推薦系統(tǒng)內的不定因素加入考慮的范疇內,從而有效挖掘用戶之間的關系。
此外,均衡接近度灰關聯(lián)方法既包含了灰關聯(lián)度對整體接近性的測度,又具有均衡度對序列均衡性測度的特點,綜合考慮了熵關聯(lián)度和點關聯(lián)度,既包含了對序列間點的距離接近性的測度,又包含了對整體的無差異性接近的測試。將均衡接近度灰關聯(lián)方法與Slope One算法結合,可有效改善Slope One 算法存在的問題,使推薦結果更貼近實際情況,提高推薦質量。
實驗環(huán)境:Window10系統(tǒng),硬件配置:CPU 2.60 GHz,RAM 8 GB,運行環(huán)境:Python3.7。
為了驗證改進算法的有效性,本文采用兩個數(shù)據(jù)集進行實驗,分別為:
(1)MovieLens 數(shù)據(jù)集。實驗數(shù)據(jù)采用了由Group-Lens 小組提供的MovieLens 100k 標準數(shù)據(jù)集,其中包括了943 名用戶對1 682 部電影(項目)的100 000 條評分信息,評分區(qū)間為1~5,評分值越大代表用戶越喜歡該電影。該數(shù)據(jù)集的數(shù)據(jù)稀疏度為93.695%。
(2)Epinions 數(shù)據(jù)集。該數(shù)據(jù)集包含了49 290 個用戶對139 738個項目的共664 824條評分信息,評分區(qū)間為1~5,評分值越大代表用戶對項目的喜愛程度越高。該數(shù)據(jù)集的數(shù)據(jù)稀疏度為99.99%。
將實驗數(shù)據(jù)隨機劃分為五組,選擇所有數(shù)據(jù)的80%作為訓練集,20%作為測試集。實驗采用五折交叉驗證方法選擇測試集與訓練集,以確保實驗結果的準確性。
本實驗采用平均絕對誤差(Mean Absolute Error,MAE)、均方根誤差(Root Mean Squared Error,RMSE)來驗證本文提出方法得到的預測結果。
(1)MAE。采用絕對值計算誤差,可以直接反應訓練集的實際分數(shù)與預測值的偏差情況。計算公式如下:

其中,rui為用戶u對項目i的實際評分,preui為用戶u對項目i的評分預測值。N為測試集,| |N表示測試集中元素個數(shù),MAE 值越小,說明實際值與預測值越接近,預測結果越準確。
(2)RMSE。RMSE 對特別大或特別小的測量誤差反映敏感,能很好地反應測量的精確性。計算公式如下:

為驗證在不同數(shù)據(jù)集下本文提出算法的推薦效果,在相同的實驗環(huán)境下設計了3 組實驗,實驗1 和實驗2分別在MovieLens數(shù)據(jù)集和Epinions數(shù)據(jù)集上將提出的算法與SO 算法、WSO 算法以及文獻[6]提出的算法,即以余弦相似度定義用戶相似度,將用戶相似度與Weighted Slope One 結合得到的CSO 算法的實驗結果進行對比分析;實驗3來進一步分析所提出算法的時間性能。
實驗1 在MovieLens 100k標準數(shù)據(jù)集上分別按照各個算法進行計算,得到評分預測值,將計算得到的CSO和GBSO兩種算法在不同K值下的MAE和RMSE值進行比較分析,觀察其變化趨勢。其中,設當前用戶的近鄰數(shù)為K=10,15,20,25,…,55。
由于SO 算法和WSO 算法在計算時不考慮用戶之間的相似度,因此通過這兩種算法求得的MAE和RMSE為固定值,在折線圖上表現(xiàn)為一條直線,無變化趨勢。各算法實驗結果見圖1、圖2。

圖1 MovieLens數(shù)據(jù)集上各算法的MAE比較

圖2 MovieLens數(shù)據(jù)集上各算法的RMSE比較
從圖1、圖2可以觀察到,在近鄰數(shù)為[10,55]的取值區(qū)間內,隨著K值的增加,CSO模型和PSO模型的MAE值和RMSE值呈現(xiàn)下降趨勢,當K>35 時,通過CSO模型得到的MAE 值均低于SO 模型和WSO 模型,當K>40 時,通過CSO 模型得到的RMSE 值均低于SO 模型和WSO 模型,當K>15 ,通過GBSO 模型得到的MAE 值和RMSE 值也均低于SO 模型和WSO 模型,這表明了相似用戶的選擇增加了預測的準確度,考慮用戶相似度的算法得到MAE 值和RMSE 值優(yōu)于原始算法,這是由于原始算法未考慮用戶相似度問題,導致其在稀疏數(shù)據(jù)集中僅依靠用戶對項目的評分的有限信息進行評分預測,實際情況中,相似的用戶的推薦采納度更高,引入用戶相似度能充分利用來自相關用戶的反饋信息,有效過濾掉不相關用戶對預測結果的影響,進一步保證預測的可靠性,提高算法整體推薦質量,且整體趨勢與推薦算法隨著近鄰數(shù)的增加,MAE 值和RMSE 值減小大體一致;此外,GBSO模型的MAE值和RMSE值隨著近鄰數(shù)的增加,其曲線呈現(xiàn)出先下降后緩慢上升的趨勢,說明如果選擇的相似用戶的比例太大或太小,會影響預測的準確性。
另外,通過比較圖1、圖2 還可以觀察到,在相同的最近鄰數(shù)目時,隨著K值的增多,本文提出的利用均衡接近度灰關聯(lián)方法衡量用戶之間的相似性得到的MAE值和RMSE 值趨于穩(wěn)定的更早,即收斂速度更快,實驗結果優(yōu)于CSO 模型,體現(xiàn)了均衡接近度灰關聯(lián)方法在貧信息系統(tǒng)中的優(yōu)勢,對提高推薦精度具有積極意義。
實驗2 在Epinions 數(shù)據(jù)集上,分別進行MAE 和RMSE 值的計算,其中,設當前用戶的近鄰數(shù)K=10,20,30,…,100。為了便于將實驗結果與MovieLens 數(shù)據(jù)集上的實驗結果進行對比,設置實驗環(huán)境與實驗1相同。SO 算法和WSO 算法在折線圖上也表現(xiàn)為一條直線,無變化趨勢。各算法實驗結果見圖3、圖4。

圖3 Epinions數(shù)據(jù)集上各算法的MAE比較

圖4 Epinions數(shù)據(jù)集上各算法的RMSE比較
通過圖3、圖4 可以看出,在Epinions 數(shù)據(jù)集上,隨著K值的增加,CSO 模型和PSO 模型的MAE 值和RMSE值都呈現(xiàn)下降趨勢,這兩種模型在該數(shù)據(jù)集上的下降趨勢要比在MovieLens數(shù)據(jù)集上的緩慢,但整體趨勢與MovieLens數(shù)據(jù)集是一致的。由于Epinions數(shù)據(jù)集更加稀疏,各算法計算得到的MAE 值和RMSE 值在相同最近鄰居數(shù)目時都比MovieLens數(shù)據(jù)集中的值要大,但是數(shù)據(jù)變化穩(wěn)定性卻優(yōu)于MovieLens數(shù)據(jù)集。
此外,在該數(shù)據(jù)集上,CSO 模型得到的MAE 值和RMSE值均高于SO模型和WSO模型,實驗結果誤差較大,推薦性能遠遠低于MovieLens 數(shù)據(jù)集,驗證了在稀疏性較大的數(shù)據(jù)集上,通過余弦相似度來計算用戶相似度容易受到個別異常點的影響,數(shù)據(jù)丟失和信息失真情況更嚴重。而本文提出算法的MAE值和RMSE值在不同最近鄰數(shù)目時,均低于其余三種算法,推薦效果更好,由此可知,本文提出的算法受數(shù)據(jù)稀疏性影響較小,在數(shù)據(jù)稀疏性較大的情況下也能得到較穩(wěn)定的推薦結果。另外,在Epinions數(shù)據(jù)集上所提出的算法的收斂速度也比MovieLens數(shù)據(jù)集快,再次說明在數(shù)據(jù)稀疏情況下所提出的算法可以獲得較好的穩(wěn)定性。
實驗3 以上兩組實驗有效驗證了所提出的算法可以在貧信息系統(tǒng)中有效提高算法推薦質量,為了進一步分析所提出算法的時間性能,在MovieLens數(shù)據(jù)集將其與原始Slope One 算法對用戶推薦的平均耗時進行了對比分析,本文以25個近鄰用戶數(shù)量為準,實驗結果如圖5所示。

圖5 各算法平均耗時比較
通過圖5可知,改進算法的用戶推薦耗時在一定程度上略高于原始算法,主要是由于篩選用戶近鄰集合這一步驟增加了算法復雜度,但由于經(jīng)過近鄰集合過濾的相關用戶數(shù)遠小于全局用戶數(shù),所以算法總體上的時間性能差別不大。
以上三組實驗結果表明,利用均衡接近度衡量用戶相關性得到的實驗結果在推薦準確度上都優(yōu)于原始SO、WSO 算法以及CSO 算法,雖然所提出算法的運行時間相比原始算法偏高,但總體來說差別較小。而且本文提出的基于均衡接近度灰關聯(lián)的Slope One 算法受數(shù)據(jù)稀疏程度的影響較小,在K值較小的區(qū)間中MAE值和RMSE值也比其他算法小很多,且均低于其他算法的最低值,預測評分也更加準確,具有明顯的特征,推薦質量提高情況較好。
針對Slope One 算法沒有考慮用戶相似性而導致推薦準確率不高的問題,本文提出了融合均衡接近度灰關聯(lián)的GBSO算法。最后的實驗結果表明:通過計算用戶相似度,考慮近鄰用戶對預測結果的影響可以有效提高算法的推薦準確率;均衡接近度灰關聯(lián)方法可以充分測量灰關聯(lián)因子序列間點的相關性,克服傳統(tǒng)相似度方法的缺點,在貧信息系統(tǒng)中有效提高了推薦質量。未來研究工作將進一步考慮優(yōu)化模型離線處理用戶近鄰,提高算法運算實時性,在提高推薦效果的同時更好地滿足用戶偏好。