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

周 泓，劉金嶺，王新功

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

?

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

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

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

近幾年來(lái)，短文本信息流廣泛應(yīng)用于一些全民媒體，它在公開(kāi)傳遞信息同時(shí)攜帶了豐富且具有極大價(jià)值的信息資源。該文提出了一種回顧式話題識(shí)別模型，改進(jìn)了權(quán)值計(jì)算方法，有效提取了具有較強(qiáng)分辨話題能力的關(guān)鍵詞，在聚類(lèi)過(guò)程中將BIC值作為話題類(lèi)別合并依據(jù)，提高了聚類(lèi)的準(zhǔn)確率。通過(guò)進(jìn)行時(shí)間段分隔和去掉孤立點(diǎn)信息提高了算法的效率。實(shí)驗(yàn)結(jié)果表明，該方法有效地提高了短文本信息流的話題檢測(cè)準(zhǔn)確率和效率。

短文本；信息流；話題識(shí)別；聚類(lèi)

1 引言

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

2 相關(guān)工作

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

3 關(guān)鍵詞的權(quán)值

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

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

其中，tfij表示文本Dj中關(guān)鍵詞wi出現(xiàn)的頻率，length(Dj)表示文本Dj的長(zhǎng)度。

定義1的意義在于關(guān)鍵字出現(xiàn)的頻率，考慮到了文檔的長(zhǎng)度，是因?yàn)殛P(guān)鍵字在較長(zhǎng)短文本中出現(xiàn)的次數(shù)一般會(huì)比相對(duì)較短的文本中出現(xiàn)的多。

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

其中，tfij表示短文本Dj中關(guān)鍵詞wi出現(xiàn)的頻率，gfi表示在短文本信息流中關(guān)鍵詞wi出現(xiàn)的次數(shù)，Nt表示短文本信息流中所包含的短文本數(shù)量。

定義2的意義是關(guān)鍵詞區(qū)分短文本的能力，利用熵理論定義了關(guān)鍵詞對(duì)于短文本的分布情況的影響。

同樣可以利用熵理論來(lái)計(jì)算短文本分布對(duì)于關(guān)鍵詞權(quán)值的貢獻(xiàn)，定義3如式(3)所示。

定義3 短文本信息流{Dj}的分布對(duì)于關(guān)鍵詞權(quán)值的影響度定義為：

其中，tfij表示短文本Dj中關(guān)鍵詞wi出現(xiàn)的頻率，length(Dj)表示短文本Dj的長(zhǎng)度，gfi表示在短文本信息流中關(guān)鍵詞wi出現(xiàn)的次數(shù)，swf表示文檔集中所有關(guān)鍵詞出現(xiàn)次數(shù)的總和。

傳統(tǒng)的聚類(lèi)算法中，沒(méi)有考慮到關(guān)鍵詞與話題本身的聯(lián)系，本文在初始聚類(lèi)時(shí)就得到與話題相關(guān)聯(lián)的一組關(guān)鍵詞，再通過(guò)不斷的修正和提煉來(lái)提高話題識(shí)別的精確度。

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

其中，dfci表示在短話題類(lèi)別Cj中包含關(guān)鍵詞wi的短文本數(shù)，Nc表示話題類(lèi)別Cj中的短文本總數(shù)，dfi表示短文本信息流中包含關(guān)鍵詞wi的短文本總數(shù)，Nt表示短文本信息流中包含短文本的總數(shù)。

定義4的意義在于如果關(guān)鍵詞wi在話題Cj中出現(xiàn)的次數(shù)較多，而在其他話題中出現(xiàn)的次數(shù)較少，則說(shuō)明wi對(duì)話題Cj的影響度較大，即有較好的話題區(qū)分能力。在本文話題聚類(lèi)過(guò)程中利用式(4)對(duì)關(guān)鍵詞不斷地進(jìn)行調(diào)整、篩選和提煉。

定義5 關(guān)鍵詞wi對(duì)于短文本Dj的權(quán)值定義如式(5)所示。

定義5的意義在于關(guān)鍵詞的權(quán)值既考慮到了TF-IDF模型的影響，同時(shí)也考慮到了短文本信息流文本的分布對(duì)關(guān)鍵詞權(quán)值的影響。

