關(guān)于新聞推薦算法的研究

李樂田，吳林，高永存

(中國傳媒大學(xué) 理學(xué)院，北京 100024)

?

關(guān)于新聞推薦算法的研究

李樂田，吳林，高永存

(中國傳媒大學(xué) 理學(xué)院，北京 100024)

隨著互聯(lián)網(wǎng)高速發(fā)展，越來越多的網(wǎng)友依賴于手機(jī)、PC獲取外界訊息。其中較為廣泛關(guān)注的當(dāng)屬新聞閱讀，用戶對(duì)新聞推薦的要求也越來越高，除了各大網(wǎng)站推出的頭條外，不同用戶渴望讀到的新聞千差萬別，那么如何更好的滿足用戶對(duì)新聞的個(gè)性需求就成為新聞推薦的一個(gè)難題，本文使用1000名用戶的新聞閱讀記錄，挖掘用戶的閱讀習(xí)慣，發(fā)現(xiàn)用戶閱讀下一條新聞只與上一條有關(guān)，而與之前的行為無關(guān)，故本文使用馬爾可夫算法對(duì)這一問題進(jìn)行研究。

馬爾可夫模型；新聞推薦；關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘

1　引言

信息時(shí)代萬物千變?nèi)f化，人們追求便捷的步伐刻不容緩，大數(shù)據(jù)隨之而生，與之同時(shí)，針對(duì)大數(shù)據(jù)的軟硬件創(chuàng)新層出不窮，先有阿里旗下的淘寶購物，極大方便了用戶購物，后將其算法優(yōu)化，對(duì)用戶推薦有可能需要的商品，又極大的提高了淘寶日營業(yè)額。后電子地圖、軟件打車、電子外賣等陸續(xù)推出，無疑是給人們的高效生活增光添彩。在這樣紛擾的社會(huì)中，讀書看報(bào)的人越來越少，一個(gè)手機(jī)、一個(gè)電腦就能走天下，讀書看報(bào)均能通過電子瀏覽器實(shí)現(xiàn)，方便又快捷。方式的改變并不影響生活的內(nèi)容，人們還是會(huì)大量閱讀新聞，了解時(shí)事熱點(diǎn)話題，那么問題來了，新聞網(wǎng)站如何能提高用戶的閱讀效率呢？我們就此問題研發(fā)出了一個(gè)新聞推薦算法。

通過大量的前期工作，挖掘出用戶的閱讀習(xí)慣，發(fā)現(xiàn)用戶閱讀下一條新聞只與上一條有關(guān)，而與之前的行為無關(guān)，這剛好符合一階馬爾可夫過程，馬爾科夫算法具有無后效性，即將來的取值只與現(xiàn)在的取值有關(guān)而與之前的無關(guān)，故本文用馬爾可夫算法作為主算法結(jié)合其他算法對(duì)用戶閱讀新聞進(jìn)行個(gè)性化推薦。

2　論文背景與數(shù)據(jù)集描述

大數(shù)據(jù)問題近兩年成為信息技術(shù)學(xué)術(shù)界和產(chǎn)業(yè)界熱論的焦點(diǎn)，普遍輿論認(rèn)為，大數(shù)據(jù)問題已經(jīng)成為信息科學(xué)技術(shù)領(lǐng)域的重要前沿課題之一。[1]

信息時(shí)代萬物變化，大數(shù)據(jù)的重要性已經(jīng)成為行業(yè)共識(shí)，針對(duì)大數(shù)據(jù)技術(shù)和應(yīng)用的創(chuàng)新，其發(fā)展勢(shì)不可擋。如何對(duì)大數(shù)據(jù)進(jìn)行充分和有效的分析和挖掘，使之轉(zhuǎn)換為有價(jià)值的信息和知識(shí)，用于解決各種各樣的科學(xué)和應(yīng)用問題，成為大數(shù)據(jù)時(shí)代信息技術(shù)發(fā)展的重大挑戰(zhàn)，同時(shí)也是信息技術(shù)創(chuàng)新的制高點(diǎn)。[1]

2.1論文背景

