基于流量時間序列的社交網絡事件聚類分析

劉 靜， 張 鴿

（山西農業大學軟件學院， 山西 太谷 030801）

0 引 言

社交網絡是一個用戶可以即時發布內容、分享信息并與他人進行交流互動的互聯網平臺，例如微博、推特等平臺。 社交網絡上每時每刻都會產生用戶發布的大量內容，表現出豐富的時間動態性。 由于社交網絡中個體用戶行為難以預測，因此分析用戶行為非常復雜。 但一些研究表明，互聯網在線內容的流量模式可以反映群體用戶的行為［1-2］。 事件隨時間變化的流量時間序列可以顯示出用戶群體何時對事件產生關注度，以及關注度如何隨時間增長消退的變化模式。 對于某種類型的事件，群體用戶的流量時間序列往往會形成一些特定的規律。

現有研究大多根據社交網絡中的流量模式分析用戶的行為，文獻［3］根據用戶在電商平臺購買及評論的時間序列分析用戶的消費行為習慣；文獻［4］通過用戶行為的時間序列分析來檢測社交網絡中的欺詐行為。 而本文旨在利用事件的流量模式對事件進行聚類分析。 具有共性特征的事件可能會呈現出相似的流量時間序列，可以根據事件的流量時間序列對事件進行聚類，找到事件的共性特征。 Kmeans 算法是聚類領域最常使用的聚類算法，該算法通過在每次迭代中交替執行簇分配步驟和簇中心更新步驟，來最小化簇內樣本到簇中心的距離平方，以找到最終的簇劃分結果［5］。 但該算法通常運用在數值型數據上，無法在時間序列數據上體現出數據的時序性；K-SC 算法是一種在K-means 算法基礎上改進的，針對時間序列數據進行聚類的算法，用來揭示在線內容時間動態性的規律［6］。 該算法與K-means算法流程相同，都是交替執行簇分配步驟和簇中心更新步驟，只不過根據時間序列數據的特點重新定義了距離和簇中心。 本文利用K-SC 算法對社交網絡上熱門事件的流量時間序列進行聚類分析，發現具有相似流量模式的事件的共同特征，并分析同類事件流量時間序列的共同特點。 首先需要獲得事件的流量時間序列，而確定事件的主題標簽是獲得事件流量時間序列的關鍵，本文利用皮爾遜相關系數來確定事件的主題標簽，利用事件的主題標簽每隔固定時間檢索出包含該主題標簽的推文，并計算推文數量，該數量形成的序列即為該事件的流量時間序列。 然后就可以利用K-SC 算法對多個事件的流量時間序列進行聚類，找到具有相似時間序列形狀的事件，并分析其共性特征。

利用推特上2020 東京奧運會期間場地自行車比賽事件的推文數據進行實驗，獲取事件的流量時間序列，并對其進行聚類分析，驗證了本文方法可以對基于流量時間序列的社交網絡事件進行有效聚類，從而發現同類事件的共性特征。

1 方法描述

1.1 獲取事件的主題標簽

社交網絡平臺上的事件是用主題標簽來確定的，因此找到每個事件的主題標簽是檢測事件流量模式的關鍵。 首先，根據事件最關鍵的主題標簽獲取包含該主題標簽的推文；然后，查看這些推文中包含其他哪些主題標簽，并將所有主題標簽保存到一個初始標簽池H中，記為H＝ ｛H1，H2，H3， …，Hn｝，其中n為當前主題標簽的個數。 然而，并非H中的所有主題標簽都能直接與某個特定事件相關聯，因此使用皮爾遜相關系數對H中的主題標簽進行重新檢查。 首先，從H中選擇那些必定與事件相關的主題標簽，如事件的名稱，并將其保存到標簽池R中，且R∈H；然后為了確定H中的各個主題標簽是否與事件相關，需要將其逐個與R中的主題標簽進行比較，計算H中每個主題標簽與R之間的皮爾遜相關系數。 如果相關性大于某個閾值，則來自H中的某個主題標簽被認為是與事件相關的，并保留在H中；如果相關性小于閾值，則將其從H中刪除。 計算了相關性后， 最終的H＝｛H1，H2，H3，…，Hm｝（其中m≤n）被視為事件的主題標簽。

1.2 創建事件的流量時間序列

獲取到每個事件的主題標簽H后，就可以根據主題標簽來計算事件流量隨時間變化的流量時間序列。 每隔一定時間t，包含H的推文總量被認為是該事件的流量，但在H中可能會存在一些噪聲主題標簽與H中真正的主題標簽非常相似但又不屬于該主題。 為了減少噪聲，需要確保那些包含與H相似的噪聲主題標簽的推文不被收集。 首先按照目標時間間隔查詢數據庫，收集與H相似但不包含在H中的主題標簽，結果集記為h；然后，在目標時間間隔t上選擇包含H但不包含h的推文，記錄每隔t分鐘的推文數量， 該事件即可獲得一個離散的時間序列Ei（mt）（其中m＝1，2，3，…，M，M為時間序列的長度），即事件i在以t為時間間隔的mt時刻上被提及的次數，這個離散的時間序列即為事件的流量時間序列。

