基于并行關聯規則的話題演化跟蹤方法

王奕文，張如玉，劉 昕，張瓊聲，田紅磊，曹 帥

(中國石油大學(華東)計算機與通信工程學院，山東 青島 266580)

0 引 言

近年來，借助時序信息實時跟蹤話題的動態演化趨勢的研究方法主要包括以下兩種[1-3]。第一種方法把文本的時間信息當作其話題屬性參與到特征計算的過程中，建立動態演變的話題模型。例如：徐會杰等引入回復加速度實現對突發性熱點話題快速發現與跟蹤[4]；趙旭劍等建立了增量式計算模型，該模型考慮了話題特征，能很好地挖掘出新聞話題演化各個階段的信息[5]。第二種方法將時間信息與概率話題模型結合，通過計算時間信息與話題、文檔、詞項的概率分布，實現對潛在話題的生成與演變過程的追蹤[6-8]。例如：Kalyanam等提出一種基于社交情景信息的話題演化模型[9]；陳興蜀等提出一種基于OLDA的熱點話題演化跟蹤模型[10]；王奕文等對關聯規則算法進行了改進，并將其應用于熱點事件時序分析中[11,12]。

目前，在話題的動態演變跟蹤領域，各種話題模型均能夠很好地考慮到話題結構與演化的特征，但是大部分研究采用相似度來衡量不同話題內容的相關程度，很少考慮各階段話題關鍵詞的關聯關系在話題演變過程中的影響。

為了解決上述問題，本文引入時間窗口和關聯規則[13,14]，提出一種基于并行關聯規則的話題演化跟蹤方法。該算法有兩個優點，一是提高了計算效率，縮短了關聯規則算法尋找頻繁項集所需的時間，能夠更快地發現數據之間隱藏關系；二是結合時間信息與關聯規則能夠發現關鍵詞在話題演化過程中隨時間推移的潛在關聯關系，從而深度分析話題演化的具體細節。

1 基本概念

本文提出的基于并行關聯規則的話題演化跟蹤方法涉及到以下相關概念。

定義1支持度(support)。一個關鍵詞集在數據集中出現的頻率。支持度越高代表著該關鍵詞集出現的頻率越高、熱度越大，說明規則越有用。支持度的計算公式為

(1)

關聯規則是形如a?b的蘊含式。s(a?b)為{a,b}這個關鍵詞集的支持度；P(a∪b)為數據集中事件a,b同時發生的概率(0≤P(a∪b)≤1)；n(a∪b)為數據集中事件a,b同時發生的次數；n(dataset)為數據集中記錄的總條數。

定義2置信度(confidence)。在事件a發生的集合中，事件b發生的概率。置信度衡量了關鍵詞集中各關鍵詞的關聯關系強弱，置信度的值越大說明其對應的關聯規則越可信。置信度的計算公式為

(2)

c(a?b)為關鍵詞集的置信度；P(b|a)為在數據集中關鍵詞集{a}發生的情況下關鍵詞集{a,b}也同時發生的條件概率(0≤P(b|a)≤1)。

定義3k_項頻繁關鍵詞集。包括k個頻繁關鍵詞的集合，其中每個頻繁關鍵詞的支持度均大于等于支持度閾值。lk[i]={wx[i]}表示第i個k_項頻繁關鍵詞集，其中的第x個關鍵詞表示為wx[i]，(x=1,2,…,k)。則Lk={lk[i]}為由全部lk[i]組成的集合，(i=1,2,…,t)，t為Lk中包含的k_項頻繁關鍵詞集的數目。

定義4關聯規則集。關聯規則集由置信度數值不小于設定閾值的關聯規則構成。如果蘊含式a[y]?b[y]代表第y個關聯規則，那么關聯規則集則表示為Rules={a[y]?b[y]}，(y=1,2,…,r)，r為該關聯規則集中包含的關聯規則數目。

2 并行關聯規則的基本流程