基于某大數(shù)據(jù)競賽中的數(shù)據(jù)，從國內(nèi)某新聞網(wǎng)上隨機(jī)選取的若干名用戶于2014年3月的新聞瀏覽記錄，每條記錄包括用戶編號(hào)、新聞編號(hào)、瀏覽時(shí)間(精確到秒)以及新聞文本內(nèi)容。

隨著近年來互聯(lián)網(wǎng)的飛速發(fā)展，個(gè)性化推薦已成為各大主流網(wǎng)站的一項(xiàng)必不可少服務(wù)。提供各類新聞的門戶網(wǎng)站是互聯(lián)網(wǎng)上的傳統(tǒng)服務(wù)，但是與當(dāng)今蓬勃發(fā)展的電子商務(wù)網(wǎng)站相比，新聞的個(gè)性化推薦服務(wù)水平仍存在較大差距。一個(gè)互聯(lián)網(wǎng)用戶可能不會(huì)在線購物，但是絕大部分的互聯(lián)網(wǎng)用戶都會(huì)在線閱讀新聞。因此資訊類網(wǎng)站的用戶覆蓋面更廣，如果能夠更好的挖掘用戶的潛在興趣并進(jìn)行相應(yīng)的新聞推薦，就能夠產(chǎn)生更大的社會(huì)和經(jīng)濟(jì)價(jià)值。初步研究發(fā)現(xiàn)，同一個(gè)用戶瀏覽的不同新聞的內(nèi)容之間會(huì)存在一定的相似性和關(guān)聯(lián)性，物理世界完全不相關(guān)的用戶也有可能擁有類似的新聞瀏覽興趣。[2]此外，用戶瀏覽新聞的興趣也會(huì)隨著時(shí)間的變化而變化，這給推薦系統(tǒng)帶來了新的機(jī)會(huì)和挑戰(zhàn)。因此，希望通過對(duì)帶有時(shí)間標(biāo)記的用戶瀏覽行為和新聞文本內(nèi)容進(jìn)行分析，挖掘用戶的新聞瀏覽模式和變化規(guī)律，設(shè)計(jì)及時(shí)、準(zhǔn)確的推薦系統(tǒng)預(yù)測(cè)用戶未來可能感興趣的新聞。

2.2本文數(shù)據(jù)集與研究問題闡述

我從國內(nèi)某著新聞網(wǎng)站—財(cái)新網(wǎng)隨機(jī)選取了10000名用戶，并抽取了這10000名用戶在2014年3月的所有新聞瀏覽記錄，每條記錄包括用戶編號(hào)、新聞編號(hào)、瀏覽時(shí)間(精確到秒)以及新聞文本內(nèi)容。本研究的目的是盡可能準(zhǔn)確地預(yù)測(cè)每個(gè)用戶瀏覽的最后一條新聞(這條新聞之前曾被其他用戶瀏覽過)，該數(shù)據(jù)用于評(píng)判算法最后成績。每個(gè)用戶最后一條瀏覽記錄之前的的所有新聞瀏覽記錄和新聞文本數(shù)據(jù)，作為訓(xùn)練集以供算法分析和建模使用。研究問題需要根據(jù)訓(xùn)練集中的瀏覽記錄以及新聞的詳細(xì)內(nèi)容，盡可能多的預(yù)測(cè)出測(cè)試集中的數(shù)據(jù)，即預(yù)測(cè)每一個(gè)用戶最后一次瀏覽的新聞編號(hào)。預(yù)測(cè)的準(zhǔn)確程度將成為量化的評(píng)價(jià)指標(biāo)。

3　本問題國內(nèi)研究現(xiàn)狀

研究問題“對(duì)新聞瀏覽推薦的算法”要求盡可能準(zhǔn)確地預(yù)測(cè)每個(gè)用戶瀏覽的最后一條新聞。當(dāng)前比較經(jīng)典的主流推薦系統(tǒng)主要包含三類。基于內(nèi)容的推薦算法，主要分析文本等內(nèi)容來尋找相似文本，然而協(xié)同過濾推薦算法則是尋找相似用戶，根據(jù)相似用戶具有的相似興趣進(jìn)行推薦。混合推薦方法，試圖平衡上述兩種方法的有點(diǎn)和缺點(diǎn)，揚(yáng)長避短。除此上述三種之外，常見的推薦算法還有基于規(guī)則的推薦算法和基于圖的推薦算法。

