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

滕傳志，趙月旭

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

0 引 言

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

1 模型與算法

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

1.1 隨機(jī)森林

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

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

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

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

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

圖1 隨機(jī)森林實(shí)現(xiàn)流程

1.2 馬爾可夫鏈

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

(1)

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

1.3 算法闡述

1.3.1 隨機(jī)森林分類(lèi)

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

1.3.2 時(shí)間-商品模型

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

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

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

(2)

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

(3)

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

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

(4)

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

1.3.4 商品質(zhì)量修正

1.3.5 隨機(jī)森林-馬爾可夫鏈算法步驟

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

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

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

(5)以上一階段用戶(hù)點(diǎn)擊商品為基礎(chǔ)可以再進(jìn)行推薦，下一階段推薦以此類(lèi)推形成動(dòng)態(tài)推薦。

2 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

2.3 模型評(píng)價(jià)指標(biāo)

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

表2 召回率與準(zhǔn)確率計(jì)算方法

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

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

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

2.4.1 時(shí)間閾值影響驗(yàn)證

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

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

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

2.4.2 隨機(jī)森林中樹(shù)的深度影響驗(yàn)證

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

圖3 隨機(jī)森林中各決策樹(shù)的深度選擇

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

2.4.3 算法有效性驗(yàn)證

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

表3 不同策略的準(zhǔn)確率與召回率比較/%

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

3 結(jié)束語(yǔ)

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