一種基于用戶興趣轉(zhuǎn)移挖掘的流式推薦算法

陳建宗 劉永堅 解 慶 唐伶俐

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

0 引 言

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

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

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

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

1 相關(guān)工作

1.1 流式推薦系統(tǒng)

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

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

1.2 用戶興趣轉(zhuǎn)移

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

2 符號與概念預定義

2.1 符 號

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

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

?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：分別表示在訓練和預測階段的衰減系數(shù)。

2.2 動態(tài)基線估計

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

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

(1)

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

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

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

(2)

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

3 模型設計

3.1 離線訓練

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

由于每一個資源的種類信息數(shù)量是有限的，因此構(gòu)建的模型中每個資源都只與少數(shù)幾個特征相關(guān)聯(lián)，從而打破了傳統(tǒng)矩陣分解模型的全連接結(jié)構(gòu)：

(3)

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

(4)

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

3.2 在線學習

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

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

λ‖Uu‖2

(5)

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

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

(6)

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

(7)

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

3.3 遺忘機制

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

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

(8)

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

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

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

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

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

(9)

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

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

(10)

對于用戶興趣轉(zhuǎn)移的另外一種情況，其背后的邏輯是用戶會持續(xù)與自己感興趣的類型資源產(chǎn)生交互，直到對其不再感興趣為止，反之，用戶會盡量避免與他們不喜歡的類型資源產(chǎn)生交互?；谠摷僭O，模型為用戶特征向量的特征值Uuk(t)定義了一個置信度參數(shù)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)計算得到，參數(shù)Tpredict是用來控制置信度Confuk的衰減參數(shù)：

(12)

4 實驗評估

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

4.1 對比模型

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

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

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

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

4.2 實驗設定

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

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

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

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

4.3 實驗結(jié)果

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

表2 模型性能對比(RMSE)

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

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

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

4.4 參數(shù)影響

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

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

圖3 Ttrain參數(shù)的影響

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

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

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

5 結(jié) 語

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