基于改進(jìn)的隱馬爾可夫模型的新聞推薦算法*

張 丹 周從華

（江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）

1 引言

隨著移動(dòng)設(shè)備的日益普及和互聯(lián)網(wǎng)的迅猛發(fā)展，人們?cè)絹?lái)越習(xí)慣于通過(guò)電腦或智能手機(jī)閱讀新聞。各種新聞網(wǎng)站為用戶提供在線新聞服務(wù)，但是面對(duì)成千上萬(wàn)篇新聞可供選擇，人們很難快速地從中找到自己下一時(shí)刻將要閱讀的新聞。這時(shí)新聞推薦系統(tǒng)應(yīng)運(yùn)而生。

傳統(tǒng)的新聞推薦算法通常是分別對(duì)用戶和新聞建立模型，再進(jìn)行相似度計(jì)算，然后進(jìn)行匹配排序，將用戶有可能感興趣的新聞按興趣值從大到小推薦給他。可是傳統(tǒng)的新聞推薦算法有著數(shù)據(jù)稀疏以及冷啟動(dòng)問(wèn)題。過(guò)去有些學(xué)者將時(shí)間特征融合到新聞推薦算法中［1～2］。以此來(lái)證明用戶的興趣是隨著時(shí)間的推移而改變的。但是，很少有人考慮到時(shí)間序列特征，而用戶閱讀新聞時(shí)一般是以時(shí)間序列的形式［3］，文獻(xiàn)中提出了一種基于改進(jìn)的協(xié)同過(guò)濾時(shí)間序列推薦算法，在協(xié)同過(guò)濾算法中考慮時(shí)間序列，但是它不可避免地也有著協(xié)同過(guò)濾中的數(shù)據(jù)稀疏性和冷啟動(dòng)問(wèn)題。隱馬爾可夫模型主要用于處理時(shí)間序列特征，即樣本之間有時(shí)間序列關(guān)系的數(shù)據(jù)，所以本文利用隱馬爾可夫模型來(lái)著重預(yù)測(cè)用戶在特定新聞之后將要閱讀的下一篇新聞，用戶下一篇將要閱讀的新聞只與當(dāng)前閱讀的新聞?dòng)嘘P(guān)，與之前的行為都無(wú)關(guān)。這樣就有效緩解了數(shù)據(jù)稀疏和冷啟動(dòng)問(wèn)題。在此基礎(chǔ)上，本文引入了狀態(tài)駐留時(shí)間元素，來(lái)表明在此狀態(tài)中停留的時(shí)長(zhǎng)，提高了推薦的準(zhǔn)確度。

2 相關(guān)工作

推薦算法主要分為基于協(xié)同過(guò)濾的推薦算法和基于內(nèi)容的推薦算法，而基于協(xié)同過(guò)濾的推薦算法里又分為基于用戶的協(xié)同過(guò)濾和基于項(xiàng)目的協(xié)同過(guò)濾。新聞推薦算法中更常用的是基于用戶的協(xié)同過(guò)濾和基于內(nèi)容的推薦。

基于用戶的協(xié)同過(guò)濾是根據(jù)用戶閱讀過(guò)的新聞而找出同樣閱讀過(guò)這些新聞的用戶，也就是目標(biāo)用戶的鄰居用戶，從而證明這些用戶與目標(biāo)用戶在一定程度上是相似的，再將這些用戶閱讀過(guò)而目標(biāo)用戶沒(méi)有閱讀過(guò)的新聞推薦給目標(biāo)用戶。

基于內(nèi)容的推薦是將用戶閱讀過(guò)的新聞進(jìn)行特征提取，新聞中一般采用的是TF-IDF模型，然后將與這個(gè)內(nèi)容相似的新聞推薦給用戶。

但是這些算法都有著一些問(wèn)題，例如文本處理較復(fù)雜，增加了算法的復(fù)雜性；還有數(shù)據(jù)稀疏和冷啟動(dòng)問(wèn)題。

