袁曉峰

(鹽城師范學(xué)院信息科學(xué)與技術(shù)學(xué)院,江蘇鹽城 224002)

0 引 言

隨著計(jì)算機(jī)網(wǎng)絡(luò)的高速發(fā)展,人們?cè)絹?lái)越依賴于網(wǎng)絡(luò),而網(wǎng)絡(luò)上信息劇烈的膨脹又會(huì)讓人們覺得在網(wǎng)絡(luò)上尋找自己想要的信息越發(fā)變得困難了.為了幫助人們更快地找到想要的信息,文本聚類技術(shù)得到廣泛的研究[1-3].雖然目前有許多文本聚類方法,但是還很少有主題聚類的方法,而主題聚類的結(jié)果更能讓用戶一目了然.主題聚類的思想是根據(jù)文本的主題來(lái)劃分類別,將具有相同主題的文本歸為一類.我們認(rèn)為,Web文本的標(biāo)題有助于主題的歸納,甚至有些文本的標(biāo)題就是主題,例如我們搜索的關(guān)鍵字序列為“世界重新認(rèn)識(shí)中國(guó)”,搜索引擎返回的結(jié)果中包含標(biāo)題為“汶川地震讓世界重新認(rèn)識(shí)中國(guó)”的文本,這個(gè)標(biāo)題就直接能反應(yīng)文本的主題;而有些就不能反應(yīng)文本的主題,對(duì)此,還必須進(jìn)一步從正文中抽取出文本的主題.基于此,本文提出一種基于主題的Web文本聚類算法(HTBC),同時(shí),在實(shí)驗(yàn)中我們還將 HTBC與經(jīng)典的文本聚類算法(KMeans、AHC、STC)做了比較,實(shí)驗(yàn)結(jié)果表明,HTBC在聚類的準(zhǔn)確率、召回率方面比傳統(tǒng)的算法要好.

1 文本聚類算法概述

目前,文本聚類算法大致上可以分為層次聚類(Hierarchical Clustering)和非層次聚類 (Partitional Clustering)[1,2].層次聚類算法的代表是會(huì)聚層次聚類方法(AHC),它首先假設(shè)所有文本自成一類,然后將最相似的兩類合并,并繼續(xù)這一過(guò)程,直到將所有文本合并為一類,因而可以形成一棵聚類樹.AHC的優(yōu)點(diǎn)是能夠清晰地顯示整個(gè)聚類過(guò)程以及中間聚類方法.非層次聚類方法的代表是K-均值聚類方法(K-Means).K-Means是一種典型的基于劃分的方法,其基本原理是首先選擇k個(gè)文本作為初始的聚類點(diǎn),然后根據(jù)簇中對(duì)象的平均值,將每個(gè)文本重新賦予最類似的簇,并更新簇的平均值,然后重復(fù)這一過(guò)程,直到簇的劃分不再發(fā)生變化.

上述兩種方法最主要的缺點(diǎn)是需要事先確定一個(gè)停止條件.比如,AHC要求事先確定所要聚成的類別數(shù),而K-均值聚類則需要設(shè)定K值.而上述條件往往在實(shí)際應(yīng)用中很難事先確定.此外,它們都不能很好地描述和解釋聚類的結(jié)果.再者,這些方法限定每個(gè)文本只能屬于一個(gè)類,而沒有考慮一個(gè)文本可能屬于多個(gè)主題的情況.

后綴樹聚類算法[3](STC)較好地克服了上述缺點(diǎn).STC利用一種名為后綴樹的數(shù)據(jù)結(jié)構(gòu)來(lái)發(fā)現(xiàn)文本所共同含有的短語(yǔ)信息并進(jìn)而利用這些信息來(lái)構(gòu)建基本類.為了避免出現(xiàn)大量重復(fù)的或非常相似的類別,STC合并那些高度重疊的基本類.但STC不是一種基于主題的聚類方法,因?yàn)樗鼰o(wú)法保證一個(gè)類別中包含共同短語(yǔ)信息的文本都是關(guān)于同一主題的.

2 HTBC算法

HTBC算法首先根據(jù)文本的標(biāo)題和正文提取文本的主題詞向量,然后通過(guò)訓(xùn)練文本集成生詞聚類,并將每個(gè)主題詞向量歸類到其應(yīng)屬的詞類,再將同屬于一個(gè)詞類的主題詞向量對(duì)應(yīng)的文本歸并到用對(duì)應(yīng)詞類的名字代表的類,從而達(dá)到聚類的目的.HTBC算法的步驟包括預(yù)處理、建立主題向量、生成詞聚類和主題聚類等環(huán)節(jié).

2.1 預(yù)處理

