基于評分填充和時間的加權Slope One算法

劉金梅，舒遠仲，張尚田

(南昌航空大學 信息工程學院，江西 南昌 330063)

0 引 言

隨著互聯網的不斷發展，產生的數據量越來越多，面對海量的數據，人們很難準確而快速地找到自己感興趣的物品，為解決此問題，推薦系統應運而生[1]。推薦算法是推薦系統的核心，常用的推薦算法是協同過濾算法[2]，該文研究的加權slope one算法[3-4]是協同過濾算法的一種，它計算簡潔、容易實現，但是在數據稀疏情況下算法預測效果仍然較差，因此許多學者針對數據稀疏性進行了研究。研究者使用了數據填充[5]、隨機游走[6]、神經網絡[7]、矩陣分解[8]等技術，以提高推薦算法的精度。最簡單的方法是對評分矩陣中的空缺值進行填補[5]。夏建勛等人[9]采用數據的平均值、中位數和眾數三種方式進行填充，雖然可以緩解數據稀疏問題，但是這些填充方法沒有考慮用戶和項目本身的特性；李歡[10]提出一種基于項目相似度的協同過濾算法，實驗結果證明可以有效緩解數據稀疏問題；馬鐵民等人[11]提出一種結合用戶相似度，并采用隨機游走技術進行推薦的方法，可以提高推薦精度；龔敏等人[12]首先根據用戶特征進行聚類，再使用slope one算法預測并填充數據，最后根據填充數據進行推薦，可有效緩解數據稀疏性；王永康等人[13]使用融合時間信息的隱語義模型對原始評分數據進行填充，同時時間因素也能反映用戶的興趣愛好變化，提高了推薦精度。

上述針對數據稀疏性問題進行的研究都取得了不錯的效果，但是該文考慮到用戶評分易受到主觀性以及環境等其他因素的影響，導致用戶對項目的評分或高或低甚至沒有評分，此種情況下用戶的評分無法準確地衡量用戶對項目的偏好，而項目的屬性一直都比較穩定，因此可以根據用戶對項目屬性的偏好間接體現用戶對項目的喜好程度，故提出一種新的評分矩陣填充方法。基于填充后的評分矩陣，又考慮到用戶興趣愛好隨時間會發生變化，于是引入時間因子，提出一種融合用戶屬性偏好特征和時間因子的加權slope one算法。

1 算法設計

1.1 填充用戶-項目評分矩陣

隨著數據量的不斷增大，用戶-項目評分矩陣變得越來越稀疏，面對數據的稀疏性，常用數據的平均數、中位數和眾數等來填充用戶對項目未評分數據[9]。該文提出一種新的用戶對項目未評分數據的填充方法，主要是通過用戶對項目的偏好以及用戶對項目的平均分進行加權填充未評分項目。具體方法如下：

設總共有m個用戶U={U1,U2,…,Um}和n個項目I={I1,I2,…,In}組成的用戶-項目評分矩陣Rmn，則用戶-項目評分矩陣如式(1)所示:

(1)

矩陣Rmn為m行n列的用戶項目評分矩陣，其中用戶Ui對項目Ij的評分用Rij表示，若用戶對項目沒有評分，則其值為0。評分反映了用戶對項目的偏好程度。

由式(1)用戶對項目的評分，計算每個用戶對項目的平均評分，則平均評分計算公式如下：

(2)

其中，Rui_avg表示用戶u對項目i的平均評分；sum(Rui)表示用戶u對項目i的評分總和；num(Rui)表示用戶u對項目i評分大于0的項目總數。

將用戶對項目的平均評分轉化成對角矩陣，如式(3)所示：

(R_avg)mm=diag(Rui_avg)

(3)

其中，m為用戶數量，對角線上的值為用戶對項目的平均評分。

每個項目都有各自的屬性類型，設有n個項目，項目屬性類型共有k個，則構建項目-屬性矩陣，如下式所示：

(4)

其中，Tnk為項目-屬性矩陣，矩陣中數值Tij取值為0或1，若項目i屬于屬性類型j，則Tij取值為1；否則，Tij為0。

