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

2(太原理工大學信息與計算機學院 山西 太原 030024)3(山西大學計算機與信息技術學院 山西 太原 030006)

0 引 言

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

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

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

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

1 高效用項集挖掘的問題模型

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

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

定義2每個項目xi∈Tj的內部效用定義為項目在會話中的頻率，表示為inter_util(xi,Tj)。

定義3每個項目xi∈Tj的總效用U(xi,Tj)計算為內部效用與外部效用的乘積：

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

(1)

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

(2)

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

(3)

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

(4)

定義7項集X的加權會話效用TWU(X)定義為：

(5)

定義8會話Tj中項集X之后的所有項集定義為Tj/X。

定義9會話Tj中項集X的剩余效用RU(X,Tj)計算為：

(6)

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

(7)

定義11會話數(shù)據(jù)庫內的項目按照TWU升序排列。

定義12最小絕對效用值定義為δ。δ的初始值設為0，挖掘過程中動態(tài)地改變δ值。

定義13高效用項集挖掘初始化階段結束的δ值定義為δl。

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

定義15D中k個效用最高的項集定義為top-k-HUI。

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

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

(8)

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

2 top-k高效用項集挖掘

2.1 三角項集效用樹(TIU-tree)數(shù)據(jù)結構

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

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

(9)

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

算法1update_TIU算法

輸入：項i在T中的位置，會話T

輸出：TIU結構

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效用累加屬性。假設X與Y是兩個任意不想交的項集(均為I的子集)，那么U(X)+U(Y)≥U(X∪Y)。

證明：屬性的左式可擴展為：

比較左式與右式的擴展結果，左式總是大于等于右式。

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

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

(10)

證明：式(10)的第1次擴展是屬性1的應用，第2次擴展表示各個項的效用值之和不小于X的效用值，所以ULB(Y)并未被過度估計。

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

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

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

定義18PQ_LB_TIU定義為項集的所有估計效用：

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

q?I,|q|≤3}

(11)

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

算法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

//獲得項集的第一項

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個值；

/*提高最小效用值*/

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

證明：對于TIU中每個連續(xù)的項目序列，PQ_LB_TIU中保存幾個項集的估計下限。因為這些項集子集均為當前HUI的一部分，所以將δ提高至第K大的效用值不會影響最終結果的正確性。

2.3 基于三角項集樹的高效用項集(TIU_HUI)挖掘算法

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

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

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

Step2.1基于定義11排列會話中的項目；

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

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

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

TIU_HUI算法的Step 3，設計了搜索算法來搜索話題候選項集樹，見3.5節(jié)。本方法在每次迭代中動態(tài)地改變δ值，所以每次迭代僅產生top-k的HUI，降低了計算成本與存儲成本。

算法3TIU_HUI算法

輸入：D,K

輸出：top-k-HUI

1.掃描D，計算所有1-項集的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. 建立每個會話的UL；

/*文獻[14]*/

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

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

/*算法2*/

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

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

3 基于高效用模式挖掘的主題預測

TIU_HUI算法的目標是同時搜索會話中頻繁且高價值的模式集。

3.1 算法總體設計

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

圖1 消息流中會話與批的關系圖

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

3.2 計算詞匯的效用

假設一個會話為Ti，話題流為TS=T1,T2,T3,…。采用滑動窗口技術提取話題流，TS表示一個話題序列，B1,B2,B3,…表示一批話題。外部效用表示了每個詞匯在檢測新主題時的重要性，TIU_HUI產生的高效用模式明顯地獨立于外部效用值。相鄰兩批的詞匯頻率是變化的，所以應當計算每批的詞匯效用。

每個話題的字符數(shù)量是有限的，所以特殊事件相關的關鍵詞頻率會快速升高。批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的外部效用定義為關于diff(i)與rate(i)的方程：

(14)

因為diff(i)≤0說明詞匯i的頻率沒有增加，所以詞匯i的效用設為0，此類詞匯不可能是新話題的關鍵詞匯。rate(i)表示詞匯頻率變化率，該值可能極大。

3.3 效用值的下限

(15)

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

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

(16)

將δ定義為：

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

(17)

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

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

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

3.5 提取話題模式

為了高效地刪除候選話題模式中的冗余模式，設計了一個話題搜索樹結構Topic-tree。Topic-tree的每個節(jié)點包含一個項目標簽與一個索引域，Topic-tree初始化為一個根節(jié)點，節(jié)點的符號與頭表均置空，Topic-tree的候選話題模式插入方法為：

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

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

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

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

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

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

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

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

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

(c) 加入(c,d,f)(d) 加入(c,b,d,f)圖3 Topic-tree的構建過程實例圖

在構建的Topic-tree中，從root節(jié)點到葉節(jié)點的路徑對應一個話題模式，采用模式效用指標評估話題模式的優(yōu)劣，模式效用定義為：

(18)

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

4 實 驗

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

4.1 實驗數(shù)據(jù)集

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

4.2 性能指標的設定

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

話題召回率定義為：

(19)

式中:A為未能檢測的標定話題；B為成功檢測的正定話題。

話題的相關性定義為：

(20)

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

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

4.3 話題檢測的性能

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

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

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

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

4.4 話題檢測的時間效率

表1為四個話題檢測算法對于消息流數(shù)據(jù)集的話題檢測平均時間?？梢钥闯觯舅惴▽τ贔A數(shù)據(jù)集與US數(shù)據(jù)集的檢測時間低于其他三個算法，對ST數(shù)據(jù)集的檢測時間略高于KBTE算法。FA、ST、US三個數(shù)據(jù)集的時段分別為1分鐘、60分鐘、10分鐘，而本算法對于三個數(shù)據(jù)集的檢測時間分別為0.31秒、8.80秒、3.83秒，因此本算法具有較快的響應時間。

表1 話題檢測算法對于三個消息流的檢測時間 s

5 結 語

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

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