解偉凡，郭巖*，匡廣生，余智華，薛源海，沈華偉

基于演化模式的推特話題流行度預(yù)測(cè)方法

解偉凡1，2，郭巖1*，匡廣生1，3，余智華1，薛源海1，沈華偉1

（1.中國科學(xué)院計(jì)算技術(shù)研究所 數(shù)據(jù)智能系統(tǒng)研究中心，北京 100190； 2.中國科學(xué)院大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，北京 101408； 3.中國科學(xué)院大學(xué) 人工智能學(xué)院，北京 101408）（?通信作者電子郵箱guoy@ict.ac.cn）

針對(duì)以往流行度預(yù)測(cè)方法未利用演化模式之間的差異和忽略預(yù)測(cè)時(shí)效性的問題，提出了一種基于演化模式的推特話題流行度預(yù)測(cè)方法。首先，基于?SC算法對(duì)大量歷史話題的流行度序列進(jìn)行聚類，并得到6類演化模式；然后，使用各類演化模式下的歷史話題數(shù)據(jù)分別訓(xùn)練全連接網(wǎng)絡(luò)（FCN）作為預(yù)測(cè)模型；最后，為選擇待預(yù)測(cè)話題的預(yù)測(cè)模型，提出幅度對(duì)齊的動(dòng)態(tài)時(shí)間規(guī)整（AADTW）算法來計(jì)算待預(yù)測(cè)話題的已知流行度序列與各演化模式的相似度，并選取相似度最高的演化模式的預(yù)測(cè)模型進(jìn)行流行度預(yù)測(cè)。在根據(jù)已知前20 h的流行度預(yù)測(cè)后5 h的流行度的任務(wù)中，與差分整合移動(dòng)平均自回歸（ARIMA）方法以及使用單一的全連接網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)的方法相比，所提方法的預(yù)測(cè)結(jié)果的平均絕對(duì)百分比誤差（MAPE）分別降低了58.2%和31.0%。實(shí)驗(yàn)結(jié)果表明，基于演化模式得到的模型群相較于單一模型能更加準(zhǔn)確地預(yù)測(cè)推特話題流行度。

推特話題；演化模式；流行度預(yù)測(cè)；社交網(wǎng)絡(luò)；時(shí)間序列

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，社交網(wǎng)絡(luò)已經(jīng)成為人們?nèi)粘Ｉ钪胁豢苫蛉钡囊徊糠?。社交網(wǎng)絡(luò)的出現(xiàn)，極大地方便了消息的產(chǎn)生和傳播。在社交網(wǎng)絡(luò)上，用戶針對(duì)自己感興趣的話題發(fā)布消息，備受關(guān)注的熱點(diǎn)話題會(huì)迅速擴(kuò)散，具體表現(xiàn)包括消息發(fā)布數(shù)量大、消息的轉(zhuǎn)發(fā)評(píng)論次數(shù)多、消息發(fā)布者的社會(huì)影響力大等。網(wǎng)絡(luò)話題的流行度預(yù)測(cè)有著重大的現(xiàn)實(shí)意義，在話題傳播早期預(yù)測(cè)出下一階段的流行程度，可以對(duì)話題在將來是否成為熱點(diǎn)話題進(jìn)行及時(shí)的預(yù)判，在輿情監(jiān)控、流量分發(fā)、話題推送、網(wǎng)絡(luò)營銷等領(lǐng)域有重大的應(yīng)用價(jià)值。推特平臺(tái)的話題以Hashtag形式呈現(xiàn)，受到人為干預(yù)程度較低，是流行度預(yù)測(cè)的合適對(duì)象。

已有的流行度預(yù)測(cè)方法的處理對(duì)象集中在消息級(jí)別，而話題級(jí)別的流行度預(yù)測(cè)研究相對(duì)匱乏。同時(shí)，流行度預(yù)測(cè)往往有時(shí)效要求，意味著待預(yù)測(cè)話題的觀測(cè)窗口較小，僅能使用早期極其有限的流行度數(shù)據(jù)。相應(yīng)地，與待預(yù)測(cè)話題同屬一類演化模式的歷史話題經(jīng)歷了完整的生命周期，觀測(cè)窗口較大，流行度數(shù)據(jù)相對(duì)完備。充分利用與待預(yù)測(cè)話題具有相同流行度演化模式的歷史話題數(shù)據(jù)，可以有效彌補(bǔ)待預(yù)測(cè)話題數(shù)據(jù)量較少對(duì)預(yù)測(cè)產(chǎn)生的干擾。已有的研究?jī)H使用待預(yù)測(cè)話題本身的數(shù)據(jù)進(jìn)行預(yù)測(cè)，或者將全部歷史話題納入單一的預(yù)測(cè)模型，忽略了不同歷史話題與待預(yù)測(cè)話題在演化模式的相似程度上存在差異，未充分利用待預(yù)測(cè)話題同屬一類演化模式的歷史話題數(shù)據(jù)，這些不足都影響了預(yù)測(cè)效果。

