趙晨陽，翟少丹，佀潔

1.西北大學(xué)數(shù)學(xué)系，西安 710127

2.西北大學(xué)信息與技術(shù)學(xué)院，西安 710027

基于最大后驗估計的無監(jiān)督聚類算法

趙晨陽1，翟少丹1，佀潔2

1.西北大學(xué)數(shù)學(xué)系，西安 710127

2.西北大學(xué)信息與技術(shù)學(xué)院，西安 710027

混合模型為密度估計和聚類提供了一個嚴(yán)密的框架，基于有限混合模型的聚類方法受到了越來越多的重視和關(guān)注。有限混合模型為一大類隨機(jī)現(xiàn)象建立統(tǒng)計模型提供了一個基于數(shù)學(xué)的方法，并可以廣泛應(yīng)用于監(jiān)督的和無監(jiān)督的聚類算法中[1]。但是，在基于混合模型的聚類過程中仍然存在多方面的問題，例如：如何去估計混合模型的參數(shù)；當(dāng)多元高斯分布的斜方差矩陣是正定時，EM算法的迭代過程雖然可以保證似然函數(shù)良好的單調(diào)性，但是并不能保證該矩陣的正定性。

Figueiredo和Jain提出了一種基于MML準(zhǔn)則的無監(jiān)督的EM算法（MML-EM）[2]，很好地解決了EM算法的局部收斂以及確定分類個數(shù)的問題。但是，MML-EM算法在估計方差矩陣時會出現(xiàn)奇異，從而導(dǎo)致最大似然估計失敗。

提出一種新的基于最大后驗估計的聚類算法，在EM算法中將MLE替換為MAP估計，并用一種改進(jìn)的BIC準(zhǔn)則（MBIC）作為模型評價的標(biāo)準(zhǔn)[3]，且將此MBIC與模型參數(shù)估計同時處理，從而集成了MML-EM算法中的優(yōu)勢。數(shù)值實驗表明，MAP-EM算法能很好地避免奇異情況的發(fā)生，同時可以防止模型選擇出現(xiàn)失敗。

1 混合模型聚類算法基本原理

基于有限混合模型聚類的原理是采用若干個概率分布的混合模型去擬合數(shù)據(jù)，其中每一分布描述一個類的特點，從而實現(xiàn)聚類[4]。相比于其他聚類算法，基于模型的聚類算法能夠更靈活地在多種概率模型中選擇合適的模型。

在基于模型的聚類中，數(shù)據(jù)x=(x1，x2，…，xn)被看做來自一個混合分布，則混合分布的密度函數(shù)可以表示為：

EM算法[5-6]是求參數(shù)極大似然估計的一種重要算法。文獻(xiàn)[7]詳細(xì)討論了如何運(yùn)用EM算法估計高斯混合模型的參數(shù)，在這里僅給出參數(shù)的更新公式：

利用上式就可以實現(xiàn)EM算法，得到Θ的極大似然估計。

2 一種新的基于MAP估計的聚類算法

提出用MAP估計代替MML估計，很好地避免了協(xié)方差矩陣陷入奇異，并且增大了模型選擇的成功率。用MBIC作為模型評價的標(biāo)準(zhǔn)，將模型評價與模型參數(shù)估計同時處理，從而增加了模型選擇成功的概率。同時選取一個大于模型真實類數(shù)的作為初始分類數(shù)目，降低了EM算法對初始值的敏感度[8]。

2.1 MAP-EM算法參數(shù)選取

樣本數(shù)據(jù)Y=(y1，y2，…，yn)的Bayesian密度函數(shù)表示為：

其中，L是混合似然函數(shù)，P是參數(shù)αk、μk、Σk及θ的先驗概率。

2.1.1 參數(shù)μ、Σ的選取

文獻(xiàn)[9-10]討論了先驗分布的選取問題。經(jīng)驗貝葉斯的方法[11]建議μ、Σ應(yīng)服從的先驗分布，分別為正態(tài)分布和負(fù)威沙特分布。

