基于相似消息的流行度預(yù)測方法

高金華,沈華偉,程學(xué)旗,劉 悅

(1. 中國科學(xué)院 計算技術(shù)研究所 網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點實驗室，北京 100190；2. 中國科學(xué)院大學(xué)，北京 100049)

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，社交網(wǎng)絡(luò)已經(jīng)成為人們?nèi)粘Ｉ钪胁豢苫蛉钡囊徊糠?。社交網(wǎng)絡(luò)的出現(xiàn)，極大地方便了消息的產(chǎn)生和傳播。在社交網(wǎng)絡(luò)上，用戶可以自由地發(fā)布消息，也可以選擇自己感興趣的用戶進(jìn)行關(guān)注，進(jìn)而獲取自己感興趣的內(nèi)容。然而，用戶有限的時間和關(guān)注度使得消息在傳播過程中獲取的流行度的分布是不均勻的[1-2]。這種分布不均勻的現(xiàn)象，吸引了研究者的廣泛關(guān)注，并最終引出流行度預(yù)測問題。流行度預(yù)測問題在很多實際應(yīng)用中都有著重要意義，包括服務(wù)商站點資源優(yōu)化、熱點資源發(fā)現(xiàn)、社交網(wǎng)絡(luò)市場營銷等。

傳統(tǒng)的流行度預(yù)測方法可以分為兩類: 基于點過程的方法[3-5]和基于特征的方法[6-8]。基于點過程的方法采用隨機過程來刻畫待預(yù)測消息在觀測窗口內(nèi)的流行度到達(dá)過程，通過對流行度變化速率的建模和估計，來預(yù)測該消息后續(xù)的流行度變化。這類方法能夠較好地刻畫流行度的到達(dá)過程，但是由于沒有顯式地利用其他歷史消息的信息，這類方法的預(yù)測能力非常有限?；谔卣鞯姆椒ㄍǔ⒘餍卸阮A(yù)測問題形式化為回歸或分類問題，人工地定義和抽取大量的特征，并以歷史消息為訓(xùn)練樣本，訓(xùn)練得到特征和流行度之間的變換函數(shù)，進(jìn)而對測試集中的消息進(jìn)行預(yù)測。這類方法采用了有監(jiān)督的學(xué)習(xí)框架，因此有較好的預(yù)測能力。但是，基于特征的方法對所有的消息都采用同一個預(yù)測模型，忽略了消息本身的特異性。實際上，消息在社交網(wǎng)絡(luò)上的傳播存在不同的傳播模式[9]，對應(yīng)的預(yù)測函數(shù)也應(yīng)不盡相同。因此，我們需要一個更細(xì)粒度的流行度預(yù)測方法。

本文提出了一種基于相似消息的流行度預(yù)測方法。對于待預(yù)測的消息，我們根據(jù)它在觀測窗口內(nèi)的流行度增長過程，從歷史消息中尋找出與之相似的部分消息，再基于相似消息來對該消息后續(xù)的流行度變化進(jìn)行預(yù)測。在定義消息之間的相似度時，我們將消息傳播中包含的傳播模式作為隱變量，利用LDA模型[10]學(xué)習(xí)得到消息在不同傳播模式上的分布來作為消息的表達(dá)，進(jìn)而使用余弦距離來度量消息之間的相似度。我們的方法既充分利用了歷史信息，同時也考慮了消息本身傳播過程的特異性。在數(shù)據(jù)集上的實驗結(jié)果表明，我們的方法在流行度預(yù)測任務(wù)上要明顯優(yōu)于前兩類方法。

1 相關(guān)工作

已有的流行度預(yù)測方法大體可以分為兩類: 基于特征的方法和基于點過程的方法。