4 子話題合并準(zhǔn)則

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

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

由定義6可以看出，BIC準(zhǔn)則的基本思想是樣本的極大似然減去模型的復(fù)雜度，根據(jù)文獻(xiàn)[10]，可以利用BIC的值來(lái)判斷聚類(lèi)過(guò)程中兩個(gè)類(lèi)別是否應(yīng)該合并，即假設(shè)短文本類(lèi)別集聚類(lèi)模型M1的某兩個(gè)類(lèi)別合并后得到聚類(lèi)模型M2，如果BIC(M1)

5 短文本數(shù)據(jù)流的回顧式話題識(shí)別模型

算法的主要思想是利用短文本信息流時(shí)序特征和話題所具有的階段性，先對(duì)每個(gè)時(shí)間段內(nèi)的短文本集進(jìn)行聚類(lèi)，得到各個(gè)話題相應(yīng)的類(lèi)別及子話題類(lèi)別。最后再對(duì)各個(gè)階段的類(lèi)別進(jìn)行合并。在聚類(lèi)過(guò)程中，通過(guò)不斷提煉能夠代表話題的特征來(lái)提高聚類(lèi)的性能。

5．1 時(shí)間段的劃分及其聚類(lèi)

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

圖1 短文本數(shù)據(jù)流按時(shí)間段分隔

關(guān)于短文本集STSi的聚類(lèi)，目前研究的方法很多，本文在后面實(shí)驗(yàn)中取文獻(xiàn)[11]中的基于語(yǔ)義密度的文本聚類(lèi)方法。

5．2 子話題類(lèi)別合并算法STCC

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

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

定義8 設(shè)類(lèi)別C的中心向量為C.center，x0∈C，如果滿足

則稱(chēng)x0為關(guān)于類(lèi)別C的孤立點(diǎn)。其中α是調(diào)節(jié)參數(shù)，0<α<1，|C|是類(lèi)別C中所含元素的個(gè)數(shù)。

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

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

輸入 STS中話題類(lèi)別X,Y及它們子話題類(lèi)別個(gè)數(shù)s

輸出 合并后的類(lèi)別Z

STSCC算法：

step1 利用文獻(xiàn)[12]，分別計(jì)算出X和Y的中心向量X.center和Y.center

step3 TSet=Φ,k=1

step4 do while k<=s

step4-1 maxD=0

step4-2 對(duì)于X和Y的子話題中任意點(diǎn)p

step4-3 if (k=1) then

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

step4-5 else

step4-6 d=dist(p,Z) //點(diǎn)p到類(lèi)別Z的距離

step4-7 if (d>maxD) then

step4-8 maxD=d

step4-9 maxP=p

step4-10 endif //找到類(lèi)別Z中與點(diǎn)p最大距離的點(diǎn)和距離值

step4-11 endif

step4-12 k=k+1

step4-13 TSet=TSet∪{maxP}

//TSet中存儲(chǔ)了X、Y類(lèi)別中與Z距離最大的s個(gè)點(diǎn)

step4-14 enddo

step6 對(duì)于話題Z中的每一個(gè)點(diǎn)q

step7 for (每一個(gè)點(diǎn)p∈TSet) do

//把TSet的點(diǎn)作為Z子話題的中心向量進(jìn)行子話題劃分

step7-1 對(duì)于話題Z中的每一個(gè)點(diǎn)q

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

step7-3 Z=Z-{q}

step7-4 endif

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

step7-6 Cp=Cp∪{q}

step7-7 endif

step7-8 endfor

step8 輸出Z

5．3 短文本數(shù)據(jù)流的回顧式話題識(shí)別算法

在短文本集STSi聚類(lèi)結(jié)果中，總假設(shè)每個(gè)話題類(lèi)別具有s個(gè)子話題，如果不足s個(gè)子話題時(shí)補(bǔ)充空子話題，如圖2所示。

圖2 話題的子話題生成

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

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

輸出 話題類(lèi)別集CT_S

STRTD算法

