后綴樹算法在輿情聚類中的應用

彭 靜，翟 英，馮 爽

（1.河北科技大學信息科學與工程學院，河北石家莊 050018；2.河北經(jīng)貿(mào)大學信息技術學院，河北石家莊 050061；3.河北科技大學教務處，河北石家莊 050018）

后綴樹算法在輿情聚類中的應用

彭 靜1，翟 英2，馮 爽3

（1.河北科技大學信息科學與工程學院，河北石家莊 050018；2.河北經(jīng)貿(mào)大學信息技術學院，河北石家莊 050061；3.河北科技大學教務處，河北石家莊 050018）

針對網(wǎng)絡輿情分析的需求背景，研究了通過后綴樹算法發(fā)現(xiàn)文本文檔之間的公共短語串，按公共短語串實現(xiàn)文檔聚類。網(wǎng)頁文檔的標題和摘要能代表文檔的主要思想，應用后綴樹算法實現(xiàn)對標題和摘要自動聚類，從而實現(xiàn)輿情信息自動聚類。

網(wǎng)絡輿情；后綴樹算法；文本聚類

在網(wǎng)絡輿情監(jiān)控系統(tǒng)中，包括輿情采集、輿情存儲、輿情分析和結(jié)果顯示4個主要模塊。輿情采集和存儲模塊對指定的網(wǎng)頁進行抓取、解析、中文分詞，按關鍵詞索引并存儲在輿情數(shù)據(jù)庫；輿情分析和顯示模塊實現(xiàn)根據(jù)關鍵詞進行輿情搜索并對搜索結(jié)果自動聚類顯示［1］。

輿情聚類的過程是實時的，為了提高速度，并不是對整個網(wǎng)頁文檔的全部內(nèi)容聚類，而是提取關鍵內(nèi)容：文檔標題、文檔摘要、文檔URL。文檔摘要能夠全面準確地反映文檔的簡單連貫的短文，比較準確地體現(xiàn)文檔的主題［2］，摘要提取本文不做討論。輿情分析模塊可以按標題、摘要和URL自動聚類。文檔標題和文檔摘要都看做短文本文檔，研究應用后綴樹算法實現(xiàn)短文本文檔的自動聚類［3］。

1 后綴及后綴樹定義

1.1 后綴定義

給定長度為n的字符串S＝S1S2…Si…Sn，子串SiSi＋1…Sn都是字符串S從i開始的后綴，記為S［i，…，n］。以字符串S＝abab為例，它的長度為4，所以S［1，…，4］，S［2，…，4］，… ，S［4，…，4］都是S的后綴，空字串＄也是后綴，字符串S后綴分別是：abab，bab，ab，b，＄（空字串）。包含這個字符串的所有后綴的壓縮 Trie［4］，就是字符串S的后綴樹。

1.2 后綴樹定義

一個具有n個字符的字符串S的后綴樹T，就是一個包含1個根節(jié)點的有向樹，該樹恰好帶有n個葉子，這些葉子被賦予從1到n的標號。除了根節(jié)點以外的每一個內(nèi)部節(jié)點，都至少有2個子節(jié)點，而且每條邊都用S的一個非空子串來標志。出自同一節(jié)點的任意兩條邊的標志不會以相同的詞開始。后綴樹的關鍵特征是：對于任何葉子i，從根節(jié)點到該葉子所經(jīng)歷的邊的所有標志串聯(lián)起來后恰好拼出S的從i位置開始的后綴，即S［i，…，n］。把樹中節(jié)點標志為從根到該節(jié)點的所有邊的標志進行串聯(lián)［5］，如圖1表示字符串S＝abab的后綴樹。

圖1 字符串S＝abab的后綴樹Fig.1 Suffix tree of string“abab”

2 后綴樹算法實現(xiàn)文檔聚類

2.1 文檔表示為后綴樹［6］

有3篇英文文檔，其內(nèi)容分別為cat ate cheese，mouse ate cheese too，cat ate mouse too，在英文文檔中，以空格分隔單詞，文檔中連續(xù)的多個單詞為有一定含義的單詞串，以下稱為短語，短語能反映文檔的含義，文檔由多個短語構成。以這3個文檔構建1棵后綴樹如圖2所示。

圖2 文檔的后綴樹表示Fig.2 Suffix tree of documents

樹中有10個葉子節(jié)點，每個葉子節(jié)點用一個二元組來表示，如葉子節(jié)點3，1表示第3個文檔，從位置1開始的后綴“cat ate mouse too”。a，b，c，d，e，f為內(nèi)部節(jié)點，從根節(jié)點到內(nèi)部節(jié)點的短語在多個句子中被包含，這個單詞串稱為短語，比如內(nèi)部節(jié)點a，從根節(jié)點到a節(jié)點的邊為短語“cat ate”，稱節(jié)點a的短語為“cat ate”。從a節(jié)點出發(fā)有2個葉子節(jié)點和，那么包含“cat ate”短語的文檔有文檔1和文檔3，后綴樹節(jié)點、短語和包含短語的文檔之間的關系如表1所示。

如果2個文檔含有多個相同短語，說明這2個文檔相似。通過計算得到文檔之間的相似度，超過一定閾值，文檔聚為一類。

2.2 應用后綴樹實現(xiàn)文檔聚類的步驟

1）文檔解析：這一步驟主要實現(xiàn)對文檔分詞，比如文檔1的內(nèi)容是“cat ate cheese”，以空格為分隔符，分解為3個單詞cat，ate，cheese。