基于特征的方法通常將流行度預(yù)測問題形式化為回歸或分類問題，人工地定義和抽取大量特征，使用有監(jiān)督的框架來學(xué)習(xí)特征到流行度之間的變換函數(shù)。Szabo等[11]研究了Digg上的新聞數(shù)據(jù)和Youtube上的視頻數(shù)據(jù)，發(fā)現(xiàn)這些內(nèi)容早期的流行度和后期流行度之間存在著很強的對數(shù)線性相關(guān)，并將消息的早期累積流行度為特征，提出了SH(Szabo-Huberman)模型來預(yù)測消息的流行度。Pinto等[12]在SH模型的基礎(chǔ)上，將觀測窗口內(nèi)的累積流行度拆分為等長時間間隔內(nèi)的流行度增長序列，利用多元回歸模型來預(yù)測流行度。這類工作中，也有研究者專注于分析和發(fā)現(xiàn)對流行度預(yù)測有指示作用的特征。Suh等[13]研究了Twitter平臺上消息的轉(zhuǎn)發(fā)情況，并抽取了一系列的特征來預(yù)測消息的最終轉(zhuǎn)發(fā)數(shù)。實驗結(jié)果表明，消息中包含的URL和hashtag標(biāo)簽信息，對消息轉(zhuǎn)發(fā)數(shù)的預(yù)測有很重要的指示作用。消息發(fā)布者的元信息，包括粉絲數(shù)和關(guān)注數(shù)等，也與最終的預(yù)測結(jié)果存在很強的關(guān)聯(lián)關(guān)系。Bao等[14]研究了新浪微博上消息轉(zhuǎn)發(fā)形成的轉(zhuǎn)發(fā)樹數(shù)據(jù)，提取了消息轉(zhuǎn)發(fā)樹的深度和連接密度兩個特征，有效提高了回歸模型的預(yù)測精度。此外，Cheng等[15]將流行度預(yù)測問題形式化為階段性的增長預(yù)測問題。他們指出，在以往的流行度分類預(yù)測問題中，由于流行度本身的分布是冪律的，導(dǎo)致各個類別樣本數(shù)極度不均勻，從而影響最終的預(yù)測效果。因此，他們提出了“kto2k”問題: 給定當(dāng)前流行度為k的消息，預(yù)測它們最終的流行度能否增長到2k。基于樣本集中流行度的分布，他們證明了提出的“kto2k”問題是一個均衡的二分類問題，并抽取了內(nèi)容特征、用戶特征、網(wǎng)絡(luò)結(jié)構(gòu)特征以及時序特征來進(jìn)行預(yù)測。實驗結(jié)果表明，隨著k的增長，分類預(yù)測的準(zhǔn)確率也在不斷提高。

基于點過程的方法通常只利用待預(yù)測消息自身的信息，通過對待預(yù)測消息在觀測窗口內(nèi)流行度到達(dá)過程的建模，來預(yù)測消息后續(xù)流行度的變化。這類方法將流行度的增長過程形式化為一個計數(shù)過程(counting process)[16]，并將強度函數(shù)(intensity function)的刻畫作為模型的核心。強度函數(shù)l(t)刻畫了給定歷史信息Ht下，在時間窗口[t,t+dt)內(nèi)有新事件發(fā)生的概率，如式(1)所示。

P{event in [t,t+dt) |Ht}=l(t)dt

(1)

基于這一框架，Shen等[3]提出了基于自增強泊松過程(Reinforced Poisson Process, RPP)的RPP模型。在建模消息的強度函數(shù)時，考慮了消息本身的吸引力、時間衰減機制和富者愈富機制。Gao等[4]將RPP模型應(yīng)用到新浪微博中，并對幾種機制的作用形式進(jìn)行了修正。Bao等[5]采用了自激勵Hawkes過程(Self-exciting Hawkes process)來建模強度函數(shù)，刻畫了消息傳播過程中轉(zhuǎn)發(fā)用戶帶來的激勵作用。Zhao等[17]在自激勵過程的基礎(chǔ)上，進(jìn)一步引入了用戶的影響力信息。他們將用戶的粉絲數(shù)加入到強度函數(shù)的建模中，進(jìn)一步提升了模型的預(yù)測效果。這類方法由于沒有利用其他歷史消息的信息，預(yù)測能力比較有限。