step1 對(duì)任意短文本ST∈S，按(5)式計(jì)算出ST每個(gè)關(guān)鍵詞權(quán)值，并將權(quán)值由大到小選出m個(gè)關(guān)鍵詞構(gòu)成ST的一個(gè)向量，最后得到S的短文本向量集，記為T(mén)ST_V

step2 按4.1分成n個(gè)時(shí)間段，將每一個(gè)時(shí)間段中的短文本向量按文獻(xiàn)[11]的方法聚類(lèi)，初始狀態(tài)是將S的各類(lèi)別存儲(chǔ)在類(lèi)別集合CT_S中，并假設(shè)每一個(gè)類(lèi)別都有s個(gè)子類(lèi)別

step3 建立存儲(chǔ)類(lèi)別對(duì)的堆棧Stack

step4 repeat

step4-1 將CT_S中的類(lèi)別按兩兩距離最近構(gòu)成若干個(gè)類(lèi)別對(duì)，并按距離由小到大壓入堆棧Stack

step4-2 出棧存入Nd

step4-3 do while (Nd!=Φ)

step4-4 將Nd中的類(lèi)別對(duì)分別賦值給X,Y

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

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

step4-7 退出該循環(huán)，重新定義關(guān)鍵詞并修改CT_S，執(zhí)行step4-1

step4-8 endif

step4-9 enddo

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

step5 輸出CT_S

短文本集STS的回顧式話題識(shí)別算法STRTD的結(jié)果給出了具體的話題、子話題內(nèi)容及話題個(gè)數(shù)，并且還可能檢測(cè)出S中尚未發(fā)現(xiàn)的話題。

6 實(shí)驗(yàn)及結(jié)果分析

為了評(píng)價(jià)算法性能，該實(shí)驗(yàn)將話題檢測(cè)算法STRTD、文獻(xiàn)[9]的X-means聚類(lèi)算法及文獻(xiàn)[4]中給出的CMU關(guān)于話題聚類(lèi)算法進(jìn)行比較。

6．1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)標(biāo)準(zhǔn)

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

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

F值F(i,j)為：

F值的全局聚類(lèi)為：

在這里，|STS|=n，并且有，F(xiàn)值越大，標(biāo)志著聚類(lèi)效果越好。

如果系統(tǒng)漏檢率用PMiss表示，由文獻(xiàn)[15]有：

6．2 小類(lèi)別數(shù)量實(shí)驗(yàn)

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

從表1可以看出，在18 000條短信文本中，孤立點(diǎn)的短信文本條數(shù)占樣本總數(shù)的61.76%，而大類(lèi)別數(shù)目?jī)H占67個(gè)，大類(lèi)別包含的短信文本的個(gè)數(shù)僅占樣本數(shù)的14.38%。

表1 大、小類(lèi)別和孤立點(diǎn)數(shù)目實(shí)驗(yàn)結(jié)果

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

該實(shí)驗(yàn)中，將X-means、CMU和 STRTD的召回率R、正確率P、漏檢率PMiss及F值進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖3所示。

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

圖3 3種算法的4種性能指標(biāo)比較

6．4 算法運(yùn)行時(shí)間比較

該實(shí)驗(yàn)中，在近94 000條手機(jī)短信文本集合中隨機(jī)抽取了18 000條短信文本進(jìn)行實(shí)驗(yàn)，為了問(wèn)題簡(jiǎn)單，先使用中科院計(jì)算所開(kāi)發(fā)的ICTCLAS 作為中文分詞工具將這18 000條短信文本進(jìn)行了分詞，構(gòu)造出了多維向量空間，然后對(duì)算法X-means、CMU和STRTD運(yùn)行的時(shí)間進(jìn)行比較，結(jié)果如圖4所示。

圖4 3種算法的運(yùn)行時(shí)間比較