為了提高計算效率，本文將頻繁關鍵詞集的獲取任務分為N個獲取頻繁關鍵詞子集的子任務。首先對時間窗口的大小進行設置，并將數據集中的文本數據按照時序信息劃分到不同窗口中來；然后獲取各時間窗口對應的一項頻繁項集L1；最后使用并行關聯規則算法獲取各個時間窗口對應的關聯規則集，具體流程如圖1所示。在已經獲取的L1基礎上，進行任務分配并實現Lk-1到Lk的迭代，任務合并形成全局Lk，在此基礎上獲得關聯規則集；最后通過對所有時間窗口的關聯規則集進行篩選和組合形成不同時間話題關鍵詞。

圖1 單個時間窗口的并行關聯規則算法流程

2.1 1_項頻繁關鍵詞集獲取

k_項頻繁關鍵詞集是在已知1_項頻繁關鍵詞集L1的基礎上計算得出的，1_項頻繁關鍵詞集L1的獲取分為3個步驟：

(1)因為各社交網站的話題信息均使用設定的TOP關鍵詞進行收集，因此我們把各TOP關鍵詞作為1_項頻繁關鍵詞集L1的候選關鍵詞。

(2)從各社交網絡頁面上收集的數據根據時序信息劃分到不同時間窗口中，形成不同的數據集。在各時間窗口對應的數據集中，統計各TOP關鍵詞出現的次數，記為n(top[i])。由支持度的計算公式知，TOP關鍵詞的支持度s_top[i]為

(3)

(3)設置支持度閾值s_min。若s_min≤s_top[i]，則將s_top[i]對應的TOP關鍵詞保留，記為l1[j]；反之舍棄。由此得到L1={l1[j]}，j≤i。

2.2 k_項頻繁關鍵詞集獲取

k_項頻繁關鍵詞集Lk由L1與Lk-1進行合并操作得到。Lk的獲得分為5個步驟：

(1)對Lk-1進行數據分割成N個互不交叉的子集，每個k-1_項頻繁關鍵詞子集分配給一個子任務。

(2)將各子任務的Lk-1與L1進行合并操作，得到k_項關鍵詞集。該k_項關鍵詞集為Lk的候選關鍵詞集之一，第i個k_項關鍵詞集記作k_keywords[i]。

(3)在時間窗口對應的文本數據集中，對各k_項關鍵詞集出現的次數進行匯總，記作n(k_keywords[i])。由支持度計算公式知，k_項關鍵詞集的支持度s_k_keywords[i]為

(4)

(4)當s_min≤s_k_keywords[i]時，則將s_k_keywords[i]對應的k_項關鍵詞合并入Lk，并記為lk[j]。則Lk={lk[j]}，j≤i。

(5)將各個子任務得到的Lk進行合并與刪減操作，得到全局Lk。

2.3 形成關聯規則集

在上一步得到的全局Lk基礎上通過計算得到關聯規則集，關聯規則集的獲得分為4個步驟：

(1)獲取每個Lk中k_項頻繁關鍵詞集的關聯規則，每個k_項頻繁關鍵詞集能產生的關聯規則數目均不少于1。定義由第i個k_項頻繁關鍵詞集lk[i]中的s個關鍵詞組成的關鍵詞集為lk[i[s]](1≤s≤k)，由lk[i]中去掉s個關鍵詞后的k-s個關鍵詞組成的關鍵詞集為lk[i[k-s]]。

(2)計算關聯規則的置信度。若將lk[i]的支持度表示為公式s_lk[i]，則lk[i[s]]的支持度可表示為s_lk[i[s]]。由式(2)可知，關聯規則lk[i[s]]?lk[i[k-s]]的置信度為

(5)

(3)篩選關聯規則。c_min為設定的置信度閾值，如果c_min≤c(lk[i[s]]?lk[i[k-s]])，則關聯規則lk[i[s]]?lk[i[k-s]]被保留，反之，對應的關聯規則lk[i[s]]?lk[i[k-s]]被舍棄。

(4)將步驟(3)篩選出來的關聯規則進行合并和約簡操作，得到關聯規則集。

3 話題演化跟蹤方法

算法1：基于并行關聯規則的話題演化跟蹤算法

輸入：從各個社交網站上爬取的所有與待分析事件有關的文本數據

輸出：各時間段對應的話題關鍵詞

