韋 煒，全渝娟，卓奕濤，陳學(xué)亮，林 艷

（暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州510632）

基于多階馬爾可夫預(yù)測(cè)的個(gè)性化推薦算法

韋 煒，全渝娟，卓奕濤，陳學(xué)亮，林 艷

（暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州510632）

針對(duì)現(xiàn)有推薦系統(tǒng)僅考慮用戶興趣偏移的隨機(jī)性，而忽略用戶興趣偏移時(shí)效性的問題，通過研究馬爾可夫模型，并引入滑動(dòng)時(shí)間窗口機(jī)制，提出一種新的多階馬爾可夫預(yù)測(cè)推薦算法。該算法通過學(xué)習(xí)用戶歷史行為數(shù)據(jù)，以及分析用戶瀏覽行為特征，達(dá)到準(zhǔn)確預(yù)測(cè)用戶瀏覽行為的目的。實(shí)驗(yàn)結(jié)果表明，與協(xié)同過濾算法相比，該推薦算法不僅能夠針對(duì)用戶興趣的偏移進(jìn)行有效預(yù)測(cè)推薦，而且運(yùn)行時(shí)間較短。

用戶興趣；馬爾可夫模型；隨機(jī)性；時(shí)效性；滑動(dòng)時(shí)間窗口；推薦系統(tǒng)

1 概述

隨著互聯(lián)網(wǎng)的發(fā)展與普及，海量的信息正在社會(huì)的每一個(gè)角落中蔓延。互聯(lián)網(wǎng)為用戶帶來便捷服務(wù)的同時(shí)，也使得用戶無法從海量的信息中找到對(duì)自己真正有用的信息，降低了信息的利用率，這即是“信息超載”問題。

傳統(tǒng)的搜索引擎往往只能給所有用戶呈現(xiàn)相同的搜索結(jié)果，為了更加精準(zhǔn)地向用戶提供感興趣的信息，推薦系統(tǒng)應(yīng)運(yùn)而生［1］。推薦系統(tǒng)作為一種信息過濾的重要手段，是當(dāng)前解決“信息超載”問題的最有效的方法之一［2-3］。推薦系統(tǒng)通過對(duì)用戶歷史瀏覽記錄等因素的分析，預(yù)測(cè)用戶的興趣偏好，向用戶推薦商品和服務(wù)［4］。與傳統(tǒng)搜索引擎不同，推薦系統(tǒng)通過對(duì)用戶歷史行為數(shù)據(jù)的分析，向用戶提供個(gè)性化推薦。

推薦系統(tǒng)的應(yīng)用領(lǐng)域非常廣泛，涵蓋電子商務(wù)、電影、音樂、視頻、廣告、社交網(wǎng)絡(luò)等諸多領(lǐng)域。其中，新聞推薦系統(tǒng)是當(dāng)前最熱門的推薦系統(tǒng)之一。在日常生活中，人們可以通過互聯(lián)網(wǎng)獲取各種類型的新聞，如財(cái)經(jīng)新聞、娛樂新聞以及體育新聞等。因此，根據(jù)用戶興趣或偏好的不同，用戶感興趣的新聞也會(huì)各自不同。如何通過推薦系統(tǒng)幫助用戶發(fā)現(xiàn)和提取其真正感興趣的新聞成為目前推薦系統(tǒng)研究的一個(gè)熱點(diǎn)。現(xiàn)實(shí)生活中，用戶的偏好時(shí)常隨著個(gè)人興趣的轉(zhuǎn)變而改變。研究結(jié)果表明，用戶的偏好會(huì)在新事物的刺激下不斷地發(fā)生變化［5］。此外，隨著時(shí)間的推移，個(gè)人偏好也會(huì)產(chǎn)生變化。因此，將新聞和用戶興趣動(dòng)態(tài)變化的特性引入研究中，將有助于發(fā)現(xiàn)用戶興趣偏移的規(guī)律，提高新聞推薦的準(zhǔn)確性。

如果將新聞動(dòng)態(tài)特征的研究與用戶瀏覽新聞的隨機(jī)行為進(jìn)行關(guān)聯(lián)，建立有效的用戶瀏覽預(yù)測(cè)模型，通過提取用戶瀏覽過程中反映出的個(gè)性化特征及用戶興趣的動(dòng)態(tài)變化，發(fā)現(xiàn)用戶興趣偏移的規(guī)律，將有利于推薦系統(tǒng)更加準(zhǔn)確地對(duì)用戶瀏覽行為進(jìn)行預(yù)測(cè)。

