基于潛在語義分析的ＢＢＳ主題發現算法研究

摘要：快速、準確獲取BBS論壇主題已成為目前Web信息獲取中一個極其重要的研究方向。針對已有的BBS論壇中有影響力主題計算方法的不足，提出了一種基于潛在語義分析的主題發現方法，其思想是借助計算回帖之間的相似度，綜合時間、空間因素，對主題進行聚類，發現主題并加以實現。系統對BBS主題發現過程進行可視化和交互，從而更直觀反映主題的變化過程，更好地驗證了算法的有效性。

關鍵詞：潛在語義分析；BBS；主題發現

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)29-0431-03

Research on Discovery of BBS Topic Based on LSA

WU Hao1， GENG Huan-tong2

(1.Department of Computer Science，Anhui Business College of Vocational Technology，Wuhu 241002，China;2.College of Computer and Software，Nanjing University of Information Science Technology，Nanjing 210044，China)

Abstract: To obtain BBS topic effectively has been an important research field of web information processing. By analyzing the shortage of existed topic discovery algorithms， a new discovery method is proposed in the paper. The method is based on latent semantic analysis， by calculating the similarity between comments， clustering the topics with the factors of time and space. Finally the visual and interactive system is implemented， which can discovery topic drift and new topic timely and effectively.

Key words: Latent Semantic Analysis; BBS; topic discovery

1 引言

隨著Internet網絡的發展，越來越多的人選擇上網獲取信息和知識，而BBS論壇成為人們獲取信息、發表言論的重要場所。但其常帶有炒作和傳播快速的特性，如果非友善的用戶發布一些敏感信息，就可能帶來巨大的不良影響。 因此從BBS論壇中獲取敏感主題信息一方面將有助于人們快速獲取感興趣的網絡信息，另一方面有助于國家有關部門進行輿論監督和實時監控。因此對BBS論壇主題的快速、準確獲取已成為目前Web信息獲取中一個極其重要的研究方向[1，5]。

在線BBS論壇中，每天都會出現大量由論壇注冊用戶發表的主題信息。這些主題信息的特點是：1) 數量巨大，一些著名的論壇，例如新浪，搜狐等，每日更新的主題量數以千計；2) 以發表時間和回帖的數量結合在一起排序，發表過的主題相隔一段時間后就會被隨后的主題淹沒；3) 內容雜亂無章，論壇中摻雜了大量的無效信息。

傳統的有影響力主題計算方法是基于簡單的統計排序，對于每個主題，論壇系統統計出在某個固定時間段內對主題回帖的注冊用戶數作為衡量主題在論壇中影響力的標準。系統對所有主題的影響力進行排序取出前幾名影響力最大的主題作為該時間段內的熱門主題。但是，這種方法的缺陷在于：1) 沒有考慮回帖的內容，只是簡單地統計了回帖數量；2) 無法對主題進行聚類，并無法發現論壇中若干相關主題組成的當前論壇中關心的熱門話題。雖現有基于回帖鏈的影響力主題計算方法[3-4] ，通過計算詞語在回帖傳播鏈上的影響力，提取出高影響力詞語，同時，對這些高影響力詞語進行聚類，并以此為基礎，利用機會發現的思想，發現潛在的、具有影響力的詞語，再次對這些新添加的詞語進行聚類，最后，將每個主題依據詞語聚類的結果提取BBS論壇中具有影響力的主題。這種方法雖然考慮了到了傳統方法的不足，但是忽略了用詞的上下文環境，同時也存在同義詞帶來的誤判問題。為了克服BBS有影響力主題計算方法的以上缺陷，根據自然語言處理方面的相關技術，從論壇中發表的帖子內容上的聯系出發，提出一種基于潛在語義分析的方法，通過對帖子按照相似度進行聚類分析，來發現BBS主題和熱門話題。

2 BBS主題發現過程與主要算法

基于潛在語義分析的BBS主題發現的基本思想如下：針對BBS帖子文檔字數少，語言隨意的特點，基于潛在語義分析的主題發現方法運用了潛在語義分析技術來消除以往算法忽略用詞的上下文環境以及同義詞帶來的誤判問題，同時利用奇異值分解降秩的方法來達到信息過濾和去除噪聲的目的；在此基礎上，依據帖子的內容進行相似度計算，并加以聚類分析，從而有效、及時地發現主題漂移，更好地滿足輿論監控的要求。在實現上，系統對BBS主題發現過程進行可視化和交互，從而更直觀反映主題的變化過程，更好地驗證了算法的有效性。系統框圖如圖1所示。

從系統功能可分為四個部分：1) 將BBS論壇社區主題中的帖子分詞、去停用詞、統計每個詞語在每個帖子，每個主題和整個論壇中的詞頻，構造“詞匯-帖子” 矩陣；2) 使用LSA處理模塊完成矩陣奇異值分解，求出相似矩陣；3) 依據相似矩陣，計算帖子間的相似度，對帖子以及整個論壇的主題聚類；4) 通過可視化手段返回給用戶。

