韋 煒,全渝娟,卓奕濤,陳學亮,林 艷
(暨南大學信息科學技術(shù)學院,廣州510632)
基于多階馬爾可夫預(yù)測的個性化推薦算法
韋 煒,全渝娟,卓奕濤,陳學亮,林 艷
(暨南大學信息科學技術(shù)學院,廣州510632)
針對現(xiàn)有推薦系統(tǒng)僅考慮用戶興趣偏移的隨機性,而忽略用戶興趣偏移時效性的問題,通過研究馬爾可夫模型,并引入滑動時間窗口機制,提出一種新的多階馬爾可夫預(yù)測推薦算法。該算法通過學習用戶歷史行為數(shù)據(jù),以及分析用戶瀏覽行為特征,達到準確預(yù)測用戶瀏覽行為的目的。實驗結(jié)果表明,與協(xié)同過濾算法相比,該推薦算法不僅能夠針對用戶興趣的偏移進行有效預(yù)測推薦,而且運行時間較短。
用戶興趣;馬爾可夫模型;隨機性;時效性;滑動時間窗口;推薦系統(tǒng)
隨著互聯(lián)網(wǎng)的發(fā)展與普及,海量的信息正在社會的每一個角落中蔓延?;ヂ?lián)網(wǎng)為用戶帶來便捷服務(wù)的同時,也使得用戶無法從海量的信息中找到對自己真正有用的信息,降低了信息的利用率,這即是“信息超載”問題。
傳統(tǒng)的搜索引擎往往只能給所有用戶呈現(xiàn)相同的搜索結(jié)果,為了更加精準地向用戶提供感興趣的信息,推薦系統(tǒng)應(yīng)運而生[1]。推薦系統(tǒng)作為一種信息過濾的重要手段,是當前解決“信息超載”問題的最有效的方法之一[2-3]。推薦系統(tǒng)通過對用戶歷史瀏覽記錄等因素的分析,預(yù)測用戶的興趣偏好,向用戶推薦商品和服務(wù)[4]。與傳統(tǒng)搜索引擎不同,推薦系統(tǒng)通過對用戶歷史行為數(shù)據(jù)的分析,向用戶提供個性化推薦。
推薦系統(tǒng)的應(yīng)用領(lǐng)域非常廣泛,涵蓋電子商務(wù)、電影、音樂、視頻、廣告、社交網(wǎng)絡(luò)等諸多領(lǐng)域。其中,新聞推薦系統(tǒng)是當前最熱門的推薦系統(tǒng)之一。在日常生活中,人們可以通過互聯(lián)網(wǎng)獲取各種類型的新聞,如財經(jīng)新聞、娛樂新聞以及體育新聞等。因此,根據(jù)用戶興趣或偏好的不同,用戶感興趣的新聞也會各自不同。如何通過推薦系統(tǒng)幫助用戶發(fā)現(xiàn)和提取其真正感興趣的新聞成為目前推薦系統(tǒng)研究的一個熱點?,F(xiàn)實生活中,用戶的偏好時常隨著個人興趣的轉(zhuǎn)變而改變。研究結(jié)果表明,用戶的偏好會在新事物的刺激下不斷地發(fā)生變化[5]。此外,隨著時間的推移,個人偏好也會產(chǎn)生變化。因此,將新聞和用戶興趣動態(tài)變化的特性引入研究中,將有助于發(fā)現(xiàn)用戶興趣偏移的規(guī)律,提高新聞推薦的準確性。
如果將新聞動態(tài)特征的研究與用戶瀏覽新聞的隨機行為進行關(guān)聯(lián),建立有效的用戶瀏覽預(yù)測模型,通過提取用戶瀏覽過程中反映出的個性化特征及用戶興趣的動態(tài)變化,發(fā)現(xiàn)用戶興趣偏移的規(guī)律,將有利于推薦系統(tǒng)更加準確地對用戶瀏覽行為進行預(yù)測。
馬爾可夫模型是一種動態(tài)隨機模型[6]。而用戶瀏覽新聞是一個受瀏覽目的、興趣愛好、文化背景等多種因素影響的動態(tài)隨機過程。因此,可以通過引入馬爾可夫模型記錄用戶的新聞瀏覽過程,并依據(jù)其緊鄰的狀態(tài)實現(xiàn)動態(tài)預(yù)測推薦。文獻[7]首先將馬爾可夫模型應(yīng)用于日志挖掘,通過對用戶瀏覽過程的抽象,建立簡單有效的用戶瀏覽行為預(yù)測模型;文獻[5]利用馬爾可夫模型通過用戶歷史記錄學習用戶的偏好模式,發(fā)現(xiàn)用戶偏好會隨著時間的推移而產(chǎn)生變化;文獻[8]通過分析用戶歷史瀏覽記錄,利用馬爾可夫模型預(yù)測用戶對產(chǎn)品的傾向性。為了解決現(xiàn)實生活中電子商務(wù)產(chǎn)品推薦問題,文獻[9]利用馬爾可夫鏈跟蹤用戶的購買行為,運用時間分集增強電子商務(wù)推薦的時間多樣性。文獻[10]基于馬爾可夫動態(tài)模型提出了一種融合停留時間的推薦模型。該模型利用停留時間來描述用戶對某一偏好的感興趣程度及所推薦網(wǎng)頁的重要性。然而,以上模型僅僅考慮了用戶瀏覽行為的隨機性,并未考慮該行為的時效性。時效性指用戶在一定時間內(nèi)查閱的所有信息對決策均有一定價值。例如,在新聞推薦系統(tǒng)中,用戶在一定時間段內(nèi)閱讀的所有新聞,均可表示用戶在該段時間內(nèi)的興趣偏好。研究結(jié)果表明,在新聞推薦系統(tǒng)中,對時效性問題的研究能夠記錄用戶興趣的偏移,提高推薦的準確性[11-12]。因此,設(shè)計基于用戶瀏覽行為的動態(tài)預(yù)測推薦模型時應(yīng)考慮時效性的影響。
本文考慮馬爾可夫模型對動態(tài)預(yù)測推薦模型研究的積極效用,提出一種多階馬爾可夫預(yù)測模型(Multi-step Markov Predict Model,MMPM),并基于該模型提出多階馬爾可夫預(yù)測推薦算法(Personalized Recommendation Algorithm Based on Multi-step Markov Predict,MMPA)。該算法在考慮用戶瀏覽隨機性和時效性的情況下,通過建立轉(zhuǎn)移概率矩陣得到候選推薦列表,并進行個性化推薦。
2.1 多階馬爾可夫預(yù)測模型
本文采用有向圖對MMPM進行描述。考慮在新聞推薦中,用戶閱讀新聞i之后點擊閱讀新聞j,就可能代表著一次興趣的轉(zhuǎn)移,因此將MMPM的一次狀態(tài)轉(zhuǎn)移作為一次事件,代表用戶關(guān)注點和興趣的偏移。
圖1為多階馬爾可夫預(yù)測模型示意圖。
圖1 多階馬爾可夫預(yù)測模型示意圖
其中,V為頂點集,表示狀態(tài),例如在新聞推薦中,頂點集V是由新聞集組成,如果用戶處于狀態(tài)v1,則表示用戶當前閱讀的新聞為v1;E為邊集,記錄用戶瀏覽記錄中的所有狀態(tài)轉(zhuǎn)移,e12表示為用戶瀏覽行為從狀態(tài)v1到狀態(tài)v2的轉(zhuǎn)移,即用戶閱讀新聞v1之后點擊新聞v2;NE為邊的連接次數(shù)的集合,的數(shù)值表示為狀態(tài)v1到狀態(tài)v2的一階轉(zhuǎn)移次數(shù),以此類推,的數(shù)值表示為狀態(tài)v1到狀態(tài)v2的d階轉(zhuǎn)移次數(shù);用戶狀態(tài)的一次轉(zhuǎn)移就可能代表著用戶興趣的一次偏移。因此,在運用多階馬爾可夫預(yù)測模型進行推薦時,依照用戶瀏覽的信息建立頂點集V;根據(jù)用戶歷史瀏覽記錄建立邊集E,運用來表示邊的用戶狀態(tài)的d階轉(zhuǎn)移次數(shù);PE是由K×K(K表示頂點集V元素個數(shù))生成的轉(zhuǎn)移概率矩陣,例如P12為狀態(tài)v1轉(zhuǎn)移到狀態(tài)v2的條件轉(zhuǎn)移概率。每條邊eE上標注有狀態(tài)的連接次數(shù)和轉(zhuǎn)移概率PE。
基于此,多階馬爾可夫預(yù)測模型可以形式化描述為:
其中,V=(v1,v2,…,vK)是頂點集,頂點用于表示狀態(tài),|V|=K;E={eij|i∈V,j∈V}是邊集,邊用于表示狀態(tài)轉(zhuǎn)移;NdE∈[0,N]是一個函數(shù),它給每條邊e=(i,j)∈E賦予數(shù)值,用于表示頂點i到頂點j的一階轉(zhuǎn)移次數(shù),以此類推,表示為頂點i到頂點j的d階轉(zhuǎn)移次數(shù);PE∈[0,1]是一個函數(shù),它給每條邊e=(i,j)∈E賦予一個條件存在概率Pe∈(0,1)用于表示頂點i和j之間實際存在的條件下,由頂點i轉(zhuǎn)移到頂點j的轉(zhuǎn)移概率。
2.2 數(shù)學模型
2.2.1 馬爾可夫鏈
設(shè)有隨機過程序列{Xn,n∈1,2,…}的狀態(tài)空間V是離散的過程Xn=Xn(tn)所處的狀態(tài)為:x1,x2,…,xn的其中一個,對于任意時刻tn,下面的條件概率公式成立:
則稱序列{Xn,n∈1,2,…}滿足k階馬爾可夫模型。
在處理實際問題時,通過引入轉(zhuǎn)移概率[13]表示系統(tǒng)狀態(tài)間的轉(zhuǎn)移情況:
上式中轉(zhuǎn)移概率表示:已知在時刻tn-1系統(tǒng)的狀態(tài)處于xj的條件下,在tn時刻系統(tǒng)的狀態(tài)處于xi的條件概率。
在離散時間變量條件下,可以得到如下形式[14]:
假設(shè)所有觀察到的變量是離散的,所以{xn,n∈1,2,…}可稱為離散狀態(tài)或有限狀態(tài)的馬爾可夫鏈。2.2.2 基于馬爾可夫模型的最大似然估計
假設(shè)存在一個瀏覽序列數(shù)據(jù)集D=(X1,X2,…,XN),其中,Xi=(xi1,xi2,…,xi,Ti),i∈1,2,…代表用戶i的瀏覽序列,在取得樣本為x1:T的條件下,模型參數(shù)用θ表示,要求使用最大似然估計得到最優(yōu)參數(shù),使得似然函數(shù)的值最大,以下是單用戶瀏覽數(shù)據(jù)的似然函數(shù)[13]。
其中,π(x1)=p(x1);I(x)為示性函數(shù)。同時定義以下等式:
假設(shè)用戶的瀏覽行為是相互獨立的,則存在數(shù)據(jù)集的對數(shù)似然函數(shù)如下:
式(1)存在以下優(yōu)化問題:
其中,j∈1,2,…,K。
可得拉格朗日函數(shù):
其中,λj>0;μk>0。
由式(2)可以得到對數(shù)似然方程組:
2.3 多階馬爾可夫預(yù)測推薦算法
圖2為用戶瀏覽順序示意圖??紤]數(shù)據(jù)時效性、瀏覽隨機性等因素,用戶到狀態(tài)v4的轉(zhuǎn)移可能受到狀態(tài)v1,v2甚至其他用戶歷史狀態(tài)的影響。本文提出了基于多階馬爾可夫預(yù)測模型的個性化推薦算法,該算法正是充分考慮了用戶瀏覽記錄(狀態(tài))蘊含的用戶偏好信息。如就單一用戶個體考慮,在短時間內(nèi),其興趣偏好不會發(fā)生太大變化。如圖2所示,用戶1從狀態(tài)v1轉(zhuǎn)移到狀態(tài)v2,即v1→v2,則代表著用戶1興趣的一次一階轉(zhuǎn)移,此次狀態(tài)的轉(zhuǎn)移記入v1→v2的一階轉(zhuǎn)移次數(shù)N112;如果在短時間內(nèi)發(fā)生了用戶從狀態(tài)v1經(jīng)過狀態(tài)v2到狀態(tài)v4的轉(zhuǎn)移,即v1→v2→v4,則考慮v1→v4的轉(zhuǎn)移是用戶興趣偏移的一次二階轉(zhuǎn)移,此次狀態(tài)的轉(zhuǎn)移記入v1→v4的二階轉(zhuǎn)移次數(shù)。
圖2 用戶瀏覽順序示意圖
MMPA的實現(xiàn)主要由MMPM建模和推薦預(yù)測兩大部分組成。其中,MMPM建模包括:(1)根據(jù)數(shù)據(jù)時效性設(shè)置時效性參數(shù)Δt;(2)計算每個狀態(tài)的一階轉(zhuǎn)移次數(shù)和一階轉(zhuǎn)移概率;(3)計算每個狀態(tài)的多階轉(zhuǎn)移次數(shù)和多階轉(zhuǎn)移概率;(4)求取每個狀態(tài)的轉(zhuǎn)移概率。推薦預(yù)測則包括:(1)生成當前時刻的轉(zhuǎn)移概率矩陣;(2)預(yù)測用戶的偏好;(3)實施個性化推薦。MMPA實現(xiàn)示意如圖3所示。
圖3 MM PA實現(xiàn)示意圖
3.1 時效性問題
對一個給定用戶作推薦時,若依賴之前過于陳舊的狀態(tài)去推演用戶當前的偏好,在推薦預(yù)測效果方面可能會大打折扣。因此,本文針對推薦中存在的信息(狀態(tài))時效性的問題,引入滑動時間窗口為時效性約束條件。圖4為滑動時間窗口示意圖。
圖4 滑動時間窗口示意圖
本文將滑動時間窗口大小設(shè)置為Δt。如圖4所示,滑動時間窗口的滑動過程可以描述如下:
(1)時刻ti,此時,滑動時間窗口內(nèi)的狀態(tài)i,j,k均可能蘊含時刻ti用戶的偏好信息。時刻ti的滑動時間窗口包含以下3種情況:1)狀態(tài)i到狀態(tài)j為狀態(tài)i的一階狀態(tài)轉(zhuǎn)移,因為t,所以此次狀態(tài)i到狀態(tài)j的一階狀態(tài)轉(zhuǎn)移計入狀態(tài)i到狀態(tài)j的一階轉(zhuǎn)移次數(shù)2)狀態(tài)i到狀態(tài)k為狀態(tài)i的二階狀態(tài)轉(zhuǎn)移,因為,所以狀態(tài)i到狀態(tài)k的二階轉(zhuǎn)移計入狀態(tài)i到狀態(tài)k的二階轉(zhuǎn)移次數(shù)特別地,在時刻ti存在,即狀態(tài)l不在時刻t i的滑動時間窗口內(nèi),因此狀態(tài)i到狀態(tài)l的三階狀態(tài)轉(zhuǎn)移將不計入狀態(tài)i到狀態(tài)l的三階轉(zhuǎn)移次數(shù)。
(2)當滑動時間窗口隨時間滑動到時刻tj時,此時且,在滑動時間窗口滑動的過程中,狀態(tài)i被移出滑動時間窗口,同時新的狀態(tài)l進入滑動時間窗口,狀態(tài)m不進入滑動時間窗口,因此,時刻tj滑動時間窗口內(nèi)的狀態(tài)包含j,k,l,狀態(tài)j到狀態(tài)k為狀態(tài)j的一階狀態(tài)轉(zhuǎn)移,狀態(tài)j到狀態(tài)l為狀態(tài)j的二階狀態(tài)轉(zhuǎn)移。
3.2 轉(zhuǎn)移概率
3.2.1 MMPM一階轉(zhuǎn)移概率
用戶在時刻ti的狀態(tài)為i,在時刻ti的滑動時間窗口Δt內(nèi),用戶狀態(tài)從狀態(tài)i一階轉(zhuǎn)移到狀態(tài)j。由基于馬爾可夫模型最大似然估計和式(3),可以計算時,用戶瀏覽記錄中由狀態(tài)i一階轉(zhuǎn)移到狀態(tài)j的一階轉(zhuǎn)移概率:
3.2.2 MMPM多階轉(zhuǎn)移概率
如果用戶在任意時刻滑動時間窗口Δt內(nèi)進行了多次狀態(tài)轉(zhuǎn)移,則用戶在該時刻的滑動時間窗口內(nèi)所有狀態(tài)轉(zhuǎn)移均可以代表著用戶在該時刻的興趣偏好,因此考慮用戶興趣狀態(tài)一階轉(zhuǎn)移的同時,也需要考慮狀態(tài)的多階轉(zhuǎn)移情況,狀態(tài)的多階轉(zhuǎn)移也代表著用戶在該時刻的興趣偏好。狀態(tài)多階轉(zhuǎn)移示意圖如圖5所示。
圖5 狀態(tài)多階轉(zhuǎn)移示意圖
3.2.3 轉(zhuǎn)移概率矩陣
假設(shè)狀態(tài)i和狀態(tài)j均為用戶在某時刻滑動時間窗口Δt內(nèi)的興趣偏好,由于用戶瀏覽順序的不同,當時,狀態(tài)i可能一階轉(zhuǎn)移到狀態(tài)j,也可能多階轉(zhuǎn)移到狀態(tài)j。考慮時效性影響,在計算轉(zhuǎn)移概率時,應(yīng)同時考慮在滑動時間窗口內(nèi),每個狀態(tài)進行轉(zhuǎn)移的一階轉(zhuǎn)移概率和多階轉(zhuǎn)移概率。
最后由轉(zhuǎn)移概率可構(gòu)成轉(zhuǎn)移概率矩陣,表示為:
3.3 推薦預(yù)測
根據(jù)轉(zhuǎn)移概率矩陣,可以計算每個用戶下一時刻最有可能轉(zhuǎn)移到的狀態(tài)。在推薦預(yù)測時,有些狀態(tài)轉(zhuǎn)移可能來自于用戶的失誤操作,因此本文設(shè)置轉(zhuǎn)移概率閾值Δp用于排除數(shù)據(jù)噪聲。推薦預(yù)測示意圖如圖6所示。
圖6 推薦預(yù)測示意圖
假設(shè)下一時刻為t5,根據(jù)轉(zhuǎn)移概率矩陣可以預(yù)測用戶在時刻t5從狀態(tài)v4轉(zhuǎn)移到其他狀態(tài)中轉(zhuǎn)移概率最高的狀態(tài),排除用戶已經(jīng)轉(zhuǎn)移的狀態(tài)(v1,v2,v3,v4),因此轉(zhuǎn)移概率矩陣中由狀態(tài)v4轉(zhuǎn)移到其他狀態(tài)中轉(zhuǎn)移概率最高且滿足轉(zhuǎn)移概率閾值的狀態(tài)即為用戶下一時刻最有可能轉(zhuǎn)移到的狀態(tài)。以此類推,可以預(yù)測出所有用戶在下一時刻可能轉(zhuǎn)移到的狀態(tài)。為了形式化描述候選推薦列表,以符號List(max)來表示依據(jù)轉(zhuǎn)移概率矩陣生成由每個狀態(tài)轉(zhuǎn)移到其他所有狀態(tài)中符合條件的狀態(tài)組成的候選推薦列表,其中List4(max)可表示用戶處于狀態(tài)v4轉(zhuǎn)移到其他所有狀態(tài)中符合推薦條件的狀態(tài)組成的候選推薦列表。
3.4 多階馬爾可夫預(yù)測算法偽代碼
為了解決興趣偏移的隨機性和時效性問題,本文提出多階馬爾可夫預(yù)測推薦算法。其算法核心偽代碼如下:
輸入 H為用戶瀏覽記錄的數(shù)據(jù)集合;U為用戶集合;d為興趣轉(zhuǎn)移階數(shù);ΔP為轉(zhuǎn)移概率閾值
輸出 R為預(yù)測下一時刻用戶的狀態(tài)
Step1 計算每階轉(zhuǎn)移次數(shù)(設(shè)最高轉(zhuǎn)移d階)
Step2 計算轉(zhuǎn)移概率,并生成轉(zhuǎn)移概率矩陣
Step3 下一時刻用戶狀態(tài)的候選列表
首先順序讀取所有用戶瀏覽記錄,并設(shè)置滑動時間窗口Δt。然后依據(jù)滑動時間窗口計算狀態(tài)Hi與其他狀態(tài)間的一階轉(zhuǎn)移次數(shù)和多階轉(zhuǎn)移次數(shù)。接著根據(jù)轉(zhuǎn)移次數(shù)計算轉(zhuǎn)移概率PHiHj并生成轉(zhuǎn)移概率矩陣。最后依據(jù)轉(zhuǎn)移概率矩陣生成每個用戶的候選列表并進行排序。如果候選列表ListHi(max)中的轉(zhuǎn)移概率高于轉(zhuǎn)移概率閾值Δp,則將ListHi(max)中符合推薦策略的新聞推薦給用戶Ri。
4.1 實驗數(shù)據(jù)及實驗環(huán)境
為了衡量本文提出的多階馬爾可夫預(yù)測算法的預(yù)測準確性,選取DataCastle網(wǎng)站公開的新聞推薦數(shù)據(jù)集[15]進行實驗。該數(shù)據(jù)集包含10 000名用戶、6 102條新聞和116 225個瀏覽記錄,且每條記錄包括用戶編號、新聞編號、瀏覽時間以及新聞文本內(nèi)容。實驗將數(shù)據(jù)集分為訓練集和測試集兩部分。其中抽取所有用戶瀏覽的最后一條記錄作為測試集,即測試集包含10 000個數(shù)據(jù)項,而其余數(shù)據(jù)作為訓練集。實驗環(huán)境為Intel(R)CoreTMi3-2320M CPU@2.4 GHz、8 GB內(nèi)存、W indow s8主機,編程環(huán)境為JDK 1.8。
4.2 實驗評價標準
對算法性能進行評估的一項重要原則是評估算法的成功率。因此,本文選取F-Measure指標作為最終的評價指標。
令U為用戶數(shù)據(jù)集合;R(u)為算法依據(jù)用戶在訓練集的行為預(yù)測的推薦集合;T(u)為測試集包含的數(shù)據(jù)。
定義1 準確率(precision)[16],即推薦列表中,用戶最終選中的新聞?wù)纪扑]列表新聞數(shù)的比例。
定義2 召回率(recall)[16],即推薦列表中,用戶最終選中的新聞?wù)妓杏脩暨x中新聞的比例。
定義3 F-Measure[16],準確率和召回率的調(diào)和平均數(shù)。準確率和召回率是相互制約和矛盾的,F(xiàn)-Measure能夠?qū)烧哌M行綜合考慮,帶來更為準確的推薦系統(tǒng)性能評價。
4.3 協(xié)同過濾算法
通過計算與當前用戶閱讀新聞相似度排名前n的用戶,預(yù)測用戶最有可能閱讀的下一條新聞。其中,用戶集合用Top@n表示。實驗結(jié)果如表1所示。當計算與用戶相似度排名前60的用戶,即用戶集為Top@60時實驗結(jié)果最優(yōu)。
表1 協(xié)同過濾算法實驗結(jié)果
4.4 MM PA實驗結(jié)果
本文通過實驗驗證權(quán)重系數(shù)δn的有效性,并分析引入轉(zhuǎn)移概率閾值、滑動時間窗口等參數(shù)后算法的推薦預(yù)測效果。通過訓練集建立模型,運用MMPA預(yù)測用戶瀏覽的最后一條新聞,將預(yù)測結(jié)果與測試集進行比較,確定在測試集中命中的記錄數(shù)。
4.4.1 權(quán)重系數(shù)實驗
本文實驗的目的是為了證明計算轉(zhuǎn)移概率時,考慮多階轉(zhuǎn)移概率能夠提高推薦預(yù)測效果。實驗僅考慮用戶興趣偏移的隨機性,忽略用戶興趣偏移的時效性,因此將滑動時間窗口Δt設(shè)置為無窮大。
表2為權(quán)重系數(shù)實驗結(jié)果,權(quán)重系數(shù)δd取值范圍為0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0。特別地,δ1=1.0為僅僅考慮一階馬爾可夫轉(zhuǎn)移概率的情況。實驗在計算轉(zhuǎn)移概率時轉(zhuǎn)移階數(shù)最高取值為6階。表2展示了F-Measure排名前20的參數(shù)取值情況。其中,6階轉(zhuǎn)移概率的權(quán)重系數(shù)δ6在多數(shù)情況下為0。因此,針對實驗所采用的數(shù)據(jù)集,在計算轉(zhuǎn)移概率時,將計算5階轉(zhuǎn)移階數(shù)。
表2 權(quán)重系數(shù)實驗結(jié)果
表3 不同階數(shù)預(yù)測效果對比
4.4.2 轉(zhuǎn)移概率閾值實驗
本文實驗?zāi)康氖菫榱俗C明在推薦預(yù)測時,考慮轉(zhuǎn)移概率閾值Δp能提高推薦預(yù)測效果。
表4為轉(zhuǎn)移概率閾值實驗結(jié)果。實驗轉(zhuǎn)移概率閾值Δp取值為0.0,0.05,0.1,0.15,0.20,0.25,0.30,0.35,0.40。實驗計算轉(zhuǎn)移概率時轉(zhuǎn)移階數(shù)最高取值為5階,表4展示了F-Measure排名前20參數(shù)取值情況。其中,轉(zhuǎn)移概率閾值Δp=0.15時,能夠得到較優(yōu)的F-Measure。在表4中,Top2(δ1= 0.7,δ2=0.1,δ3=0.1,δ4=0.1)為考慮四階轉(zhuǎn)移概率的情況。
表4 轉(zhuǎn)移概率閾值實驗結(jié)果
通過對比轉(zhuǎn)移概率閾值實驗(表4)與權(quán)重系數(shù)實驗結(jié)果(表2),發(fā)現(xiàn)考慮轉(zhuǎn)移概率閾值后,實驗得到的F-Measure有明顯提升。實驗結(jié)果表明,進行推薦預(yù)測時運用轉(zhuǎn)移概率閾值Δp過濾數(shù)據(jù)噪聲能得到更好地推薦預(yù)測效果。
圖7為一階與四階在不同轉(zhuǎn)移概率閾值下實驗結(jié)果的對比。其中一階情況下權(quán)重系數(shù)δ1=1.0,四階情況下權(quán)重系數(shù)δ1=0.7,δ2=0.1,δ3=0.1,δ4= 0.1。從圖7可以發(fā)現(xiàn)四階的預(yù)測效果優(yōu)于一階的預(yù)測效果,同時可以發(fā)現(xiàn)隨著轉(zhuǎn)移概率閾值的增長,F(xiàn)-Measure指標會有所下降。這種情況產(chǎn)生的原因是隨著轉(zhuǎn)移概率閾值的增長,轉(zhuǎn)移概率矩陣中滿足轉(zhuǎn)移概率閾值的新聞會減少,雖然準確率會有明顯提升,但可提交的推薦新聞數(shù)大幅減少致使召回率明顯下降,最終導致F-Measure指標下降。
圖7 一階與四階轉(zhuǎn)移概率閾值對比實驗結(jié)果
4.4.3 滑動時間窗口實驗
本文實驗?zāi)康氖窃u估時效性對推薦預(yù)測的影響。首先,驗證引入時效性約束條件后,算法的推薦預(yù)測效果。實驗將滑動時間窗口設(shè)為固定值,滑動時間窗口Δt取值范圍為100 s~2 000 s,實驗結(jié)果如表5所示。實驗結(jié)果展示了F-Measure排名前20的參數(shù)取值情況。如表5所示,Top3(δ1=0.9,δ2= 0.1)為考慮二階滑動時間窗口的情況。通過滑動時間窗口實驗(表5)與轉(zhuǎn)移概率閾值實驗(表4)的對比,發(fā)現(xiàn)引入時效性約束條件能夠有效提升推薦預(yù)測效果。實驗結(jié)果表明,引入滑動時間窗口能夠有效地提高推薦預(yù)測效果。
表5 滑動時間窗口實驗結(jié)果
圖8描述了在滑動時間窗口取值不同的情況下,一階與二階實驗結(jié)果的對比情況。其中一階情況下權(quán)重系數(shù)δ1=1.0,轉(zhuǎn)移概率閾值Δp=0.3。二階情況下權(quán)重系數(shù)δ1=0.9,δ2=0.1,轉(zhuǎn)移概率閾值Δp=0.3。圖8表明考慮多階轉(zhuǎn)移概率可以得到比考慮一階轉(zhuǎn)移概率更好的預(yù)測效果。
圖8 滑動時間窗口對比實驗結(jié)果
4.4.4 不同方法的推薦結(jié)果比較
表6表示2種方法實驗結(jié)果取值最優(yōu)的推薦結(jié)果比較。協(xié)同過濾算法在Top@60得到最優(yōu)結(jié)果。MMPA在權(quán)重系數(shù)δ1=0.9,δ2=0.1,轉(zhuǎn)移概率閾值Δp=0.3的情況下得到最優(yōu)結(jié)果。表6表明本文提出的MMPA相較于協(xié)同過濾算法具有較好的預(yù)測推薦效果,尤其在運行時間方面,優(yōu)勢更為明顯。
表6 不同算法推薦結(jié)果比較
本文通過分析用戶瀏覽新聞產(chǎn)生的歷史瀏覽記錄,對用戶的瀏覽興趣偏好進行建模,并結(jié)合傳統(tǒng)的馬爾可夫模型,提出一種新的多階馬爾可夫預(yù)測推薦模型?;谠撃P吞岢隽硕嚯A馬爾可夫預(yù)測推薦算法,并在實際數(shù)據(jù)集上進行了比較實驗。實驗結(jié)果表明,本文提出的算法能對用戶下一條瀏覽記錄進行較為有效的預(yù)測推薦。通過算法比較表明,MMPA算法具有更好的推薦預(yù)測效果和更短的運行時間。但算法中存在很多不足,比如用戶瀏覽內(nèi)容、新聞受歡迎程度等因素沒有考慮在算法中,算法仍不能準確反映出用戶關(guān)注新聞的內(nèi)容和用戶對新聞的滿意程度。考慮到新聞的時效性和時新性,在選取用戶歷史瀏覽記錄時,選取歷史記錄時間跨度較大會造成預(yù)測不準確、加載數(shù)據(jù)過多等問題,例如,選取一定時間內(nèi)的用戶歷史瀏覽記錄作為當前新聞推薦依據(jù),能夠減少加載數(shù)據(jù)量。所以,在選取用戶歷史瀏覽記錄時,也需要考慮歷史瀏覽記錄的時效性問題。因此,在今后的研究工作中將考慮用戶瀏覽內(nèi)容等信息,以及用戶歷史瀏覽記錄時效性等問題,進一步提高推薦預(yù)測的準確度和效率。
[1] 劉建國,周 濤,汪秉宏.個性化推薦系統(tǒng)的研究進展[J].自然科學進展,2009,19(1):1-15.
[2] 許海玲,吳 瀟,李曉東,等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學報,2009,20(2):350-362.
[3] Awad M A,Khalil I.Prediction of User's Web-brow sing Behavior:Application of Markov Model[J].IEEE Transactions on System s,M an,and Cybernetics,Part B:Cybernetics,2012,42(4):1131-1142.
[4] Resnick P,Varian H R.Recomm ender System s[J]. Communications of the ACM,1997,40(3):56-58.
[5] Sahoo N,Singh P V,Mukhopadhyay T.A Hidden Markov Model for Collaborative Filtering[J].Management Information Systems,2012,36(4):1329-1356.
[6] Kukhtarev N V,Markov V B,Odulov S G,et al. Holographic Storage in Electrooptic Crystals:I.Steady State[J].Ferroelectrics,1978,22(1):949-960.
[7] Zukerman I,A lbrecht D W,Nicholson A E.Predicting Users' Requests on the WWW[C]//Proceedings of the 7th International Conference on User Modeling.Banff,Canada:[s.n.],1999:216-222.
[8] He M,Ren C,Zhang H.Intent-based Recommendation for B2C E-commerce Platforms[J].IBM Journal of Research and Development,2014,58(5/6):1-5.
[9] Gu W,Dong S,Zeng Z.Increasing Recommended Effectiveness with Markov Chains and Purchase Intervals[J].Neural Computing and Applications,2014,25(5):1153-1162.
[10] 劉勝宗,樊曉平,廖志芳,等.融合停留時間的隱Markov個性化推薦模型[J].通信學報,2014,35(9):112-121.
[11] Li L,Zheng L,Yang F,et al.Modeling and Broadening Temporal User Interest in Personalized New s Recommendation[J].Expert System s with Applications,2014,41(7):3168-3177.
[12] 楊興耀,于 炯.基于信任模型填充的協(xié)同過濾推薦模型[J].計算機工程,2015,41(5):6-13.
[13] Chung K L.Markov Chains with Stationary Transition Probabilities[M].Berlin,Germany:Springer,1960.
[14] Murphy K P.Machine Learning:A Probabilistic Perspective[M].Cambridge,USA:M IT Press,2012.
[15] 用戶瀏覽新聞的模式分析及個性化新聞推薦[EB/OL].[2015-03-01].http://www.115.28.182.124/c/0000000005 0/data.
[16] Büttcher S,Clarke C L,Cormack G V.Information Retrieval:Implementing and Evaluating Search Engines[M]. Cambridge,USA:M IT Press,2010.
編輯 索書志
Personalized Recommendation Algorithm Based on Multi-order Markov Prediction
WEI Wei,QUAN Yujuan,ZHUO Yitao,CHEN Xueliang,LIN Yan
(College of Information Science and Technology,Jinan University,Guangzhou 510632,China)
The current research on the recommendation system just considers the randomness too much but ignores the point of timeliness.This paper proposes a new multi-order Markov predicting recommendation system based on the traditional standard Markov model.The algorithm can make up for the deficiency of timeliness by using the new sliding time window mechanism.The algorithm can achieve the mission of accurate prediction about user's browsing activity according to the study of the history data and the analysis of user's brow sing habits.Experimental results show that compared with the collaborative filtering scheme,the new proposed algorithm can provide the predicting recommendation efficiently and effectively judging by the user's interest shift behavior.
user interest;Markov model;randomness;timeliness;sliding time window;recommendation system
韋 煒,全渝娟,卓奕濤,等.基于多階馬爾可夫預(yù)測的個性化推薦算法[J].計算機工程,2015,41(11):59-66.
英文引用格式:Wei Wei,Quan Yujuan,Zhuo Yitao,et al.Personalized Recommendation Algorithm Based on Multi-order Markov Prediction[J].Computer Engineering,2015,41(11):59-66.
1000-3428(2015)11-0059-08
A
TP391
10.3969/j.issn.1000-3428.2015.11.011
廣東省產(chǎn)學研基金資助項目(2013B090500030);廣州市科技攻關(guān)計劃基金資助項目(2014Y 2-00133)。
韋 煒(1987-),男,碩士研究生,主研方向:機器學習,數(shù)據(jù)挖掘;全渝娟(通訊作者),副教授、博士;卓奕濤,本科生;陳學亮、林 艷,碩士研究生。
2015-05-28
2015-06-18 E-m ail:josiah.wei@qq.com