一種基于用戶興趣轉移挖掘的流式推薦算法

陳建宗 劉永堅 解 慶 唐伶俐

(武漢理工大學計算機科學與技術學院 湖北 武漢 430070)

0 引 言

近年來，互聯網規模和覆蓋面的迅速增長帶來了信息超載的問題，五花八門的信息從各個渠道涌入用戶的視野中，使得用戶難以從中發現對自己真正有價值的內容。不同于搜索引擎，個性化推薦系統通過“推送”的方式主動將用戶感興趣的信息和資源投送給用戶，在很大程度上節省了用戶主動去“拉取”未知信息并過濾出有效信息的成本，從而緩解了信息超載的問題。

雖然傳統推薦算法在各個應用領域中已經取得了一定的成功，但是隨著實際應用的不斷發展，對推薦系統也提出了新的挑戰。傳統的推薦模型通常是靜態模型，需要按照一定時間周期對模型進行定期更新，所以模型無法及時對外界變化做出相應的調整，進而導致模型的推薦質量在更新周期內不斷下降。流數據中通常蘊含著豐富的信息，若推薦系統能及時捕捉到這些信息并加以利用，便能及時應對外界的變化，有效提高推薦結果的精準度和合理性。

同時，隨著時間的遷移，歷史數據的時間跨度變得越來越大，與最初相比，用戶的興趣偏好可能已經發生了很大的變化，然而傳統的推薦系統通常認為用戶的興趣偏好是恒定不變的，依據“過時”的歷史數據所做出的推薦不僅效果差，而且非常容易引起用戶的反感。若推薦系統能夠成功地捕捉并適應用戶興趣轉移的現象，便能有效提高推薦的質量，推薦的結果也更容易給用戶帶來驚喜感，從而提高用戶對于系統的忠誠度。

為了應對上述挑戰，本文提出了一種改進的流式推薦模型streamGBMF(Stream Genre-based Matrix Factorization)。該模型根據資源的種類信息來構建資源的特征向量，打破了傳統矩陣分解模型中用戶和資源特征向量之間的全連接結構。同時，模型通過只對用戶特征向量采取實時更新的方式，避免了傳統增量矩陣分解模型中出現的整體擬合殘差擴大的現象。為了使模型能夠捕捉用戶的興趣轉移現象，本文針對streamGBMF模型的特點，提出了兩種新型的遺忘機制，能夠有效區分用戶的長期偏好和臨時偏好，使模型能夠在遺忘掉“過時”的用戶歷史數據的同時，保留用戶的長期偏好特征。實驗結果表明本文提出的方法有效提升了推薦效果。

1 相關工作

1.1 流式推薦系統

自Henzinger于1998年第一次提出流數據處理以來[1]，流數據處理逐漸成為了一個熱門的研究領域。為使推薦系統能根據流數據中的信息實時更新模型參數，許多推薦系統研究采用了在線學習的方式。其中文獻[2-4]將基于內存的推薦算法與增量更新策略相結合，此類增量更新策略主要是針對資源之間的相似度計算，然而其計算耗時與用戶或資源的數量成正比，因此無法滿足流數據環境下對算法時間復雜度的要求。

另一部分研究將傳統矩陣分解模型與增量更新策略相結合。其中一種增量更新策略是面向特征矩陣的，如Huang等[5]基于線性變換的假設，將流數據按固定的時間段分成多個批次矩陣進行分解，最后通過線性方程將所有批次分解矩陣組合在一起，得到更新后的模型參數。但由于單個時間段內的流數據所構成的批次矩陣相比原始矩陣要更加稀疏，因此批次矩陣的分解效果并不理想，并且，該模型的更新延時取決于時間分割周期的大小和批次矩陣訓練的耗時，因此其無法做到實時更新。另一種增量更新策略是面向特征向量的[6-7]，其核心思想是只更新與流數據相對應的用戶和資源特征向量，而不相關的特征向量則維持不變。但是在傳統矩陣分解模型中，用戶特征向量和資源特征向量之間是全連接的，這種全連接結構在增量更新過程中會導致模型整體擬合殘差不斷擴大。

1.2 用戶興趣轉移

