結合CFDP與時間因子的協同過濾推薦算法

張凱輝，周志平，趙衛東

同濟大學 電子信息與工程學院，上海 200093

1 引言

近年來，隨著大數據和服務推薦技術的不斷發展，針對每位用戶的個性化推薦應運而生。因此，在基于大數據時代的背景下，利用收集到的海量用戶行為數據，設計出高效的推薦算法，為每位目標用戶提供精準高效的個性化服務，便成了要急迫解決的問題[1-2]。

本文研究的協同過濾推薦算法，其原理為：找出數據集中與目標用戶興趣愛好、性格特征或者社會屬性相似甚至相同的用戶，將這些用戶所感興趣的項目推薦給目標用戶。但是，目前傳統的協同過濾算法仍然有著許多值得優化的地方。本文重點研究了該算法出現的數據稀疏性問題、冷啟動問題和實時性問題。如何更好緩解或解決以上問題，便成了優化協同過濾算法的關鍵[3]。

本文針對協同過濾算法出現的以上問題，提出了一系列的改進方法：首先采用密度峰值聚類算法（CFDP）對項目進行聚類處理[1]，并用Slope-One算法進行數據填充以解決數據稀疏和冷啟動問題；在計算推薦項目評分時引入時間因子來對傳統協同過濾算法的評分步驟進行優化，保證了推薦算法的推薦內容具有實時性，可以給予用戶更準確的推薦[4]。

2 相關工作

2.1 傳統協同過濾推薦算法

算法的基本思想是：根據已有的用戶歷史行為數據，構造協同過濾矩陣，其中每一行數據代表該用戶在所有項目上的評分情況；每一列則代表該項目獲取的評分情況。由于算法默認具有相似瀏覽記錄和評分行為的用戶，在隨后的項目選擇和評價上往往也是相似的。傳統協同過濾算法的基本運算流程如圖1所示[5]。

圖1 協同過濾算法流程圖

2.2 協同過濾評分矩陣

表1顯示了用戶-項目協同過濾評分矩陣R，該矩陣為一個m×n階的評分矩陣，代表共有m位用戶n項項目，其中用戶對項目的偏好程度用其對項目的評分rij的大小來反映。

表1 用戶-項目協同過濾評分矩陣

2.3 用戶相似性評價指標

協同過濾評分矩陣中，每一個用戶的歷史數據都可以提取為一個向量，衡量兩名用戶的相似性即判斷兩名用戶向量的相似度。一般來說，常用的向量相似度評價指標有：余弦相似性、Pearson相關系數以及修正余弦相似性三種，以下為詳細介紹。

（1）余弦相似性

評價用戶ui與用戶uj的余弦相似度：首先從協同過濾矩陣R中提取用戶評價向量vui和vuj，則用戶ui與用戶uj的余弦相似性為向量vui和vuj的余弦夾角。計算方法如式（1）所示：

其中，ui?uj為兩個向量的點積，||ui||×||uj||則代表兩個向量模的大小乘積。

（2）Pearson相關系數

計算用戶ui與用戶uj的Pearson相關系數：如式（2）：

其中，Iuiuj代表用戶ui與用戶uj評論過的項目交集，Ruic代表用戶ui對項目c的評分，代表用戶ui的平均評分。

（3）修正余弦相似性

由于不同用戶打分風格的差異，導致相同喜好用戶的評分期望會有很大差異，采用余弦相似度會導致相似度計算結果不準確，修正余弦相似性在計算時不采用評分期望這一變量，很好地規避了該問題，用戶ui與用戶uj的修正余弦相似性如式（3）：

其中，Iui代表用戶ui評價過的項目集合，Iuiuj為用戶ui與用戶u均評論過的項目交集，為用戶u的平均評ji分，Ruic為用戶ui對項目c的評分。

一般來說，有兩種通用的方法來選取相似用戶：閾值法和TOP-N法。其中，閾值法是將計算出的相似性與人為設定的相似度閾值進行比較，若大于則將該用戶放入相似用戶集合中。TOP-N法則是對所有用戶的相似度進行從大到小的排序，選出前N個用戶作為相似用戶。由于閾值法的閾值不好進行設定，過大或者過小都會影響相似用戶選取的質量，所以本文采用TOP-N法來進行篩選。