馬爾可夫模型是一種動(dòng)態(tài)隨機(jī)模型［6］。而用戶瀏覽新聞是一個(gè)受瀏覽目的、興趣愛好、文化背景等多種因素影響的動(dòng)態(tài)隨機(jī)過程。因此，可以通過引入馬爾可夫模型記錄用戶的新聞瀏覽過程，并依據(jù)其緊鄰的狀態(tài)實(shí)現(xiàn)動(dòng)態(tài)預(yù)測(cè)推薦。文獻(xiàn)［7］首先將馬爾可夫模型應(yīng)用于日志挖掘，通過對(duì)用戶瀏覽過程的抽象，建立簡(jiǎn)單有效的用戶瀏覽行為預(yù)測(cè)模型；文獻(xiàn)［5］利用馬爾可夫模型通過用戶歷史記錄學(xué)習(xí)用戶的偏好模式，發(fā)現(xiàn)用戶偏好會(huì)隨著時(shí)間的推移而產(chǎn)生變化；文獻(xiàn)［8］通過分析用戶歷史瀏覽記錄，利用馬爾可夫模型預(yù)測(cè)用戶對(duì)產(chǎn)品的傾向性。為了解決現(xiàn)實(shí)生活中電子商務(wù)產(chǎn)品推薦問題，文獻(xiàn)［9］利用馬爾可夫鏈跟蹤用戶的購買行為，運(yùn)用時(shí)間分集增強(qiáng)電子商務(wù)推薦的時(shí)間多樣性。文獻(xiàn)［10］基于馬爾可夫動(dòng)態(tài)模型提出了一種融合停留時(shí)間的推薦模型。該模型利用停留時(shí)間來描述用戶對(duì)某一偏好的感興趣程度及所推薦網(wǎng)頁的重要性。然而，以上模型僅僅考慮了用戶瀏覽行為的隨機(jī)性，并未考慮該行為的時(shí)效性。時(shí)效性指用戶在一定時(shí)間內(nèi)查閱的所有信息對(duì)決策均有一定價(jià)值。例如，在新聞推薦系統(tǒng)中，用戶在一定時(shí)間段內(nèi)閱讀的所有新聞，均可表示用戶在該段時(shí)間內(nèi)的興趣偏好。研究結(jié)果表明，在新聞推薦系統(tǒng)中，對(duì)時(shí)效性問題的研究能夠記錄用戶興趣的偏移，提高推薦的準(zhǔn)確性［11-12］。因此，設(shè)計(jì)基于用戶瀏覽行為的動(dòng)態(tài)預(yù)測(cè)推薦模型時(shí)應(yīng)考慮時(shí)效性的影響。

本文考慮馬爾可夫模型對(duì)動(dòng)態(tài)預(yù)測(cè)推薦模型研究的積極效用，提出一種多階馬爾可夫預(yù)測(cè)模型（Multi-step Markov Predict Model，MMPM），并基于該模型提出多階馬爾可夫預(yù)測(cè)推薦算法（Personalized Recommendation Algorithm Based on Multi-step Markov Predict，MMPA）。該算法在考慮用戶瀏覽隨機(jī)性和時(shí)效性的情況下，通過建立轉(zhuǎn)移概率矩陣得到候選推薦列表，并進(jìn)行個(gè)性化推薦。

2 數(shù)學(xué)模型及問題描述

2.1 多階馬爾可夫預(yù)測(cè)模型

本文采用有向圖對(duì)MMPM進(jìn)行描述?？紤]在新聞推薦中，用戶閱讀新聞i之后點(diǎn)擊閱讀新聞j，就可能代表著一次興趣的轉(zhuǎn)移，因此將MMPM的一次狀態(tài)轉(zhuǎn)移作為一次事件，代表用戶關(guān)注點(diǎn)和興趣的偏移。

圖1為多階馬爾可夫預(yù)測(cè)模型示意圖。

圖1 多階馬爾可夫預(yù)測(cè)模型示意圖

