基于隨機森林-馬爾可夫用戶冷啟動推薦系統(tǒng)

滕傳志，趙月旭

(杭州電子科技大學(xué) 經(jīng)濟學(xué)院，浙江 杭州 310018)

0 引 言

用戶冷啟動問題是推薦系統(tǒng)中亟待解決的問題之一。目前大量的學(xué)者在這方面做了深入的研究工作，取得了豐碩的研究成果：高玉凱等[1]、王斯峰[2]、毛明松等[3]以及劉江紅等[4]在協(xié)同過濾的基礎(chǔ)上進行改進和擴展，取得了良好的效果，一定程度上緩解了冷啟動問題。朱坤廣等[5]、黎雪微等[6]、Margam等[7]以及Wei等[8]從個性化角度對冷啟動問題進行了較為詳細的研究，取得了不錯的效果。王素琴等[9]針對用戶冷啟動問題提出了改進的Epsilon-greedy算法。Antoio等[10]利用統(tǒng)計學(xué)中概率模型來解決非注冊的用戶冷啟動問題。馮宇等[11]、胡祥[12]以及張亞楠等[13]將社會關(guān)系信息融入推薦系統(tǒng)中，較好緩解了冷啟動。本文將馬爾科夫的動態(tài)時效轉(zhuǎn)移優(yōu)勢與隨機森林對數(shù)據(jù)噪聲和數(shù)據(jù)缺失等問題敏感性低的優(yōu)點結(jié)合起來，從而既可以充分利用用戶的個性化標簽屬性特征來保障推薦的商品的個性化效果，又使得推薦具有動態(tài)效果，以保障在不同時間段都能夠得到較為滿意且符合用戶個性化特征的商品列表，同時在推薦精度以及覆蓋率上較傳統(tǒng)以及其它算法有一定提升。從目前國內(nèi)對冷啟動推薦算法研究來看，隨機森林較少涉及，本文嘗試將隨機森林引入并用來解決用戶冷啟動問題，可以為以后對隨機森林在這方面的研究提供一定參考。

1 模型與算法

為方便計算首先引入下面一些記號：記N(>0) 為總用戶量，M(>0) 為總商品量，U={un+1|u1,u2,…,un} 為系統(tǒng)中的n個用戶，n+1為新進的用戶。記C={c1,c2,…,cm} 為系統(tǒng)中m個商品量。S={s1,s2,…,sf}(f∈N)，記Tag={tag1,tag2,…,tagw} 為用戶特征屬性集合，Ctagi={tag1,tag2,…,tagk} 表示商品i的k個標簽屬性。A=[vij]n×m是用戶-商品評分矩陣，vij表示用戶i對商品j的評分值，若用戶對某一商品沒有評分，則記為空值。

1.1 隨機森林

隨機森林屬于集成算法Bagging類型的一種，它是將多個弱分類器進行組合，以“少數(shù)服從多數(shù)”的原則或者取其平均值形成強分類器。相較于其它分類算法，隨機森林在精度與泛化上均有良好的表現(xiàn)。該算法只需通過對給定樣本的學(xué)習(xí)訓(xùn)練分類規(guī)則，不需要任何先驗假設(shè)條件。隨機森林由于簡單、易實現(xiàn)、計算開銷小等優(yōu)點使得其在現(xiàn)實中得到廣泛的應(yīng)用。

為實現(xiàn)隨機森林，下面給出該算法的操作步驟：

(1)記初始數(shù)據(jù)集分為N個樣本集，利用自助法隨機抽取N個樣本集作為訓(xùn)練集，抽取K次，訓(xùn)練集分別為：T1,T2,…,Tk。

