結合貢獻度與時間權重的協同過濾推薦算法

賈俊康，李玲娟

(南京郵電大學 計算機學院，江蘇 南京 210023)

0 引 言

隨著互聯網和信息技術的普及，人類全面進入web2.0時代以后，就面臨著“信息超載”[1]問題，用戶想要從海量數據中篩選出滿意的結果變得愈加艱難。因此，作為信息過濾工具的推薦系統應運而生，它能夠根據用戶的需求，快速、準確地向用戶進行有效推薦。推薦算法作為推薦系統的核心[2]，直接決定了推薦效果。主流推薦算法包括基于內容的推薦、協同過濾推薦和混合推薦三類傳統的推薦算法，以及各種與深度學習結合的推薦算法[3-4]。其中，協同過濾推薦算法是應用最為成功的推薦算法之一[5]。它又分為兩類，一類是基于模型的協同過濾，另一類是基于內存的協同過濾。后者又有基于用戶的協同過濾UserCF和基于項目的協同過濾ItemCF之分[3]。UserCF源于生活中的經驗假設：興趣愛好類似的用戶，他們對同一項目可能有著相似的喜好程度[6]，這種算法不是分析用戶之間潛在的某種關系，而是從用戶歷史行為數據信息中計算用戶相似度，從中尋找相似用戶進行推薦，思路簡單，易于實現[7]。但是這種算法至少存在三方面的問題：①未考慮時間因素，沒有將用戶不同時間的評分區別對待；②未考慮跟風用戶帶來的影響；③未考慮不同用戶對同一個項目評分差異過大帶來的影響。

由于存在以上問題，傳統的UserCF算法的推薦精度仍有待提高。為此，該文設計了一種結合貢獻度與時間權重的協同過濾推薦算法(collaborative filtering recommendation algorithm combining contribution and time weight)，命名為CTCF。該算法通過定義可信誤差閾值與貢獻度來減少不同用戶對同一項目評分差異過大對推薦結果產生的負面影響；通過在用戶相似度計算中引入擬合時間因子與貢獻度的時間權重來動態模擬用戶興趣隨時間的變化；既充分利用了傳統的UserCF算法的優勢，又避免其存在的問題，進一步提高了基于用戶的協同過濾推薦算法的精度。

1 相關技術

1.1 UserCF算法推薦過程

UserCF的推薦過程如圖1所示。

圖1 UserCF算法推薦過程

主要步驟為[8]：

①利用用戶的歷史行為數據構建用戶-項目評分矩陣；

②使用用戶相似度計算方法計算用戶相似度，并找出目標用戶的最近鄰；

③選擇最近鄰喜歡而目標用戶未評分的項目；

④預測目標用戶對第③步中得到的項目的評分，并將預測評分高(即喜歡程度高)的項目推薦給目標用戶。

1.2 評分矩陣

假設U={u1,u2,…,um}表示m個用戶，I={i1,i2,…,in}表示n個項目。用戶-項目評分矩陣可表示為Rm,n={Ru,i}，Ru,i是用戶u對項目i的評分。表1是5個用戶對6個項目的評分示例，其中“/”表示該用戶沒有對項目進行過評分，評分值為1至5的整數，數值越大表示用戶對這個項目喜好程度越高。

表1 用戶對項目的評分示例

與之對應的評分矩陣如下：

1.3 相似度計算方法

相似度的計算方法主要有余弦相似性[9]、歐幾里得相似度[10]、皮爾遜相關系數[11]等。余弦相似度是兩個評分向量夾角的余弦值。歐幾里得相似度指的是兩個點之間的真實距離。皮爾遜相關系數廣泛用于度量兩個變量之間的相關性，其計算公式如下：

sim(a,b)=

(1)

2 CTCF算法設計

該文所設計的CTCF算法的核心內容包括：可信誤差閾值與貢獻度的計算、擬合貢獻度與時間因子的時間權重的計算、用戶相似度的計算、評分的預測。