2.4 項目推薦

從目標用戶的相似用戶集合U中提取所有目標用戶未評價過的項目，并預測這些項目的評分Puij如式（4）：

3 改進協同過濾推薦算法

3.1 傳統協同過濾算法推薦算法的不足

（1）數據稀疏問題

一般來說，根據數據集得出的協同過濾評分矩陣稀疏度往往非常高：一般在90%以上。因此，用這樣的數據計算出的用戶相似度往往是不準確的，由此得到的相似用戶也是不準確的，自然也難以得到好的推薦結果[6]。

（2）冷啟動問題

由于協同過濾算法是基于歷史數據來進行推薦的，對于沒有任何歷史記錄的新用戶和新項目，默認與任何用戶或項目的相似度都為零，推薦系統也就自然無法將合適的項目推薦給目標用戶[7]。

（3）實時性問題

由于用戶的喜好或需求是一個不斷變化的過程，過去的喜好與當前的喜好可能存在較大差距。因此，將目標用戶最近的歷史記錄與以前的歷史記錄等價看待顯然是不科學的，推薦系統給出的推薦也就難以滿足目標用戶的當下需求[8]。

3.2 基于密度的聚類算法（CFDP）

根據大量的用戶行為數據顯示，有著相似興趣的用戶，其興趣主要集中在有限的幾個類型。因此，每位用戶的評分一般都集中在一類或幾類項目上。因此，本文選擇使用Clustering by Fast search and Find of Density Peaks（CFDP）是一種基于密度的聚類算法，將所有項目分成若干個類別。若有新的項目加入，還可以將其聚類到某個大類下面所對應的簇。有效地解決了矩陣稀疏與項目冷啟動的問題。

算法的基本思想是：某人聚類中心的密度要高于其周邊所有屬于該類數據點的密度，且屬于該類的數據點對應的聚類中心是距離所有聚類中心中最近的一個。

對于每一個數據點，要計算該點的兩個量：局部密度ρi和到具有更高局部密度的點的距離δi。

局部密度計算如下：

其中，dij該數據點與其他數據點間的距離，dc為截斷距離，其值一般滿足可讓點的平均鄰居個數約為數據點總數的1%～2%。

距離定義如下：

計算出所有數據點局部密度和距離后，可根據需要的聚類個數選定聚類中心：設定閾值ρmin和δmin，將所有（ρi>ρmin&δi>δmin）的數據點定為聚類中心，一個聚類中心代表一個類別。剩余未被劃為聚類中心的點，分別計算出每個點與各個聚類中心的距離，找出距離最近的聚類中心[9]。

3.3 Slope-One算法

Slope-One算法是一種填充矩陣空缺值的算法，其基本思想是：找出矩陣空缺值與已知數值的某種線性關系，利用線性回歸的方法計算出空缺值的大小，其具體的計算方法如下[9]。

計算項目i的預測評分P(u)i，首先要計算相關項目j的平均偏差devij，平均偏差devij的計算方法如式（7）所示：

其中，Rij為用戶u對項目j的評分，Uij為所有均評價過項目i與項目j的用戶集合，Ij為與項目i被同時評價過的項目集合。

項目i的預測評分P(u)i計算方法為：

有一種改進方法是將sum(Uij)作為權值，這樣可以保證用戶評分次數越多的項目，其預測評分的可信度越高。修正后的預測評分Pw(u)i計算方法分別為：

3.4 引入時間因子

目前來說，推薦算法引入的計算因子主要有時間因子、用戶關系以及用戶信譽度等。在當前各種用戶行為數據集中，用戶每次行為的時間往往是會被準確記錄的；記錄用戶關系以及用戶信譽度的數據集則相對較少，且有可能涉及隱私問題。更為重要的是：推薦算法的目的是為了找出目標用戶當前最有可能感興趣的項目，即目標用戶最近的行為數據是最具有價值的數據，引入時間因子可以更好地劃分不同數據的價值。因此，本文采用引入時間因子來進行算法優化。

