融合時間衰減函數的改進協同過濾算法

殷佳莉，江智威，楊 毅，劉培培

(成都理工大學 信息科學與技術學院(網絡安全學院、牛津布魯克斯學院)，四川 成都 610059)

0 引 言

隨著互聯網、大數據以及移動技術的飛速發展，這些技術在給予人們便利的同時數據量也與日俱增，用戶要從龐大的信息中找到所需要的資源也變得越來越困難。為了解決信息過載的問題，幫助用戶有效提取數據，提出了推薦系統[1]。推薦系統目前已經是一項比較成熟和成功的技術，已深入運用到了互聯網產品的許多方面，如短視頻平臺、音樂和電影網站、電子商務、社交平臺以及在線電子書等。搜索引擎和推薦系統都是解決信息過載的方法，但和搜索引擎相比它有如下優點:不需要用戶主動提出搜索需求,而是系統從用戶的行為日志中幫助提取用戶行為信息,主動向用戶做出推薦；能給用戶帶來新的物品體驗,個性化程度高于搜索引擎；在推薦列表中會給用戶提供更多選擇。

傳統的協同過濾推薦算法一般只利用用戶的歷史行為信息，通過有限的數據挖掘用戶的興趣點，算法只關注用戶行為，而沒有將用戶在與物品產生聯系時的時間上下文信息加以利用，從而導致推薦的精度不高。針對傳統協同過濾算法忽略了時間上下文關系的缺點，該文提出了以傳統協同過濾算法為基礎的改進算法。該算法充分利用了時間上下文信息，用戶在不同時間下歷史信息并不相同，時間越近越能反映用戶當前行為信息。通過對人類記憶遺忘曲線進行擬合引入時間衰減函數，達到短期和長期興趣度的融合對算法進行約束，強化最近時間的用戶信息，優先對當前情況下感興趣的物品進行推薦，從而提高推薦的精確率和召回率。

1 推薦算法相關理論

1.1 基于協同過濾的推薦算法

協同過濾是推薦算法中的經典，這個概念第一次被提出是在1992年Xerox PARC公司的Tapestry項目中[2]，該項目創建的目的是讓員工節約篩選垃圾郵件的時間。隨后GroupLens網站利用其進行新聞篩選，幫助閱讀者過濾大量的新聞，得到感興趣的內容[3-4]。它不需要收集產品的有關信息，而是從用戶的行為數據中過濾出有用信息進行分析和處理，從而為用戶做出推薦的建議[5]。目前協同過濾已在各個推薦任務中(如圖書、音樂、電影等)都有了非常廣泛的應用，同時基于協同過濾的推薦算法在近幾年的Netflix大獎賽中也多次獲獎。

協同過濾根據算法機制的不同可分為：基于鄰域的協同過濾和基于模型的協同過濾[6]。基于鄰域的協同過濾是一種啟發式的推薦算法，是推薦系統中的核心算法，具有直觀、易實現、易于理解、準確率較高且無需長時間的訓練過程等優點，得到了深入研究和廣泛應用。因此，該文也將采用基于鄰域的算法進行實驗對比。此外根據計算角度的差異可將基于鄰域的算法分為:基于用戶的協同過濾(user-based collaborative filtering，User-CF)和基于物品的協同過濾(item-based collaborative filtering，Item-CF)[7]，在實際應用中，基于物品的算法使用更加廣泛，圖1是協同過濾推薦算法的幾種分類。

圖1 協同過濾推薦算法的分類

1.2 基于用戶的協同過濾推薦算法

基于用戶的協同過濾推薦算法(User-CF)以用戶為研究對象，只從用戶產生過行為的物品中獲取特征偏好進行分析，基本原理是利用用戶訪問物品行為的相似性來找出相似用戶，在用戶與用戶之間互相推薦可能感興趣的資源，主要體現了“人以群分”的思想[8-9]。 如表1所示，用戶A喜歡物品[A,C]，用戶B只喜歡物品[B]，用戶C喜歡物品[A,C,D]，那么可以認為用戶A和用戶C是具有相似品味的人，這時候就可以把用戶C喜歡的物品D推薦給用戶A。

表1 基于用戶的協同過濾

1.3 基于物品的協同過濾推薦算法

在實際應用中(如電子商務、視頻點播)，用戶數量遠遠大于項目數量，且物品的相似度相對于用戶的興趣較穩定，由此亞馬遜在2001年提出了基于物品的協同過濾推薦算法(Item-CF)[10]。它以物品為研究對象，在實際的使用中更加廣泛。從表2可以看出，喜歡物品A的用戶同時也喜歡物品C，那么可以認為物品A和物品C是相似的，當出現了一個用戶C，若他也喜歡物品A，那么可以認為他也會喜歡同類型的物品C，這時便把物品C推薦給他。

表2 基于物品的協同過濾

1.4 算法實現流程