其中，V為頂點(diǎn)集，表示狀態(tài)，例如在新聞推薦中，頂點(diǎn)集V是由新聞集組成，如果用戶處于狀態(tài)v1，則表示用戶當(dāng)前閱讀的新聞為v1；E為邊集，記錄用戶瀏覽記錄中的所有狀態(tài)轉(zhuǎn)移，e12表示為用戶瀏覽行為從狀態(tài)v1到狀態(tài)v2的轉(zhuǎn)移，即用戶閱讀新聞v1之后點(diǎn)擊新聞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ùn)用多階馬爾可夫預(yù)測(cè)模型進(jìn)行推薦時(shí)，依照用戶瀏覽的信息建立頂點(diǎn)集V；根據(jù)用戶歷史瀏覽記錄建立邊集E，運(yùn)用來表示邊的用戶狀態(tài)的d階轉(zhuǎn)移次數(shù)；PE是由K×K（K表示頂點(diǎn)集V元素個(gè)數(shù)）生成的轉(zhuǎn)移概率矩陣，例如P12為狀態(tài)v1轉(zhuǎn)移到狀態(tài)v2的條件轉(zhuǎn)移概率。每條邊eE上標(biāo)注有狀態(tài)的連接次數(shù)和轉(zhuǎn)移概率PE。

基于此，多階馬爾可夫預(yù)測(cè)模型可以形式化描述為：

其中，V=（v1，v2，…，vK）是頂點(diǎn)集，頂點(diǎn)用于表示狀態(tài)，|V|=K；E=｛eij|i∈V，j∈V｝是邊集，邊用于表示狀態(tài)轉(zhuǎn)移；NdE∈［0，N］是一個(gè)函數(shù)，它給每條邊e=（i，j）∈E賦予數(shù)值，用于表示頂點(diǎn)i到頂點(diǎn)j的一階轉(zhuǎn)移次數(shù)，以此類推，表示為頂點(diǎn)i到頂點(diǎn)j的d階轉(zhuǎn)移次數(shù)；PE∈［0，1］是一個(gè)函數(shù)，它給每條邊e=（i，j）∈E賦予一個(gè)條件存在概率Pe∈（0，1）用于表示頂點(diǎn)i和j之間實(shí)際存在的條件下，由頂點(diǎn)i轉(zhuǎn)移到頂點(diǎn)j的轉(zhuǎn)移概率。

2.2 數(shù)學(xué)模型

2.2.1 馬爾可夫鏈

設(shè)有隨機(jī)過程序列｛Xn，n∈1，2，…｝的狀態(tài)空間V是離散的過程Xn=Xn（tn）所處的狀態(tài)為：x1，x2，…，xn的其中一個(gè)，對(duì)于任意時(shí)刻tn，下面的條件概率公式成立：

則稱序列｛Xn，n∈1，2，…｝滿足k階馬爾可夫模型。

在處理實(shí)際問題時(shí)，通過引入轉(zhuǎn)移概率［13］表示系統(tǒng)狀態(tài)間的轉(zhuǎn)移情況：

上式中轉(zhuǎn)移概率表示：已知在時(shí)刻tn-1系統(tǒng)的狀態(tài)處于xj的條件下，在tn時(shí)刻系統(tǒng)的狀態(tài)處于xi的條件概率。

在離散時(shí)間變量條件下，可以得到如下形式［14］：

假設(shè)所有觀察到的變量是離散的，所以｛xn，n∈1，2，…｝可稱為離散狀態(tài)或有限狀態(tài)的馬爾可夫鏈。2.2.2 基于馬爾可夫模型的最大似然估計(jì)

假設(shè)存在一個(gè)瀏覽序列數(shù)據(jù)集D=（X1，X2，…，XN），其中，Xi=（xi1，xi2，…，xi，Ti），i∈1，2，…代表用戶i的瀏覽序列，在取得樣本為x1：T的條件下，模型參數(shù)用θ表示，要求使用最大似然估計(jì)得到最優(yōu)參數(shù)，使得似然函數(shù)的值最大，以下是單用戶瀏覽數(shù)據(jù)的似然函數(shù)［13］。

其中，π（x1）=p（x1）；I（x）為示性函數(shù)。同時(shí)定義以下等式：

假設(shè)用戶的瀏覽行為是相互獨(dú)立的，則存在數(shù)據(jù)集的對(duì)數(shù)似然函數(shù)如下：

式（1）存在以下優(yōu)化問題：

其中，j∈1，2，…，K。

可得拉格朗日函數(shù)：

其中，λj＞0；μk＞0。

由式（2）可以得到對(duì)數(shù)似然方程組：

2.3 多階馬爾可夫預(yù)測(cè)推薦算法