此外，Mishra等[18]提出了將上述兩類方法融合的方法。他們先利用自激勵過程來建模消息在觀測窗口內(nèi)的流行度增長過程，再將學(xué)習(xí)得到的參數(shù)與人工抽取的其他特征合并，利用回歸模型來預(yù)測消息的最終流行度。近年來，深度學(xué)習(xí)的方法在流行度預(yù)測領(lǐng)域也取得了不錯的的進(jìn)展。Li等[19]提出了端到端的DeepCas模型。他們在監(jiān)督學(xué)習(xí)框架下，先利用深度學(xué)習(xí)模型將消息在觀測窗口內(nèi)的轉(zhuǎn)發(fā)情況表示為向量，再利用神經(jīng)網(wǎng)絡(luò)模型學(xué)習(xí)消息的流行度增長與轉(zhuǎn)發(fā)向量間的轉(zhuǎn)換函數(shù)。Cao等[20]在自激勵過程的啟發(fā)下，提出了DeepHawkes模型。他們利用深度學(xué)習(xí)模型，刻畫了傳播過程中的用戶影響力、用戶激勵以及時間衰減效應(yīng)等影響因子，在數(shù)據(jù)集上取得了很好的預(yù)測效果。

2 模型

2.1 問題形式化

2.2 整體預(yù)測框架

不同于傳統(tǒng)的基于特征的方法和基于點過程的方法，我們提出了一種基于相似消息的流行度預(yù)測方法。我們首先對所有消息在觀測窗口的傳播數(shù)據(jù)進(jìn)行表示學(xué)習(xí)，得到他們的表示。對于待預(yù)測的每一條消息j，我們根據(jù)他們的表示，從歷史消息中找到與之最相似的前K條消息，利用這K條消息在窗口[T0,T]內(nèi)的數(shù)據(jù)，來預(yù)測消息j在預(yù)測窗口[T0,T]內(nèi)的流行度。我們提出的方法，既充分利用了歷史消息的傳播數(shù)據(jù)，同時又避免了對所有的消息使用統(tǒng)一的預(yù)測模型，充分考慮了消息傳播過程的特異性。在我們的模型中，如何對消息的傳播數(shù)據(jù)進(jìn)行表示，進(jìn)而找到與之相似的歷史消息，是至關(guān)重要的部分。

2.3 消息傳播數(shù)據(jù)的表示

時間序列(x1,x2,…,xN)通常被用來將消息的傳播數(shù)據(jù)轉(zhuǎn)化為定長的向量化表示，其中N表示劃分的等長時間區(qū)間的個數(shù)，xi表示在第i個時間間隔內(nèi)流行度的增長量。這種時間序列的表示方式能一定程度上反映消息的流行度變化趨勢，但是這種表示方法的效果受時間區(qū)間粒度的影響，同一條消息在不同大小的時間區(qū)間下的表示差異較大。另外，它也不能刻畫消息在傳播模式上的區(qū)別。事實上，消息的傳播過程中包含著不同的傳播模式，如快速爆發(fā)的模式、均勻增長的模式、逐漸衰退的模式等。圖1中展示了兩條示例消息的傳播過程。從圖中可以看到，在時間序列表示下，以5個單位時間為一個時間區(qū)間，兩條消息的表達(dá)都是(25,21)，但是兩條消息的傳播過程并不相同。第一條消息經(jīng)歷了平穩(wěn)增長和衰落的過程，可以預(yù)見后續(xù)的流行度增長量會比較??；而第二條消息在經(jīng)歷了第1個時間間隔內(nèi)的快速增長和衰落后，在第2個時間間隔內(nèi)又迎來了平穩(wěn)增長的過程，后續(xù)的流行度應(yīng)該會持續(xù)增加。因此，基于時間序列的表示方法，會忽略消息傳播過程所包含的不同傳播模式，難以真正捕獲傳播過程相似的消息用于預(yù)測。

