基于短文本信息流的回顧式話題識別模型

周 泓，劉金嶺，王新功

(1. 淮陰工學院 計算機工程學院，江蘇 淮安 223005；2. 滄州師范學院 計算機系，河北 滄州 061000)

?

基于短文本信息流的回顧式話題識別模型

周 泓1，劉金嶺1，王新功2

(1. 淮陰工學院 計算機工程學院，江蘇 淮安 223005；2. 滄州師范學院 計算機系，河北 滄州 061000)

近幾年來，短文本信息流廣泛應用于一些全民媒體，它在公開傳遞信息同時攜帶了豐富且具有極大價值的信息資源。該文提出了一種回顧式話題識別模型，改進了權值計算方法，有效提取了具有較強分辨話題能力的關鍵詞，在聚類過程中將BIC值作為話題類別合并依據，提高了聚類的準確率。通過進行時間段分隔和去掉孤立點信息提高了算法的效率。實驗結果表明，該方法有效地提高了短文本信息流的話題檢測準確率和效率。

短文本；信息流；話題識別；聚類

1 引言

在這個信息技術日新月異的年代，短文本信息流在生活中隨處可見，如手機短信、網絡即時通信、微博、微信、論壇等。短文本通常指內容較短的文本，多數字數不超過140，其在傳遞過程中除了顯式的字面信息外，還蘊藏著豐富且極具價值的隱式信息資源。在面對海量短文本動態信息時，如何利用計算機高速的計算能力，自動識別、鎖定、收集、跟蹤、預判信息流中蘊含的熱點話題或突發事件等問題，具有較高的學術研究價值及現實意義，可廣泛應用于如信息安全、輿情分析及預警等多個領域。話題識別分為在線話題識別和回顧式話題識別兩個研究方向，在線話題識別就是在線檢測當前所到達的短信文本所屬話題，回顧式話題識別就是檢測已接收到的短文本信息流中尚未發現的話題，這些檢測都是在缺乏話題先驗知識的情況下把短文本信息流中內容相似的無標簽短文本組織到一塊，這就需要將短文本信息流進行聚類。但是短文本信息流的聚類與傳統文本聚類有兩個不同之處，一是它具有時序性，短文本信息流的短文本是按時間有序的；二是話題具有生存周期： 產生(提出)→發展(熱議)→消失(趨冷)，而傳統的文本聚類只是把與話題內容相近的文本聚類到一起。本文所研究的是回顧式話題識別。一個話題通常包含與信息相關的若干方面，即由若干子話題構成，因此無法用一個中心向量來概括。以2012年備受關注的“毒膠囊”話題為例，其是圍繞著“問題膠囊子話題”、“工業明膠子話題”、“鉻超標子話題”、“皮革廢料子話題”、“果凍子話題”、“老酸奶子話題”、“黑心藥子話題”、“食品藥品安全子話題”、“食品藥品監管子話題”、“違規生產子話題”等眾多子話題展開的。而這些子話題中又富含該話題的一系列關鍵詞，如毒膠囊、黑心藥、政府、衛生部、國家食藥監局、國家質量總局、明膠、鉻、皮革、四川蜀中、修正藥業、通化金馬等，這些關鍵詞對區分話題無疑是比較重要的，但若是只依賴于關鍵詞來區分話題，其檢測性能卻是有限的[1]?；谠掝}的時間特性，本文不斷提煉話題的代表性關鍵詞向量，從而提高了話題識別的準確率，并利用BIC(Bayesian information criterion)的值使得多個相近子話題被聚集到了同一個話題類別。

2 相關工作

