缺失數據建模的改進型ALS在線推薦算法

邢玉瑩,,

(江南大學 數字媒體學院,江蘇 無錫 214122)

0 概述

隨著信息技術的快速發展,推薦系統成為解決信息過載問題的重要工具之一。其中,個性化推薦[1]作為現代推薦系統的主流,在實際中被廣泛應用,其根據用戶行為來為用戶提供個性化服務,以滿足各類用戶的不同需求。

協同過濾推薦算法是應用最廣泛的推薦算法之一,它使用用戶對物品的評分矩陣來訓練推薦模型,然后進行預測并向用戶推薦其感興趣的事物或產品[2]。隨著推薦系統數據量的不斷增多,矩陣分解方法[3]成為獲取用戶特征和物品特征的重要技術,其核心設計思想是將高維評分矩陣分解成低維用戶特征矩陣與物品特征矩陣的乘積。在已有研究中,基于矩陣分解的協同過濾算法是面向用戶評分[4]的,但用戶評分的來源和可靠性存在局限性,在很多場景中無法獲得準確的用戶評分[5]。

多數推薦系統收集到的數據是用戶正向選擇行為的記錄,如購買記錄、瀏覽歷史等隱式反饋信息。用戶在信息系統中無意留下的大量隱式反饋信息很容易被獲得。但與用戶評分相比,隱式反饋信息存在2個主要缺陷:只包含用戶正傾向信息而缺乏負傾向信息,這類問題稱為單類問題[6];存在數據噪聲,如用戶購買某物品作為禮物但用戶自己不一定喜歡該物品。此外,隱式數據是用戶日常行為的記錄,數據稀疏性導致其存在大量缺失數據,在訓練時,矩陣分解方法無法充分提取用戶和物品特征。

針對以上問題,目前較流行的處理方法是將缺失數據都作為負樣本并設置較小的權重,將其加入基于權值的模型中,并采用帶權的交替最小二乘(weighted Alternating Least Square,wALS)矩陣分解方法進行離線批量訓練[6-7]。但是,數據缺失并不是隨機產生的[8-9],其針對每個用戶成為負樣本的概率不同,設置統一的權重不適合實際推薦場景。此外,用戶的興趣往往隨時間變化而變化,推薦系統的時效性對用戶的滿意度有極大影響,為了更好地服務用戶,實時更新推薦模型非常重要[10]。而利用觀測數據和全部缺失數據并采用矩陣分解來訓練推薦模型,會大幅降低訓練效率,導致矩陣分解技術與在線學習算法的結合較難實現。

為解決上述問題,本文提出一種缺失數據建模的改進型交替最小二乘在線推薦算法NeALS,其依據物品相似度啟發式地為用戶選擇正樣本,并構建用戶近鄰評分矩陣代替原始矩陣進行模型訓練,以減小數據噪聲。此外,該算法根據物品流行度構建流行置信度函數,采用加權法對缺失數據建模,并處理缺失數據中的負樣本。為及時獲取用戶興趣的動態變化,本文將基于元素的改進型ALS算法與在線學習算法相結合,以提高在線學習效率。

1 相關工作

定義Rm×n為具有m個用戶、n個物品的二元隱式反饋矩陣。Rui∈R,Rui=1表示用戶u選擇了物品i,Rui=0表示用戶u對物品i沒有行為記錄。Pm×k和Qn×k分別表示用戶和物品的特征矩陣。其中,k是特征因子的個數。pu∈P和qi∈Q分別為用戶和物品的特征向量。

1.1 基于隱式反饋的矩陣分解推薦算法

矩陣分解算法的設計思路是用戶行為受多種因素的影響,且不同因素的影響程度不同[11]。因此,用戶u對物品i的偏好可定義為:

由于隱式反饋存在單類問題,因此傳統基于矩陣分解的推薦模型不能直接應用于隱式反饋的推薦場景中。解決單類問題的總體思路是引入負樣本,將缺失數據都作為負樣本并為其設置較小的權重。

文獻[7]提出基本帶權潛在因子模型的損失函數為:

其中,wui是樣本實例的置信度,λ是正則系數。

