基于時間衰減的物品相似度協同推薦算法改進

陳昕宇 楊帆

摘? 要：推薦系統作為信息過濾技術的典型代表，是目前解決信息過載問題的重要實現手段。其中協同過濾算法是目前推薦系統中應用最廣泛的推薦算法之一。基于物品的協同過濾推薦算法，實質上是在鄰近相似度計算的基礎上，根據用戶的歷史行為特征，給用戶推薦與用戶之前喜歡物品相似物品的過程。文章在傳統的基于物品推薦的協同算法基礎上，針對用戶-物品評分矩陣以及數據處理時可能存在的數據稀疏性問題，輔以時間衰減函數與修正的夾角余弦，對傳統物品相似度計算方法做出改進，經過實驗證明，基于時間衰減的物品相似度協同推薦算法可提高推薦結果準確性。

關鍵詞：時間衰減;物品相似度;協同過濾推薦;相似度計算;推薦準確性

Abstract：The recommended system，as a typical representative of the information filtering technology，is an important one of realization methods. The collaborative filtering algorithm was applied most extensively compared with other algorithms. The collaborative filtering algorithm based on items and similarity calculation between item scores of uses is a process which recommends users their similar items liked by users before with their history behavior characteristics. Based on the traditional collaborative algorithm on item recommendation，aiming at the problem of data sparsity in user item scoring matrix and data processing，this paper improves the traditional method of calculating item similarity with the help of time decay function and modified cosine，experimental results show that the collaborative recommendation algorithm based on time decay can improve the accuracy of recommendation results.

Keywords：time decay;item similarity;collaborative recommendation;similarity calculation;recommendation accuracy

0? 引? 言

伴隨著互聯網用戶的增多、網絡互聯技術的發展，網絡帶給了人們許多便利，而在享受便利的同時，我們也會被網絡中各種各樣、不計其數的信息困擾。面對信息過載問題，推薦系統應運而生，其中的核心便是推薦算法，一個推薦系統的推薦效果、推薦性能和推薦準確性，很大程度上受算法的影響。常用的推薦算法有：協同過濾推薦算法（Collaborative Filtering Recommendation）、內容推薦算法（Content-based Recommendation）[1]、相似性推薦算法（Simi-larity Recommendation）[2]、關聯規則推薦算法（Association Rule Based Recommendations）[3]。

筆者一直從事Python算法方面的研究工作，本文的研究是基于物品的協同過濾算法。傳統的基于物品的協同過濾算法主要依賴于用戶的行為特征，也就是用戶-物品評分矩陣，來計算物品間的相似程度和用戶對物品的喜好程度，進而為用戶推薦與用戶之前喜歡的物品相似的物品。但是在傳統的算法中存在很多問題：數據處理問題、算法過于依賴用戶-物品評分矩陣，以及在現如今推薦系統個性化等問題。本文會針對這些問題，在計算物品相似度的基礎上改進計算方法，使計算結果準確性增加，并加入時間因子增強推薦系統個性化服務[4，5]。

本文接下來內容組織如下：第1部分主要介紹傳統的基于物品的協同過濾推薦算法;第2部分介紹了本文提出了改進的協同過濾算法的主要思想及處理流程;第3部分在改進的算法的基礎上，進行實驗驗證;第4部分對全文總結。

1? 基于物品的協同過濾算法

基于物品的協同過濾推薦算法的原理和基于用戶的協同過濾推薦算法相似，在計算時計算的是物品之間的關系，而不是用戶之間的關系，從物品本身出發，基于用戶對物品的偏好找到相似的物品，然后利用K個最近鄰居物品的加權來預測當前用戶對這K個鄰居物品的喜好程度，從而將喜好程度高的若干個物品推薦給用戶。基于物品的協同過濾推薦算法實現主要有兩個核心部分：計算物品之間的相似度和計算推薦結果完成向用戶推薦。

1.1? 算法實現流程

下載相關數據集，對初始的數據進行數據處理，分離出用戶-物品評分表、物品、用戶屬性表等數據文件;選擇基于物品的協同過濾作為算法，構建模型;根據用戶對物品評分數據文件，建立用戶物品倒排表，從倒排表中找出不同用戶對不同物品的行為記錄，并構建物品同現矩陣;計算物品（item）之間的相似度，通過計算出的相似度，得到物品之間的相似度矩陣，再對每個用戶構建評分矩陣;得到物品的相似度矩陣之后，ItemCF通過公式計算用戶對物品的感興趣程度，返回用戶最可能喜歡的物品。

