李 增,劉 羽，李誠誠

(桂林理工大學(xué)信息科學(xué)與工程學(xué)院，廣西 桂林 541006)

1 引言

智能化交互式的網(wǎng)絡(luò)平臺，使得每個人都可以是信息的上傳者和接收者。信息量的爆炸式增加導(dǎo)致信息量過載和人們需求量的嚴(yán)重不平衡[1]。因此，如何從大量的信息中找出用戶想要的信息并推薦給用戶變得尤為重要。

智能新聞推薦系統(tǒng)的出現(xiàn)進(jìn)一步迎合了用戶的需求，該系統(tǒng)不僅能幫助用戶發(fā)現(xiàn)有價值的新聞，還可以將新聞發(fā)送給對其感興趣的用戶。在國內(nèi)，個性化新聞推薦系統(tǒng)也在飛速發(fā)展。2003年，Baidu推出了比較成熟的新聞推薦系統(tǒng)，使之成為了當(dāng)時最成功的中文新聞推薦系統(tǒng)[2]。2008年，非負(fù)矩陣分解為推薦系統(tǒng)的設(shè)計提供了新的策略和方法[3]。2015年，研究者將隱馬爾科夫模型運用于推薦系統(tǒng)的研究中，在傳統(tǒng)的協(xié)作型過濾算法的基礎(chǔ)上加入隱馬爾科夫模型，其推薦效果得到意想不到的提高[4]。在個性化推薦系統(tǒng)中，應(yīng)用最為廣泛的是協(xié)同過濾算法[5]，根據(jù)其選取的鄰域不同，分為基于用戶的協(xié)同過濾算法和基于內(nèi)容的協(xié)同過濾算法。2種算法都存在各自的問題。對于基于用戶的協(xié)同過濾算法，其算法本身更容易忽略掉新聞的本身特性，如時效性，這就會導(dǎo)致推薦的新聞時效性不好，降低了用戶的實際接受率；基于內(nèi)容的協(xié)同過濾算法往往會忽略用戶的特性，如喜好度，這就會導(dǎo)致同一種相似的新聞大量出現(xiàn)在推薦列表中，無法達(dá)到拓寬視野的效果[6,7]。

在新聞系統(tǒng)中，用戶的所有行為都會以日志的形式保存下來。日志是記錄系統(tǒng)事件的文件集合，在新聞瀏覽過程中，用戶的點擊瀏覽、閱讀時長、分享、評論等操作會以日志的形式記錄下來，用戶瀏覽新聞的先后順序也會以日志的形式記錄下來。這些日志是分析用戶行為的重要依據(jù)。在前人的理論研究基礎(chǔ)上[8]，用戶瀏覽新聞的行為更符合馬爾科夫過程，即下一個決策僅僅取決于當(dāng)前的狀態(tài)，跟以前的狀態(tài)并無關(guān)系。因此，本文對馬爾科夫算法進(jìn)行深入研究，將其應(yīng)用于新聞推薦系統(tǒng)中。

2 用戶行為日志分析和隱馬爾科夫模型

2.1 用戶行為日志分析

用戶行為日志來自于字節(jié)跳動公司內(nèi)部開發(fā)使用的新聞頭條用戶日志，其中有10 000個用戶，523 145條記錄，出于隱私考慮對用戶的記錄做了特殊處理。圖1給出了部分用戶的行為日志。

Figure 1 Original user log圖1 原始用戶日志記錄

如圖1所示，用戶原始日志為我們提供了大量的信息，如IP可以提供上網(wǎng)地域，瀏覽時長可以提供用戶的喜好，最重要的是日志中的網(wǎng)址，這個網(wǎng)址記錄了用戶是從哪個新聞頁面跳轉(zhuǎn)到此新聞來的。這條記錄在用戶的瀏覽過程中可以形成一個閱讀鏈，這個閱讀鏈跟馬爾科夫鏈(Markov Chain)有相似之處。因此，用馬爾科夫鏈模擬用戶的瀏覽過程，更接近用戶的實際瀏覽行為。

