基于項目聚類和時間衰減的動態協同過濾算法

劉 旭，李玲娟

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

0 引 言

隨著互聯網的發展和進步，人們在享受網絡 資源極大便利的同時，也受到信息超載的困擾，推薦系統是解決信息過載問題的主流方法。其中最著名的便是協同過濾推薦算法[1]。該算法有基于用戶的和基于項目的兩種類型，兩者都基于用戶的歷史記錄信息，前者結合與目標用戶有類似偏好的其他用戶興趣，后者 基于項目間的相似性，把用戶可能感興趣的項目快速呈現。

盡管協同過濾推薦算法在個性化 推薦中有明顯的優點：基于用戶行為和項目相似性，不需要先驗知識，在用戶行為比較豐富的時候，推薦效果不錯，但是有關用戶興趣隨時間變化的事實被忽略了。在基于項目的協同過濾算法中，計算最近鄰項目時，將不同時段的項目評分同等 對待，以致尋找到的目標項目的最近鄰，有可能不是真正意義上的最近鄰居，使推薦結果存在較大偏差。另外，基于項目的協同過濾算法搜索目標項目的最近鄰居時，需要遍歷整個項目空間，費時又費力[2]。

文中以基于項目的協同過濾算法為研究對象，設計了一種基于項目聚類和時間衰減的動態協同過濾算法(dynamic collaborative filtering algorithm based on item clustering and time decay，ITDCF)。首先根據用戶的評分對項目進行聚類，接下來在計算相似度時引入時間衰減因子反映用戶興趣的變化，在預測評分時也考慮時間衰減。最后，生成Top-N推薦列表，提高了推薦的準確性和效率。

1 相關研究

1.1 協同過濾算法

協同過濾(collaborative filtering，CF)算法的基本思想是：基于過去的行為或現有用戶組的意見來預測數據，并使用與當前用戶或當前項目類似的鄰居數據來生成推薦結果[3]。該算法的輸入是用戶-項目評分矩陣，輸出數據一般分為兩類：當前用戶對項目偏好的預測值和Top-N的推薦項目列表。其基本步驟包括：數據的收集與處理、生成用戶-項目評分矩陣、計算相似度、產生最近鄰、預測評分和產生Top-N推薦[3]。

基于用戶的協同過濾算法(UserCF)[4]的主要思想是：首先，輸入評分數據集和當前用戶ID，以查找出與當前用戶有相似偏好的其他用戶，這些用戶被稱為最近鄰居；然后，利用鄰居用戶預測項目的評分；對所有項目的評分按照從大到小進行排序，將評分居前的N個項目推薦給當前用戶。

基于項目的協同過濾算法(ItemCF)[4]的核心思想是：首先構建一個項目相似度矩陣來描述兩個項目之間的相似性；找出與當前項目相似的k個最近鄰項目，然后根據k個最近鄰計算當前用戶沒有看到的每一項目i的用戶評分；最后，將用戶對所有項目的評分從大到小排序，向當前用戶推薦所有項目中得分最高的前N項。

盡管UserCF算法在推薦領域得到了廣泛的應用，但也面臨著很多挑戰。像電商網站，一方面，項目的數量比較穩定，但用戶數目更新頻率較高，當用戶數量遠大于項目數量時，計算用戶間的相似性將越來越耗時并占用更多內存[5]。另一方面，基于用戶的算法生成的推薦結果可解釋性較差[6]。而ItemCF算法時間復雜度相對較低，并能根據用戶的歷史行為做出推薦解釋，可以比較容易令用戶信服。

1.2 基于項目的協同過濾算法

基于項目的協同過濾算法(ItemCF)的基本步驟是：處理數據、生成用戶-項目評分矩陣、計算項目相似度、產生最近鄰、預測評分和產生Top-N推薦。

該算法利用式(1)所示的余弦相似度計算兩個項目之間的相似度。

(1)

其中，N(i)是評價了項目i的用戶，N(j)是評價了項目j的用戶，|N(i)|是評價了項目i的用戶數，|N(j)|是評價了項目j的用戶數，|N(i)∩N(j)|是同時評價了項目i和j的用戶數。相似性的范圍為[0,1]，值越接近1，越相似。

此外，基于所獲取的k個最近鄰項目后，用式(2)預測當前用戶對目標項目的興趣。

(2)

其中，N(u)是用戶u評價過的項目集合，S(i,k)包含了和項目i最相似的k個項目，項目j屬于和用戶評價過的最相似的項目的集合，sim(i,j)是項目i和j的相似度，ruj是用戶u對項目j的興趣。根據數據集的類型，這里的ruj=1。

