連續時間區間內的頻繁詞序列挖掘算法

王 璐，劉曉清，何震瀛

（1.復旦大學 軟件學院，上海 200441；2.復旦大學 計算機科學技術學院，上海 200433）

0 概述

互聯網和人工智能等信息技術的快速發展，使得新聞報道、博客推文、用戶評論等大量文本數據呈指數級增長，這些文本數據中蘊含著時事政治、熱點話題等具有重要價值和研究意義的信息。但由于網絡中文本數據海量、繁雜等特點，人們難以在大量篇幅文本中直接獲取有效信息，因此快速高效地在海量文本數據中提取有效信息成為研究人員關注的重點。以詞序列形式挖掘文本中頻繁出現的短語成為用戶獲取關鍵信息及進行文本集探索的有效方式之一。頻繁詞序列挖掘是將頻繁出現的詞序列看作能夠反映文檔主題內容的短語，挖掘在文本集合中頻繁出現的詞序列。頻繁詞序列挖掘工作在短語挖掘［1］、文本聚類［2］、話題檢測［3］等任務中發揮重要作用。EL-KISHKY 等［4］在語料庫中抽取頻繁詞序列作為短語候選集，用于短語挖掘。BEIL 等［5］挖掘文本集合中的頻繁項集，使用頻繁項集作為候選簇進行文本聚類。MA［6］檢測滑動時間窗口中的詞頻統計等信息，并將其應用于新聞流的熱點話題提取模型。在這些工作中，頻繁詞序列挖掘是目標任務中重要且耗時的步驟，因此高效的挖掘方法能夠帶來整體任務效率的提升。

在很多實際應用中，新聞、博客等文本數據通常會以時間為單位進行組織并存儲。近年來，文獻［7-9］等諸多研究工作都聚焦在流數據、時空數據等具有時間屬性的文本數據中進行文本挖掘。因此，研究時間維度下的文本挖掘工作同樣具有重要意義。在一段時間區間內持續頻繁出現的短語，更能體現熱點話題和文章內容趨勢。例如，當使用《紐約時報》新聞作為輸入數據時，劃定時間區間為“2020 年3 月”、頻次閾值為20，在這段連續時間區間內進行頻繁詞序列挖掘，發現獲得的頻繁詞序列為“冠狀病毒實時更新”、“冠狀病毒的簡報”和“伯尼·桑德斯”等，通過這些頻繁詞序列，可以看出該階段的熱點話題更多與新冠肺炎和美國大選的候選人選問題相關。然而，在面對海量文本數據并無法完全掌握文本內容的情況下，用戶難以在一次查詢中準確設置閾值和時間區間，需要多次迭代查詢從而完成挖掘任務。用戶趨向于以探索性方式逐步進行挖掘，例如通過調整最小頻次閾值的大小獲取合適的關鍵短語集合，或通過調整時間區間來探索不同時間段內的熱點話題的變化。傳統頻繁項集挖掘方法在修改最小頻次閾值或數據集后需要重新進行挖掘，因此在海量文本數據庫上進行頻繁詞序列挖掘時存在耗時嚴重的問題，無法達到頻繁迭代的查詢效率要求。

針對文本挖掘中熱點話題檢測、關鍵短語挖掘等實際應用場景，本文提出連續時間區間內的頻繁詞序列挖掘算法。使用頻率樹（Frequency Tree，F-Tree）作為基本索引結構支持高效的頻繁詞序列挖掘，同時設計頻率樹的序列化構建方式和多棵頻率樹的連續剪枝挖掘算法，快速尋找在連續時間區間內的熱點短語信息。

1 相關工作

1.1 熱點話題檢測