由于文本中有些詞語(yǔ)對(duì)文本主題的概括幫助甚微,甚至沒有幫助且會(huì)干擾主題的提取,所以必須要對(duì)文本集進(jìn)行預(yù)處理.有一些詞在文本中出現(xiàn)頻率極高,可將其稱為停用詞,如“的”“我”“你”“地”等,停用詞對(duì)主題概括沒有任何幫助.此外,還有一些出現(xiàn)頻率極低的詞同樣對(duì)主題概括沒有幫助,所以在預(yù)處理時(shí)應(yīng)考慮將其剔除.

另外,在預(yù)處理時(shí)應(yīng)將正文部分做中文分詞的同時(shí)進(jìn)行詞性標(biāo)注,去除停用詞、副詞、形容詞、功能詞和虛詞等對(duì)主題基本沒幫助或者幫助甚微的詞,僅保留動(dòng)詞、名詞.同樣,對(duì)文本的標(biāo)題,也應(yīng)按上述方法進(jìn)行處理.

2.2 計(jì)算各特征項(xiàng)的權(quán)重

文本聚類之前需要將文本表示為計(jì)算機(jī)能夠處理的形式.目前,向量空間模型(VSM)是使用較多且效果較好的表示方法之一[4],其計(jì)算特征權(quán)值w的一種方法是TFIDF[5],詞條ti在文本d中的TFIDF值由下式定義:

其中,TFi是詞條ti在文本d中出現(xiàn)的頻數(shù),N表示全部訓(xùn)練文本的總數(shù),DFi表示包含詞條ti的文本頻數(shù).

通常,標(biāo)題中出現(xiàn)的詞肯定是比正文中出現(xiàn)的詞對(duì)主題的概括更為重要.據(jù)統(tǒng)計(jì),標(biāo)題中出現(xiàn)的詞的重要性是正文中出現(xiàn)的相同詞的5倍[6].

在計(jì)算文本正文中每個(gè)詞的頻率時(shí),考慮是否有與標(biāo)題中相同的詞,如果有則按下式計(jì)算,

在此基礎(chǔ)上,挑選每篇文本中 TFIDF值高于閾值v的詞作為一個(gè)主題用向量加以保存,用以聚類.

2.3 聚 類

在進(jìn)行聚類時(shí),可考慮利用計(jì)算詞序列之間的相關(guān)度來(lái)排除干擾詞,同時(shí)進(jìn)行合并.

詞的相關(guān)度通常采用互信息(MI)來(lái)計(jì)算[7],因?yàn)檫@種方法在處理中文文本時(shí)具有較好的性能[8].

如果用A表示包含詞條t且屬于類別c的文本頻數(shù),B為包含t但是不屬于c的文本頻數(shù),C表示屬于c但是不包含t的文本頻數(shù),N表示語(yǔ)料中文本總數(shù),t和c的互信息可由下式計(jì)算:

通過(guò)在訓(xùn)練文本集中計(jì)算各主題詞向量中特征項(xiàng)的相關(guān)度,然后用一個(gè)最能反映主題的詞作為種子詞,并將其作為最終類的代表.

2.4 HTBC算法的具體步驟

HTBC算法的具體步驟如下:

(1)特征項(xiàng)選取.對(duì)待聚類文本集中的文本進(jìn)行預(yù)處理,得到詞集,W={W1,W2,…,Wm},Wi= {wi1,wi2,…,wim}.其中,i表示所在文本序號(hào).對(duì) W中的詞進(jìn)行詞頻統(tǒng)計(jì),并選取頻度大于閾值f的詞構(gòu)成特征項(xiàng)集,T={T1,T2,…,Tm},Tij={twil1, twi2,…,twij,…,twim}.

(2)生成訓(xùn)練詞序列.將訓(xùn)練文本集進(jìn)行預(yù)處理,得到詞序列,U={w1,w2,…,wn}.

(3)詞聚類.先將U中每個(gè)詞wi作為一個(gè)類.對(duì)U中每個(gè)詞wi(i=1,2,…,n),按(3)式依次計(jì)算它與U中每個(gè)詞wj(j=1,2,…,n)的互信息 MI(wi, wj),若MI(wi,wj)≥r(r為給定的聚類閾值),則將詞wj歸于wi所屬的類,否則繼續(xù)計(jì)算wi與U中下一個(gè)詞的互信息,直到U中所有詞都計(jì)算完畢,得到詞類序列.其中,每個(gè)詞類由一個(gè)詞表示,每個(gè)詞類記為 uwi(uwi1,uwi2,…,uwik),uwi為U中的第i個(gè)詞表示的詞類.