我們的工作是以馬爾科夫模型為基礎(chǔ)。首先，我們提出了通過衰減窗口來彌補(bǔ)一階馬爾科夫模型巨大的時(shí)間和空間需求，減少計(jì)算量。第二，通過信任度修剪訓(xùn)練集中得到的較弱規(guī)則。第三，在修剪之后的強(qiáng)規(guī)則基礎(chǔ)上，來修剪每個(gè)用戶的狀態(tài)空間。這樣我們不僅提高了預(yù)測(cè)準(zhǔn)確度和召回率，還大大減少了計(jì)算的時(shí)間和空間消耗。

以馬爾科夫鏈作為主算法，計(jì)算用戶對(duì)此算法的適應(yīng)度作為優(yōu)化方式，適應(yīng)度優(yōu)化算法核心思想即盡可能刪除錯(cuò)誤數(shù)據(jù)，從而在穩(wěn)定準(zhǔn)確率的同時(shí)，提高召回率。研究問題是刪除用戶訪問記錄的最后一條作為數(shù)據(jù)集，適應(yīng)度算法刪除用戶訪問的倒數(shù)第二條新聞作為數(shù)據(jù)集進(jìn)行計(jì)算。例如，推測(cè)出的倒數(shù)第二條新聞與真實(shí)數(shù)據(jù)不符則認(rèn)為該用戶不適用于此算法，故不用此算法進(jìn)行新聞推薦，以此類推至倒數(shù)第五條作為閥值和評(píng)分標(biāo)準(zhǔn)，去除所有新聞完全預(yù)測(cè)錯(cuò)誤的用戶，用此算法將f值提高到了34.654%。

4　算法分析

在這一章里，將會(huì)介紹我們的工作里關(guān)于馬爾科夫模型的相關(guān)背景知識(shí)。

4.1馬爾科夫鏈

針對(duì)上述算法中遇到的問題，我認(rèn)為加強(qiáng)推薦關(guān)聯(lián)性才是提高推薦準(zhǔn)確度的關(guān)鍵。為了加強(qiáng)關(guān)聯(lián)性，我不再進(jìn)行用戶的關(guān)聯(lián)，而是轉(zhuǎn)為進(jìn)行新聞的關(guān)聯(lián)。對(duì)此我引用馬爾科夫鏈的概念。

人們常把事物的隨機(jī)變化過程稱作馬爾可夫過程。它具有無后效性，即事物的將來呈什么狀態(tài)、取什么值，僅與它現(xiàn)在的狀態(tài)和取值有關(guān)，與它以前的狀態(tài)和取值無關(guān)。馬爾可夫鏈則是事物在連續(xù)一段時(shí)期內(nèi)若干馬爾可夫過程的總稱，表明事物狀態(tài)由過去到現(xiàn)在、由現(xiàn)在到將來，一環(huán)接一環(huán)，像一根鏈條。在預(yù)測(cè)領(lǐng)域，人們用其對(duì)預(yù)測(cè)對(duì)象各個(gè)狀態(tài)的初始分布和各狀態(tài)間的轉(zhuǎn)移概率進(jìn)行研究，描述狀態(tài)的變化趨勢(shì)，并由此來預(yù)測(cè)未來。[3]

設(shè)隨機(jī)過程{X(t)，t∈T}的狀態(tài)空間為I。如果對(duì)時(shí)間t的任意n個(gè)數(shù)值t1

X(tn-1)=xn-1下X(tn)的條件分布函數(shù)，即

P{X(tn)≤xn|X(t1)=x1，X(t2)=x2，···X(tn-1)=xn-1}=P{X(tn)≤xn|X(tn-1)=xn-1}，xn∈R，

