熱點(diǎn)詞匯的最長時間區(qū)間查詢算法

路 暢 何震瀛 荊一楠 王曉陽

1(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203)2(上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室(復(fù)旦大學(xué)) 上海 200433)3(上海智能電子與系統(tǒng)研究院 上海 201203)

0 引 言

高效、快速地獲取熱點(diǎn)詞匯在新聞話題追蹤[1]、金融市場分析[2]、商業(yè)智能[3]以及社會輿情監(jiān)測[4]等領(lǐng)域發(fā)揮著重要作用。作為話題檢測與追蹤的核心任務(wù)之一，熱點(diǎn)詞匯(以下簡稱為熱詞)提取是當(dāng)前的一個研究熱點(diǎn)。

對語料庫中的關(guān)鍵詞及包含關(guān)鍵詞的短語、句子進(jìn)行聚類，是提取熱點(diǎn)話題的一個重要手段。但在實(shí)際應(yīng)用中，為了了解不同約束條件下的熱詞情況，用戶經(jīng)常查看不同過濾條件下的熱詞，以了解不同時間區(qū)域內(nèi)的熱詞。因此，對關(guān)鍵詞提取方法的效率進(jìn)行優(yōu)化，能有效提高熱詞檢測的效率。

針對熱詞提取，業(yè)界已開展了大量研究工作。Krulwich等[5]利用啟發(fā)式規(guī)則抽取文檔中重要的詞和短語。Salton[6]提出了TF-IDF算法，刻畫了詞匯對于語料庫或其中一份文檔的重要性。Bun等[7]改進(jìn)了TF-IDF算法可能將更高的權(quán)重賦予語料庫中出現(xiàn)較少的詞匯的不足，提出了TF*PDF算法，將更高的權(quán)重賦予出現(xiàn)在多個文檔中的詞匯，以提取整個語料庫的關(guān)鍵詞和熱點(diǎn)話題。遲呈英等[8]引入了話題權(quán)重，并將其與TF*PDF結(jié)合，以更全面地反映話題的熱度分布情況。趙志洲等[9]提出了EHWE算法，對數(shù)據(jù)進(jìn)行劃分，在一定程度上優(yōu)化了TF*PDF的計(jì)算過程。但是這些算法的一些共同不足是：

① 僅考慮整個語料庫在某個時間區(qū)間關(guān)鍵詞，未考慮不同偏好的用戶對不同類別新聞等的查詢需求。

② 面向挖掘任務(wù)，時間復(fù)雜度較高，當(dāng)用戶不斷地更改查詢條件(類別和時間區(qū)間)時，算法需要對詞頻和包含關(guān)鍵詞的文檔數(shù)進(jìn)行重復(fù)計(jì)算，無法滿足用戶對于關(guān)鍵詞提取的在線查詢的需求。

在實(shí)際應(yīng)用中，為了進(jìn)行新聞追蹤，用戶需要對一組特定的詞匯進(jìn)行查詢，以尋找這組詞匯能夠成為熱點(diǎn)詞匯所處的最長時間范圍。這要求算法不斷地更新查詢條件，使用TF*PDF算法查詢關(guān)鍵詞，以判斷該組特定詞匯是否滿足成為關(guān)鍵詞的條件。而由于上述的不足，傳統(tǒng)的TF*PDF算法無法快速、高效地對關(guān)鍵詞進(jìn)行查詢，以滿足用戶在線查詢的需求。