1.2? 物品相似度計算

相似度計算在數據挖掘和推薦系統中有著廣泛的應用場景。主要常見的相似度計算方法有：歐幾里得距離、曼哈頓距離[6]、切比雪夫距離[7]、馬氏距離[8]、夾角余弦距離、杰卡德距離。不同的計算方法有著不同的使用環境和優缺點，而在基于物品的協同過濾中，主要使用歐幾里得、余弦相似度、皮爾遜相似度、杰卡德相似度。

1.2.1? 修正的余弦相似度

余弦相似度只計算向量的夾角，但是在數值計算時，向量夾角只能表示兩向量在方向上的差距，并不能表示實際差距。特別在將目標映射到多維數值坐標中進行運算時，如果同一夾角的兩個向量數值相差很大，將會出現計算偏差，所以本文采用從傳統余弦相似度演變來的修正余弦相似度，并在此修正余弦相似度基礎上，進行物品相似度改進計算。修正的余弦相似度計算，是對用戶評分過的所有項目進行去中心化，從而減小用戶對物品過好或過壞的評分所帶來的影響，提高了推薦準確性。修正的余弦相似度計算公式[9]如下：

此修正的余弦相似度計算公式，是傳統余弦與皮爾森系數的結合，其中Ru，i和Ru，j表示用戶u對物品i，j的評分， 表示的是用戶u已評級項目的平均值，即計算時未被評級的項目不采取置0而是直接忽略。

1.2.2? 杰卡德相似度

杰卡德相似性系數[10]表示為集合中樣本集交集個數和樣本集并集個數的比值。與其他傳統相似性計算公式相比，杰卡德算法彌補了余弦相似度可能忽略其他信息量以及數據稀疏性過高的不足。本文在引用杰卡德相似性系數時，在原有式子上做出了一點改變，得到了式（2）所示的加權的杰卡德相似系數計算公式。

2? 基于物品相似度的改進

2.1? 加入時間因子

如今的推薦系統在個性化服務方面，必須具有實時性，而時間因子便能很好地體現出時間效應這方面。由于用戶最近的行為最能表達用戶當前的興趣，所以在相似度計算時加入時間衰減函數[11]。時間衰減函數又多種形式，本文中的時間衰減函數公式如下：

其中tui和tuj分別表示用戶u對物品i和j產生的行為時間。b為時間因子，在這里取b=0.5。

2.2? 算法改進步驟

根據文中提出的問題及對問題的分析，本文提出一種基于物品相似度計算改進的推薦算法，算法步驟如下：

第一步：輸入物品-用戶集，并且進行預處理來建立物品-用戶的倒排表;

第二步：產生物品之間的共現矩陣C[i][j]，表示物品i與j被不同用戶評分的矩陣;

第三步：根據用戶-物品評分矩陣計算物品相似度。本文的相似度計算在修正余弦相似度的基礎上融合杰卡德相似性[12]和時間衰減函數，在填補用戶-物品評分數據稀疏、個性化推薦服務方面，提高了推薦結果準確性，聯系式（1）、式（2）、式（3）得物品相似度計算公式如下：

第四步：返回推薦結果。

3? 實驗數據與結果分析

3.1? 實驗數據

本文采用推薦系統中常用的MovieLens數據集，下載地址為http：//files.grouplens.org/datasets/movielens，其中movies.dat記錄每部電影所屬類型，文件rating.dat記錄了用戶對電影評分數據。本文使用的是其中一個較小的數據集，里面含有6 040個用戶對3 900部電影的1 000 209條評分記錄，評分在1至5分之間。數據集隨機分為測試集和訓練集兩部分，訓練集隨機分配80%數據，測試集隨機分配20%數據。

3.2? 實驗環境

硬件環境：Windows 10（64位）操作系統，內存4G，2.5 GHz Intel Core i5-7200U CPU。

軟件環境：Python 3.8，Pycharm集成開發環境，MySQL 8.0.19，Navicat Premium 12。

3.3? 評估標準