本文提出了一種基于演化模式的推特話題流行度預(yù)測(cè)方法，先進(jìn)行歷史話題的聚類，得到各類演化模式并訓(xùn)練對(duì)應(yīng)的預(yù)測(cè)模型，然后判斷待預(yù)測(cè)話題的演化模式，最后基于該模式的預(yù)測(cè)模型進(jìn)行流行度預(yù)測(cè)。本文使用小時(shí)內(nèi)與話題相關(guān)的消息發(fā)布數(shù)量作為流行度。為了得到反映大部分推特話題的流行度變化趨勢(shì)且彼此存在明顯差異的一組演化模式，本文基于歷史話題在時(shí)序上完整的流行度序列，采用Yang等［1］提出的?SC（?Spectral Centroid）聚類算法生成各類別的中心作為話題級(jí)別的流行度演化模式，同時(shí)得到每類模式下包含的歷史話題，對(duì)每個(gè)演化模式單獨(dú)訓(xùn)練預(yù)測(cè)模型。對(duì)于待預(yù)測(cè)的話題，本文根據(jù)早期的流行度數(shù)據(jù)進(jìn)行演化模式級(jí)別的分類，以待預(yù)測(cè)話題的已知流行度序列與基于歷史話題數(shù)據(jù)生成的各個(gè)演化模式的序列距離作為分類依據(jù)。考慮到?SC算法只能計(jì)算長(zhǎng)度相等的序列之間的距離，而待預(yù)測(cè)話題的已知流行度序列與基于歷史話題數(shù)據(jù)生成的演化模式是一對(duì)長(zhǎng)度不等的序列，本文提出基于幅度對(duì)齊的動(dòng)態(tài)時(shí)間規(guī)整（Amplitude?Alignment Dynamic Time Warping， AADTW）算法計(jì)算待預(yù)測(cè)話題的已知流行度序列與各演化模式的距離，以與其距離最小的類別下的預(yù)測(cè)模型進(jìn)行流行度預(yù)測(cè)。在實(shí)驗(yàn)中，本文的方法與完全不使用歷史話題數(shù)據(jù)的方法、使用全部歷史話題訓(xùn)練單一預(yù)測(cè)模型的方法分別進(jìn)行了對(duì)比，結(jié)果表明本文方法取得了更優(yōu)的效果。

本文主要工作如下：

1）提出基于演化模式的推特話題流行度預(yù)測(cè)框架。該框架在離線階段挖掘歷史話題的流行度演化模式，并訓(xùn)練對(duì)應(yīng)的預(yù)測(cè)模型；在線階段根據(jù)待預(yù)測(cè)話題的早期數(shù)據(jù)，將其分到演化模式相似的類別中，并使用相應(yīng)的預(yù)測(cè)模型預(yù)測(cè)其流行度。該框架的優(yōu)點(diǎn)是：對(duì)于待預(yù)測(cè)話題，僅需其早期流行度序列作為輸入，無需非時(shí)序數(shù)據(jù)，很好地適應(yīng)了流行度預(yù)測(cè)問題對(duì)時(shí)效性要求，解決了待預(yù)測(cè)話題早期數(shù)據(jù)少的問題。

2）提出基于幅度對(duì)齊的動(dòng)態(tài)時(shí)間規(guī)整（AADTW）算法。樸素的動(dòng)態(tài)時(shí)間規(guī)整（Dynamic Time Warping， DTW）［2］算法雖然提供了變長(zhǎng)序列之間距離的定義，能夠較好地適應(yīng)歷史話題的演化模式與待預(yù)測(cè)話題的已知流行度序列在長(zhǎng)度上存在的差異，但是該距離定義沒有充分強(qiáng)調(diào)一對(duì)序列在時(shí)序上的變化趨勢(shì)的相似程度，會(huì)對(duì)待預(yù)測(cè)話題的演化模式做出錯(cuò)誤的判斷。針對(duì)該問題，本文提出AADTW算法，該算法通過引入?SC算法計(jì)算等長(zhǎng)序列之間的距離時(shí)采用的幅度對(duì)齊思想，并結(jié)合DTW算法處理變長(zhǎng)序列的時(shí)序拉伸思想，更好地解決了判斷待預(yù)測(cè)話題的演化模式這一問題。

1 相關(guān)工作

1.1　消息級(jí)別的流行度預(yù)測(cè)

從消息級(jí)別的流行度預(yù)測(cè)方法中可以發(fā)現(xiàn)，有必要引入消息級(jí)別或話題級(jí)別的相似度計(jì)算方法，據(jù)此對(duì)待預(yù)測(cè)的消息或話題進(jìn)行分類，按類別分別訓(xùn)練預(yù)測(cè)模型，這樣可以對(duì)不同話題進(jìn)行更具針對(duì)性的流行度預(yù)測(cè)，避免噪聲數(shù)據(jù)對(duì)預(yù)測(cè)產(chǎn)生干擾。

1.2　話題級(jí)別的流行度預(yù)測(cè)

