基于快速高效用項(xiàng)集挖掘的大規(guī)模消息流預(yù)測(cè)算法研究與應(yīng)用

穆曉芳 鄧紅霞 郭虎升 趙 鵬(太原師范學(xué)院計(jì)算機(jī)系 山西 太原 0069)

2(太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院 山西 太原 030024)3(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006)

0 引 言

隨著社交媒體、新聞APP以及自動(dòng)推薦系統(tǒng)的廣泛應(yīng)用，導(dǎo)致網(wǎng)絡(luò)中每天產(chǎn)生許多突發(fā)事件，成功預(yù)測(cè)出這些突發(fā)事件有助于遏制惡劣事件的傳播與發(fā)酵，或者及時(shí)地預(yù)知網(wǎng)絡(luò)的熱點(diǎn)信息[1-2]。網(wǎng)絡(luò)的話題預(yù)測(cè)方法大體可分為三種類(lèi)型[3]：(1) 搜索文檔集中的共生詞組，將其作為特征；(2) 比較文檔或消息流之間的相似性；(3) 通過(guò)預(yù)測(cè)詞匯關(guān)于話題的概率分布。上述三類(lèi)預(yù)測(cè)方法的計(jì)算成本與存儲(chǔ)成本均較高，難以應(yīng)用于大規(guī)模的互聯(lián)網(wǎng)場(chǎng)景。

根據(jù)許多相關(guān)研究的成果[4]，對(duì)話題中的關(guān)鍵詞進(jìn)行分析，便足以識(shí)別出突發(fā)話題的趨勢(shì)，僅分析話題的關(guān)鍵詞極大地降低了處理的難度[5]。詞頻是判斷突發(fā)話題的一個(gè)核心判斷依據(jù)，詞頻高低反映了其熱門(mén)程度，但僅僅依靠詞頻一個(gè)指標(biāo)所獲得的檢測(cè)準(zhǔn)確率較低，因此許多研究人員將詞頻與其他的指標(biāo)進(jìn)行了結(jié)合，例如：詞頻與傳播影響力度量[6]、信息密度變化[7]、粉絲關(guān)系和用戶(hù)活躍度的話題傳播模型[8]等。這些方法對(duì)突發(fā)話題的評(píng)估指標(biāo)進(jìn)行了深入的分析，但在話題檢測(cè)的過(guò)程中需要針對(duì)大規(guī)模的消息流進(jìn)行搜索與排序處理，該處理過(guò)程的計(jì)算成本與存儲(chǔ)成本均十分龐大。

高效用項(xiàng)集(High Utility Itemset,HUI)挖掘[9]是一種針對(duì)實(shí)時(shí)消息流的處理模型，該模型中包括了多種有效的數(shù)據(jù)結(jié)構(gòu)，例如：PreHU-tree[9]、HUIL-Tree[10]等，能夠有效地提高挖掘的時(shí)間效率與存儲(chǔ)效率。當(dāng)前的top-k高效用頻繁項(xiàng)集挖掘算法[11-12]對(duì)于稀疏數(shù)據(jù)庫(kù)的挖掘效率較好，但對(duì)于密集數(shù)據(jù)集的挖掘效率較低。

消息流的話題數(shù)據(jù)是一種大規(guī)模的密集數(shù)據(jù)集，為了提高top-k高效用項(xiàng)集挖掘算法對(duì)于話題類(lèi)密集數(shù)據(jù)集的挖掘效果，設(shè)計(jì)了動(dòng)態(tài)的top-k項(xiàng)集挖掘算法，在挖掘的早期階段大幅度地提高最小效用閾值。在挖掘過(guò)程中設(shè)計(jì)了三角項(xiàng)集效用樹(shù)結(jié)構(gòu)(Triangle Itemset Utility Tree,TIU-tree)數(shù)據(jù)結(jié)構(gòu)來(lái)保存項(xiàng)集的效用信息，降低了保存效用信息的存儲(chǔ)成本。針對(duì)話題設(shè)計(jì)了專(zhuān)門(mén)的Topic-tree數(shù)據(jù)結(jié)構(gòu)，有助于提高候選項(xiàng)集的搜索速度與存儲(chǔ)效率。

1 高效用項(xiàng)集挖掘的問(wèn)題模型