進(jìn)一步地觀察圖1我們可以發(fā)現(xiàn): 消息在處于不同的傳播模式時，轉(zhuǎn)發(fā)到達(dá)的速率不同，形成的轉(zhuǎn)發(fā)時間間隔的分布也不相同。當(dāng)消息處于快速爆發(fā)的模式時，會產(chǎn)生大量的短時間間隔；而當(dāng)消息處于衰退模式時，會產(chǎn)生較少但是持續(xù)時間長的轉(zhuǎn)發(fā)時間間隔。因此，消息在傳播過程中產(chǎn)生的時間間隔數(shù)據(jù)，可以幫助推斷消息所處的傳播模式。

圖1 兩條示例消息的傳播數(shù)據(jù)

① 消息i根據(jù)自身傳播模式的分布，采樣一個傳播模式P；

2.4 消息的流行度預(yù)測

我們模型的整體預(yù)測框架如圖2所示。

圖2 模型的整體預(yù)測框架

3 實驗

3.1 實驗數(shù)據(jù)

我們抓取了微博上某一天的全部源發(fā)消息和它們發(fā)布后24小時內(nèi)的轉(zhuǎn)發(fā)數(shù)據(jù)來作為我們的實驗數(shù)據(jù)。我們過濾了發(fā)布1h后累計轉(zhuǎn)發(fā)數(shù)小于10的消息，最終用于實驗的數(shù)據(jù)集包含了6.5萬條源發(fā)消息和它們在發(fā)布后24h內(nèi)的轉(zhuǎn)發(fā)數(shù)據(jù)。我們將數(shù)據(jù)集平均分成5份，輪流選取其中1份為測試集，剩余4份為訓(xùn)練集來進(jìn)行實驗。所有展示的實驗結(jié)果均為5個測試集的平均結(jié)果。

3.2 實驗準(zhǔn)備

3.2.1 對比模型

我們選取了以下三個模型來和我們的模型進(jìn)行對比:

① RPP模型[3]: 采用了自增強泊松過程來刻畫流行度的到達(dá)過程，考慮了消息自身的吸引力、時間衰減效應(yīng)和富者愈富效應(yīng)；

② Pinto模型[12]: 將消息在觀測時間窗口內(nèi)的轉(zhuǎn)發(fā)數(shù)據(jù)表示為時間序列，利用多元線性回歸模型來學(xué)習(xí)時間序列特征與流行度之間的變換函數(shù)；

③ SeqSim模型: 和我們提出的模型一樣，SeqSim模型也是先從歷史消息中尋找到和待預(yù)測消息相似的消息，再利用相似消息進(jìn)行預(yù)測。不同于我們的模型，SeqSim模型直接使用時間序列來表示消息的傳播數(shù)據(jù)。

3.2.2 評價指標(biāo)

我們使用了平均絕對百分誤差(Mean Absolute Percentage Error， MAPE)來度量不同模型的預(yù)測效果。模型在預(yù)測時間點t的MAPE值定義如式(2)所示。

(2)

3.2.3 參數(shù)設(shè)置

在我們的實驗中，消息的觀測窗口設(shè)置為1小時，預(yù)測窗口設(shè)置為24小時。在利用LDA模型學(xué)習(xí)消息的表示時，LDA的主題數(shù)為4時效果最好，因此實驗部分的結(jié)果均為主題數(shù)為4時的結(jié)果。主題數(shù)對預(yù)測效果的影響將在實驗分析章節(jié)中進(jìn)行討論。在選取最相似的歷史消息時，我們將K設(shè)置為10，即為每條待預(yù)測消息找到與之最相似的10條歷史消息來進(jìn)行預(yù)測。對于Pinto模型和SeqSim模型，在生成時間序列時，我們選擇的時間區(qū)間的長度為5min。在使用截尾均值進(jìn)行預(yù)測時，截尾均值的參數(shù)e%設(shè)置為10%。

3.3 實驗結(jié)果

我們以消息發(fā)布后1小時內(nèi)的轉(zhuǎn)發(fā)情況作為觀測，來預(yù)測后續(xù)每隔1小時后消息的流行度情況，實驗結(jié)果如圖3所示。