隨著用戶審美的不斷變化和外界難以預測的事件不斷發生，使得用戶的興趣不斷發生轉移[8]，捕捉并且能夠適應這些變化，是推薦系統改善推薦質量的關鍵[9]。其中最直接的方式就是“遺忘”掉過時的歷史數據，現有的研究提出了很多遺忘機制，文獻[10]提出了一種實例選擇方法，其定義了一個固定大小的時間滑動窗口，模型在訓練和預測時只考慮位于時間窗口內的數據，而位于窗口外的數據則會被直接丟棄，因此該方法不僅無法保留用戶的長期偏好，還會加劇數據的稀疏性問題。Ding等[11]提出了一種實例權重方法，該方法根據數據生成時與當前的時間差，給予每一條數據一個指數型的時間衰減權重。但是同實例選擇方法一樣，實例權重方法在降低過時數據影響的同時，也會丟失用戶長期偏好信息。為了解決這個問題，模型需要保存歷史數據，由于歷史數據量太大，無法都存儲在主存儲器中，“蓄水池”的技術被提了出來[12]。蓄水池中保存著歷史數據的采樣，在此基礎上，Wang等[13]設計了一個新型高斯分類模型，從蓄水池和流數據中采樣出信息量最大、最有用的數據。但是該模型將評分限制為二值類型，且把未觀測的數據視為負樣本，然而未觀測的數據很大可能是因為用戶從未接觸過該資源，不完全等同于負樣本。Chang等[14]假設用戶和資源的特征向量服從布朗運動，其為每個特征向量設計了一個連續馬爾科夫過程，但由于算法時間復雜度太高容易造成數據的積壓問題。Sun等[15]指出在部分應用場景中，只有極少數人會對同一個資源進行多次評價，因此模型無法獲得足夠的信息來確定用戶是否仍然喜歡或者不喜歡該資源，基于這個考慮，Sun提出對資源進行聚類，從而能夠觀察用戶對于同一類資源的偏好是否發生了改變。然而，數據的稀疏性導致在聚類結果中部分并不相似的資源被分到了同一類別中，從而影響了最終的推薦結果。Matuszyk等[16]針對增量矩陣分解模型提出了五種不同的遺忘機制，但這些機制無法處理個體用戶偏好的細微變化。

2 符號與概念預定義

2.1 符 號

為了便于后文理解，在介紹模型之前，本節中將對后文公式中的符號進行定義和說明。

?M,N：分別表示用戶和資源的數量；

?K：表示高階特征的維度；

?Uu(t),Vi(t)：分別表示用戶u和資源i在時刻t的特征向量；

?R：所有觀測評分的集合；

?KV(i)：表示資源i包含的種類信息集合；

?Ik：表示包含種類信息k的資源集合；

?tr：表示評分r生成的時間；

?τU(u),τU(u,k)：分別表示用戶u最后一次評分的時間和用戶u最后一次對包含種類信息k的資源評分的時間；

?Ttrain,Tpredict：分別表示在訓練和預測階段的衰減系數。

2.2 動態基線估計

評分是一種顯性的用戶反饋數據，評分的高低間接反映了用戶對資源的興趣偏好，但同時，評分也會受不同用戶之間評價標準的差異所影響。例如，在一個評分取值范圍為1至5分的評分系統內，對于一個高要求的用戶，“3分”意味著一個中性的評價，而對于一個容易滿足的用戶來說卻代表的是消極的評價。為了消除用戶之間評價標準差異帶來的影響，本文采用了Koren提出的動態基線估計方法[9]，用戶u對資源i的動態基線估計被定義為：

bui(t)=μ+bu(t)+bi(t)

(1)

式中:μ代表所有觀測評分的均值;bu(t)和bi(t)分別表示用戶u和資源i的觀測偏差值，bu(t)可理解為用戶u評分的嚴苛程度，而bi(t)可理解為資源i受大眾喜愛的程度。

本文在動態基線估計的基礎上，將用戶u對資源i進行評價時表達的偏好情緒定義為eui(t)：

eui(t)=rui(t)-bui(t)

(2)

當eui(t)大于0時，代表用戶表達的是積極的情緒，即模型認為用戶u喜歡資源i。動態基線估計是模型能夠捕捉用戶興趣轉移的重要一環，因為在消除用戶之間評價標準的差異帶來的影響后，模型能更準確地學習到用戶的真實偏好。

