一種對BBS語料進行話題提取的聚類算法

1、一種對BBS語料進行話題提取的聚類算法第25卷第8期2008年8月計算機應用與軟件ComputerApplicationsandSoftwareVol_25No.8Aug.2008一種對BBS語料進行話題提取的聚類算法李卓爾胡運發(fā)(復旦大學計算機信息與技術(shù)系上海200433)摘要基于BBS語料的話題提取主要是從大量的BBS論壇討論信息中,將正在或近期討論的各種話題提取出來.在自主開發(fā)的一套話題提取系統(tǒng)中采用了一個原始聚類算法,能夠?qū)φ鎸嵉腂BS語料進行有效話題提取.隨后將語料中的關(guān)聯(lián)信息引入到原始聚類算法中進行改進,提高了算法的性能,取得了良好的效果.關(guān)鍵詞BBS話題提取關(guān)聯(lián)信息聚類算法ACL

2、USTEIUNGALGoIUTHMFoRToPICDETECTIoNANDTRACKINGINBBSLiZhuoerHuYunfa(DepartmentofComputingInformationandTechnology,FudanUniversity,Shanghai200433,China)AbstractTopicdetectionandtrackinginBBSismainlytodetectthetopicsbeingdiscussedorhadbeendiscussedrecentlyfromahostofrelatedinformationfromBBS.Thetopicdet

3、ectionsystemwithaclusteringalgorithmiseffectivefortopicdetectionandtrackinginBBS.ImprovementismadeontherelatedinformationofBBS,whichisintroducedtotheoriginalclusteringalgorithm.Theperformanceofthealgorithmisimproved,andbetterresultsareachieved.KeywordsBBSTopicdetectionandtrackingRelatedinformationCl

4、usteringalgorithm0引言近年來隨著網(wǎng)絡(luò)在國內(nèi)的普及,網(wǎng)民人數(shù)大幅攀升,越來越多的人開始在網(wǎng)絡(luò)上獲取信息,發(fā)表看法或評論,并與他人進行交流.其中網(wǎng)絡(luò)論壇(簡稱BBS)作為一個重要的網(wǎng)絡(luò)媒介,在民眾意見表達的方面起到了舉足輕重的作用.如果可以從BBS這個渠道了解到對各種事件的民意情況,那么對相關(guān)部門及時疏導民意或采取相應措施都將給予極大的幫助.所以如何從在各種BBS發(fā)表的大量信息中及時地獲取最新的熱點討論話題,成為了一個關(guān)鍵的問題.但是傳統(tǒng)的一些話題提取算法一般是基于比較正式的文本,如報紙雜志,新聞報道,社論專欄,廣播等,或者是專業(yè)性比較強的論文,報告,文檔之類的.與之相比,在BB

5、S上發(fā)表的文章專業(yè)性不強,具有極大的隨意性,多則幾千上萬字,少則寥寥幾句.而且涉及內(nèi)容相當廣泛,幾乎可以觸及到社會的各個方面.傳統(tǒng)的話題提取算法難以直接運用到基于BBS語料的話題提取上,因此需要針對BBS語料的特點設(shè)計更合適的話題提取算法.基于這個前提,我們實驗室研究開發(fā)了一個針對BBS語料的話題提取系統(tǒng).在這個系統(tǒng)中運用了一個聚類算法,是通過對傳統(tǒng)的話題提取算法進行改進,并針對BBS語料的特點設(shè)計而成,有效地解決了在BBS語料的基礎(chǔ)上進行話題提取的問題.在實際的研究過程中,我們發(fā)現(xiàn)人們討論的話題不是完全獨立的,多多少少都會有互相關(guān)聯(lián)的部分.而這一點,也是目前獲得大家所承認的.盡管這個特點混淆

6、了各個話題之間的界限,給話題提取帶來了一定的難度.但是利用好這個特點,對話題提取也可以產(chǎn)生積極的影響.我們將關(guān)聯(lián)信息引入到原始的話題提取算法中去,對其加以改進.從而得到了一個改進算法,經(jīng)過實驗測試證明,這個算法更有效地實現(xiàn)了話題提取功能.1原始話題提取算法1.1基本思想BBS上的語料與一般傳統(tǒng)的需要進行分類的語料有較大的區(qū)別,這一點已經(jīng)在上文介紹了.BBS語料在時間上的連續(xù)性,話題需要考慮之前和之后語料的聯(lián)系,而且BBS語料數(shù)量上十分龐大,難以由人提供大量有效的幫助.在BBS語料中,一個標題下的大部分回帖都是基于第一篇文章的,因此我們可以充分利用這個特性.另外我們需要將熱點話題的識別與話題跟蹤