根據項目-屬性矩陣可以計算出用戶對項目屬性的偏好值，計算公式如下所示：

(5)

其中，num(Tuj)表示用戶u評價j類項目的數量；num(Iu)表示用戶u已評分的所有項目數量。

當某個項目非常流行時，大多數人會對該項目評高分，而此時項目屬性類別反映的則是該項目的流行度，并不能由此得出用戶對項目的個性化偏好，因此，需要降低高頻率屬性對項目屬性的影響，于是引入權重因子優化項目-屬性矩陣。權重因子計算公式如下所示：

(6)

其中，num(pi)表示用戶喜歡的具有屬性pi的項目數量；sum(num(pi))表示所有用戶喜歡的具有屬性pi的項目數量的總數。

將權重因子轉化為對角矩陣，公式如下所示：

(W)kk=diag(Wpi)

(7)

將式(7)中的權重因子與原始的項目-屬性矩陣(式(4))相結合即得到加權項目-屬性矩陣，公式如下所示：

(8)

由用戶對項目屬性偏好值(式(5))以及加權項目屬性矩陣，可以得出用戶對項目的偏好值，計算公式為：

P(u,i)=(Puj)mk*Tnk'

(9)

通過用戶對項目的偏好值(式(9))乘以用戶對項目的平均評分(式(2))來填充原始用戶-項目評分矩陣，填充后的評分矩陣可以有效緩解數據稀疏性。

1.2 屬性興趣特征向量

傳統的協同過濾算法僅僅考慮用戶評分，根據評分矩陣區分用戶對項目的喜愛程度，但是在數據比較稀疏時，無法準確地知道用戶的偏好。日常生活中，用戶興趣特征主要體現在一種或者多種項目類別上，也就是對于項目或者商品用戶具有類別屬性偏好[14]。用戶的評級有主觀性，并且很容易受到環境等其他因素的影響，用戶會對項目給予較高或較低的評分，最終導致評分數據的不真實；而每個項目都有自身的屬性特征，并且項目屬性特征比較穩定，因此，可以通過構建項目-屬性矩陣代替原始用戶-項目評分矩陣，通過項目-屬性矩陣計算用戶的偏好，相比于原始的評分矩陣可以更好地反映用戶在多方面的興趣特征，可以有效改善數據的稀疏性，可以獲得較準確的用戶相似度，從而能夠提高推薦精度。

由式(5)計算出的用戶對項目屬性的偏好度，構建用戶-屬性興趣矩陣，如下式所示：

(10)

其中，Pmk表示用戶對項目屬性的興趣矩陣，公式中的值為m個用戶對項目類型k的偏好值，偏好值越大表明用戶對該類型項目越感興趣。

通過用戶對項目屬性的興趣矩陣，將用戶對項目屬性的興趣矩陣轉化為用戶對項目屬性的特征向量。若用戶u對項目i有評分，而項目i所屬類型有k類，如何求出用戶u對項目i屬性的偏好值。可以根據用戶u對k類偏好值的總和求得用戶u對項目i屬性的偏好度，如式(11)所示：

(11)

其中，num(pi)表示項目i所屬類型的數量。

用戶u對項目i屬性的偏好度Pui即為屬性興趣特征向量，與原始用戶-項目評分相比，其中包含數值0的數量更少。在共同評分很少甚至沒有時，可以通過屬性興趣特征向量計算用戶間的相似度，相比于原始評分數據，可以有效緩解數據稀疏性問題。

用戶對項目的偏好表述了用戶在項目屬性維度上的興趣愛好，相比于傳統的用戶-項目評分矩陣，更能夠體現出用戶對項目的偏好。在數據集比較稀疏時，傳統的用戶-項目評分矩陣中含有的數值0更多，不能精確地體現用戶的偏好；而在用戶-項目屬性矩陣中，即使用戶對此項目沒有評分，但是從項目所屬類型上也可以反映用戶對此項目的偏好，可以較好地緩解數據稀疏性，提高推薦的精確度。

1.3 時間影響函數構建