DARPA支持的話題識別及跟蹤項目[2](Topic Detection and Tracking，TDT)是最早開展的話題識別研究。隨后，國內外與話題識別相關的研究日漸深入，研究成果也日益豐富起來。文獻[3]分析了英文報道的基本特征，并給出了基于內容分析的話題識別算法，將話題按其語義內容表示為標識中心向量與內容中心向量。文獻[4]提出了話題檢測算法CMU，使用訓練語料建立了所有詞語的倒排文檔頻率，并利用分段的GAC方法進行了聚類。文獻[5]則利用時域分析法對事件內容進行分析。現有方法中大都具有以下缺陷：一是在基于文本相似度的聚類上進行特征擴展的過程中，沒有考慮到上下文的相關性，即文本信息間的交互性；二是有些方法簡單地以信息時間順序對特征向量值進行加權，忽視了會話深層的時序特征。Takeshi等所設計并實現的基于Twitter的實時地震監控系統[6]，是短文本話題識別及處理方面的典型應用。該系統采用了貝葉斯決策來篩選關鍵字，可成功檢測到的地震發生率達80%以上。其時效性遠高于相關地震告警機構，且其還可以依據信息中所包含的地理數據，估算出地震發生的大體位置。Sasa和Miles等提出了一種改進的新話題識別算法[7]，能夠在不失精度的前提下，快速地處理大于1.6億條Twitter消息。Zitao Liu等人利用part-of-speech和HowNet擴展單詞的語義特征的方法篩選出短文本的關鍵詞，以改進短文本分類和聚類效果[8]。目前，多數話題識別算法是以語法信息為基礎計算話題和報道的相似度，很少考慮短文本信息的特征稀疏性、時序性、交互性、奇異性和動態性，難以區分短文本信息的差異程度，另一方面，這些方法也很少考慮話題的時間特性以及一個話題可能包含幾個差異較大的子話題，這些都會影響話題識別的質量。

3 關鍵詞的權值

TF-IDF(term frequency-inverse document frequency)概念被公認為信息檢索中最重要的發明。它是一種常用的、有效的詞匯加權算法，其基本思想是： 在文本集中出現次數越多的關鍵詞或者在文本集中出現越少的關鍵詞區分度越高，因此關鍵詞權值也就越大。但也有如下明顯不足： 如果某個關鍵詞在某些文本中出現得較頻繁，而在另一些文本中出現得比較少時關鍵字區分度較低；另一是當包含某個關鍵詞的文本分散到多個話題中，且文本數量不多時關鍵字區分度也較低。當前專門針對短文本的度量技術研究并不多，且短文本聚類算法多是長文本聚類算法的簡單變形，沒有突出短文本短小、內容表達隨意、語句不完整、語法不規范和關鍵詞稀疏等特點。本文主要依據“短文本聚類過程中，某些核心詞匯可能極具判別性”語義特征來刻畫關鍵詞權值的影響程度。從關鍵詞在短文本中出現的頻率、關鍵詞對短文本信息流分布影響度、短文本信息流分布對于關鍵詞的影響度和關鍵詞關于話題的影響度四個因素考慮關鍵詞的權值。

定義1 關鍵詞wi在短文本Dj中出現的頻率定義為式(1)。

其中，tfij表示文本Dj中關鍵詞wi出現的頻率，length(Dj)表示文本Dj的長度。

定義1的意義在于關鍵字出現的頻率，考慮到了文檔的長度，是因為關鍵字在較長短文本中出現的次數一般會比相對較短的文本中出現的多。

定義2 關鍵詞wi對于短文本信息流{Dj}分布影響度定義為式(2)。

其中，tfij表示短文本Dj中關鍵詞wi出現的頻率，gfi表示在短文本信息流中關鍵詞wi出現的次數，Nt表示短文本信息流中所包含的短文本數量。

定義2的意義是關鍵詞區分短文本的能力，利用熵理論定義了關鍵詞對于短文本的分布情況的影響。

同樣可以利用熵理論來計算短文本分布對于關鍵詞權值的貢獻，定義3如式(3)所示。

定義3 短文本信息流{Dj}的分布對于關鍵詞權值的影響度定義為：

其中，tfij表示短文本Dj中關鍵詞wi出現的頻率，length(Dj)表示短文本Dj的長度，gfi表示在短文本信息流中關鍵詞wi出現的次數，swf表示文檔集中所有關鍵詞出現次數的總和。

傳統的聚類算法中，沒有考慮到關鍵詞與話題本身的聯系，本文在初始聚類時就得到與話題相關聯的一組關鍵詞，再通過不斷的修正和提煉來提高話題識別的精確度。

定義4 關鍵詞wi關于話題Cj(表示話題的類別)的影響度定義如式(4)所示。