話題級(jí)別的流行度預(yù)測(cè)的已有工作相對(duì)較少。Hu等［14］分析了若干突發(fā)話題在社交網(wǎng)絡(luò)的流行度隨時(shí)間變化的周期性，發(fā)現(xiàn)其中包含間隔較短的多個(gè)峰值，提出了一種基于Holt?Winters模型的話題級(jí)別的流行度預(yù)測(cè)方法，僅使用待預(yù)測(cè)話題早期的評(píng)論間隔數(shù)據(jù)。Li等［15］提出了一種基于情感強(qiáng)度的話題級(jí)別流行度預(yù)測(cè)方法，將話題相關(guān)的發(fā)文量作為流行度量化指標(biāo)，對(duì)大量用戶特定話題下消息的情感表達(dá)數(shù)據(jù)和流行度數(shù)據(jù)進(jìn)行特征融合，結(jié)合差分整合移動(dòng)平均自回歸（Auto?Regressive Integrated Moving Average， ARIMA）方法預(yù)測(cè)話題在將來一段時(shí)間的流行度，效果優(yōu)于不引入情感特征的方法。Wang等［16］同樣考慮到情感強(qiáng)度在話題級(jí)別流行度預(yù)測(cè)中的作用，結(jié)合Markov隨機(jī)場(chǎng)對(duì)流行度進(jìn)行預(yù)測(cè)，效果優(yōu)于不引入情感特征的方法。Gupta等［17］設(shè)計(jì)了多個(gè)流行度量化指標(biāo)，根據(jù)文本特征等非時(shí)序特征對(duì)話題進(jìn)行分類，訓(xùn)練多個(gè)模型進(jìn)行預(yù)測(cè)，并驗(yàn)證了指標(biāo)設(shè)計(jì)的合理性。王新樂等［18］使用推特平臺(tái)和微博平臺(tái)的Hashtag的內(nèi)容主題特征、時(shí)間特征、序列特征、用戶粉絲網(wǎng)絡(luò)特征等進(jìn)行基于支持向量機(jī)的主題標(biāo)簽的流行度預(yù)測(cè)，但該方法需要大量的非時(shí)序數(shù)據(jù)支撐，獲取的時(shí)間成本較高。

以往的話題級(jí)別流行度預(yù)測(cè)方法或者忽略了歷史話題數(shù)據(jù)的作用，僅使用待預(yù)測(cè)話題自身的數(shù)據(jù)進(jìn)行預(yù)測(cè)；或者將歷史話題的數(shù)據(jù)集中訓(xùn)練單一預(yù)測(cè)模型，未考慮到某些歷史話題的流行度演化模式與待預(yù)測(cè)話題不同，在訓(xùn)練數(shù)據(jù)中作為干擾噪聲存在，影響預(yù)測(cè)效果，而那些演化模式與待預(yù)測(cè)話題相似的歷史話題卻未被重視；或者考慮到了對(duì)不同類別下的話題分別訓(xùn)練預(yù)測(cè)模型，但是需要大量的非時(shí)序數(shù)據(jù)作為支持，獲取數(shù)據(jù)的時(shí)間成本較高，忽略了預(yù)測(cè)的時(shí)效性要求。

2 本文模型

2.1　問題形式化

2.2　整體預(yù)測(cè)框架

本文方法首先根據(jù)流行度演化模式對(duì)歷史話題進(jìn)行聚類，得到各個(gè)話題類別中心以及歷史話題的類別標(biāo)簽；然后使用每個(gè)話題類別的數(shù)據(jù)訓(xùn)練該類的預(yù)測(cè)模型，各話題類別的預(yù)測(cè)模型構(gòu)成了模型群。對(duì)于每個(gè)待預(yù)測(cè)話題，計(jì)算其早期的流行度序列與各話題類別中心的相似度，將待預(yù)測(cè)話題路由至與其相似度最高的話題類別下的預(yù)測(cè)模型進(jìn)行流行度預(yù)測(cè)。整體框架如圖1所示。

圖1　整體預(yù)測(cè)框架

預(yù)測(cè)框架可以分為以下三個(gè)模塊：

1）歷史話題的聚類模塊：功能為離線挖掘歷史話題的流行度演化模式，并根據(jù)演化模式對(duì)話題進(jìn)行分類。實(shí)際場(chǎng)景中能獲得歷史話題整個(gè)生命周期中的流行度序列，可以設(shè)置較大的觀測(cè)窗口，故各歷史話題序列長(zhǎng)度相等且較大。問題抽象為計(jì)算長(zhǎng)度相等的時(shí)間序列之間的距離，Yang等［1］的工作證明?SC算法可以很好地解決該問題，因此本文基于?SC算法建立此模塊。

2）預(yù)測(cè)話題的分類模塊：功能為根據(jù)待預(yù)測(cè)話題的早期數(shù)據(jù)，判斷話題的演化模式類別。由于觀測(cè)窗口通常較小，因此待預(yù)測(cè)話題的早期流行度序列較短，而歷史話題的聚類模塊得到的各類別中心的序列通常較長(zhǎng)，需要計(jì)算兩個(gè)不等長(zhǎng)序列之間的距離，序列距離是待預(yù)測(cè)話題分類的唯一根據(jù)。問題抽象為計(jì)算長(zhǎng)度存在較大差別的時(shí)間序列之間的距離，且距離定義應(yīng)當(dāng)充分體現(xiàn)序列在演化模式上的差異。DTW算法的序列距離定義較好地適應(yīng)了序列之間長(zhǎng)度不相等的情況，但是受到序列間的幅度差異、演化模式上的差異等諸多因素影響，直接使用該距離定義會(huì)使部分待預(yù)測(cè)話題沒有選擇與其在變化趨勢(shì)上最相似的類別中心作為自身的演化模式，而是錯(cuò)誤地選擇與其在幅度上最接近的類別中心作為自身的演化模式。針對(duì)該問題，本文提出了AADTW算法以建立待預(yù)測(cè)話題分類模塊。