新聞推薦網(wǎng)站中較有名的如Google。在Google新聞中，對(duì)已經(jīng)登錄并明確啟用網(wǎng)絡(luò)歷史記錄的用戶，推薦系統(tǒng)會(huì)根據(jù)用戶的過(guò)去點(diǎn)擊行為構(gòu)建用戶新聞興趣，使用貝葉斯算法來(lái)預(yù)測(cè)用戶對(duì)當(dāng)前新聞的興趣［4］。本文著重根據(jù)當(dāng)前閱讀的新聞，去預(yù)測(cè)下一篇可能閱讀的新聞，也就是說(shuō)將當(dāng)前閱讀的新聞和將要閱讀的新聞視為上下文關(guān)系。有人曾根據(jù)用戶的上下文信息和新聞內(nèi)容，主動(dòng)向移動(dòng)用戶推送即時(shí)個(gè)性化新聞［5］。

隱馬爾可夫模型是一個(gè)關(guān)于時(shí)序的概率模型，描述由一個(gè)隱藏的馬爾可夫鏈隨機(jī)生成不可觀測(cè)的狀態(tài)序列，再由各個(gè)狀態(tài)隨機(jī)生成一個(gè)觀測(cè)而產(chǎn)生觀測(cè)序列的過(guò)程。我們常將隱馬爾可夫模型應(yīng)用到語(yǔ)音識(shí)別、輸入法、地圖匹配、金融預(yù)測(cè)、DNA序列分析等。

文獻(xiàn)［6］中用隱馬爾可夫模型去預(yù)測(cè)用戶的評(píng)分軌跡并結(jié)合BP神經(jīng)網(wǎng)絡(luò)進(jìn)行用戶的偏好學(xué)習(xí)最終產(chǎn)生推薦結(jié)果。但是它沒(méi)有考慮到在隱馬爾可夫模型中，模型在某狀態(tài)停留一定時(shí)間的概率是隨著時(shí)間的增長(zhǎng)呈指數(shù)下降的趨勢(shì)的，所以傳統(tǒng)的隱馬爾可夫模型并不能合適的表征用戶評(píng)分軌跡的時(shí)域結(jié)構(gòu)。

3 基于改進(jìn)的隱馬爾可夫模型的新聞推薦算法

3.1 隱馬爾可夫模型

隱馬爾可夫模型（Hidden Mar kov Model，HMM）屬于動(dòng)態(tài)的貝葉斯網(wǎng)——一種有向圖模型。隱馬爾可夫模型中的變量分為狀態(tài)變量和觀測(cè)變量。狀態(tài)變量｛y1，y2，…，yn｝，其中yi∈Y 表示第i時(shí)刻的系統(tǒng)狀態(tài)。狀態(tài)變量我們一般認(rèn)為是隱藏的，不能被觀測(cè)到的，所以我們又稱它為隱變量；觀測(cè)變量｛x1，x2，…，xn｝，其中xi∈X 表示第i時(shí)刻的觀測(cè)值。在隱馬爾可夫模型中，系統(tǒng)一般在多個(gè)狀態(tài)｛s1，s2，…，sN｝中轉(zhuǎn)換，所以狀態(tài)變量yi的取值范圍Y（稱為狀態(tài)空間）通常是有N 個(gè)可能取值的離散空間。并假定觀測(cè)變量xi的取值范圍X 為｛o1，o2，…，oM｝。無(wú)論何時(shí)，觀測(cè)變量的取值依賴且僅依賴于狀態(tài)變量，即xt由yt確定，與其他狀態(tài)變量及觀測(cè)變量的取值無(wú)關(guān)。同時(shí)，t 時(shí)刻的狀態(tài)yt依賴且僅依賴于t-1 時(shí)刻的狀態(tài)yt-1，與其余的n-2 個(gè)狀態(tài)無(wú)關(guān)。這就是所謂的“馬爾可夫鏈”（Markov chain），也就是說(shuō)：系統(tǒng)下一時(shí)刻的狀態(tài)僅由當(dāng)前狀態(tài)決定，不依賴于以往的任何狀態(tài)，基于這種依賴關(guān)系，所有變量的聯(lián)合概率分布為

以上為隱馬爾可夫模型的結(jié)構(gòu)信息，除此以外，想要確定一個(gè)隱馬爾可夫模型還需要一個(gè)三組參數(shù)。

1）狀態(tài)轉(zhuǎn)移概率：模型在各個(gè)狀態(tài)之間轉(zhuǎn)換的概率，一般記為矩陣