確定加權矩陣的構成后,wALS是優化矩陣分解模型的常用方法。然而,引入負樣本將導致wALS訓練負擔的增加,其時間復雜度為O((m+n)k3+mnk2),嚴重影響訓練效率。為降低時間復雜度,文獻[12]提出隨機塊坐標下降法(Randomized block coordinate descent,Rcd),文獻[13]提出基于元素的交替最小二乘(element-wise Alternating Least Square,eALS)矩陣分解算法,該算法交替更新模型參數中的每個坐標元素,直至其達到聯合最優值。

以上方法均認為用戶有過正向行為的物品為用戶喜歡的物品,忽略了隱式反饋中存在的數據噪聲。隱式反饋不能明確反映用戶對物品的偏好程度,其對用戶歷史反饋不進行區分,由此導致矩陣分解時特征提取不明確。本文提出的NeALS算法根據物品相似度來為用戶選擇正樣本,對與用戶相關的物品和不相關的物品進行區分,并依據物品的流行度構建流行置信度函數,然后對缺失數據進行建模,以適應實際隱式反饋推薦場景。

1.2 基于隱式反饋的在線推薦模型

傳統推薦算法(如timeSVD++)通過結合時間信息來提高預測準確率,但這類算法仍使用離線批量訓練的模式[14-15]。由于隱式反饋是系統自動記錄下的用戶行為,其會連續不斷地產生,因此使用離線批量訓練將無法及時利用用戶最近的反饋信息。這些用戶最近的反饋信息具有較大的研究價值,它們反映了用戶近一段時間的興趣,因此,其會影響推薦結果。

為及時獲取用戶興趣的變化,避免“新用戶”(這里指沒有任何反饋信息的用戶)的冷啟動問題,文獻[16]在微博推薦場景下提出RMFX模型,對基于隱式反饋數據流構建實時推薦模型進行進一步研究。文獻[12]提出適用于在線更新的Rcd算法。文獻[13]將基于元素的最小二乘矩陣分解方法與在線學習算法進行結合。

但以上在線模型對用戶新反饋信息和歷史反饋信息沒有進行區分,這在一定程度上限制了在線學習的效果。為此,本文對新用戶反饋信息進行加強學習,同時,對缺失數據的置信度作實時更新,以達到提高在線學習效果的目的。

2 改進型ALS在線推薦算法

2.1 近鄰評分矩陣構建

由于隱式反饋是用戶日常行為的記錄,僅依靠用戶行為對用戶的偏好進行預測較困難。比如,某用戶購買了一件物品作為贈送他人的禮物,但該物品并非用戶自己所喜歡的,又或者用戶購買后發現該物品并不令人滿意。在這種情況下,用戶的隱式反饋不一定能反映出其真實的喜好,即存在數據噪聲。

為解決上述問題,本文利用物品的相似度來啟發式地區分與用戶相關的物品和不相關的物品[17],將與用戶選擇過的物品相似度都較高的物品作為正樣本,構建近鄰評分矩陣S代替原始矩陣R,從而在使用矩陣分解方法訓練模型時,有效減小數據噪聲的影響。構建近鄰評分矩陣的具體步驟如下:

1)使用余弦相似度來計算物品i和物品j的相似度:

2)計算用戶u對物品i的評分:

sui=RuSimi

(4)

其中,Sim是n×n維的物品相似矩陣。

3)為每個用戶選擇評分在前ρ個的物品添加在其近鄰評分矩陣S中。

目前,多數推薦系統會定期計算物品相似度,因此,不會導致計算成本增加。構建近鄰評分矩陣的時間復雜度為O(mn)。

2.2 流行置信度定義與ALS算法改進

缺失數據包括負樣本和潛在正樣本,因此,使用加權法對缺失數據建模的關鍵步驟是如何區分負樣本和潛在正樣本。

對缺失數據每個樣本實例賦予不同的權值時,會消耗大量的存儲空間。為解決該問題,wALS方法和Rcd方法為每個缺失數據設置相同的權重,然而,針對同一用戶,在實際推薦場景中不同物品被稱為負樣本的概率不同。

