基于時(shí)間衰減的物品相似度協(xié)同推薦算法改進(jìn)

陳昕宇 楊帆

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

關(guān)鍵詞：時(shí)間衰減;物品相似度;協(xié)同過濾推薦;相似度計(jì)算;推薦準(zhǔn)確性

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? 引? 言

伴隨著互聯(lián)網(wǎng)用戶的增多、網(wǎng)絡(luò)互聯(lián)技術(shù)的發(fā)展，網(wǎng)絡(luò)帶給了人們?cè)S多便利，而在享受便利的同時(shí)，我們也會(huì)被網(wǎng)絡(luò)中各種各樣、不計(jì)其數(shù)的信息困擾。面對(duì)信息過載問題，推薦系統(tǒng)應(yīng)運(yùn)而生，其中的核心便是推薦算法，一個(gè)推薦系統(tǒng)的推薦效果、推薦性能和推薦準(zhǔn)確性，很大程度上受算法的影響。常用的推薦算法有：協(xié)同過濾推薦算法（Collaborative Filtering Recommendation）、內(nèi)容推薦算法（Content-based Recommendation）[1]、相似性推薦算法（Simi-larity Recommendation）[2]、關(guān)聯(lián)規(guī)則推薦算法（Association Rule Based Recommendations）[3]。

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

本文接下來內(nèi)容組織如下：第1部分主要介紹傳統(tǒng)的基于物品的協(xié)同過濾推薦算法;第2部分介紹了本文提出了改進(jìn)的協(xié)同過濾算法的主要思想及處理流程;第3部分在改進(jìn)的算法的基礎(chǔ)上，進(jìn)行實(shí)驗(yàn)驗(yàn)證;第4部分對(duì)全文總結(jié)。

1? 基于物品的協(xié)同過濾算法

基于物品的協(xié)同過濾推薦算法的原理和基于用戶的協(xié)同過濾推薦算法相似，在計(jì)算時(shí)計(jì)算的是物品之間的關(guān)系，而不是用戶之間的關(guān)系，從物品本身出發(fā)，基于用戶對(duì)物品的偏好找到相似的物品，然后利用K個(gè)最近鄰居物品的加權(quán)來預(yù)測(cè)當(dāng)前用戶對(duì)這K個(gè)鄰居物品的喜好程度，從而將喜好程度高的若干個(gè)物品推薦給用戶?；谖锲返膮f(xié)同過濾推薦算法實(shí)現(xiàn)主要有兩個(gè)核心部分：計(jì)算物品之間的相似度和計(jì)算推薦結(jié)果完成向用戶推薦。

1.1? 算法實(shí)現(xiàn)流程

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

1.2? 物品相似度計(jì)算

相似度計(jì)算在數(shù)據(jù)挖掘和推薦系統(tǒng)中有著廣泛的應(yīng)用場(chǎng)景。主要常見的相似度計(jì)算方法有：歐幾里得距離、曼哈頓距離[6]、切比雪夫距離[7]、馬氏距離[8]、夾角余弦距離、杰卡德距離。不同的計(jì)算方法有著不同的使用環(huán)境和優(yōu)缺點(diǎn)，而在基于物品的協(xié)同過濾中，主要使用歐幾里得、余弦相似度、皮爾遜相似度、杰卡德相似度。

1.2.1? 修正的余弦相似度

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

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

1.2.2? 杰卡德相似度

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

2? 基于物品相似度的改進(jìn)

2.1? 加入時(shí)間因子

如今的推薦系統(tǒng)在個(gè)性化服務(wù)方面，必須具有實(shí)時(shí)性，而時(shí)間因子便能很好地體現(xiàn)出時(shí)間效應(yīng)這方面。由于用戶最近的行為最能表達(dá)用戶當(dāng)前的興趣，所以在相似度計(jì)算時(shí)加入時(shí)間衰減函數(shù)[11]。時(shí)間衰減函數(shù)又多種形式，本文中的時(shí)間衰減函數(shù)公式如下：

其中tui和tuj分別表示用戶u對(duì)物品i和j產(chǎn)生的行為時(shí)間。b為時(shí)間因子，在這里取b=0.5。

2.2? 算法改進(jìn)步驟

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

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