圖2為用戶瀏覽順序示意圖?？紤]數(shù)據(jù)時(shí)效性、瀏覽隨機(jī)性等因素，用戶到狀態(tài)v4的轉(zhuǎn)移可能受到狀態(tài)v1，v2甚至其他用戶歷史狀態(tài)的影響。本文提出了基于多階馬爾可夫預(yù)測(cè)模型的個(gè)性化推薦算法，該算法正是充分考慮了用戶瀏覽記錄（狀態(tài)）蘊(yùn)含的用戶偏好信息。如就單一用戶個(gè)體考慮，在短時(shí)間內(nèi)，其興趣偏好不會(huì)發(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；如果在短時(shí)間內(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的實(shí)現(xiàn)主要由MMPM建模和推薦預(yù)測(cè)兩大部分組成。其中，MMPM建模包括：（1）根據(jù)數(shù)據(jù)時(shí)效性設(shè)置時(shí)效性參數(shù)Δt；（2）計(jì)算每個(gè)狀態(tài)的一階轉(zhuǎn)移次數(shù)和一階轉(zhuǎn)移概率；（3）計(jì)算每個(gè)狀態(tài)的多階轉(zhuǎn)移次數(shù)和多階轉(zhuǎn)移概率；（4）求取每個(gè)狀態(tài)的轉(zhuǎn)移概率。推薦預(yù)測(cè)則包括：（1）生成當(dāng)前時(shí)刻的轉(zhuǎn)移概率矩陣；（2）預(yù)測(cè)用戶的偏好；（3）實(shí)施個(gè)性化推薦。MMPA實(shí)現(xiàn)示意如圖3所示。

圖3 MM PA實(shí)現(xiàn)示意圖

3 多階馬爾可夫預(yù)測(cè)推薦算法設(shè)計(jì)

3.1 時(shí)效性問題

對(duì)一個(gè)給定用戶作推薦時(shí)，若依賴之前過于陳舊的狀態(tài)去推演用戶當(dāng)前的偏好，在推薦預(yù)測(cè)效果方面可能會(huì)大打折扣。因此，本文針對(duì)推薦中存在的信息（狀態(tài)）時(shí)效性的問題，引入滑動(dòng)時(shí)間窗口為時(shí)效性約束條件。圖4為滑動(dòng)時(shí)間窗口示意圖。

圖4 滑動(dòng)時(shí)間窗口示意圖

本文將滑動(dòng)時(shí)間窗口大小設(shè)置為Δt。如圖4所示，滑動(dòng)時(shí)間窗口的滑動(dòng)過程可以描述如下：

（1）時(shí)刻ti，此時(shí)，滑動(dòng)時(shí)間窗口內(nèi)的狀態(tài)i，j，k均可能蘊(yùn)含時(shí)刻ti用戶的偏好信息。時(shí)刻ti的滑動(dòng)時(shí)間窗口包含以下3種情況：1）狀態(tài)i到狀態(tài)j為狀態(tài)i的一階狀態(tài)轉(zhuǎn)移，因?yàn)閠，所以此次狀態(tài)i到狀態(tài)j的一階狀態(tài)轉(zhuǎn)移計(jì)入狀態(tài)i到狀態(tài)j的一階轉(zhuǎn)移次數(shù)2）狀態(tài)i到狀態(tài)k為狀態(tài)i的二階狀態(tài)轉(zhuǎn)移，因?yàn)?，所以狀態(tài)i到狀態(tài)k的二階轉(zhuǎn)移計(jì)入狀態(tài)i到狀態(tài)k的二階轉(zhuǎn)移次數(shù)特別地，在時(shí)刻ti存在，即狀態(tài)l不在時(shí)刻t i的滑動(dòng)時(shí)間窗口內(nèi)，因此狀態(tài)i到狀態(tài)l的三階狀態(tài)轉(zhuǎn)移將不計(jì)入狀態(tài)i到狀態(tài)l的三階轉(zhuǎn)移次數(shù)。

（2）當(dāng)滑動(dòng)時(shí)間窗口隨時(shí)間滑動(dòng)到時(shí)刻tj時(shí)，此時(shí)且，在滑動(dòng)時(shí)間窗口滑動(dòng)的過程中，狀態(tài)i被移出滑動(dòng)時(shí)間窗口，同時(shí)新的狀態(tài)l進(jìn)入滑動(dòng)時(shí)間窗口，狀態(tài)m不進(jìn)入滑動(dòng)時(shí)間窗口，因此，時(shí)刻tj滑動(dòng)時(shí)間窗口內(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)移概率