由于許多用戶的新聞閱讀數(shù)目有限，直接限制了鏈長的長度，所以我從三階馬爾科夫鏈開始，作為嘗試。提取某用戶最后三條新聞ID，然后在所有用戶中尋找閱讀過這三條新聞，并且相互緊鄰的用戶，統(tǒng)計(jì)其下一條新聞，進(jìn)行推薦投票操作，獲得票數(shù)最高的新聞，在一定票數(shù)閾值限制下可以進(jìn)入推薦名單。票數(shù)相同的新聞可以采用全部推介或者取新聞ID號(hào)最大者，或者隨機(jī)取值的方案。

4.2相似用戶推薦

為了針對(duì)用戶的行為模式進(jìn)行分析，為每個(gè)用戶尋找與其瀏覽行為較為相似的用戶作為參照，并將相似用戶中原用戶未瀏覽的新聞根據(jù)一定的原則選取進(jìn)行推薦。

先要針對(duì)每名用戶選取相似用戶，相似用戶的選取主要是以用戶瀏覽新聞的相似度為基礎(chǔ)的，在權(quán)衡計(jì)算機(jī)的計(jì)算效率與結(jié)果可用度的前提下，初步將相似度選取的閾值定為相似性新聞數(shù)在原用戶中不不低于50%，在對(duì)應(yīng)用戶中不低于50%。相似用戶選取后，每個(gè)用戶都有與其對(duì)應(yīng)的若干相似用戶，根據(jù)相似程度與新聞相關(guān)數(shù)據(jù)可以進(jìn)行推薦指數(shù)的排序。

recommend_indexnews

此方法得到的結(jié)果較上一種方法有了提升，f值在0.11～0.12之間，準(zhǔn)確率約在15%左右，召回率再10%左右，經(jīng)過對(duì)閾值的詳細(xì)調(diào)整，結(jié)果再次得到提高，不過這樣的結(jié)果顯然并不算好。

沙門氏菌、志賀氏菌、金黃色葡萄球菌、單核細(xì)胞增生李氏特菌、蠟樣芽胞桿菌、銅綠假單胞菌、阪奇腸桿菌、致瀉性大腸埃希氏菌8種致病菌的監(jiān)測(cè)檢驗(yàn)。

經(jīng)過對(duì)數(shù)據(jù)的再次研究與討論，我發(fā)現(xiàn)數(shù)據(jù)中有很多的瀏覽記錄為重復(fù)瀏覽，即同一用戶多次瀏覽同一條新聞，這樣的記錄為數(shù)不少，推測(cè)此類記錄出現(xiàn)的原因大致是因?yàn)榫W(wǎng)絡(luò)刷新、誤操作等原因?qū)е?，所以并不能?duì)其直接刪除，另新聞?dòng)涗洸蝗臈l目因?yàn)轭愃圃蛲瑯硬荒軇h除。

同時(shí)此次的算法雖然不再基于新聞內(nèi)容，但在用戶關(guān)聯(lián)的處理仍舊未做到密切關(guān)聯(lián)，導(dǎo)致很多誤導(dǎo)新聞被導(dǎo)入且無法推薦重復(fù)新聞(依靠此方法關(guān)聯(lián)用戶)，導(dǎo)致準(zhǔn)確率偏低。但此方法在經(jīng)濟(jì)預(yù)測(cè)上可取得一定的效果。

4.3.APRIORI算法

Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來挖掘頻繁項(xiàng)集。其原本被應(yīng)用于預(yù)測(cè)超市購物商品擺放順序，通過提煉大量用戶選擇的各種不同商品的數(shù)據(jù)，進(jìn)行關(guān)聯(lián)，最終找到各商品間的關(guān)聯(lián)方式。但目前該算法已經(jīng)被廣泛的應(yīng)用到商業(yè)、網(wǎng)絡(luò)安全等各個(gè)領(lǐng)域。

需要注意的是，在規(guī)則概率為1的情況下，對(duì)于用戶未知購物行為的預(yù)測(cè)是最有利的。但是在此模型下，概率為1的規(guī)則必須舍棄。將閾值設(shè)置為0.7，支持度設(shè)置為139所獲得的規(guī)則為3000多條。對(duì)用戶歷史記錄中的新聞條數(shù)與規(guī)則中的新聞條數(shù)差不超過2，則可以用此條規(guī)則預(yù)測(cè)用戶的下一次行為。用此算法得到的結(jié)果f值約為8.6%。