2.1 數據的獲取和預處理

借助網絡爬蟲從BBS論壇中獲取原始網頁，根據帖子與主題的關系將每個帖子作為一條記錄按照一定的格式也保存在數據庫中。數據的預處理模塊分為中文分詞、詞頻統計、詞語權重計算以及構造“詞匯-帖子”矩陣四個步驟組成。中文分詞與詞性標注采用中國科學院計算技術研究所研制的漢語詞法分析系統ICTCLAS[8]。由于ICTCLAS分詞系統是由C++語言實現的，而文中是使用JAVA語言來實現，因此我們采用C++與JAVA語言間的接口JNI技術將ICTCLAS分詞系統與我們的系統進行連接，并對其中接口文件的部分代碼進行了改寫，加入了詞典，詞頻統計等類以及一些方法。

在去除停用詞上，本文對第一類停用詞采用對照停用詞表的方法濾除，第二類依據中文分詞結果中帶有的詞性標注進行濾除。為進一步壓縮處理規模，只保留名詞。詞頻統計是本系統中的一項基本功能，完成對帖子進行詞頻統計。具體算法如下：

Input：List//帖子去停用詞得到的詞語鏈表

Output：Dic //詞典鏈表，其中每個元素包含詞和其出現的頻數

Alg.For i:=0 to length do//length是list的長度

If list.index(i) in dic//詞典中包含的當前詞

The value of Current word in dic add 1//value是詞典中對應詞的頻數

Else add list.index(i) to dic and set value 1 //不包含該詞，將其添入詞典，頻數設1

構造“詞語-帖子”矩陣Xm×n。構造如下：先統計所有帖子中出現的詞，建立空的“詞匯-帖子”矩陣，運用前面詞頻統計的結果依次填充每個帖子向量，如果包含該詞，就在相應位置上填充上權重值，如果不存在就設為0。最后得到“詞匯-帖子”矩陣。

Input：listall，Diclist //一個主題中所有帖子包含的詞匯；詞典鏈表，元素為每個帖子的詞典

Output：mtx //詞匯-帖子矩陣

Alg.For i:=0 to Diclist.length do

For j:=0 to listall.length do

If current dic contains current word //dic 當前帖子詞典 ，word當前詞匯

mtx[j][i]=diclist[i].value//value 當前詞在當前詞典中的頻數

Else mtx[j][i]=0

2.2 潛在語義分析和帖間相似度計算

潛在語義分析方法（Latent Semantics Analysis; LSA）是用線性代數的技術來發現文件或單詞間的潛在關系[2，6]。假設一個話題T，包含原帖在內的n帖子，用到了m個詞匯，構造“詞匯-帖子”矩陣Xm×n = [Xij] = (c1，c2，…，cn) = (w1，w2，…，wm)T，其中Xij表示詞匯i在帖子j中出現的頻數。矩陣奇異值分解（SVD）是算法的一個重要組成部分，文中采用周長發博士[7]提供的類包導入到工程中，將矩陣奇異值分解方法定義在矩陣類下，直接實例化一個矩陣后就可以直接調用了。以前面的“詞匯-帖子”矩陣Xm×n作為輸入，運用SVD進行分解. 分解成三個矩陣的乘積Xm×n=U×S×VT，其中U和V分別為m×m和n×n的正交矩陣，S為對角矩陣，S的非零對角元δi，(i=1…r)叫做矩陣X的奇異值，r為非零對角元的個數，從而計算原矩陣的相似矩陣X'。

利用相似矩陣X'來計算帖子間相似度。在文中，主要考查兩帖子間中意義相同或相近詞出現的分布情況，以此來判斷兩帖子間是否相似。計算帖子間相似度方法如下：如c1，c2對應的向量為（x1，x2，...，xm）和（y1，y2，...，ym）則c1與c2的相似度：

2.3 帖子與主題間聚類分析

文中對帖子的聚類分析分為兩個層次：一是同一主題內的帖子聚類分析，用以判斷此主題是否發生漂移；二是不同主題間的聚類分析，用以選出有影響力的主題。示意圖如2所示。

2.3.1 帖子聚類分析

根據前面相似度計算的結果，依據相似度運用最鄰近聚類算法進行聚類，將相似度大的帖子放在同一簇內，簇間相似度較小。將聚類結果（簇集）按照其影響力（簇集大小，緊密程度）排序，選出值最高的作為主題，根據原帖是否在該聚類中判斷是否發生漂移現象。過程如下：先將原帖作為簇集1，以后依次取一個帖子，找出其與已有簇集中各個元素的相似度最大的，如果大于閾值，將其添加到該簇集，否則重新生成一個聚類。

2.3.2 主題間聚類分析

