文本聚類中的貝葉斯后驗(yàn)?zāi)Ｐ瓦x擇

1、8- 辛宀姜寧文本聚類中的貝葉斯后驗(yàn)?zāi)Ｐ瓦x擇方法史忠植中國(guó)科技大學(xué)研究生院計(jì)算機(jī)學(xué)部北京100039)(中國(guó)科學(xué)院計(jì)算技術(shù)研究所北京100080)摘要文章對(duì)聚類分析中的模型選擇特別是混合模型方法進(jìn)行了較全面地介紹與總結(jié)，對(duì)其中的關(guān)鍵技術(shù)逐一進(jìn)行了討論。在此基礎(chǔ)上，文中提出了貝葉斯后驗(yàn)?zāi)Ｐ瓦x擇方法，并把它與文檔產(chǎn)生特征序列的物理模型相結(jié)合，給出了一個(gè)用于聚類分析的概率模型。對(duì)真實(shí)文本數(shù)據(jù)的測(cè)試中該模型取得了了非常好的效果。同時(shí)本文對(duì)不同的貝葉斯估計(jì)方法的效果進(jìn)行了討論。關(guān)鍵詞文本聚類、貝葉斯后驗(yàn)?zāi)Ｐ瓦x擇、混合模型、期望最大化、貝葉斯估計(jì)BayesianPosteriorModelSelectio

2、nforTextClusteringAbstractAcompleteintroductionofthemodelselectioninclusteringanalysisisincludedinthepaper,andkeytechnologiesinitarediscussedseriatim,adhocmixturemodel.Basedonthese,theauthorintroducestheBayesianposteriormodelselection.Thispaperalsodescribesaposteriormodelbasedhierarchicalclusteringa

3、lgorithm,withtheanalysisofthedomainitself.Resultsofhighaccuracyhavebeenachievedinexperimentsforrealworldtextclustering.KeywordsTextClustering,BayesianPosteriorModelSelection,MixtureModel,ExpectationMaximization,BayesianEstimation1.引言與結(jié)構(gòu)化的信息相比，非結(jié)構(gòu)化的文本信息更加豐富與繁雜。隨著互聯(lián)網(wǎng)絡(luò)的發(fā)展，Web上的文本資源在幾年間呈現(xiàn)爆炸式的增長(zhǎng)。這些文本信息數(shù)據(jù)

4、量大、內(nèi)容繁雜而且處在不斷變化之中。隨著信息資源的日益豐富，如何充分有效的利用信息成為人們關(guān)注的焦點(diǎn)。聚類分析作為一種數(shù)據(jù)挖掘的重要手段，在文本挖掘中也扮演著非常重要的角色。在最近幾年的研究文獻(xiàn)中1，一類基于概率模型的聚類分析技術(shù)逐漸被研究者所關(guān)注。研究人員通過(guò)分析數(shù)據(jù)與各種概率模型之間的匹配問(wèn)題，提出了一系列新的聚類算法。同時(shí)這方面的研究也表明，許多傳統(tǒng)的聚類算法都可以解釋為某種概率模型的近似。常用的K均值算法和Wards方法也可以用特定情形下的多元正態(tài)模型加以解釋2。本文介紹了基于模型選擇進(jìn)行聚類分析的理論，和相關(guān)的基本算法。在此基礎(chǔ)上討論了一種特征序列的“隨機(jī)發(fā)生”模型，并給出了一個(gè)基于

5、貝葉斯后驗(yàn)概率的模型選擇算法。其中對(duì)于參數(shù)的學(xué)習(xí)，我們采用了兩種不同的貝葉斯估計(jì)策略，最大后驗(yàn)估計(jì)和條件期望估計(jì)，并進(jìn)行了比較?；诒疚牡暮篁?yàn)?zāi)Ｐ停覀冊(cè)O(shè)計(jì)了采用層次聚類的算法進(jìn)行測(cè)試。通過(guò)測(cè)試，新的算法取得了令人滿意的效果，對(duì)正式文本數(shù)據(jù)的測(cè)試準(zhǔn)確率達(dá)到了85%。值得一提的是，新算法對(duì)目標(biāo)聚類數(shù)目不敏感，即使應(yīng)用選擇的目標(biāo)個(gè)數(shù)不是最佳的，也能獲得較好的精度，這大大提高了算法的應(yīng)用價(jià)值。另外，MSBE與MSBP的對(duì)比也表明了采用隨機(jī)化的條件期望估計(jì)能更好的適應(yīng)稀疏數(shù)據(jù)的情況。2.貝葉斯模型選擇模型選擇的原理模型選擇問(wèn)題可以表述為在給定的數(shù)據(jù)樣本和相關(guān)參數(shù)信息的條件下，尋求具有最大后驗(yàn)概率的模型