假設(shè)μ0、k0、ν0和Λ0對于每一分支是相同的，因此對于一個多元高斯混合模型，其正態(tài)-負(fù)威沙特先驗分布為：

根據(jù)先驗分布可得到后驗均值和后驗方差（推導(dǎo)過程見文獻(xiàn)[3]）。

2.1.2 參數(shù)αk的選取

αk的先驗分布通常選為Dirichlet分布，即

2.2 MAP-EM算法分支刪除策略

將分支個數(shù)起始于一個大于模型真實的類數(shù)mmax，在迭代的過程中，一些分支的混合比率αk會收縮至0，采取的處理方式是將其刪除。這種競爭的方法能夠有效避免EM算法收斂于參數(shù)空間邊界的問題[2，12]。

在EM算法的M步直接應(yīng)用公式可能會導(dǎo)致算法失敗：當(dāng)mmax非常大時，將會發(fā)生所有分支都會被刪除的情形。為了避免這一問題，MAP-EM算法采用一種Componentwise EM（CEM）方法：如果一個分支收縮到0，那么立即重新分配它的概率質(zhì)量給其他的分支，以增加其他分支幸存的機(jī)會。

2.3 MAP-EM算法參數(shù)的初始化

由于選擇了一個大于模型真實類數(shù)的mmax作為初始分類數(shù)目，有效地降低了基本EM算法對初始值的依賴程度。具體如下：

（1）選擇一個大于模型真實類數(shù)的mmax作為初始分類數(shù)目。

（2）在數(shù)據(jù)集中隨機(jī)抽取mmax個點作為聚類中心。

2.4 MAP-EM算法流程

（1）令模型分支數(shù)m=mmax，并指定一最小分支數(shù)mmin；給定一個判斷EM算法是否收斂的閥值。按照2.3節(jié)方法，分別初始化混合比率α0、均值μ0和協(xié)方差矩陣Σ0。

（2）令i=1，根據(jù)文獻(xiàn)[2]中的方法計算MBICi的值。令k=1。

（4）若k≤m，轉(zhuǎn)到（3）；否則，令i=i+1，重新計算MBICi的值。

（5）若滿足EM算法的收斂條件，更新max(MBICi)所對應(yīng)的參數(shù)為最優(yōu)參數(shù)；否則，令k=1，轉(zhuǎn)到（3）。

（6）若m到達(dá)mmin，輸出最優(yōu)解；否則，刪除最小αk所對用的分支，重新分配其概率質(zhì)量給其他分支。并令i=i+1，計算MBICi的值，轉(zhuǎn)到（3）。

2.5 MAP-EM算法時間復(fù)雜度

MAP-EM算法將模型選擇與參數(shù)估計同時進(jìn)行，因此它的時間復(fù)雜度由兩個部分決定。

MAP-EM算法采用MBIC準(zhǔn)則進(jìn)行模型選擇，所以其時間復(fù)雜度為O(d2)，其中kmax為最大分類數(shù)，d為分支數(shù)。參數(shù)估計由改進(jìn)的EM算法完成，則復(fù)雜度為O(MNE)，其中M為混合分布的分支數(shù)，N為樣本數(shù)，E為EM算法迭代次數(shù)。因此，MAP-EM算法的時間復(fù)雜度為O(Md2NE)。

3 實驗性能及對比分析

實驗采用兩組不同類型的測試數(shù)據(jù)集，一組是按照文獻(xiàn)[2]中根據(jù)給定參數(shù)生成1 000個隨機(jī)數(shù)據(jù)，另一組數(shù)據(jù)是來從UCI機(jī)器學(xué)習(xí)庫中的Iris和Zoo兩個基準(zhǔn)數(shù)據(jù)集。表1中給出了數(shù)據(jù)集和它們的一些簡單特征。文中的數(shù)值實驗均在R語言（www.r-project.org）2.6.1環(huán)境下實現(xiàn)。

表1 實驗數(shù)據(jù)集說明

3.1 實驗1

