基于SVM的查詢向量微博話題跟蹤技術(shù)研究

， ，

(鄭州輕工業(yè)學(xué)院，鄭州 450000)

隨著互聯(lián)網(wǎng)信息科技的快速發(fā)展，微博已經(jīng)成為人們?nèi)粘Ｉ钪行畔⒔涣鞯闹匾脚_。每天微博中都充斥著數(shù)以萬計的信息，人們利用微博話題檢測技術(shù)可以從這些雜亂無章的信息中很容易地獲取自己需要的內(nèi)容。在微博系統(tǒng)的使用中，人們在發(fā)現(xiàn)了自己需要或者感興趣的話題后，不僅想知道該話題事件以前和當(dāng)前都發(fā)生了什么，更想知道該話題事件將來會發(fā)生什么。微博話題跟蹤技術(shù)就是根據(jù)用戶的需求，按照一定的算法，對相關(guān)的話題內(nèi)容進(jìn)行跟蹤，并將跟蹤到的結(jié)果進(jìn)行歸類整合，自動提供給用戶的一種計算機(jī)技術(shù)。

本文介紹了微博話題跟蹤技術(shù)中常用的兩種方法：支持向量機(jī)(SVM)算法和基于查詢向量的話題跟蹤算法，在結(jié)合傳統(tǒng)話題跟蹤技術(shù)和微博自身特點(diǎn)的基礎(chǔ)上，提出了一種基于SVM的查詢向量話題跟蹤算法，并給出了該算法在微博話題跟蹤應(yīng)用中的流程，最后通過數(shù)據(jù)模擬實(shí)驗(yàn)對該算法的性能進(jìn)行驗(yàn)證。

1 微博話題跟蹤的流程

微博話題的跟蹤過程，從數(shù)學(xué)角度上來說，可以形容為一個關(guān)系的映射。它是將最新出現(xiàn)的微博話題文本(A)根據(jù)一定的跟蹤規(guī)則(f)與系統(tǒng)中已有的話題進(jìn)行對比，并映射到相應(yīng)話題集(B)中去的一個過程。公式(1)為話題關(guān)系映射的表示形式：

f:A→B

(1)

其中，A表示最新的話題集；B表示已知的、系統(tǒng)預(yù)設(shè)的話題集；f表示跟蹤映射規(guī)則，該規(guī)則的主要內(nèi)容為：系統(tǒng)根據(jù)已知話題的樣本集，歸納出話題間內(nèi)在聯(lián)系的判別規(guī)則f，當(dāng)有新的話題出現(xiàn)時，系統(tǒng)就根據(jù)上述規(guī)則f將新來的話題歸入相應(yīng)的話題類中。

微博話題跟蹤流程[1]分為兩個階段,如圖1所示。第一個階段為訓(xùn)練階段，主要目的是形成分類模型，方法是先對預(yù)設(shè)話題進(jìn)行一定數(shù)量的訓(xùn)練，從而形成訓(xùn)練樣本，然后對訓(xùn)練樣本進(jìn)行信息預(yù)處理，并根據(jù)一定的算法，最終生成分類模型。第二個階段為分類階段，目的是形成分類結(jié)果，方法是對新出現(xiàn)的話題進(jìn)行信息處理，并與第一階段生成的分類模型進(jìn)行比較，再根據(jù)一定的分類算法判斷該報道屬于哪個話題。

圖1 話題跟蹤的流程

2 傳統(tǒng)的微博話題跟蹤算法

2.1 支持向量機(jī)(SVM)算法

支持向量機(jī)(SVM)算法理論是在1995年由Vapnik提出的[2-4]，該理論的提出是為了解決訓(xùn)練集有限的問題。它包含了統(tǒng)計學(xué)的VC維理論和結(jié)構(gòu)遇險概率最小化的理論，是在二者相結(jié)合的基礎(chǔ)上建立的。

支持向量機(jī)(SVM)算法的主要理論內(nèi)容是：將訓(xùn)練樣本表示為一個空間向量模型，并對該模型進(jìn)行二次規(guī)劃求解，從而求得一個最優(yōu)分類函數(shù)，然后將待分類的文本向量代入該最優(yōu)分類函數(shù)求值，并根據(jù)求得的值判斷該文本向量的類別，如果其值能夠滿足某個分類條件，就將該文本向量劃入相應(yīng)分類中去。支持向量機(jī)算法(SVM)的示意圖如圖2所示。

圖2 支持向量機(jī)算法(SVM)示意圖

圖2中，▲和●分別表示不同類別的文本；虛線表示其他分類平面，該平面平行于最優(yōu)分類平面，且穿過離最優(yōu)分類平面最近的文本向量。雖然這樣的分類平面有無數(shù)多條，但是只有最優(yōu)分類平面可以使文本類別間的距離最大。