6、。在給定的樣本D下，某一模型M的后驗(yàn)概率與M的先驗(yàn)概率和似然函數(shù)的乘積成比例，因而模型選擇問(wèn)題可以表示成下面的優(yōu)化問(wèn)題：argmaxP(M|D)argmaxP(D|M)P(M)(2-1)MM貝葉斯方法下的模型選擇通過(guò)選取適當(dāng)?shù)哪Ｐ拖闰?yàn)分布p(m)，可以將人類專家的知識(shí)和給定的樣本數(shù)據(jù)中提供的信息結(jié)合在一起3。在沒(méi)有任何先驗(yàn)信息的情況下，可以采用貝葉斯假設(shè)將p(M)看作均勻分布。這種情況下模型選擇問(wèn)題可以進(jìn)一步化簡(jiǎn)為似然函數(shù)P(D|M)的優(yōu)化問(wèn)題：argmaxP(MID)二argmaxP(DIM)(2-2)MM為了比較不同模型的優(yōu)略，通常采用貝葉斯因子B(bayesfactor)2：12P(DI

7、M)B=112P(DIM)2(2-3)混合模型在基于概率模型的聚類分析中，通常認(rèn)為數(shù)據(jù)是通過(guò)多個(gè)相互獨(dú)立的過(guò)程產(chǎn)生的，其中每個(gè)產(chǎn)生過(guò)程對(duì)應(yīng)著一個(gè)類別。數(shù)據(jù)產(chǎn)生的概率可以用混合模型表示。混合模型(mixturemodels)假設(shè)數(shù)據(jù)的分布是一些簡(jiǎn)單分布的線性組合。如果已知分類類別數(shù)為K，混合模型可表示為K個(gè)分量分布的混合：P(dIM)=P(M)P(dIM)(2-4)kkk=1其中M是混合模型，m表示與第k個(gè)類別Mk相對(duì)應(yīng)的模型分量。分量分布P(dIM)表示類別kk產(chǎn)生數(shù)據(jù)d的概率，P(M)表示分量P(dIM)的權(quán)重，可以理解為從數(shù)據(jù)全集中(而不是給定的樣本中)取出一個(gè)數(shù)據(jù)恰好是類別k的先驗(yàn)概率。

8、分量分布的選擇很大程度上決定了混合模型對(duì)數(shù)據(jù)的適應(yīng)能力，選擇適當(dāng)?shù)姆植甲鍖?duì)于混合模型的效果有很大影響。由于數(shù)學(xué)處理方便等原因，通常選擇多元正態(tài)分布(multivariatenormal)作為分量分布，在這種形式下混合模型的分布為超橢圓分布(hyperellipsoidal)4。如果給定的數(shù)據(jù)d=ddd是一個(gè)隨12N機(jī)樣本，其中的每一個(gè)實(shí)例d,d都是相互獨(dú)立ij的。上面的混合模型M對(duì)樣本D的似然函數(shù)可以表示為：L(DIM)=口P(M)P(dIM)(2-5)kkdGDk=1混合模型的期望最大化前面已經(jīng)指出，模型選擇問(wèn)題通常轉(zhuǎn)化為對(duì)argmaxL(DIM)的優(yōu)化冋題。L(DIM)中通常包M含某些與M

9、相關(guān)的參數(shù)需要確定，一般可以采用最大似然估計(jì)既L(DIM)=maxL(DI0)。通常0要通過(guò)解析方法求解混合模型的最大似然估計(jì)值非常困難，需要采用某種數(shù)值方法，如期望最大化算法(EM,expectationmaximization)0EM算法是一種常用的求解最大似然估計(jì)和最大后驗(yàn)估計(jì)的方法，特別是在似然函數(shù)形式較復(fù)雜時(shí)非常有效。EM算法的推廣形式，如MonteCarloEM和CEM2等也較為常見(jiàn)。本文將要介紹的算法通過(guò)選擇適當(dāng)?shù)哪Ｐ?，能夠通過(guò)解析方法直接得到參數(shù)，避免了這種復(fù)雜性。這里僅對(duì)混合模型的EM算法作一個(gè)簡(jiǎn)單介紹。基本的EM算法是一個(gè)迭代的過(guò)程，它交替的執(zhí)行E步和M步，直到參數(shù)的估計(jì)穩(wěn)