在推薦系統中存在流行偏置問題,即推薦系統往往會向用戶推薦流行產品,物品越流行,被推薦的次數越多[18-19]。因此,用戶獲取物品受物品流行度的影響,即用戶更容易獲取流行的物品。針對流行度偏置問題,本文認為,如果一個物品流行度高,但是用戶并沒有對其發生正向行為,則該物品對此用戶成為負樣本的概率較大。依據物品的流行度構建不同物品在加權矩陣分解推薦模型中的置信度函數如下:

其中,fi是R中物品i的頻數,其表示i的流行度。流行度不為0的物品成為負樣本的概率與流行度正相關。對于新物品,則設置統一權重。

結合上文構建的近鄰評分矩陣,基于物品流行度加權的隱式反饋推薦模型損失函數為:

其中,wui是正樣本的置信度,wui=sui。因為隱式反饋矩陣是一個二元矩陣,已有研究認為所有能觀察到的隱式反饋都可以作為正樣本,而沒有區分與用戶相關的物品和不相關的物品。本文結合近鄰評分矩陣為用戶選擇正樣本,并根據用戶對物品的評分來對其設置不同權重。

為提高矩陣分解的訓練效率,采用eALS算法對式(6)關于puf求導,并令一階導數等于0,計算得:

(7)

(8)

將式(8)進一步優化為:

使用以上優化方法可將式(7)改寫為:

(11)

同理,有:

(12)

其中,Si表示所有選擇物品S的用戶集合向量。

缺失數據建模的改進型ALS算法偽代碼如下:

算法1缺失數據建模的改進型ALS算法

輸入近鄰評分矩陣S,潛在特征維度k,正則化系數λ

輸出用戶特征矩陣P,物品特征矩陣Q

1.初始化P,Q;對(u,i)∈S,wui=sui;//對每個物品i,根//據式(5)計算w0(i)

3.計算Cq和Cp;

4.while沒有達到終止條件 do

5.for u=1 to m do

6.for f=1 to k do

8.更新puf=式(11);

10.end for

11.end for

12.更新Cp;

13.for i=1 to n do

14.for f=1 to k do

16.根據式(12)更新qif;

18.end for

19.end for

20.更新Cq;

21.end while

22.輸出P和Q

該算法在一次迭代中,更新Cp和Cq的時間復雜度分別為O(mk2)和O(nk2)。更新一次用戶u的特征向量pu的時間復雜度為O(|Su|k+k2),更新m個用戶特征向量的時間復雜度為O(|S|k+mk2),其中,|S|是矩陣S中非零元素的個數。同理,更新n個物品特征向量的時間復雜度為O(|S|k+nk2)。因此,算法完成一次迭代的總時間復雜度為O(|S|k+(n+m)k2),與wALS算法相比,降低了k倍。該算法的效率受近鄰評分矩陣S中所選擇正樣本的數量影響,而eALS和Rcd算法的時間復雜度為O(|R|k+(n+m)k2),其與原始矩陣的樣本數量相關。因此,相比eALS算法和Rcd算法,缺失數據建模的改進型ALS算法的效率是否提高,取決于|S|和|R|的大小。

2.3 在線推薦模型

缺失數據建模的改進型ALS算法仍采用離線批量訓練的模式,這種模式存在訓練效率低且信息利用不及時的局限性。為此,本文將缺失數據建模的改進型ALS算法擴展為在線模型,提出一種缺失數據建模的改進型ALS在線推薦算法NeALS,算法框架如圖1所示。

圖1 NeALS算法框架

與離線批量訓練模式不同,在線訓練模式無需一次性重復訓練一批樣本,而是隨著用戶新的反饋數據來實時更新推薦模型。新反饋以數據流的形式進入推薦系統后,算法更新用戶u和物品i對應的用戶特征向量pu和物品特征向量qi。新反饋只會影響用戶u和物品i,并不會影響整個用戶和物品特征矩陣。

在用戶的反饋中包含2種情況:1)反映用戶新興趣的反饋,這類反饋反映出用戶近期喜好,對于推薦系統具有很高的價值;2)用戶習慣行為的反饋,推薦系統已經從歷史反饋中充分學習到用戶和物品特征,需要弱化學習[10]。對于反映用戶新興趣的反饋應加強學習,給予比歷史反饋更高的權重wnew。據此,本文提出的NeALS算法偽代碼如下。