在3種算法的運(yùn)行時(shí)間比較試驗(yàn)中，由圖4可以看出，當(dāng)對(duì)11 340條短信文本進(jìn)行試驗(yàn)時(shí)，CMU算法和STRTD算法的運(yùn)行時(shí)間基本上相同，當(dāng)在大于這個(gè)數(shù)的短信文本集上驗(yàn)證時(shí)，STRTD算法比其它兩種算法所需時(shí)間都少，而且隨著樣本量的增大，效果越來(lái)越好。這是因?yàn)樵谏倭慷绦盼谋炯膶?shí)驗(yàn)中，STRTD算法需要對(duì)短信文本信息流進(jìn)行時(shí)間段的劃分，在子話題類(lèi)別合并過(guò)程中需要去點(diǎn)孤立點(diǎn)，占用了一些時(shí)間開(kāi)銷(xiāo)，但隨著短文本數(shù)據(jù)量的增大，使得短信文本信息流的話題檢測(cè)的運(yùn)行效率大大提高。

6．5 檢測(cè)話題數(shù)量實(shí)驗(yàn)

對(duì)6.2實(shí)驗(yàn)中得到的67個(gè)大類(lèi)別短信文本作為準(zhǔn)確的話題數(shù)目，該實(shí)驗(yàn)利用3種算法檢測(cè)出話題數(shù)量與真實(shí)話題數(shù)量進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 3種算法檢測(cè)的話題數(shù)比較實(shí)驗(yàn)

由實(shí)驗(yàn)結(jié)果可以看出，STRTD算法優(yōu)于其它兩種算法，在超過(guò)3 000條短信文本的試驗(yàn)中，STRTD算法檢測(cè)出的話題數(shù)量與真實(shí)話題數(shù)量的差異在10%以內(nèi)，而且隨著實(shí)驗(yàn)樣本數(shù)量的增多，更接近于真實(shí)話題數(shù)量。

7 結(jié)束語(yǔ)

在短文本信息流中檢測(cè)話題的中心問(wèn)題是如何把短文本歸類(lèi)到相應(yīng)話題中，目前大多話題檢測(cè)方法都是利用傳統(tǒng)的聚類(lèi)方法，沒(méi)有體現(xiàn)出話題的本身特點(diǎn)，性能也較低下。本文利用了短文本信息流的時(shí)序特征進(jìn)行分段、聚類(lèi)、類(lèi)別合并，并去掉話題識(shí)別過(guò)程中孤立點(diǎn)信息，提高了話題檢測(cè)的效率。在檢測(cè)過(guò)程中又不斷提取具有辨別能力的短文本關(guān)鍵詞，利用TF-IDF的改進(jìn)算法賦予權(quán)值，引入了子話題提高話題檢測(cè)的準(zhǔn)確率。實(shí)驗(yàn)表明，該算法具有較好的話題檢測(cè)質(zhì)量和效率。

[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] 趙華,趙鐵軍,張姝,等.基于內(nèi)容分析的話題識(shí)別研究[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),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] 駱衛(wèi)華,于滿泉,許洪波,等.基于多策略優(yōu)化的分治多層聚類(lèi)算法的話題發(fā)現(xiàn)研究[J].中文信息學(xué)報(bào),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] 張小明,李舟軍,巢文涵.基于增量型聚類(lèi)的自動(dòng)話題識(shí)別研究[J].軟件學(xué)報(bào),2012,23(6): 1578-1587.

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

[12] 王強(qiáng),關(guān)毅,王曉龍.基于標(biāo)題類(lèi)別語(yǔ)義識(shí)別的文本分類(lèi)算法研究[J].電子與信息學(xué)報(bào),2007,29(12):2886-2890.

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

[14] 黃九鳴,吳泉源,劉春陽(yáng),等.短信文本信息流的無(wú)監(jiān)督會(huì)話抽取技術(shù)[J].軟件學(xué)報(bào),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—)，碩士，講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘、計(jì)算機(jī)應(yīng)用。E?mail：hong＿zhou@126．com劉金嶺(1958—)，學(xué)士，教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘、數(shù)據(jù)庫(kù)應(yīng)用。E?mail：liujinlingg@126．com王新功(1978—)，學(xué)士，講師，主要研究領(lǐng)域?yàn)槲谋緮?shù)據(jù)挖掘。E?mail：flash?mx2004@163．com

1003-0077(2015)01-0111-07

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

河北省科技支撐計(jì)劃項(xiàng)目(10213581)；淮安市社會(huì)發(fā)展項(xiàng)目(HASZ2012046)；淮安市科技支撐計(jì)劃(工業(yè))項(xiàng)目(HAG2012086)

TP391

A