圖1所示的是文獻(xiàn)[2]中數(shù)據(jù)集（Data1）的聚類結(jié)果，圖（a）為MAP-EM算法對數(shù)據(jù)集中1 000個隨機(jī)數(shù)據(jù)聚類的結(jié)果，圖（b）是MML-EM算法的聚類結(jié)果。實驗結(jié)果表明MAP-EM算法和MML-EM算法都能選擇出最優(yōu)的模型，并且得到較好的聚類效果，同時具有很好的魯棒性。

圖1 兩種聚類算法比較

3.2 實驗2

圖2所示的是文獻(xiàn)[2]中的第二個數(shù)據(jù)集（Data2）的損失函數(shù)變化。Data2是一種分支間相互重疊的數(shù)據(jù)，而在重疊度較大時，MML-EM算法會因為協(xié)方差陣趨于奇異，無法保證算法能夠正確收斂[13]，從而導(dǎo)致算法失?。▓D2）。

圖2 Data2 BIC變化

對于數(shù)據(jù)集2，MAP-EM算法首先假設(shè)參數(shù)服從一個先驗分布，因此即使每個組成函數(shù)不接近任何樣本，它們都會有一個小的概率值[13]，這樣就防止了方差和概率值的估計失敗。這種方法不但能夠防止方差陣陷入奇異，還能夠選擇出最優(yōu)的模型（圖3（a））。在數(shù)據(jù)集有嚴(yán)重重疊的情況下，MAP-EM通過刪除后驗概率最小的分支避免了參數(shù)收斂于參數(shù)空間的邊界。同時將模型選擇與模型的參數(shù)估計同時處理，在一定程度上擴(kuò)大了對M的搜索范圍。使得MAP-EM算法在避免協(xié)方差矩陣趨于奇異而導(dǎo)致EM算法的失敗的同時，能夠達(dá)到良好的聚類效果（圖3（b））。

圖3 基于MAP-EM算法聚類結(jié)果

3.3 實驗3

對UCI數(shù)據(jù)集Iris和Zoo，分別采用MML-EM和MAP-EM進(jìn)行測試的結(jié)果見表2。從表中的實驗結(jié)果可以看出，在聚類的質(zhì)量上MAP-EM算法效果明顯優(yōu)于MML-EM算法。雖然Zoo數(shù)據(jù)集中的數(shù)據(jù)具有嚴(yán)重的重疊區(qū)域，但是MAP-EM算法依然具有良好的聚類效果。

表2 MML-EM算法與MAP-EM算法比較

4 小結(jié)

針對EM算法的一些缺陷，提出在算法流程，先驗分布的選取，模型選擇等方面的一系列改進(jìn)。首先，MAP-EM算法基于最大后驗估計，可以有效地避免聚類過程中協(xié)方差矩陣陷入奇異的狀況。其次，采用一種競爭的機(jī)制，使得在參數(shù)估計的同時淘汰后驗概率最小的分支。另外，將參數(shù)估計與模型選擇相結(jié)合，有效地擴(kuò)大了模型選擇的范圍。大量數(shù)值實驗證明，改進(jìn)后的算法具有良好的聚類效果。

由于MAP-EM算法采取淘汰后驗概率最小分支的策略，當(dāng)數(shù)據(jù)在參數(shù)空間中分布不均勻，同時有過于密集區(qū)域和稀疏區(qū)域時，一些較為稀疏的區(qū)域可能會因為后驗概率過小而被刪除，使得算法陷入局部最優(yōu)。如何在此類情況下找到一個全局最優(yōu)解，也是下一步需要研究的問題。

[1]Constantinopoulos C，Likas A.Unsupervised learning of Gaussian mixturesbasedonvariationalcomponentsplitting[J].IEEE Transactions on Neural Networks，2007，18（3）：745-755.

[2]Figueiredo M，Jain A K.Unsupervised learning of the mixture models[J].IEEETransonPattern AnalysisandMachine Intelligence，2002，24（3）：381-396.

[3]Fraley C，Raftery A.Bayesian regularization for normal mixture estimation and model-based clustering[J].Journal of Classification，2007，24：155-181.

[4]Ketchantany W，Derrde S，Martin L，et al.Pearson-based mixture model for color object tracking[J].Machine Vision and Applications，2008，19（5/6）：457-466.