用戶在時(shí)刻ti的狀態(tài)為i，在時(shí)刻ti的滑動(dòng)時(shí)間窗口Δt內(nèi)，用戶狀態(tài)從狀態(tài)i一階轉(zhuǎn)移到狀態(tài)j。由基于馬爾可夫模型最大似然估計(jì)和式（3），可以計(jì)算時(shí)，用戶瀏覽記錄中由狀態(tài)i一階轉(zhuǎn)移到狀態(tài)j的一階轉(zhuǎn)移概率：

3.2.2 MMPM多階轉(zhuǎn)移概率

如果用戶在任意時(shí)刻滑動(dòng)時(shí)間窗口Δt內(nèi)進(jìn)行了多次狀態(tài)轉(zhuǎn)移，則用戶在該時(shí)刻的滑動(dòng)時(shí)間窗口內(nèi)所有狀態(tài)轉(zhuǎn)移均可以代表著用戶在該時(shí)刻的興趣偏好，因此考慮用戶興趣狀態(tài)一階轉(zhuǎn)移的同時(shí)，也需要考慮狀態(tài)的多階轉(zhuǎn)移情況，狀態(tài)的多階轉(zhuǎn)移也代表著用戶在該時(shí)刻的興趣偏好。狀態(tài)多階轉(zhuǎn)移示意圖如圖5所示。

圖5 狀態(tài)多階轉(zhuǎn)移示意圖

3.2.3 轉(zhuǎn)移概率矩陣

假設(shè)狀態(tài)i和狀態(tài)j均為用戶在某時(shí)刻滑動(dòng)時(shí)間窗口Δt內(nèi)的興趣偏好，由于用戶瀏覽順序的不同，當(dāng)時(shí)，狀態(tài)i可能一階轉(zhuǎn)移到狀態(tài)j，也可能多階轉(zhuǎn)移到狀態(tài)j?？紤]時(shí)效性影響，在計(jì)算轉(zhuǎn)移概率時(shí)，應(yīng)同時(shí)考慮在滑動(dòng)時(shí)間窗口內(nèi)，每個(gè)狀態(tài)進(jìn)行轉(zhuǎn)移的一階轉(zhuǎn)移概率和多階轉(zhuǎn)移概率。

最后由轉(zhuǎn)移概率可構(gòu)成轉(zhuǎn)移概率矩陣，表示為：

3.3 推薦預(yù)測(cè)

根據(jù)轉(zhuǎn)移概率矩陣，可以計(jì)算每個(gè)用戶下一時(shí)刻最有可能轉(zhuǎn)移到的狀態(tài)。在推薦預(yù)測(cè)時(shí)，有些狀態(tài)轉(zhuǎn)移可能來自于用戶的失誤操作，因此本文設(shè)置轉(zhuǎn)移概率閾值Δp用于排除數(shù)據(jù)噪聲。推薦預(yù)測(cè)示意圖如圖6所示。

圖6 推薦預(yù)測(cè)示意圖

假設(shè)下一時(shí)刻為t5，根據(jù)轉(zhuǎn)移概率矩陣可以預(yù)測(cè)用戶在時(shí)刻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)即為用戶下一時(shí)刻最有可能轉(zhuǎn)移到的狀態(tài)。以此類推，可以預(yù)測(cè)出所有用戶在下一時(shí)刻可能轉(zhuǎn)移到的狀態(tài)。為了形式化描述候選推薦列表，以符號(hào)List（max）來表示依據(jù)轉(zhuǎn)移概率矩陣生成由每個(gè)狀態(tài)轉(zhuǎn)移到其他所有狀態(tài)中符合條件的狀態(tài)組成的候選推薦列表，其中List4（max）可表示用戶處于狀態(tài)v4轉(zhuǎn)移到其他所有狀態(tài)中符合推薦條件的狀態(tài)組成的候選推薦列表。

3.4 多階馬爾可夫預(yù)測(cè)算法偽代碼

為了解決興趣偏移的隨機(jī)性和時(shí)效性問題，本文提出多階馬爾可夫預(yù)測(cè)推薦算法。其算法核心偽代碼如下：

輸入 H為用戶瀏覽記錄的數(shù)據(jù)集合；U為用戶集合；d為興趣轉(zhuǎn)移階數(shù)；ΔP為轉(zhuǎn)移概率閾值

輸出 R為預(yù)測(cè)下一時(shí)刻用戶的狀態(tài)

Step1 計(jì)算每階轉(zhuǎn)移次數(shù)（設(shè)最高轉(zhuǎn)移d階）

Step2 計(jì)算轉(zhuǎn)移概率，并生成轉(zhuǎn)移概率矩陣

Step3 下一時(shí)刻用戶狀態(tài)的候選列表