2.2 馬爾科夫模型

馬爾科夫鏈，又稱為離散時間馬爾科夫鏈DTMC(Discrete-Time Markov Chain)，其含義為狀態(tài)空間從一個狀態(tài)到另一個狀態(tài)的過程，該過程“無記憶”，即下一狀態(tài)的概率分布只能由當(dāng)前狀態(tài)決定[9,10]。

用形式化的語言描述，即當(dāng)?shù)仁絻蛇叺臈l件概率都有意義時：

P(Xn+m=j|Xn=in,Xn-1=in-1,…,X1=i1)=

P(Xn+m=j|Xn=i1)

(1)

其中，in為從狀態(tài)i經(jīng)過n次轉(zhuǎn)移變?yōu)闋顟B(tài)j。當(dāng)m=1時，等式成立，則隨機變量序列X=(X1,X2,…,Xn)是1個馬爾科夫鏈。其中Xi為閱讀新聞X1的狀態(tài)，狀態(tài)集合為馬爾科夫鏈的狀態(tài)空間(State Space)。該鏈最大的特點是無后效性，即事物將來的狀態(tài)僅與現(xiàn)有的狀態(tài)有關(guān)，跟以前的狀態(tài)沒有關(guān)系。這在新聞推薦的預(yù)測中，更加符合人們平時閱讀新聞的習(xí)慣。

從用戶的瀏覽日志分析可以直觀地看出用戶所瀏覽的新聞內(nèi)容，這里用其行為和內(nèi)容進(jìn)行建模，如圖2所示。其中，B1，B2，B3，B4是用戶的行為操作，即點擊某一類新聞網(wǎng)頁，該行為是不可見的，因此被稱為隱馬爾科夫鏈。X1，X2，X3，X4是用戶瀏覽的該類的新聞內(nèi)容。通過日志可以很容易發(fā)現(xiàn)X1，X2，X3，X4，……這樣的序列，而如何去求解下一個行為的概率是實現(xiàn)該推薦算法的核心。

Figure 2 Markov chain model圖2 馬爾科夫鏈模型

算法模型如式(2)所示：

P(Bn)=

P(B1→B2)·P(X1)·

P(B1→B2)·P(X2)·

…·

P(Bn-1→Bn)·P(Xn)

(2)

其中，P(Bn-1→Bn)為行為的轉(zhuǎn)換概率，Bn為用戶瀏覽行為，而P(Xn)為用戶瀏覽Xn所屬某類新聞下某一新聞的概率。為了方便計算以獲得最大的概率，本文采用參數(shù)n=3計算。

2.3 相關(guān)推薦算法

協(xié)同過濾算法根據(jù)相似用戶瀏覽的新聞進(jìn)行打分，形成評分矩陣。本文采用改進(jìn)的余弦公式計算新聞Ni和Nj的相似度：

(3)

其中,Ru表示用戶u對瀏覽的新聞給出的評分平均值，Ru,i為用戶u對新聞Ni的評分。在相似用戶中，統(tǒng)計瀏覽量最高的前50條新聞，根據(jù)評分矩陣計算出評分最高的新聞加入推薦名單中。

由于新聞平臺上的相似內(nèi)容太多，推薦算法計算復(fù)雜度大，因此采用K-means(K均值)聚類優(yōu)化。K-means聚類在本文中主要有2個用處：(1)新聞聚類。把相似的新聞聚類成1個組，選取其中2個作為該類新聞的推薦，能夠減少相似新聞的推薦。(2)決定用戶的喜好。如果1個用戶瀏覽某一類新聞過多，可以推測該用戶對這類新聞的興趣比較大。假設(shè)矩陣M為用戶的偏好矩陣，矩陣中行表示用戶，列表示新聞，每個元素表示用戶對新聞的偏好度，由此可以構(gòu)建如下矩陣：