設(shè)I={i1,i2,…,im}為一個(gè)項(xiàng)集，Tj={xl|l=1,2,…,Nj,?xl∈I}為一個(gè)會(huì)話，Nj是會(huì)話Tj的項(xiàng)目數(shù)量。若干的會(huì)話組成一個(gè)會(huì)話數(shù)據(jù)庫(kù)D，D={T1,T2,…,Tn}，n為數(shù)據(jù)庫(kù)的會(huì)話總量。集合X{x1,x2,…,xp}?I表示p-項(xiàng)集。

定義1每個(gè)項(xiàng)目xi∈I的外部效用表示為ext_util(xi)。本模型中外部效用反映了每個(gè)詞匯在檢測(cè)新主題時(shí)的重要性。

定義2每個(gè)項(xiàng)目xi∈Tj的內(nèi)部效用定義為項(xiàng)目在會(huì)話中的頻率，表示為inter_util(xi,Tj)。

定義3每個(gè)項(xiàng)目xi∈Tj的總效用U(xi,Tj)計(jì)算為內(nèi)部效用與外部效用的乘積：

U(xi,Tj)=ext_util(xi)·iter_util(xi,Tj)

(1)

定義4會(huì)話Tj中項(xiàng)集X的效用表示為U(X,Tj)：

(2)

定義5數(shù)據(jù)庫(kù)D中項(xiàng)集X的效用表示為U(X)：

(3)

定義6會(huì)話Tj的會(huì)話效用TU(Tj)定義為：

(4)

定義7項(xiàng)集X的加權(quán)會(huì)話效用TWU(X)定義為：

(5)

定義8會(huì)話Tj中項(xiàng)集X之后的所有項(xiàng)集定義為T(mén)j/X。

定義9會(huì)話Tj中項(xiàng)集X的剩余效用RU(X,Tj)計(jì)算為：

(6)

定義10數(shù)據(jù)庫(kù)D中項(xiàng)集X的剩余效用RU(X)計(jì)算為：

(7)

定義11會(huì)話數(shù)據(jù)庫(kù)內(nèi)的項(xiàng)目按照TWU升序排列。

定義12最小絕對(duì)效用值定義為δ。δ的初始值設(shè)為0，挖掘過(guò)程中動(dòng)態(tài)地改變?chǔ)闹怠?/p>

定義13高效用項(xiàng)集挖掘初始化階段結(jié)束的δ值定義為δl。

定義14如果一個(gè)項(xiàng)集X的效用U(X)大于等于閾值δ，那么項(xiàng)集X定義為高效用項(xiàng)集。

定義15D中k個(gè)效用最高的項(xiàng)集定義為top-k-HUI。

定義16最優(yōu)的最小效用閾值δF定義為：

δF=min{U(X)|X∈top-k-HUI}

(8)

給定一個(gè)會(huì)話數(shù)據(jù)庫(kù)D與期望的HUI數(shù)量K，top-k高效用挖掘問(wèn)題簡(jiǎn)單描述為從D中選出K個(gè)效用最高的HUI。本文的目標(biāo)則是從D中高效率地挖掘出top-k-HUI。

2 top-k高效用項(xiàng)集挖掘

2.1 三角項(xiàng)集效用樹(shù)(TIU-tree)數(shù)據(jù)結(jié)構(gòu)

設(shè)(xi..xj)表示連續(xù)的項(xiàng)目序列,即(xi..xj)={xi,xi+1,xi+2,…,xj}。TIU-tree結(jié)構(gòu)是一種保存連續(xù)項(xiàng)集效用信息的三角矩陣：

LIU(xi,xj)=LIU((xi..xj))=LIU({xi,xi+1,…,xj})=

(9)

根據(jù)會(huì)話數(shù)據(jù)庫(kù)產(chǎn)生每對(duì)連續(xù)項(xiàng)集的TIU-tree，具體方法如算法1所示。理論上TIU-tree所需的空間為O(m2)，m為項(xiàng)目數(shù)量，TIU-tree結(jié)構(gòu)的入口數(shù)量?jī)H為O(L2)，L為會(huì)話的平均長(zhǎng)度。TIU-tree結(jié)構(gòu)有助于獲取連續(xù)項(xiàng)集長(zhǎng)序列的效用。估計(jì)效用共生結(jié)構(gòu)(Estimated Utility Co-occurrence Structure,EUCS)[13]是一種保存效用信息的常見(jiàn)數(shù)據(jù)結(jié)構(gòu)，EUCS結(jié)構(gòu)對(duì)于挖掘HUI短序列的效果較好，TIU-tree結(jié)構(gòu)對(duì)于密集型數(shù)據(jù)集的效果優(yōu)于EUCS結(jié)構(gòu)。