(2)設(shè)原始數(shù)據(jù)集中有D個特征，并組成D維特征空間，在生成每顆決策樹中，隨機選取S個特征 (S

(3)根據(jù)上述的訓(xùn)練，得出分類結(jié)果，運用“少數(shù)服從多數(shù)”的原則進行投票或者將分類結(jié)果進行平均化，求其平均值。具體流程如圖1所示。

圖1 隨機森林實現(xiàn)流程

1.2 馬爾可夫鏈

馬爾可夫鏈模型是一個重要的統(tǒng)計模型，其中時間和狀態(tài)空間都是離散形式的馬爾可夫鏈的轉(zhuǎn)移概率為

(1)

對應(yīng)的狀態(tài)轉(zhuǎn)移概率矩陣為P=[pij]k×k。

1.3 算法闡述

1.3.1 隨機森林分類

記用戶特征屬性以及與之對應(yīng)的偏好標簽集合為：{(Tag1,S1)，(Tag2,S2),…,(Tagl,Sl)}，其中Tagi={tagi1,tagi2,…,tagin} 表示用戶i的特征屬性集合，Si={si1,…,sik} 為第i個用戶偏好的商品標簽集合。運用隨機森林對特征屬性進行有監(jiān)督分類訓(xùn)練，監(jiān)督屬性即為商品標簽屬性值。根據(jù)新用戶特征屬性得出的偏好標簽記為 {s1,s2,…,sn}，初始推薦列表為 {c1,…,cn}。

1.3.2 時間-商品模型

由馬爾可夫鏈轉(zhuǎn)移概率公式，注意到時間范圍選擇尤為重要，因為如果選擇的時間范圍過大，會導(dǎo)致推薦效果欠佳(后面的模擬中會給出相關(guān)說明)，如果選擇時間范圍過小則會導(dǎo)致轉(zhuǎn)移矩陣過大，增加計算量。因此選擇適當?shù)臅r間范圍。設(shè)時間T={t1,t2,…,tx}，記TH=[tq,tq+h](q,q+h∈{1,2,…,x}) 為一步時間區(qū)間，其中h=tq+h-tq為狀態(tài)轉(zhuǎn)移的時間長度，為簡便計算以及考慮時間的連續(xù)性，文中選擇一步轉(zhuǎn)移馬爾可夫鏈模型。

1.3.3 轉(zhuǎn)移概率修正

本文將用戶偏好標簽考慮進去，將用戶偏好的商品賦予較大的概率值使其在下一階段將被優(yōu)先考慮。故馬爾可夫一步轉(zhuǎn)移概率可表示為

(2)

其中，I(si→sj) 表示si一步轉(zhuǎn)移到sj的示性函數(shù)，T(Utagk∩tagcj) 表示用戶偏好的標簽與商品j標簽匹配數(shù)量，為了體現(xiàn)差別且保證未匹配的商品概率不為0，做以下規(guī)定

(3)

由于在大樣本情況下，當發(fā)生狀態(tài)轉(zhuǎn)移時會使得轉(zhuǎn)移矩陣出現(xiàn)較為嚴重的稀疏現(xiàn)象，而這對于提高運行效率是非常不利的。為此本文在確定狀態(tài)空間時引入轉(zhuǎn)移閾值α，以此來緩解轉(zhuǎn)移矩陣的稀疏性問題，借鑒最大信息熵方法來確定閾值α，即

αi=arg min max{(∑pij)log(∑pij)}

(4)

以隨機森林分類模型得到新進用可能偏好的商品標簽類別，并以此為依據(jù)進行第一層商品推薦列表。然后以第一層推薦商品為基礎(chǔ)，建立商品之間的狀態(tài)轉(zhuǎn)移矩陣，當用戶點擊商品時，觸發(fā)轉(zhuǎn)移矩陣，自動形成下一時刻可能偏好的商品。但當用戶沒有點擊原始列表中的商品，則根據(jù)用戶當前點擊的商品立即更新轉(zhuǎn)移矩陣，由此來推測下一時刻用戶可能感興趣的商品。

1.3.4 商品質(zhì)量修正

1.3.5 隨機森林-馬爾可夫鏈算法步驟

(2)求出閾值αi，并訓(xùn)練轉(zhuǎn)移矩陣P。

(3)以標簽選擇符合的U個商品組成第一層列表。

(4)以被選出的商品為基礎(chǔ)，結(jié)合訓(xùn)練好的一步轉(zhuǎn)移概率矩陣，并且將運用質(zhì)量修正因子進行修正后概率最大的商品作為下一階段推薦商品。

(5)以上一階段用戶點擊商品為基礎(chǔ)可以再進行推薦，下一階段推薦以此類推形成動態(tài)推薦。

2 實驗與分析

2.1 數(shù)據(jù)集介紹

本文使用推薦系統(tǒng)中常用的movielens數(shù)據(jù)集，選擇 m1-1m 數(shù)據(jù)集，該數(shù)據(jù)集包含約3900多部電影，6040位用戶共1 000 209條評分記錄，每位用戶至少對一部電影做出評價。表1展示了movielens數(shù)據(jù)集中部分信息具體情況。

表1 movielens數(shù)據(jù)集部分數(shù)據(jù)展示

表1數(shù)據(jù)中Occupation代表職業(yè)，本數(shù)據(jù)集中共分為20類職業(yè)并分別進行了虛擬化處理，Zip-code代表郵編(美國)，Times代表時間該數(shù)據(jù)集的時間是以1970年1月1日為基準，將后期對某部電影評分時間節(jié)點轉(zhuǎn)化為秒的形式。將數(shù)據(jù)集隨機拆分成訓(xùn)練集與測試集比例為7∶3。

2.2 數(shù)據(jù)預(yù)處理