首先順序讀取所有用戶瀏覽記錄，并設(shè)置滑動(dòng)時(shí)間窗口Δt。然后依據(jù)滑動(dòng)時(shí)間窗口計(jì)算狀態(tài)Hi與其他狀態(tài)間的一階轉(zhuǎn)移次數(shù)和多階轉(zhuǎn)移次數(shù)。接著根據(jù)轉(zhuǎn)移次數(shù)計(jì)算轉(zhuǎn)移概率PHiHj并生成轉(zhuǎn)移概率矩陣。最后依據(jù)轉(zhuǎn)移概率矩陣生成每個(gè)用戶的候選列表并進(jìn)行排序。如果候選列表ListHi（max）中的轉(zhuǎn)移概率高于轉(zhuǎn)移概率閾值Δp，則將ListHi（max）中符合推薦策略的新聞推薦給用戶Ri。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)及實(shí)驗(yàn)環(huán)境

為了衡量本文提出的多階馬爾可夫預(yù)測(cè)算法的預(yù)測(cè)準(zhǔn)確性，選取DataCastle網(wǎng)站公開的新聞推薦數(shù)據(jù)集［15］進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集包含10 000名用戶、6 102條新聞和116 225個(gè)瀏覽記錄，且每條記錄包括用戶編號(hào)、新聞編號(hào)、瀏覽時(shí)間以及新聞文本內(nèi)容。實(shí)驗(yàn)將數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集兩部分。其中抽取所有用戶瀏覽的最后一條記錄作為測(cè)試集，即測(cè)試集包含10 000個(gè)數(shù)據(jù)項(xiàng)，而其余數(shù)據(jù)作為訓(xùn)練集。實(shí)驗(yàn)環(huán)境為Intel（R）CoreTMi3-2320M CPU@2.4 GHz、8 GB內(nèi)存、W indow s8主機(jī)，編程環(huán)境為JDK 1.8。

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

對(duì)算法性能進(jìn)行評(píng)估的一項(xiàng)重要原則是評(píng)估算法的成功率。因此，本文選取F-Measure指標(biāo)作為最終的評(píng)價(jià)指標(biāo)。

令U為用戶數(shù)據(jù)集合；R（u）為算法依據(jù)用戶在訓(xùn)練集的行為預(yù)測(cè)的推薦集合；T（u）為測(cè)試集包含的數(shù)據(jù)。

定義1 準(zhǔn)確率（precision）［16］，即推薦列表中，用戶最終選中的新聞?wù)纪扑]列表新聞數(shù)的比例。

定義2 召回率（recall）［16］，即推薦列表中，用戶最終選中的新聞?wù)妓杏脩暨x中新聞的比例。

定義3 F-Measure［16］，準(zhǔn)確率和召回率的調(diào)和平均數(shù)。準(zhǔn)確率和召回率是相互制約和矛盾的，F(xiàn)-Measure能夠?qū)烧哌M(jìn)行綜合考慮，帶來更為準(zhǔn)確的推薦系統(tǒng)性能評(píng)價(jià)。

4.3 協(xié)同過濾算法

通過計(jì)算與當(dāng)前用戶閱讀新聞相似度排名前n的用戶，預(yù)測(cè)用戶最有可能閱讀的下一條新聞。其中，用戶集合用Top@n表示。實(shí)驗(yàn)結(jié)果如表1所示。當(dāng)計(jì)算與用戶相似度排名前60的用戶，即用戶集為Top@60時(shí)實(shí)驗(yàn)結(jié)果最優(yōu)。

表1 協(xié)同過濾算法實(shí)驗(yàn)結(jié)果

4.4 MM PA實(shí)驗(yàn)結(jié)果

本文通過實(shí)驗(yàn)驗(yàn)證權(quán)重系數(shù)δn的有效性，并分析引入轉(zhuǎn)移概率閾值、滑動(dòng)時(shí)間窗口等參數(shù)后算法的推薦預(yù)測(cè)效果。通過訓(xùn)練集建立模型，運(yùn)用MMPA預(yù)測(cè)用戶瀏覽的最后一條新聞，將預(yù)測(cè)結(jié)果與測(cè)試集進(jìn)行比較，確定在測(cè)試集中命中的記錄數(shù)。

4.4.1 權(quán)重系數(shù)實(shí)驗(yàn)