根據上文的分析，時間越近的用戶評價越可以反映當前目標用戶的興趣，即用戶的興趣愛好是不固定的，并在某一時間段只會對有限的幾個項目感興趣，并且用戶在相隔很短的時間內具有愛好的項目具有更高的相似度。根據以上分析，可以定義用戶u對項目i評分的時間權重的計算方法為：

其中，參數α∈(0,1)，通過改變α的值來調整權重大小；Te為用戶第一次進行項目評價時對應的時間，Lu表示用戶u使用該推薦系統的總時長，Ti表示用戶對項目i評分時對應的時間。

但是，根據分析，用戶的興趣變化與時間應該呈現已知非線性的負相關關系。根據研究，用戶的興趣變化與遺忘規律相近，因此本文采用艾賓浩斯遺忘規律作為時間因子的計算方法。則改進的用戶u對項目i評分的時間權重計算方法為：

其中，每一個不同時間點的評分項都有一個不同的時間權重，距離當前時間越近的評分時間權重越大[10]。

3.5 改進算法流程

本文提出的改進協同過濾推薦算法，首先采用CFDP算法對項目進行聚類，并用Slope-One算法進行數據填充，有效緩解了傳統協同過濾算法的數據稀疏與冷啟動問題。在計算預測評分的時候又引入了時間因子，使得對項目的評分更側重于參考最近的數據。改進算法的具體流程如圖2所示[11-12]。

圖2 改進協同過濾算法流程圖

3.6 改進算法分析

本文針對傳統協同過濾推薦算法存在的一系列問題，采用CFDP聚類算法，將相似的項目歸為一類，以解決冷啟動問題；同時，聚類算法縮減了協同過濾評分矩陣的大小，加快了后面數據填充的效率。針對數據稀疏的問題，本文采用Slope-One算法進行數據填充，填充過后，增加了不同用戶之間共同評分過的項目數量，使得在計算用戶相似性時有更多的數據可以利用，計算出的結果也就更為可靠。

由于本文提出的算法為推薦算法，需要對目標用戶進行實時性推薦。由于用戶對項目的興趣是隨著時間而不斷變化的，用戶很久以前的行為是不具有很大的參考價值的；因此，將某用戶的所有行為數據同等對待是不科學的。針對這一問題，本文提出的改進算法引入時間因子，將每個評分項前乘一個時間權重項，從而使計算結果更貼近與最近的用戶行為數據，得到更準確的結果[13-14]。

4 實驗仿真與結果分析

4.1 實驗環境

本實驗的開發語言Python3，在Windows10 64位運行。硬件配置：i5-7300HQ，2.50 GHz，內存：16 GB。顯卡NvidiaGTX1060（6 GB），硬盤500 GB。

4.2 測試數據集

目前，主流的推薦系統最常用數據集有：MovieLens數據集、Jester數據集和Book-Crossings數據集。Jester數據集為群眾對于150個笑話的約600萬個評分數據，由于參與評價的笑話數偏少，且沒有評分的時間數據，因此該數據集不適合本文的算法仿真；同樣，Book-Crossings數據集也沒有評分時間，因此也不適合。本實驗采用的數據集是MovieLens 1M數據集，收集了共6 000余名的用戶對近4 000部電影的100萬余條評論，每條評論都有相應的評論時間。評分共有1～5共5個等級，等級越高代表用戶對該電影的喜愛程度越高。其中，用戶的職業有20余種，電影的種類有18種，數據集的稀疏度為1?1 000 209/（6 040×3 952）=95.81%。

數據集共包含：users.dat、movies.dat和ratings.dat。

用戶數據分別有用戶ID、性別、年齡段、職業ID和壓縮編號5個字段，其中用戶ID以及職業ID不需要變，壓縮編號本實驗并未用到。性別的F和M轉換成0和1，年齡轉成7個連續的數字0～6，職業轉成連續的數字1～20。

評分數據分別有用戶ID、電影ID、用戶評分和時間戳4個字段。用戶、電影ID和用戶評分都不需要進行處理，時間戳轉化成標準的時間格式。

電源數據則主要有電影ID、電影名稱以及電影類型3個字段。電影ID與名稱不想要改變，電影類型成連續的數字1～20。