2）文檔表示為后綴樹，按短語進行文檔聚類：表1中所示的節(jié)點a對應的短語“cat ate”，文檔1和文檔3含有該短語，文檔1和文檔3聚類為1個基類。每個聚類后的基類通過計算得到1個值，值較高（超過一定閾值）的再進行步驟3）。

3）基類的合并，第2步得到的基類合并為更大的文檔聚類。

表1 后綴樹節(jié)點、短語及文檔之間的關系Tab.1 Suffix tree nodes，prases and documents

在步驟2）中按短語進行文檔聚類，聚類的效果用一個分值來評價，這個分值相當于通常的文本分類的相似度，這里用S（m）來表示：式中：tf（w i，d）是w i在文檔d中出現(xiàn)的次數(shù)即詞頻；N是文檔集合中文檔的總數(shù)；df（w i）是w i所在文檔的個數(shù)。

第3步是基類的合并，在第2步中，確定了含有共同短語的為1個基類，然而1個文檔中包含多個短語，因此不同基類中包含的文檔可能是重疊的，比如c節(jié)點的短語聚類有文檔1和文檔2，f節(jié)點的短語聚類也包含文檔1和文檔2，STC算法的第3步是把不同的基類（有重疊或交叉的文檔經(jīng)過計算相似度超過一定閾值）合并成更大的聚類。

定義相互交叉或重疊的2個短語聚類之間的相似度用sim（mi，mj）表示，其值為

α取值在0～1之間，通常取0.7。

在表1的基礎上計算所有短語聚類的相似度，α取值分別為0.7的時候，合并基類的結(jié)果見圖3，聚類結(jié)果的表格形式見表2。

表2 短語聚類的合并結(jié)果Tab.2 Clusters identified by the phrase cluster

3 實驗結(jié)果及分析

聚類的數(shù)據(jù)源采用通過雅虎搜索的100篇關于“核爆炸”的網(wǎng)頁文檔。提取標題、摘要、URL，結(jié)果用XML文檔格式表示［7］。

圖3 短語聚類結(jié)果Fig.3 Phrase cluster graph

眾所周知，火星因富含氧化鐵的沙土呈現(xiàn)迷人的紅色。但最新科學研究發(fā)現(xiàn)，這顆行星并非生來如此。據(jù)英國《每日郵報》4月2日的報道，一名俄羅斯科學家日前指出，巨大的核爆炸是火星如今呈現(xiàn)紅色的真正原因，他還聲稱我們居住的地球在未來也可能會同樣地“變臉”。

應用后綴樹算法對標題和摘要自動聚類的結(jié)果如表3所示，聚類處理時間1 500 ms。

表3 網(wǎng)頁文檔聚類結(jié)果Tab.3 Clusters of web document

4 結(jié) 語

結(jié)合網(wǎng)絡輿情分析的應用背景，研究了后綴樹算法。通過對文本文檔建立后綴樹，發(fā)現(xiàn)文檔之間的公共短語串，實現(xiàn)文本文檔的聚類，不需要中文分詞，公共短語串比公共關鍵詞更能體現(xiàn)文檔之間的相似度。在輿情監(jiān)控系統(tǒng)中，對Web文檔的摘要、標題和URL應用后綴樹模型實現(xiàn)聚類，相當于對短文檔聚類，可以大大提高速度，有助于快速準確地發(fā)現(xiàn)輿情熱點，為進一步實現(xiàn)話題跟蹤打下基礎。

［1］湯寒青，王漢軍.改進的K-means算法在網(wǎng)絡輿情分析中的應用［J］.計算機系統(tǒng)應用（Computer Systems and Applications），2011，20（3）：165-168.

［2］廉 捷，劉 云.網(wǎng)絡輿情中的信息預處理與自動摘要算法［J］.北京交通大學學報（Journal of Beijing Jiaotong University），2010，34（5）：94-99.

［3］郭 莉，張 吉，譚建龍.基于后綴樹模型的文本實時分類系統(tǒng)的研究和實現(xiàn)［J］.中文信息學報（Journal of Chinese Information Processing），2005，19（5）：16-23.

［4］GUO Xi，YANG Xiao-chun，YU Ge，et al.Choosing meaningful structure data for improving web search［J］.Journal of Southeast University（English Edition），2008，24（3）：243-246.

［5］UKKONEN E.On-line construction of suffix trees［J］.Algorithmica，1995，14（3）：249-260.

［6］ZAMIR O E.Clustering Web docaments：A phrase-based method for grouping search engine results［D］.Washington：University of Washington，1999.

［7］SONG Ming－qiu，WU Xin-tao.Content extraction from Web pagesbased on Chinese punctuation number［A］.International Conference on Wireless Communications，Networking and Mobile Computing［C］.Shanghai：［s.n.］，2007.5 573-5 575.

Application of STC algorithm to internet public opinions clustering

PENG Jing1，ZHAI Ying2，F(xiàn)ENG Shuang3
（1.College of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；2.College of Information Technology，Hebei University of Economics and Bussiness，Shijiazhuang Hebei 050061，China；3.Department of Teaching Affairs，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China）

In answer to the requirement of internet opinions analysis，this paper discusses the STC algorithm for text clustering，in order to discover common phrases that can assign documents and form document clusters.Because web document titles and abstracts can express the main ideas，web document clusters are created by STC algorithm，and clusters of internet public opinions information are created by using this method.

internet public opinions；STC algorithm；text clustering

TP391.1

A

1008-1542（2012）01-0065-04

2011-06-27；

2011-11-17；責任編輯：陳書欣

河北省科技支撐計劃項目（10213557）

彭 靜（1970-），女，河北定州人，副教授，碩士，主要從事文本挖掘方面的研究。