實驗以推薦準確率為評估標準，準確率（Precision）表示的是在所有預測為真陽（TP）和假陽（FP）的樣本中有多少樣本是真陽（TP）。準確率可以用TP/（TP+FP）表示，其意義為真正的正例占總正例的比重：

檢驗算法的標準還有召回率（Recall）和F-measure值（又稱F-score）是一種統計量，是精確率和召回率的加權調和平均，召回率公式如下：

3.4? 實驗結果分析

按照上述式（5）（6）（7）計算在不同K值下三種算法的精確率、召回率和F-measure值。表1表示三種算法在K值范圍5～30之間，評估標準準確率的平均值;表2表示三種算法在K值范圍5～30之間，評估標準召回率的平均值;表3表示三種算法在K值范圍5～30之間，評估標準F-measure的平均值。

本文稱改進后的算法為Nitem-CF，在本小節中，Nitem-CF算法會和傳統的Item-CF算法、修正的余弦相似度算法，以推薦準確率為評估標準做對比實驗。為方便起見，在文中以Item-CF*代表修正的余弦相似度算法。圖1是在K值（近鄰用戶個數）不同，物品返回數為20的條件下，對三種不同算法得出的不同數據，作出準確率對比折線圖（圖1折線圖中，只可以參考走勢，具體數據參照表1）。

從圖1中我們可以清晰地看到改進后的算法準確率要高于傳統的余弦相似度算法和修正的余弦相似度算法。

4? 結? 論

本文在傳統基于物品的協同過濾算法上，對物品相似度計算方法做了一些改進，在修正的余弦相似度的基礎上，針對用戶-物品評分矩陣可能會存在的數據缺失、數據集稀疏性高、用戶活躍度過高等，影響用戶-物品評分矩陣，進而影響推薦結果的問題，本文改進的算法在計算物品之間相似度時，融合了加權后的杰卡德相似性，并在追求個性化的同時，引進時間衰減函數，突顯個性化推薦系統時效性。在實驗過程中，本文采用的數據集較小，而且實驗數據集單一，不能保證在其他環境下不同數據集適應此種算法。因此文中算法需要進一步進行擴展性行為實驗，研究此算法能應用的場景。

參考文獻：

[1] 楊凱，王利，周志平，等.基于內容和協同過濾的科技文獻個性化推薦 [J].信息技術，2019，43（12）：11-14.

[2] 韓志俊.基于關聯規則優化的協同過濾混合推薦算法研究 [D].銀川：寧夏大學，2018.

[3] VUZA D T，VLADESCU M. Solving an EMC/EMI problem occurred inside a complex programmable logic device [C]//Electronics Technology（ISSE），Proceedings of the 2014 37th International Spring Seminar on. S.l.：s.n.，2014：390-394.

[4] 劉源.基于特征距離和時間效應的上下文感知推薦技術研究 [D].北京：北京郵電大學，2019.

[5] 張宇航，姚文娟，姜姍.個性化推薦系統綜述 [J].價值工程，2020，39（2）：287-292.

[6] 方樂笛，李順東，竇家維.曼哈頓距離的保密計算 [J].密碼學報，2019，6（4）：512-525.

[7] KISEOK LEE. Chebyshev collocation method for the constant mobility Cahn-Hilliard equation in a square domain [J].Applied Mathematics and Computation，2020：370.

[8] MOHAMMAD M N，MOHAMMAD A M，RASOOLZADEGAN A. Software defect prediction using over-sampling and feature extraction based on Mahalanobis distance [J].Journal of Supercomputing，2020，76（1）：602-635.

[9] 唐積益.推薦系統中相似度計算方法的研究 [D].鎮江：江蘇科技大學，2015.

[10] 高文堯.基于協同過濾的推薦算法研究 [D].廣州：華南理工大學，2016.

[11] 李世偉.基于協同過濾算法的推薦系統研究與應用 [D].北京：北京工業大學，2017.

[12] 袁煦聰.基于長尾理論的物品協同過濾推薦算法研究 [D].淮南：安徽理工大學，2019.

作者簡介：陳昕宇（1998.05—），男，漢族，湖北棗陽人，本科，學士學位，研究方向：推薦系統、計算機軟件開發;楊帆（1980.06—），女，漢族，湖北武漢人，博士，教授，研究方向：推薦系統、電子商務。