本文實(shí)驗(yàn)的目的是為了證明計(jì)算轉(zhuǎn)移概率時(shí)，考慮多階轉(zhuǎn)移概率能夠提高推薦預(yù)測(cè)效果。實(shí)驗(yàn)僅考慮用戶興趣偏移的隨機(jī)性，忽略用戶興趣偏移的時(shí)效性，因此將滑動(dòng)時(shí)間窗口Δt設(shè)置為無窮大。

表2為權(quán)重系數(shù)實(shí)驗(yàn)結(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)移概率的情況。實(shí)驗(yàn)在計(jì)算轉(zhuǎn)移概率時(shí)轉(zhuǎn)移階數(shù)最高取值為6階。表2展示了F-Measure排名前20的參數(shù)取值情況。其中，6階轉(zhuǎn)移概率的權(quán)重系數(shù)δ6在多數(shù)情況下為0。因此，針對(duì)實(shí)驗(yàn)所采用的數(shù)據(jù)集，在計(jì)算轉(zhuǎn)移概率時(shí)，將計(jì)算5階轉(zhuǎn)移階數(shù)。

表2 權(quán)重系數(shù)實(shí)驗(yàn)結(jié)果

表3 不同階數(shù)預(yù)測(cè)效果對(duì)比

4.4.2 轉(zhuǎn)移概率閾值實(shí)驗(yàn)

本文實(shí)驗(yàn)?zāi)康氖菫榱俗C明在推薦預(yù)測(cè)時(shí)，考慮轉(zhuǎn)移概率閾值Δp能提高推薦預(yù)測(cè)效果。

表4為轉(zhuǎn)移概率閾值實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)轉(zhuǎn)移概率閾值Δp取值為0.0，0.05，0.1，0.15，0.20，0.25，0.30，0.35，0.40。實(shí)驗(yàn)計(jì)算轉(zhuǎn)移概率時(shí)轉(zhuǎn)移階數(shù)最高取值為5階，表4展示了F-Measure排名前20參數(shù)取值情況。其中，轉(zhuǎn)移概率閾值Δp=0.15時(shí)，能夠得到較優(yōu)的F-Measure。在表4中，Top2（δ1= 0.7，δ2=0.1，δ3=0.1，δ4=0.1）為考慮四階轉(zhuǎn)移概率的情況。

表4 轉(zhuǎn)移概率閾值實(shí)驗(yàn)結(jié)果

通過對(duì)比轉(zhuǎn)移概率閾值實(shí)驗(yàn)（表4）與權(quán)重系數(shù)實(shí)驗(yàn)結(jié)果（表2），發(fā)現(xiàn)考慮轉(zhuǎn)移概率閾值后，實(shí)驗(yàn)得到的F-Measure有明顯提升。實(shí)驗(yàn)結(jié)果表明，進(jìn)行推薦預(yù)測(cè)時(shí)運(yùn)用轉(zhuǎn)移概率閾值Δp過濾數(shù)據(jù)噪聲能得到更好地推薦預(yù)測(cè)效果。

圖7為一階與四階在不同轉(zhuǎn)移概率閾值下實(shí)驗(yàn)結(jié)果的對(duì)比。其中一階情況下權(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ù)測(cè)效果優(yōu)于一階的預(yù)測(cè)效果，同時(shí)可以發(fā)現(xiàn)隨著轉(zhuǎn)移概率閾值的增長(zhǎng)，F(xiàn)-Measure指標(biāo)會(huì)有所下降。這種情況產(chǎn)生的原因是隨著轉(zhuǎn)移概率閾值的增長(zhǎng)，轉(zhuǎn)移概率矩陣中滿足轉(zhuǎn)移概率閾值的新聞會(huì)減少，雖然準(zhǔn)確率會(huì)有明顯提升，但可提交的推薦新聞數(shù)大幅減少致使召回率明顯下降，最終導(dǎo)致F-Measure指標(biāo)下降。

圖7 一階與四階轉(zhuǎn)移概率閾值對(duì)比實(shí)驗(yàn)結(jié)果

4.4.3 滑動(dòng)時(shí)間窗口實(shí)驗(yàn)