3）預(yù)測(cè)模塊：功能包括兩個(gè)階段，即離線為每個(gè)類別訓(xùn)練預(yù)測(cè)模型，以及在線為待預(yù)測(cè)話題預(yù)測(cè)其流行度。各個(gè)類別的預(yù)測(cè)模型之間結(jié)構(gòu)相同，區(qū)別在于訓(xùn)練數(shù)據(jù)不同導(dǎo)致參數(shù)不同。本文基于全連接神經(jīng)網(wǎng)絡(luò)建立預(yù)測(cè)模塊。

2.3　基于K?SC算法的歷史話題聚類模塊

聚類模塊的輸入是若干歷史話題的流行度序列，聚類算法將在觀測(cè)窗口內(nèi)流行度變化趨勢(shì)相似的歷史話題歸入同一類別，輸出包括：

1）各個(gè)歷史話題所屬的唯一的類別標(biāo)簽，根據(jù)該標(biāo)簽確定每個(gè)類別的預(yù)測(cè)模型的訓(xùn)練集；

2）各個(gè)類別的中心，每個(gè)類別中心代表一類演化模式，要直觀表現(xiàn)類內(nèi)所有流行度序列在變化趨勢(shì)上的共同點(diǎn)，同時(shí)要淡化類內(nèi)不同流行度序列在幅度上的差異。

?SC算法的執(zhí)行流程與K?Means算法類似，是多階段迭代的過程，在每個(gè)階段首先嘗試逐個(gè)更新序列所屬的類別，然后重新計(jì)算各個(gè)類別的中心，直至所有序列的類別保持不變。

K?Means算法將類別內(nèi)全體樣本的均值作為類別中心，不能在時(shí)間序列聚類中沿用，因?yàn)檫@種定義中心的方法與使用歐幾里得距離進(jìn)行相似度計(jì)算的方法一樣，淡化了序列的演化模式，過分強(qiáng)調(diào)序列之間的幅度區(qū)別和細(xì)微延遲引發(fā)的差異。?SC算法設(shè)計(jì)了新的類別中心：

2.4　基于AADTW算法的待預(yù)測(cè)話題分類模塊

此模塊將判斷待預(yù)測(cè)話題的演化模式這一問題轉(zhuǎn)化為多分類問題，以預(yù)測(cè)話題的已知流行度序列與基于歷史話題數(shù)據(jù)生成的各個(gè)演化模式的序列距離作為分類依據(jù)。歷史話題經(jīng)歷了從產(chǎn)生到消亡的完整生命周期，其流行度序列與待預(yù)測(cè)話題早期數(shù)據(jù)構(gòu)建的流行度序列在長(zhǎng)度上存在明顯差異，如何定義和計(jì)算長(zhǎng)度不同的序列之間的距離？針對(duì)該問題，本文提出了一種基于幅度對(duì)齊的動(dòng)態(tài)時(shí)間規(guī)整算法，對(duì)待預(yù)測(cè)話題進(jìn)行演化模式級(jí)別的分類。樸素的DTW算法雖然能夠較好地適應(yīng)序列之間的長(zhǎng)度差異，但直接使用可能會(huì)得到待預(yù)測(cè)序列與趨勢(shì)不同的演化模式存在最小的序列距離，導(dǎo)致分類結(jié)果錯(cuò)誤。

1）狀態(tài)為當(dāng)前取出的兩個(gè)子序列各自的長(zhǎng)度。

2）階段為兩個(gè)子序列的長(zhǎng)度之和。在問題求解的過程中，兩個(gè)子序列的長(zhǎng)度都是單調(diào)不減的，保證了子問題的無后效性。

綜上所述，狀態(tài)轉(zhuǎn)移方程為：

針對(duì)以上問題，引入?SC算法中的伸縮度概念，重新定義不等長(zhǎng)序列之間的距離，提出AADTW算法。

圖2以一個(gè)在觀測(cè)窗口中經(jīng)歷多次流行度峰值的待預(yù)測(cè)話題為例，展示了AADTW算法與DTW算法的區(qū)別。模式A代表在生命周期中經(jīng)歷單個(gè)流行度峰值的一類話題，模式B代表在生命周期中經(jīng)過多個(gè)流行度峰值的一類話題。待預(yù)測(cè)話題的流行度曲線在觀測(cè)窗口內(nèi)已經(jīng)經(jīng)歷一次完整的波峰，并且即將到達(dá)新的波峰，從流行度變化趨勢(shì)的角度應(yīng)當(dāng)歸入模式B。圖2（a）中可以看到模式A與待預(yù)測(cè)話題的流行度曲線逼近程度較高，二者均偏離模式B的曲線，樸素DTW算法計(jì)算出的結(jié)果是模式A與待預(yù)測(cè)話題的距離更接近，會(huì)錯(cuò)誤地將待預(yù)測(cè)話題歸入模式A。圖2（b）中AADTW算法對(duì)模式A進(jìn)行了幅度壓縮，對(duì)模式B進(jìn)行了幅度拉伸，目的均是使二者的曲線盡可能逼近待預(yù)測(cè)話題，經(jīng)過幅度對(duì)齊的處理后，AADTW算法計(jì)算的結(jié)果是待預(yù)測(cè)話題與模式B更接近。

