基于改進的隱馬爾可夫模型的新聞推薦算法*

張 丹 周從華

（江蘇大學計算機科學與通信工程學院 鎮江 212013）

1 引言

隨著移動設備的日益普及和互聯網的迅猛發展，人們越來越習慣于通過電腦或智能手機閱讀新聞。各種新聞網站為用戶提供在線新聞服務，但是面對成千上萬篇新聞可供選擇，人們很難快速地從中找到自己下一時刻將要閱讀的新聞。這時新聞推薦系統應運而生。

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

2 相關工作

推薦算法主要分為基于協同過濾的推薦算法和基于內容的推薦算法，而基于協同過濾的推薦算法里又分為基于用戶的協同過濾和基于項目的協同過濾。新聞推薦算法中更常用的是基于用戶的協同過濾和基于內容的推薦。

基于用戶的協同過濾是根據用戶閱讀過的新聞而找出同樣閱讀過這些新聞的用戶，也就是目標用戶的鄰居用戶，從而證明這些用戶與目標用戶在一定程度上是相似的，再將這些用戶閱讀過而目標用戶沒有閱讀過的新聞推薦給目標用戶。

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

但是這些算法都有著一些問題，例如文本處理較復雜，增加了算法的復雜性；還有數據稀疏和冷啟動問題。

新聞推薦網站中較有名的如Google。在Google新聞中，對已經登錄并明確啟用網絡歷史記錄的用戶，推薦系統會根據用戶的過去點擊行為構建用戶新聞興趣，使用貝葉斯算法來預測用戶對當前新聞的興趣［4］。本文著重根據當前閱讀的新聞，去預測下一篇可能閱讀的新聞，也就是說將當前閱讀的新聞和將要閱讀的新聞視為上下文關系。有人曾根據用戶的上下文信息和新聞內容，主動向移動用戶推送即時個性化新聞［5］。

隱馬爾可夫模型是一個關于時序的概率模型，描述由一個隱藏的馬爾可夫鏈隨機生成不可觀測的狀態序列，再由各個狀態隨機生成一個觀測而產生觀測序列的過程。我們常將隱馬爾可夫模型應用到語音識別、輸入法、地圖匹配、金融預測、DNA序列分析等。

文獻［6］中用隱馬爾可夫模型去預測用戶的評分軌跡并結合BP神經網絡進行用戶的偏好學習最終產生推薦結果。但是它沒有考慮到在隱馬爾可夫模型中，模型在某狀態停留一定時間的概率是隨著時間的增長呈指數下降的趨勢的，所以傳統的隱馬爾可夫模型并不能合適的表征用戶評分軌跡的時域結構。

3 基于改進的隱馬爾可夫模型的新聞推薦算法

3.1 隱馬爾可夫模型

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

以上為隱馬爾可夫模型的結構信息，除此以外，想要確定一個隱馬爾可夫模型還需要一個三組參數。

1）狀態轉移概率：模型在各個狀態之間轉換的概率，一般記為矩陣

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

2）輸出觀測概率：模型根據當前狀態獲得各個觀測值的概率，一般記為矩陣

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

3）初始狀態概率：模型在初始時刻各狀態出現的概率，一般記為

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

通過以上可知，一個隱馬爾可夫模型的確定，需要狀態空間Y 、觀測空間X 和三組參數［A，B，π］。一般用參數λ=［Y，X，A，B，π］來表示一個隱馬爾可夫模型。給定一個隱馬爾可夫模型λ，它根據以下過程可以產生一個觀測序列｛x1，x2，…，xn｝：

1）設置t=1，并根據初始狀態概率π 選擇初始狀態y1；

2）根據狀態yt和輸出觀測概率B 選擇觀測變量取值xt；

3）根據狀態yt和狀態轉移矩陣A 轉移模型狀態，也就是確定yt+1；

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

其 中yt∈{s1，s2，…，sN} 和xt∈{o1，o2，…，oM}分別為第t時刻的狀態和觀測值。

3.2 基于改進的隱馬爾可夫模型的新聞推薦算法