算法1update_TIU算法

輸入：項(xiàng)i在T中的位置，會(huì)話T

輸出：TIU結(jié)構(gòu)

1.next_item=xi；

2.cum_util=U(xi,T)；

3.for eachj∈[0,i-1] do

4.cur_util=xj,xj∈T；

5. ifcur_item

6.cum_util+=U(curr_item,T)；

7.TIU(curr_item,xi)+=cum_util；

2.2 修改閾值的策略

屬性1效用累加屬性。假設(shè)X與Y是兩個(gè)任意不想交的項(xiàng)集(均為I的子集)，那么U(X)+U(Y)≥U(X∪Y)。

證明：屬性的左式可擴(kuò)展為：

比較左式與右式的擴(kuò)展結(jié)果，左式總是大于等于右式。

屬性2效用下限屬性。項(xiàng)集Y的效用下限表示為ULB(Y)，對(duì)于任意項(xiàng)集X?I，ULB(Y)的計(jì)算為：

ULB(Y)=U(X∪Y)-U(X)=

(10)

證明：式(10)的第1次擴(kuò)展是屬性1的應(yīng)用，第2次擴(kuò)展表示各個(gè)項(xiàng)的效用值之和不小于X的效用值，所以ULB(Y)并未被過(guò)度估計(jì)。

根據(jù)屬性2，使用項(xiàng)集Y的超集X∪Y與項(xiàng)集X來(lái)估計(jì)Y的效用下限值。

結(jié)合中國(guó)的實(shí)際情況來(lái)說(shuō)，社區(qū)服務(wù)點(diǎn)是以服務(wù)于區(qū)域生活、商業(yè)中心為目的的快捷、便利的銀行服務(wù)場(chǎng)所。作為余額寶服務(wù)的延伸，社區(qū)服務(wù)點(diǎn)將承擔(dān)起未來(lái)開(kāi)拓零售業(yè)務(wù)市場(chǎng)的重任。站在余額寶的業(yè)務(wù)經(jīng)營(yíng)角度，社區(qū)服務(wù)點(diǎn)的發(fā)展將成為余額寶改變傳統(tǒng)業(yè)務(wù)模式，從“坐商”走向“行商”的重要一步。

定義17TIULB(x,y,q)定義為一個(gè)項(xiàng)集的估計(jì)下限，其中q是從序列(x..y)中刪除的項(xiàng)集，q?I。

定義18PQ_LB_TIU定義為項(xiàng)集的所有估計(jì)效用：

PQ_LB_TIU={TIULB(x,y,q)|(x..y)∈TIU,

q?I,|q|≤3}

(11)

本方法產(chǎn)生項(xiàng)集的子集，根據(jù)效用下限屬性(屬性2)估計(jì)項(xiàng)集的下限。將q設(shè)為定值3，從而限制產(chǎn)生的項(xiàng)集子集數(shù)量。算法2是通過(guò)修改閾值產(chǎn)生項(xiàng)集子集的算法，其中包括了效用計(jì)算與下限估計(jì)兩個(gè)重要步驟。

算法2修改閾值的算法

輸入：TIU,PQ_TIU,PQ_LB_TIU,δ

輸出：δ

1.for eachx,y∈TIUdo

2. for eacha∈(item1..itemn) do

3.util_LB=TIU(x,y)-U(a)；

4. ifutil_LB≥δ

5. 將util_LB加入PQ_LB_TIU中；

6. for eachb=start_item(a)∈(item1..itemn) do

//獲得項(xiàng)集的第一項(xiàng)

7.util_LB=TIU(x,y)-U(a)-U(b)；

8. ifutil_LB≥δ

9. 將util_LB加入PQ_LB_TIU中；

10. for eachc=succ(b)∈(item1..itemn) do

11.util_LB=TIU(x,y)-U(a)-U(b)-U(c)；

12. ifutil_LB≥δ

13. 將util_LB加入PQ_LB_TIU中；

14.if |PQ_ALL={PQ_TIU∪PQ_LB_TIU}|≥K

15.δ=PQ_ALL中第K個(gè)值；

/*提高最小效用值*/

屬性3TIU的下限。PQ_ALL={PQ_TIU∪PQ_LB_TIU}，如果|PQ_ALL|≥K，那么δ可提高至PQ_ALL中第K個(gè)值。