人們的興趣愛好不是一成不變的，用戶興趣會隨著時間發生改變，因此，時間變化會對預測結果產生影響。許多學者對時間因素進行了研究，因此衡量時間變化的曲線有很多，最早的遺忘曲線是艾賓浩斯遺忘曲線，如圖1所示。該條曲線能夠體現出人的記憶隨著時間變化的遺忘程度。其數學公式如下所示：

(12)

其中，b表示記憶內容保存量，t為時間間隔，c和k為常數，c=1.25，k=1.84。

圖1 遺忘曲線

從圖1可以看出，用戶的遺忘程度隨著時間的推移先快后慢，是一種非線性的函數。Ding等人[15]于2005年首次根據遺忘曲線提出時間加權函數f(t)，用來表述時間不同，產生的結果也不相同。時間加權函數f(t)的計算公式如下：

f(t)=e-αt

(13)

其中，f(t)的取值范圍為(0,1]，參數α控制信息的衰減程度。

在推薦算法中，用戶對項目的興趣會隨著時間的變化而變化，而根據前人的研究可知，用戶對項目的興趣變化規律符合遺忘曲線的變化規律，因此可以根據遺忘曲線來擬合時間衰減函數。

該文所使用的時間衰減函數在式(13)的基礎上進行改進，用戶的興趣愛好會隨著時間在改變，用戶在購買某種商品時，更傾向購買與他近期興趣愛好相似的物品，對久遠的物品可能興趣度較低，時間越近越能反映用戶當前的興趣愛好。但是在最近較短的一段時間段內，用戶的興趣愛好變化程度較小，往往可以認為用戶在此時間段內興趣愛好是相同的，同樣在這段時間內用戶興趣的衰減程度是一樣的。于是，將用戶評分時間分為一個個時間段，每一個時間段代表一個時間窗口T，引入時間窗口來修正時間衰減函數，公式如下所示：

(14)

其中，tui表示用戶u對項目i的評分時間；t0表示用戶u最初開始評分時間；T表示時間保持周期即時間窗口。利用時間衰減函數對原始評級矩陣進行處理，解決了原始評級的時效性問題。

1.4 改進的加權slope one算法

傳統加權slope one算法是通過計算項目間評分差異值，再根據評分差異值以及用戶的歷史評分來預測用戶對未評分項目的評分，沒有考慮用戶以及項目對預測結果的影響，因此該文對加權slope one算法進行改進。

(15)

在新的加權評分矩陣中，f'(t)Rij為用戶i對項目j的時間加權評分值，相比于原始的評分矩陣，添加了時間因素更能夠體現用戶的興趣隨時間是動態變化的。根據新的加權評分矩陣計算用戶對項目類型的偏好值，從而獲得用戶對項目的偏好度，將用戶對項目的偏好度構建成用戶-屬性興趣矩陣，如式(10)所示。

在填充的用戶-項目評分數據下，用戶相似度使用皮爾遜相關系數進行計算，皮爾遜相似度計算公式如下：

Simpcc(u,v)=

(16)

當用戶共同評分數量很少甚至沒有時，此時新構建的用戶-屬性興趣矩陣Pmk相比原始用戶-項目評分矩陣Rmn更能夠體現用戶間的相似度，因此在新構建的用戶-屬性興趣矩陣Pmk中，使用余弦相似度計算用戶間相似度，計算公式如下：

(17)

其中，Puv表示屬于同一屬性類型的用戶數量；Pui表示用戶u對屬性類型i的偏好值；Pvi表示用戶v對屬性類型i的偏好值。

將式(16)和式(17)計算出的用戶相似度通過參數λ進行融合得到最終的用戶相似度，公式如下：

Sim(u,v)=λSimpcc(u,v)+(1-λ)Simpu(u,v)

(18)

由式(18)中獲得的最終用戶相似度，選取前K個相似度作為目標用戶的鄰居，再根據鄰居對目標項目的評分預測用戶對目標項目的評分。原始的加權slope one預測公式如下：

(19)

在式(19)的基礎上，該文考慮時間對預測結果的影響，從而用時間衰減函數優化預測評分公式，新的預測公式如下：

(20)

1.5 算法描述

算法詳細步驟如下：

輸入：用戶-項目評分矩陣Rmn，鄰居數K。

