黃九鳴,吳泉源,張圣棟,賈 焰,劉 東,周 斌

(國防科學技術大學計算機學院，湖南長沙 410073)

?

基于AC-Trie的在線社交網(wǎng)絡文本流熱點短語挖掘

黃九鳴,吳泉源,張圣棟,賈 焰,劉 東,周 斌

(國防科學技術大學計算機學院，湖南長沙 410073)

在線社交網(wǎng)絡文本流中的熱點短語能反映文本流中隱含的熱點話題和突發(fā)事件.本文提出了一種無需分詞并能支持多種熱度度量函數(shù)的熱點短語挖掘技術.首先用文本流的某個典型時段采樣得到候選短語,構建AC-Trie前綴樹.然后,基于該前綴樹,單遍掃描后續(xù)的文本流,將候選短語的歷史出現(xiàn)頻率記錄在Trie相應節(jié)點上,從而支持多種基于歷史頻率的熱度計算方法.此外,為及時發(fā)現(xiàn)新的熱點短語并減少AC-Trie的構建次數(shù),本文通過分析Trie樹各節(jié)點上的遺漏短語頻率,動態(tài)確定候選短語的更新時機.新浪微博數(shù)據(jù)集上的實驗驗證了本文方法的有效性(準確率達89%)和高效性(時空開銷僅為基準算法的2%).

文本流;熱點短語;AC-Trie;文本挖掘;在線社交網(wǎng)絡

1 引言

微博、即時通信、BBS等在線社交網(wǎng)絡應用的用戶通過文本消息來表達和傳遞自己的思想.這些帶有時間屬性的文本消息構成了網(wǎng)絡文本流或網(wǎng)絡文本流.挖掘網(wǎng)絡文本流中被廣泛討論和關注的熱點短語,可有效地應用于輿情分析、股市預測以及商業(yè)智能等領域.

已有的熱點詞挖掘技術面臨以下挑戰(zhàn):①在高速到達的海量網(wǎng)絡文本流上進行統(tǒng)計挖掘,計算和存儲開銷巨大;②熱點短語的鑒別與用戶需求相關,單一的統(tǒng)計方法適應性差.針對上述問題,本文提出一種網(wǎng)絡熱點短語挖掘技術AC-Hot.該技術與最大頻繁項挖掘技術[1]相比，具有以下顯著特點:①只需單遍掃描文本流.②作為一種熱點短語挖掘框架，通過詳細記錄了候選短語的歷史狀態(tài),可支持各種自定義的熱度度量方法.③內(nèi)存空間占用量可控,通過從文本流中采樣構建候選短語集合,有效控制內(nèi)存占用量.④無需預先分詞,可自動發(fā)現(xiàn)熱點新詞和短語.

2 相關研究

有一些研究與本文方法間接相關,它們致力于挖掘突發(fā)詞語或檢測給定詞語的爆發(fā)時間點.例如,文獻[2]用一個突發(fā)屬性集合來表示一個突發(fā)事件.文獻[3]針對博客和論壇文本流的特點對Kleinberg的算法[4]進行擴展.這類方法只考察單個詞語,沒有考慮詞語的組合,無法發(fā)現(xiàn)由多個詞語組成的熱點短語.給定文檔集中的頻繁短語挖掘有較多研究成果,如文獻[5,6].但是,這類方法無法處理流數(shù)據(jù).數(shù)據(jù)流中挖掘最大頻繁項集方面有三類方法,分別是滑動窗口模型[7],時間消逝模型[8]和界標模型[9].但它們都是在特定前提下給出了頻繁項集的定義,不保存各個(項集)子串的所有歷史狀態(tài),因此無法支持多種熱度度量模型.

社會媒體熱點話題檢測與突發(fā)事件檢測方面的研究[10～12]與本文目的相似,旨在發(fā)現(xiàn)能代表熱點話題或突發(fā)事件的文檔集或關鍵詞.文檔集方面,主要采用基于文本聚類的方法,通過比較文檔的相似性并采用Single-Pass或K-Means等聚類方法實現(xiàn)聚類[11],進而通過各類別的文檔數(shù)量和點擊率等指標計算話題熱度.這類方法的計算量巨大,可理解性差.另一方面,基于關鍵詞的熱點話題或突發(fā)事件檢測方面,比較有代表性的是基于LDA模型的各種改良方法[12].這類方法的計算量同樣比較大,并且需事先對文檔進行分詞,無法自動發(fā)現(xiàn)網(wǎng)絡新詞.

3 問題定義