為此，本文對如何有效地使用TF*PDF算法對關(guān)鍵詞進(jìn)行快速提取進(jìn)行研究。關(guān)鍵詞在線提取的兩個核心研究問題是：① 區(qū)分不同類別的新聞，以面向不同偏好的用戶；② 在用戶不斷調(diào)整查詢新聞的類別、時間區(qū)間的條件下，快速、高效地對關(guān)鍵詞進(jìn)行提取。因此，設(shè)計(jì)在類別、時間兩個維度上對關(guān)鍵詞進(jìn)行在線查詢的方法依然是一個具有挑戰(zhàn)性的問題。針對上述傳統(tǒng)方法的缺點(diǎn)，本文將TF*PDF算法與Prefix Cube結(jié)合，優(yōu)化TF*PDF算法的詞頻統(tǒng)計(jì)、包含關(guān)鍵詞的文檔數(shù)統(tǒng)計(jì)的過程，提出一種高效地對二維新聞數(shù)據(jù)進(jìn)行關(guān)鍵詞提取并查詢最大時間范圍的方法(PCTF)，以根據(jù)用戶提供的詞匯，快速尋找這些詞匯能夠成為熱點(diǎn)詞匯的最大區(qū)域。

1 相關(guān)研究

本文所使用的主要符號如表1所示。

表1 符號說明

1.1 話題檢測與追蹤

話題檢測與追蹤(TDT)的研究始于1996年[10]，旨在從大量的新聞數(shù)據(jù)流中發(fā)現(xiàn)并追蹤新興事件和話題。一個話題由一個種子事件或活動以及與其直接相關(guān)的事件或活動組成[11]。熱門話題是指在一段時間內(nèi)，在某個領(lǐng)域受到人們廣泛關(guān)注和討論的話題，同時該話題被多個媒體廣泛報(bào)道。熱點(diǎn)話題檢測與追蹤是指發(fā)現(xiàn)在一定時期內(nèi)的熱門話題，并在此基礎(chǔ)上判斷后續(xù)新聞報(bào)道與該話題的相關(guān)性，從而實(shí)現(xiàn)追蹤功能。

國內(nèi)外學(xué)者在TDT的基礎(chǔ)上提出了許多熱門話題檢測和追蹤的方法，其中一種流行的方法是基于詞匯權(quán)重，檢測文章內(nèi)容中關(guān)鍵或具有代表性的詞匯。常用的方法有Salton等提出的TF-IDF算法[6]，另一個是Bun等提出的TF*PDF算法[7]。與TF-IDF方法相比，TF*PDF算法將更多的權(quán)重賦予在整個語料庫中出現(xiàn)頻率較高的詞匯，因此，TF*PDF算法提取的關(guān)鍵詞能夠更好地反映話題的熱度，更適用于整個語料庫上的熱點(diǎn)詞匯提取。

1.2 TF*PDF算法

在傳統(tǒng)的TF*PDF算法中，某個詞匯在單個新聞渠道的權(quán)重與其在該渠道的詞頻成線性正相關(guān)，且與該渠道中包含該詞匯的文檔數(shù)成指數(shù)正相關(guān)。單詞在所有渠道中的權(quán)重為其在單個渠道中權(quán)重之和，其計(jì)算過程如下所示：

(1)

(3)

TF*PDF通過計(jì)算詞匯的詞頻以及包含該詞匯的文檔數(shù)，來尋找大多數(shù)渠道中能夠代表熱點(diǎn)話題的關(guān)鍵詞。當(dāng)用戶改變查詢的時間或類別區(qū)間時，TF*PDF算法需要遍歷區(qū)間內(nèi)的文檔，來計(jì)算詞匯在該區(qū)間內(nèi)的詞頻和包含該詞匯的文檔數(shù)，導(dǎo)致了大量的重復(fù)計(jì)算，使得傳統(tǒng)的TF*PDF算法無法滿足用戶頻繁改變查詢條件的需要。

2 問題定義

本文研究的主要問題為如何根據(jù)用戶給定的一組詞匯，快速尋找這組詞匯能夠成為熱點(diǎn)詞匯所處的最長時間區(qū)間。

定義1(時間區(qū)間T(a,b)) 語料庫的一個時間區(qū)間T(a,b)={ta,ta+1,…，tb}，其中ti表示語料庫的第i個時間間隔，也即語料庫中最小的時間單位。特殊地，T(1,Nt)表示語料庫中的整個時間區(qū)間，其中Nt表示語料庫中包含的全部時間間隔。