(1)從各社交網絡頁面上獲得的數據根據時序信息劃分到不同時間窗口中，形成不同的數據集。

(2)在各時間窗口的文本數據集中，對各TOP關鍵詞出現的次數進行匯總，支持度大于s_min的TOP關鍵詞作為1_項頻繁關鍵詞集L1，此時k=1。

(3)令k=k+1，將集合Lk-1分為N個互不相交的k-1_項頻繁關鍵詞子集，并為每個子集設定一個獨立子任務，將各子任務的Lk-1與所有的L1進行合并操作，各子任務獨立生成滿足支持度閾值s_min的Lk。

(4)將N個子任務獲得的Lk結果合并后去重，得到全局Lk。

(5)迭代進行步驟(3)和步驟(4)，當得到的k+1_項關鍵詞集合為空時停止迭代，將頻繁關鍵詞集存在的最大項集數記作n。

(6)在全局Lk(2≤k≤n)基礎上通過計算得到滿足置信度閾值c_min的關聯規則，對獲得的所有關聯規則合并并刪減，得到關聯規則集。

(7)通過以上6個步驟得到全部時間窗口對應的關聯規則集，通過對關聯規則集進行篩選與組合操作，得到各時間段對應的話題關鍵詞。

4 實 驗

4.1 實驗數據

本文用到的實驗數據均通過網絡爬蟲技術爬取獲得，設定關鍵詞“華為，犯罪，孟晚舟”，從新浪微博收集時間范圍為2020年1月20日到2020年6月6日的輿情數據，共收集到36 245條相關的言論，日均230條左右。本文使用Ansj技術從收集到的微博言論中挖掘關鍵詞，從同一條微博言論中挖掘到的關鍵詞彼此互不相同，從不同的微博言論中挖掘到的關鍵詞數量也互不相同。

4.2 參數設置及實驗結果

4.2.1 支持度閾值設置

關聯規則集在1_項頻繁關鍵詞集L1的基礎上獲得，L1中的關鍵詞將會對整個話題演化跟蹤的準確率產生影響，因此支持度閾值的設定尤為重要。恰當的支持度閾值可以使算法獲取到各時間窗口對應的盡可能多的高價值關鍵詞，對2020年1月20日的數據設置不同的支持度閾值，得到不同的L1見表1。

表1 不同支持度下的L1結果

支持度設置為14.6%～14.9%時，L1包括當前時間窗口全部有價值的關鍵詞信息；支持度設置為14%時，L1不僅包括當前時間窗口全部有價值的關鍵詞信息，還包括一些與事件主題無關的信息，如“彈劾、港股、英特爾、洛桑、冬奧”；支持度設置為15.0%時，篩選出的關鍵詞數目較少，部分較為重要的關鍵詞信息被漏掉，如“伊朗 欺詐 制裁 律師”，無法通過挖掘到的關鍵詞信息獲得事件起因。由分析可知當前時間窗口的支持度閾值設置為14.6%，使用以上方式獲取所有時間窗口的支持度閾值。

4.2.2 置信度閾值設置

話題相關的關鍵詞信息在已有關聯規則集的基礎上獲得，關聯規則集中的關聯規則會對話題演化跟蹤的結果造成巨大影響，而關聯規則集中的關聯規則又受到置信度閾值的直接影響。故此處將時間窗口設為1天，使用該時間 窗口對應的包含約230條微博言論或新聞報道的數據集，對支持度、置信度閾值與新聞報道的數目之間的關系進行分析，如圖2所示。

圖2 支持度閾值與置信度閾值關系趨勢

由圖2可知，數據點集中分布在s_min∈[12%，19%]，c_min∈[85%，93%]區間范圍內。即，當微博言論約230條時，支持度與置信度閾值有較大幾率落在以上區間內。因支持度閾值較大時，關聯規則算法會將一些重要的話題相關關鍵詞信息過濾掉；支持度閾值較小時，則會獲取到大量的冗余話題相關關鍵詞，比如：當s_min=14.4%時，c_min=89.9%；當s_min=14.2%時，c_min=91.0%。所以，在微博言論的數目已經確定的前提下，設定的置信度閾值整體上會隨著設定的支持度閾值的升高表現出下降的趨勢。