其中aij=P（yt+1=sj|yt=si），1 ≤i，j ≤N 。表示在任何時(shí)刻t，若狀態(tài)為si，則在下一時(shí)刻狀態(tài)為sj的概率。

2）輸出觀測(cè)概率：模型根據(jù)當(dāng)前狀態(tài)獲得各個(gè)觀測(cè)值的概率，一般記為矩陣

其中：bij=P(xt=oj|yt=si)，1 ≤i ≤N ，1 ≤j ≤M ，表示在任何時(shí)刻t，若狀態(tài)為si，則觀測(cè)值oj被獲取的概率。

3）初始狀態(tài)概率：模型在初始時(shí)刻各狀態(tài)出現(xiàn)的概率，一般記為

其中πi=P（y1=si），1 ≤i ≤N 。表示模型的初始狀態(tài)為si的概率。

通過(guò)以上可知，一個(gè)隱馬爾可夫模型的確定，需要狀態(tài)空間Y 、觀測(cè)空間X 和三組參數(shù)［A，B，π］。一般用參數(shù)λ=［Y，X，A，B，π］來(lái)表示一個(gè)隱馬爾可夫模型。給定一個(gè)隱馬爾可夫模型λ，它根據(jù)以下過(guò)程可以產(chǎn)生一個(gè)觀測(cè)序列｛x1，x2，…，xn｝：

1）設(shè)置t=1，并根據(jù)初始狀態(tài)概率π 選擇初始狀態(tài)y1；

2）根據(jù)狀態(tài)yt和輸出觀測(cè)概率B 選擇觀測(cè)變量取值xt；

3）根據(jù)狀態(tài)yt和狀態(tài)轉(zhuǎn)移矩陣A 轉(zhuǎn)移模型狀態(tài)，也就是確定yt+1；

4）若t ＜n，設(shè)置t=t+1，并返回第2）步，否則停止。

其 中yt∈{s1，s2，…，sN} 和xt∈{o1，o2，…，oM}分別為第t時(shí)刻的狀態(tài)和觀測(cè)值。

3.2 基于改進(jìn)的隱馬爾可夫模型的新聞推薦算法

一般的新聞推薦算法沒(méi)有考慮到用戶瀏覽新聞的時(shí)間序列特征。也就是說(shuō)可以用來(lái)預(yù)測(cè)用戶將點(diǎn)擊的下一篇新聞，用戶對(duì)新聞的操作序列正好符合隱馬爾可夫隨機(jī)過(guò)程。我們將用戶對(duì)新聞的操作行為假設(shè)為可觀測(cè)的，被操作的新聞即觀測(cè)值，操作行為我們分為點(diǎn)擊、評(píng)論、收藏三種，三者的權(quán)重我們暫不考慮。系統(tǒng)對(duì)于用戶的閱讀興趣是未知的，那么下一次的對(duì)新聞的操作行為只與當(dāng)前的狀態(tài)有關(guān)，與之前的狀態(tài)無(wú)關(guān)。

根據(jù)上一節(jié)的概述將隱馬爾可夫模型融合到新聞推薦算法中。再此基礎(chǔ)上，我們引入了狀態(tài)駐留這個(gè)概念，在原來(lái)5 個(gè)元素的基礎(chǔ)上加入了駐留時(shí)間的元素，在t 時(shí)刻對(duì)新聞操作行為的狀態(tài)y 的概率依賴3 個(gè)因素：在t-1 時(shí)刻的對(duì)新聞操作行為的狀態(tài)yt-1；用戶在前一個(gè)新聞的駐留時(shí)間dt-1；t時(shí)刻觀測(cè)到的新聞序列ot。隨著新聞ID 的改變，駐留時(shí)間d 重新置0，因此，d 可以表示一個(gè)用戶對(duì)某個(gè)新聞進(jìn)行操作行為的持續(xù)時(shí)間。

3.2.1 參數(shù)初始化

λ=［Y，X，A，B，π，d］進(jìn)行初始化：

1）Y：狀態(tài)Y 代表的是用戶對(duì)新聞操作的可能的取值集合，N表示集合中元素的數(shù)量；

