基于隱馬爾科夫模型的融合推薦算法

楊安駒，楊 云，周嬡嬡，閔玉涓，秦 怡

(揚州大學(xué)信息工程學(xué)院，江蘇 揚州 225127)

0 引言

21 世紀是互聯(lián)網(wǎng)的時代，網(wǎng)絡(luò)已經(jīng)成為人們最主要的信息來源之一。但是隨著信息量爆炸式的增長，其中必然夾雜著大量的干擾信息，嚴重妨礙了人們從信息的海洋中找到自己需要的或者感興趣的信息。因此，推薦系統(tǒng)應(yīng)運而生，它根據(jù)人們的行為習(xí)慣，從海量數(shù)據(jù)中挖掘?qū)τ脩粲杏玫男畔?。推薦系統(tǒng)迅速地得到了蓬勃的發(fā)展，已經(jīng)廣泛應(yīng)用到電子商務(wù)、高校圖書館、新聞網(wǎng)站、網(wǎng)絡(luò)音樂等系統(tǒng)中，推薦算法作為其核心受到了國內(nèi)外學(xué)者的廣泛研究。

基于項目的協(xié)同過濾推薦算法(Item-based CF)［1］是推薦算法中最基本的算法，也是目前應(yīng)用最廣泛的推薦算法之一。該算法通過計算項目間的相似度，找到與目標用戶喜歡的、相似的項目進行推薦。

傳統(tǒng)協(xié)同過濾推薦算法存在的冷啟動、數(shù)據(jù)稀疏、數(shù)據(jù)長尾、數(shù)據(jù)擴展等難題［2-3］。許多國內(nèi)外學(xué)者針對這些難題，通過改進相似度計算算法［4-5］、用戶或項目聚類［6-7］、機器學(xué)習(xí)［8-9］等方法對傳統(tǒng)算法進行優(yōu)化。然而這些算法都忽略了時間效應(yīng)，對用戶興趣和項目生命周期的影響。

以推薦音樂為例，經(jīng)分析發(fā)現(xiàn)，時間效應(yīng)對用戶和項目的影響表現(xiàn)為以下2 方面:

1)人們的興趣是變化的。隨著年齡的增長，人們的愛好會發(fā)生變化，小朋友更喜歡童歌，年輕人更喜歡當下流行歌曲，中年人更喜歡20 世紀八九十年代懷舊歌曲，老年人更喜歡戲曲歌劇;人生經(jīng)歷的不同，對人們的愛好也有一定的影響，有時候更喜歡輕快的歌，有時候更喜歡傷感的歌，有時候更喜歡搖滾風(fēng)格，有時候更喜歡重金屬風(fēng)格等。

2)音樂具有一定的生命周期。時代不同，流行的歌曲也不一樣，20 世紀八九十年代鄧麗君、譚詠麟、劉德華等人的歌最為流行;2000 年起周杰倫歌曲風(fēng)靡歌壇;近幾年鄧紫棋的歌很受歡迎。

本文在Item-based CF 推薦算法的基礎(chǔ)上，融合隱馬爾科夫模型［10］(Hidden Markov Model，HMM)，提出一種基于HMM 的融合推薦算法HMM-ItemCF，它能夠有效地提高傳統(tǒng)推薦算法的推薦準確度。

1 相關(guān)工作

隱馬爾科夫模型是在馬爾科夫模型的基礎(chǔ)上衍生而來的，是一種雙重隨機過程。HMM 建模包含一個有限狀態(tài)的馬爾科夫鏈，它描述從一個狀態(tài)轉(zhuǎn)移到下一個狀態(tài)的概率分布;另一個隨機過程表示可觀察值與隱藏狀態(tài)之間概率上的對應(yīng)關(guān)系。

一般而言，一個標準的HMM 用一個五元組來表示λ=(S，V，Π，A，B)，其中:

1)S 表示模型中狀態(tài)的集合，S={S1，S2，...，SN}，N 表示狀態(tài)的數(shù)量，在第T 個時間點的狀態(tài)序列為Q={Q1Q2...QT};

2)V 表示每個狀態(tài)可能輸出的觀測值的集合，V={V1，V2，...，VM}，M 表示不同觀測值的數(shù)量，在第T 個時間點的觀測值序列為O={O1O2...OT};

3)Π 表示初始狀態(tài)的概率分布，Π={π1，π2，…，πN}。πi=P(Q1=Si)(1≤i≤N)表示在初始狀態(tài)Q1取某個狀態(tài)Si的概率;

4)A 表示狀態(tài)轉(zhuǎn)移矩陣，A=［aij］N×N。aij=P(Qt+1=Sj|Qt=Si)(1≤i，j≤N)表示從t 時刻所處狀態(tài)Si在t+1 時刻轉(zhuǎn)移到狀態(tài)Sj的概率;