定義2(類別樹G) 語料庫中的新聞具有類別屬性，所有的類別構(gòu)成了一個樹狀結(jié)構(gòu)G。G中的一個子類別gci={gcx,gcx+1,…,gcy}，其中g(shù)cj表示類別gci的第j個子類別。

定義3(類別區(qū)間G(x,y)) 類別樹G的所有葉子節(jié)點(diǎn)被定義為{g1,g2,…,gNg}，則一個類別區(qū)間G(x,y)={gx,gx+1,…,gy}。特殊地，G中的每一個子類別gc都構(gòu)成一個類別區(qū)間。

定義4(詞匯列表L) 語料庫中的一個詞匯列表Lmn={Lwmn}={(w,Fwmn,dwmn)|w同時出現(xiàn)在gm和tn}，其中w是一個詞匯，F(xiàn)wmn是w在gm和tn中所有文檔的詞頻，dwmn是在gm和tn中包含w的文檔數(shù)。

定義5(基本數(shù)據(jù)結(jié)構(gòu)s) 用于存儲一個語料庫的一個基本數(shù)據(jù)結(jié)構(gòu)s={Lmn|1≤m≤Ng,1≤n≤Nt}。

定義6(Top-k熱詞Y) 所有語料庫在某個時間區(qū)間T(a,b)和一個子類別gc的Top-k熱詞為一個詞匯集合Y={w1,w2,…,wk}，且對于該區(qū)間的詞匯w∈Y,w′?Y，有Weightw≥Weightw′。

基于以上的定義，本文研究的主要問題的形式化定義如下：

定義7(熱詞最長時間區(qū)間查詢)

給定一組詞匯W={w1,w2,…,wl}，G中的一個子類別gc，查詢初始時間間隔ta，正整數(shù)k，尋找一個最長的時間區(qū)間T(a,b)，對?w∈W,?i∈(a,b)，在T(a,i)中，有w∈Y。

3 基于改進(jìn)TF*PDF的熱詞最長區(qū)間查詢方法

3.1 PC:Prefix Cube

文獻(xiàn)[12]使用Prefix Sum技術(shù)提出了一個名為Prefix Cube(PC)的存儲結(jié)構(gòu)。給定存儲一個語料庫的基本數(shù)據(jù)結(jié)構(gòu)s，首先計(jì)算其中一個詞匯w詞頻Fw的Prefix Cube表示為:

(4)

對于一個時間區(qū)間T(a,b)和一個子類別gc=G(x,y)，w在這個區(qū)間內(nèi)的詞頻Fw可以通過FPC快速計(jì)算：

FPCw(y,b)-FPCw(y,a-1)-

FPCw(x-1,b)+FPCw(x-1,b-1)

(5)

式(5)表明，F(xiàn)w在區(qū)間T(a,b)和子類別gc=G(x,y)構(gòu)成的二維區(qū)間內(nèi)的詞頻可以通過該二維區(qū)間頂點(diǎn)的FPCw來快速計(jì)算，從而避免了對該二維區(qū)間內(nèi)的全部文檔進(jìn)行迭代計(jì)算。

DPCw和FPCw同樣具有式(5)所示的性質(zhì)，在區(qū)間T(a,b)和子類別gc=G(x,y)構(gòu)成的二維區(qū)間，有:

DPCw(x-1,b)+DPCw(x-1,b-1)

(7)

當(dāng)x=y=m，a=b=n時，式(5)和式(7)可變化為：

Fw=FPCw(m,n)-FPCw(m,n-1)-

FPCw(m-1,n)+FPCw(m-1,n-1)=Fwmn

(8)

dw=DPCw(m,n)-DPCw(m,n-1)-

DPCw(m-1,n)+DPCw(m-1,n-1)=dwmn

(9)

因此，可以通過迭代的方式來計(jì)算FPCw和DPCw：

FPCw(m,n)=FPCw(m,n-1)+FPCw(m-1,n)-