本實驗中，本文采用80%的數據作為訓練集，20%的數據作為測試集進行試驗。

4.3 評估標準

本文采用平均絕對偏差MAE來進行算法評估，指的是所有數據與均值之差的平均值大小，計算方法如下：

其中，pi代表用戶u對項目i的預測評分，p′1則代表實際評分。

因此，推薦系統總的MAE為所有用戶{u1,u2,…,um}的MAE的平均值[15]，即：

4.4 實驗結果分析

本實驗對CFDP算法中的超參數dc和時間因子中的超參數α分別取0.2和0.5，且要確定本實驗的相似度計算方法、最近鄰用戶個數K和項目聚類數量N的最優解。

（1）確定相似度計算方法

本文在控制其他變量與流程相同的情況下，采用傳統的協同過濾算法，比較各相似性公式下MAE的大小。其中，最近鄰用戶個數K的取值為10～50，間隔為10，共5個值。實驗結果如表2和圖3所示。

表2 三種相似性計算方法推薦精度

圖3 三種相似性計算方法對比圖

從圖3可以看出，當采用修正的余弦相似性且最近鄰個數K取30的時候，推薦精度最高。因此，本實驗采用修正的余弦相似性作為計算用戶與項目相似性的指標。

（2）項目聚類數目

CFDP算法通過調整dc來決定聚類種類數目N的大小，使其的取值分別為5、10、15、20、25、30（鄰居用戶數目K的大小恒為30），實驗結果如圖4所示。

由圖4可知，當聚類數目N取20時，MAE的值最小。因此，將改進協同過濾算法的聚類數目N固定為20。

圖4 基于項目協同過濾算法聚類個數測試

（3）添加CFDP算法與Slope-One算法

確定最優的聚類數目N后，便要構造新的協同過濾評分矩陣R′，并用Slope-One算法進行數據填充。仿真后的實驗結果如表3和圖5所示。

表3 兩種算法的平均絕對偏差比較表

圖5 傳統算法與未添加時間因子改進算法實驗結果對比圖

由圖5所示，經過聚類和數據填充后，推薦算法的推薦效果得到了明顯的提升。且通過實驗發現，由于聚類極大地縮減了協同過濾評分矩陣的大小，推薦算法的推薦速度也得到明顯改善。

（4）添加時間因子

時間權重超參數α的確定：

本算法里，本文采用控制超參數α的值來控制時間權重WT(u,i)的大小；且α越小，則距離當前時間較近的用戶數據權重比率越大。確定α的仿真實驗結果如圖6所示。

由圖6可知，當α約為0.02時，MAE最小。且由于0.02?1，說明當前時間較近的數據的確具有更大的參考價值。

比較三種算法的效果，實驗結果如表4和圖7所示。

圖6 α值的影響示意圖

表4 兩種算法的平均絕對偏差比較

圖7 三種算法實驗結果對比圖

4.5 實驗總結

本實驗基于MovieLens數據集，首先采用控制變量的方法，找出了超參數鄰居個數K與項目聚類數N的最優值。隨后，本文對原算法添加CFDP聚類算法和Slope-One算法，并進行了對比實驗，證明填充這兩種算法的確可以提高協同過濾算法的推薦效果。最后，本文又在改進算法的基礎上添加了時間因子。實驗結果表明，改進的協同過濾算法的MAE值更低，即推薦效果明顯要好于傳統的協同過濾算法。

5 結束語

本文針對傳統協同過濾算法存在的一系列問題，通過引入其他算法以及改良傳統算法的方式，有效緩解了傳統算法的存在的一系列問題，得出了更好的實驗結果。

不過，協同過濾算法仍然存在很多值得改進的點：（1）單純地通過矩陣數據的線性關系來填充未知數據的方法是不夠嚴謹的。所以，可以引入其他因子：例如用戶的社會屬性來進行綜合判斷。（2）本文提出的改進算法有聚類數目、最近鄰個數、推薦結果數目等多個超參數，如何更為準確地得出這些超參數的最優值仍值得研究。（3）隨著數據量的增多，推薦系統的速度會越來越慢，如何引入并行計算，提高推薦系統的訓練推薦速度也是很值得研究的。