證明：對(duì)于TIU中每個(gè)連續(xù)的項(xiàng)目序列，PQ_LB_TIU中保存幾個(gè)項(xiàng)集的估計(jì)下限。因?yàn)檫@些項(xiàng)集子集均為當(dāng)前HUI的一部分，所以將δ提高至第K大的效用值不會(huì)影響最終結(jié)果的正確性。

2.3 基于三角項(xiàng)集樹(shù)的高效用項(xiàng)集(TIU_HUI)挖掘算法

如算法3所示，TIU_HUI算法是基于一階段效用列表的高效用項(xiàng)集挖掘算法。其步驟為：

Step1掃描數(shù)據(jù)庫(kù)D，計(jì)算所有1-項(xiàng)集的TWU。

Step2采用3.3節(jié)的方法確定δ，δ的初始值設(shè)為0。

Step2.1基于定義11排列會(huì)話中的項(xiàng)目；

Step2.2創(chuàng)建一個(gè)TIU矩陣，更新矩陣中的效用值；

Step2.3建立一個(gè)效用列表(Utility List,UL)。

Step3采用TIU的修改閾值策略來(lái)修改δ值(算法3的第9行)。

TIU_HUI算法的Step 3，設(shè)計(jì)了搜索算法來(lái)搜索話題候選項(xiàng)集樹(shù)，見(jiàn)3.5節(jié)。本方法在每次迭代中動(dòng)態(tài)地改變?chǔ)闹?，所以每次迭代僅產(chǎn)生top-k的HUI，降低了計(jì)算成本與存儲(chǔ)成本。

算法3TIU_HUI算法

輸入：D,K

輸出：top-k-HUI

1.掃描D，計(jì)算所有1-項(xiàng)集的TWU；

2.for eachTs∈Ddo

3.newT={x|TWU(x)≥δ,?x∈Ts}；

4. 排列newT；

/*定義11*/

5. for eachxi∈Tsdo

6.update_TIU(i,Ts)；

/*算法1*/

7. 建立每個(gè)會(huì)話的UL；

/*文獻(xiàn)[14]*/

8.根據(jù)TIU計(jì)算PQ_TIU；

9.Modifythreshold_LB_TIU(TIU,PQ_TIU,{},δ)；

/*算法2*/

10.top-k-HUI=serarch_tree(?,UL,δ)；

/*3.5節(jié)的Topic_tree搜索策略*/

3 基于高效用模式挖掘的主題預(yù)測(cè)

TIU_HUI算法的目標(biāo)是同時(shí)搜索會(huì)話中頻繁且高價(jià)值的模式集。

3.1 算法總體設(shè)計(jì)

采用TIU_HUI實(shí)現(xiàn)對(duì)突發(fā)主題的檢測(cè)。圖1為消息流中會(huì)話與批的關(guān)系圖，圖2為本文方法的流程圖，總體的過(guò)程包括了詞匯效用的計(jì)算與最小效用的決定，通過(guò)TIU_HUI產(chǎn)生候選話題模式。

圖1 消息流中會(huì)話與批的關(guān)系圖

圖2 本文方法的總體流程圖

3.2 計(jì)算詞匯的效用

假設(shè)一個(gè)會(huì)話為T(mén)i，話題流為T(mén)S=T1,T2,T3,…。采用滑動(dòng)窗口技術(shù)提取話題流，TS表示一個(gè)話題序列，B1,B2,B3,…表示一批話題。外部效用表示了每個(gè)詞匯在檢測(cè)新主題時(shí)的重要性，TIU_HUI產(chǎn)生的高效用模式明顯地獨(dú)立于外部效用值。相鄰兩批的詞匯頻率是變化的，所以應(yīng)當(dāng)計(jì)算每批的詞匯效用。

每個(gè)話題的字符數(shù)量是有限的，所以特殊事件相關(guān)的關(guān)鍵詞頻率會(huì)快速升高。批Bt中詞匯i的頻率表示為f(Bt,i)，批BL與批BL-1中詞匯i的頻率差異定義為diff(i)：

diff(i)=f(BL,i)-f(BL-1,i)

(12)

如果diff(i)>0，那么詞匯i的頻率增加；如果diff(i)<0，詞匯i的頻率則降低。將批BL與BL-1之間詞匯i的頻率變化率定義為rate(i)：

(13)