圖2　DTW算法與AADTW算法對(duì)觀測(cè)窗口內(nèi)存在多峰的待預(yù)測(cè)話題進(jìn)行分類時(shí)的區(qū)別

2.5　基于全連接網(wǎng)絡(luò)群的預(yù)測(cè)模塊

本文使用全連接網(wǎng)絡(luò)（Fully Connected Network， FCN）進(jìn)行時(shí)間序列的多步預(yù)測(cè)，網(wǎng)絡(luò)結(jié)構(gòu)包括輸入層、隱藏層、輸出層。其中：輸入層的輸入長(zhǎng)度等于待預(yù)測(cè)話題的觀測(cè)窗口，輸出層的輸出長(zhǎng)度為預(yù)測(cè)窗口。使用每個(gè)話題類別包含的流行度數(shù)據(jù)訓(xùn)練該類別的全連接預(yù)測(cè)網(wǎng)絡(luò)，各類別對(duì)應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)相同，區(qū)別在于參數(shù)，共同構(gòu)成一個(gè)網(wǎng)絡(luò)群，選擇平均絕對(duì)百分比誤差（Mean Absolute Percentage Error， MAPE）作為損失函數(shù)實(shí)驗(yàn)數(shù)據(jù)。

Yang等［1］分析了推特上1 000個(gè)Hashtag從首次出現(xiàn)起各小時(shí)內(nèi)被提及次數(shù)，發(fā)現(xiàn)對(duì)于大部分話題Hashtag，用戶的發(fā)文行為基本集中在前128 h，所以本文設(shè)置采集時(shí)間為128 h。多數(shù)Hashtag在第50 h前后會(huì)經(jīng)歷小時(shí)內(nèi)被提及次數(shù)的峰值，之后的流行度變化幅度明顯小于前50 h內(nèi)，即50 h后話題的傳播規(guī)模趨于穩(wěn)定，從時(shí)效性考慮，觀測(cè)窗口在50 h內(nèi)流行度預(yù)測(cè)更有意義，所以實(shí)驗(yàn)中設(shè)置的觀測(cè)窗口均在50 h以內(nèi)。話題的流行度在20 h內(nèi)基本處于不斷增長(zhǎng)的狀態(tài)，難以從中發(fā)現(xiàn)演化模式的差異，所以實(shí)驗(yàn)中設(shè)置的觀測(cè)窗口至少為20 h。本文采集了推特平臺(tái)上7.5萬個(gè)話題Hashtag前128 h內(nèi)的發(fā)文數(shù)據(jù)，按小時(shí)切分后得到各小時(shí)的發(fā)文量。選取其中90%的話題Hashtag作為訓(xùn)練集，其余10%話題Hashtag作為測(cè)試集。測(cè)試的觀測(cè)窗口分別為20 h、30 h、40 h，預(yù)測(cè)窗口始終為5 h。注意到測(cè)試設(shè)置的觀測(cè)窗口的長(zhǎng)度遠(yuǎn)小于采集數(shù)據(jù)的完整時(shí)間區(qū)間，這是為了模擬實(shí)際預(yù)測(cè)場(chǎng)景下已知待預(yù)測(cè)話題的少量數(shù)據(jù)和各歷史話題的完整時(shí)序數(shù)據(jù)。

3 實(shí)驗(yàn)與結(jié)果分析

3.1　實(shí)驗(yàn)設(shè)置

1）ARIMA模型：僅使用待預(yù)測(cè)話題本身的數(shù)據(jù)進(jìn)行預(yù)測(cè)，完全不使用歷史數(shù)據(jù)。

2）單一的FCN模型：使用全部訓(xùn)練數(shù)據(jù)訓(xùn)練一個(gè)全連接網(wǎng)絡(luò)，所有的測(cè)試數(shù)據(jù)均使用該模型進(jìn)行預(yù)測(cè)。

3）復(fù)用?SC算法建立分類模塊的模型（?SC+FCN）：對(duì)訓(xùn)練數(shù)據(jù)使用?SC算法進(jìn)行聚類后，采取將各話題類別中心進(jìn)行裁剪尾部的處理，保留長(zhǎng)度等于觀測(cè)窗口的前綴，使用?SC算法的距離定義計(jì)算其與測(cè)試數(shù)據(jù)的序列距離，選擇與測(cè)試數(shù)據(jù)距離最小的一類作為測(cè)試數(shù)據(jù)的類別。

4）使用樸素DTW算法建立分類模塊的模型（?SC+DTW+FCN）：對(duì)訓(xùn)練數(shù)據(jù)使用?SC算法進(jìn)行聚類后，使用DTW算法計(jì)算測(cè)試數(shù)據(jù)與各話題類別中心的距離，選擇與測(cè)試數(shù)據(jù)距離最小的一類作為測(cè)試數(shù)據(jù)的類別。