輸出：目標用戶u對項目i的預測評分。

步驟1：創建用戶-項目評分矩陣Rmn，項目-屬性矩陣Tnk，時間衰減函數f'(t)，并根據給定的數據集填充矩陣Rmn，Tnk。

步驟2：根據評分矩陣Rmn，使用式(2)計算用戶對項目的平均評分。

步驟3：根據項目-屬性矩陣Tnk，使用式(5)、式(6)分別計算用戶u對項目屬性偏好以及高頻率屬性所占全部屬性的權重，并用權重優化項目屬性矩陣，即通過式(8)得到加權項目-屬性矩陣。

步驟4：根據用戶對項目屬性偏好值以及加權項目-屬性矩陣，使用式(9)計算用戶u對項目i的偏好值，并結合平均評分來填充用戶對項目未評分矩陣。

步驟7：由步驟4得出的填充矩陣，使用式(16)計算用戶相似度；在矩陣Pmk中，使用式(17)計算用戶相似度，將兩個相似度通過式(18)進行融合得到最終用戶相似度。

步驟8：根據步驟7得到的最終用戶相似度，將相似度進行降序排列再選擇前K個作為用戶鄰居，放入鄰居集合S(K)中。

步驟9：由步驟8的鄰居集合S(K)，根據最近鄰居用戶對未知項目的評分來預測目標用戶對項目的評分，最后再將步驟1中的時間衰減函數f'(t)加入到預測公式中，最后使用式(20)預測出最終目標用戶對項目的評分。

流程如圖2所示。

圖2 算法流程

2 實驗環境及評估指標

2.1 實驗環境

本實驗在win7 64位操作系統下進行，開發使用的工具是Matlab2014a。

2.2 實驗數據集

本次實驗所使用數據集是Movielens100K數據集，此數據集是由美國明尼蘇大學GroupLens項目組提供。用戶對電影評分范圍為1～5分，評分越高表明用戶對電影越喜愛，反之，則表明用戶對電影喜愛程度較低。表1和表2列出了部分電影類別評分信息以及用戶對電影的評分信息。

表1 部分電影信息示例

本次實驗將數據集按比例8∶2隨機劃分為訓練集和測試集，根據訓練集中的數據通過預測公式預測用戶對未評分項目的評分，然后再與測試集中的評分數據進行比較，當誤差達到最小時，此時的預測效果最好，采用五折交叉驗證法進行驗證。

表2 部分用戶對電影評分時間信息

2.3 評估指標

為驗證該算法的預測效果，采用平均絕對誤差(mean absolute error，MAE)和均方根誤差(root mean square error，RMSE)來衡量。

(21)

(22)

其中，Pi為預測評分，Ti為測試集中實際評分，N為測試集中評分的總數。

3 實驗結果與分析

3.1 確定參數λ、K最優值

在填充評分矩陣中計算用戶相似度時，使用皮爾遜相關系數計算用戶間相似度；當共同評分較少或者沒有時，在屬性興趣特征矩陣中，使用余弦相似度計算用戶相似度，將兩種不同數據集中計算的相似度通過參數λ進行融合。將λ設置為[0.1，0.9]，步長為0.1，鄰居數K設置為[100，500]，步長為100進行實驗，從而確定參數λ以及K的最優值。實驗結果如圖3所示。

圖3 不同參數λ、K對預測結果的影響

從圖3可以看出，在不同鄰居數K和不同參數λ下，其預測結果也是不相同的。在鄰居數K為300時，MAE和RMSE值達到最低，再根據鄰居數K為300，尋找一個最優參數λ。從圖中可以看出，在鄰居數K為300，參數λ取值為0.8時，此時的MAE和RMSE達到最小值。因此，該文在相似度融合時將參數λ設為0.8，鄰居數K設為300，基于設置的最優參數進行下面實驗。

3.2 實驗結果對比與分析

3.2.1 填充評分矩陣與未填充評分矩陣實驗對比

