一種基于主題的Web文本聚類算法

袁曉峰

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

0 引 言

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

1 文本聚類算法概述

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

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

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

2 HTBC算法

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

2.1 預(yù)處理

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

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

2.2 計算各特征項的權(quán)重

文本聚類之前需要將文本表示為計算機能夠處理的形式.目前,向量空間模型(VSM)是使用較多且效果較好的表示方法之一[4],其計算特征權(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)的詞對主題的概括更為重要.據(jù)統(tǒng)計,標(biāo)題中出現(xiàn)的詞的重要性是正文中出現(xiàn)的相同詞的5倍[6].

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

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

2.3 聚 類

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

詞的相關(guān)度通常采用互信息(MI)來計算[7],因為這種方法在處理中文文本時具有較好的性能[8].

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

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

2.4 HTBC算法的具體步驟

HTBC算法的具體步驟如下:

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

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

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

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

3 實 驗

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

在實驗中,我們使用準(zhǔn)確率(precision)和召回率(recall)對算法進行評價.準(zhǔn)確率、召回率的定義如下:

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

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

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

圖2 4種算法召回率比較

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

4 結(jié) 語

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

[1]劉泉鳳,陸 蓓,王小華.文本挖掘中聚類算法的比較研究[J].計算機時代,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]陳 濤,謝陽群.文本分類中的特征降維方法綜述[J].情報學(xué)報,2005,24(6):690-695.

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

[6]韓客松,王永成,沈 洲,等.三個層面的中文文本主題自動提取研究[J].中文信息學(xué)報,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é)報,2004,18(1):26-32.