為驗(yàn)證本文方法的穩(wěn)定性，還根據(jù)待預(yù)測(cè)話題的分類結(jié)果，以及流行度預(yù)測(cè)結(jié)果計(jì)算每類演化模式下的MAPE。

3.2　結(jié)果與分析

本文使用MAPE作為預(yù)測(cè)結(jié)果的評(píng)價(jià)指標(biāo)，該指標(biāo)的計(jì)算方法為：

表1　不同模型的MAPE

從表1可以發(fā)現(xiàn)，本文方法（?SC+AADTW+FCN）在各觀測(cè)窗口下均取得了最優(yōu)的效果，下面依次對(duì)各組實(shí)驗(yàn)進(jìn)行分析：

1）ARIMA：ARIMA模型的MAPE始終大于1，預(yù)測(cè)結(jié)果存在嚴(yán)重失真，ARIMA模型僅基于待預(yù)測(cè)話題已有的數(shù)據(jù)進(jìn)行預(yù)測(cè)，而且假設(shè)序列具有周期性，實(shí)際上話題傳播的演化模式并不具有明顯的周期性，違背了ARIMA的假設(shè)。驗(yàn)證了在觀測(cè)窗口較小的情況下，僅使用待預(yù)測(cè)話題的已知流行度對(duì)后續(xù)流行度預(yù)測(cè)難以取得理想效果。

2）FCN：一方面，F(xiàn)CN模型相較于ARIMA有明顯的性能提升，驗(yàn)證了引入歷史話題數(shù)據(jù)的必要性；另一方面，F(xiàn)CN模型的表現(xiàn)相較于使用?SC算法進(jìn)行歷史話題聚類的后兩種方法存在差距。使用單一預(yù)測(cè)模型實(shí)際上將所有歷史話題的數(shù)據(jù)置于同等的地位，沒有發(fā)現(xiàn)歷史話題流行度演化模式存在的明顯差異，與待預(yù)測(cè)話題的演化模式不同的歷史話題成為噪聲，對(duì)預(yù)測(cè)形成干擾。這說明引入?SC算法可以發(fā)現(xiàn)相似話題，歷史的相似話題在流行度預(yù)測(cè)中發(fā)揮重要作用。

3）?SC+FCN：使用KSC算法同時(shí)完成歷史話題聚類和待預(yù)測(cè)話題分類的方法，其預(yù)測(cè)效果隨著觀測(cè)窗口增大有最明顯提升，驗(yàn)證了KSC算法能起到過濾歷史話題數(shù)據(jù)、保留演化模式與待預(yù)測(cè)話題相似的歷史話題的作用。

4）?SC+DTW+FCN：一方面，在待預(yù)測(cè)話題分類模塊使用樸素DTW算法使得預(yù)測(cè)效果相較于使用?SC算法有了進(jìn)一步的提升，驗(yàn)證了DTW算法能夠更好地量化長(zhǎng)度存在明顯差異的時(shí)間序列之間的相似程度。另一方面，相較于上一種方法（?SC+FCN）的預(yù)測(cè)效果提升程度隨著觀測(cè)窗口增大不斷縮小。這是因?yàn)槲墨I(xiàn)［1］發(fā)現(xiàn)推特話題的流行度演化模式在話題首次出現(xiàn)后接近50 h基本可被確定，而本文設(shè)置的觀測(cè)窗口越來越接近50 h。換言之，越是在話題出現(xiàn)的早期，觀測(cè)窗口越小，DTW算法相較于?SC算法在待預(yù)測(cè)話題分類任務(wù)上的優(yōu)勢(shì)越明顯。

5）?SC+AADTW+FC：本文提出的AADTW算法在計(jì)算序列之間的距離時(shí)同時(shí)具備?SC算法抵消序列之間的幅度差異，以及DTW算法適應(yīng)序列之間長(zhǎng)度差異的特點(diǎn)，使得序列之間演化模式的相似程度成為影響序列距離的主要因素，在流行度預(yù)測(cè)問題上充分利用了歷史話題的演化模式?；贏ADTW算法建立待預(yù)測(cè)話題分類模塊，相較于使用樸素DTW算法進(jìn)一步提高了預(yù)測(cè)效果。與ARIMA和FCN相比，本文方法的MAPE分別降低了58.2%和31.0%

本文還根據(jù)待預(yù)測(cè)話題的分類結(jié)果，以及流行度預(yù)測(cè)結(jié)果計(jì)算每類演化模式下的MAPE，結(jié)果見表2?？梢园l(fā)現(xiàn)，在每個(gè)觀測(cè)窗口下，每類演化模式的MAPE與測(cè)試集整體的MAPE十分接近，表明本文的方法對(duì)不同的待預(yù)測(cè)話題進(jìn)行預(yù)測(cè)時(shí)具有穩(wěn)定的表現(xiàn)。

表2　不同演化模式的MAPE

4 結(jié)語