3 模型設計

3.1 離線訓練

在離線訓練過程中，模型根據歷史觀測評分來訓練模型參數。由于傳統的矩陣分解模型是全連接的結構，因此在增量更新的過程中，局部的更新會導致整個模型的擬合殘差不斷擴大。為了避免這個問題，本文決定根據資源的種類信息來構建資源特征矩陣，這些資源的種類信息是由專家進行標注，且在實際生活中是非常常見的，例如電影領域中的“動作片”、“冒險片”，和音樂領域中的“流行樂”、“搖滾樂”等。另外，應用資源種類信息來構建模型能夠使推薦結果具有良好的可解釋性。

由于每一個資源的種類信息數量是有限的，因此構建的模型中每個資源都只與少數幾個特征相關聯，從而打破了傳統矩陣分解模型的全連接結構：

(3)

通過式(3)構建得到的資源特征向量，其特征值Vik能反映出資源i在同樣具有特征k的所有資源中的地位。之后，模型根據歷史評分數據，通過最小化整體擬合誤差訓練得到用戶特征矩陣，其目標函數表達式為：

(4)

式中:eui(tr)由式(2)計算得到，表示評分r生成時用戶u對資源i所表達的情緒值。至此，模型已經完成了離線訓練的過程，即根據歷史數據訓練得到用戶和資源的特征矩陣。

3.2 在線學習

在本文模型的在線學習過程中，將系統接收到的流數據分為兩種類型：用戶反饋數據、新用戶注冊和新資源創建事件。

1) 用戶反饋數據。當系統接收到一條新的評分數據rui時，模型需要根據該評分數據來實時更新模型參數，以從中獲取用戶最新的興趣偏好。基于離線訓練中的設定，資源的特征向量是根據其固有屬性生成的，其值相比較于用戶的特征向量要為穩定，因此模型并不需要像更新用戶特征向量一樣頻繁對資源特征向量進行更新。本文將時間線按照固定的時長進行分段，資源特征向量在同一時間段內被視為恒定的值。時間分段粒度的設置應根據具體的應用場景來決定，在本文模型的實驗中，其值被設為一天。基于以上考慮，模型通過下式對新的評分數據rui所對應的用戶特征向量進行更新：

λ‖Uu‖2

(5)

由于模型只對相應的用戶特征向量進行更新，因此，與該用戶相連的其他資源特征向量不會受到更新的影響。同時，不同于傳統面向特征向量的增量更新策略，本文模型在更新時將該用戶所有的歷史評分數據都納入增量更新的考慮范圍，因此，該用戶歷史評分的擬合誤差也能得到有效控制。這兩個特點使得本文模型在增量更新的過程中能夠很好地避免模型整體擬合殘差不斷擴大的問題。

2) 新用戶注冊和新資源創建事件。在流數據的設定下，系統中不斷有新用戶注冊和新資源被創建。對于每一個新的用戶和資源，模型需要對相應的特征矩陣進行擴維，并對其特征向量進行初始化。一方面，模型假設新用戶u的興趣偏好符合大眾的興趣偏好，其特征向量的初始化如下：

(6)

另一方面，模型依然根據新資源的種類信息來初始化其特征向量：

(7)

式中：參數σ用來控制新用戶和新資源的初始特征向量的分布，本文模型中將其值設為0.1。

3.3 遺忘機制

為了將用戶的長期偏好與臨時偏好進行區分，本文提出了兩種新型的遺忘機制：奇異點移除法和時間衰減置信度法。值得注意的是，對于僅有少量數據的用戶，為了避免丟失其中重要的信息，模型中設定了一個閾值，評分數量低于該閾值的用戶不會受到遺忘機制的影響，本文實驗中將此閾值設為10。

1) 奇異點移除法。奇異點移除法的思想是，在用戶的歷史評分數據中，若某個評分符合用戶的日常興趣偏好，則模型對該評分的擬合誤差理應較小。反之，若模型對某個歷史評分的預測誤差顯著大于其他的評分，則意味著該歷史評分與用戶平常的興趣偏好不一致，屬于用戶的臨時偏好或異常行為。基于以上思想，模型根據用戶u的歷史評分，計算出評分預測誤差的標準差，記為sdU(u)。若某一歷史評分rui滿足式(8)，則會被標記為奇異點評分并被移除。