雖然ItemCF算法在項目數明顯少于用戶數的場合，相對于UserCF算法有一定的優勢，但是如果項目過多，計算項目之間的相似度矩陣的代價偏高，而且算法也忽略了用戶興趣隨時間變化對推薦效果產生的影響[7]。

2 ITDCF算法

文中為進一步提升ItemCF算法效率而設計的基于項目聚類和時間衰減的動態協同過濾推薦算法ITDCF包括：項目聚類、時間加權、產生最近鄰、預測評分、產生推薦等步驟。

2.1 項目聚類

針對基于項目的協同過濾算法在尋找目標項目的最近鄰居時，因需要遍歷整個項目空間而導致耗時大的問題[7]，ITDCF算法先對項目進行聚類，選擇評分數量達到一定標準的項目為初始簇類中心，可以認為這些初始中心就是最受用戶喜歡的項目；然后遍歷所有項目，計算其與初始中心的相似度，并歸入相似度最高的簇中，從而使目標項目最近鄰居的計算從全局空間轉到簇內空間，大大降低了計算量，提升推薦的時效性。

項目聚類的具體處理過程如下：

輸入：類簇的數目K和數據集合。

輸出：K個簇。

步驟1：選擇初始中心點。

根據構建的用戶-項目評分矩陣R，從項目集合中檢索所有n個項目，計算每個item的評分數量V。將所有的V值按降序排列，選擇前K個V值大的項目作為初始的聚類中心，得到K個聚類簇{C1,C2,…,Ck}。

步驟2：利用余弦相似度公式計算item分別到初始化聚類中心的距離。

步驟3：按照與聚類中心距離最近(相似度最高)的原則，將各個item分配到最鄰近的簇中，并記錄下item與每個聚類中心的相似度。

步驟4：算法結束，輸出聚類結果。

聚類時，以評價數量最多的K個item作為初始的聚類中心，減少了迭代次數，提高了算法效率。在這里，需要通過嘗試來確定最優的K值。

采用余弦相似度公式，將項目間的相似度作為評判距離的標準，相似度越大則距離越近。采用余弦相似度公式還可以避免由于各屬性衡量單位的差異性而導致的“相似不相同”問題[8]。

2.2 時間加權

考慮到用戶興趣會隨著時間而改變[9]，ITDCF算法將時間信息加入到推薦算法中，以在特定時間向用戶推薦其最感興趣的項目。ITDCF算法對基于項目的協同過濾推薦算法的改進 有兩個方面：計算相似度時加入時間衰減因子和預測評分時加入時間衰減因子。其中時間衰減函數選擇的是艾賓浩斯曲線。

艾賓浩斯曲線是由德國心理學家艾賓浩斯發現的，描述了人類大腦忘記新事物的規律[10]。將之應用到推薦系統上就是，用戶對越久遠的項目越不感興趣，在向用戶進行推薦時，將他以前看到過的項目進行適當地降權。但是如果用戶最近又對其中一個項目進行了操作，那么在推薦時就增加這類物品的權重。這樣得到的最近鄰項目更能符合用戶的興趣。

時間加權[11]的具體任務是：擬合艾賓浩斯曲線，編寫加權函數。

隨著時間的變化，人的興趣會逐漸衰減，但衰減趨勢為先快后慢[12]。所以指數函數在一定程度上更符合興趣的衰減特性。擬合所依賴的帶參數指數函數為：

Wt=AeBx+CeDx

(3)

艾賓浩斯遺忘曲線的最終擬合公式為：

(4)

其中，Tui表示用戶u對項目i操作的時間，Tuj表示用戶u對項目j操作的時間，單位為min。

2.3 產生最近鄰

在加入時間權重后，認為項目i和j相似是因為在同一時間內，二者同時被多個用戶選擇過[13]。考慮到艾賓浩斯遺忘曲線對用戶偏好的影響，用戶選擇時間間隔越短，項目間的相似度越高，文中采用余弦相似函數[14]來判斷兩個項目之間的相似度，得到計算項目i和j相似度的改進公式為：

(5)

其中，N(i)是評價了項目i的用戶，N(j)是評價了項目j的用戶，|N(i)|是評價了項目i的用戶數，|N(j)|是評價了項目j的用戶數，用戶u屬于同時評價了項目i和項目j的用戶集合，新增的Wt為時間衰減函數。

因為在計算簇集的時候保存了每個項目和聚類中心的相似度，所以根據記錄直接將目標項目劃分到相似度最大的類簇中；再取類簇內與目標項目最為相似的前K個項目作為最近鄰居。

2.4 預測評分

用戶最近的行為比用戶遠期的行為更能反映用戶當前的興趣[15]。通過項目相似性預測用戶對項目的興趣，并考慮用戶最近的行為。預測時采用如下公式：