基于協同過濾的推薦算法根據用戶歷史數據，挖掘用戶與用戶或物品與物品之間的相似性，并根據此預測偏好程度形成推薦列表。一般來說算法的實現步驟分為如下三步：

(1)計算相似度；

(2)根據相似度找出K近鄰；

(3)偏好程度預測。

以基于物品的協同過濾推薦算法進行說明，第一步是利用歷史信息計算物品相似度，然后找到與目標物品相似的K個相似物品，相似度計算是推薦系統的一個核心[11]。假設有物品i和物品j，N(i)表示物品i有過行為的物品集合，N(j)表示物品j有過行為的物品集合。相似度可通過Jaccard相似度或余弦相似度進行計算，其中余弦相似度算法最為經典，適用于數據稀疏情況，因此該文選用余弦相似度進行計算[12]，公式如下：

Jaccard相似度:

(1)

余弦相似度：

(2)

在計算得到物品間的相似度以后，按照要求選取K個物品作為相似物品，利用相似度以及用戶對物品的興趣度得到用戶對未知物品的偏好程度，計算用戶u對物品i的偏好程度的公式如下：

(3)

其中，S(i,K)表示和項目i的K近鄰，N(u)是用戶u有過正反饋行為的項目集合，sim(i,j)cos是物品i和物品j的相似度，ruj表示用戶u對物品j的興趣度，若用戶u對物品j有過行為，則可以令ruj=1，否則ruj=0。得到偏好程度值后按從小到大排列，選出N個物品作為待推薦物品,這種方法也稱為Top-N推薦。

2 融合時間衰減函數的推薦

2.1 時間上下文

傳統的協同過濾推薦算法一般只利用用戶的歷史行為記錄和評分數據挖掘用戶的興趣偏好，進而向用戶推薦感興趣的物品，而忽略了用戶發生行為時所處的環境，這里的環境也指用戶所處的上下文信息，如：時間、地點、心情等。

其中時間信息是上下文信息中的一個重要因素，時間信息對推薦系統的影響體現在：用戶興趣是變化的；物品有生命周期的；季節效應[13]。例如，用戶在小學階段對動畫的興趣更高，但隨著年齡增長而轉向電視劇。有些項目生命周期比較短，如新聞。招聘信息、促銷活動等，一旦時間超過項目生命周期，再進行推薦就失去了意義。此外特定項目還會受到季節效應影響，如夏天穿短袖，冬天穿羽絨服等。即考慮到人的偏好行為特性是隨著時間而變換的，在不同時間段，人的行為特征是不一樣的。此外，比起其他上下文因素，時間上下文信息是最容易獲取的情境信息，可以通過系統時鐘、事務時間戳等方法隱式地獲取時間[14]。因此，綜合考慮時間對用戶興趣度和物品相似度的變化影響，將時間上下文信息融入傳統協同過濾推薦算法中，是該文研究的出發點。

2.2 人類記憶遺忘規律

在心理學研究中，人類的記憶可以區分為短時記憶和長時記憶，短時記憶容量有限，如果不在一定時間內回顧，這些短時記憶很快就會被遺忘。人類的記憶是有限的，如今天學的知識會清晰記得，但是在昨天學的知識可能會有些模糊，時間更久一點或許就完全遺忘。德國著名心理學家赫爾曼·艾賓浩斯，通過實驗研究人類記憶遺忘變化情況，并通過實驗結果總結出人類記憶遺忘規律[15]，如表3。從該表格可以看出人類的記憶在第一天內大部分都會被遺忘，在此之后遺忘的速度開始變得平緩，最終只保留下一小部分。

表3 艾賓浩斯遺忘規律

將實驗結果繪制成艾賓浩斯遺忘曲線，如圖2所示。可以看出，人類對事物的遺忘速度并不是一直不變的，剛開始的遺忘速度很快，隨著時間的推移遺忘速度會慢慢變得平緩，這是一個“先快后慢”的過程。

圖2 艾賓浩斯遺忘曲線

用戶的興趣變化與人類記憶特性相似，通過類比人類記憶遺忘特性，可以認為用戶對物品的興趣度會隨著記憶的遺忘而逐漸衰退，用戶可能會對短時間內關注的物品具有更高的興趣度，用戶的短期行為應該受到更高的關注。在推薦系統中通過類比人類記憶遺忘特性，時間越近越能體現用戶的興趣度，物品間的相似度也越高，短期興趣在推薦中的權重也越高。

2.3 時間衰減函數

通過類比人類記憶遺忘規律擬合時間衰減函數，用時間衰減函數來表示用戶對物品興趣的權重，用戶對物品產生行為的時間越長，對用戶現在的興趣影響就越小。衰減函數的擬合方式可以有線性、指數和對數形式[16]，f(|T-t|)為線性時間衰減函數，其表達式如下所示：

(4)