2）X：觀測(cè)值X 代表的是用戶可能感興趣的新聞ID 的集合，表示的是系統(tǒng)可以觀察到的用戶操作的新聞，M表示集合中元素的數(shù)量；

3）A：狀態(tài)轉(zhuǎn)移概率矩陣A=[aij]N×N，aij=P（yt+1=sj|yt=si）（1 ≤i，j ≤N）代表的是系統(tǒng)中所有用戶在t 時(shí)刻對(duì)新聞的操作行為為si，在t+1 時(shí)刻轉(zhuǎn)移到操作行為為sj的概率，這里的t 僅代表操作行為的先后時(shí)間順序。

其中，1 ≤i，j，k ≤N；

4）B：輸出的觀測(cè)值概率分布矩陣B=[bij]N×M，bij=P(xt=oj|yt=si)（1 ≤i ≤N ，1 ≤j ≤M）代表的是用戶的操作行為為si)且它正好是新聞ID 為oj的概率。

其中，1 ≤i ≤N ，1 ≤j ≤M ；

5）π：初始狀態(tài)的概率矩陣π={πi} ，πi=P（y1=si）（1 ≤i ≤N）代表的是系統(tǒng)中所有的用戶第一次的操作行為為si的概率。

其中，1 ≤i，j ≤N；

6）d：駐留時(shí)間Pi(d) =P（τt=d|yt=si）（1 ≤i≤N）代表的是在t 時(shí)刻操作行為狀態(tài)為si上駐留時(shí)間為d的概率。

3.2.2 模型參數(shù)學(xué)習(xí)

根據(jù)T 時(shí)刻目標(biāo)用戶給出的進(jìn)行過(guò)操作的新聞ID 序列（觀測(cè)值序列）X={x1，x2，…，xT}和狀態(tài)序列Y={y1，y2，…，yT} ，采 用 基 于EM 算 法 的Baum-Welch算法進(jìn)行模型訓(xùn)練，使之不斷迭代，并在此過(guò)程中更新初始模型，每次迭代都使似然函數(shù)P（x| λ）朝著局部最大方向變化，以保證得到該似然函數(shù)最大的模型。直接計(jì)算P（x| λ）的話，運(yùn)算量很大，而前向-后向算法可以使之變得簡(jiǎn)捷高效。

1）前向變量αt（i）：表示在t 時(shí)刻處于狀態(tài)i 的概率，并且假設(shè)t+1時(shí)刻的狀態(tài)為j。

可得出：

其中，1 ≤j ≤N，1 ≤t ≤T-1；

2）后向變量βt（i）：表示在t 時(shí)刻的狀態(tài)為si，那么從t+1 時(shí)刻到T 時(shí)刻的觀察序列為X=｛xt+1，xt+2，…，xT｝的概率，

可得出：

其中，βT（i，d）=1，1 ≤i ≤N，1 ≤t ≤T-1; 1 ≤d ≤D。

3）求解P（x| λ）

其中，1 ≤i ≤N，1 ≤t ≤T 。

4）假設(shè)用戶在t時(shí)刻對(duì)新聞ot的操作行為為si及在此狀態(tài)的駐留時(shí)間為d，并且在t+1 時(shí)刻對(duì)新聞ot+1的操作行為為sj的概率為γt（i，j，d）（1 ≤i，j ≤N，1 ≤t ≤T）。由式（4）～式（6）可得：

5）假設(shè)用戶在t時(shí)刻對(duì)新聞ot的操作行為為si及駐留在此狀態(tài)的時(shí)間為d的概率為δt（i，d）（1 ≤i≤N，1 ≤t ≤T）。

由式（4）～（6）可得：

所以：

6）由4）和5）可知，用戶對(duì)新聞的操作行為習(xí)慣從si轉(zhuǎn)移到sj的期望為

7）更新隱馬爾可夫模型參數(shù)λ’=（Π′，A′，B′）

當(dāng)xt=ot時(shí)，Cxt，ot=1，否則Cxt，ot=0。

8）重復(fù)以上步驟，直到Π′，A′，B′收斂，此時(shí)P（x|λ′）最大。

3.2.3 生成推薦列表