FPCw(m-1,n-1)+Fwmn

(10)

DPCw(m,n)=DPCw(m,n-1)+DPCw(m-1,n)-

DPCw(m-1,n-1)+dwmn

(11)

式中：FPCw(1,1)=Fw11,DPCw(1,1)=dw11。因此FPCw和DPCw可以通過迭代的方式進(jìn)行構(gòu)建，而不需使用式(4)和式(6)對已經(jīng)計(jì)算出的所有元素進(jìn)行循環(huán)計(jì)算。接下來，將FPCw和DPCw合并，以構(gòu)建出w的Prefix Cube：PCw。最后對所有的單詞進(jìn)行迭代計(jì)算，以構(gòu)建出整個語料庫存儲s的Prefix Cube：PC。

對PC的構(gòu)建算法的詳細(xì)描述如算法1所示。

算法1構(gòu)建PC

ConstructPC(s,Nt,Ng,Q)

輸入：語料庫的基本存儲結(jié)構(gòu)s，時間間隔個數(shù)Nt，類別樹的所有葉子節(jié)點(diǎn)個數(shù)Ng，全部詞匯Q

輸出：所有單詞的Prefix Cube：PC

1:Forw∈QBegin

2: FetchFw11,dw11froms;

3: FPCw(1,1)=Fw11,DPCw(1,1)=dw11;

4:Form∈(1,Ng)Begin

5:Forn∈(1,Nt)Begin

6:FetchFwmn,dwmnfroms;

7:FPCw(m,n)=FPCw(m,n-1)+FPCw(m-1,n)-

FPCw(m-1,n-1)+Fwmn;

8:DPCw(m,n)=DPCw(m,n-1)+DPCw(m-1,n)-

DPCw(m-1,n-1)+dwmn;

9:PCw(m,n)=(w,FPCw(m,n-1),DPCw(m,n-1));

10:End

11:End

12:End

13:PC={PCw};

14:ReturnPC;

在算法1中，構(gòu)建PC需要對語料庫中的全部詞匯、時間間隔和類別樹的葉子節(jié)點(diǎn)做循環(huán)，因此，算法的時間復(fù)雜度為O(NwNgNt)。對于構(gòu)建出的PC，由于每個PCw的每個元素需要存儲w、FPCw(m,n)和DPCw(m,n)，每個PCw的空間復(fù)雜度為O(3NtNg)。因此，整個PC的空間復(fù)雜度為O(3NwNtNg)，和原始的s的空間復(fù)雜度相同。因此使用PC作為語料庫輔助存儲并不增加存儲的空間復(fù)雜度。

3.2 最長時間區(qū)間查詢

根據(jù)第2節(jié)的問題定義，本文所涉及的查詢?yōu)橛脩艚o定一組單詞、初始時間間隔、類別和k，查詢該組單詞在該類別上滿足成為熱詞的最長時間區(qū)間。這就要求算法不斷地更新時間區(qū)間，計(jì)算出詞匯的權(quán)重，以判斷詞匯是否是Top-k的熱詞。

當(dāng)使用傳統(tǒng)的TF*PDF算法時，時間區(qū)間需要不斷地被更新來計(jì)算詞匯權(quán)重以查找Top-k的熱詞，TF*PDF算法中的詞頻和包含詞匯的文檔數(shù)需要進(jìn)行大量的重復(fù)計(jì)算。而當(dāng)使用PC作為存儲結(jié)構(gòu)時，由于詞頻和文章數(shù)可以通過式(5)和式(7)直接得出，這些計(jì)算可以被避免。

當(dāng)用戶給定一組詞匯W={w1,w2,…,wl}、初始時間間隔ta、類別gc和k，查詢該組單詞在該類別上滿足成為熱詞的最長時間區(qū)間時，我們以ta為初始點(diǎn)，對ta后的時間間隔進(jìn)行遍歷以查詢熱詞，并判斷W是否在Top-k熱詞Y中，如算法2所示。