(4)文本聚類.從 T取出未處理的特征項(xiàng)Ti,在詞類中查找,如果任意 Tij都屬于同一個(gè)詞類wi,則標(biāo)注 Ti屬于wi.否則將少數(shù)不屬于wi的干擾詞剔除,并標(biāo)注Ti屬于wi.重復(fù)該過(guò)程,直到所有的Ti都處理過(guò).最后將同屬一個(gè)詞類的特征項(xiàng)對(duì)應(yīng)的文本劃分到以詞類名表示的簇.

3 實(shí) 驗(yàn)

在實(shí)驗(yàn)中,我們用“世界重新認(rèn)識(shí)中國(guó)”作為搜索語(yǔ)句,隨機(jī)下載的100篇相關(guān)文本作為測(cè)試語(yǔ)料,文本平均長(zhǎng)度約為325字,利用HTBC算法中步驟(1)、(2)得到特征項(xiàng)集T.再將特征項(xiàng)集中每個(gè)詞在新華網(wǎng)站的新華搜索中進(jìn)行搜索,并隨機(jī)選取500篇網(wǎng)頁(yè)文本下載作為訓(xùn)練語(yǔ)料庫(kù),有312個(gè)詞頻大于6的詞.根據(jù)初步實(shí)驗(yàn)及分析取聚類閾值 r=0. 005,共產(chǎn)生27個(gè)詞類,每個(gè)詞類至少包含2個(gè)元素.

在實(shí)驗(yàn)中,我們使用準(zhǔn)確率(precision)和召回率(recall)對(duì)算法進(jìn)行評(píng)價(jià).準(zhǔn)確率、召回率的定義如下:

其中,n(i,r)是聚類 r中包含類別i中的文本的個(gè)數(shù),nr是聚類形成的類別個(gè)數(shù),ni是預(yù)定義類別的個(gè)數(shù).

我們將待聚類文本集分別用 K-means、AHC、STC、HTBC算法進(jìn)行聚類,并計(jì)算聚類的準(zhǔn)確率、召回率,得到如圖1、圖2所示結(jié)果.

圖1 4種算法準(zhǔn)確率比較

圖2 4種算法召回率比較

從圖1、圖2的比較結(jié)果可看出,HTBC算法的精確度較其余3種經(jīng)典聚類算法要高許多,但召回率卻低于K-Means和AHC算法.這主要是因?yàn)檎Z(yǔ)言的復(fù)雜性,即同義詞可能擁有相去甚遠(yuǎn)的表達(dá)方式.但是,79.7%的召回率對(duì)互聯(lián)網(wǎng)上文本聚類方法來(lái)說(shuō)應(yīng)該是可以接受的.

4 結(jié) 語(yǔ)

在本文中,我們提出一種基于主題的Web文本聚類算法:即通過(guò)提取Web文本中的高頻詞,并結(jié)合文章的標(biāo)題,計(jì)算這些詞在文本中出現(xiàn)的頻率,取頻率最高的幾個(gè)組成主題向量,然后通過(guò)在訓(xùn)練文本集中計(jì)算每個(gè)主題向量中詞與詞之間的相關(guān)度,剔除相關(guān)度低的干擾詞,再計(jì)算不同主題向量中各個(gè)詞之間的相關(guān)度,并將相關(guān)度高的聚為一類.實(shí)驗(yàn)表明,本文提出的文本聚類算法具有較高的精確度和召回率,特別是精確度,較其他幾種經(jīng)典的聚類算法要高.

[1]劉泉鳳,陸 蓓,王小華.文本挖掘中聚類算法的比較研究[J].計(jì)算機(jī)時(shí)代,2005,6(1):7-8.

[2]Yanjun Li.Text Document Clustering Based on Frequent Word Meaning Sequences[J].Data and Knowledge Engineering,2008, 64(1):381-404.

[3]ZAMIR O E.Clustering Web Documents:A Phrase-Based Method for Grouping Search Engine Results[D].Washington DC:Unioversity of Washinton,1999.

[4]陳 濤,謝陽(yáng)群.文本分類中的特征降維方法綜述[J].情報(bào)學(xué)報(bào),2005,24(6):690-695.

[5]Xu D X.Energy,Entropy and Information Poterntial for Neural Coputation[D].Florida:Universtiy of Florida,1999.

[6]韓客松,王永成,沈 洲,等.三個(gè)層面的中文文本主題自動(dòng)提取研究[J].中文信息學(xué)報(bào),2005,15(4):45-49.

[7]Yang Z R,Zwolinski Z.Mutual Information Theory for Adaptive Mixture Models[J].IEEE Transactions on Pattern Analaysis and Machine Intelligence,2001,23(4):26-32.

[8]代六玲,黃河燕,陳肇雄.中文文本分類中特征抽取方法的比較研究[J].中文信息學(xué)報(bào),2004,18(1):26-32.