7、的技術(shù)統(tǒng)一,便于對熱點話題的跟蹤.而且我們要求這個算法是無需人工干預的.1.2算法實現(xiàn)在我們的系統(tǒng)中使用的聚類算法仍然采用了目前國際上通用的對文本進行描述的方法(在這里,我們假設(shè)對每篇文檔的分詞工作已經(jīng)完成).對于所有BBS語料中的每一篇文章,我們有如下描述:收稿日期:2007一O1一lO.國家自然科學基金項目(60173027).李卓爾,碩士生,主研領(lǐng)域:數(shù)據(jù)庫知識與工程,信息檢索.2計算機應用與軟件2008血1)對文章中的每一個詞t賦予權(quán)重'log(0.5+)/df,)Wt.s廠一ll其中是詞t在文章s中出現(xiàn)的次數(shù),是在所有的語料中出現(xiàn)過這個詞t的文章數(shù),是所有文章的總數(shù).2)從每

8、篇文章中選出權(quán)重最大的1000個詞組成一個向量來表示它自己.1000這個閾值對于絕大部分文章來說能包含其所有詞,因為BBS語料中的文章絕大部分都具有篇幅短小的特點.但是對于一些特別長的文章,這個方法也能集中體現(xiàn)其內(nèi)容.而且規(guī)定這個閾值以后,每個向量的空間大小已經(jīng)確定,可以便于管理和儲存.3)我們通過計算兩個向量的余弦夾角來衡量兩篇文章的相似度:d.,Rsim(A,B)赫'其中sim(A,B)表示A,B兩篇文章的相似度,其他的符號含義同上.4)如果我們用一個向量來表示一個類,那么我們用以上公式也可以計算文章與類之間以及類與類之間的相似度.下面,可以開始介紹我們的系統(tǒng)中原始聚類算法的基本過

9、程了:(1)首先從原始BBS語料中將同一標題下帖子數(shù)大于一定數(shù)目(這個閾值可以綜合機器性能,文章總量,用戶關(guān)心話題的文章數(shù)等情況進行自由設(shè)定)的文章提取出來,并按文章數(shù)排序.從數(shù)目最大的文章集合開始,首先將文章向量化,然后求這些文章的加權(quán)平均值Cmean.在這里我們?yōu)槊恳黄恼略O(shè)置一個屬I生topiclD用來記錄其類別.然后將所有的文章向量與加權(quán)平均值Cmean進行比較,超過一定閾值od的劃歸一類;應該大部分文章都可歸到一類里,topielD標記為1,其余的topiclD標記為一2;對topiclD標記為1的文章重新計算加權(quán)平均值Cmean,將其當作類心,并記為c1.(2)從數(shù)目次大的文章集合

10、開始,文章向量化之后求這些文章的加權(quán)平均值Cmean,將該平均值與第一類的類心C1相比:.)如果超過閾值0,可以認為它們是同一類文章,將該集合內(nèi)的文章與Cmean作比較:超過閾值,標記該文章的topiclD為1;沒有超過閡值,則標記為一2,然后用Cmean和c1的加權(quán)平均值更新C1;b)如果沒超過閾值0,則認為它們不是同一話題的的文章,產(chǎn)生一個新類,產(chǎn)生的過程同步驟1,新類的topiciD記為2.(3)重復步驟2,設(shè)現(xiàn)在處理的是第K個集合,已有m個類,文章向量化之后求這些文章的加權(quán)平均值Cmean,將該平均值與m個類心相比,設(shè)與第i類的類心Ci(1im,1mK)最近(相似度最大):.)如果超過