2.1 可信誤差閾值與貢獻度的計算方法設計

如前所述，傳統的UserCF算法，在計算用戶相似度時，可能會遇到不同用戶對同一項目評分差異較大的情況，例如表1中user1和user2雖然共同評分的項目占比為67.7%，但其中至少有75%的項目評分差異較大。這種不同用戶對共同項目的評分差異從一定程度上能夠反映出用戶興趣的差異，因此，在判斷當前用戶對目標用戶的價值時，應該充分考慮這種差異。該文分別定義了可信誤差閾值與貢獻度，用可信誤差閾值來計算貢獻度，依據貢獻度來評定當前用戶對目標用戶的價值大小，從而為進一步計算用戶相似度提供權重。

定義1 可信誤差閾值：是不同用戶對同一項目的評分差異的度量，計算方法如公式(2)所示：

(2)

(3)

定義2 貢獻度：是用戶間的參考價值度量，反映不同用戶的共同喜好程度高低，計算方法如公式(4)所示：

(4)

其中，t為|ga,i-gb,i|<χ的數目，|I(a)∪I(b)|為用戶a和用戶b評分項目的總數量。可以看出sup∈[0,1]，且評分相近的項目越多(即共同喜好程度越高)，貢獻度sup就越大，彼此的參考價值越高。

2.2 擬合貢獻度與時間因子的時間權重計算方法設計

如前文所述，傳統的UserCF算法忽略了用戶興趣愛好會隨時間變化這一事實[12]，由此得出的最近鄰可能并不準確。一般來講用戶近期的行為更能充分說明其目前的興趣愛好。隨著時間推移，用戶會逐漸減弱對某個項目的喜好，這種趨勢呈現出先快后慢、最后趨于穩定的特點，這與艾賓浩斯曲線[13]很相似。因此，該文進一步將貢獻度與時間因子相結合來對艾賓浩斯曲線加以改進，設計了擬合貢獻度與時間因子的時間權重，計算方法如公式(5)所示。

(5)

不難看出，該時間權重既考慮了不同用戶對同一項目評分差異過大對推薦結果的影響，又動態模擬了用戶興趣隨時間的變化。

2.3 改進的用戶相似度計算方法設計

在計算用戶相似度時，該文對皮爾遜相關系數加以改進，引入公式(5)的擬合貢獻度與時間因子的時間權重，同時考慮目標用戶a評價過的項目可能包含某用戶b評價過的全部項目(即前者是后者的超集，如表1中user2與user4)的情況，因后者不能為目標用戶提供有用的信息，將其視為跟風用戶[14]，并將目標用戶與跟風用戶的相似度置零。改進后的相似度計算方法如公式(6)所示：

sim(a,b)=

(6)

2.4 評分預測方法

計算得到目標用戶與其他用戶的相似度后，按照相似度降序排列，取前K個作為目標用戶的近鄰集，產生近鄰評價過的項目集，并用公式(7)[15]對其中目標用戶未評價的項目進行評分預測。

(7)

最后，按照目標用戶a的預測評分的降序對項目排序，取Top-N個加以推薦。

2.5 CTCF算法流程

CTCF算法的總體流程如圖2所示。

圖2 CTCF算法流程

具體步驟可描述如下：

算法：結合貢獻度與時間權重的協同過濾推薦算法。

輸入：用戶評分信息，目標用戶a，推薦結果個數N；

輸出：推薦給目標用戶a的項目列表。

Step1：首先，對用戶評分信息做預處理，用公式(8)將時間戳歸一化；其中，ti為當前時間戳，tmin為最小時間戳，tmax為最大時間戳。

(8)

然后，構建出用戶-項目評分矩陣與用戶-項目評分時間矩陣。

Step2：用公式(4)計算貢獻度sup，用公式(5)計算時間權重。