1.3 利用流量時間序列對事件進行聚類

獲取了社交網絡中事件的流量時間序列后，根據流量時間序列對事件進行聚類。 本文利用經典的K-SC 算法對事件的時間序列進行聚類。 K-SC 算法通過在每次迭代中交替執行兩個步驟，即簇分配步驟和簇中心更新步驟，來最小化簇內樣本到簇中心的距離平方和，即式（1）：

其中，K為簇的個數；Ck為第k個簇的樣本集合；d（Ei，μk） 為時間序列Ei到簇中心μk的距離。

K-SC 算法將時間序列樣本到簇中心的距離定義為式（2）：

其中，αi為用于匹配兩個時間序列形狀的縮放系數，Ei（qi）為將時間序列Ei平移qi個時間單位的結果，使得Ei和μk在相同的時間達到峰值。

在K-SC 的算法流程中，首先隨機選擇K個初始樣本作為簇中心；在簇分配步驟中，將每個樣本分配到與簇中心距離最近的簇；在簇中心更新步驟中，新的簇中心應該使得對于所有樣本的d（Ei，μk）的和最小，即式（3）：

經過推導可得出公式（4）：

其中：

因此求解等價于求解矩陣M的最小特征向量。 根據上述迭代步驟，K-SC 的算法流程見算法1。

算法1K-SC 聚類算法

輸入時間序列Ei，i＝1，2，…，N；簇個數K；初始簇中心μk，k＝1，2，…，K

重復

直到L不變

輸出C，μ1，…，μK

2 實驗分析

2.1 數據集

實驗采用推特上2020 東京奧運會的數據，創建比賽事件的流量時間序列，并對事件進行聚類分析，找到同類事件的一般特性。 本文實驗通過推特流媒體API 獲取本屆奧運會期間與場地自行車決賽項目相關的公開推文，對表1 中的8 項場地自行車比賽事件的流量時間序列進行聚類。 首先，獲取各事件的初始主題標簽，其中將“比賽名稱”和“獲勝者名字”視為最關鍵的主題標簽；然后，獲取各事件最終的主題標簽，其中皮爾遜相關系數的閾值設定為0.8；最后，創建各事件的流量時間序列，將時間間隔t設置為5 min，并為各事件的時間序列選取合理且相同長度的時間區間。

表1 本實驗選取的場地自行車比賽名稱Tab. 1 Names of the selected track cycling races in this experiment

2.2 確定簇的個數

對事件進行聚類前，首先需要確定簇的個數。本實驗在不同的簇個數（即令K＝1，2，3，4，5，6）下執行K-SC 算法，得到目標函數值L（即距離平方和）收斂后的值，目標函數L的值隨簇個數K的變化如圖1 所示。 從圖1 中可以看出，在K＝3 后，目標函數值的下降率變得平緩，簇個數對聚類目標值影響不大，因此將簇的個數設置為3。

圖1 目標函數L 的值隨簇個數K 的變化Fig. 1 The change of the value of objective function L with respect to the number of clusters K

2.3 聚類結果分析

獲取了場地自行車比賽事件的流量時間序列并確定了簇的個數后，用基于時間序列的K-SC 算法對事件進行聚類。 聚類結果見表2，可以看出這些比賽事件基本按照是否為團體項目被劃分開；每個簇中每個事件的流量時序折線圖如圖2 所示，可以看出除了簇2 中事件的時間序列形狀較為特殊之外，團體項目和個人項目顯示出不同的時間序列形狀。 簇1 中的團體項目事件都只有一個明顯較高的峰值，而簇3 中的個人項目（男子或女子非團體項目）事件都顯示出兩個明顯的峰值。 實驗結果表明，聚類結果中同一類事件具有明顯的共性特征，并且顯示出類似的流量時序模式，從而驗證了K-SC 算法對于基于流量時間序列的社交網絡事件聚類的有效性。

圖2 每個簇中比賽事件的流量時序折線圖Fig. 2 Line graphs of the traffic time series for events within each cluster

表2 基于流量時間序列的場地自行車比賽事件聚類結果Tab. 2 Clustering results of track cycling events based on traffic time series

3 結束語

社交網絡上用戶實時生成的在線數據表現出豐富的時間動態性，但一些具有共性特征的事件可能會呈現出相似的流量模式。 本文根據事件的流量時間序列對事件進行聚類，找到事件的共性特征。 首先，利用皮爾遜相關系數來確定各事件的主題標簽；然后，利用各事件的主題標簽獲得各事件的流量時間序列；最后，利用K-SC 聚類算法對多個事件的流量時間序列進行聚類，發現同類事件的共性特征。利用推特上2020 東京奧運會期間場地自行車比賽事件的推文數據驗證了本文方法可以對基于流量時間序列的社交網絡事件有效聚類，從而發現同類事件的共性特征。