其中，dfci表示在短話題類別Cj中包含關鍵詞wi的短文本數，Nc表示話題類別Cj中的短文本總數，dfi表示短文本信息流中包含關鍵詞wi的短文本總數，Nt表示短文本信息流中包含短文本的總數。

定義4的意義在于如果關鍵詞wi在話題Cj中出現的次數較多，而在其他話題中出現的次數較少，則說明wi對話題Cj的影響度較大，即有較好的話題區分能力。在本文話題聚類過程中利用式(4)對關鍵詞不斷地進行調整、篩選和提煉。

定義5 關鍵詞wi對于短文本Dj的權值定義如式(5)所示。

定義5的意義在于關鍵詞的權值既考慮到了TF-IDF模型的影響，同時也考慮到了短文本信息流文本的分布對關鍵詞權值的影響。

4 子話題合并準則

一般來講，短文本信息流中通常包含若干個話題，而每個話題又包含若干個子話題，表達這些子話題的短文本相互交織在一起，因此首先需要確定哪些子話題是可以合并的。傳統聚類算法中大都采用模型選擇的方法來確定類別的合并。而文獻[9]中的聚類過程，則利用貝葉斯BIC (bayesian information criterion)來實現模型打分，并合并 BIC分值最高的聚類模型。由于該算法對新的聚類模型采取不間斷的測試評分，因此需要較大的空間來存儲相關統計信息。本文采用文獻[10]的方法，通過計算BIC值來確定需要合并的子話題。

定義6 假設{xi|i=1,2,…,n}是d維樣本數據集，被聚類為k個數據子集{C1,C2,…,Ck}，記該聚類模型為M，而Pi為聚類模型M中獨立參數的個數，則M的BIC值定義如式(6)所示。

由定義6可以看出，BIC準則的基本思想是樣本的極大似然減去模型的復雜度，根據文獻[10]，可以利用BIC的值來判斷聚類過程中兩個類別是否應該合并，即假設短文本類別集聚類模型M1的某兩個類別合并后得到聚類模型M2，如果BIC(M1)

5 短文本數據流的回顧式話題識別模型

算法的主要思想是利用短文本信息流時序特征和話題所具有的階段性，先對每個時間段內的短文本集進行聚類，得到各個話題相應的類別及子話題類別。最后再對各個階段的類別進行合并。在聚類過程中，通過不斷提煉能夠代表話題的特征來提高聚類的性能。

5．1 時間段的劃分及其聚類

短文本信息流的回顧式話題識別是在主題相關性的基礎上考慮多個文本集之間的時序關系，如圖1所示把短文本信息流S的生存時間T劃分為n個時間段[t0,t1],[t1,t2],…,[tn-1,tn]，各個時段包含的文本集分別為STS1, STS2,…,STSn。短文本信息流的話題識別以文本集STS1,STS2,…, STSn中話題聚類的類別為基礎，進一步對這些類別進行合并以得到最后話題識別結果。

圖1 短文本數據流按時間段分隔

關于短文本集STSi的聚類，目前研究的方法很多，本文在后面實驗中取文獻[11]中的基于語義密度的文本聚類方法。

5．2 子話題類別合并算法STCC

定義7 設在m維空間中有兩個點x =(x1,x2,…,xm)，y=(y1,y2,…,ym)，x和y的距離定義如式(7)所示。

其中, xk和yk分別是x和y的第k個屬性值。如果Ci，Cj是兩個類別，則定義Ci與Cj的距離如式(8)所示。

定義8 設類別C的中心向量為C.center，x0∈C，如果滿足

則稱x0為關于類別C的孤立點。其中α是調節參數，0<α<1，|C|是類別C中所含元素的個數。

定義8是利用密度的思想定義了孤立點，即孤立點附近是稀疏的。其意義在于有些與話題不太相關的短文本可以不去考慮。

下面給出兩個話題類別合并的算法。為了問題討論方便，不妨設兩個話題為X、Y，它們的子話題類別個數均為s，話題類別X、Y進行合并后為話題類別Z?；舅枷胧牵?每一個短文本作為向量空間的一個結點，先是在類中選擇相互之間距離最大的s個分散的結點作為子話題中心結點，然后去掉孤立結點并選擇離它們最近的結點作為各自子話題的成員。算法STSCC(Short Text Subtopic Categories Combination)如下所示。