熱點話題檢測主要關注在一段時間內持續受到關注和討論的主題內容，近年來研究人員對于熱點話題檢測進行大量研究。文獻［10］提出PCTF 方法，并將其用于查詢一組詞匯成為熱詞的最長持續時間。文獻［11-12］在帶有時空信息的數據流中，查找一段時間內發布的k個最相關的詞匯或文檔。文獻［13］通過優化TF-IPDF 的計算過程，加快熱點詞匯查詢效率。在上述工作中，熱點話題的挖掘結果均以單個詞匯為單位呈現。短語相比詞匯在語意中更加完整，能夠表達更準確的主題含義，在實際應用場景中，人們更傾向于使用短語作為主題表達方式。

1.2 頻繁項集挖掘

頻繁詞序列挖掘問題類似于數據挖掘中的頻繁項集挖掘問題［14］。在頻繁項集挖掘中，以Apriori 算法［15-16］為代表的層次優先搜索方法通過遍歷迭代數據集發現項集，以FP-Growth 算法［17］為代表的一系列算法根據數據信息構建FP-Tree，在此基礎上進行頻繁項集發現。Apriori 算法能夠通過簡單修改應用于頻繁詞序列挖掘問題，但由于算法需要多次掃描整個事務數據庫，在大規模文本挖掘中效率低下。憑借良好的擴展性和易編寫的特點，仍有一些研究人員［18-19］使用Apriori 類算法進行詞序列挖掘。FP-Growth 類算法利用樹形結構對原始數據進行索引，在挖掘過程中無需生成候選頻繁項集，提高了算法效率。但在FP-Tree 的構建過程中，需要按照項集頻繁度進行重新排序，打亂了項集之前的前后順序和關聯關系，對于頻繁詞序列挖掘任務而言，單詞構成的詞序列是有序且連續的。因此，上述頻繁項集工作對于解決頻繁詞序列挖掘問題具有一定指導意義，但無法完全適用于頻繁詞序列的挖掘。

1.3 后綴樹

與FP-Tree 類似，后綴樹是一種多叉樹型的數據結構，能夠索引一個字符串的所有后綴。對于由給定字符串S 構成的后綴樹T，T 中每個內部節點到葉子節點的路徑均能夠構成S 的一個后綴。如圖1 所示，由字符串S=“I Know You Know I Know”構成的后綴樹T 可以看出，S 包含兩個以I 為起始點的后綴“I Know You Know I Know”和“I Know”。

圖1 后綴樹Fig.1 Suffix tree

后綴樹的概念由WEINER［20］在1973 年提出，為了降低后綴樹的存儲代價，MCCREIGHT 等［21］對后綴樹采取壓縮冗余節點的方法，如圖2 所示，每條邊不再僅限于包含一個單詞而是一個部分叉的字符串，使用$表示字符串結束。每個內部節點都至少具有兩個子節點。為提高后綴樹的構造效率，UKKONEN［22］在1995 年提出在 線構造字 符串后綴樹的算法，能夠從左向右對字符串進行處理，當遇到不同后綴時對后綴樹的邊進行分割，該方法具有線性的時間復雜度。

圖2 壓縮后綴樹Fig.2 Compressed suffix tree

2 問題定義

本文研究的主要問題為根據用戶給定的查詢范圍和最小頻次閾值，快速找到查詢范圍內在所有最小時間區間上均滿足頻次閾值的詞序列集合，實現對連續熱點話題的檢測。

定義1（時間區間T(x，y)）T(x，y)={tx，tx+1，…，ty}，1≤x≤y≤n表示時間區間，其中，t為最小區間間隔單位，ti為數據集的第i個區間間隔。T(1，n)表示包含整個數據集的完整區間，其中n表示包含的全部最小區間的個數。

定義2（帶有時間屬性的文本數據庫D）數據集中的文本根據時間屬性值分布在對應區間中，存儲分布于時間區間T(1，n)內的文本數據庫D={Di|1≤i≤n}，其中Di為時間屬性值屬于時間區間ti的文本數據。