4.3 熱點跟蹤實驗及結果

本實驗將時間窗口設為1天，圖3為各時間窗口使用并行關聯規則算法獲取的部分關聯規則集結果。

1月20日……孟晚舟 華為 聽證會->引渡 中國孟晚舟 法庭 聽證會->引渡 華為 溫哥華加拿大 犯罪 法庭->引渡 美國 孟晚舟 雙重孟晚舟 聽證會 中方 耿爽 回應 公正->加媒引渡 美國 孟晚舟 加拿大 法庭->雙重 犯罪孟晚舟 脫困 引渡案->雙重 犯罪 抗辯 聽證會引渡 加拿大 雙重->伊朗 犯罪 孟晚舟 法庭引渡 孟晚舟 犯罪->審理 雙重 加拿大 美國引渡 標準 美國 審理 雙重 犯罪->孟晚舟 加拿大 案件孟晚舟 審理 法庭 美國->引渡 華為 加拿大 雙重 犯罪審理 犯罪 引渡案->引渡 加拿大 孟晚舟 雙重伊朗 孟晚舟 犯罪 美國->引渡 加拿大 雙重……1月21日……孟晚舟 雙重->犯罪 引渡開庭 引渡->聽證會 孟晚舟孟晚舟 首場 -> 聽證會 開庭加拿大 法院 孟晚舟->中國加拿大 孟晚舟 開庭->律師腳戴 電子 開庭->鐐銬 法院孟晚舟 司法 華為->加拿大 清白聽證會 華為->加拿大 孟晚舟 引渡加拿大 開庭 引渡->孟晚舟 引渡案中國 孟晚舟 開庭->拘押案 加拿大加拿大 孟晚舟 引渡案->聽證會 開庭拘押案 鐐銬->法院 電子 孟晚舟 開庭鐐銬 法院 電子 孟晚舟->不卑不亢 開庭…………5月28日……犯罪 雙重 未能->標準 孟晚舟公布 雙重 孟晚舟->加拿大 引渡案雙重 認定 孟晚舟->加拿大 犯罪 判決犯罪 獲釋->加拿大 雙重 未能 孟晚舟引渡案 雙重 判決->加拿大 認定 孟晚舟加拿大 判決 不列顛->孟晚舟 哥倫比亞省犯罪 認定 孟晚舟->加拿大 雙重 引渡案加拿大 引渡案 標準->犯罪 雙重 審理 孟晚舟加拿大 犯罪 雙重 判決->引渡案 標準 孟晚舟加拿大 高等法院 不列顛 孟晚舟->哥倫比亞省加拿大 雙重 不列顛 孟晚舟->犯罪 引渡案 哥倫比亞省…………

將圖3中的所有關聯規則集按照時間順序組合后篩選，得到的熱點話題的相關關鍵詞結果見表2。其中，為了表格直觀、清晰，實驗中涉及的相同語義的關鍵詞，如：中國和中方、加拿大和加方等，只選用一個關鍵詞。

表2 各階段熱點話題的關鍵詞結果

根據事件發展，“孟晚舟聽證會”事件可分為7個階段，每個階段的話題相關關鍵詞信息解析如下：

(1)1.20-1.28階段：加拿大哥倫比亞省法院對孟晚舟案舉行了引渡聽證會，該聽證會聚焦了華為首席財務官孟晚舟被起訴雙重犯罪問題。孟晚舟腳戴電子鐐銬，不卑不亢出席，其被指控引導匯豐銀行違反美國對伊朗的制裁，且在加拿大犯有欺詐罪。中方發言控告美加兩方濫用引渡條約，侵害了中國公民權益，希望能早日釋放孟晚舟。庭審法官表示將延期判決。

(2)2.13-2.16階段：美國對華為的打壓升級，司法部公布了一份聯邦起訴書，指控華為犯有敲詐勒索罪，并密謀竊取美國公司的商業機密，非法與朝鮮伊朗等國家合作。被告包括華為及其4家子公司和華為首席財務官孟晚舟。