輸入 STS中話題類別X,Y及它們子話題類別個數s

輸出 合并后的類別Z

STSCC算法：

step1 利用文獻[12]，分別計算出X和Y的中心向量X.center和Y.center

step3 TSet=Φ,k=1

step4 do while k<=s

step4-1 maxD=0

step4-2 對于X和Y的子話題中任意點p

step4-3 if (k=1) then

step4-4 d=dist(p,Z.center)

step4-5 else

step4-6 d=dist(p,Z) //點p到類別Z的距離

step4-7 if (d>maxD) then

step4-8 maxD=d

step4-9 maxP=p

step4-10 endif //找到類別Z中與點p最大距離的點和距離值

step4-11 endif

step4-12 k=k+1

step4-13 TSet=TSet∪{maxP}

//TSet中存儲了X、Y類別中與Z距離最大的s個點

step4-14 enddo

step6 對于話題Z中的每一個點q

step7 for (每一個點p∈TSet) do

//把TSet的點作為Z子話題的中心向量進行子話題劃分

step7-1 對于話題Z中的每一個點q

step7-2 if (q是孤立點) then

step7-3 Z=Z-{q}

step7-4 endif

step7-5 if (q離p所在類Cp的中心向量最近) then

step7-6 Cp=Cp∪{q}

step7-7 endif

step7-8 endfor

step8 輸出Z

5．3 短文本數據流的回顧式話題識別算法

在短文本集STSi聚類結果中，總假設每個話題類別具有s個子話題，如果不足s個子話題時補充空子話題，如圖2所示。

圖2 話題的子話題生成

短文本集STSi的回顧式話題識別算法STRTD(Short Text Review Topic Detection)如下：

輸入 短文本信息流S，子話題數s，短文本向量維數m，距離閾值μ

輸出 話題類別集CT_S

STRTD算法

step1 對任意短文本ST∈S，按(5)式計算出ST每個關鍵詞權值，并將權值由大到小選出m個關鍵詞構成ST的一個向量，最后得到S的短文本向量集，記為TST_V

step2 按4.1分成n個時間段，將每一個時間段中的短文本向量按文獻[11]的方法聚類，初始狀態是將S的各類別存儲在類別集合CT_S中，并假設每一個類別都有s個子類別

step3 建立存儲類別對的堆棧Stack

step4 repeat

step4-1 將CT_S中的類別按兩兩距離最近構成若干個類別對，并按距離由小到大壓入堆棧Stack

step4-2 出棧存入Nd

step4-3 do while (Nd!=Φ)

step4-4 將Nd中的類別對分別賦值給X,Y

step4-5 將值X,Y,s傳給算法STSCC算法，合并后的類別為Z

step4-6 if (BIC(Z)>BIC(X,Y)) then

step4-7 退出該循環，重新定義關鍵詞并修改CT_S，執行step4-1

step4-8 endif

step4-9 enddo

step4-10 until (step4-6中條件不滿足)

step5 輸出CT_S

短文本集STS的回顧式話題識別算法STRTD的結果給出了具體的話題、子話題內容及話題個數，并且還可能檢測出S中尚未發現的話題。

6 實驗及結果分析

為了評價算法性能，該實驗將話題檢測算法STRTD、文獻[9]的X-means聚類算法及文獻[4]中給出的CMU關于話題聚類算法進行比較。

6．1 實驗數據及評價標準

為了驗證相關結論，我們從江蘇某短信運營商截取2012年2月1日0點整到4月30日24點0分時間段的近9.4萬條手機短信文本集合進行了人工標注。抽取出了如載有化學品的船在江陰段沉船、江蘇沿江部分城市出現市民搶購礦泉水、元宵節祝福等78個話題，假設每個話題中有8個子話題。為了問題的簡化，實驗前已將樣本集S通過分詞、特征提取和降維等預處理為短信文本向量集STS[13]。

假設類別i中包含ni條短信文本，聚類j中包含nj條短信文本，聚類j中隸屬于類別i的短信文本條數記為nij，則召回率R(i,j) 和正確率P(i,j)的定義如下[14]：

F值F(i,j)為：

F值的全局聚類為：

在這里，|STS|=n，并且有，F值越大，標志著聚類效果越好。