如果rate(i)>1，那么詞匯i的頻率提高；如果rate(i)<1，詞匯i的頻率則降低。批BL中詞匯i的外部效用定義為關(guān)于diff(i)與rate(i)的方程：

(14)

因?yàn)閐iff(i)≤0說(shuō)明詞匯i的頻率沒(méi)有增加，所以詞匯i的效用設(shè)為0，此類(lèi)詞匯不可能是新話題的關(guān)鍵詞匯。rate(i)表示詞匯頻率變化率，該值可能極大。

3.3 效用值的下限

(15)

將式(15)右側(cè)的3項(xiàng)分別表示為α、β、γ，那么，第1項(xiàng)α=∑tu(T)/∑l(T)表示詞集X屬于某個(gè)消息流T的平均效用，第2項(xiàng)β=∑l(T)/s(X)表示含有詞集X的消息流平均長(zhǎng)度，第3項(xiàng)γ=s(X)表示含有詞集X的消息流數(shù)量。

消息流的話題長(zhǎng)度動(dòng)態(tài)變化，包含的詞匯量也隨之改變，將選擇的詞匯比例表示為ρ，為消息流中話題的詞匯數(shù)量設(shè)立上下界。假設(shè)批BL中所有的詞匯數(shù)量為S，那么詞匯量計(jì)算為：

(16)

將δ定義為：

δ=avg(α)×avg(β)×avg(γ)

(17)

式中:avg(α)、avg(β)、avg(γ)分別表示α、β、γ的平均值。δ反映了X中含有關(guān)鍵詞匯的TWU，并且動(dòng)態(tài)地計(jì)算當(dāng)前消息流的δ。

3.4 基于高效用模式挖掘的候選話題模式

將3.2節(jié)、3.3節(jié)所獲得關(guān)于批BL的信息輸入TIU_HUI算法，產(chǎn)生滿足TWU(X)≥δ的高效用模式X。在TIU_HUI算法中，首先計(jì)算每個(gè)詞集的TWU，再刪除TWU小于δ的詞匯，最后將剩下的詞匯按照TWU值升序排列重建話題集。高效用模式挖掘重建的話題集作為候選話題模式。

3.5 提取話題模式

為了高效地刪除候選話題模式中的冗余模式，設(shè)計(jì)了一個(gè)話題搜索樹(shù)結(jié)構(gòu)Topic-tree。Topic-tree的每個(gè)節(jié)點(diǎn)包含一個(gè)項(xiàng)目標(biāo)簽與一個(gè)索引域，Topic-tree初始化為一個(gè)根節(jié)點(diǎn)，節(jié)點(diǎn)的符號(hào)與頭表均置空，Topic-tree的候選話題模式插入方法為：

Step1如果頭表中不存在i1的節(jié)點(diǎn)，則創(chuàng)建一條從根節(jié)點(diǎn)發(fā)出的路徑root→i1→i1→…→in，跳至Step 3，更新頭表。

Step2如果頭表中存在i1的節(jié)點(diǎn)，那么遍歷頭表中節(jié)點(diǎn)i1的路徑L。

Step2.1如果遍歷L的過(guò)程中發(fā)現(xiàn)i2,i3,…,in，那么結(jié)束節(jié)點(diǎn)的插入操作。

Step2.2如果遍歷L的過(guò)程中未能發(fā)現(xiàn)i2,i3,…,in，那么創(chuàng)建路徑root→i1→i1→…→in，并且與已存在的根節(jié)點(diǎn)-葉節(jié)點(diǎn)路徑共享前綴項(xiàng)。跳至Step 3，更新頭表。

Step3對(duì)于新創(chuàng)建的節(jié)點(diǎn)ik(k=1,2,…,n)。

Step3.1如果頭表中不存在ik的節(jié)點(diǎn)，那么在頭表中加入新的ik節(jié)點(diǎn)，并且建立頭表中ik到樹(shù)中ik的索引。

Step3.2如果頭表中存在ik的節(jié)點(diǎn)，那么建立從索引L最后一個(gè)節(jié)點(diǎn)到樹(shù)中節(jié)點(diǎn)ik的索引。