5)B 表示觀測值的概率分布矩陣，B=［bjk］M×N。bjk=P(Ot=Vk|Qt=Sj)(1≤j≤N，1≤k≤M)表示在狀態(tài)Sj出現(xiàn)觀測值Vk的概率。

通常，一個確定的HMM 中可能出現(xiàn)的狀態(tài)數(shù)量和觀測值數(shù)量是可以確定的，因此可將它簡記為:λ=(Π，A，B)。

通過隱馬爾科夫模型，可以對用戶的評分行為進行模擬，以尋找目標用戶在下一時間最可能進行評分的項目，這樣可解決數(shù)據(jù)稀疏問題，并且能夠根據(jù)用戶最近的行為，找到用戶最有可能的評分路徑，從而降低計算的時間復(fù)雜度以及避免時間效應(yīng)的影響;融合Item-CF 算法預(yù)計用戶的感興趣程度，在其中選擇符合用戶歷史興趣特征的進行推薦，從而提高推薦的準確度。

2 HMM-ItemCF 推薦算法

假設(shè)用戶給項目評分的行為是可觀察的，被評分的項目即觀察值，暫時不考慮評分值表示的意義，用戶的喜好系統(tǒng)不知道，那么下一次的評分行為只與當前的狀態(tài)有關(guān)，與之前的狀態(tài)無關(guān)。因此，用戶給項目評分的行為序列符合隱馬爾科夫隨機過程。

針對Item-based CF 存在的問題，本文將HMM 與Item-based CF 相融合，建立動態(tài)模型以提高系統(tǒng)向用戶推薦的效果，新模型基本框架如圖1 所示。

圖1 HMM-ItemCF 模型基本框架

HMM-ItemCF 模型各階段具體步驟如下:

Step1 對HMM 的參數(shù)在新模型中作初始化:

1)狀態(tài)S 表示用戶對項目評分的可能取值的集合，僅代表用戶對項目的喜歡程度的劃分，N 表示集合中元素的數(shù)量;

2)觀測值V 表示用戶可能感興趣的項目的集合，代表系統(tǒng)可以觀察到的用戶評分項目，M 表示集合中元素的數(shù)量;

3)初始狀態(tài)的概率分布Π={πi}，πi=P(Q1=Si)表示系統(tǒng)中所有用戶第一次評分為Si的概率。

其中，1≤i，j≤N;

4)狀態(tài)轉(zhuǎn)移概率矩陣A=［aij］N×N，aij=P(Qt+1=Sj|Qt=Si)(1≤i，j≤N)表示系統(tǒng)中所有用戶在某一時刻t 評分為Si，在t+1 時刻轉(zhuǎn)移到給出評分Sj的概率，這里t 只表示評分的先后順序。

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

5)觀測值的概率分布矩陣B=［bjk］M×N，bjk=P(Ot=Vk|Qt=Sj)(1≤j≤N，1≤k≤M)表示用戶給出的評分為Sj恰好是項目Vk的概率。

其中，1≤j≤N，1≤k≤M。

Step2 使用Baum-Welch 算法，根據(jù)訓(xùn)練集中T時刻目標用戶已給出評分的項目序列(觀察序列)O={O1O2...OT}，隱狀態(tài)序列為Q={Q1Q2...QT}，對HMM 模型中的參數(shù)進行訓(xùn)練使得P(O|λ)最大。

1)定義一個前向變量表示在t 時刻處于狀態(tài)i的概率為αt(i)。假設(shè)t +1 時刻狀態(tài)為j，則根據(jù)前向算法有:

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

2)類似的定義一個后向變量βt(i)表示在t 時刻已知狀態(tài)為Si，從t +1 時刻到時刻T 觀察序列為Ot+1Ot+2...OT的概率，則根據(jù)后向算法有:

其中，βT(i)=1，1≤i≤N，1≤t≤T-1;

3)計算P(O|λ):

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

4)假設(shè)目標用戶在某一時間點t 對項目Ot評分為Si同時在t+1 時刻對項目Ot+1評分為Sj的概率變量為ξt(i，j)(1≤i，j≤N，1≤t≤T)。根據(jù)定義將公式(4)～公式(6)代入則有:

5)假設(shè)目標用戶在某一時間點t 對項目Ot評分為Si的概率變量為γt(i，j)(1≤i，j≤N，1≤t≤T)。根據(jù)定義將公式(4)～公式(6)代入則有:

可知:

6)由第4)和第5)可知，用戶的評分習(xí)慣從Si轉(zhuǎn)移到其他評分值的期望為:

評分值從Si轉(zhuǎn)移到Sj的期望為:

Step3 根據(jù)Step2 得到的能夠描述用戶行為的最優(yōu)隱馬爾科夫模型:)以及用戶已有的評分行為路徑，計算K 個下一時刻用戶可能評分的項目OT+1，以及對應(yīng)的隱藏狀態(tài)Si使得P(O1O2...OTOT+1|)最大，按照P(O1O2...OTOT+1|)的大小將OT+1加入候選集I={OT+1，1，OT+1，2，...，OT+1，K}。

Step4 通過Item-CF 算法計算候選集I 中項目與用戶以往評論過的項目的相似度sim(Oj，OT+1，i)(1≤i≤K，1≤j≤T)。

Step5 令m+n=1，m≥0，n≥0，則用戶對項目的喜歡程度為:

Step6 將大于用戶評分平均值的項目，按照預(yù)測評分從大到小排序，形成推薦列表向用戶推薦。

具體算法流程如圖2 所示。

圖2 算法流程圖

3 實驗與結(jié)果分析

3.1 實驗環(huán)境

1)硬件環(huán)境:CPU 為Intel 酷睿i5-4590，8G 1600 MHz 內(nèi)存;

2)軟件環(huán)境:實驗在Ubuntu10.04 操作系統(tǒng)下進行，搭建環(huán)境的軟件包括JDK7，Mathout-0.5，Hadoop-1.1.1 和Maven2.2.1;

3)實驗數(shù)據(jù):采用著名音樂網(wǎng)站LastFM 的數(shù)據(jù)集，對HMM-ItemCF 模型進行訓(xùn)練分析。在其中隨機抽取1000 名用戶的所有評分記錄，包含對大約17 萬首音樂的19 150 868 個評分，評分范圍為整數(shù)1～5，數(shù)值越高表示用戶越喜歡。按照評分的時間順序，選取前90%為訓(xùn)練集，后10%為測試集。

3.2 模型參數(shù)設(shè)置

根據(jù)多次實驗，模型中K 值的選取、項目相似度算法的選擇，以及權(quán)重參數(shù)的分配對模型的性能有比較大的影響。因此，首先通過實驗確定以上3 個參數(shù)，使模型的性能最優(yōu)化，再與其他著名算法進行比較。實驗將使用均方根誤差評估模型性能。

RMSE 表示均方根誤差(R)，加大了對預(yù)測評分偏差的懲罰，對系統(tǒng)的評測更苛刻［12］。計算公式為:

經(jīng)過多次實驗發(fā)現(xiàn)，參數(shù)K 對模型性能的影響最大。因此，通過多組實驗，找到最佳的K 值使得模型最優(yōu)。

1)不同K 值下音樂相似度算法對模型性能的影響。

根據(jù)訓(xùn)練集的數(shù)據(jù)特征，選擇權(quán)重參數(shù)m=n=0.5，不同的音樂相似度計算方法下，當候選集I 的長度K 的取值變化時，HMM-ItemCF 模型預(yù)測結(jié)果的RMSE 變化如圖3 所示。

圖3 不同K 值下對相似度算法模型預(yù)測結(jié)果的影響

由圖3 可以看出，當候選集I 的長度K ＞220 時，使用改進的余弦相似度算法計算音樂間的相似度時，模型預(yù)測性能最優(yōu)。當K=300 時，RMSE 取得最小值，即此時HMM-ItemCF 模型的預(yù)測性能最佳;當K≥400 時，模型預(yù)測結(jié)果的RMSE 值逐漸取得收斂。因此，在本實驗的數(shù)據(jù)環(huán)境中，候選集I 的長度K 取300，選擇使用改進的余弦相似度算法取得最好的性能。

2)不同K 值下權(quán)重m，n 對模型性能的影響。

通過實驗比較不同K 值下，m 和n 的設(shè)置對HMM-ItemCF 模型性能的影響，實驗結(jié)果如圖4 所示。

圖4 不同K 值下權(quán)重m、n 對模型性能的影響

由圖4 可以看出，在不同K 值下，當權(quán)重m=0.6，n=0.4 時，HMM-ItemCF 模型預(yù)測結(jié)果的平方根誤差最小，其中K=300 時預(yù)測結(jié)果最優(yōu)。

根據(jù)以上2 組實驗，得出結(jié)論:針對同一個Last-FM 數(shù)據(jù)集，當K=300，m=0.6，n=0.4 時，使用改進的余弦相似度算法計算音樂相似度，HMM-ItemCF 模型的推薦性能最佳。

3.3 算法對比

1)預(yù)測評分偏差對比。

在預(yù)測準確度對比實驗中，選取傳統(tǒng)的Userbased CF、Item-based CF、RSVD、Bias-RSVD、SVD ++和TimeSVD 算法作為參照，驗證HMM-ItemCF 模型，在LastFM 數(shù)據(jù)集下的推薦性能，仍然以RMSE 作為評估標準，對比結(jié)果如圖5 所示。

圖5 HMM-ItemCF 模型與其他著名算法的對比