(4)

其中,m，n分別代表用戶數(shù)量和新聞數(shù)量，每1行表示1個用戶對所有新聞的偏好程度，而每1列表示所有用戶對1個新聞的偏好程度。對于某一新聞的喜好程度，很大程度上取決用戶的瀏覽時長，而瀏覽時長由用戶的日志提供，因此用戶的偏好度可由式(5)求得：

(5)

其中,btsij表示用戶i對新聞j的瀏覽時長，btsik表示用戶i對新聞k的瀏覽時長。

Top-N算法可以根據(jù)關(guān)鍵詞對新聞進(jìn)行排序，同時可以篩選出與關(guān)鍵詞相關(guān)性強的新聞，也可以對關(guān)鍵詞匹配高的關(guān)鍵詞進(jìn)行調(diào)整。通過Top-N算法推薦熱點新聞可以有效解決用戶的冷啟動問題，從而提高算法的準(zhǔn)確度。

如果為每個用戶都建立1個馬爾科夫鏈，其計算量巨大。為了減少馬爾科夫鏈的計算量，使其更好地應(yīng)用于新聞推薦算法中，需要對用戶進(jìn)行相似度計算。相似用戶的計算應(yīng)以瀏覽新聞的相似度為基礎(chǔ)，本文通過設(shè)置新聞的相似度閾值來計算相似用戶。

本文采用Jaccard相似系數(shù)進(jìn)行用戶相似度計算，如式(6)所示：

(6)

式(6)只能獲取2個用戶閱讀新聞的相似度，因此更符合本文要求。將用戶A和用戶B瀏覽的新聞集合UserAnews和UserBnews相交，產(chǎn)生共同的新聞集合，再將用戶A和用戶B瀏覽的新聞集合相并，得出2個用戶的新聞總集。用共同的新聞數(shù)除以新聞總數(shù)，其結(jié)果即是兩者的相似度。本文設(shè)置1個閾值，即若User_similar>50，就認(rèn)為用戶A和用戶B為相似用戶。

3 基于隱馬爾科夫模型的混合算法設(shè)計與實現(xiàn)

3.1 隱馬爾科夫算法狀態(tài)轉(zhuǎn)換

通過協(xié)同過濾算法可以很容易地計算出用戶瀏覽每一類新聞的概率P(B)。而在每類新聞中所投票選舉出來的新聞又可以作為下一次各類新聞的可選新聞集，如果每類新聞的前5條作為候選，那么點擊這5條新聞的概率就是1/5。

在實際中，每個用戶閱讀的新聞數(shù)量有限，這就導(dǎo)致了隱馬爾科夫鏈的長度不一。根據(jù)以上模型，本文采用用戶最近的3條瀏覽記錄作為模型的參數(shù)n，推算出下一次最大概率要瀏覽的新聞。

根據(jù)最后3次的操作B1，B2，B3，求解B4作為預(yù)測用戶的點擊動作，其狀態(tài)轉(zhuǎn)換過程為：

P(B1)=P(Xi),i=1,2,3

(7)

式(7)表示在B1動作下，用戶點擊新聞瀏覽的概率可以是P(Xi)，i=1，2，3。

P(B2)=P(B1→B2)=

(8)

式(8)是B1→B2狀態(tài)的轉(zhuǎn)換過程，其中Yi表示第2類新聞下的內(nèi)容，而P(Yi)是Yi在所屬新聞類選出來的概率，max(·)表示取矩陣中的最大元素值。因此，得出B2可能出現(xiàn)的概率。同理B2→B3的狀態(tài)類似，因此可以得到B4存在的概率。

P(B3→B4)=

(9)

其中，Ci表示在B3狀態(tài)下瀏覽的該新聞類下的其他新聞。P(C1)表示C1新聞出現(xiàn)的概率。選取式(8)得到的概率矩陣中前幾個最大概率的新聞作為推薦名單。