支持向量機(jī)(SVM)算法的優(yōu)點(diǎn)是：它在樣本數(shù)量有限的情況下，能夠獲得最好的分類結(jié)果，這解決了實(shí)際應(yīng)用中樣本有限的問題，比較貼近實(shí)用。該算法的缺點(diǎn)是：它通過最優(yōu)分類函數(shù)將樣本劃分到不同的聚類中，而不是將樣本的劃分精確到數(shù)值，故準(zhǔn)確率不高。

2.2 基于查詢向量的話題跟蹤算法

美國國防部高級研究設(shè)計局和美國國家標(biāo)準(zhǔn)與技術(shù)研究所等單位聯(lián)合開展研究了TDT(Topic Detection and Tracking)問題。在研究過程中，為了解決話題跟蹤任務(wù)不直接給定主題的問題，研究者們只給出了1～4篇蘊(yùn)含話題的相關(guān)報道作為訓(xùn)練樣本。雖然訓(xùn)練樣本數(shù)量很有限，但是在此基礎(chǔ)上，衍生出了很多的話題跟蹤算法，比如KNN算法[5]和決策樹算法等。然而，基于查詢向量的話題跟蹤算法在TDT研究的基礎(chǔ)上，不用去考慮先驗(yàn)報道的稀疏性[6]。

基于查詢向量話題跟蹤算法的主要思想是：在話題檢測完成的基礎(chǔ)上，將檢測出的話題向量作為查詢向量，將對微博用戶頁面信息進(jìn)行采集得到的XML數(shù)據(jù)作為文本向量，并將查詢向量和文本向量進(jìn)行相似度計算，然后將計算出的結(jié)果與提前設(shè)置的閾值進(jìn)行比較，根據(jù)比較結(jié)果來判斷話題向量是否為相關(guān)話題的后續(xù)報道。該方法適用于微博話題的跟蹤[7]。

基于查詢向量的話題跟蹤算法的優(yōu)點(diǎn)是：不用去考慮前面查詢向量的稀疏性報道，算法簡單且高效。該算法的缺點(diǎn)是：由于事件隨著時間不斷地發(fā)展變化，從而使相關(guān)話題也跟著變化，故而可能出現(xiàn)話題漂移現(xiàn)象，影響話題跟蹤的準(zhǔn)確率。

基于查詢向量的話題跟蹤算法的流程如圖3所示。

圖3 基于查詢向量的話題跟蹤算法流程圖

3 基于SVM的查詢向量話題跟蹤算法

支持向量機(jī)(SVM)算法雖然能夠在樣本數(shù)量有限的情況下獲得較好的分類結(jié)果，但是其分類的精度還不高。而基于查詢向量的話題跟蹤算法雖然可以不考慮先驗(yàn)報道的稀疏性，但可能會引起話題漂移現(xiàn)象。所以，本文在考慮上述兩種算法優(yōu)缺點(diǎn)的基礎(chǔ)上，提出一種新的算法，即基于SVM的查詢向量話題跟蹤算法。

基于SVM的查詢向量話題跟蹤算法的主要思想是：第一，在話題檢測完成的基礎(chǔ)上，將檢測出的話題向量作為查詢向量，將對微博用戶頁面信息進(jìn)行采集得到的XML數(shù)據(jù)構(gòu)建為文本向量；第二，對構(gòu)建好的文本向量模型進(jìn)行二次規(guī)劃求解，從而求得一個最優(yōu)分類函數(shù)；第三，將待分類的文本向量代入該最優(yōu)分類函數(shù)求值，并根據(jù)求得的值判斷該文本向量的類別；第四，將待分類的文本向量根據(jù)判斷類別進(jìn)行分類后，將剛進(jìn)入該類的文本向量作為查詢向量，與已構(gòu)建的文本向量進(jìn)行相似度計算，并將計算出的結(jié)果與提前設(shè)置的閾值進(jìn)行比較；第五，根據(jù)比較結(jié)果來判斷話題向量是否為相關(guān)話題的后續(xù)報道。

該算法既能夠利用SVM算法的最優(yōu)分類函數(shù)確定話題區(qū)域，縮小話題范圍，提高跟蹤準(zhǔn)確率，又能夠運(yùn)用基于查詢向量的算法優(yōu)化話題空間，減小話題漂移差距。

基于SVM的查詢向量話題跟蹤算法的流程圖如圖4所示。

圖4 基于SVM的查詢向量話題跟蹤算法流程圖

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證基于SVM的查詢向量話題跟蹤算法在實(shí)際應(yīng)用中是否能夠提高話題跟蹤的準(zhǔn)確率和綜合效率，本文進(jìn)行了數(shù)字模擬實(shí)驗(yàn)。