針對用戶-項目評分矩陣稀疏性問題，提出一種基于改進的填充評分矩陣方法的加權slope one算法(FWSOA)。通過用戶對項目平均評分以及用戶對項目偏好來填充用戶對項目未評分數據，利用填充評分矩陣計算用戶相似度，再通過加權slope one算法預測。原始未填充評分矩陣在相似度計算時使用皮爾遜相關系數計算相似度，然后利用加權slope one算法預測。在MovieLens100K數據集進行實驗，實驗結果如圖4所示。

圖4 填充矩陣與原始矩陣的MAE和RMSE對比

從圖4可以看出，隨著鄰居數量的不斷增大，使用填充數據集進行預測的效果要好于使用原始評分數據集的預測效果，因此填充用戶-項目評分矩陣可以有效緩解數據稀疏問題。

3.2.2 時間修正評分矩陣與未用時間優化評分矩陣實驗對比

用戶興趣愛好隨著時間會發生動態變化，因此提出一種用時間修正評分的加權slope one算法(TWSOA)。該算法使用時間函數修正原始用戶-項目評分矩陣得到加權時間評分矩陣，在新的評分矩陣下，計算用戶對項目屬性興趣愛好并根據興趣愛好用余弦相似度計算用戶相似度；在原始評分矩陣下通過皮爾遜相關系數計算用戶相似度，將計算的兩個相似度通過參數λ相結合得到最終用戶相似度。相比于單獨使用皮爾遜相關系數計算相似度，融合相似度可以有效緩解在共同評分很少甚至沒有時數據稀疏性問題。在得出的融合相似度下，選擇相近的前K個作為用戶鄰居集，再根據鄰居用戶使用加權slope one算法進行評分預測，在預測評分時，引入時間函數優化預測評分公式。將TWSOA算法與未用時間修正的算法(WSOA)進行對比，實驗結果如圖5所示。

圖5 TWSOA算法和WSOA算法與MAE和RMSE關系

從圖5可以看出，使用時間優化的評分矩陣進行預測時，其預測誤差相比于原始評分矩陣小，因此，用時間修正評分矩陣不僅可以反映用戶興趣愛好隨時間是動態變化的，同時在預測評分時也可以提高預測精度。

3.2.3 不同算法實驗對比

由上述可知，實驗參數λ設置為0.8進行如下實驗，將該文提出的FTWSOA算法、FWSOA算法、TWSOA算法與文獻[16]中基于加權slope one和用戶協同過濾的推薦算法(CF_WSOA)進行對比，實驗結果如圖6所示。

圖6 不同算法實驗對比

從圖6可以看出，該文提出的算法相比于原始的基于加權slope one和用戶協同過濾的推薦算法(CF_WSOA)，預測效果均有所提高。在鄰居數為100時，使用時間優化的加權slope one算法(TWSOA)誤差比較小，隨著鄰居數的不斷增多，使用填充評分矩陣以及時間加權的加權slope one算法(FTWSOA)誤差較小；在鄰居數K取值為300時，使用FTWSOA算法預測效果達到最優；隨著鄰居數K繼續增大，使用填充評分矩陣的加權slope one算法(FWSOA)的效果相比于其他算法效果更好。

3.2.4 使用五折交叉驗證法實驗對比

基于參數λ為0.8，鄰居數K為300進行實驗，將提出的FTWSOA算法、FWSOA算法、TWSOA算法與文獻[16]中基于加權slope one和用戶協同過濾的推薦算法(CF_WSOA)進行對比，使用五折交叉驗證法驗證不同算法的結果，實驗結果如圖7所示。

從圖7可以看出，提出的算法的MAE和RMSE均小于文獻[16]中的CF_WSOA算法。

圖7 不同算法結果對比

4 結束語

通過填充評分矩陣下的加權slope one算法(FWSOA)與原始評分矩陣下的加權slope one算法對比，發現FWSOA的效果優于原始的算法；將使用時間優化的加權slope one算法(TWSOA)與未使用時間優化的算法(WSOA)進行對比，結果顯示TWSOA算法優于WSOA算法；最后，將提出的FTWSOA算法、FWSOA算法、TWSOA算法與其他算法CF_WSOA算法進行對比，在MovieLens100K數據集上進行實驗，結果表明該算法相比于其他算法在MAE和RMSE上均有所減小。