通過(guò)以上可以得到最優(yōu)隱馬爾可夫模型λ′=（Π′，A′，B′），根據(jù)模型λ′和用戶的對(duì)新聞的歷史操作行為路徑，計(jì)算下一時(shí)刻用戶可能操作的新聞xT+1，以及對(duì)應(yīng)的操作行為si使得P（x1x2…xTxT+1|λ′）最大，將xT+1加入給用戶的推薦列表中，在以上步驟上重復(fù)K-1 次，最后生成推薦列表w=

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

在我們的實(shí)驗(yàn)中，數(shù)據(jù)集采用的是某新聞網(wǎng)站的后臺(tái)新聞日志數(shù)據(jù)，可在github中查看［7］。對(duì)基于隱馬爾可夫模型的新聞推薦算法進(jìn)行模型的訓(xùn)練分析。隨機(jī)選取了1000名用戶的行為記錄，如圖1所示，包括用戶id，新聞id，操作行為時(shí)間，新聞標(biāo)題，操作行為。按照操作行為的時(shí)間順序，前80%為訓(xùn)練集，后20%為測(cè)試集。

圖1 數(shù)據(jù)集示例

4.2 評(píng)價(jià)指標(biāo)

我們將基于隱馬爾可夫模型的新聞推薦算法（HMM）與傳統(tǒng)的基于用戶的協(xié)同過(guò)濾推薦算法（User-based CF）和基于項(xiàng)目的協(xié)同過(guò)濾推薦算法（Item-based CF）進(jìn)行對(duì)比，設(shè)Τ 為測(cè)試集，? 為推薦結(jié)果。本文的性能指標(biāo)參考準(zhǔn)確（Precision，P），召回率（Recall，R）以及F1指數(shù)。

Precision 描述了推薦精度，數(shù)值越高意味著更少的用戶得到錯(cuò)誤的推薦。

召回率越高意味著越多的用戶得到正確的推薦，但這通常是以犧牲精度為代價(jià)的，所以為了全面評(píng)價(jià)三個(gè)推薦算法的性能，引入了F1 作為最重要的綜合指標(biāo)之一，F(xiàn)1越高意味著綜合性能最好。

我們將三個(gè)算法按照時(shí)間的變化統(tǒng)計(jì)用戶的行為數(shù)據(jù)進(jìn)行推薦，實(shí)驗(yàn)結(jié)果如圖2 ～圖4所示。

圖2 準(zhǔn)確率隨時(shí)間變化對(duì)比

圖3 召回率隨時(shí)間變化對(duì)比

圖4 F1指數(shù)隨時(shí)間變化對(duì)比

由圖2～圖4 可知，傳統(tǒng)的User-based CF 和Item-based CF 算法的準(zhǔn)確度隨著時(shí)間的推移下滑明顯，明顯不及HMM 的新聞推薦算法。F1 指數(shù)也是隨著時(shí)間的推移，HMM 的新聞推薦算法后來(lái)居上。由此可見(jiàn)，基于隱馬爾可夫模型的新聞推薦算法是有效的，推薦性能相比傳統(tǒng)的協(xié)同過(guò)濾得到了提升。

5 結(jié)語(yǔ)

傳統(tǒng)的新聞推薦算法一般是協(xié)同過(guò)濾或者基于內(nèi)容的推薦，這其中對(duì)于時(shí)間特征的研究都較少，少有的也是對(duì)于用戶興趣建模，隨著時(shí)間的推移，用戶興趣的改變。而用戶閱讀新聞時(shí)是按照時(shí)間序列的形式，所以我們著重在預(yù)測(cè)用戶下一篇將要閱讀的新聞上也就是找出用戶的閱讀軌跡。

這對(duì)于時(shí)間序列的研究與隱馬爾可夫模型相吻合，所以我們將隱馬爾可夫模型融合到新聞推薦算法中，在此基礎(chǔ)上引入狀態(tài)駐留時(shí)間元素來(lái)表示用戶對(duì)該新聞的喜歡程度，提出了一種新型的基于時(shí)間序列的新聞推薦算法，用戶下一篇將要閱讀的新聞只與當(dāng)前閱讀的新聞?dòng)嘘P(guān)。經(jīng)過(guò)廣泛的實(shí)驗(yàn)證明，我們提出的新算法具有較高的有效性與可行性。在之后的工作中，我們將進(jìn)一步完善以及改進(jìn)算法。