(6)

其中，N(u)是用戶u評價過的項目集合，S(i,k)包含了和項目i最相似的k個項目，項目j屬于和用戶評價過的最相似的項目的集合，t0表示當前時間，tuj代表用戶u操作項目j的時間；對于時間衰減參數α，不同數據集中的值是不同的[16]，用戶的興趣變化越快，值越大。

最后，根據預測評分公式和得到的K個最近鄰項目，預測用戶的興趣度，排序后得到Top-N推薦。

基于以上步驟，ITDCF算法的流程可歸納為圖1。

圖1 ITDCF算法的推薦流程

3 算法性能測試

3.1 實驗數據集及劃分

MovieLens數據集[17]是研究人員廣泛使用的一種經典數據集，用于測量推薦算法的精度。

文中主要使用U.data文件，其中用戶的評分值為1至5分，代表評價從低到高。timestamp是自1970年1月1日零點后到用戶提交評價的時間的秒數。

3.2 實驗環境

文中的實驗硬件環境如下：Windows7；intel(R)Core(TM) i5-6200U CPU @2.30 GHz 2.40 GHz；4G內存；64位操作系統，基于x64的處理器。

實驗在JetBrains PyCharm 5.0.3平臺下運行；使用Python語言，環境為python3.6.3；Python包有：numpy、math、matplotlib.pyplot等。

3.3 實驗方案

按照每個用戶選擇項目的時間先后對U.data的項目進行排序，然后將用戶最后選擇的項目作為測試集，并把這之前用戶對項目的選擇記錄作為訓練集。利用改進后的算法構建用戶興趣模型，向每個用戶推薦N個物品，并且利用準確率、召回率和F1值對推薦算法的性能進行評價。

為了檢驗ITDCF算法的性能，文中將之與Popular算法和基于項目的協同過濾算法ItemCF進行對比，其中的Popular算法是按照物品的流行度高低向用戶推薦當天最受歡迎物品的算法。

給定時間T，項目i最近的流行度pi(T)可以定義為：

(7)

其中，三元組(u,i,t)表示用戶u在t時刻評價了項目i，Train是測試集數據集，α是時間衰減參數。

通過試驗取最佳類簇數7；設定目標項目的最近鄰項目的閾值參數從0增加到45，增加的間隔為5；進行10次實驗；觀察召回率、準確率和F1值的變化趨勢。

召回率為推薦列表中預測的用戶感興趣的項目與系統中用戶真喜歡的所有項目的百分比[18]。計算公式為：

(8)

其中，R(u,N)是給用戶u提供的長度為N的推薦列表，T(u)是測試集中用戶評價過的項目集合。

準確率為推薦列表中用戶喜歡的項目在所有被推薦的項目中所占的百分比[18]，計算公式為：

(9)

其中，R(u,N)表示算法給用戶u提供的長度為N的推薦項目列表，T(u)為測試集中用戶喜歡的物品集合。

召回率Recall說明了推薦列表的覆蓋性，Precision說明了推薦列表的準確率，都是衡量推薦性能的重要參數[18]。用F1值來擬合Precision與Recall，其中P為Precision，R為Recall。F1值越大，表明算法的推薦效果越好。計算公式如下：

(10)

3.4 實驗結果分析

Popular算法、ItemCF算法和ITDCF算法在不同推薦項目數N值下的準確率、召回率和F1值分別如圖2至圖4所示。

圖2 MovieLens數據集上各算法在不同N值下的準確率

圖3 MovieLens數據集上各算法在不同N值下的召回率

圖4 MovieLens數據集上各算法在不同N值下的F1值

由圖2可以看出，對MovieLens數據集，ITDCF算法在不同推薦項目數下的準確率都更高，這是由于用戶的興趣隨時間而改變，在計算相似度時考慮了用戶對項目的遺忘，因此提高了預測項目評分的準確性。同時可以看出選擇合適的推薦項目數N，可以獲得最好的推薦效果。

由圖3和圖4可以看出，ITDCF算法的召回率和F1值在整體上也比Popular、ItemCF高。

4 結束語

以提高推薦的準確率為目標，基于協同過濾和流行度推薦的思想，引入聚類和進一步考慮興趣隨時間的變化因素，設計了一種基于項目聚類和時間衰減的動態協同過濾推薦算法。該算法根據評分數量選擇初始簇類中心，減少了迭代次數，并縮小了尋找目標項目最近鄰的候選集；通過在基于項目的協同推薦算法中加入時間衰減因子提高了推薦的精度。MovieLens數據集上對ITDCF算法、Popular算法和ItemCF算法的準確率、召回率和F1值的對比實驗結果表明，ITDCF算法在推薦的準確性和效率方面有所提高。