定義3（詞序列s（x，y））根據由有限個單詞a組成的詞典Σ，文本可表示為d={a1，a2，…，an}。詞序列s(x，y)={ax，ax+1，…，ay}，s(x，y)∈D是由文本集合D中依次出現的單詞組成的連續序列。

定義4（詞序列的頻次Freq(s，D)）對于給定的文本數據庫D={D1，D2，…，Dn}，詞序列s在D中的頻繁度可表示為Freq(s，D)=|{d∈D：s?d}|，即詞序列s在D中完整出現的次數。

定義5（連續時間區間內的頻繁詞序列查詢query(D，θ，T)）對于分布在時間區間T(1，n)內的文本數據集D={D1，D2，…，Dn}，給定時間 區間子集T(x，y)和最小查詢閾值θ，查詢在所有最小時間子區間tx…ty上的所有 文本子集Dx…Dy均滿足Freq(s，Di)≥θ，且不存在s的子串s'滿足Freq(s'，Di)≥θ的所有詞序列s構成的集合S。

3 算法描述

3.1 頻率樹

原始后綴樹在邊上記錄子串起始位置等信息，同時后綴樹通常作為單個字符串而不是文本集合的索引結構，無法很好地表示多條文本數據信息。本文對后綴樹結構進行改進，提出頻率樹，使其可用于詞序列頻次的計算，實現詞序列挖掘算法。F-Tree對于原始后綴樹結構修改如下：

1）給定一個包含n條文本數據的文本集合D={s1，s2，…，sn}，F-Tree 是一個包含n條文本數據的所有后綴的后綴樹。在構造F-Tree 時，在插入第i條文本數據s={a1，a2，…，an}時，在s后填充唯一的終止標記符$i，得到s={a1，a2，…，an，$i}。

例1頻率樹與僅索引單條字符串的后綴樹不同，能夠包含多條文本串的所有后綴。使用不同終止符保證了文本數據的所有后綴為唯一存在，每個后綴均由唯一的葉節點表示，避免了后綴數據被隱藏在內部節點中或頻次計算被忽略的問題。例如，根據UKKONEN算法在圖2 的后綴樹中插入新的句子“I Know”時，原始后綴樹在讀取到與邊“I Know”完全匹配后，判斷完成本次插入而無須進行任何操作，導致對于完全相同的后綴錯誤的頻次計算。如圖3 所示，對于由“I Know You Know I Know”和“I Know”構成的F-Tree，當修改為插入“I Know $2”時，能夠與“I Know You Know I Know$1”中“I Know”后綴在終止符位置進行區分，從而保證頻率統計的正確性。

圖3 頻率樹Fig.3 Frequency tree

2）F-Tree 的每個節點由節點標號i與頻次屬性值freq 組成node(i：freq)，用freq 來表示由根節點0到當前節點i的路徑拼接得到的詞序列s[0，1，…，i]的頻次，即對于由數據集D構成的具有n個節點的F-Tree，樹中的任意節點i∈(1，n)，freqi=Freq(s[0，1，…，i]，D)。

例2以圖3 中節點2 為例，節點9 存儲的freq=1，即由根節點0 到節點9 的路徑與路徑拼接成的詞序列“Know I Know $1”在數據集中的出現頻次為1。同理，節點1 的freq=3 表示“I Know”詞序列出現頻次為3。

引理1在F-Tree 中，葉子節點的freq 為1。

證明如圖3 所示，F-Tree 中由根節點到葉子節點的路徑表示文本數據后綴，由于每條插入數據采用不同終止符進行標記，因此數據集中所有后綴均是唯一的，即葉子節點的freq 為1。

引理2每個內部節點的freq 等于其直接連接子節點的freq 之和。

證明數據集中詞序列s出現頻次Freq(s，D)等于數據集中以s為前綴的所有后綴個數，由于每個后綴能夠由葉節點唯一表示，根據引理1，對于根節點到i的路徑構成的詞序列s[root，i]，Freq(s，D)等于i的所有孩子節點中葉節點freq 之和，即等于與節點i直接連接的孩子節點的freq 之和。