一般的新聞推薦算法沒有考慮到用戶瀏覽新聞的時間序列特征。也就是說可以用來預測用戶將點擊的下一篇新聞，用戶對新聞的操作序列正好符合隱馬爾可夫隨機過程。我們將用戶對新聞的操作行為假設為可觀測的，被操作的新聞即觀測值，操作行為我們分為點擊、評論、收藏三種，三者的權重我們暫不考慮。系統對于用戶的閱讀興趣是未知的，那么下一次的對新聞的操作行為只與當前的狀態有關，與之前的狀態無關。

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

3.2.1 參數初始化

λ=［Y，X，A，B，π，d］進行初始化：

1）Y：狀態Y 代表的是用戶對新聞操作的可能的取值集合，N表示集合中元素的數量；

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

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

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

4）B：輸出的觀測值概率分布矩陣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）π：初始狀態的概率矩陣π={πi} ，πi=P（y1=si）（1 ≤i ≤N）代表的是系統中所有的用戶第一次的操作行為為si的概率。

其中，1 ≤i，j ≤N；

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

3.2.2 模型參數學習

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

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

可得出：

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

2）后向變量βt（i）：表示在t 時刻的狀態為si，那么從t+1 時刻到T 時刻的觀察序列為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）假設用戶在t時刻對新聞ot的操作行為為si及在此狀態的駐留時間為d，并且在t+1 時刻對新聞ot+1的操作行為為sj的概率為γt（i，j，d）（1 ≤i，j ≤N，1 ≤t ≤T）。由式（4）～式（6）可得：

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

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

所以：

6）由4）和5）可知，用戶對新聞的操作行為習慣從si轉移到sj的期望為

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

當xt=ot時，Cxt，ot=1，否則Cxt，ot=0。

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

3.2.3 生成推薦列表

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

4 實驗結果及分析

4.1 實驗數據集

在我們的實驗中，數據集采用的是某新聞網站的后臺新聞日志數據，可在github中查看［7］。對基于隱馬爾可夫模型的新聞推薦算法進行模型的訓練分析。隨機選取了1000名用戶的行為記錄，如圖1所示，包括用戶id，新聞id，操作行為時間，新聞標題，操作行為。按照操作行為的時間順序，前80%為訓練集，后20%為測試集。

圖1 數據集示例

4.2 評價指標

我們將基于隱馬爾可夫模型的新聞推薦算法（HMM）與傳統的基于用戶的協同過濾推薦算法（User-based CF）和基于項目的協同過濾推薦算法（Item-based CF）進行對比，設Τ 為測試集，? 為推薦結果。本文的性能指標參考準確（Precision，P），召回率（Recall，R）以及F1指數。

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

召回率越高意味著越多的用戶得到正確的推薦，但這通常是以犧牲精度為代價的，所以為了全面評價三個推薦算法的性能，引入了F1 作為最重要的綜合指標之一，F1越高意味著綜合性能最好。

我們將三個算法按照時間的變化統計用戶的行為數據進行推薦，實驗結果如圖2 ～圖4所示。

圖2 準確率隨時間變化對比

圖3 召回率隨時間變化對比

圖4 F1指數隨時間變化對比

由圖2～圖4 可知，傳統的User-based CF 和Item-based CF 算法的準確度隨著時間的推移下滑明顯，明顯不及HMM 的新聞推薦算法。F1 指數也是隨著時間的推移，HMM 的新聞推薦算法后來居上。由此可見，基于隱馬爾可夫模型的新聞推薦算法是有效的，推薦性能相比傳統的協同過濾得到了提升。

5 結語

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

這對于時間序列的研究與隱馬爾可夫模型相吻合，所以我們將隱馬爾可夫模型融合到新聞推薦算法中，在此基礎上引入狀態駐留時間元素來表示用戶對該新聞的喜歡程度，提出了一種新型的基于時間序列的新聞推薦算法，用戶下一篇將要閱讀的新聞只與當前閱讀的新聞有關。經過廣泛的實驗證明，我們提出的新算法具有較高的有效性與可行性。在之后的工作中，我們將進一步完善以及改進算法。