如果系統漏檢率用PMiss表示，由文獻[15]有：

6．2 小類別數量實驗

根據Power Laws和Pareto分布特征原理，小類別的中文短信文本信息的數量往往遠遠大于大類別[16]。本文對海量中文短信文本信息進行研究，對于小類別的中文短信文本盡量減少其聚類時間，或者將其清除掉，對于大類別的中文短信文本盡量增加其聚類機會，以提高大類別中文短信文本信息的聚類效率。本文從江蘇某短信運營商的文本短信樣本庫中隨機抽取了18 000條短信，在經過人工標注后，使用K-means算法對其進行聚類，實驗中規定每個樣本為一個類別，故類別個數k取18 000，該實驗中對于短信文本個數超過20的類別定義為大類別，短信文本小于5的為小類別，孤立點指包含短信文本個數為1的類別。實驗結果如表1所示。

從表1可以看出，在18 000條短信文本中，孤立點的短信文本條數占樣本總數的61.76%，而大類別數目僅占67個，大類別包含的短信文本的個數僅占樣本數的14.38%。

表1 大、小類別和孤立點數目實驗結果

6．3 召回率、正確率及F值比較

該實驗中，將X-means、CMU和 STRTD的召回率R、正確率P、漏檢率PMiss及F值進行比較，實驗結果如圖3所示。

從圖3可以看出， STRTD話題檢測方法性能明顯優于其他 兩 種算法， 這是由于算法STRTD采用了分段聚類，而后進行類別合并，并且引入了子話題的思想，提取具有高辨別能力的關鍵詞，這樣就會減少X-means和CMU中依賴類中心向量對話題檢測性能的影響，提高了話題檢測的召回率和準確率，同時也減少了話題檢測的漏檢率。

圖3 3種算法的4種性能指標比較

6．4 算法運行時間比較

該實驗中，在近94 000條手機短信文本集合中隨機抽取了18 000條短信文本進行實驗，為了問題簡單，先使用中科院計算所開發的ICTCLAS 作為中文分詞工具將這18 000條短信文本進行了分詞，構造出了多維向量空間，然后對算法X-means、CMU和STRTD運行的時間進行比較，結果如圖4所示。

圖4 3種算法的運行時間比較

在3種算法的運行時間比較試驗中，由圖4可以看出，當對11 340條短信文本進行試驗時，CMU算法和STRTD算法的運行時間基本上相同，當在大于這個數的短信文本集上驗證時，STRTD算法比其它兩種算法所需時間都少，而且隨著樣本量的增大，效果越來越好。這是因為在少量短信文本集的實驗中，STRTD算法需要對短信文本信息流進行時間段的劃分，在子話題類別合并過程中需要去點孤立點，占用了一些時間開銷，但隨著短文本數據量的增大，使得短信文本信息流的話題檢測的運行效率大大提高。

6．5 檢測話題數量實驗

對6.2實驗中得到的67個大類別短信文本作為準確的話題數目，該實驗利用3種算法檢測出話題數量與真實話題數量進行比較。實驗結果如圖5所示。

圖5 3種算法檢測的話題數比較實驗

由實驗結果可以看出，STRTD算法優于其它兩種算法，在超過3 000條短信文本的試驗中，STRTD算法檢測出的話題數量與真實話題數量的差異在10%以內，而且隨著實驗樣本數量的增多，更接近于真實話題數量。

7 結束語

在短文本信息流中檢測話題的中心問題是如何把短文本歸類到相應話題中，目前大多話題檢測方法都是利用傳統的聚類方法，沒有體現出話題的本身特點，性能也較低下。本文利用了短文本信息流的時序特征進行分段、聚類、類別合并，并去掉話題識別過程中孤立點信息，提高了話題檢測的效率。在檢測過程中又不斷提取具有辨別能力的短文本關鍵詞，利用TF-IDF的改進算法賦予權值，引入了子話題提高話題檢測的準確率。實驗表明，該算法具有較好的話題檢測質量和效率。

[1] Wang ZM,Zhou XS. A topic detection method based on bicharacteristic vectors[C]//Proceedings of the Int’l Conf. on Networks Security,Wireless Communications and Trusted Computing. Vol. 2. Washington: IEEE Computer Society, 2009. 683-687.