本文實(shí)驗(yàn)?zāi)康氖窃u(píng)估時(shí)效性對(duì)推薦預(yù)測(cè)的影響。首先，驗(yàn)證引入時(shí)效性約束條件后，算法的推薦預(yù)測(cè)效果。實(shí)驗(yàn)將滑動(dòng)時(shí)間窗口設(shè)為固定值，滑動(dòng)時(shí)間窗口Δt取值范圍為100 s～2 000 s，實(shí)驗(yàn)結(jié)果如表5所示。實(shí)驗(yàn)結(jié)果展示了F-Measure排名前20的參數(shù)取值情況。如表5所示，Top3（δ1=0.9，δ2= 0.1）為考慮二階滑動(dòng)時(shí)間窗口的情況。通過滑動(dòng)時(shí)間窗口實(shí)驗(yàn)（表5）與轉(zhuǎn)移概率閾值實(shí)驗(yàn)（表4）的對(duì)比，發(fā)現(xiàn)引入時(shí)效性約束條件能夠有效提升推薦預(yù)測(cè)效果。實(shí)驗(yàn)結(jié)果表明，引入滑動(dòng)時(shí)間窗口能夠有效地提高推薦預(yù)測(cè)效果。

表5 滑動(dòng)時(shí)間窗口實(shí)驗(yàn)結(jié)果

圖8描述了在滑動(dòng)時(shí)間窗口取值不同的情況下，一階與二階實(shí)驗(yàn)結(jié)果的對(duì)比情況。其中一階情況下權(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ù)測(cè)效果。

圖8 滑動(dòng)時(shí)間窗口對(duì)比實(shí)驗(yàn)結(jié)果

4.4.4 不同方法的推薦結(jié)果比較

表6表示2種方法實(shí)驗(yàn)結(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ù)測(cè)推薦效果，尤其在運(yùn)行時(shí)間方面，優(yōu)勢(shì)更為明顯。

表6 不同算法推薦結(jié)果比較

5 結(jié)束語

本文通過分析用戶瀏覽新聞產(chǎn)生的歷史瀏覽記錄，對(duì)用戶的瀏覽興趣偏好進(jìn)行建模，并結(jié)合傳統(tǒng)的馬爾可夫模型，提出一種新的多階馬爾可夫預(yù)測(cè)推薦模型。基于該模型提出了多階馬爾可夫預(yù)測(cè)推薦算法，并在實(shí)際數(shù)據(jù)集上進(jìn)行了比較實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文提出的算法能對(duì)用戶下一條瀏覽記錄進(jìn)行較為有效的預(yù)測(cè)推薦。通過算法比較表明，MMPA算法具有更好的推薦預(yù)測(cè)效果和更短的運(yùn)行時(shí)間。但算法中存在很多不足，比如用戶瀏覽內(nèi)容、新聞受歡迎程度等因素沒有考慮在算法中，算法仍不能準(zhǔn)確反映出用戶關(guān)注新聞的內(nèi)容和用戶對(duì)新聞的滿意程度?？紤]到新聞的時(shí)效性和時(shí)新性，在選取用戶歷史瀏覽記錄時(shí)，選取歷史記錄時(shí)間跨度較大會(huì)造成預(yù)測(cè)不準(zhǔn)確、加載數(shù)據(jù)過多等問題，例如，選取一定時(shí)間內(nèi)的用戶歷史瀏覽記錄作為當(dāng)前新聞推薦依據(jù)，能夠減少加載數(shù)據(jù)量。所以，在選取用戶歷史瀏覽記錄時(shí)，也需要考慮歷史瀏覽記錄的時(shí)效性問題。因此，在今后的研究工作中將考慮用戶瀏覽內(nèi)容等信息，以及用戶歷史瀏覽記錄時(shí)效性等問題，進(jìn)一步提高推薦預(yù)測(cè)的準(zhǔn)確度和效率。

［1］ 劉建國(guó)，周 濤，汪秉宏.個(gè)性化推薦系統(tǒng)的研究進(jìn)展［J］.自然科學(xué)進(jìn)展，2009，19（1）：1-15.

［2］ 許海玲，吳 瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究［J］.軟件學(xué)報(bào)，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］ 劉勝宗，樊曉平，廖志芳，等.融合停留時(shí)間的隱Markov個(gè)性化推薦模型［J］.通信學(xué)報(bào)，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］.計(jì)算機(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］ 用戶瀏覽新聞的模式分析及個(gè)性化新聞推薦［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ù)測(cè)的個(gè)性化推薦算法［J］.計(jì)算機(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)學(xué)研基金資助項(xiàng)目（2013B090500030）；廣州市科技攻關(guān)計(jì)劃基金資助項(xiàng)目（2014Y 2-00133）。

韋 煒（1987-），男，碩士研究生，主研方向：機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘；全渝娟（通訊作者），副教授、博士；卓奕濤，本科生；陳學(xué)亮、林 艷，碩士研究生。

2015-05-28

2015-06-18 E-m ail：josiah.wei@qq.com