(8)

式中：參數α用來控制遺忘機制的靈敏度。值得一提的是，為了避免丟失流數據中的信息，模型只對歷史數據中的奇異點評分進行移除。

2) 時間衰減置信度法。不同于奇異點移除法，時間衰減置信度法根據資源的種類信息將用戶對于單個資源的興趣轉移問題轉換為用戶對于某一類資源的興趣轉移問題，并將用戶興趣轉移問題分為以下兩種情況：

(1) 當用戶在不同時間點對同一類資源表達了不同的興趣偏好時，該如何確定用戶當前對這類資源的興趣偏好。

(2) 當用戶已經很長時間沒有與某一類資源產生交互，該如何確定用戶當前對這類資源的興趣偏好。

對于第一種情況，顯然模型需要學習的是用戶最新表達的興趣偏好，而以前的數據則被視為過時數據。因此，在模型訓練的過程中，對于每一個評分r，根據tr與τU(u,k)的時間差，為其設置一個權重wtrain(r)：

(9)

式中：wtrain(r)的取值范圍為(0,1]，對于時間越久遠的評分，其權值越低。參數Ttrain是用來控制過時數據對模型影響的衰減參數。在此基礎上，式(5)被擴展為：

Uu(t)TVi(t))2+λ‖Uu(t)‖2

(10)

對于用戶興趣轉移的另外一種情況，其背后的邏輯是用戶會持續與自己感興趣的類型資源產生交互，直到對其不再感興趣為止，反之，用戶會盡量避免與他們不喜歡的類型資源產生交互。基于該假設，模型為用戶特征向量的特征值Uuk(t)定義了一個置信度參數Confuk，代表模型對該特征值的把握性。若模型認為特征k是該用戶的臨時偏好，模型將通過降低置信度Confuk的值來降低特征k對于評分預測的影響：

ConfuKUuK(t))Vi(t)+bui(t)

(11)

為了驗證上述假設中時間衰減置信度Confuk分別對于積極和消極偏好的影響，本文設計了三種不同的衰減策略進行比較。令Uuk(t)≥0代表用戶u對包含特征k的資源持積極的興趣偏好，反之則代表用戶u對包含特征k的資源持消極的興趣偏好。如表1所示，作為對照，策略A不衰減任何偏好特征的影響，而在策略B中，模型同時衰減積極和消極偏好特征的影響，最后在策略C中，模型只衰減積極偏好特征的影響。

表1 Confuk的設置策略

表1中：wpredict(u,k)的值由式(12)計算得到，參數Tpredict是用來控制置信度Confuk的衰減參數：

(12)

4 實驗評估

為了評估模型的有效性，本文將模型與不同的遺忘機制相結合，并評估其模型性能。本文實驗數據集采用公開電影評分數據集MovieLens 1M，數據集中包含2000年到2003年間6 040名用戶對3 952部電影的1 000 209個評分，評分均為1至5分的整數，其中每名用戶至少貢獻了20個評分，且每部電影都被標記了至少一個種類信息。

4.1 對比模型

本文將提出的steamGBMF模型與一些具有代表性的算法進行比較：

? PMF[17]：Probabilistic Matrix Factorization是基于高斯觀測噪聲的概率線性模型。

? DA-PMF[6]：Dual-Averaging Method for PMF是一種面向特征向量的增量矩陣分解模型，其通過將當前特征向量與流數據中的特征相結合的方式來更新模型參數。

? timeSVD[9]：bias-SVD[18]的時間變種模型，可以捕捉用戶評價標準隨時間的變化現象。

4.2 實驗設定

為了模擬流數據環境，本文將數據按時間順序進行排序，并將排序后的數據按照下方兩種實驗設定進行分割：

1) T8：選擇前80%的數據作為訓練集，剩下20%的數據作為測試集。

2) T9：選擇前90%的數據作為訓練集，剩下10%的數據作為測試集。

基于上述實驗設定，有部分用戶的數據只存在于訓練集中或只存在于測試集中，這雖然加大了模型預測的難度，但該現象也與現實中流數據設定的情況相符。本文通過均方根誤差(RMSE)來評估模型的性能。為便于實驗對比，對比模型中的公共參數將被賦予相同的值，因MovieLens 1M數據集中種類信息一共有18種，所以特征向量的維度K設為18，正則化系數λ被設為0.1，學習率η的值為0.01。