Step3：用公式(6)計算相似度矩陣，并產生目標用戶a的近鄰集以及該近鄰集已評價的項目集I，在I中去除用戶a已評價過的項目，構成I'。

Step4：用公式(7)預測目標用戶a對I'中各個項目的評分。

Step5：將預測得到的評分由高到低排序，并將前N個項目作為目標用戶a的推薦集。

3 實驗及結果分析

為了測試CTCF算法的性能，做了相關實驗。

3.1 實驗數據及環境

實驗所用的數據是MovieLens ml-100K數據集中u.data文件的數據，有943個用戶、1 652部電影、100 000個評分[16]。隨機選取其中的75%用作訓練集，剩余的25%用作測試集，用戶的評分范圍為1～5，數值越大表示用戶興趣越大。

實驗環境：CPU為Intel Core i7，主頻為2.2 GHz，內存為16 GB；操作系統是macOS 10.13；編程語言是Python3.7。

3.2 評價指標

該文采取目前比較主流的推薦算法評價指標召回率(recall)和精度(precision)來評估算法。分別用公式(9)和公式(10)進行計算。

(9)

(10)

其中，R(a)表示算法推薦給用戶a的項目集合，I'(a)表示用戶a實際喜歡的項目集合，U表示測試集中所有用戶的集合。

為了比較全面地評價算法，還采用F-Measure作為評價指標，F-Measure公式如下：

(11)

當參數α=1時，就是最常用的F1值，即：

(12)

F1的值越大表示算法的綜合表現越好。

3.3 實驗結果分析

(1)可信誤差閾值(χ)的有效性實驗。

為驗證定義的可信誤差閾值(χ)的有效性，在χ取常數(0、1、2、3、4)以及用公式(2)進行動態計算的情況下，測試CTCF算法的F1值，結果如圖3所示。

圖3 不同可信誤差閾值對F1值的影響

從圖3可以看出，隨著近鄰數的增加，F1值不斷增大，然后趨于穩定，而且采用該文定義的可信誤差閾值時，F1明顯高于其他幾種情況。

(2)CTCF算法總體性能實驗。

為驗證CTCF算法能有效提升推薦質量，將其與采用皮爾遜相似度的UserCF、使用了改進皮爾遜相似度的文獻[17]的算法作對比，統計三種算法的precision、recall和F1值，結果如圖4至圖6所示。

圖4 不同近鄰數N對應的precision

圖5 不同近鄰數N對應的recall

圖6 不同近鄰數N對應的F1

從圖4和圖5可以看出，不同近鄰數下，CTCF算法對recall和precision有了明顯的提升。從圖6可以看出，CTCF算法的F1值始終高于另外兩種算法。

時間復雜度也是評價一個算法優劣的重要指標，CTCF算法與UserCF類似，最耗時的階段是用戶相似度計算，時間復雜度是O(n2)，n為用戶數；文獻[17]算法的時間復雜度是O(n3)。為對比三種算法的時間開銷，進行了相關實驗，結果如圖7所示。

由圖7可知，CTCF算法與傳統的協同過濾算法耗時相近，遠遠小于文獻[17]算法。綜上，CTCF算法在不增加時間復雜度的前提下，提升了推薦精度。

圖7 三種算法對應不同近鄰數N的時間開銷

4 結束語

以提高推薦精度為目標，該文設計了一種結合貢獻度與時間權重的協同過濾算法CTCF，該算法對傳統的基于用戶的協同過濾推薦算法做了改進，在用戶相似度計算中引入貢獻度與時間因子，降低了不同用戶對相同項目評分差異過大帶來的影響，同時在一定程度上增大了用戶近期反饋行為的權重，對用戶早期的行為信息權重進行了衰減，客觀地反映了用戶興趣隨時間的動態變化。在MovieLens數據集上與類似算法的對比實驗結果表明，設計的CTCF算法能有效提高推薦質量。