引理3如果由根節點到節點i的路徑組成的詞序列s[0，i]的頻次為n，那么對于i的所有孩子節點，根節點到孩子節點的路徑組成的詞序列頻次一定小于等于n，即?j∈child(i)，Freq(s[0，j]，D)＜Freq(s[0，i]，D)。

證明由于每個節點的freq 等于其直接孩子節點的freq 之和，如果該節點的頻次小于設定閾值，那么它的孩子節點freq 一定小于設定閾值，即如果一個詞序列s的出現頻次為n，那么所有以s為前綴的更長詞序列出現頻次一定小于等于n。

3.2 基于頻率樹的頻繁詞序列挖掘算法

由F-Tree 節點的freq 特點可知，通過對比節點freq 值與頻次閾值的大小，可以判斷詞序列是否符合查詢要求。當使用F-Tree 進行最小頻次為θ的頻繁詞序列挖掘時，可以通過對F-Tree 進行深度遍歷實現。根據引理3，F-Tree 能夠通過節點freq 值與閾值θ的對比對F-Tree 進行剪枝，從而減少遍歷范圍，提高查詢效率。遍歷F-Tree 到達某個節點時，如果它的freq 大于最小閾值，記錄邊中的詞序列并繼續向下遍歷；直到節點freq 不再滿足閾值要求，那么對應后綴不再滿足頻繁詞序列要求，向上回溯到父節點；如果節點滿足閾值且它的所有孩子節點均不滿足閾值要求，那么由根節點到該節點的記錄的路徑邊詞序列即為滿足要求的一個最長頻繁詞序列。基于頻率樹的頻繁詞序列挖掘算法（TS_Mining）描述如算法1 所示。

算法1基于頻率樹的頻繁詞序列挖掘算法

使用F-Tree 的頻繁詞序列挖掘算法能夠獲得每個單位時間區間內的頻繁詞序列結果。為了進行連續時間區間范圍內的頻繁詞序列挖掘，需要對每個單位時間區間內的挖掘結果進行合并，得到在所有單位時間區間內均滿足查詢條件的詞序列。在對單個F-Tree 挖掘結果進行合并時，一個基礎的取交集方法是對所有的結果集合逐個合并取交集，從而獲取滿足要求的最終結果集合。對第i個時間區間的詞序列集合Si中的詞序列s逐個進行遍歷，獲取s與前i-1 個區間合并的結果集合S′i-1的最長交集，將不為空的詞序列加入S′i，從而得到前i個區間的詞序列結果集合S′i。連續區間查詢的取交集算法（Intersection）描述如算法2 所示。

算法2連續區間查詢的取交集算法

3.3 改進的剪枝挖掘算法

算法1 與算法2 在對每個F-Tree 都進行閾值為θ的挖掘的同時，需要對每個單位時間區間內的結果集合進行重復取交集操作，從而找到在所有F-Tree中均滿足查詢條件的詞序列。從結果來看，此類算法需要掃描經過更多的路徑并進行額外的取交集計算，造成了效率損失。因此，本文在此基礎上進行改進，充分利用F-Tree 的數據結構，在F-Tree 掃描過程中完成取交集操作，將頻率樹的頻繁詞序列挖掘算法改進為剪枝挖掘算法（TS_Pruning），具體描述如算法3 所示。

算法3改進的剪枝挖掘算法

使用前i-1 個單位時間區間內的結果作為輸入，對第i棵F-Tree 進行掃描剪枝，獲得在前i個單位區間內均滿足查詢條件的結果集合。在剪枝查詢算法中，對于輸入集合的每個詞序列s，在區間i中的F-Tree 中以根節點為起點，自上而下在F-Tree 中查找詞序列s所經節點是否滿足查詢閾值，從而找到滿足查詢條件的最長前綴。該算法充分利用了第i-1 個區間的挖掘結果，能夠減少F-Tree 需要掃描的范圍，同時無須對結果集合進行合并，減少了多次遍歷的時間代價。后綴樹的詞序列匹配算法（find_prefix）描述如算法4 所示。