11、閾值0,可以認為它們是同一類文章,用Cmean和c的加權(quán)平均值更新c,然后將該集合內(nèi)的文章與c作比較:超過閡值O/,標記該文章的topiclD為;沒有超過閾值O/,則標記為一(i+1);b)如果沒超過閾值0,則認為它們不是同一話題的的文章,產(chǎn)生一個新類,產(chǎn)生的過程同步驟1,新類的topiclD記為m+1.(4)假設(shè)共有n個這樣的集合,最后產(chǎn)生了C個類,對于標記為負值的文章,重新聚類,標記為一2的文章與第2C類的類心相比,相比過程同上.如果仍不能歸類,記為一1.標記為一i的文章與第iC類的類心相比,相比過程及歸類同上.如果仍不能歸類,記為一1.(5)對于原始BBS語料里剩余的帖子(TopiclD

12、為0),逐進行處理,可以歸類的topiclD標記為Ci;不能歸類的記為一1.(6)調(diào)整C個類的類心,并記錄下來.以后做話題跟蹤時,可以用相似的辦法,如果可歸為c類中的某一個,則屬于跟蹤的對象,給予標識;如果是新類,則屬于新的熱點話題,標識為新話題.2運用關(guān)聯(lián)信息改進原始算法在實際對BBS語料進行話題提取的過程中,我們發(fā)現(xiàn)BBS語料內(nèi)容十分繁雜,同一標題下經(jīng)常有許多與標題不相符的內(nèi)容,但是又基本上圍繞標題展開.圍繞這個性質(zhì),在進一步的研究中我們發(fā)現(xiàn)了如下兩點:(1)從同一個標題所有跟帖中分離出無關(guān)的帖子與將同個類別的文章歸類是有矛盾的.從宏觀上來說,從同一個標題所有跟帖中分離出無關(guān)的帖子是將一批

13、文檔逐漸縮小的過程;而將同一個類別的文章歸類是將很多批文檔聚合增大的過程.很明顯這兩個過程努力的方向是不一致的.(2)同一個類別中,每個標題下被分離出來的無關(guān)帖之間仍然有共同的地方.這一點是接下來我們要重點介紹的.首先我們定義兩個概念:?標題無關(guān)帖:從一個標題的所有跟帖中分離出的與標題無關(guān)的帖子.?關(guān)聯(lián)信息:在同一個類別的所有標題下產(chǎn)生的標題無關(guān)帖中,文字或語義有共同之處的一些帖子;或者是與其他標題下所討論內(nèi)容相關(guān)的帖子.下面我們用一些實例來說明什么是關(guān)聯(lián)信息.(以下語料均來自于)例如:中醫(yī)問題.標題1:科學本身就一定正確么?,有如下標題無關(guān)帖:1.你知道哥德爾不完備定理嗎?2.一樣的,別的東

14、西也有自己的完全一套邏輯.一樣可能有一定的不完美.所以,中醫(yī)可能比西醫(yī)更好,就看怎么標準法.標題2:方舟子:中醫(yī)批判小問答,有如下標題無關(guān)帖:1.西藥中有些副作用在投放時可能沒有發(fā)現(xiàn)后來慢慢顯著,所以現(xiàn)在藥品的生產(chǎn)和投放越來越嚴格.2.西醫(yī)只是借助自然科學研究中使用的部分儀器設(shè)備,試劑,及借鑒了某些思想,但離自然科學還差得遠呢.首先看標題1下的兩篇無關(guān)帖,很明顯并不是在討論科學的正確性問題,但是其中第2篇帖子明顯是在討論中醫(yī)問題,可見這篇帖子應該是歸人中醫(yī)問題這一類中的.然后比較兩個標題下的帖子,發(fā)現(xiàn)都有討論西藥或西醫(yī)的內(nèi)容.實際上從我們搜集的BBS語料中來看,凡是在討論中醫(yī)問題的,也會有很多

15、的帖子是在討論與西醫(yī)西藥相關(guān)的內(nèi)容.那么如果抓住了這一點,也有利于我們將這些標題下討論的內(nèi)容歸人正確的類別.從上面的例子中,我們可以看到有很多的關(guān)聯(lián)信息在聚類第8期李卓爾等:一種對BBS語料進行話題提取的聚類算法3時被丟棄了.由此,我們可以設(shè)想,希望在不影響每一個標題下標題無關(guān)帖分離工作的同時,運用關(guān)聯(lián)信息提高聚類的準確度.下面就來介紹改進后的話題提取聚類算法:(1)首先從原始BBS語料中將同一標題帖子數(shù)大于一定數(shù)目的文章提取出來,并按文章數(shù)排序.從數(shù)目最大的文章集合開始,首先將文章向量化,然后求這些文章的加權(quán)平均值,所有的文章向量與加權(quán)平均值進行比較,超過一定閾值的劃歸一類,標記這些文章,計