[5]Dempster A P，Laird N M，Rubin D B.Maximum-likelihood from incomplete data via the EM algorithem[J].J R Statist Soc，1997，39：1-38.

[6]茆詩松，王靜龍，濮曉龍.高等數(shù)理統(tǒng)計[M].北京：高等教育出版社，1998：427-440.

[7]Bilmes J A.A gentle tutorial of the EM algorithm and its applicationtoparameterestimationforGaussianmixtureand hidden Markov models[R]，ICSI Technical Report，1997：97-021.

[8]Ruan Lingyan，Yuan Ming，Zou Hui.Regularized parameter estimation in high-dimensional Gaussian mixture models[J]. Neural Conputation，2011，23（6）：1605-1622.

[9]Tadjudin S，Landgrebe D.Covaraince estimation for limited training samples[J].Geoscience and Remote Sensing Symposium，1998，37（4）：123-128.

[10]Friedman J F.Regularized discriminant analysis[J].Statist Soc，1989，84：17-42.

[11]Rayens W，Greene T.Covariance pooling and stabilization for classification[J].Computational Statistics and Data Analysis，1991，11：17-42.

[12]Figueiredo M，Jain A K.Unsupervised selection and estimation of finite mixture models[J].Pattern Recognition，2000，36：87-90.

[13]Ma Jinwen，Xu Lei，Jordan M.Asymptotic convergence rate of the EM algorithm for Gaussian mixtures[J].Neural Computation，2000，12：2881-2907.

ZHAO Chenyang1,ZHAI Shaodan1,SI Jie2

1.Department of Mathematics,Northwest University,Xi’an 710127,China
2.School of Information and Technology,Northwest University,Xi’an 710027,China

When EM method is used to estimate the maximum likelihood of models,the method will fail because of the covariance matrix become singularity matrix.This paper replaces the Maximum Likelihood Estimation（MLE）by a Maximum a Posteriori（MAP）estimator.By using the improved BIC criterion and the model parameter estimation at the same time,it can enlarge the area of model selection.The algorithm is effective to avoid singularity in the iterations,and uses the improved BIC criterion and the model parameter estimation at the same time.Finally,the R simulation results show that the proposed algorithm decreases the calculation,and improves the accuracy of the cluster,it also has strong robustness.

mixture model;EM algorithm;Maximum a Posteriori（MAP）;model selection;clustering

傳統(tǒng)的基于EM算法的聚類方法，當(dāng)模型的某個高斯分量的協(xié)方差矩陣變?yōu)槠娈惥仃嚂r，會導(dǎo)致聚類失敗。提出在聚類過程中用最大后驗估計（MAP）來代替極大似然估計（MLE）；將一種改進(jìn)的貝葉斯信息準(zhǔn)則（BIC）與模型參數(shù)估計同時處理，擴(kuò)大了模型選擇的搜索范圍。該算法有效地避免了協(xié)方差矩陣在迭代中陷入奇異，并將參數(shù)估計和模型選擇同時進(jìn)行。通過R軟件進(jìn)行仿真分析，結(jié)過表明改進(jìn)的算法在減少計算量同時，提高了聚類的準(zhǔn)確度，并具有魯棒性。

混合模型；EM算法；最大后驗估計（MAP）；模型選擇；聚類

A

TP311

10.3778/j.issn.1002-8331.1201-0190

ZHAO Chenyang,ZHAI Shaodan,SI Jie.Unsupervised clustering algorithm based on Maximum a Posteriori.Computer Engineering and Applications,2013,49（19）：131-134.

國家自然科學(xué)基金（No.10771169）。

趙晨陽（1984—），女，博士研究生，主要研究方向為數(shù)據(jù)挖掘；翟少丹（1984—），男，碩士研究生，主要研究方向為人工智能。E-mail：starstaryang@163.com

2012-01-18

2012-04-26

1002-8331（2013）19-0131-04

CNKI出版日期：2012-07-03http://www.cnki.net/kcms/detail/11.2127.TP.20120703.1628.039.html