算法4基于頻率樹的詞序列匹配算法

3.4 外存頻率樹加載

當使用大規模文本數據集進行查詢時，常規主機的內存往往無法容納全部頻率樹索引結構。根據F-Tree 結構可以看出，樹中邊信息與節點信息僅與文本數據集相關，而與每次查詢的設定閾值無關。因此，當面臨內存中無法容納所有F-Tree 索引結構的情況下，通過序列化方法構建每個最小區間內的后綴樹并存儲在本地文件中，當進行查詢時，只需通過反序列化將時間區間范圍內的后綴樹進行結構恢復，而無須對時間區間內的全部文檔重新遍歷來構建后綴樹。當進行連續時間區間內挖掘時，不再需要多次根據不同時間區間內的文本集合構造F-Tree。相對于讀取原數據并重新構建F-Tree 的方法，序列化方法能快速還原F-Tree 結構，從而提升整體挖掘效率。

3.5 時間復雜度分析

假設文本數據集中文本長度為m，查詢時間區間長度為T，在單位時間區間下挖掘的頻繁詞序列的總長度平均為L1，最終頻繁詞序列結果集合總長度為L2。

F-Tree 構造具有與壓縮后綴樹相同的時間復雜度，根據文獻［9］可知，F-Tree 構造的時間復雜度為O（m）。對于樸素F-Tree 的頻繁詞序列挖掘算法，需要對F-Tree 進行深度遍歷找到滿足查詢要求的所有路徑，查找長度為L1，對于所有區間下的F-Tree 挖掘的時間復雜度為O(T×L1)。同時，取交集的結果集合的合并方式共需要進行t次合并操作，每次合并操作對兩個集合進行遍歷，時間復雜度為因此，總的時間復雜度為改進的剪枝挖掘算法將第i-1 個區間挖掘結果集合作為新的時間區間挖掘的輸入，避免結果合并帶來的時間代價。同時，在F-Tree 的挖掘過程中，只需對上一個區間的結果集合路徑進行遍歷剪枝，利用剪枝算法避免無效路徑的搜索，從而降低時間復雜度。在每次挖掘過程中，遍歷路徑長度L'滿足L1＜L'＜L2，因此時間復雜度將趨近于O(T×L2)，進一步降低了挖掘時間復雜度。

4 實驗結果與分析

4.1 實驗設置

4.1.1 實驗數據集

實驗使用2 個開放數據集進行測試：twitter 數據集采用2009 年4月至2009年6月的16萬條twitter 文本；blogs 數據集采用來自blogger.com 的2004 年1 月至2004 年12 月的博客文章［23］，該語料庫共包 含681 288 篇文章。在實驗中設置單位時間區間長度為1 周。為了更加符合現實應用場景，使用NLTK 自然語言處理庫對文本集合進行預處理，包括按照標點和停用詞對文章進行斷句、詞形還原等。表1 給出了數據集的詳細信息。

表1 數據集詳細信息Table 1 Dataset details

4.1.2 實驗環境和對比算法

實驗算法均由C++11 語言編寫，gcc 編譯，運行環境為2 GHz Intel Core i5 四核處理器，16 GB 內存，macOS Catalina 10.15.7 操作系統。

實驗將Apriori 頻繁項集挖掘算法作為對比算法，并分別修改頻繁詞序列查詢的各項參數，以驗證本文提出的基于頻率樹的頻繁詞序列挖掘算法TS_Mining 和改進的剪枝挖掘算法TS_Pruning 的有效性。

4.2 性能分析

對于twitter 數據集，設置查詢的起始時間為2009 年4 月1 日，查詢時間區間T為1、3、6、9、12 周；對于blogs 數據集，設置查詢的起始時間為2004 年1 月1 日，查詢時間區間T為5、10、20、50 周。