將該數(shù)據(jù)集分成兩部分，一部分是用戶特征屬性集合，例如：職業(yè)、性別、年齡等，另一部分為其它集合，例如：時間、電影、標簽值等。在時間區(qū)間劃分上由于該數(shù)據(jù)集的時間戳是以1970年1月1日為基準將用戶評分的時間轉(zhuǎn)換成以秒為單位的時間值。經(jīng)過計算得出：1 h=3600 s，1 day=86 400 s，1 m=2 592 000 s(以30天為準)，1 year=31 104 000 s。

在運用隨機森林進行分類時，本文做如下設(shè)置：每次隨機重復(fù)抽取訓(xùn)練集：N=50 000樣本，訓(xùn)練次數(shù)為500次。

2.3 模型評價指標

為了可以和其它方法進行比較，本文以第一，二層共20種商品為準進行比較。選用推薦系統(tǒng)中常用的準確率與召回率作為各模型評比標準。表2為準確率與召回率的具體計算方法。

表2 召回率與準確率計算方法

準確率=A(A+B)-1，召回率=A(A+C)-1。

2.4 模型結(jié)果及比較

本節(jié)給出各模型的準確率與召回率及其比較，以及相關(guān)參數(shù)變化給算法準確率與召回率帶來的影響分析。具體如下。

2.4.1 時間閾值影響驗證

根據(jù)上文1.3.2節(jié)可知，時間閾值的選取對模型準確率與召回率有較大影響，需要對其進行模擬說明，圖2展示了所提算法在movielens數(shù)據(jù)集中由于選擇不同時間閾值對準確率與召回率產(chǎn)生的影響結(jié)果。

圖2 不同時間閾值下準確率與召回率的表現(xiàn)

圖2中18 000、36 000、86 400分別代表5小時、10小時、1天的時間范圍。從圖2可以看出，時間因素對模型的準確率與召回率有重要影響，當時間閾值由5小時逐步擴大到1天可以看到準確率呈現(xiàn)出下降的趨勢，對于實現(xiàn)個性化推薦是不夠理想的，但注意到召回率卻呈現(xiàn)出遞增的趨勢，但是召回率范圍過大會導(dǎo)致推薦的商品種類過于繁多，這不僅增加了計算機的運算負擔(dān)，降低了推薦時效性而且使得推薦列表不夠精準化。因此要綜合權(quán)衡這兩方面的考慮選擇最佳閾值。

2.4.2 隨機森林中樹的深度影響驗證

隨機森林中各棵決策樹的深度選擇也將會影響到模型的準確率與召回率的表現(xiàn)，圖3展示了本文所提給出的算法在movielens數(shù)據(jù)集中由于樹的深度不同而使得準確率與召回率的差異的具體表現(xiàn)。

圖3 隨機森林中各決策樹的深度選擇

由圖3可知，決策樹的深度選擇對模型是有一定的影響的，當決策樹的深度為4時，其準確率最高，但是召回率有所降低，因此在決策樹深度的選擇上，要結(jié)合實際考慮。

2.4.3 算法有效性驗證

為驗證本文所提算法的有效性，將隨機森林-馬爾可夫算法(random forest-Markov chain，RF-MC)與冷啟動中經(jīng)典算法：流行策略及用戶協(xié)同過濾(USER-CF)，當前較新算法：協(xié)同概率矩陣分解與迭代決策樹(GBDT-MPMF)與近鄰協(xié)同過濾算法(CF-AFN)，進行對比分析。表3展示了各算法在movielens數(shù)據(jù)集中準確率與召回率的具體表現(xiàn)。

表3 不同策略的準確率與召回率比較/%

從表3可以看出相較于經(jīng)典的算法如流行策略，USER-CF在準確率和召回率上有較大的提升，相比于新的算法如GBDT-MPMF、CFAFN，準確率和召回率有一定的提升。

3 結(jié)束語

在冷啟動推薦系統(tǒng)中，以往的研究很少能做到實時動態(tài)推薦的效果，文中的算法可以較好地完成這一目標。從模擬的結(jié)果來看，該算法具有較高的準確率和召回率，注意到時間區(qū)間劃分上不是越大越好，當范圍擴大后雖然召回率得到提升但是準確率會有所降低，不利于實現(xiàn)個性化推薦，因此在時間選擇上應(yīng)該根據(jù)實際需要做適當選擇。同時在決策樹深度的選擇上同樣也要根據(jù)實際需要進行選擇。當然本文也有不足之處，其一在時效性方面，由于目前沒有較好的在線測試平臺，故而無法有效驗證實際效果，其二本文只考慮了用戶的特征屬性信息以及消費時間因素。所以如何將社會關(guān)系信息加入模型當中而且又有較好時效性是今后的主要研究工作。