算法2NeALS算法

輸出更新后的P、Q

1.順序讀取隱式反饋(u,i)

2.if u是一個新用戶 do 隨機初始化pu;

3.if i是一個新物品 do 隨機初始化qi;

4.if (u,i)∈S do wui=sui;

5.else

6.sui=1;

7.wui=wnew;

8.end if

10.根據式(11)更新pu;

11.更新 Cp;

12.根據式(12)更新qi;

13.更新 Cq;

14.直至沒有新的隱式反饋數據

15.輸出P,Q

NeALS算法更新一次pu的時間復雜度為O(k2+|Su|k),更新一次qi的時間復雜度為O(k2+|Si|k),更新Cp和Cq的時間復雜度為O(k2)。因此,算法完成一次在線學習的時間復雜度為O(k2+(|Su|+|Si|)k)。

3 實驗結果與分析

本節通過離線實驗和在線實驗分析各參數對算法推薦結果的影響,并將本文算法與其他基于隱式反饋的推薦算法進行比較。

3.1 數據集

本次實驗數據來自MovieLens-1M數據集,該數據集包含6 040個用戶和3 706部電影,共1 000 209條評價記錄,其中,用戶至少對20部電影有評分,電影評分為1分～5分。為將該數據集轉換成隱式反饋數據集,將有評分的數據值均設為1,沒有評分的數據值設為0。

實驗分為離線實驗和在線實驗,根據用戶瀏覽電影的記錄按照時間順序從小到大排序數據集。離線實驗采用離線批量訓練的模式,分別選擇前30%、50%、70%的數據作為訓練集,其余數據作為測試集,分析訓練集數據量的大小對推薦結果的影響。在線實驗選擇前70%的數據作為訓練集,后30%的數據作為測試集,根據實際中的推薦系統場景模擬動態數據流。首先,使用訓練集離線訓練推薦模型,為每個用戶生成一個Top-N的推薦列表;然后,將測試集中的數據以數據流的形式輸入,更新推薦模型并重排推薦列表;最終,由測試得到的相關數值來分析推薦算法的性能。

3.2 評價標準

本實驗評價標準采用Top-N推薦中常用的2個指標:命中率(HR)和歸一化折扣累計利潤(NDCG)。HR是指系統每次向用戶推薦N個物品,用戶選擇的物品占推薦物品的比例。NDCG反映用戶喜歡的物品在推薦列表中的位置準確性。各算法的評價結果為執行5次實驗結果的平均值。

3.3 離線實驗

本文根據文獻[12]經驗地設置潛在特征維數為50,迭代次數為25,正則系數為0.01。在NeALS算法中,近鄰評分矩陣的正樣本數ρ的大小是重要影響因素。

表1所示為不同的基于隱式反饋的推薦算法在訓練集為30%、50%和70%下得到的Top-30的HR值和NDCG值。NeALS算法為每個用戶選擇不同數量的正樣本構建近鄰評分矩陣,ρ的取值分別為50、100、500,流行度不為0的物品設置負樣本權重正相關于流行度,流行度為0的物品設置負樣本權重w0=0.2。wALS算法和Rcd算法的正樣本權重w1=1,將缺失數據都看作負樣本進行訓練,負樣本的權重為w0=0.2。eALS算法正樣本權重w1=1,流行度不為0的物品設置負樣本權重正相關于流行度。

表1 不同基于隱式反饋的推薦算法推薦效果對比

由表1可以看出:

1)隨著為每個用戶選擇的正樣本數量的增加,HR和NDCG均逐漸降低。這說明引入一些用戶可能不感興趣的偽正樣本,導致在使用矩陣分解訓練模型時提取出了錯誤的特征信息。

2)在不同大小的訓練集中,使用ALS模型比使用Rcd模型在矩陣稀疏的情況下效果更好。

3)在離線實驗中,無論訓練集數據大小如何變化,根據物品相似度為每個用戶選擇50個正樣本構成近鄰評分矩陣,應用NeALS算法進行模型訓練,其推薦效果明顯優于其他對比方法。因此,在線實驗中選取ρ=50。