本文將微博、BBS、即時通信等在線社交網(wǎng)絡應用的文本消息數(shù)據(jù)抽象為文本流,簡稱文本流.稱字母表中的一系列字符組成的字符串為一個短語.如果短語q是消息m的子串，稱消息m包含短語q,又稱短語q在m中出現(xiàn),記為m?q.一個文本流截至時間t時包含短語q的消息條數(shù),稱為截至t時q在該文本流的出現(xiàn)次數(shù).短語的出現(xiàn)頻率指其在一定時間窗口內(nèi)該短語出現(xiàn)次數(shù)與消息條數(shù)的比值,用函數(shù)θ表示,如定義1所示.

定義1 (出現(xiàn)頻率) 令q為一短語,S為文本流,頻率統(tǒng)計時間窗口為Δt,函數(shù)τ(m)表示消息m的產(chǎn)生時刻,則t時q在S中的出現(xiàn)頻率為:

(1)

熱點短語挖掘任務為在指定時間點,查找出熱度值排名在前k位的短語,如定義2所示.

定義2 (熱點短語挖掘) 給定的文本流S,時刻t,用Q表示所有短語的集合,d為用戶指定的熱度度量函數(shù),稱熱度值排名前k位的短語為t時刻文本流S的TopK熱門短語,如式(2)所示:

Hot(t,k,S)=

{qx|qx∈Q,1≤x≤k,?q∈Qd(qx,t)≥d(q,t)}

(2)

4 基于Trie的樸素算法

根據(jù)定義2,熱點短語挖掘直觀的解決方案是在內(nèi)存中保存所有短語,將短語出現(xiàn)次數(shù)的變化情況保存在歷史頻率表中.為壓縮數(shù)據(jù)存儲,本文的樸素方法基于Trie實現(xiàn).在Trie樹的每個節(jié)點上增加一個歷史頻率表.歷史頻率表中的元素為時間與出現(xiàn)頻率組成的二元組.該方法分為兩個步驟:首先將短語及其出現(xiàn)頻率保存在Trie樹上,然后在Trie樹上查找最熱門的k個短語.

綜上，2018年冬季至2019年早春果園管理應緊緊圍繞“保護樹體，規(guī)范樹形，調(diào)節(jié)花量，減少病蟲”的重點，不違農(nóng)時，抓緊實施，努力做到“適時、規(guī)范、到位”。

第一個步驟的過程如下:(1)為文本流創(chuàng)建一個Trie樹;(2)當新消息m到達時,將m包含的所有短語放在集合E中;(3)對每個q∈E,在Trie樹上查找是否存在q,如果不存在則將q加入Trie樹;(4)對每個q∈E,設其歷史頻率表表尾的元素為〈t,x〉,若τ(m)

第二個步驟中,當用戶需要獲取文本流的熱點短語時,遍歷Trie樹的所有短語并用指定的熱度公式來計算短語的熱度,然后,按熱度值對所有短語進行排序,挑選出最熱的k個短語.

這個樸素算法的缺點是時空開銷巨大.對于一個文本流,設消息集合為S,短語集合為E,第一個步驟的時間復雜度為O(∑m∈S2|m|),內(nèi)存存儲的開銷是O(∑q∈E|q|).第二個步驟每次查找最熱的k個短語的時間復雜度為O(|E|log(|E|)).

5 基于AC-Trie的熱點短語挖掘技術AC-Hot

由于AC-Trie只需單遍掃描文本流便可同時匹配出多個模式串,本節(jié)提出基于AC-Trie的熱點短語挖掘框架AC-Hot.只要能及時地從文本流中截取一個片段作為樣本,將樣本消息中的所有短語加入AC-Trie中進行監(jiān)視,便可高效發(fā)現(xiàn)新出現(xiàn)的熱點短語.因此,AC-Hot是短語采樣和文本流掃描監(jiān)視兩個狀態(tài)交替運行的過程.由于AC-Trie的構建開銷巨大,因此為提高運行效率應盡可能減少短語采樣次數(shù).同時,為保證及時發(fā)現(xiàn)新熱點短語,應動態(tài)確定短語采樣時機.AC-Hot通過估計掃描過程遺漏掉熱點短語的概率,動態(tài)確定短語采樣的時機.

定義3 (遺漏短語) 設文本流S,短語出現(xiàn)頻率統(tǒng)計處于掃描階段,監(jiān)視S的AC-Trie樹為T,有短語q?T∧m?q,m為S中新產(chǎn)生的消息,則在該掃描階段稱q為遺漏短語.

出現(xiàn)頻率統(tǒng)計由掃描狀態(tài)轉入采樣狀態(tài)的時機,將根據(jù)遺漏短語是熱點短語的可能性大小來動態(tài)確定.為估計遺漏短語是熱點短語的可能性大小,我們用遺漏短語的頻率值(簡稱遺漏頻率)來估計遺漏短語是熱點短語的概率.遺漏頻率記錄在AC-Trie遺漏短語的父節(jié)點上.