3.2 隱馬爾科夫算法的實現(xiàn)

本文采用隱馬爾科夫算法為主要算法，輔以協(xié)同過濾算法和Top-N算法進(jìn)行混合推薦。協(xié)同過濾算法能夠快速對新聞進(jìn)行評分，而Top-N算法能快速選取最優(yōu)的新聞，加入到隱馬爾科夫算法的候選名單中。因此，輔以這2種算法比傳統(tǒng)的排序查找能更快得到候選新聞集合。用韋恩圖表示如圖3所示。

Figure 3 Wayne diagram of result set 圖3 結(jié)果集韋恩圖

算法A為基于內(nèi)容的協(xié)同過濾算法，算法B為Top-N算法，A、B算法重疊的部分表示2個算法得出來的新聞推薦列表，用來做隱馬爾科夫算法的候選新聞集合，最終得到新聞推薦列表。這樣在減少了主算法計算量的同時，提高了其推薦的準(zhǔn)確度。

上述組合算法的流程圖如圖4所示。

Figure 4 Flow chart of algorithm 圖4 算法流程圖

隱馬爾科夫算法步驟如下所示：

步驟1根據(jù)新聞數(shù)據(jù)集和用戶行為日志，分別計算相似新聞和相似用戶，將相似新聞放入同一個集合，相似用戶放入同一個集合。

步驟2通過協(xié)同過濾算法得出推薦名單；同時以并行模式用Top-N算法計算各相似新聞集合中點擊量最高的前3條新聞，作為隱馬爾科夫計算狀態(tài)。

步驟3計算2個推薦名單的并集和交集。

步驟4根據(jù)馬爾科夫算法從相似用戶集合中隨機選擇一位用戶，計算該用戶最近3次瀏覽的新聞ID，統(tǒng)計這3條新聞所有的瀏覽用戶的下一條新聞，生成馬爾科夫鏈。

步驟5若新聞存在于并集中，則將該新聞加入新的推薦名單中，若不在，則舍棄。將新生成的推薦名單和交集上的新聞合并，得出最后的推薦名單，根據(jù)馬爾科夫鏈，選舉出票數(shù)最高的前30條新聞，推送給用戶。

其隱馬爾科夫算法的偽代碼如下所示：

begin:

initializeβ,T,t∈T,aij,bjk,可見序列VT;

fort←t-1;

untilt=1;

returnP(VT)←βi(0)//已知的初始狀態(tài)

end

其中，T為通過協(xié)同過濾和Top-N算法得出的推薦名單集合。VT表示可見序列集合，可見序列為用戶行為序列，即用戶瀏覽新聞序列。for循環(huán)中執(zhí)行的是計算狀態(tài)t-1到狀態(tài)t的概率。βi(0)為第i個用戶的初始化狀態(tài)，aij表示第i個用戶在該狀態(tài)下瀏覽的新聞，bjk表示該新聞類的其他新聞。

4 實驗和結(jié)果分析

本文選取的硬件實驗平臺為若干型號相同的電腦，操作系統(tǒng)是Linux CentOS 6.5,Spark版本是2.2.0，處理器是Intel I7四核處理器(Quad core processor)，8 GB運行內(nèi)存，1 TB硬盤。

本文主要實現(xiàn)基于Spark的隱馬爾科夫算法在推薦算法中的應(yīng)用，通過輔以基于內(nèi)容的協(xié)同過濾算法和Top-N算法，使其準(zhǔn)確度更好。本文通過2個實驗來驗證其混合算法的優(yōu)越性。

在推薦效果測評中，準(zhǔn)確率和召回率是常用的測試指標(biāo)，本文采用該指標(biāo)對算法進(jìn)行測評的時候需要對新聞進(jìn)行劃分。