如果候選話題模式的插入順序發(fā)生變化，那么Topic-tree也會(huì)發(fā)生微小的改變。TIU_HUI通過(guò)一些規(guī)則產(chǎn)生候選話題模式，因此本文可通過(guò)按照TIU_HUI生成的順序插入所有的候選話題模式，從而保持Topic-tree穩(wěn)定。Topic-tree的構(gòu)建復(fù)雜度為O(nlw)，其中:n為候選話題模式的數(shù)量；l是候選話題模式的最大長(zhǎng)度；w是Topic-tree的寬度。圖3為T(mén)opic-tree的構(gòu)建過(guò)程實(shí)例圖，假設(shè)按順序插入候選話題模式(e,c,b,d)、(e,c,d)、(c,d,f)、(c,b,d,f)。圖3(a)是第一個(gè)模式(e,c,b,d)加入樹(shù)的情況，因?yàn)槌跏蓟^表中不存在節(jié)點(diǎn)e，因此在頭表中加入一條路徑root→e→c→b→d；(b)是第二個(gè)模式(e,c,d)加入樹(shù)的情況，頭表中已經(jīng)存在節(jié)點(diǎn)e，檢查節(jié)點(diǎn)e所有列表中是否存在(c,d)，因此不會(huì)重新加入(e,c,d)；(c)是第三個(gè)模式(c,d,f)加入樹(shù)的情況，因?yàn)轭^表中存在節(jié)點(diǎn)c，檢查節(jié)點(diǎn)c所有列表中是否存在(d,f)，路徑root→e→c→b→d中不存在節(jié)點(diǎn)f，因此，加入新鏈接root→c→d→f，并且更新頭表；(d)是第四個(gè)模式(c,b,d,f)加入樹(shù)的情況，路徑root→e→c→b→d中存在(b,d)但不存在節(jié)點(diǎn)f，路徑root→c→d→f中存在(d,f)但不存在b，因此路徑為root→c→b→d→f，該路徑共享前綴節(jié)點(diǎn)c。

(a) 加入(e,c,b,d)(b) 加入(e,c,d)

(c) 加入(c,d,f)(d) 加入(c,b,d,f)圖3 Topic-tree的構(gòu)建過(guò)程實(shí)例圖

在構(gòu)建的Topic-tree中，從root節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑對(duì)應(yīng)一個(gè)話題模式，采用模式效用指標(biāo)評(píng)估話題模式的優(yōu)劣，模式效用定義為：

(18)

式中:PU表示模式中詞集的外部效用之和，選出所有模式的top-k模式。對(duì)于每批消息流選出候選話題模式，并將候選集組成一個(gè)Topic-tree，隨著滑動(dòng)窗口移動(dòng)，創(chuàng)建新的Topic-tree。

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

實(shí)驗(yàn)環(huán)境為Dell工作站，配置為：Intel Xeon 3.7 GHz處理器，64 GB主內(nèi)存，8 GB二級(jí)緩存，Linux操作系統(tǒng)。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

采用文獻(xiàn)[15]的數(shù)據(jù)集，分別為三個(gè)子集FA Cup Final(FA) 、Super Tuesday(ST)、US Elections(US)，這三個(gè)數(shù)據(jù)集是2012年的國(guó)際性事件。FA數(shù)據(jù)集共包含360個(gè)時(shí)段，每個(gè)時(shí)段包括1分鐘的推文。標(biāo)定數(shù)據(jù)包含了13個(gè)時(shí)段的13個(gè)話題數(shù)據(jù)。ST數(shù)據(jù)集共包含24個(gè)時(shí)段，每個(gè)時(shí)段包括60分鐘的推文。標(biāo)定數(shù)據(jù)包括8個(gè)時(shí)段的22個(gè)話題數(shù)據(jù)。US數(shù)據(jù)集共包含216個(gè)時(shí)段，每個(gè)時(shí)段包括10分鐘的推文。標(biāo)定數(shù)據(jù)包括26個(gè)時(shí)段的64個(gè)話題數(shù)據(jù)。

4.2 性能指標(biāo)的設(shè)定

采用話題召回率與話題相關(guān)性作為話題檢測(cè)的性能指標(biāo)，話題檢測(cè)方法發(fā)現(xiàn)的話題包括所有的關(guān)鍵詞均屬于標(biāo)定話題，則認(rèn)為發(fā)現(xiàn)的話題被成功檢測(cè)。話題召回率為在標(biāo)定話題中話題的檢測(cè)率。話題相關(guān)性是發(fā)現(xiàn)的話題與標(biāo)定話題的相似性。

話題召回率定義為：

(19)

式中:A為未能檢測(cè)的標(biāo)定話題；B為成功檢測(cè)的正定話題。

話題的相關(guān)性定義為：