10、定為止，以達(dá)到使似然函數(shù)值最大的目的。它的迭代過(guò)程可描述如下：E步，基于當(dāng)前的參數(shù)估計(jì)，計(jì)算添加潛在數(shù)據(jù)后似然函數(shù)對(duì)潛在數(shù)據(jù)的條件期望Q(0,0)；M步，基于E步的期望值，最大化當(dāng)前的參數(shù)估計(jì)0=argmaxQ(0,0)；0混合模型的EM算法關(guān)鍵在于確定q(0,0)的表達(dá)式，為此我們重新書(shū)寫(xiě)混合模型的形式，并省去M以簡(jiǎn)化書(shū)寫(xiě)。記0為模型M的參數(shù)集，b=P(M)，0為P(dIM)與模型的分量Mkkkkk相關(guān)聯(lián)的參數(shù)：P(d10)=P(d10)(2-6)kkk=1為使用EM算法，為每個(gè)數(shù)據(jù)d添加一個(gè)指示類別的潛在矢量屮(d)=仰(d)M(d)，M(d)，并12K且：屮(d)=|1ifdGck，這使

11、得屮(d)的值域是一k0else離散有限集合。模型M在添加數(shù)據(jù)屮(由所有的屮(d)構(gòu)成的矩陣)下的對(duì)數(shù)似然表示為：logL(DI屮,0)=ElogbP(d10)(2-7)c(d)c(d)dGD式中我們用c(d)表示屮(d)為文檔d所指派的類別，也就是屮(d)中僅有的為1的分量。在給定當(dāng)前參數(shù)0下屮的分布可以表示為：P(屮ID,0)=nP(屮(d)Id,0)(2-8)dGD其中：.&P(dIO)P(屮(d)Id,0)=c(d兗&P(dIO)kk(2-9)k=1計(jì)算logL(DI屮,0)在給定的樣本數(shù)據(jù)d和給定的參數(shù)0上的條件期望：Q(0,0)=ETogL(DI屮,0)ID,0=工logL(DI屮

12、,0)P(屮ID,&)屮K(2-10)=LLlog(CT)P(d,TI0)+kkk=1dgDKLLlogP(d10)P(d,TI0)kkk=1dgD此式的詳細(xì)化簡(jiǎn)過(guò)程可以參考文獻(xiàn)6的敘述。再EM的迭代過(guò)程中，更新的&總可以使模型對(duì)給定數(shù)據(jù)的似然函數(shù)值得到改善。一般在給出具體的分布形式之后，0=argmaxQ(0,0)0的更新，可以通過(guò)拉格朗日乘數(shù)法進(jìn)行計(jì)算。采用高斯分布時(shí)具體的表達(dá)式可以在文獻(xiàn)6中找到。采用多項(xiàng)分布的情況可以參考3。EM算法處理混合模型存在一些限制2，對(duì)于混合模型，算法的收斂速度變得非常慢，而且算法得到的往往是一個(gè)局部極大值而不是最大值。樣本中屬于某個(gè)類別的對(duì)象較少時(shí)，算法產(chǎn)生

13、較大的誤差。即使這樣，EM算法仍然被廣泛地用于混合模型的最大似然估計(jì)，并且取得了不錯(cuò)的效果。證據(jù)在貝葉斯分析中，當(dāng)P(D|M)中存在未知的參數(shù)時(shí)，可以通過(guò)期望最大化找到其最大似然估計(jì)值。這種方法僅當(dāng)每個(gè)類別都有足夠的樣本點(diǎn)時(shí)，才能獲得較理想的效果。一般來(lái)說(shuō)對(duì)參數(shù)進(jìn)行隨機(jī)化處理，引入?yún)?shù)的先驗(yàn)分布，可以使結(jié)果更具穩(wěn)健性。對(duì)P(DIM)中的參數(shù)應(yīng)用全概率公式有：P(DIM)=fL(DI0,M)兀(0IM)d0(2-11)上式中0是似然函數(shù)中的參數(shù)，l(DI0,M)表示在給定參數(shù)下的似然函數(shù)，兀(0IM)是模型M中參數(shù)的先驗(yàn)分布。此時(shí)的P(dim)稱為M的邊界似然(MarginalLikelihoo

14、d)或積分似然(IntegratedLikelihood)7或者稱為證據(jù)(Evidence)8。與多層先驗(yàn)相類似，隨機(jī)化處理是邊界似然比點(diǎn)估計(jì)能得到更好的穩(wěn)健型。在高維的參數(shù)空間下，計(jì)算混合模型的邊界似然是非常困難的，需要采用某種近似形式。常用的近似方法有BIC(BayesianInformationCriterion)和AIC(AkaikeInformationCriterion)：BIC:2logP(DIM)2logL(DI0,M)-vlog(n)(2-12)AIC:logP(DIM)logL(DI0,M)-n(2-13)其中v是獨(dú)立參數(shù)的個(gè)數(shù)，L(D|0,M)是最大對(duì)數(shù)似然估計(jì)值，n是樣