定義4 (遺漏頻率) 設統(tǒng)計時間窗口為Δt,時間段[t-Δt,t)內(nèi)文本流S中有遺漏短語q1,q2,…,qn在AC-Trie樹上的最長前綴都為q,則q對應節(jié)點v(q)在t時的遺漏頻率為:

(3)

記錄在每個節(jié)點上的遺漏頻率,是以節(jié)點對應短語為前綴的所有遺漏短語的出現(xiàn)頻率之和,不能直接用于熱度計算,應根據(jù)遺漏頻率估算出每條遺漏短語的出現(xiàn)頻率范圍.由于掃描狀態(tài)下沒有為新短語新增子節(jié)點,因此各節(jié)點應新增的子節(jié)點數(shù)量,等于以節(jié)點短語為前綴的遺漏短語個數(shù).給定一個文本流S,對于任意短語(字符串)“c1c2…ck”(k≥1),相應后繼字符集合C(t)={c|“c1c2…ckc”?m,τ(m)≤t,m∈S},則集合C(t)的大小隨t增長遞增,但增長速度逐漸變慢.本文假設短語后繼字符的數(shù)量關于時間呈指數(shù)分布.在AC-Trie樹上,對于任一節(jié)點(短語),其指向子節(jié)點的邊上的字符即為該節(jié)點的后繼字符.后繼字符數(shù)量關于時間的分布情況,等價于潛在子節(jié)點數(shù)量關于時間的分布情況.因此,潛在子節(jié)點數(shù)量關于時間的分布函數(shù)如下式所示:

(4)

其中,x為一節(jié)點,t為時間,αx和βx為待定參數(shù).為估計各個節(jié)點的αx和βx參數(shù),首先記錄每個節(jié)點在采樣階段的每個統(tǒng)計時間窗口內(nèi)新增子節(jié)點的數(shù)量,再用最小二乘法進行估計.

TopK查找過程與短語出現(xiàn)頻率監(jiān)視過程并行運行,基于AC-Trie中各候選短語的歷史頻率表,用具體的熱度計算公式計算并查找出熱度排名在前k位的短語,同時根據(jù)各節(jié)點的遺漏歷史表估計遺漏短語出現(xiàn)頻率的取值,以判斷是否需要重新進行短語采樣.TopK查找過程首先采用自底向上寬度優(yōu)先遍歷Trie樹的策略,將子節(jié)點上歷史頻率表的值匯總到父節(jié)點和fail 指針指向的節(jié)點(后綴)上.對每個節(jié)點,計算其熱度,并估算以該節(jié)點為前綴的各遺漏短語中的最大熱度值,然后將這兩個值分別用兩個格式為<熱度,節(jié)點,類型>的三元組表示.執(zhí)行完上述步驟后,檢查遺漏歷史表,若相應節(jié)點下的遺漏短語中可能含有熱度在前k位的短語,文本流中可能有AC-Trie上不存在的熱點短語,監(jiān)視狀態(tài)轉入短語采樣狀態(tài).

6 實驗驗證

為驗證本文方法的有效性,我們從新浪微博、騰訊微博和Twitter三個社交網(wǎng)絡平臺上采集2015年5月1日至5月30日一個月內(nèi)關于“四川”的2661萬條微博,構建實驗數(shù)據(jù)集.本實驗以“自動發(fā)現(xiàn)每天輿情熱點”為需求背景,設置TopK查找的運行周期(簡稱TopK周期)為1天.由于人的關注范圍有限,TopK查找輸出的熱點短語數(shù)目k設為20.

由于本文方法AC-Hot與基于話題模型的熱點話題發(fā)現(xiàn)在表現(xiàn)形式、計算性能上存在顯著差異(見本文相關研究),因此本實驗不同這類方法進行對比.另一方面,已有的基于關鍵詞的方法,都需要事先分詞,不能發(fā)現(xiàn)新詞,更不能靈活支持多種統(tǒng)計方法,難以同AC-Hot進行實驗對比.為此,本實驗以基于Trie的樸素算法為基準算法,對比分析AC-Hot的準確性和處理速度.

我們在數(shù)據(jù)集上充分測試了AC-Hot.各個TopK周期上的準確率如圖2所示,平均準確率為0.89,總體上比較穩(wěn)定.表1列出了AC-Hot在數(shù)據(jù)集上運行時,短語采樣被觸發(fā)的TopK周期編號.可見,幾處波動較大的地方,恰為AC-Hot判斷需重新進行短語采樣的時刻.并且,重新采樣完畢后,準確率馬上又回到較高的水平.

表1 短語采樣時刻