(20)

式中:C為與標(biāo)定話題匹配的話題數(shù)量；D為與標(biāo)定話題不匹配的話題數(shù)量。

選擇其他三個(gè)不同類(lèi)型的話題檢測(cè)算法與本算法進(jìn)行比較，分別為：基于特征的算法SFPM[16]、基于圖模式的方法KBTE[17]、基于話題概率模型的檢測(cè)方法WEEC[18]。這些方法均為近年三個(gè)不同類(lèi)型的話題檢測(cè)算法。

4.3 話題檢測(cè)的性能

圖4比較了4個(gè)話題檢測(cè)算法對(duì)于3個(gè)消息流的話題檢測(cè)效果。FA數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明本算法的話題召回率最高，而SFPM的召回率為0.846，SFPM的結(jié)果優(yōu)于KBTE與WEEC兩個(gè)算法，但是比本算法大約低8%。本算法對(duì)于ST數(shù)據(jù)集的話題召回率約為0.364，SFPM的話題召回率依然高于其他兩個(gè)算法，但是比本算法大約低5%。本算法對(duì)于US數(shù)據(jù)集的話題召回率約為0.453，高于其他三個(gè)算法。此外，本算法對(duì)于FA、ST兩個(gè)數(shù)據(jù)集的話題相關(guān)性結(jié)果優(yōu)于其他三個(gè)算法，但對(duì)于US數(shù)據(jù)集的話題相關(guān)性結(jié)果略低于KBTE。

(a) FA數(shù)據(jù)集

(b) ST數(shù)據(jù)集

(c) FA數(shù)據(jù)集圖4 話題檢測(cè)算法對(duì)于三個(gè)消息流的檢測(cè)性能

4.4 話題檢測(cè)的時(shí)間效率

表1為四個(gè)話題檢測(cè)算法對(duì)于消息流數(shù)據(jù)集的話題檢測(cè)平均時(shí)間。可以看出，本算法對(duì)于FA數(shù)據(jù)集與US數(shù)據(jù)集的檢測(cè)時(shí)間低于其他三個(gè)算法，對(duì)ST數(shù)據(jù)集的檢測(cè)時(shí)間略高于KBTE算法。FA、ST、US三個(gè)數(shù)據(jù)集的時(shí)段分別為1分鐘、60分鐘、10分鐘，而本算法對(duì)于三個(gè)數(shù)據(jù)集的檢測(cè)時(shí)間分別為0.31秒、8.80秒、3.83秒，因此本算法具有較快的響應(yīng)時(shí)間。

表1 話題檢測(cè)算法對(duì)于三個(gè)消息流的檢測(cè)時(shí)間 s

5 結(jié) 語(yǔ)

采用高效用項(xiàng)集挖掘方法處理消息流突發(fā)話題檢測(cè)問(wèn)題，分別設(shè)立了項(xiàng)集的內(nèi)部效用與外部效用。設(shè)計(jì)了三角項(xiàng)集樹(shù)的數(shù)據(jù)結(jié)構(gòu)保存項(xiàng)集的效用信息，降低內(nèi)存的存儲(chǔ)成本。設(shè)計(jì)了專(zhuān)門(mén)的話題Topic-tree數(shù)據(jù)結(jié)構(gòu)，提高候選項(xiàng)集的搜索速度與存儲(chǔ)效率。設(shè)計(jì)了動(dòng)態(tài)的top-k項(xiàng)集挖掘算法，在挖掘的早期階段大幅度地提高最小效用閾值，降低候選項(xiàng)集的產(chǎn)生數(shù)量。

本算法通過(guò)高效用挖掘技術(shù)預(yù)測(cè)消息流的熱門(mén)話題，是一種新穎的設(shè)計(jì)方案，實(shí)現(xiàn)了較好的檢測(cè)性能與較快的響應(yīng)時(shí)間。本算法的局限性主要是僅能分析高效用的詞匯，對(duì)于新聞消息流、金融消息流等專(zhuān)門(mén)領(lǐng)域的預(yù)測(cè)處理容易受到冗余信息的影響。未來(lái)的研究重點(diǎn)是將本算法應(yīng)用于新聞消息流、金融消息流等領(lǐng)域，針對(duì)專(zhuān)門(mén)的領(lǐng)域給出相應(yīng)的效用評(píng)估方法，準(zhǔn)確地預(yù)測(cè)出重大的突發(fā)新聞與金融災(zāi)難。