4.3 實驗結果

各模型的對比實驗結果如表2所示，在流數據的環境中，PMF表現一般，說明了靜態模型在流數據環境下的劣勢。通過對比timeSVD模型與streamGBMF模型，可以發現在去除了動態基線估計的影響后，本文流模型在性能上有所提升。通過對比DA-PMF模型與本文模型的實驗結果，驗證了本文流模型通過資源的種類信息來構建資源的特征矩陣，并在增量更新時采取只對用戶特征向量進行訓練的方式，在一定程度上避免了由全連接結構帶來的擬合殘差擴大的問題，取得了比傳統增量矩陣分解模型更優的實驗結果。

表2 模型性能對比(RMSE)

為了評估模型中遺忘機制帶來的影響，將本文提出的兩種遺忘機制與Sensitivity-based Forgetting[16]方法進行比較，Sensitivity-based Forgetting方法對于每一條新的數據，計算其對于用戶的特征產生了多少變化，若新的數據大幅改變了原有的用戶特征，則這條數據被認為與用戶之前的偏好不相同，因此將被移除。此外，為了對照實驗，本文將沒有結合任何遺忘機制的實驗結果加入進行對比，記為NoForgetting。由圖1和圖2所示，Sensitivity-based Forgetting方法的效果與NoForgetting相差無幾，意味著該方法在移除奇異點的同時，也丟失了部分流數據中的重要信息。而本文提出的奇異點移除法(Outliers Discarding)的實驗結果要優于Sensitivity-based Forgetting方法，證明了奇異點移除法中采取只移除歷史數據中的奇異點的策略是有效的，該策略很好地保留了流數據中的用戶興趣轉移信息。實驗結果表明，本文提出的時間衰減置信度法(Time-decay Confidence)在T8和T9的實驗設定下都取得了最優的實驗結果，證明了該遺忘機制的優越性，表明該方法能使模型在捕捉用戶興趣轉移現象的同時，有效保留了用戶的長期偏好信息。

圖1 T8設定下遺忘機制的實驗對比

圖2 T9設定下遺忘機制的實驗對比

4.4 參數影響

在這一節中將對時間衰減置信度法中高階參數的影響進行實驗分析。

1)Ttrain的影響。Ttrain是模型訓練過程中用來控制過時數據對于模型訓練影響的衰減參數，其值越大，過時數據對于模型的影響越大。如圖3所示，當Ttrain取值過低時，在訓練過程中會過度忽略歷史數據中的重要信息，導致推薦質量下降，而當其取值過大時，則會導致時間衰減的效果降低，使模型無法傾向于捕捉用戶最新的興趣偏好信息。實驗結果表明，當Ttrain取值為700天時，模型取得了最優的實驗結果。

圖3 Ttrain參數的影響

2)Tpredict的影響。Tpredict是用來控制用戶陳舊特征對于模型預測結果影響的衰減參數，其值越小，模型對于用戶陳舊特征的真實性把握就越小。圖4和圖5展示了本文模型在T8和T9實驗設定下，當Tpredict取不同值時的實驗對比結果。其中對積極和消極的用戶特征同時衰減的策略B取得了最優的實驗結果，而僅對積極的用戶特征衰減的策略C取得了次優的實驗結果，這與本文中提出的假設“用戶會持續避免與不喜歡的類型的資源接觸”有一定出入。但與不作任何衰減的策略A相比，衰減策略B與衰減策略C均起到了一定的優化效果，且當Tpredict取值為60天時，取得了最優的實驗結果。

圖4 T8設定下預測策略的實驗對比

圖5 T9設定下預測策略的實驗對比

5 結 語

本文提出了一種基于資源種類信息的流式推薦模型streamGBMF，避免了傳統增量矩陣分解模型中存在的擬合殘差擴大問題。并基于streamGBMF模型的特點，提出了兩種改進的遺忘機制，可以有效區分用戶的長期偏好與臨時偏好，從而使模型能夠更準確地把握用戶的興趣偏好。實驗結果驗證了本文算法的有效性。后續將研究矩陣預填充技術，用于改善評分矩陣稀疏性問題。