使用上一步得出的各個主題的再次運用潛在語義分析，按照主題相似度進行聚類分析，選取出具有較高影響力的主題。按照帖子聚類的算法及方法，再對主題進行相似度聚類。具體做法如下：1) 根據帖內聚類的結果，選取每個主題中產生的主簇集代表該主題；2) 將主題中的詞用前面的結果再次進行詞頻統計，得到新的主題的詞典。其結構仍然由詞和其在該主題（主簇集）中的頻率；3) 構造“詞匯-主題”矩陣；4) LSA處理，計算相似度；5) 依據相似度進行聚類，綜合時間，空間考慮選取有影響力的主題。

3 實驗系統及實驗結果

3.1 實驗系統

系統在Eclipse環境下開發，本文使用SWT-Designer插件進行SWT程序開發。界面總共分為三個部分，包括主體列表，對應主題下的帖子列表以及聚類分析結果圖。通過jdbc與oracle數據庫相連。設置好閾值后，點擊聚類分析建立按鈕，聚類圖部分顯示出當前主題的帖子聚類效果圖。點擊左邊主題類表的編號時，會顯示對應的原帖內容及回帖列表，相似度閾值設置框用于設置聚類時的閾值。

3.2 實驗與結果

實驗數據取自天涯社區國際觀察板塊[9]。

第一類實驗：帖子聚類分析

運行程序，閾值為0.5時的運行結果。可以看出，有兩個簇集，且前十一個帖子為一個簇集，第十二個帖子單獨成為一個簇集，不論是在簇集大小還是緊密程度上簇集1較簇集2占有絕對優勢，因此我們認為，簇集1是反映該主題的主簇集，簇集2可以忽略，由于原帖包含在簇集1中，所以認為主題沒有發生漂移。與人工判斷是相符的。

閾值為0.8時的運行結果。簇集1和簇集3大小和緊密程度相當，在簇集中占較大優勢，簇集2簇集小而分散，簇集4小均被忽略。對簇集1和簇集3再進行時間上的考慮，簇集3因為靠近當前時間，可以認為其是一種新的發展傾向，可以認為它占有優勢，由于選取閾值較大，可能并未發生主題上大的改變，只是在語義上有細微差別。

通過以上分析，可以看出系統自動分析結果與人工分析結果基本吻合，這說明這種基于潛在語義分析的主題發現算法是有效的。

第二類實驗：主題間聚類分析

再次選取天涯網站論壇中的國際觀察板塊進行試驗[9]，共選取了此論壇中一段時間的帖子作為實驗語料（限于篇幅而未能列出）。整個語料大概有20個主題，230個帖子，通過計算得出了主題聚類，并通過分析選取出有影響力的主題。表1是主題聚類結果。

從表1中看出簇集3，包含主題數最多，包含帖子數也最多，這些主題都是圍繞關于日本問題的討論，可見日本問題是當前論壇中非常熱門有影響力的主題。同時我們對照原主題中的內容也可以看出簇1包含的三個主題都是同時關于軍事和國家之間的關系的。簇集3都是關于日本方面的話題，9，13，17都是關于朝鮮半島問題的。這個結果進一步驗證了算法的有效性。

4 結論與展望

從論壇的帖子內容分析出發，提出一種基于潛在語義分析的BBS主題發現算法。通過實驗，驗證了系統能夠對BBS論壇中主題下的帖子進行有效的聚類，并對主題的變化進行跟蹤，同時能夠對論壇主題進行聚類，幫助找出當前BBS論壇中的熱門話題。運用系統對國內一些熱門論壇數據進行分析，取得了較好的效果，作了有意義的探索。該方法還可用于博客主題信息挖掘中，有助于國家有關部門進行輿論監督和實時監控。值得進一步研究有：1) 通過主題聚類信息，跟蹤主題變化；2) 優化算法，能適應大規模數據分析。

參考文獻：

[1] 劉云峰，齊歡，代建民.潛在語義分析在中文信息處理中的應用[J].計算機工程與應用，2005，41(3):91-93.

[2] 劉昌鈺，唐常杰，于中華，等.基于潛在語義分析的BBS文檔Bayes鑒別器[J].計算機學報，2004，27(4):556-572.

[3] 蔣凡，高俊波，張敏，等.BBS中主題發現原型系統的設計與實現[J].數據庫與信息處理，2005，31(5):151-153.

[4] Matsumura N，Ohsawa Y，Ishizuka M.profiling of participants in online-community[J].American Association for Artificial Intelligence，2002，27(4):171-176.

[5] Seppanen J K，Bingham E，Mannila H.A simple algorithm for topic identification in 0-1 data PKDD2003[M].LNAI 2838， 2003:423-434

[6] Christos H，Papadimitriou，Hisao P R，et al.Latent Semantic Indexing:A Probabilistic Analysis[J].PODS 1998，Seattle，1998(1-3):159-168.

[7] 周長發.Java數值計算算法編程[M].北京:電子工業出版社，2007.

[8] 中文自然語言處理開放平臺[EB/OL].http://www.nlp.org.cn/project/project.php?proj_id=6.

[9] 天涯虛擬社區[EB/OL].http://www8.tianya.cn/default.asp.