15、本數(shù)據(jù)的個(gè)數(shù)。此外在AutoClass10中給出了一種通過(guò)完整數(shù)據(jù)(即添加了潛在變量之后的數(shù)據(jù))的證據(jù)估計(jì)不完整數(shù)據(jù)(原始數(shù)據(jù)D)的證據(jù)的近似方法：P(DIM)-P(DIM)*三(2-14)這里的潛在變量屮通常就是上一節(jié)所提到的期望最大化中的添加數(shù)據(jù)，l(D,屮|0,M)和L(D|0,M)分別表示完整數(shù)據(jù)和不完整數(shù)據(jù)的最大似然估計(jì)值，可以用EM算法得到。3.貝葉斯后驗(yàn)?zāi)Ｐ瓦x擇采用混合模型導(dǎo)致了計(jì)算上的復(fù)雜性同并會(huì)引起較大的計(jì)算誤差，本文嘗試尋找適當(dāng)?shù)母怕誓Ｐ?，以便用解析方法避免這些問(wèn)題貝葉斯后驗(yàn)?zāi)Ｐ途垲愃惴ㄖ械哪Ｐ瓦x擇的核心是對(duì)不同的分類方案Q的后驗(yàn)概率進(jìn)行比較，找出有最大后驗(yàn)概率的分類方案。