實(shí)驗(yàn)嚴(yán)格按照TDT話題評測規(guī)則進(jìn)行，主要從召回率(R)、準(zhǔn)確率(P)、F值3個指標(biāo)進(jìn)行量化考察。

召回率(R)是指對于某一個話題屬性，系統(tǒng)能夠正確識別出來的話題文本數(shù)(D)占系統(tǒng)應(yīng)該識別出來的話題文本總數(shù)(T)的比重。其具體公式如下：

R=D/T×100%

準(zhǔn)確率(P)是指對于某一個話題屬性，系統(tǒng)能夠正確識別出來的話題文本數(shù)(D)占系統(tǒng)已經(jīng)識別出來的話題文本數(shù)(U)的比重。其具體公式如下：

P=D/U×100%

F值是描述召回率(R)與準(zhǔn)確率(P)綜合性能的指標(biāo)，是反映話題跟蹤技術(shù)整體性能的重要指標(biāo)。其具體公式如下：

F=2PR/(P+R)×100%

實(shí)驗(yàn)設(shè)備：惠普Compaq dx2390 服務(wù)器，英特爾Pentium(R) Dual-core E5200 2.5GHz處理器，2046MB內(nèi)存，Microsoft windows XP professional (5.1,版本2600)操作系統(tǒng)，網(wǎng)絡(luò)帶寬10 M。

實(shí)驗(yàn)數(shù)據(jù)選取如下：從網(wǎng)頁中隨機(jī)抽取18 543個XML文件；通過話題檢測隨機(jī)抽取得到10個微博話題；在微博系統(tǒng)中隨機(jī)選出1 000個微博用戶，并對這1 000個微博用戶的主頁面和二級頁面進(jìn)行信息提取，共提取出27 654個話題信息，并將這些信息轉(zhuǎn)變?yōu)?7 654個XML數(shù)據(jù)。

為了增強(qiáng)實(shí)驗(yàn)的對比性，分別對傳統(tǒng)的支持向量機(jī)(SVM)算法、基于查詢向量的話題跟蹤算法和新提出的基于SVM的查詢向量話題跟蹤算法進(jìn)行話題跟蹤模擬實(shí)驗(yàn)。經(jīng)過實(shí)驗(yàn)，得到了評測結(jié)果，如表1所示。

通過實(shí)驗(yàn)評測結(jié)果可以看出，支持向量機(jī)(SVM)算法和基于查詢向量的話題跟蹤算法雖然都能夠較快地完成話題跟蹤任務(wù)，但是其準(zhǔn)確率及綜合性能相對較差，而基于SVM的查詢向量話題跟蹤算法在微博話題跟蹤任務(wù)中的召回率、準(zhǔn)確率、F值都優(yōu)于前兩種算法。雖然該算法在用時上還有待縮短，但是它提高了話題跟蹤的準(zhǔn)確率，是一種優(yōu)良的算法。

表1 話題跟蹤評測結(jié)果

5 結(jié) 語

目前，關(guān)于話題跟蹤技術(shù)常用的算法有支持向量機(jī)(SVM)算法和基于查詢向量的話題跟蹤算法。然而在實(shí)際運(yùn)用中，這兩種算法都存在微博話題跟蹤的準(zhǔn)確率不高的問題。為了進(jìn)一步提高微博話題跟蹤的準(zhǔn)確率，本文提出了基于SVM的查詢向量話題跟蹤算法，該算法既能夠運(yùn)用最優(yōu)分類函數(shù)縮小話題范圍，又能夠運(yùn)用查詢向量減少話題漂移現(xiàn)象，從而提高微博話題跟蹤的精確度。通過模擬實(shí)驗(yàn)證明，該算法雖然在用時上還有待縮短，但確實(shí)提高了微博話題跟蹤準(zhǔn)確率。

參考文獻(xiàn)：

[1] 韓威,趙鐵軍.網(wǎng)絡(luò)輿情熱點(diǎn)發(fā)現(xiàn)與話題跟蹤技術(shù)研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2012.

[2] 張健沛,徐華.支持向量機(jī)(SVM)主動學(xué)習(xí)方法研究與應(yīng)用[J].計算機(jī)應(yīng)用,2004,24(1):1-3.

[3] 王順利.基于支持向量機(jī)(SVM)的圖像去噪方法[J].微電子學(xué)與計算機(jī),2005,22(4):96-99.

[4] Cortes C, Vapnik V.Support Vector Networks[J].Machine Learning,1995,20(3):273-297.

[5] 李秀娟.KNN分類算法研究[J].科學(xué)信息,2009(31):25-28.

[6] 洪宇.基于語義結(jié)構(gòu)和時序特征的話題檢測與跟蹤技術(shù)研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2009.

[7] 孫勝平,張真繼.中文微博熱點(diǎn)話題檢查與跟蹤技術(shù)研究[D].北京:北京交通大學(xué),2011.