彭 靜，翟 英，馮 爽

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

后綴樹(shù)算法在輿情聚類中的應(yīng)用

彭 靜1，翟 英2，馮 爽3

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

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

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

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

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

1 后綴及后綴樹(shù)定義

1.1 后綴定義

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

1.2 后綴樹(shù)定義

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

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

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

2.1 文檔表示為后綴樹(shù)［6］

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

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

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

如果2個(gè)文檔含有多個(gè)相同短語(yǔ)，說(shuō)明這2個(gè)文檔相似。通過(guò)計(jì)算得到文檔之間的相似度，超過(guò)一定閾值，文檔聚為一類。

2.2 應(yīng)用后綴樹(shù)實(shí)現(xiàn)文檔聚類的步驟

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

2）文檔表示為后綴樹(shù)，按短語(yǔ)進(jìn)行文檔聚類：表1中所示的節(jié)點(diǎn)a對(duì)應(yīng)的短語(yǔ)“cat ate”，文檔1和文檔3含有該短語(yǔ)，文檔1和文檔3聚類為1個(gè)基類。每個(gè)聚類后的基類通過(guò)計(jì)算得到1個(gè)值，值較高（超過(guò)一定閾值）的再進(jìn)行步驟3）。

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

表1 后綴樹(shù)節(jié)點(diǎn)、短語(yǔ)及文檔之間的關(guān)系Tab.1 Suffix tree nodes，prases and documents

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

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

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

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

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

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

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

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

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

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

應(yīng)用后綴樹(shù)算法對(duì)標(biāo)題和摘要自動(dòng)聚類的結(jié)果如表3所示，聚類處理時(shí)間1 500 ms。

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

4 結(jié) 語(yǔ)

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

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

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

［3］郭 莉，張 吉，譚建龍.基于后綴樹(shù)模型的文本實(shí)時(shí)分類系統(tǒng)的研究和實(shí)現(xiàn)［J］.中文信息學(xué)報(bào)（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；責(zé)任編輯：陳書欣

河北省科技支撐計(jì)劃項(xiàng)目（10213557）

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