算法2PCTF：查詢最長時間區(qū)間

PCTF(W,ta,gc,k,PC,Q)

輸入：詞匯W={w1,w2,…,wl}，初始時間間隔ta，類別gc，整數(shù)k，所有語料庫的Prefix CubePC={PC1,PC2,…,PCNc}，全部詞匯Q

輸出：時間區(qū)間T(a,b)

1:b=a;

2:{gx,gx+1,…,gy}=gc;

3:Do

4:Weight=?;

5:D=?;

6:b=b+1;

7:Forc∈(1,Nc)Begin

9:lc=0;

Forw∈QBegin

12:End

13:End

14:Forw∈QBegin

15:Weightw=0;

16:Forc∈(1,Nc)Begin

22:End

23:Weight=Weight∪Weightw;

24:End

25:Y=Top-k(Weight);

26:WhileW?Y;

27:ReturnT(a,b-1);

算法2首先獲取給定類別gc的類別區(qū)間(x,y)，在7～13行，該算法計(jì)算在每個Channel中的詞頻的平方和，時間復(fù)雜度為O(NcNw)。隨后算法2依次迭代更新時間區(qū)間的終止時間間隔tb，并使用Prefix Cube查詢T(a,b)上所有單詞的權(quán)重，時間復(fù)雜度同樣為O(NcNw)。最后算法計(jì)算Top-k的熱詞，直到用戶給定的詞匯W不滿足熱詞的條件，算法返回時間區(qū)間T(a,b-1)。在計(jì)算Top-k熱詞時，使用最小堆技術(shù)，時間復(fù)雜度為O(Nwklogk)，而判斷W?Y需要O(k)的時復(fù)雜度，因此，算法的總復(fù)雜度為(b-a)O(Nwklogk+2NcNw)。

4 實(shí) 驗(yàn)

本節(jié)設(shè)計(jì)了一系列實(shí)驗(yàn)來比較PCTF算法和傳統(tǒng)的TF*PDF算法在提取熱詞并查詢熱詞所在的最長時間區(qū)間的運(yùn)行效率。

4.1 語料庫

為測試PCTF算法的效率，本文從一些著名的新聞網(wǎng)站——路透社(https://uk.reuters.com)，紐約時報(bào)(https://www.nytimes.com)和BBC(https://www.bbc.com)上收集了自2016年1月1日至2017年1月1日的新聞文章。表2列出了三個語料庫的詳細(xì)信息。

表2 語料庫詳細(xì)信息

實(shí)驗(yàn)中，渠道總數(shù)Nc=3，語料庫的最小時間單位為天。本文使用了Stanford CoreNLP對語料庫進(jìn)行了預(yù)處理，包括去除停止詞、分詞和詞形還原等。

4.2 實(shí)驗(yàn)環(huán)境

采用的實(shí)驗(yàn)環(huán)境為：Intel?Xeon(R) CPU E5-2650v3 @ 2.30 GHz×40，128 GB內(nèi)存和256 GB SSD磁盤，操作系統(tǒng)為Ubuntu Kylin 16.04，程序語言為Java (Version 1.8.0_92)。

4.3 尋找最長時間區(qū)間

(1) 改變k通過改變k，研究不同的k對PCTF算法查詢熱詞所滿足的最長時間區(qū)間的時間開銷的影響。在本次實(shí)驗(yàn)中，設(shè)置初試時間間隔為2016年6月15日(ta=288)，類別為politics(gc=politics，類別區(qū)間長度為23)，用戶給定的一組詞匯W={Trump,Clinton,Obama,President}。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 改變k時查詢時間的變化曲線

從圖 1可以看出，隨著k的增加，PCTF算法和傳統(tǒng)的TF*PDF算法查詢最大時間區(qū)間所消耗的時間均有所增加，這是因?yàn)樵谟?jì)算出所有詞匯的權(quán)重之后，算法需要計(jì)算Top-k的熱詞。此外，隨著k的增加，用戶給定詞匯滿足Top-k的最長時間區(qū)間的范圍也可能增加。因此，兩個算法的整體時間消耗均有所增加。然而，隨著k的增加，PCTF算法的時間開銷均遠(yuǎn)小于TF*PDF算法。

