基于最大后驗估計的無監督聚類算法

趙晨陽，翟少丹，佀潔

1.西北大學數學系，西安 710127

2.西北大學信息與技術學院，西安 710027

基于最大后驗估計的無監督聚類算法

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

1.西北大學數學系，西安 710127

2.西北大學信息與技術學院，西安 710027

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

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

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

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

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

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

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

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

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

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

2.1 MAP-EM算法參數選取

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

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

2.1.1 參數μ、Σ的選取

文獻[9-10]討論了先驗分布的選取問題。經驗貝葉斯的方法[11]建議μ、Σ應服從的先驗分布，分別為正態分布和負威沙特分布。

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

根據先驗分布可得到后驗均值和后驗方差（推導過程見文獻[3]）。

2.1.2 參數αk的選取

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

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

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

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

2.3 MAP-EM算法參數的初始化

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

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

（2）在數據集中隨機抽取mmax個點作為聚類中心。

2.4 MAP-EM算法流程

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

（2）令i=1，根據文獻[2]中的方法計算MBICi的值。令k=1。

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

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

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

2.5 MAP-EM算法時間復雜度

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

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

3 實驗性能及對比分析

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

表1 實驗數據集說明

3.1 實驗1

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

圖1 兩種聚類算法比較

3.2 實驗2

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

圖2 Data2 BIC變化

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

圖3 基于MAP-EM算法聚類結果

3.3 實驗3

對UCI數據集Iris和Zoo，分別采用MML-EM和MAP-EM進行測試的結果見表2。從表中的實驗結果可以看出，在聚類的質量上MAP-EM算法效果明顯優于MML-EM算法。雖然Zoo數據集中的數據具有嚴重的重疊區域，但是MAP-EM算法依然具有良好的聚類效果。

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

4 小結

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

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

[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]茆詩松，王靜龍，濮曉龍.高等數理統計[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

傳統的基于EM算法的聚類方法，當模型的某個高斯分量的協方差矩陣變為奇異矩陣時，會導致聚類失敗。提出在聚類過程中用最大后驗估計（MAP）來代替極大似然估計（MLE）；將一種改進的貝葉斯信息準則（BIC）與模型參數估計同時處理，擴大了模型選擇的搜索范圍。該算法有效地避免了協方差矩陣在迭代中陷入奇異，并將參數估計和模型選擇同時進行。通過R軟件進行仿真分析，結過表明改進的算法在減少計算量同時，提高了聚類的準確度，并具有魯棒性。

混合模型；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.

國家自然科學基金（No.10771169）。

趙晨陽（1984—），女，博士研究生，主要研究方向為數據挖掘；翟少丹（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