本文采用準(zhǔn)確率和召回率來評價實驗的結(jié)果：

(10)

(11)

其中，NRS,NRN分別表示感興趣的新聞推薦的條數(shù)和未推薦的條數(shù)。NIS,NIN分別表示不感興趣的新聞推薦的條數(shù)和未推薦的條數(shù)。NS,NN分別表示推薦的新聞總條數(shù)和未推薦的新聞總條數(shù)。

不同數(shù)據(jù)量下的準(zhǔn)確率和召回率如圖5所示。

Figure 5 Accuracy and recall under different data volumes圖5 不同數(shù)據(jù)量下的準(zhǔn)確率和召回率

通過圖5可以看出，算法的性能與數(shù)據(jù)的復(fù)雜度有關(guān)系，隨著數(shù)據(jù)量的增加，新聞集中會有越來越多的“過期”新聞，對于馬爾科夫算法來說，算法的性能隨著推薦數(shù)量的增加而提高。當(dāng)數(shù)據(jù)量在10 000以上時，其準(zhǔn)確率穩(wěn)定在45%，而召回率穩(wěn)定在19%。即超過一定的閾值時，該算法的性能既不會提高也不會降低。

通過對不同的算法的實驗，得出在同樣的數(shù)據(jù)下，不同算法的準(zhǔn)確率和召回率，其結(jié)果如圖6所示。

Figure 6 Accuracy and recall comparison of each algorithm 圖6 各個算法準(zhǔn)確率和召回率對比

通過圖6可知，在同樣的數(shù)據(jù)下，通過余弦相似度計算方法的協(xié)同過濾算法的準(zhǔn)確率為28%，基于Person的協(xié)同過濾算法的準(zhǔn)確率在33%左右，基于內(nèi)容的推薦算法的準(zhǔn)確率為38%，而基于馬爾科夫算法的準(zhǔn)確率達(dá)到了45%，這說明本文的基于馬爾科夫算法在新聞推薦系統(tǒng)中的應(yīng)用明顯優(yōu)于其他推薦算法，且召回率和準(zhǔn)確率有明顯的提高。

實驗顯示，以馬爾科夫為主算法混合基于內(nèi)容的協(xié)同過濾算法和Top-N算法，在新聞推薦中其準(zhǔn)確率明顯比傳統(tǒng)的算法要高。

通過對比基于內(nèi)容的協(xié)同過濾算法在相同的數(shù)據(jù)中的運行時間，來進(jìn)行其運行效率的驗證。實驗結(jié)果如圖7所示。

Figure 7 Comparison of running time of algorithms圖7 算法運行時間對比

通過圖7可以看出，在相同的運行環(huán)境和相同的運算數(shù)據(jù)下，以馬爾科夫算法為主算法的混合推薦算法的運行時間相對少于基于內(nèi)容的協(xié)同過濾算法的，也就是馬爾科夫算法的運行效率要好于協(xié)同過濾算法。但是，由于混合算法的輸入輸出延誤，導(dǎo)致其效果并不是太明顯。

5 結(jié)束語

從人們?yōu)g覽新聞的行為出發(fā)，分析其瀏覽新聞的無目的性更接近于馬爾科夫鏈。因此，將馬爾科夫算法應(yīng)用于新聞推薦系統(tǒng)，通過大量的實驗數(shù)據(jù)對比表明，該算法在推薦過程中比傳統(tǒng)的推薦算法更有效，其準(zhǔn)確率和運行效率更好。但是，該推薦算法具有一定的局限性，即計算復(fù)雜度由所選的行為參數(shù)形成的矩陣所決定，若行為參數(shù)過大，數(shù)據(jù)量隨之增加，其計算復(fù)雜度也會相應(yīng)提高，從而影響推薦效率。因此，在后續(xù)研究中，會進(jìn)一步優(yōu)化算法效率和行為參數(shù)的選擇，提高推薦的準(zhǔn)確度。