(2) 改變類別和用戶指定的詞匯 通過改變類別和用戶指定的關(guān)鍵詞，研究PCTF算法對于不同用戶偏好的適用性。實(shí)驗(yàn)設(shè)置初始時間間隔為2016年8月1日(ta=213)，k=50，類別和詞匯分別為：

①gc=basketball，類別區(qū)間長度為5，W={NBA,Rockets,Harden}；

②gc=football，類別區(qū)間長度為8，W={Spain,Argentina,Ronaldo,Messi}；

③gc=tennis，類別區(qū)間長度為3，W={Nadal,Federer,Final}。

實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 改變類別和關(guān)鍵詞時查詢時間變化的柱狀圖

由圖 2可以看出，對于不同的類別和用戶指定的詞匯，兩種算法在較大的類別區(qū)間上有較高的查詢時間。而與TF*PDF算法相比，PCTF算法均能以較低的查詢時間得到最大的時間區(qū)間。

(3) 改變初始時間間隔 由于一組詞匯可以在不同的時間區(qū)間內(nèi)都成為熱詞，也即該組詞匯描述的事件發(fā)生了多次，可以通過改變初始時間間隔來更加全面地尋找詞匯能夠成為熱詞的最長時間區(qū)間。

實(shí)驗(yàn)設(shè)置類別為Sports(gc=Sports，類別區(qū)間長度為14)，W={NBA,Rockets,Lakers}，k=50，初始時間間隔分別為2016年1月18日(ta=17)，2016年4月11日(ta=101)，2016年10月27日(ta=300)，2016年12月8日(ta=342)。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 改變初始時間間隔時查詢時間變化的柱狀圖

由圖3可以看出，當(dāng)改變查詢的初始時間間隔時，PCTF算法均能保持較低的查詢時間復(fù)雜度，且查詢時間較為穩(wěn)定。

通過以上的實(shí)驗(yàn)我們可以看出，PCTF算法能夠較好地應(yīng)對不同的查詢場景。當(dāng)用戶不斷改變k、查詢類別和詞匯以及查詢的初始時間間隔時，傳統(tǒng)的TF*PDF算法耗時較長，而PCTF算法均能以小于1 s的時間消耗查詢出用戶給定詞匯的最長時間區(qū)間。因此PCTF算法能夠面向不同的用戶，快速高效地對關(guān)鍵詞進(jìn)行提取，并查詢詞匯所在的最長時間區(qū)間。

5 結(jié) 語

本文對二維區(qū)間內(nèi)關(guān)鍵詞提取的在線算法進(jìn)行研究。基于Prefix Cube，對傳統(tǒng)的TF*PDF算法進(jìn)行改進(jìn)，提出了FPC、DPC的存儲結(jié)構(gòu)，快速、高效地對關(guān)鍵詞進(jìn)行提取，并能快速查詢用戶指定的詞匯成為關(guān)鍵詞的最長時間區(qū)間。PCTF算法在空間復(fù)雜度不變的情況下，降低了關(guān)鍵詞提取的時間復(fù)雜度，具有能夠面向不同偏好的用戶和較好地應(yīng)對用戶不斷更新查詢條件的優(yōu)點(diǎn)。試驗(yàn)結(jié)果表明，PCTF算法在不同查詢條件下，查詢所用時間優(yōu)于傳統(tǒng)的TF*PDF算法。在自然語言處理方面，由于本文的算法采用Stanford CoreNLP對新聞文章進(jìn)行分詞，算法對中文文檔的支持性不足。在未來的研究中，將考慮數(shù)據(jù)的更新及更加復(fù)雜的查詢，此外，將考慮使用更多中文分詞庫以增加算法對中文文檔的支持能力。