圖3(a)與圖3(b)分別展示了AC-Hot與基準算法在數(shù)據(jù)集上的時間開銷對比和內(nèi)存空間開銷對比.兩張圖的橫軸均為TopK周期編號,縱軸分別為所需CPU時間與內(nèi)存使用量.可見,AC-Hot的時間開銷和內(nèi)存開銷都遠小于基準算法(樸素算法).

7 結束語

文本流中的熱點短語能反映文本流中隱含的熱點話題和突發(fā)事件.本文分析了熱點短語的形成規(guī)律,針對熱度度量方法多樣、文本消息數(shù)量巨大等挑戰(zhàn),提出了具有極高性能的近似方法AC-Hot.該方法能支持多種熱度度量方法,平均準確率達89%,時空開銷僅為基準算法的2%.

[1]Calders T,Dexters N,Goethals B.Mining frequent itemsets in a stream[A].Seventh IEEE International Conference on Data Mining[C].Omaha,Nebraska:IEEE,2007.83-92.

[2]Yuan Z,Jia Y,Yang S.Online burst detection over high speed short text streams[A].Computational Science-ICCS 2007[C].Heidelberg,Berlin:Springer,2007.717-725.

[3]Fujiki T,Nanno T,Suzuki Y,Okumura M.Identification of bursts in a document stream[A].First International Workshop on Knowledge Discovery in Data Streams (in conjunction with ECML/PKDD 2004)[C].Pisa,Italy,2004.55-64.

[4]Kleinberg J.Bursty and hierarchical structure in streams[J].Data Mining and Knowledge Discovery,2003,7(4):373-397.

[5]Ahonen-Myka H.Discovery of frequent word sequences in text[A].Pattern Detection and Discovery[M].Berlin Heidelberg:Springer,2002.180-189.

[6]Han J,Pei J,Yin Y.Mining frequent patterns without candidate generation[A].ACM SIGMOD Record[C].Dallas,Texas:ACM,2000.29(2):1-12.

[7]Wong R C W,Fu A W C.Mining top-K frequent itemsets from data streams[J].Data Mining and Knowledge Discovery,2006,13(2):193-217.

[8]Lee D,Lee W.Finding maximal frequent itemsets over online data streams adaptively[A].Fifth IEEE International Conference on Data Mining[C].Houston,Texas:IEEE,2005.8.

[9]Yu J X,Chong Z,Lu H,et al.False positive or false negative:mining frequent itemsets from high speed transactional data streams[A].Proceedings of the Thirtieth International Conference on Very Large Data Bases (VLDB Endowment)[C].Toronto,2004.Volume 30:204-215.

[10]Thanh Lam H,Calders T.Mining top-k frequent items in a data stream with flexible sliding windows[A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Washington,DC:ACM,2010.283-292.

[11]Zhou G,Zou H C,Xiong X B,et al.MB-singlepass:microblog topic detection based on combined similarity[J].Computer Science,2012,39(10):198-202.

[12]Liu G,Xu X,Zhu Y,et al.An improved latent dirichlet allocation model for hot topic extraction[A].IEEE Fourth International Conference on Big Data and Cloud Computing (BdCloud)[C].Sydney:IEEE,2014.470-476.

黃九鳴 男,1981年生于福建安溪.博士、中國人民解放軍國防科學技術大學助理研究員.研究方向為Web挖掘、大數(shù)據(jù)、分布式計算和社交網(wǎng)絡分析.

E-mail:jiuming.huang@qq.com

吳泉源 男,1942年生于上海.中國人民解放軍國防科學技術大學教授、博士生導師.研究方向為人工智能和分布式計算.

Mining Hot Phrases on Social Network Text Streams Based on AC-Trie

HUANG Jiu-ming,WU Quan-yuan,ZHANG Sheng-dong,JIA Yan,LIU Dong,ZHOU Bin

(SchoolofComputer,NationalUniversityofDefenseTechnology,Changsha,Hunan410073,China)

The hot phrases in the social network text streams can reflect the hidden hot topics and sudden events.This paper proposes a hot phrase mining technology which can support various hot degree measures without word segmentation.We first construct an AC-Trie using the candidate phrases gathered from text streams.Based on such AC-Trie,we record the historical occurrence frequency of phrases on the Trie by scanning the following streams in single-pass.Furthermore,the AC-Trie needs to be reconstructed using the new samples in the text stream because of the evolution of hot phrases.Thus,we start the reconstruction dynamically according to estimating the occurrence frequency of the missed phrases.The experiments on the Sina micro-blog show that our approach is effective (precision of 89%) and efficient (overhead is 2% of na?ve approach).

text stream;hot phrase;AC-Trie;text mining;micro-blog

2015-02-15;

2015-08-14;責任編輯：李勇鋒

國家973重點基礎研究發(fā)展計劃(No.2013CB329601);國家自然科學基金(No.61502517)

TP391

A

0372-2112 (2016)10-2466-05

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.026