[2] Allan J, Papka R.On-line new event detection and tracking[C]//Proceedings of the 21 st Annual International ACM SIGIR Conference on Research and Devel-opment in Information Retrieval. Melbourne:ACM Press,1998.37-45.

[3] 趙華,趙鐵軍,張姝,等.基于內容分析的話題識別研究[J].哈爾濱工業大學學報,2006,38(10) : 1740-1743.

[4] Seo YW,Sycara K.Text clustering for topic detection[C]//Proceedings of the Pittsburgh: Robotics Institute, Carnegie Mellon University, 2004. 1-11.

[5] 駱衛華,于滿泉,許洪波,等.基于多策略優化的分治多層聚類算法的話題發現研究[J].中文信息學報,2006,20(1):29-36.

[6] Sakaki Ti,Okazzki M,Matsuo Y.Earthquake Shakes Twitter User:Real-time Event Detection Detection by Social Sensors[C]//Proceedings of the 19th International Conference on World Wide Web,2010. Raleigh,North Carolina:ACM Press,2010:851-861.

[7] Petrovi S,Osborne M,Lavrenko V.Streaming First Story Detection with application to Twitter[C]//Proceedings of HLTNAACL,2010. stroudsburg,PA,USA:Association for Computational Linguistics,2010:181-189.

[8] Liu Zitao,Yu Wenchao,Chen Wei,et al.Short Text Feature Selection for Micro-blog Mining[C]//Computational Intelligence and Softeare Engineering,2010. Wuhan, China:Wuhan Unive- sity, 2010:1-4.

[9] Pelleg D, Moore A. X-means: Extending K-means with Efficient Estimation of the Number of Clusters[C]//Proceedings 17th ICML. Stanford University.2000.727-734.

[10] 張小明,李舟軍,巢文涵.基于增量型聚類的自動話題識別研究[J].軟件學報,2012,23(6): 1578-1587.

[11] 劉金嶺. 基于語義密度的文本聚類研究[J].計算機工程,2010,36(5):81-83.

[12] 王強,關毅,王曉龍.基于標題類別語義識別的文本分類算法研究[J].電子與信息學報,2007,29(12):2886-2890.

[13] 劉金嶺.基于降維的短信文本語義分類及主題提取[J].計算機工程與應用,2010,46(23): 159-161.

[14] 黃九鳴,吳泉源,劉春陽,等.短信文本信息流的無監督會話抽取技術[J].軟件學報,2012,23(4):735-747.

[15] NIST.The 2004 Topic Detection and Tracking(TDT2004) Task Definition and Evaluation Plan version1.1c[EB/OL]. http://www.nist.gov.

[16] M. E. J. Newman. Powerlaws, Pareto distributions and Zipf’s law[J]. Contemporary Physics, 2005,46(5):323-351.

Retrospective Topic Identification Model for Short Text Information Flow

ZHOU Hong1, LIU Jinling1, WANG Xingong2

(1. Computer Engineering Faculty, Huaiyin Institute of Technology, Huaian, Jiangsu 223005, China;2. Department of Computer, Cangzhou Teachers College, Cangzhou, Hebei 061001, China)

In recent years, the short text information flow has occured in some public media. For this kind of data, a retrospective topic identification model is presented with an improved weight estimation. It employes the value of BIC for clustering to improve the clustering accuracy. By dividing the time segments and removing isolated information point, the efficiency of the algorithm is further improved. The experimental results show that this method achieves good accuracy and efficiency in the topic detection of the short text information flow.

short text; information flow; topic identification; clustering

周泓(1980—)，碩士，講師，主要研究領域為數據挖掘、計算機應用。E?mail：hong＿zhou@126．com劉金嶺(1958—)，學士，教授，主要研究領域為數據挖掘、數據庫應用。E?mail：liujinlingg@126．com王新功(1978—)，學士，講師，主要研究領域為文本數據挖掘。E?mail：flash?mx2004@163．com

1003-0077(2015)01-0111-07

2013-02-28 定稿日期： 2013-07-28

河北省科技支撐計劃項目(10213581)；淮安市社會發展項目(HASZ2012046)；淮安市科技支撐計劃(工業)項目(HAG2012086)

TP391

A