圖4 給出了在內存存儲數據情況下改變查詢時間區間后的查詢耗時對比。由圖4 可以看出，當數據全部存在于內存時，TS_Pruning 算法運行時間開銷最低，這是由于在查詢條件相同的情況下TS_Pruning 算法掃描路徑更少，TS_Mining 算法不需要多次迭代掃描數據集，因此相比Apriori 算法查詢耗時約減少了2 個數量級，具有明顯的效率提升。

圖4 改變查詢時間區間后的查詢耗時對比Fig.4 Comparison of query time consumption after changing the query time interval

圖5給出了在磁盤加載數據情況下改變查詢時間區間后的加載與查詢總耗時對比。由圖5可以看出，查詢所需數據需要從磁盤中加載到內存，基于F-Tree的算法相對于Apriori算法具有大幅的效率提升，但由于查詢任務的耗時主要在數據加載到內存的過程中，因此TS_Mining與TS_Pruning算法的總耗時差別并不明顯。對于twitter 數據集和blogs 數據集，設置查詢閾值θ為10、20、50、100、200。圖6給出了在twitter數據集和blogs數據集下的查詢耗時對比，由兩個數據集中的運行結果顯示，TS_Pruning算法的查詢效率高于Apriori算法。

圖5 改變查詢時間區間后的加載與查詢總耗時對比Fig.5 Comparison of loading and total query time consumption after changing the query time interval

圖6 改變查詢閾值后的查詢耗時對比Fig.6 Comparison of query time consumption after changing the query threshold

通過以上實驗結果可以看出，本文提出的TS_Mining 算法和TS_Pruning 算法能夠較好地適應不同需求的查詢問題，在不同查詢閾值和查詢時間區間的應用場景下均能保持更好的查詢效率。

為驗證本文算法在實際應用場景中的可用性，除了算法查詢時間外，還統計了基于Apriori 和F-Tree 算法的內存和磁盤存儲開銷。在所有數據及索引全部存儲于內存的應用場景下，基于F-Tree 的算法的內存存儲開銷約為Apriori 算法的3 倍，如表2 所示。

表2 Apriori 與F-Tree 的內存存儲開銷Table 2 Memory storage overhead of Apriori and F-Tree

如表3 所示，當數據量較大需要在磁盤中進行存儲時，F-Tree 索引的存儲方式在磁盤存儲開銷上相對原始文本大小約有5 至6 倍的增長，但隨著磁盤存儲價格的不斷降低，在外存存儲的方式還是能夠被接受的。對兩類算法實時加載的最大內存消耗進行統計，如圖7 所示，在實時加載數據的應用場景下，基于F-Tree 的算法內存消耗約為Apriori 算法的4 倍。然而，由于對于連續時間區間查詢而言，只需逐次加載一個單位時間區間內的數據并進行挖掘，內存消耗僅與單位時間區間內數據量有關，與總數據集大小和查詢條件的設置無關。

表3 F-Tree 磁盤存儲開銷Table 3 Disk storage overhead of F-Tree

圖7 實時加載的最大內存消耗Fig.7 Maximum memory consumption for real-time loading

5 結束語

本文研究連續時間區間內的頻繁詞序列挖掘問題，通過改進后綴樹結構提出基于頻率樹的快速頻繁詞序列挖掘算法。針對連續時間區間內的頻繁詞序列查詢問題，設計改進的剪枝挖掘算法進一步提升頻繁詞序列挖掘效率。實驗結果表明，本文提出的基于頻率樹的快速頻繁詞序列挖掘算法和改進的剪枝挖掘算法在不同的應用場景下的查詢效率均明顯優于傳統Apriori 挖掘算法。后續將針對頻率樹的外存存儲代價問題進行優化，通過壓縮頻率樹索引和改進后綴樹加載效率，進一步提高整體查詢和加載效率。