何 婧,胡 杰
(西南財經(jīng)大學(xué) 統(tǒng)計學(xué)院,成都611130)
隨著互聯(lián)網(wǎng)時代的來臨,網(wǎng)絡(luò)資源數(shù)量呈爆炸式增長,個性化推薦系統(tǒng)建立在大量用戶數(shù)據(jù)的基礎(chǔ)上,能夠?yàn)槊课挥脩敉扑]出最感興趣或者最需要的信息。近年來,個性化推薦算法已經(jīng)成為學(xué)術(shù)界的研究熱點(diǎn)之一。推薦系統(tǒng)中應(yīng)用最廣泛的是協(xié)同過濾推薦算法(CF,Collaborative Filtering),其概念最早由1992年Goldberg等[1]在開發(fā)Tapestry郵件過濾系統(tǒng)時首次提出,其核心思想是通過算法對用戶的歷史行為數(shù)據(jù)進(jìn)行分析,并挖掘出用戶的興趣偏好,根據(jù)不同的興趣偏好對用戶進(jìn)行類別劃分并推薦偏好相似的物品。目前,在推薦算法中還存在數(shù)據(jù)稀疏性、可擴(kuò)展性、冷啟動等問題。數(shù)據(jù)的稀疏性是造成推薦系統(tǒng)精確度不高的主要原因之一。廣泛應(yīng)用的推薦系統(tǒng)中,用戶 項目(user-item)評分矩陣提供了反映用戶對項目喜好程度的重要信息。當(dāng)項目數(shù)量巨大時,評分矩陣往往具有高度的稀疏性,缺失率甚至?xí)_(dá)到90%以上。極度稀疏的用戶評分矩陣會使得利用經(jīng)典的協(xié)同過濾算法計算的相似性精度不高,無法準(zhǔn)確找出目標(biāo)用戶的最近鄰居。為解決評分矩陣的稀疏性問題,常用的方法有兩類,一類是基于預(yù)測項目評分的協(xié)同過濾算法,例如,韓亞楠等[3]和Liji等[4]分別利用用戶屬性偏好和用戶的屬性來對評分矩陣進(jìn)行填充。另一類解決稀疏性的方法是利用奇異值分解(SVD,Singular Value Decomposition)對評分矩陣進(jìn)行降維[5-7]。但在維數(shù)很高的情形中,降維將會導(dǎo)致信息損失,影響模型預(yù)測效果。Bokde等[8-9]指出將多種傳統(tǒng)推薦算法相結(jié)合可以有效提高推薦精確度。當(dāng)用戶與項目數(shù)量巨大時,計算量較大,推薦算法很難在短時間內(nèi)作出響應(yīng)。在推薦算法中融合聚類方法可以有效提高推薦系統(tǒng)的響應(yīng)速度[9-11]。
除了上述基于協(xié)同過濾算法建立的個性化推薦系統(tǒng),也有很多基于機(jī)器學(xué)習(xí)方法建立的推薦系統(tǒng),例如,胡思才等[12]建立了基于深度神經(jīng)網(wǎng)絡(luò)和概率矩陣分解的混合推薦算法;Wei等[13]結(jié)合協(xié)同過濾與深度學(xué)習(xí)方法解決冷啟動問題。Wang等[14]提出的樹增強(qiáng)嵌入方法并結(jié)合樹模型和嵌入模型的優(yōu)點(diǎn),使得推薦模型同時具有可泛化性和可解釋性。Chen[15]提出了XGBoost(eXtreme Gradient Boosting)算法,它是一種集成樹模型,能在梯度提升(Gradient Boosting)框架下實(shí)現(xiàn)大規(guī)模集成學(xué)習(xí),其特點(diǎn)是計算高效,能夠解決實(shí)際問題。分析結(jié)果顯示,XGBoost算法有助于提升推薦問題中的精確度[17-18]。這歸功于XGBoost算法能從大規(guī)模數(shù)據(jù)集中學(xué)習(xí)到數(shù)據(jù)之間復(fù)雜的相關(guān)性。
為了解決評分矩陣的稀疏性問題,提高推薦精確度,文中提出基于矩陣分解與XGBoost集成學(xué)習(xí)方法構(gòu)建的個性化推薦算法MFXGB(Matrix Factorization XGBoost algorithm)。該推薦算法實(shí)質(zhì)為一個監(jiān)督模型,可以充分利用用戶 項目評分矩陣中的信息和用戶及項目自身的特征,利用聚類方法降低計算時間,并且能夠有效提高推薦的準(zhǔn)確度。
MFXGB推薦算法可分為3個階段,第一階段就是采用矩陣分解的方法來填充用戶 項目評分矩陣。假設(shè)用戶 項目評分矩陣R=r(ui)n×m,它包含了n個用戶對m個項目的評分,其中,元素r ui表示用戶u對項目i的評分。經(jīng)典的矩陣分解方法為SVD算法[18],是將含有缺失值的用戶 項目評分矩陣R,用來近似,即選擇一個小于n和m的d,去估計維度為n×d的矩陣P n×d和維度為d×m的矩陣Q d×m。假設(shè)q i∈Rd為矩陣Q的第i列向量,p u∈Rd為矩陣P的第u行向量,則它們的內(nèi)積代表用戶u對項目i的興趣偏好,即預(yù)測評分,記為。需要估計P和Q,使得它們的乘積近似等于評分矩陣考慮到用戶和項目都存在個體偏差,用戶u對項目i的預(yù)測評分可表示為
其中:μ為基準(zhǔn)評分;b i為項目i的個體偏差;b u為用戶u的個體偏差。
SVD++算法[18]在SVD算法的基礎(chǔ)上進(jìn)一步引入了用戶對有過評分行為的項目的“隱式反饋”信息。假設(shè)用戶u對項目i有評分,代表該用戶u對項目i有偏好,在式(1)中進(jìn)一步增加用戶u的已有偏好信息。定義x j∈Rd,j=1,…,m為每個項目對應(yīng)的因子向量,表示項目j的評分特征向量。用戶u對項目i的近似評分可以表示為式(2)。
其中:N u()表示用戶u評價過的項目集合表示用戶u給出評價的項目數(shù)。式(2)相較于式(1)增加了已有評分的所有隱含信息項估計特征矩陣P和Q可以通過最優(yōu)化式(3)中的目標(biāo)函數(shù)來實(shí)現(xiàn),該目標(biāo)函數(shù)是由損失函數(shù)加上正則項構(gòu)成,λ為正則項中的調(diào)節(jié)參數(shù)。
MFXGB推薦算法采用SVD++算法填充用戶 項目評分矩陣,將最優(yōu)化式(3)得到的特征矩陣估計和帶回式(2),對用戶 項目評分矩陣中R中的缺失值進(jìn)行填充。
MFXGB算法的第二階段就是利用聚類算法構(gòu)造用戶和項目的特征。第一階段已經(jīng)利用矩陣分解的方法得到了填充完整的用戶評分矩陣,即預(yù)測得到了用戶 項目的“評分”特征,可以用作模型的自變量。但在實(shí)際應(yīng)用中,用戶和項目的個數(shù)都可能巨大,將其作為自變量直接利用XGBoost算法進(jìn)行訓(xùn)練的計算成本過高,對處理大數(shù)據(jù)時產(chǎn)生的計算量巨大的問題尤為突出。為此,采用聚類方法將用戶和項目按相似度分門別類,再計算每個用戶和項目的“類別”特征,以節(jié)約計算時間。
具體來說,用戶評分矩陣的行向量代表用戶的評分向量?;趎個用戶的評分向量,將這n個用戶分成K1個類別,每個類別代表用戶的評分偏好屬性。例如,有些用戶比較挑剔,總是給予很低的評分,可以將其歸入一個類別;有些用戶總是給予較高的評分,則將其歸入另一個類別。文中采用K-均值方法進(jìn)行聚類,類別數(shù)K1可根據(jù)實(shí)際問題自行設(shè)定。特別地,若K1=n,則代表不對用戶進(jìn)行聚類,以每個用戶的評分向量作為其“評分”特征。同理,將m個項目分成K2個類別,每個類別代表項目的類別評分屬性。例如,有些小眾的文藝電影總是評分不高,而有些動作大片受到很多人的關(guān)注和歡迎,可以分別將它們歸入不同的類別。同理,若K2=m,則代表不對項目進(jìn)行聚類。
進(jìn)行聚類后,可分別計算得到每類用戶和項目的中心向量,再通過計算每個用戶的評分向量與K1類用戶的中心向量之間的相似度,這就是用戶的“評分”特征。這里采用Pearson相關(guān)系數(shù)來計算評分向量與中心向量之間的相似度。相似度越高,表明該用戶與某個類別用戶的評分偏好越相似。例如,將用戶聚為三類,計算得到用戶1的評分向量與三類的中心向量的相似度分別為0.7、0.5和0.4,這表明用戶1和第一類用戶的評分偏好最為相似。將(0.7,0.5,0.4)這個向量作為用戶1的“評分”特征,在下一步中放入XGBoost模型進(jìn)行訓(xùn)練。同理,可以計算得到每個項目的評分向量與K2類項目的中心向量之間的相似度,作為項目的“評分”特征。
除此之外,每個用戶和每個項目還有其自身的特征,例如,基于電影的數(shù)據(jù)集中,用戶的年齡、性別、職業(yè)、電影的類別等。假設(shè)共有K3個這樣的特征,稱為基礎(chǔ)特征。那么,將K1個用戶“評分”特征、K2個項目“評分”特征和K3個用戶與項目的基礎(chǔ)特征結(jié)合在一起,構(gòu)成(nm)×(K1+K2+K3)維的特征矩陣,用于訓(xùn)練預(yù)測模型。
MFXGB算法的第三階段就是利用XGBoost算法訓(xùn)練推薦模型。XGBoost算法[15]利用集成樹模型預(yù)測響應(yīng)變量,并用梯度提升樹算法優(yōu)化求解。假設(shè)數(shù)據(jù)集中有n個樣本,p個特征,記為其中,y i∈R,X i∈Rp。集成樹模型是利用多棵回歸樹的結(jié)果對y i進(jìn)行預(yù)測,即
其中,f m為第m棵回歸樹的函數(shù)表達(dá)式。常用的回歸樹為加法形式,即其中,T表示回歸樹中的葉節(jié)點(diǎn)個數(shù);q(X i)表示回歸樹的劃分規(guī)則;ωj表示第j個葉節(jié)點(diǎn)上的輸出值;I(·)為示性函數(shù)。為了估計式(4)中的樹結(jié)構(gòu)和參數(shù),定義目標(biāo)函數(shù)為
其中,l(·,·)為損失函數(shù)為正則項,用于控制模型的復(fù)雜程度。XGBoost算法采用梯度提升樹(Gradient Tree Boosting)算法求解式(5)的最優(yōu)化問題,即使得目標(biāo)函數(shù)L達(dá)到最小。為求解該優(yōu)化問題,采用迭代法,在每一次迭代中都加入一棵新的回歸樹去減小估計誤差,則第t次迭代的目標(biāo)函數(shù)定義為
其中,g i和h i分別為損失函數(shù)在處的一階和二階導(dǎo)數(shù)。此處用二階泰勒展開近似目標(biāo)函數(shù)是XGBoost算法區(qū)別于經(jīng)典梯度提升樹算法的特點(diǎn)之一,有利于對目標(biāo)函數(shù)的快速優(yōu)化。給定一個回歸樹結(jié)構(gòu)及劃分規(guī)則q(X i),定義I j={i|q(X i)=j}為被劃分到葉節(jié)點(diǎn)j上的樣本集合。經(jīng)過推導(dǎo),可確定第t次迭代中的最優(yōu)權(quán)重和響應(yīng)的目標(biāo)函數(shù)值,表達(dá)式為
然后采用貪婪算法(Exact Greedy Algorithm)尋找最優(yōu)的q(·),使得達(dá)到最小,第t次迭代完成,進(jìn)入下一次迭代,直到滿足停止條件。
MFXGB算法第三階段將第二階段中構(gòu)建的特征矩陣中用戶和項目特征作為自變量X i∈RK1+K2+K3,以用戶對項目的評分作為因變量y i,i=1,…,nm。再利用XGBoost算法訓(xùn)練模型,并且對算法中的參數(shù)進(jìn)行調(diào)優(yōu),例如,優(yōu)化過程中的學(xué)習(xí)率、停止條件中的樹的最大深度、子模型的最大數(shù)量、正則化項中的參數(shù)λ和γ。最后,利用訓(xùn)練好的模型可以得到目標(biāo)用戶對未評分項目的預(yù)測評分,并以預(yù)測評分由高到低的順序向該用戶產(chǎn)生推薦結(jié)果。
基于矩陣分解的XGBoost個性化推薦算法(MFXGB)主要包括以下3個步驟,其算法步驟如圖1所示。
步驟1.使用SVD++的矩陣分解方法填充用戶 項目評分矩陣中缺失的元素;
步驟2.利用填充完整的矩陣通過聚類算法構(gòu)造用戶和項目的特征,即分別將用戶和項目進(jìn)行聚類,計算每個用戶和項目的“類別”特征,再加入用戶和項目的基礎(chǔ)信息,最終將數(shù)據(jù)集處理成一個適用于有監(jiān)督訓(xùn)練的數(shù)據(jù)集。
步驟3.使用XGBoost算法對目標(biāo)項目進(jìn)行評分預(yù)測,根據(jù)預(yù)測結(jié)果生成推薦列表。
圖1 MFXGB算法步驟結(jié)構(gòu)圖Fig.1 The flowcharts of the MFXGB algorithm
實(shí)驗(yàn)采用Minnesota大學(xué)Group Lens研究小組提供的Movie Lens實(shí)驗(yàn)數(shù)據(jù)集(http:∥grouplens.org/datasets/movielens/),其中包括2組不同規(guī)模的數(shù)據(jù)集,如表1所示。數(shù)據(jù)集的記錄格式為用戶ID、項目ID、評分值、評分時間,其中每個用戶至少對15部電影進(jìn)行評分,評分范圍為1~5的正整數(shù),值越高表示用戶對該電影的喜愛程度越高。
表1 MovieLens數(shù)據(jù)集描述Table 1 Data description of the MovieLens datasets
除了用戶評分?jǐn)?shù)據(jù)集外,還有用戶和電影的信息記錄維表。在用戶信息維表中,記錄了每個用戶的年齡、性別、職業(yè)與郵政編碼等信息。在電影信息維表中,記錄了電影的名稱、發(fā)布時間、鏈接以及所屬的類別等信息,原數(shù)據(jù)集中將所有電影共分為19個類別,每一部電影可能會屬于幾個不同的類別。
實(shí)驗(yàn)環(huán)境配置如下:PC Inter(R)Core(TM)i5-8300 H CPU@2.30GHz64位操作系統(tǒng),虛擬內(nèi)存24 G,編程語言:python3.7。
為了衡量算法的預(yù)測準(zhǔn)確度,采用平均絕對誤差(MAE,mean absolute error)和均方根誤差(RMSE,root mean square error)對算法進(jìn)行評價,其定義如下:
非洲豬瘟病毒和經(jīng)典豬瘟病毒若要通過飼料傳播,飼料需被病毒污染且以傳染性形式存活。不幸的是,在跨境運(yùn)輸中,僅少數(shù)飼料原料做了病毒存活性評估,來自美國多個委員會的一份關(guān)于飼料原料安全性的聯(lián)合文件給出了用于評估原料傳播風(fēng)險的決策樹。
為了避免偶然性對實(shí)驗(yàn)結(jié)果的影響,文中利用五折交叉驗(yàn)證的方法對推薦算法的效果進(jìn)行評估,即將原始數(shù)據(jù)集等分為5個子集,每次選擇其中的4個子集作為訓(xùn)練集,剩下的1個子集作為測試集。最終將5次實(shí)驗(yàn)中得到的預(yù)測誤差取平均值,來衡量算法的推薦精確度。將文中MFXGB推薦算法的結(jié)果與傳統(tǒng)的協(xié)同過濾推薦算法進(jìn)行對比。
2.3.1 算法的效果展示
將MFXGB算法與矩陣分解(SVD++)推薦算法、基于項目的協(xié)同過濾推薦算法(Item-CF)和基于用戶的協(xié)同過濾推薦算法(User-CF)進(jìn)行比較,以驗(yàn)證MFXGB算法的有效性。取聚類數(shù)為60,在MFXGB算法中取K1=K2=60,基于數(shù)據(jù)集Movie Lens_100k計算得到的實(shí)驗(yàn)結(jié)果,如圖2所示。
可以看出,MFXGB推薦算法的RMSE和MAE明顯小于傳統(tǒng)的協(xié)同過濾推薦算法和矩陣分解算法。特別地,不進(jìn)行聚類的MFXGB模型的預(yù)測效果最好,RMSE比SVD++算法提升了26.61%,比Item-CF和User-CF算法分別提升了27.64%和28.93%,MAE相比于SVD++算法、Item-CF和User-CF算法分別提升了28.93%、30.08%和31.51%。當(dāng)聚類數(shù)K1=K2=60時,MFXGB算法的RMSE比SVD++、和Item-CF和User-CF算法分別提升了8.91%、10.18%和11.79%,MAE分別提升了8.79%、10.26%和12.10%,推薦精確度也有明顯提高。但是,不進(jìn)行聚類的MFXGB算法計算成本非常高,它的計算時間是MFXGB算法(K1=K2=60)的14.96倍??梢娎镁垲惙椒?gòu)造特征將有效提升計算速度。
為了避免小數(shù)據(jù)集帶來的偶然性,采用數(shù)據(jù)量更大的Movie Lens_1M數(shù)據(jù)集驗(yàn)證算法的普適性,仍取聚類數(shù)為60,實(shí)驗(yàn)結(jié)果如圖3所示。不聚類的MFXGB算法計算量較大,計算時間將超過30 h,因此未記錄不聚類的MFXGB算法結(jié)果。同樣可以看出,針對MovieLens_1M數(shù)據(jù)集,MFXGB推薦算法的精確度都明顯好于其他3種算法。
圖2 基于MovieLens_100k數(shù)據(jù)集的各算法結(jié)果對比圖Fig.2 RMSE and MAE comparison of MFXGB algorithm,SVD++algorithm,Item-based CF algorithm and User-based CF algorithm using the MovieLens_100 k dataset
圖3 基于MovieLens_1M數(shù)據(jù)集的各算法結(jié)果對比圖Fig.3 RMSE and MAE comparison of MFXGB algorithm,SVD++algorithm,Item-based CF algorithm and User-based CF algorithm using the MovieLens_1M dataset
2.3.2 MFXGB算法的穩(wěn)健性分析
MFXGB算法的穩(wěn)健性主要從聚類數(shù)、矩陣填充和加入用戶與項目的基礎(chǔ)特征這3個方面進(jìn)行分析,實(shí)驗(yàn)結(jié)果均基于MovieLens_100k數(shù)據(jù)集。
1)聚類數(shù)對計算時間和推薦算法效果的影響。
選取聚類數(shù)K1=K2分別為10、20、30、40、50、60、70、80、90、100、200,K1=n,K2=m(不聚類),將MFXGB算法的預(yù)測誤差和計算時間繪制成折線圖,如圖4所示。可見隨聚類數(shù)量的增加,算法的RMSE和MAE均呈下降趨勢;當(dāng)不進(jìn)行聚類時,算法預(yù)測精度明顯提升,但計算時間成本較高。因此,在實(shí)際應(yīng)用中,應(yīng)兼顧計算時間成本與預(yù)測效果來選擇聚類數(shù)。
圖4 MFXGB模型的預(yù)測誤差和訓(xùn)練時間與聚類數(shù)的折線圖Fig.4 RMSE and MAE and computation time comparison of different clustering numbers in the MFXGB algorithm
2)矩陣填充對算法效果的影響。
MFXGB推薦算法的特點(diǎn)之一就是事先對用戶評分矩陣進(jìn)行填充。將MFXGB算法與未進(jìn)行缺失值填充的XGBoost算法進(jìn)行效果對比,實(shí)驗(yàn)結(jié)果如圖5所示。使用未填充用戶評分矩陣的XGBoost算法時,先將評分矩陣中的缺失值填充為零,再進(jìn)行聚類??梢钥闯?隨聚類數(shù)量k的增加,填充矩陣對模型的效果提升顯著。當(dāng)取聚類數(shù)為60時,MFXGB算法比XGBoost算法的RMSE和MAE均減小了4.5%,結(jié)果表明,矩陣分解對用戶評分矩陣進(jìn)行填充,能夠提高算法的精確度。
3)加入用戶和項目的基礎(chǔ)特征對模型的影響。
MFXGB推薦算法的另一大特點(diǎn)是建立了基于XGBoost算法的有監(jiān)督模型,在聚類后產(chǎn)生的用戶和項目特征基礎(chǔ)上再加入年齡、性別、職業(yè)作為用戶的基礎(chǔ)特征,加入電影類型作為項目的基礎(chǔ)特征。
圖6繪制了MFXGB算法加入基礎(chǔ)特征與不含加入基礎(chǔ)特征的預(yù)測誤差RMSE和MAE并隨聚類數(shù)變化的折線圖。實(shí)驗(yàn)結(jié)果表明,加入用戶和項目基礎(chǔ)特征對算法有一定的提升效果。無論聚類數(shù)為多少,加入用戶和項目的基礎(chǔ)特征的MFXGB算法的預(yù)測誤差始終小于不加入基礎(chǔ)特征的算法。進(jìn)一步說明增加基礎(chǔ)信息會提升推薦精確度。
圖5 MFXGB算法與XGBoost算法的預(yù)測誤差RMSE和MAE對比圖Fig.5 RMSE and MAE comparison between the MFXGB algorithm and the XGBoost algorithm
圖6 加入基礎(chǔ)特征的MFXGB模型與不加入基礎(chǔ)特征的MFXGB模型的預(yù)測誤差的對比圖Fig.6 RMSE and MAE comparison between the MFXGB algorithm with user and item’s attributes and the MFXGB algorithm without user and item’s attributes
2.3.3 推薦結(jié)果展示
運(yùn)用MFXGB算法訓(xùn)練的模型,生成所選取的用戶的推薦列表。表2展示了2個用戶的Top10推薦列表。
表2 基于MFXGB推薦算法產(chǎn)生的用戶1和2的推薦列表Table 2 The recommendation lists generated by the MFXGB algorithm for users 1 and 2
以用戶1為例,在Top10的推薦列表中,有6部電影都有用戶1的5分評分,表明該用戶非常喜愛這6部電影??紤]到只挑選了預(yù)測評分排名前10的電影進(jìn)行推薦,而這些電影的推薦評分大多都在4.5分以上,基于數(shù)據(jù)集Movie Lens_100k,計算所有用戶產(chǎn)生的Top10推薦列表中,用戶評價為5分的電影數(shù)量占MFXGB算法推薦的10部電影的平均比例為28.57%。說明MFXGB算法對用戶評價為5分的電影的推薦精確率(precision)達(dá)到28.57%。考慮到各個用戶評為5分的電影數(shù)量可能各不相同,針對這一情況,計算Top10推薦列表對用戶評為5分電影的召回率,即Top10列表中所推薦的電影中用戶真實(shí)評價為5分的電影所占比例。基于數(shù)據(jù)集MovieLens_100k,計算得到用戶評價為5分的電影召回率為19.18%。除此之外,在Top10推薦列表中,推薦給用戶的未評分電影平均數(shù)為6.63,表明MFXGB算法能推薦大約6部給用戶未看過但可能感興趣的電影,可以為商家?guī)碛?/p>
隨著網(wǎng)絡(luò)資源數(shù)量的快速增加,傳統(tǒng)推薦算法受限于高度稀疏的用戶 項目的評分矩陣,推薦效果不佳。針對評分矩陣高度稀疏性問題,文中提出的融合矩陣分解和XGBoost的推薦算法MFXGB,能夠有效解決用戶 項目評分矩陣的稀疏性問題并提升推薦精確度。MFXGB算法具有三大特點(diǎn):一是事先對用戶 項目評分矩陣進(jìn)行填充,避免過多的缺失值對模型預(yù)測結(jié)果產(chǎn)生影響;二是對用戶和項目進(jìn)行K-均值聚類,對用戶和項目進(jìn)行特征提取,克服計算成本過高的困難;三是利用XGBoost算法訓(xùn)練一個有監(jiān)督模型用于預(yù)測用戶評分,該模型還允許加入用戶和電影的自身屬性作為自變量,使信息量更加豐富,有利于提升模型預(yù)測效果。實(shí)證結(jié)果表明,MFXGB的推薦效果明顯優(yōu)于傳統(tǒng)的推薦算法。MFXGB算法可以廣泛應(yīng)用于各個領(lǐng)域,如旅游景點(diǎn)、商品、音樂、新聞、圖書等推薦問題中,幫助消費(fèi)者找到自己感興趣的東西,同時也能夠?yàn)樯碳覄?chuàng)造不菲的收益。