其中，α代表時間衰減因子，α決定著f(|T-t|)的衰減速率，通過調整取值即可模擬記憶遺忘曲線，如果用戶興趣變化越快則衰減速率越快，α的值要大一些，在不同系統中應根據實際情況設定；T表示當前時間；t表示產生行為的時間；|T-t|表示時間差，f(|T-t|)隨著時間差的增長而減小,即取值范圍為(0,1)。

2.4 融合時間衰減函數的推薦

融合時間衰減函數的推薦算法需要提高用戶近期行為的權重，把時間衰減函數作為權重因子對用戶或物品相似度進行約束，用戶近期行為相比用戶以前的行為更能體現用戶現在的興趣。考慮時間的影響因素，在傳統的協同過濾相似度計算公式上進行改進，優化后的余弦相似度計算公式如下：

(5)

除了在相似度計算時融入時間衰減函數外，也應該考慮時間信息對偏好程度的影響，用戶的近期行為相比用戶遠期行為更能體現用戶當前的興趣。因此，在預測用戶當前的興趣時，應該將用戶近期反饋項目的權重增大，優先推薦與用戶近期喜歡或購買過的項目相似的項目，在得到用戶對項目產生行為的時間后，可計算用戶的興趣偏好，修正后的偏好程度見公式(6)，其中β為時間衰減因子，需要根據不同的數據集調整值的大小。

(6)

3 實驗和結果分析

3.1 實驗設置

實驗方法：實驗將采用離線實驗對比融合時間衰減函數的協同過濾推薦算法與傳統協同過濾推薦算法的離線性能。

實驗數據集：選擇delicious-2k數據集，它包含了1 867名用戶，105 000個書簽和69 226個網址信息，因為網頁由URL標識，因此可以根據域名將網頁分成不同的類別。從中獲取域名為“www.nytimes.com”的數據集進行實驗。

3.2 算法評估指標

Top-N推薦一般通過精確率與召回率進行衡量。其中U表示用戶集，R(u)是根據用戶在訓練集上的行為給用戶做出的推薦列表,T(u)表示用戶在測試集上的行為列表。精確率的意義在于所預測的推薦列表中有多少是用戶真正感興趣的，預測列表的精確率可以直接反映推薦的好壞[17],精確率的定義為：

(7)

召回率表示用戶真正感興趣的列表中有多少是被推薦算法準確預測出來的，即真實列表的召回率，召回率的定義為：

(8)

3.3 實驗過程

Nytimes數據集中包含了443名用戶的行為數據，對數據集進行提取整理得到(u,i,t)的三元組。對每個用戶的行為按照時間戳由早到晚排序，時間越近排序越靠前，由于一名用戶對書簽有多個行為數據也就有多個時間戳，將用戶最后一個時間戳的行為作為測試集，測試集包含了443名用戶的443條行為數據；將443名用戶在最后一個時間戳之前的所有行為記錄作為訓練集。

在基于物品的協同過濾算法實驗中，近鄰個數設置為10，計算物品間的相似度時采取余弦相似度；在實現融合時間衰減函數的協同過濾算法實驗中，近鄰個數設置為10，分別使用改進后的余弦相似度和興趣偏好程度進行計算。

改進后的算法根據訓練集學習用戶興趣模型，給每個用戶推薦N個物品，該文將選取不同N(1，2，…，10)進行10次實驗，得到融合時間上下文的協同過濾算法與未融合時間上下文的協同過濾算法的精確率和召回率，并將實驗結果繪制成表格和折線圖進行結果對比。

3.4 實驗結果

利用優化過的融合時間衰減函數的協同過濾算法在進行離線測試時，采用TOP-N列表推薦，最終的評估指標選擇精確率和召回率。在數據集上分別比較融合了時間上下文的協同過濾與未融合時間因子的協同過濾的實驗結果，如表4和表5所示。由這兩個表格可知：在相同推薦長度下，改進后的算法的準確率和召回率均優于傳統算法；將精確率和召回率繪制成折線圖分別如圖3、圖4所示：隨著推薦長度逐漸增加，推薦精確率逐漸下降，而召回率有所提高，但改進后的算法的效果比傳統算法更優。

通過圖表可以得出結論：融合時間衰減函數的協同過濾推薦算法和傳統協同過濾推薦算法相比，能在一定程度上提高推薦的精確率和召回率。

表4 NYtimes數據集不同推薦長度精確率對比 %

表5 NYtimes數據集不同推薦長度召回率對比 %

圖3 NYTimes數據集的精確率曲線

圖4 NYTimes數據集的召回率曲線

4 結束語

將時間上下文信息引入傳統協同過濾中以獲得更好的推薦精度，由此提出了一種融合時間衰減函數的改進協同過濾推薦算法。參考人類記憶遺忘特性曲線，擬合時間衰減函數與傳統推薦算法結合，建立與時間相關的基于物品的協同過濾推薦算法，從而做出推薦。通過實驗測試，驗證了所提出的融合時間衰減函數的協同過濾推薦算法相比傳統協同過濾算法能在一定程度上提高推薦的精確率和召回率，驗證了時間衰減函數的有效性。