16、與通常的化簡(jiǎn)方法不同我們沒(méi)有將最大化后驗(yàn)概率argmaxP(QID)近似Q為最大化似然函數(shù)argmaxP(DIQ)，而是通過(guò)給Q出Q的一個(gè)具體的形式，來(lái)直接得到后驗(yàn)概率P(QID)的形式。為了表示分類方案Q，我們考慮每一篇文章d都有一個(gè)對(duì)應(yīng)的概率矢量屮(d)，屮()=(屮(d),屮(d),，屮(d),L屮(d)=112KkK是預(yù)期的類k=1別數(shù)。這樣與數(shù)據(jù)D對(duì)應(yīng)著個(gè)IDI行K列的矩陣屮，他的每一個(gè)元素屮(d)表示文章d在多大程k度上屬于類別ck，從而屮可以表示任意的分類方案?？梢詫的后驗(yàn)概率表示為:了EM算法陷入局部極大值引起的誤差。P(屮)P(DI屮)jP(屮)P(DI屮)特征序列產(chǎn)生過(guò)程

17、的表示(3-1)我們假設(shè)每篇文章的產(chǎn)生過(guò)程是相互獨(dú)立的，相應(yīng)的每篇文章的類別矢量也是相互獨(dú)立的，貝lPwID)可以表示為：p(qId)xnp(屮(d)p(dI屮(d)(3-2)dgD通常情況下由全概率公式可以給出為了得到P(dIc)的具體形式，我們通過(guò)描k述一個(gè)文檔中特征詞的產(chǎn)生過(guò)程，來(lái)給出一個(gè)合理的文檔特征序列的隨機(jī)發(fā)生模型。按照矢量空間模型(VSM)的觀點(diǎn)，每一篇文章都可以用一個(gè)特征空間中的矢量表示。矢量的每一個(gè)維度表示一個(gè)特征詞，其數(shù)值表示特征詞在文章中出現(xiàn)的次數(shù)。這種表示法忽略了文章的結(jié)構(gòu)性信息，使得聚類完全依賴于文檔中特征P(dI屮(d)=屮(d)p(dIc)，這正是文檔的混合模kk

18、k1型，上式在數(shù)學(xué)上很難處理。幸運(yùn)的是由于我們采用非模糊聚類，聚類算法所考慮的每一個(gè)潛在劃分方案都是將每個(gè)文檔劃入特定的類別中的，也就是說(shuō)中類別矢量屮(d)只能有一個(gè)分量為1，其他的分量都為零：的出現(xiàn)頻率。在VSM中：文檔d的特征矢量表示為d(n,n,n,n,n)，1m0(k)0。實(shí)際上0(k)就表示文檔類c產(chǎn)生特征mmk詞t的概率P(tIc)。mmk文檔類產(chǎn)生文檔中的每個(gè)特征詞是個(gè)相互獨(dú)立的過(guò)程。如果用w表示文檔d中出現(xiàn)的第i個(gè)特征詞，文檔類c產(chǎn)生長(zhǎng)度為N的特征詞序k(3一11)列d的概率可以表示為P(dIc)=兀(NIc)p(d10(k)kk=兀(NIc)flp(w10(k)ki(3-7)

19、0(k)=(其中兀(NJ表示c產(chǎn)生長(zhǎng)度為N的序列kk的概率。我們認(rèn)為文章的長(zhǎng)度與類別無(wú)關(guān)，因”(c,：)1”(ck)”(c,：)2”(ck)M)”(ck)這樣我們可以給出最大后驗(yàn)估計(jì)值：(3一12)而將其視為一常數(shù)。由此可以給出P(d|c)的最k終形式：P(G*D)=flk=1cI(k)IckDflm=1”(ck)(m)”(ck)(3一13)條件期望估計(jì)(3-8)P(dIC)=p(dI0(k)=flp(tI0(k)nmkmm=1=flM(0(k)mm=1這樣基于這一模型，潛在的劃分方案G*的后驗(yàn)概率可以表示為：P(G*|D)=flflIP(屮)flM(0(k)Ikmk=1dgc上m=1丿(3一

20、9)=flp(t)IckIflfl(0(k)”md)kmk=1dgcm=1k式中Ic丨表示類別c中的文檔個(gè)數(shù)。其中隱kk含有約束條件0(k)=1，且10(k)0和mmm=1P(t)=1。kk=1模型參數(shù)的學(xué)習(xí)上式中先驗(yàn)概率P(t)和文檔類的特征詞k分布矢量0(k)都是從文檔全集中獲得的，是未知參數(shù)，需要從樣本數(shù)據(jù)D中進(jìn)行估計(jì)。為了書(shū)寫(xiě)簡(jiǎn)便，我們記參數(shù)b=p(t)，kkb=(b,b,Q)，后驗(yàn)概率改寫(xiě)為：12KP(G*D)=flKbckflflM(0(k)”m(d)(3一10)kmk=1dgcm=1k和混合模型中處理似然函數(shù)的做法相似，此處對(duì)于未知參數(shù)的處理也可以采用兩種不同的策略：采用點(diǎn)估計(jì)，

21、可以采用貝葉斯方法中的最大后驗(yàn)估計(jì)來(lái)學(xué)習(xí)參數(shù)。參數(shù)隨機(jī)化方法，實(shí)際上就是貝葉斯方法中的條件期望估計(jì)。最大后驗(yàn)估計(jì)從b,0,0的意義上看它們之間在文檔全1k集D中沒(méi)有必然的聯(lián)系，我們假設(shè)這K+1組參數(shù)矢量間相互獨(dú)立。這樣可以給出各個(gè)參數(shù)的最大后驗(yàn)估計(jì)：在貝葉斯決策中條件期望估計(jì)是損失函數(shù)為平方損失時(shí)，使損失為最小的估計(jì)方式。由于平方損失是最常用的損失函數(shù)，條件期望估計(jì)在貝葉斯估計(jì)中有特殊的地位9。P(0,G*ID)對(duì)參數(shù)集0的條件期望為：P(G*ID)=fP(0,G*ID)兀(0)d0(3-14)類似最大后驗(yàn)估計(jì)的做法，可以假設(shè)這K+1組參數(shù)矢量間相互獨(dú)立。于是參數(shù)的先驗(yàn)密度函數(shù)有如下的形式：兀

22、(0)=n(b)fln(0(k)(3一15)k=1相應(yīng)的條件期望估計(jì)可以表示為：P(G*D)=fflKkk=1(3一16)flKfflM(0(k)”m(ck)n(0(k)c)d0(k)mkk=1m=1為先驗(yàn)分布n(b)、n(0(k)Ic)選擇適當(dāng)?shù)姆謐布族，可以采用共軛分布法。共軛分布使得參數(shù)的先驗(yàn)與后驗(yàn)屬于相同的類型，使得經(jīng)驗(yàn)知識(shí)與樣本提供的信息信息保持了某種一致性。如果我們用過(guò)去的知識(shí)和現(xiàn)有的樣本提供的信息作為歷史知識(shí)，也就是以這里的后驗(yàn)分布P(0,G*D)n(0)，作為下一步實(shí)驗(yàn)的先驗(yàn)知識(shí)，那么在新的數(shù)據(jù)下，我們得到新的后驗(yàn)分布仍然可以保持相同的類型。我們得到共軛分布為狄利克雷分布。顯然

23、共軛分布使得參數(shù)的后驗(yàn)分布總能夠保持相同的類型。這里我們選擇狄利克雷分步的密度函數(shù)作為先驗(yàn)密度：Kb=1n(b)=邙0)fl其中k=(3-17)flr(卩k)k=卩k=pok=1k=1一r(a(k)時(shí)一l兀(o(k)ic)=0(o(k)a*-1kMmnr(a(k)m二1mm-1(3-18)藝0(k)-1其中m-1m藝a(k)-a(k)m0m-1其中b,a(k)為超參數(shù)。這樣我們得到潛km在分類方案在給定數(shù)據(jù)下后驗(yàn)概率的條件期望估計(jì)如下式。nr(|c|+b)r(B)kk0k-1nKr(B)r(|D|+B0)kk-1nr(n(ck)+a(k)r(a(k)mm0m-1nr(a(k)r(n(ck*+a

24、0k*)mm-14.基于后驗(yàn)?zāi)Ｐ偷膶哟尉垲愃惴?log將層次聚類算法與模型選擇相結(jié)合在許多領(lǐng)域都取得了成功11,12。一方面層次聚類限制搜索范圍，在速度與準(zhǔn)確度之間找到了較好的折衷；另一方面在層次聚類的局部目標(biāo)函數(shù)中使用對(duì)數(shù)似然比(或貝葉斯因子)，消去一些項(xiàng)后，可以大幅度降低后驗(yàn)概率的計(jì)算量。對(duì)于我們的后驗(yàn)?zāi)Ｐ停捎谇懊娼o出了兩種不同的參數(shù)估計(jì)方法，這里將在層次聚類的框架內(nèi)分別對(duì)局部目標(biāo)函數(shù)進(jìn)行優(yōu)化。采用最大后驗(yàn)估計(jì)的層次聚類算法層次聚類中的每一步是基于前一步的選擇進(jìn)行局部?jī)?yōu)化。第k步的分類方案Q和第k+1k步的分類方案Q之間顯然有函數(shù)關(guān)系k+1Q-Q-c,c+coc存在。當(dāng)算法執(zhí)行到k+1k

25、xyxyk+1步時(shí)前一步分類方案為Q-c,c,c，k12|D|-k相應(yīng)的后驗(yàn)概率P(QID)是已經(jīng)確定的常數(shù)，顯k然有：argmaxP(Qk+1Qk+1ID)-argmaxlogQk+1P(QID)k(4-1)化簡(jiǎn)后得到局部目標(biāo)函數(shù)為：(c,c)-xyargmaxIcIlog(IcI)-IcIlog(IcI)-IcIlog(IcI)zzxxyyc,cxy+(n匕)logf匕)-n(cx*logf匕)-n(cy*logf(cy*)mmmmmmm-1(4-2)其中c=cuc，f表示特征詞t在整個(gè)類別中zxymm的出現(xiàn)頻率。為了引用方便，此算法在后面的討論中被稱作MSBP(ModelSelectio

26、nBasedalgorithmwithmaximumPosterior)采用條件期望估計(jì)的層次聚類算法類似前面的做法，局部目標(biāo)函數(shù)為：(3-19)12IDI-k1log+logr(M)IDIk1-r(IcI+1)+log(cm,cn)ir(IcI+1)r(IcI+1)mn(c,c)-argmaxmr(M+n(cm)r(M+n(J)(4-3)r(M+n(cl)+lognr(1+n(ci)j-1r(1+njUr(1+njU其中c-cuc。上式中前兩項(xiàng)對(duì)于聚類過(guò)lmn程每一階段的局部?jī)?yōu)化函數(shù)而言是常數(shù)(因?yàn)閗是常數(shù))，實(shí)際計(jì)算中可以忽略。由于超參數(shù)的選擇對(duì)結(jié)果沒(méi)有顯著的影響，在式中我們選擇了統(tǒng)一的超

27、參數(shù)以簡(jiǎn)化計(jì)算：令aB都為1，相應(yīng)的a-M，ij0B0k+1-IDI-k-1，B0k-IDI-k上式在實(shí)際計(jì)算過(guò)程中需要計(jì)算大量的形如logn!的項(xiàng)。為了提高算法的速度，在計(jì)算較大的n時(shí)(大于1000)，我們采用了stirling近似公式，取對(duì)數(shù)后為：lnn!-丄ln2兀+(n+丄)lnn一n(4-4)22為了引用方便，此算法在后面的討論中被稱作MSBE(ModelSelectionBasedalgorithmwithconditionalExpectation)算法復(fù)雜度分析n個(gè)對(duì)象進(jìn)行層次聚類的平均復(fù)雜度為O(n2),最壞復(fù)雜度為O(n3)?？紤]到特征的因素，在m個(gè)特征詞構(gòu)成的空間中，對(duì)n

28、個(gè)文檔特征矢量進(jìn)行聚類的平均復(fù)雜度為O(n2m)，最壞復(fù)雜度為O(n3m)。兩個(gè)算法有相同的復(fù)雜度，條件期望估計(jì)中每一步的計(jì)算量較大，且涉及更多的對(duì)數(shù)運(yùn)算，在實(shí)際測(cè)試中采用最大后驗(yàn)估計(jì)的算法處理相同的數(shù)據(jù)使用的時(shí)間要少許多。5.試驗(yàn)比較方案設(shè)計(jì)我們選用的測(cè)試數(shù)據(jù)是一組體育方面的文章,六個(gè)類別共計(jì)485篇中文文章,是通過(guò)spider從FM365網(wǎng)站上搜集的。經(jīng)過(guò)切詞處理，去掉停用詞(stopwords)后保留了2719個(gè)特征詞。足球籃球排球乒乓球網(wǎng)球棋牌篇數(shù)12010077416384表5-1衡量傳統(tǒng)信息檢索系統(tǒng)的性能參數(shù)召回率(Recall)和精度(Precision)也是衡量分類算法效果的常

29、用指標(biāo)。然而聚類的過(guò)程中并不存在自動(dòng)分類類別與手工分類類別確定的一一對(duì)應(yīng)關(guān)系，因而無(wú)法像分類一樣直接以精度和召回率作為評(píng)價(jià)標(biāo)準(zhǔn)。為此本文選擇了文獻(xiàn)13中的平均準(zhǔn)確率(AveragedAccuracy,AA)作為評(píng)價(jià)的標(biāo)準(zhǔn)。平均準(zhǔn)確率通過(guò)考察任意兩篇文章之間類屬關(guān)系是否一致來(lái)評(píng)價(jià)聚類的效果。任意兩篇文章之間的關(guān)系，按照手工分類的標(biāo)準(zhǔn)和自動(dòng)聚類的標(biāo)準(zhǔn)可以有以下四種情況：兩篇文檔之間關(guān)系屬于同類類是否自動(dòng)聚類中是AB否CD表5-2平均準(zhǔn)確率定義為積極準(zhǔn)確率(PositiveAccuracy,PA)與消極準(zhǔn)確率(negativeaccuracy,NA)的算術(shù)平均值，即：PA+NAAA二2積極準(zhǔn)確率PA

30、定義為：a(5-1)(5-2)PA二消極準(zhǔn)確率NA定義為：NA一(5-3)b+d結(jié)果分析為了考察算法的效果，我們用K-means，Wardsmethod，著名的混合模型的模型選擇算法AutoClass10，和一種采用非混合模型模型選擇的層次聚類算法HBC(HierarchicalBayesianClustering)13，與本文提出的兩種算法(MSBP,MSBE)共同作了測(cè)試(K-means,Wardsmethod使用SPSSv10.0進(jìn)行的測(cè)試)。使用K-means算法聚類，聚類目標(biāo)為6時(shí)最大的類別包括了446篇文章，準(zhǔn)確率為53.28%。使用Wardsmethod進(jìn)行聚類，準(zhǔn)確率最高為61

31、.41%。AutoClass由于降文檔劃分為了20個(gè)類別，準(zhǔn)確率也不高。所以我們只與HBC算法作進(jìn)一步對(duì)比。下圖顯示了三種算法在聚類過(guò)程中平均準(zhǔn)確的變化過(guò)程。0.9)vcarucQAe身r確準(zhǔn)均平體育類文章聚類準(zhǔn)確率變化(局部)0.80.70.60.5460464468472476480484聚類步驟圖5-1聚類準(zhǔn)確率隨聚類過(guò)程的變化(局部)明顯的HBC、MSBP和MSBE的準(zhǔn)確率依次提高，顯示出了極好的適應(yīng)性。分為六個(gè)類別時(shí)MSBE算法準(zhǔn)確率相對(duì)HBC算法提高了7.6個(gè)百分點(diǎn)，而MSBE算法更有11.9個(gè)百分點(diǎn)的改進(jìn)，這是相當(dāng)令人滿意的結(jié)果。采用條件期望估計(jì)的算法如我們所預(yù)期的那樣比采用最大

32、后驗(yàn)估計(jì)的算法效果更好。對(duì)其他不同數(shù)據(jù)的測(cè)試顯示，樣本集合越小，這一差距越明顯。這也表明了條件期望估計(jì)有較好的穩(wěn)健性。注意到區(qū)間460,475步上，MSBE算法有一段相對(duì)平坦的區(qū)域取得了較高的準(zhǔn)確率，在對(duì)其它數(shù)據(jù)的測(cè)試中也存在類似現(xiàn)象。這一特性意味著算法對(duì)聚類目標(biāo)的分類數(shù)不敏感，在聚類目標(biāo)類別數(shù)難以判斷的情況下，具有很大的實(shí)用價(jià)值。即使應(yīng)用程序選擇的分類數(shù)不太合理，聚類結(jié)果對(duì)應(yīng)用仍具有較好的指導(dǎo)意義。6.結(jié)論在本文介紹的貝葉斯后驗(yàn)?zāi)Ｐ椭?，我們將參與模型選擇的分類方案嚴(yán)格限制在0、1型的分類方案中，即文章要么完全屬于某個(gè)類別，要么不屬于，不存在中間狀態(tài)。更普遍的情況是文章以不同的隸屬度屬于多個(gè)類

33、別，可以按照隸屬度最大的類別進(jìn)行分類。這樣做的問(wèn)題是會(huì)使模型的搜索范圍變?yōu)闊o(wú)限大（采用連續(xù)概率矢量描述隸屬度），成倍增加參數(shù)的數(shù)目，使數(shù)學(xué)處理非常的困難甚至是不可能的。如何在準(zhǔn)確率與數(shù)學(xué)近似和計(jì)算復(fù)雜度之間尋找一個(gè)平衡點(diǎn)，是今后采用模型選擇的聚類算法所面臨的關(guān)鍵問(wèn)題。7.參考文獻(xiàn)H.H.Bock,ProbabilisticModelsinClusterAnalysis,ComputationalStatisticsandDataAnalysis,1996,23,pp.528ChrisFraleyandAdrianE.Raftery,Model-BasedClustering,Discrimin

34、ateAnalysis,andDensityEstimation,TechnicalReportNO.380,DepartmentofStatistics,UniversityofWashington,October2000PetriT.Kontkanen,PetriJ.MyllymakiandHenryR.Tirri,ComparingBayesianModelClassSelectionCriteriabyDiscreteFiniteMixtures,Information,作者簡(jiǎn)介StatisticsandInductioninScience(ProceedingsoftheISIS96ConferenceinMelbourne,Australia,August1996),1996,pp.364374AnIntroductiontoClusterAnalysisforDataMining，from HYPERLINK /classes/Spring-2000/csci5980-d /classes/Spring-2000/csci5980-dm/cluster-survey.pdf5高等數(shù)理統(tǒng)計(jì)，超星圖書(shū)館，pp.442444JeffA.B