本文NeALS算法較其他算法的推薦效果有所提高,原因是NeALS算法使用近鄰評分矩陣代替原始矩陣訓練模型,能夠合理區分出與用戶相關和不相關的物品。此外,根據流行度對缺失數據進行加權,同時將新物品也一同加入模型中訓練,更適合基于隱式反饋的推薦場景。

3.4 在線實驗

在線實驗將測試集中的用戶反饋以數據流的形式輸入系統,平均每10 000次連續推薦進行一次推薦效果評價。本次實驗研究新反饋的權重對推薦效果的影響,由于wALS算法的時間復雜度較高,不適合應用于在線推薦,因此本次實驗只對比NeALS算法和Rcd算法、eALS算法在在線模式下Top-30的推薦效果。

3.4.1 參數分析

由于用戶新反饋中包含用戶新的興趣,因此這類反饋對系統而言具有比歷史數據更高的價值。圖2所示為新反饋的權重對在線學習算法結果的影響。由圖2可以看出,當wnew設置為1時,新的反饋數據和歷史反饋數據具有相同的權值。隨著wnew的增加,NeALS算法和Rcd算法、eALS算法的NDCG均逐步提高。Rcd算法在wnew=2處NDCG達到最大值,NeALS算法和eALS算法在wnew=8時達到最好的推薦效果。對新反饋的加強學習在一定程度上強化了用戶的短期興趣。但隨著wnew的繼續增加,3種算法的NDCG均呈下降趨勢。因此,可以得出結論:平衡用戶近期興趣和歷史興趣對推薦系統十分重要。但無論wnew取何值,本文NeALS算法的推薦效果均優于eALS算法和Rcd算法。

圖2 新反饋的權重wnew對3種在線推薦算法的影響

3.4.2 算法性能分析

在流入樣本數相同時,Rcd算法選擇wnew=2作為新反饋的權重,eALS算法和NeALS算法選擇wnew=8作為新反饋的權重。圖3所示為3種算法的在線推薦結果對比。

圖3 3種算法Top-30在線推薦結果對比

流入樣本數為0時,是算法在離線批量訓練時得到的結果。由圖3可以看出:

1)在線模型比離線模型在推薦效果上更有優勢。在線訓練能夠及時捕獲用戶的興趣變化,而離線訓練存在信息利用不及時的局限性。此外,對于一個沒有任何歷史記錄的新用戶,若采用離線模型,推薦給他的物品幾乎是隨機的。而在線模型中,當捕捉到用戶第一個行為記錄時,就會有效地提高推薦效果,隨著用戶反饋的增加,推薦效果會進一步提高。因此,在線模型在一定程度上能夠改善離線模型的冷啟動問題。

2)eALS算法在開始有樣本流入時HR和NDCG先下降再上升。NeALS算法和Rcd算法均隨著流入樣本數的增加,HR和NDCG先上升最后達到平穩,達到平穩后,隨著流入樣本數的增加,2種算法推薦效果均沒有特別明顯的變化。這是因為電影更新速度較慢且用戶的興趣變化不大,當一個用戶看過很多電影后,其之后的選擇可能不會有太大變化。

3)NeALS算法取得了比eALS算法和Rcd算法更好的在線推薦效果,這說明結合物品近鄰信息能夠在一定程度上減小原始數據中的數據噪聲,且構造流行置信度函數對缺失數據建模,可以有效提高推薦的精確度。

4 結束語

本文建立一種基于快速矩陣分解和隱式反饋的在線推薦模型。針對隱式反饋存在數據噪聲的問題,使用物品相似度信息啟發式地選擇與用戶相關度較高的物品作為正樣本,并構造近鄰評分矩陣代替原始數據矩陣進行模型訓練。同時,提出缺失數據建模的改進型ALS算法,根據物品流行度構建流行置信度函數并作為缺失數據的權值。在此基礎上,結合基于元素的優化思想對ALS算法進行改進,最終提出基于隱式反饋的在線推薦算法NeALS。在真實數據集MovieLens上進行的離線和在線實驗結果表明,NeALS算法能夠有效提高推薦的精確度和效率。下一步將考慮不引入負樣本,而直接對用戶的行為進行建模,并將改進后的算法應用于電子商務中。