(3)2.23-2.26階段：近日華為開始了反擊，向紐約法院遞交了一封信，這封信揭露了美國串通匯豐銀行誣陷華為的事實，以及其引渡孟晚舟的意圖。

(4)3.30-4.3階段：周一，加拿大卑詩省最高法院舉行視頻會議審理孟晚舟向美國引渡案。美國稱華為涉嫌伊朗商業交易有關的銀行欺詐指控，因受疫情影響，下次案件管理會議延后至4月27日，且短期內不再就是否符合“雙重犯罪”原則公布裁決。

(5)4.28-5.2階段：受疫情影響，在加拿大卑詩省最高法院以電話會議的方式舉行了聽證會，該聽證會聚焦了華為首席財務官孟晚舟被起訴雙重犯罪問題。

(6)5.22-5.27階段：加拿大哥倫比亞省最高法院將于5月27日就孟晚舟引渡案做出關鍵裁決。如果判決不符合美加引渡條件，孟晚舟將擺脫持續了500多天的被軟禁狀態，重獲自由。5月26日，加拿大總理表示加方司法獨立，孟晚舟判決情況將不受政治干預。中國外交發言人趙立堅回應稱，美加兩國濫用引渡條約致使中國公民的合法權益受到侵害，希望能切實糾正錯誤，早日釋放孟晚舟。

(7)5.28-6.6階段：北京時間28日凌晨，加拿大法院公布孟晚舟引渡案的第一個判決結果，孟晚舟被加拿大法院認定符合“雙重犯罪”標準，因此針對孟晚舟的引渡案將會繼續審理。該事件引起中方的強烈不滿，中方外交部發言人表示，加方在該事件中充當了美國幫兇，為了打壓華為等高新企業，濫用引渡條約，損害了中國公民的合法權益。

4.4 對比實驗及結果

實驗選取文獻[10]中的OLDA算法作對比。首先，按照時間信息使用OLDA算法對話題語料進行劃分。然后，采用LDA模型通過對不同時間段對應的文本數據進行建模，最終實現話題演化分析，其中話題的先驗知識是其歷史分布。實驗結果見表3。

對比表2與表3，使用本文方法獲取的關鍵詞個數為276個，比使用OLDA方法得到的關鍵詞個數多了50個，且本文方法能獲取到更詳細準確的信息。如：1.20-1.28階段“司法、公民、腳戴、鐐銬、主權、匯豐銀行、哥倫比亞省、延期”等關鍵詞，2.13-2.16階段“首席、民企、起訴書、民主、特朗普、任正非、5G、歐美、朝鮮”等關鍵詞，2.23-2.26階段“業務、手段、發聲、違反、法院、正式、政府”等關鍵詞，3.30-4.3階段“伊朗、公布、開庭、欺詐、市場、雙重、制裁、銀行、會議、違反” 等關鍵詞，4.28-5.2階段“芯片、遠程、損害、卑詩省、雙重、違反、 會議、涉及、庭審” 等關鍵詞，5.22-5.27階段“高管、立場、銀行、欺詐、伊朗、結束、500、法律、發言人、回應、合法權益、損害、律師、糾正錯誤” 等關鍵詞，5.28-6.6階段“交涉、自由、趙立堅、合法權益、打壓、出賣、支持、發言人、大國、5G、采訪、侵犯、原則、強烈不滿” 等關鍵詞。說明本文方法能夠挖掘出事件具體細節相關的關鍵詞，準確分析事態進展程度，有助于正確把握話題演化趨勢。

表3 各時間片OLDA算法的結果

5 結束語

本文引入“時間窗口”的概念，首先對各個時間窗口采用并行關聯規則算法獲取關聯規則集，進而發現話題與其后續事件的關聯關系，從而跟蹤話題發展演變的來龍去脈。實驗結果表明，本文提出的算法能夠更加完整有效地深入分析話題的動態演化細節。

本文只針對話題的內容進行跟蹤，沒有從話題強度分析話題的演化趨勢，而且話題在發展過程中存在漂移的情況。因此，如何有效跟蹤話題的漂移趨勢，并結合內容和強度兩方面跟蹤話題的動態演化趨勢將是今后研究的主要內容。