4.4基于內(nèi)容的協(xié)同過濾算法

此處我使用基于item的協(xié)同過濾，通過用戶對(duì)不同item的評(píng)分來評(píng)測(cè)item之間的相似性，基于item之間的相似性做出推薦。[6]

協(xié)同過濾算法首先根據(jù)所有相似用戶新聞瀏覽行為對(duì)某個(gè)用戶瀏覽的新聞進(jìn)行打分，形成評(píng)分矩陣?；诟饔脩魹g覽新聞的分?jǐn)?shù)用改進(jìn)的余弦公式計(jì)算用戶之間的相似度。統(tǒng)計(jì)相似用戶范圍內(nèi)，統(tǒng)計(jì)瀏覽次數(shù)最高的前50條新聞。根據(jù)用戶相似度乘以評(píng)分矩陣中新聞分?jǐn)?shù)計(jì)算出前50條新聞的推薦分?jǐn)?shù)，選擇此分?jǐn)?shù)最高的新聞作為推薦新聞。用此算法得到的結(jié)果f值約為16.2%。

4.5算法綜合

考慮到各種算法的局限性以及正確率，我綜合考慮上述優(yōu)化過主算法與輔算法，將輔算法中待選集交集以外的部分在主算法中加以排除，再將所有輔算法的交集并入主算法待選集之中，得到最終結(jié)果。用集合論表示，其公式為：

O=(AIBIC)Y[D-D

I[A-AIB-AIC+AIBIC

+B-BIA-BIC+AIBIC

+C-CIA-CIB+AIBIC]]

用韋恩圖具體表示如下，其中陰影部分即為最終提交的結(jié)果集。使用SPSS軟件實(shí)現(xiàn)的最終結(jié)果f值為34.940%。

圖1　結(jié)果集韋恩圖　

4.6算法實(shí)驗(yàn)

步驟1：分別對(duì)用戶操作：設(shè)用戶瀏覽本條新聞、點(diǎn)擊瀏覽相關(guān)新聞、瀏覽其他新聞、評(píng)論新聞、分享新聞、五個(gè)動(dòng)作分別為S1，S2，···S5，用戶在Si狀態(tài)

(1)

步驟2：記所有用戶五個(gè)狀態(tài)概率ai，(i=1，2，...，5)，為初始狀態(tài)，根據(jù)初始狀態(tài)概率向量和轉(zhuǎn)移矩陣，對(duì)以后用戶動(dòng)作進(jìn)行預(yù)測(cè)，下一次這五個(gè)動(dòng)作概率將變?yōu)椋?/p>

(2)

步驟3：重復(fù)步驟(1)、(2)，經(jīng)過n次計(jì)算，求得穩(wěn)定狀態(tài)下a(n)，則a(n)表示五個(gè)動(dòng)作用戶選擇的概率。

步驟4：計(jì)算

(3)

bij表示用戶由動(dòng)作i轉(zhuǎn)為執(zhí)行動(dòng)作j的概率，從中可得到每個(gè)用戶下一步可能的動(dòng)作。

步驟5：綜合(1)(2)(3)對(duì)用戶可能進(jìn)行的下一步操作給出兩個(gè)預(yù)測(cè)。

用這種方法，我進(jìn)行了二階和一階馬爾科夫鏈的嘗試。其中，一階馬爾科夫鏈的f值在不同的票數(shù)的條件下，效果優(yōu)于二階、三階的結(jié)果，基本能保持在f值29%之上的成績。在票數(shù)為20的條件下，達(dá)到了31.787%的效果。二階和三階馬爾科夫鏈的效果略次于之。其算法流圖如下。

圖2　主算法流圖 　

4.7評(píng)價(jià)標(biāo)準(zhǔn)

本實(shí)驗(yàn)采用召回率和準(zhǔn)確率來評(píng)價(jià)實(shí)驗(yàn)結(jié)果，定義如下：