話題級(jí)別的流行度預(yù)測(cè)問題有時(shí)效要求，在話題出現(xiàn)早期存在流行度數(shù)據(jù)不足的問題，歷史話題的數(shù)據(jù)相對(duì)完備，考慮使用與待預(yù)測(cè)話題的流行度演化模式相似的歷史話題數(shù)據(jù)提高預(yù)測(cè)效果。本文提出一種基于演化模式相似的歷史話題進(jìn)行流行度預(yù)測(cè)的方法。通過一系列的對(duì)比試驗(yàn)，驗(yàn)證了該方法的有效性。本文方法與完全基于待預(yù)測(cè)話題自身數(shù)據(jù)的ARIMA模型相比，驗(yàn)證了引入歷史數(shù)據(jù)可以顯著降低早期流行度預(yù)測(cè)的誤差；與使用全部歷史話題數(shù)據(jù)訓(xùn)練單一預(yù)測(cè)模型的方法對(duì)比，驗(yàn)證了引入?SC聚類算法可以有效過濾對(duì)預(yù)測(cè)任務(wù)產(chǎn)生干擾的歷史事件；與使用?SC算法做待預(yù)測(cè)話題分類的方法對(duì)比，驗(yàn)證了在話題出現(xiàn)早期數(shù)據(jù)不足的情況下，引入DTW算法可以明顯提高待預(yù)測(cè)話題分類效果；與使用樸素DTW算法進(jìn)行待預(yù)測(cè)話題分類的方法對(duì)比，驗(yàn)證了AADTW算法相較DTW算法能更好地判斷待預(yù)測(cè)話題的演化模式，進(jìn)而提高預(yù)測(cè)效果。本文計(jì)算了每類演化模式下的MAPE，驗(yàn)證了方法的穩(wěn)定性。

在本文的流行度預(yù)測(cè)方法中，僅使用了話題的部分時(shí)序特征，未來可以考慮結(jié)合話題的非時(shí)序特征，例如話題的情感色彩等。在計(jì)算時(shí)間序列之間的變化趨勢(shì)的相似度問題上，可以考慮使用其他的幅度對(duì)齊方法，或者使用其他的計(jì)算變長(zhǎng)序列距離的算法以更好地解決問題。

[1] YANG J， LESKOVEC J. Patterns of temporal variation in online media［C］// Proceedings of the 4th ACM International Conference on Web Search and Web Data Mining. New York： ACM， 2011：177-186.

[2] BERNDT D J， CLIFFORD J. Using dynamic time warping to find patterns in time series［C］// Proceedings of the 1994 AAAI Conference on Knowledge Discovery and Data Mining. Menlo Park， CA： AAAI Press， 1994：359-370.

[3] SZABO G， HUBERMAN B A. Predicting the popularity of online content［J］. Communication of the ACM， 2010， 53（8）：80-88.

[4] 朱海龍，云曉春，韓志帥. 基于傳播加速度的微博流行度預(yù)測(cè)方法［J］. 計(jì)算機(jī)研究與發(fā)展， 2018， 55（6）：1282-1293.（ZHU H L， YUN X C， HAN Z S. Weibo popularity prediction method based on propagation acceleration［J］. Journal of Computer Research and Development， 2018， 55（6）：1282-1293.）

[5] BAO P， SHEN H W， HUANG J M， et al. Popularity prediction in microblogging network： a case study on Sina Weibo［C］// Proceedings of the 22nd International Conference on World Wide Web. New York： ACM， 2013：177-178.

[6] 高金華，沈華偉，程學(xué)旗，等. 基于相似消息的流行度預(yù)測(cè)方法［J］. 中文信息學(xué)報(bào)， 2018， 32（11）：79-85.（GAO J H， SHEN H W， CHENG X Q， et al. Popularity prediction method based on similar historical tweets［J］ Journal of Chinese Information Processing， 2018， 32（11）：79-85.）

[7] WANG X M， FANG B X， ZHANG H L， et al. Predicting the popularity of news based on competitive matrix［C］// Proceedings of the IEEE 2nd International Conference on Data Science in Cyberspace. Piscataway： IEEE， 2017：151-155.

[8] AHMED M， SPAGNA S， HUICI F， et al. A peek into the future： predicting the evolution of popularity in user generated content［C］// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York： ACM， 2013：607-616.

[9] LYMPEROPOULOS I N. RC?Tweet： modeling and predicting the popularity of tweets through the dynamics of a capacitor［J］. Expert Systems with Applications， 2021， 163： No.113785.

[10] TSAGKIAS M， WEERKAMP W， DE RIJKE M. Predicting the volume of comments on online news stories［C］// Proceedings of the 18th ACM Conference on Information and Knowledge Management. New York： ACM， 2009：1765-1768.

[11] FIGUEIREDO F， BENEVENUTO F， ALMEIDA J. The tube over time： characterizing popularity growth of YouTube videos［C］// Proceedings of the 4th ACM International Conference on Web Search and Web Data Mining. New York： ACM， 2011：745-754.

[12] 鐘志豪，肖井華，吳曄，等. 基于抖音平臺(tái)的在線短視頻流行度建模研究［J］. 電子科技大學(xué)學(xué)報(bào)， 2021， 50（5）：774-781.（ZHONG Z H， XIAO J H， WU Y， et al. Modeling dynamics of online short video popularity based on Douyin platform［J］. Journal of University of Electronic Science and Technology of China， 2021， 50（5）：774-781.）

