一種新的文本聚類算法

0基于夾角余弦系數(shù)的文本聚類分析frenet分布模式（ap）是2007年frey和dueck提出的一種新的聚類算法。它具有速度快、效率高、無需指定聚類數(shù)、更適合解決不同歐洲的空間問題（例如，不滿足對稱或三角形等）以及大規(guī)模稀疏矩陣的計算。因此，它被用來識別臉色識別、檢測基因、搜索最佳路線、碼書設(shè)計和實物成像。接收子傳播算法的基本思想是將所有樣本視為網(wǎng)絡(luò)節(jié)點，并根據(jù)網(wǎng)絡(luò)上每個邊的消息傳輸來計算每個樣本的收集中心。在聚類過程中，每個節(jié)點都會發(fā)送兩種消息，即集資能力和歸因度。集群結(jié)果取決于樣本數(shù)和消息傳輸。文本聚類是文本挖掘中的一種重要方法.通常采用向量空間模型來進行描述.其中,每一個單詞都作為特征空間的一維,每一個樣本都作為特征空間的一個向量.文本向量空間模型中常用夾角余弦系數(shù)(cosinecoefficient)來度量向量間的相似性,其計算公式如下:s=|X∩Y||X|1/2|Y|1/2,(1)其中,|X∩Y|代表文本向量X和Y共同包含的特征.|X|和|Y|代表兩個文本各自包含的特征詞的個數(shù).歐氏空間中,X=(x1,…,xn),Y=(y1,…,yn),其計算公式轉(zhuǎn)化為s=n∑i=1xiyi(n∑i=1x2i)1/2(n∑i=1y2i)1/2.(2)基于夾角余弦系數(shù)的向量空間方法簡單直接,但樣本數(shù)目的增加會使得向量空間矩陣變得非常高維而且稀疏.傳統(tǒng)方法通常需要在進行特征選擇或降維之后再進行文本聚類,因此需要花較長時間,且效果不夠理想.鑒于吸引子傳播算法具備處理非歐空間問題的能力及其高效的特性,本文嘗試利用基于非歐空間相似性度量的吸引子傳播算法處理文本聚類問題.Frey和Dueck在文獻中給出了尋找文章中心句以及搜索最優(yōu)航線的非歐空間相似性度量方法.同時指出在這兩個例子中,相似性分別有97%和36%是不滿足歐氏空間對稱性的;而第2個例子中還有97%的相似性不滿足三角不等式.在他們工作的啟發(fā)下,我們從文本間的差異信息和結(jié)構(gòu)信息出發(fā),提出了一種基于相似特征集、排斥特征集和仲裁特征集的新的非歐空間相似性度量方法,并提出了新的聚類算法:權(quán)吸引子傳播算法(weightaffinitypropagation,WAP).由于這種算法采用了新的相似性度量,不需要建立基于全局特征的高維稀疏矩陣,所以能夠在不進行特征選擇和降維的條件下進行聚類.因而解決了傳統(tǒng)聚類算法因計算高維稀疏矩陣導致計算復雜度較高的問題.另外,由于該算法在聚類時,不需要提前指定簇類的數(shù)目,大大提高了算法的實用性及靈活性.為了進行比較分析,我們把本文提出的WAP算法與k-means聚類算法、具備非線性特征的SOFM聚類算法以及采用經(jīng)典相似性度量的吸引子傳播算法3種經(jīng)典聚類算法進行了比較.k-means算法是由MacQueen于1967年提出的.該算法的應(yīng)用非常廣泛,曾被評為數(shù)據(jù)挖掘中最具影響力的10種算法之一.它的特點是能夠快速收斂到極值,缺點是需要事先知道簇類的數(shù)目并且容易陷入局部極值.自組織特征映射神經(jīng)網(wǎng)絡(luò)(SOFM)是由芬蘭學者Kohonen等人于1981年提出的一種非線性聚類算法.目前,該算法已經(jīng)被廣泛的應(yīng)用到工程學、醫(yī)學、經(jīng)濟學等多個領(lǐng)域.該算法的特點是能夠?qū)崿F(xiàn)非線性映射,缺點是計算量大且樣本輸入順序會影響聚類效果.采用經(jīng)典相似性度量的吸引子傳播算法(affinitypropagationwithcosinecoefficient,APCC)是指采用夾角余弦系數(shù)度量相似性,然后結(jié)合吸引子傳播算法進行聚類.實驗結(jié)果表明,WAP算法明顯優(yōu)于上述3種算法.1基于最優(yōu)證據(jù)的估計和更新消息矩陣設(shè)數(shù)據(jù)集合為D={d1,d2,…,dN},聚類問題就是要把該集合中的樣本按照某種度量劃分成若干簇類,使得類間距離極大化,類內(nèi)距離極小化.描述樣本間相似程度的統(tǒng)計量很多,目前用得最多的是距離和相似性.吸引子傳播算法以樣本之間的相似性作為輸入,輸出為簇類中心以及各樣本與簇類中心的所屬關(guān)系.算法中引入了兩類在樣本之間傳遞的消息:吸引度(responsibility)和歸屬度(availability).設(shè)樣本i和j屬于數(shù)據(jù)集合D.候選類代表樣本j從每個數(shù)據(jù)樣本i中搜集證據(jù)r(i,j)(稱為樣本j對樣本i的吸引度)來描述樣本j適合作為樣本i的類代表的程度;歸屬度為樣本i從候選類代表j搜集證據(jù)a(i,j)(稱為點i對點j的歸屬度)來描述樣本i選擇樣本j作為其類代表的適合程度.證據(jù)越強(即r(i,j)與a(i,j)之和越大),點j作為最終聚類中心的可能性就越大.計算和更新消息矩陣的方法分別如式(3)(4)(5)所示:r(i,j)=s(i,j)-maxj′{a(i,j′)+s(i,j′)},j′≠j;(3)a(i,j)={min{0,r(j,j)+∑i′≠i,jmax{0,r(i′,j)}},i≠j,∑i′≠jmax{0,r(i′,j)},i=j;(4)Rt+1=(1-λ)Rt+λRt-1,At+1=(1-λ)At+λAt-1;(5)其中,s(i,j)是樣本i和樣本j的相似性度量,λ∈稱為阻尼因子,R=(r(i,j)),A=(a(i,j))分別為吸引度矩陣和歸屬度矩陣,t代表算法的迭代次數(shù).算法流程如圖1所示.Frey和Dueck發(fā)表在Science的工作中,對于人工數(shù)據(jù)以及人臉圖像識別的例子采用了歐氏距離作為算法的相似性度量.不久,他們又在文獻中給出了圖像處理中有關(guān)非歐空間相似性的計算方法:s(i,k)=-min∥Τ0xi-Τxk∥2(6)或s(i,k)=m(i,k)-1ΝΝ∑j=1m(i,j)-1ΝΝ∑j=1m(j,k),(7)其中,式(6)中的T0和T分別代表圖像中心和圖像的窗口參數(shù);式(7)中的m(i,k)代表圖像i和圖像k滿足特定匹配的特征個數(shù).但由于其定義的相似性度量存在應(yīng)用領(lǐng)域的局限性,因此該方法不適合在文本聚類相關(guān)領(lǐng)域中推廣.Jiang等人將吸引子傳播算法應(yīng)用于碼本設(shè)計問題,給出了在該領(lǐng)域的自相似性計算方法:s(m,m)=ω×∑m′s.t.m′≠m{s(m′,m)}Ν-1,(8)其中,ω為憑經(jīng)驗設(shè)定的權(quán)值.文獻又進一步討論了自相似性對吸引子傳播算法聚類結(jié)果的影響.Michele等人針對微陣列數(shù)據(jù)分析問題設(shè)計了一種消息傳遞矩陣,其計算公式如式(9)所示:a(i,j)={min{0,r(j,j)+∑i′≠i,jmax{0,r(i′,j)}},i≠j,min{p,∑i′≠jmax{0,r(i′,j)}},i=j,(9)其中,參數(shù)p的作用是降低樣本將自身作為聚類中心的可能性.通過分析AP算法和有關(guān)的改進算法,我們注意到相似性的定義直接影響吸引子傳播算法的聚類能力.在Frey和Dueck等人工作的啟發(fā)下,我們針對文本聚類的特點提出了基于非歐空間相似性度量的權(quán)吸引子傳播算法.2資源委員會fpsi我們在分析文本時發(fā)現(xiàn):在很多文本中,標題、摘要以及各段段首語句中出現(xiàn)的單詞更能表達文章的中心思想.因此,基于文本的這種結(jié)構(gòu)信息以及文本間的相互關(guān)系,我們引入了如下3個概念:相似特征集、排斥特征集和仲裁特征集.對于樣本集合D={d1,d2,…,dN}中的任意一個樣本di(1≤i≤N),將它看作為形如{<f1i,n1i>,<f2i,n2i>,?,<fΜi,nΜi>}的集合.其中,fxi(1≤x≤M)代表樣本di的第x個特征,nxi代表di在第x個特征上的取值.M代表此樣本的特征的數(shù)量.于是D可以表示為N個由若干二元組集合構(gòu)成的超集,即:D={{<f11,n11>,<f21,n21>,?,<fΜ(1)1,nΜ(1)1>},?,{<f1Ν,n1Ν>,<f2Ν,n2Ν>,?,<fΜ(Ν)Ν,nΜ(Ν)Ν>}}.我們不考慮基于所有樣本和全部特征的向量空間,而是從兩個樣本間的相互關(guān)系出發(fā),設(shè)樣本集合D中的任意兩個樣本di,dj分別為:di={<f1i,n1i>,<f2i,n2i>,?,<fΜi,nΜi>}；dj={<f1j,n1j>,<f2j,n2j>,?,<fLj,nLj>}；1≤i,j≤Ν.它們的特征集合分別為Fi和Fj.即Fi={f1i,f2i,…,fMi};Fj={f1j,f2j,…,fLj}.令F(i,j)=Fi∩Fj,其示意圖如圖2所示,陰影部分為F(i,j).令ˉF(i,j)=Fi-F(i,j),其示意圖如圖3所示,陰影部分為ˉF(i,j).設(shè)DFj代表dj中具有較強區(qū)分力特征的集合,令?F(i,j)=F(i,j)∩DFj.其示意圖如圖4所示,陰影部分為?F(i,j).于是有F(i,j)+ˉF(i,j)=Fi,?F(i,j)?F(i,j).特殊情況下:F(i,j)=ue064,則ˉF(i,j)=Fi??F(i,j)=?.下面我們給出如下3個集合的定義:定義1.相似特征集.對任意兩個樣本di和dj,若di的部分特征被dj所包含,則由這些特征以及它們在dj中的取值構(gòu)成的二元組的集合稱為i與j的相似特征集(similarfeatureset,SFS),即<fqj,nqj>∈SFS(i,j)當且僅當fqj∈F(i,j),<fqj,nqj>∈dj.定義2.排斥特征集.對任意兩個樣本di和dj,若di的某些特征未被樣本dj所包含,則由這些特征以及它們在di中的取值構(gòu)成的二元組的集合稱為i與j的排斥特征集(rejectivefeatureset,RFS),即ue537fpi,npi>∈RFS(i,j)當且僅當fpi∈ˉF(i,j),<fpi,npi>∈di.定義3.仲裁特征集.任意兩個樣本di和dj,若di的某些特征也是dj的具有較強區(qū)分力的特征,則由這些特征以及它們在dj中作為強區(qū)分力特征時的取值構(gòu)成的二元組的集合稱為i與j的仲裁特征集(arbitralfeatureset,AFS),即<fmi,nDj>∈AFS(i,j),其中,fmi∈?F(i,j),nDj代表此特征在作為較強區(qū)分力特征時的取值.關(guān)于較強區(qū)分力特征的判定方法,我們在第3節(jié)討論.基于相似特征集、排斥特征集和仲裁特征集的概念,我們提出了權(quán)吸引子傳播算法.算法步驟為:①初始化.將樣本集轉(zhuǎn)化為N個由若干二元組集合構(gòu)成的超集D={{<f11,n11>,<f21,n21>,?,<fΜ(1)1,nΜ(1)1>},?,{<f1Ν,n1Ν>,<f2Ν,n2Ν>,?,<fΜ(Ν)Ν,nΜ(Ν)Ν>}}；②根據(jù)定義計算各樣本間的相似特征集SFS(i,j)、排斥特征集RFS(i,j)和仲裁特征集AFS(i,j);③計算各個樣本間的相似性:當i,j∈D(i≠j)時,設(shè):<fqj,nqj>∈SFS(i,j)；<fpi,npi>∈RFS(i,j)；<fmi,nDj>∈AFS(i,j)；則有:s(i,j)=α|SFS|∑q=1nq+β|AFS|∑m=1nm-γ|RFS|∑p=1np,(10)其中,α,β,γ為調(diào)節(jié)權(quán);|x|表示集合x中元素的個數(shù);④計算自相似性:s(i,i)=φΝ∑i,j=1;i≠js(i,j)Ν(Ν-1),(11)其中,φ為調(diào)節(jié)權(quán);⑤初始化兩種消息矩陣:r(i,j)=s(i,j)-max{s(i,j′)}；a(i,j)=0,j′≠j；(12)⑥根據(jù)式(3)(4)計算消息矩陣;⑦按式(5)更新消息;⑧消息矩陣疊加:R+A,找出對于每一個樣本i的候選聚類中心,即ci←argmax1≤k≤n[r(i,k)+a(i,k)]；(13)⑨重復步驟⑥～⑧直到全部樣本的聚類中心不再變化或達到預設(shè)的最大迭代次數(shù),算法結(jié)束.在權(quán)吸引子傳播算法中,我們從樣本間的相似、相斥和強相似3個不同的角度定義了3種集合以及它們對應(yīng)的調(diào)節(jié)權(quán),更加精細地給出了相似性的定義方法.由于權(quán)吸引子傳播算法具有能夠處理非歐空間問題的能力,且包含了不同樣本間的差異信息和樣本的主要特征信息,使得它能夠廣泛地應(yīng)用于文本挖掘、圖像處理以及基因發(fā)現(xiàn)等領(lǐng)域.3模型的運行時間權(quán)吸引子傳播算法在應(yīng)用到不同的領(lǐng)域時,3種集合的構(gòu)造方法略有不同.例如:在文本聚類時,相似特征集是指由樣本di和dj共同包含的特征詞及它們在dj中的詞頻構(gòu)成的二元組集合;而只屬于di的特征詞及它們在di中的詞頻所構(gòu)成的二元組集合就是di和dj的排斥特征集;還有一些屬于di的特征詞在dj中的標題、摘要或各段段首等重要部分也出現(xiàn)了,由這些詞及其在那些重要位置出現(xiàn)的頻率組成的二元組集合就是di和dj的仲裁特征集.在處理圖像問題時,可以將圖像的中心區(qū)域看作仲裁特征集;在處理基因發(fā)現(xiàn)問題時,可以把已知功能的編碼基因看作仲裁特征集等等.為了檢驗權(quán)吸引子傳播算法的聚類效果,我們選用了文本挖掘中常用的Reuters-21578(Reuters)數(shù)據(jù)集.該數(shù)據(jù)集由采用SGML格式的22個文件構(gòu)成,并帶有標題、類別以及文章的起始標記等信息.預處理時,先將22個文件依據(jù)標記切割成單個文本.然后選擇那些至少屬于一類的文本,通過刪除停頓詞、詞根還原以及計算詞頻的方法將Reuters數(shù)據(jù)集轉(zhuǎn)換成超集的形式:D={{<f11,n11>,<f21,n21>,?,<fΜ(1)1,nΜ(1)1>},?,{<f1Ν,n1Ν>,<f2Ν,n2Ν>,?,<fΜ(Ν)Ν,nΜ(Ν)Ν>}}.為了對聚類結(jié)果進行有效的評價,本文采用了文本挖掘領(lǐng)域常用的評價標準F-measure和Entropy,同時考慮了算法運行時間.F-measure是通過準確率和召回率來計算的.對于j個簇類中的i個類別,準確率Precison(i,j)和召回率Recall(i,j)的計算公式如下:Ρrecison(i,j)=ΝijΝj;(14)Recall(i,j)=ΝijΝi;(15)其中,Nij代表簇類j中類別為i的樣本數(shù),Nj代表簇類j中的樣本數(shù),Ni代表類別i中的樣本數(shù).則F-measure的計算公式為F(i,j)=2Ρrecison(i,j)Recall(i,j)Ρrecison(i,j)+Recall(i,j).(16)整個聚類結(jié)果的F-measure計算公式為F=∑iΝiΝmaxj(F(i,j)),(17)其中,N代表所有文檔的數(shù)目.F-measure的值越高,聚類的結(jié)果越好,同時,也越接近已知的人為劃分.與此相反,Entropy越小,表明聚類的結(jié)果越好.Entropy提供了一種考察簇類純度的度量指標.其計算方法如下:對于每一個簇類j,其Entropy為Ej=-∑iΡijlbΡij,(18)其中,Pij代表簇類j中的樣本屬于類別i的概率.整個聚類結(jié)果的Entropy是所有聚類的Entropy的加權(quán)平均和:E=∑j=1m(ΝjΝ×Ej),(19)其中,N代表整個數(shù)據(jù)集中的樣本數(shù),Nj代表簇類j中包含的樣本數(shù).除上述兩種對聚類結(jié)果的評價標準外,運行時間也是算法評價的重要指標.運行環(huán)境:Pentium(R)DualE21802.5GHz,2.5GHz,內(nèi)存2.0GB.實驗中,我們分別選擇了Reuters中常用的5個類別“acq”,“crude”,“earn”,“grain”和“money-fx”,分別采用200,300,500,700,1000個樣本進行測試.首先,我們通過大量的實驗對算法中調(diào)節(jié)權(quán)的選取進行了計算與分析(取不同權(quán)值時各次實驗的詳細結(jié)果請參見文獻).針對上述3種規(guī)模的數(shù)據(jù)集WAP算法的調(diào)節(jié)權(quán)選取如表1所示:此外,其余3種算法的初始設(shè)定如下:k-means算法的參數(shù)k取為5,每次運行隨機選擇200組初始中心.SOFM算法的輸入層節(jié)點個數(shù)為數(shù)據(jù)集包含的特征詞的個數(shù)(分別為3786,4814,6299,7559,8838),輸出層節(jié)點為數(shù)據(jù)集包含的樣本數(shù)目(分別為200,300,500,700,1000).APCC的相似性為歐氏空間中的夾角余弦系數(shù)度量(式(2)),但自相似性定義為s(k,k)=min1≤i,j≤Ν,i≠j{s(i,j)}-Ρ×(max1≤i,j≤Ν,i≠j{s(i,j)}-min1≤i,j≤Ν,i≠j{s(i,j)}),(20)其中,s(k,k)代表第k個節(jié)點的自相似性,P為調(diào)節(jié)參數(shù),與聚類得到的簇類數(shù)目有關(guān).本實驗中,我們根據(jù)文獻提供的AP算法的P調(diào)節(jié)方法,結(jié)合本文的數(shù)據(jù)集對系數(shù)P的選擇進行了調(diào)試.實驗表明,P取值分別為2,3,5,7,11時,APCC取得了較好的聚類效果,得到的簇類數(shù)目為5類.圖5～7分別給出了k-means,SOFM,APCC和WAP4種算法在F-measure,Entropy和運行時間上的比較.考慮到k-means算法初始中心選擇以及SOFM算法樣本輸入順序?qū)Y(jié)果的影響,下面各圖表中所列出的結(jié)果均為4種算法10次運行的平均結(jié)果.從圖5中我們可以看出,WAP算法明顯優(yōu)于k-means算法、傳統(tǒng)的SOFM算法以及基于經(jīng)典度量的AP算法.WAP的F-measure值平均比k-means高27.49%,比SOFM高98.76%,比APCC高21.31%;由圖6所示,WAP在Entropy上平均比k-means低20.45%,比SOFM低42.89%,比APCC低16.31%;表2給出了4種方法運行時間的比較,WAP的運行時間分別是k-means的5.57%,是SOFM的0.35%,而與APCC算法大致相當.圖7給出了4種方法運行時間對數(shù)與數(shù)據(jù)規(guī)模關(guān)系的比較結(jié)果,可以看出,k-means,SOFM與兩種AP算法的時間對數(shù)是呈較穩(wěn)定的倍數(shù)關(guān)系的