(4)

其中U為要推薦的用戶的集合，表示推薦給用戶的新聞中，確實(shí)在測(cè)試集中被此用戶瀏覽的個(gè)數(shù)。由于本次試驗(yàn)每個(gè)用戶在測(cè)試集中只有一條記錄，所以的值為0或1。表示推薦給用戶的推薦列表長度。

(5)

其中為測(cè)試集中用戶真正瀏覽的新聞數(shù)目，在我們的測(cè)試環(huán)境中，等于推薦的用戶總數(shù)。

5　結(jié)束語

本研究良好的迎合了當(dāng)前信息業(yè)發(fā)展的趨勢(shì)，為瀏覽其用戶提供了個(gè)性化的新聞推薦，從而提高用戶瀏覽體驗(yàn)。論文中使用了一種簡單易懂但卻卓有成效的主算法——馬爾可夫算法，結(jié)合適應(yīng)度優(yōu)化算法并綜合各種輔算法，在良好的預(yù)測(cè)f值的基礎(chǔ)上進(jìn)一步拔高，獲得了優(yōu)異的推薦結(jié)果，并對(duì)不同的算法作了嘗試和總結(jié)，找出更適合本問題的推薦算法，當(dāng)然，一定還存在著更準(zhǔn)確的推薦算法，這些算法及其思想在其本質(zhì)上是有著扎實(shí)數(shù)學(xué)與概率學(xué)基礎(chǔ)的，潛力無窮，在未來的數(shù)據(jù)挖掘應(yīng)用中必將呈現(xiàn)其價(jià)值，為商業(yè)經(jīng)濟(jì)提供技術(shù)支持與保障。相信在又一代數(shù)據(jù)研究者的開發(fā)與推動(dòng)之下，大數(shù)據(jù)時(shí)代將提高人們的生產(chǎn)及生活體驗(yàn)，促進(jìn)生產(chǎn)力與效率的提升，福蔭后世。

[1]黃哲學(xué)，曹付元，李俊杰.面向大數(shù)據(jù)的海云數(shù)據(jù)系統(tǒng)關(guān)鍵技術(shù)研究[J].網(wǎng)絡(luò)新媒體技術(shù)，2012，1(6)：20-26.

[2]B Yang，P F Zhao. Recommendation algorithm overview[J].Journal of Shanxi University (Nat Sci Ed)，2011，34(3)：337-350.

[3]F Abel，N Henze，D Krause. Exploiting additional Context for Graph-based Tag Recommendations in Folksonomy System[J].2008 IEEE/WIC/ACM International Conference on Web Intelligence an Intelligent Agent Technology，2008：148-154.

[4]盛驟，謝式千，潘承毅.概率論與數(shù)理統(tǒng)計(jì)[M].高等教育出版社，1979，319-320.

[5]S Bin，L Page. The anatomy of a large-scale hypertext web search engine[J].In：Seventh International World-Wide Web Conference (WWW 1998)，April 14-18，1998.

[6]J M Kleinberg. Authoritative sources in a hyperlink environment[J].Journal of the ACM，1999，46(5)：604-632.

(責(zé)任編輯：馬玉鳳)

Study on Recommendation Algorithm News

LI Le-tian，WU Lin，GAO Yong-cun

(School of Science，Communication University of China，Beijing 100024)

With the rapid development of the Internet，more and more users intend to rely on mobile phones，PC access to get external information. The news reading has got more widespread attention，the users’ requirements of the news recommendation are increasingly high. In addition to the headlines of the websites，different users have different need and interest of different topics. Therefore，it has been a difficulty to satisfy the individual eager of the users. By studying on the record of 1000 users and mining the user’s reading habits，this paper found that users read the news related to the last one，has nothing to do with the previous behavior. So we use Markov Model study on this issue.

markov model；news recommended；association rules；data mining

2015-09-27

李樂田(1991-)，女(漢族)，山西大同人，中國傳媒大學(xué)研究生.E-mail：liletian@cuc.edu.cn

O29

A

1673-4793(2016)01-0040-05