由圖5 可以看出，以上算法在取得最優(yōu)推薦結(jié)果的情況下，HMM-ItemCF 模型預(yù)測結(jié)果與用戶實際評分的偏差最小。

2)推薦性能隨時間變化對比。

在算法的推薦性能隨時間變化的對比中，將HMM-ItemCF 模型與原始的Item-based CF 算法進行對比，主要考察它們的推薦準確度隨時間的變化。因此，在這里引進準確率(Precision，P)、召回率(Recall，R)以及F1 指數(shù)3 項評估標準［13-14］。令X(u)表示根據(jù)用戶在訓(xùn)練集上的行為，系統(tǒng)給用戶作出的推薦列表，O(u)表示用戶在測試集上的行為列表，則有:

分別按日、周、月、年統(tǒng)計用戶的行為數(shù)據(jù)進行推薦，實驗結(jié)果如圖6～圖8 所示。

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

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

圖8 F1 指數(shù)隨時間變化對比

由圖6～圖8 可以看出，在本次實驗的數(shù)據(jù)集上隨著時間的推移，傳統(tǒng)的Item-based CF 算法的準確度，由剛開始的逐漸升高到后來會迅速降低，而HMM-ItemCF 模型的推薦準確度變化不明顯，具有較高的穩(wěn)定性。

根據(jù)以上2 組對比實驗不難得出:HMM-ItemCF模型，不論是預(yù)測的準確度還是隨著時間推移的穩(wěn)定性，在傳統(tǒng)的Item-based CF 算法基礎(chǔ)上得到了較大的提升。這證明該模型是有效的，算法性能得到了明顯的提高。

4 結(jié)束語

針對傳統(tǒng)的基于項目的協(xié)同過濾推薦算法中數(shù)據(jù)稀疏問題，以及隨著時間推移推薦準確度大幅度降低問題，提出將隱馬爾科夫模型與傳統(tǒng)的基于項目的協(xié)同過濾推薦算法相融合的推薦算法。該算法通過隱馬爾科夫模型，對系統(tǒng)中所有用戶的評分行為，與目標用戶的歷史評分行為進行統(tǒng)籌分析，找到一批用戶下一時刻概率最高的評分對象，并將這些評分對象發(fā)生概率與傳統(tǒng)的項目相似度計算方法相加權(quán)，得到新的相似度，最終產(chǎn)生推薦結(jié)果。實驗表明，改進后的新算法具有較高的可行性。在今后的工作中，筆者將對該算法作進一步擴展和改進，考慮項目的內(nèi)容特征，從而進一步改善推薦性能。

［1］Breese J S，Heckerman D，Kadie C，et al.Empirical analysis of predictive algorithms for collab-orative filtering［C］// Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI '98).1998:43-52.

［2］Dietmar Jannach，Markus Zanker，Alexander Felfernig，et al.Recommender Systems An Introduction［M］.Britain:Cambridge University Press，2010.

［3］Lü Linyuan，Medo M，Yeung C H，et al.Recommender systems［J］.Physics Reports，2012，519(1):1-49.

［4］林德軍.基于Slope One 改進算法推薦模型的設(shè)計與實現(xiàn)［D］.北京:北京郵電大學(xué)，2013.

［5］段利國，陳俊杰.綜合句法結(jié)構(gòu)及語義相似度的問題推薦技術(shù)［J］.計算機科學(xué)，2012，39(1):203-206.

［6］陳克寒，韓盼盼，吳健.基于用戶聚類的異構(gòu)社交絡(luò)推薦算法［J］.計算機學(xué)報，2013，36(2):349-359.

［7］鄧愛林，左子葉，朱揚勇.基于項目聚類的協(xié)同過濾推薦算法［J］.小型微型計算機系統(tǒng)，2004，25(9):1665-1670.

［8］Lopez-Lopez L M，Castro-Schez J，Vallejo-Fernandez D，et al.A recommender system based on a machine learning algorithm for B2C portals［C］// Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology(WI-IAT'09).2009:524-531.

［9］羅恒.基于協(xié)同過濾視角的受限玻爾茲曼機研究［D］.上海:上海交通大學(xué)，2011.

［10］Rabiner L R.A tutorial on hidden Markov models and selected applications in speech recognition［J］.Proceedings of the IEEE，1991，77(2):257-285.

［11］Baum L E.An inequality and associated maximization technique in statistical estimation of probabilistic functions of Markov processes［J］.Inequalities，1972，3(1):1-8.

［12］項亮.推薦系統(tǒng)實踐［M］.北京:人民郵電出版社，2012.

［13］Du Zhanle.The relationship between prediction accuracy and correlation coefficient［J］.Solar Physics，2011，270(1):407-416.

［14］朱郁筱，呂琳媛.推薦系統(tǒng)評價指標綜述［J］.電子科技大學(xué)學(xué)報，2012，41(2):163-175.