[13] GAO X F， ZHENG Z W， CHU Q Q， et al. Popularity prediction for single tweet based on heterogeneous Bass model［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 33（5）：2165-2178.

[14] HU Y， HU C J， FU S S， et al. Predicting the popularity of viral topics based on time series forecasting［J］. Neurocomputing， 2016， 210：55-65.

[15] LI J N， GAO Y R， GAO X F， et al. SENTI2POP： sentiment? aware topic popularity prediction on social media［C］// Proceedings of the 2019 IEEE International Conference on Data Mining. Piscataway： IEEE， 2019： 1174-1179.

[16] WANG X， WANG C， DING Z Y， et al. Predicting the popularity of topics based on user sentiment in microblogging websites［J］. Journal of Intelligent Information Systems， 2018， 51（1）： 97-114.

[17] GUPTA M， GAO J， ZHAI C X， et al. Predicting future popularity trend of events in microblogging platforms［J］. Proceedings of the American Society for Information Science and Technology， 2012， 49（1）：1-10.

[18] 王新樂，楊文峰，廖華明，等. 基于多維度特征的主題標(biāo)簽流行度預(yù)測(cè)［J］. 山東大學(xué)學(xué)報(bào)（理學(xué)版）， 2020， 55（1）：94-101.（WANG X L， YANG W F， LIAO H M， et al. Popularity prediction of hashtags based on multi?dimensional features［J］. Journal of Shandong University （Natural Science）， 2020， 55（1）：94-101.）

[19] MATSUBARA Y， SAKURAI Y， PRAKASH B A， et al. Rise and fall patterns of information diffusion： model and implications［C］// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2012： 6-14.

Popularity prediction method of Twitter topics based on evolution patterns

XIE Weifan1，2， GUO Yan1*， KUANG Guangsheng1，3， YU Zhihua1， XUE Yuanhai1， SHEN Huawei1

（1，，，100190，；2，，101408，；3，，101408，）

A popularity prediction method of Twitter topics based on evolution patterns was proposed to address the problem that the differences between evolution patterns and the time?effectiveness of prediction were not taken into account in previous popularity prediction methods. Firstly， the?SC （?Spectral Centroid） algorithm was used to cluster the popularity sequences of a large number of historical topics， and 6 evolution patterns were obtained. Then， a Fully Connected Network （FCN） was trained as the prediction model by using historical topic data of each evolution pattern. Finally， in order to select the prediction model for the topic to be predicted， Amplitude?Alignment Dynamic Time Warping （AADTW） algorithm was proposed to calculate the similarity between the known popularity sequence of the topic to be predicted and each evolution pattern， and the prediction model of the evolution pattern with the highest similarity was selected to predict the popularity. In the task of predicting the popularity of the next 5 hours based on the known popularity of the first 20 hours， the Mean Absolute Percentage Error （MAPE） of the prediction results of the proposed method was reduced by 58.2% and 31.0% respectively， compared with those of the Auto?Regressive Integrated Moving Average （ARIMA） method and method using a single fully connected network. Experimental results show that the model group based on the evolution patterns can predict the popularity of Twitter topic more accurately than single model.

Twitter topic; evolution pattern; popularity prediction; social network; time series

This work is partially supported by National Natural Science Foundation of China （U21B2046）.

XIE Weifan， born in 1997， M. S. candidate. His research interests include popularity prediction.

GUO Yan， born in 1974， Ph. D.， senior engineer. Her research interests include network information acquisition， network content processing.

KUANG Guangsheng， born in 1995， M. S. candidate. His research interests include natural language processing， data fusion.

YU Zhihua， born in 1973， Ph. D.， chief senior engineer. His research interests include internet public opinion analysis.

XUE Yuanhai， born in 1987， Ph. D.， senior engineer. His research interests include information retrieval， big data.

SHEN Huawei， born in 1982， Ph. D.， research fellow. His research interests include social computing， data mining， machine learning.

TP181

A

1001-9081（2022）11-3364-07

10.11772/j.issn.1001-9081.2022010045

2022?01?17；

2022?03?03；

2022?03?07。

國家自然科學(xué)基金資助項(xiàng)目（U21B2046）。

解偉凡（1997—），男，山西運(yùn)城人，碩士研究生，主要研究方向：流行度預(yù)測(cè)；郭巖（1974—），女，陜西西安人，高級(jí)工程師，博士，主要研究方向：網(wǎng)絡(luò)信息獲取、網(wǎng)絡(luò)內(nèi)容處理；匡廣生（1995—），男，江西贛州人，碩士研究生，主要研究方向：自然語言處理、數(shù)據(jù)融合；余智華（1973—），男，江西吉安人，正高級(jí)工程師，博士，主要研究方向：網(wǎng)絡(luò)輿情分析；薛源海（1987—），男，云南玉溪人，高級(jí)工程師，博士，主要研究方向：信息檢索、大數(shù)據(jù)；沈華偉（1982—），男，河南周口人，研究員，博士，主要研究方向：社會(huì)計(jì)算、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)。