從圖3中可以看出，我們提出的模型的預(yù)測效果要明顯優(yōu)于其他3個模型。Pinto模型的表現(xiàn)效果最差，因為它用一個模型來預(yù)測所有的待預(yù)測消息，噪聲影響很大。比較Pinto模型和SeqSim模型可以看出，利用相似微博來預(yù)測流行度，可以有效地區(qū)分出消息本身的特異性，從而顯著地提升預(yù)測效果。對比SeqSim模型和我們提出的模型的結(jié)果可以看出，相比于時間序列的表示方法，我們提出的基于消息傳播模式的表示方法，可以更好地刻畫消息的傳播過程，進(jìn)而找到傳播過程相似的歷史消息來進(jìn)行預(yù)測，得到更精確的預(yù)測效果。另外，綜合對比兩個基于相似消息的模型和其他兩個模型，可以發(fā)現(xiàn)基于相似消息的模型在進(jìn)行預(yù)測時，隨著時間的增長，預(yù)測誤差的增長更加平穩(wěn)，預(yù)測性能更好。

圖3 不同模型的流行度預(yù)測效果

3.4 實驗分析

3.4.1 LDA模型中主題個數(shù)的影響

在利用LDA模型進(jìn)行表示學(xué)習(xí)時，主題個數(shù)是一個非常重要的超參。我們對不同主題個數(shù)設(shè)定下的預(yù)測效果進(jìn)行了實驗，結(jié)果如圖4所示，其中M表示主題個數(shù)，t表示預(yù)測時刻。

圖4 不同主題數(shù)目下的預(yù)測效果

從圖4可以看出，在不同的預(yù)測時間點上，主題個數(shù)為4的模型的預(yù)測效果都要明顯地優(yōu)于其他模型。因此，在對比實驗中，我們將LDA模型的主題個數(shù)設(shè)置為4。

3.4.2 相似消息分析

我們在圖5中展示了部分待預(yù)測消息以及模型，并找到與之相似的歷史消息的傳播數(shù)據(jù)。圖中豎線標(biāo)識的位置為觀測窗口的大小，加號數(shù)據(jù)標(biāo)識了待預(yù)測消息流行度的實際變化情況。從圖中可以看到，我們找到的相似消息，在觀測窗口內(nèi)的傳播過程和流行度大小與待預(yù)測消息非常相似；同時在預(yù)測時間窗口中，消息的流行度變化趨勢也非常一致。這表明我們提出的基于傳播模式的表示方法，可以有效地刻畫消息的傳播過程，從而找到那些變化趨勢相近的歷史消息來輔助預(yù)測。另外，從圖中可以看出，找到的近似消息中存在離群點，這也說明了采用截尾平均值的必要性。

4 總結(jié)

針對現(xiàn)有的兩類流行度預(yù)測方法的不足，本文中提出了一種基于相似消息的流行度預(yù)測方法。對于每一條待預(yù)測的消息，我們從歷史消息中選取出傳播相似度最高的K條消息來進(jìn)行預(yù)測。在計算消息間的相似度時，我們利用了文檔主題建模領(lǐng)域的LDA模型，來學(xué)習(xí)得到消息的表示。我們將消息轉(zhuǎn)發(fā)過程中產(chǎn)生的時間間隔數(shù)據(jù)作為輸入，將消息中包含的不同傳播模式作為隱變量，利用LDA模型，學(xué)習(xí)得到消息在不同傳播模式上的分布作為消息的表示。數(shù)據(jù)集上的實驗結(jié)果表明，我們的方法能夠有效地發(fā)現(xiàn)傳播模式相近的消息，進(jìn)而取得了更好的流行度預(yù)測效果。在本文的模型中，在學(xué)習(xí)消息的表示時，學(xué)到的消息并沒有顯式的時序特征。在接下來的工作中，我們會從這個方向展開，來研究消息的傳播模式隨時間的變化，以及其對流行度預(yù)測效果的影響。