第二步：產(chǎn)生物品之間的共現(xiàn)矩陣C[i][j]，表示物品i與j被不同用戶評(píng)分的矩陣;

第三步：根據(jù)用戶-物品評(píng)分矩陣計(jì)算物品相似度。本文的相似度計(jì)算在修正余弦相似度的基礎(chǔ)上融合杰卡德相似性[12]和時(shí)間衰減函數(shù)，在填補(bǔ)用戶-物品評(píng)分?jǐn)?shù)據(jù)稀疏、個(gè)性化推薦服務(wù)方面，提高了推薦結(jié)果準(zhǔn)確性，聯(lián)系式（1）、式（2）、式（3）得物品相似度計(jì)算公式如下：

第四步：返回推薦結(jié)果。

3? 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果分析

3.1? 實(shí)驗(yàn)數(shù)據(jù)

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

3.2? 實(shí)驗(yàn)環(huán)境

硬件環(huán)境：Windows 10（64位）操作系統(tǒng)，內(nèi)存4G，2.5 GHz Intel Core i5-7200U CPU。

軟件環(huán)境：Python 3.8，Pycharm集成開發(fā)環(huán)境，MySQL 8.0.19，Navicat Premium 12。

3.3? 評(píng)估標(biāo)準(zhǔn)

實(shí)驗(yàn)以推薦準(zhǔn)確率為評(píng)估標(biāo)準(zhǔn)，準(zhǔn)確率（Precision）表示的是在所有預(yù)測(cè)為真陽(yáng)（TP）和假陽(yáng)（FP）的樣本中有多少樣本是真陽(yáng)（TP）。準(zhǔn)確率可以用TP/（TP+FP）表示，其意義為真正的正例占總正例的比重：

檢驗(yàn)算法的標(biāo)準(zhǔn)還有召回率（Recall）和F-measure值（又稱F-score）是一種統(tǒng)計(jì)量，是精確率和召回率的加權(quán)調(diào)和平均，召回率公式如下：

3.4? 實(shí)驗(yàn)結(jié)果分析

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

本文稱改進(jìn)后的算法為Nitem-CF，在本小節(jié)中，Nitem-CF算法會(huì)和傳統(tǒng)的Item-CF算法、修正的余弦相似度算法，以推薦準(zhǔn)確率為評(píng)估標(biāo)準(zhǔn)做對(duì)比實(shí)驗(yàn)。為方便起見，在文中以Item-CF*代表修正的余弦相似度算法。圖1是在K值（近鄰用戶個(gè)數(shù)）不同，物品返回?cái)?shù)為20的條件下，對(duì)三種不同算法得出的不同數(shù)據(jù)，作出準(zhǔn)確率對(duì)比折線圖（圖1折線圖中，只可以參考走勢(shì)，具體數(shù)據(jù)參照表1）。

從圖1中我們可以清晰地看到改進(jìn)后的算法準(zhǔn)確率要高于傳統(tǒng)的余弦相似度算法和修正的余弦相似度算法。

4? 結(jié)? 論

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

參考文獻(xiàn)：

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

[2] 韓志俊.基于關(guān)聯(lián)規(guī)則優(yōu)化的協(xié)同過濾混合推薦算法研究 [D].銀川：寧夏大學(xué)，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] 劉源.基于特征距離和時(shí)間效應(yīng)的上下文感知推薦技術(shù)研究 [D].北京：北京郵電大學(xué)，2019.

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

[6] 方樂笛，李順東，竇家維.曼哈頓距離的保密計(jì)算 [J].密碼學(xué)報(bào)，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] 唐積益.推薦系統(tǒng)中相似度計(jì)算方法的研究 [D].鎮(zhèn)江：江蘇科技大學(xué)，2015.

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

[11] 李世偉.基于協(xié)同過濾算法的推薦系統(tǒng)研究與應(yīng)用 [D].北京：北京工業(yè)大學(xué)，2017.

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

作者簡(jiǎn)介：陳昕宇（1998.05—），男，漢族，湖北棗陽(yáng)人，本科，學(xué)士學(xué)位，研究方向：推薦系統(tǒng)、計(jì)算機(jī)軟件開發(fā);楊帆（1980.06—），女，漢族，湖北武漢人，博士，教授，研究方向：推薦系統(tǒng)、電子商務(wù)。