16、算出類心C1;然后取一個更小的閾值,將相似度超過的文章取出,計算出偽類心CI'.(2)從數(shù)目次大的文章集合開始,以同樣的方法求出加權(quán)平均值Cmean,將Cmean與第一類的偽類心C1'相比:a)如果超過閾值0,可以認為它們是同一類文章,將該集合內(nèi)的文章與Cmean作比較:超過閾值,標記該文章的topicID為1;沒有超過閾值,則標記為一2,然后更新cl.同樣,將超過閾值的文章取出,用來更新cl'.b)如果沒超過閾值0,則認為它們不是同一話題的的文章,產(chǎn)生一個新類,產(chǎn)生的過程同步驟1,新類的topiclD記為2.(3)重復步驟2,設(shè)現(xiàn)在處理的是第K個集合,已有m個類,文章

17、向量化之后求這些文章的加權(quán)平均值Cmean,將該平均值與m個偽類心相比,設(shè)與第i類的偽類心Ci'(1im,1mK)最近:a)如果超過閾值0,可以認為它們是同一類文章,然后將該集合內(nèi)的文章與Cmean作比較:超過閾值,標記該文章的topicID為i;沒有超過閾值,則標記為一(i+1),更新Ci;同樣,將超過閾值的文章取出,用來更新'.b)如果沒超過閾值0,則認為它們不是同一話題的的文章,產(chǎn)生一個新類,產(chǎn)生的過程同步驟1,新類的topicID記為m+1.(4)與改進前相同.(5)與改進前相同.3測試結(jié)果這里閾值取0.1;閾值分別取0.05,0.03和0.0l,與閾值取0.1的情況(

18、相當于改進前的算法)進行比較如圖l所示.圖1橫軸:閾值口縱軸:平均相似度增長量縱坐標表示相似度的平均增長數(shù)值,對于類間比較閾值0的經(jīng)驗取值0.21來說,這個增幅是明顯的.如果不是同一類,相似度增長的數(shù)值遠遠不及同一類增長的數(shù)值.這說明這個方法是有效的,不會混淆本不屬于同一類的文檔.從0.05到0.0l,增幅不明顯,說明關(guān)聯(lián)信息在閾值為0.05時已經(jīng)基本使用完了.4總結(jié)首先針對BBS語料的特殊性,介紹了一個實用的話題提取聚類算法.接下來在實際應用中發(fā)現(xiàn)還有一些沒有利用的關(guān)聯(lián)信息可以利用.于是利用關(guān)聯(lián)信息對原始聚類算法進行了改進,取得了良好的效果.接下來依然還有許多問題需要進一步研究并解決:1)如

19、何更準確地找到關(guān)聯(lián)信息?這里需要考慮排除本來就無關(guān)的文章和發(fā)現(xiàn)本來就應該屬于某話題而錯誤分離的文章.2)如何更好地利用關(guān)聯(lián)信息?關(guān)聯(lián)信息的相似程度與話題之間的相似程度有區(qū)別,加以統(tǒng)一的度量標準是否科學?是否可以將關(guān)聯(lián)信息加以準確地度量.3)如何對關(guān)聯(lián)信息內(nèi)部的各種類別話題進行區(qū)分?一個話題通常有許多種的關(guān)聯(lián)信息,這是使得與無關(guān)類別相似度也提升的主要原因.參考文獻1AllanJ,HardingS,FisherD,eta1.Takingtopicdetectionfromevalua?tiontopractice.InProceedingsofthe38'"HawaiiInter

20、nationalConfer-enceonSystemSciences,2005.2AllanJ,CarbonellJ,DoddingtonG,eta1.Topicdetectionandtrackingpilotstudy:Finalreport.InProceedingsoftheDARPABroadcastNewsTranscriptionandUnderstandingWorkshop,1998:194218.3AllanJ,PapkaR,LavrenkoV.On?lineneweventdetectionandtrack?ing.InProceedingsofConferenceon

21、InformationRetrievalResearch,1998:3745.4JamesAllan.Introductiontotopicdetectionandtracking.InJamesAI?lan,editor,TopicDetectionandTracking:EventbasedInformationOr-ganization.KluwerAcademicPublishers,Boston,2002:116.5ChristopherCieri,StephanieStrassel,DavidGraft,eta1.Corporafortopicdetectionandtracking.InJamesAll&a