胡慶輝　阮曉霞

1　桂林航天工業(yè)學(xué)院　計算機科學(xué)與工程系，廣西　桂林　541004；2　桂林航天工業(yè)學(xué)院　外語外貿(mào)系，廣西　桂林　541004

基于MCD初始化的高斯混合模型聚類*

胡慶輝1阮曉霞2

1桂林航天工業(yè)學(xué)院計算機科學(xué)與工程系，廣西桂林541004；2桂林航天工業(yè)學(xué)院外語外貿(mào)系，廣西桂林541004

摘要高斯混合模型聚類是一種基于概率模型的有效聚類方法，傳統(tǒng)算法對模型的初始化(包含成分?jǐn)?shù)、每個成分的均值和方差)的設(shè)置非常敏感，容易導(dǎo)致EM算法陷入局部最優(yōu)解或收斂到解空間的邊界，為了解決這個問題，可利用最小化協(xié)方差矩陣行列式(MCD), 結(jié)合傳統(tǒng)成熟的高斯混合模型算法，來實現(xiàn)對高斯混合模型的初始化，而MCD初始化的算法對初始值的設(shè)定沒有特殊的要求，通過實驗證明其具有很好的聚類性能和魯棒性。

關(guān)鍵詞高斯混合模型；聚類；最小協(xié)方差矩陣行列式；EM算法

有限概率混合模型是進行聚類和密度估計的一種非常有效的數(shù)學(xué)方法之一。它通過利用有限個獨立概率模型的線性凸組合，來刻畫一個復(fù)雜的數(shù)據(jù)分布。相對于單個模型，混合模型有更強的可解釋性和表達能力。目前，有限混合模型已經(jīng)得到了廣泛的應(yīng)用，如語音識別[1]、醫(yī)學(xué)研究[2]、圖像中的人臉膚色區(qū)域檢測等。

在選擇有限概率混合模型進行數(shù)據(jù)分析時，需要假設(shè)數(shù)據(jù)服從某種概率分布。根據(jù)中心極限定理，對于大量相互獨立的隨機變量，其均值分布以正態(tài)分布為極限，即大量隨機變量之和近似服從高斯正態(tài)分布，因此概率混合模型通常假定數(shù)據(jù)服從混合高斯分布[1-4]，即高斯混合模型。在該假定條件下，模型中的每個成分都服從各自的高斯分布。但是高斯混合模型對噪聲非常敏感，對于含有大量噪聲的數(shù)據(jù)，高斯混合模型通常達不到理想的建模效果，這時可以選擇具有重尾的t分布[5-6]來代替高斯分布。另外，針對不同的實際應(yīng)用，還可以選擇皮爾遜分布[7]、Dirichlet分布[8-9]等。

聚類任務(wù)中所使用的觀測數(shù)據(jù)是不完整的，期望最大化的EM算法可以通過迭代使用觀測到的數(shù)據(jù)量來估計不可觀測的數(shù)據(jù)量。 因此，在利用有限混合模型進行聚類時，通常采用EM算法求解未知標(biāo)記的最大似然值，EM算法的優(yōu)點是簡單穩(wěn)定，但是收斂過程比較緩慢，并且通常使參數(shù)陷入局部最優(yōu)值。對于有限概率混合模型來說，模型中各成分的初始化參數(shù)如果設(shè)置不當(dāng)，則很容易使算法收斂到一個比較差的局部最優(yōu)解。因此如何設(shè)置混合模型的參數(shù)對算法的性能是非常重要的。為此，在文獻[10]中，作者有針對性地討論了EM算法的初始化方法，文獻[11-12]中，作者針對混合模型的成分估計進行了研究。針對算法的魯棒性問題，文獻[4]中作者提出了一個最小信息長度(MML) 收斂準(zhǔn)則,一定程度上提高了EM算法的魯棒性，但是該算法仍然可能會因為初始成分的設(shè)置不同而收斂到不同的次優(yōu)解。文獻[3]中，作者設(shè)置了成分?jǐn)?shù)初值直接等于觀測值個數(shù)，通過對成分的混合系數(shù)施加熵懲罰因子，在迭代中根據(jù)一定準(zhǔn)則快速自動減少成分?jǐn)?shù)目，大量實驗證明該算法具有很好的魯棒性。但是該算法只適合于觀測值較少的情況，隨著觀測值數(shù)量的增大，該算法的效率會因為初始成分?jǐn)?shù)太大而大大降低。因此，使算法在較少迭代次數(shù)內(nèi)快速降低成分?jǐn)?shù)目是一個有效提高該算法效率的辦法。

本文針對文獻[3]的算法，提出了利用最小化協(xié)方差矩陣行列式(Minimum Covariance Determinant Estimator ，MCD)進行該算法的成分初始化及相應(yīng)的參數(shù)設(shè)置，MCD是一個魯棒的多變量散布估計算法[13]，對于給定的數(shù)據(jù)集，MCD的目標(biāo)是尋找該數(shù)據(jù)集一個子集，使得子集的協(xié)方差矩陣的行列式最小。我們通過迭代調(diào)用MCD來獲取混合模型的成分?jǐn)?shù)和每個成分的參數(shù)值。由于通過MCD初始化大大減少了文獻[3]的初始成分?jǐn)?shù)，使得算法的執(zhí)行速度有很大提高，同時通過實驗表明，用MCD初始化的算法仍然具有很好的魯棒性，算法的精度也沒有降低。

1高斯混合模型及優(yōu)化算法

混合模型的密度函數(shù)可表示為c個概率密度函數(shù)(也叫做成分)的線性組合形式：

(1)

(2)

其中μi和Σi分別為第i個成分的均值向量和協(xié)方差，δ(x,μ;Σ)表示x與μ的Mahalanobis距離。

L(ω,μ,Σ;x1,x2,...xn)

(3)

在公式(3)中，針對未知參數(shù)zki，可以使用EM算法進行求解。該算法分為以下兩步：

E-Step：求解參數(shù)zki：

(4)

M-Step：對(3)式的μk、Σk和ωk求最大，有：

(5)

(6)

(7)

(8)

求解公式(8)，得到ωk第t+1次迭代的更新公式為：

(9)

(10)

(11)

2基于MCD高斯混合模型優(yōu)化算法

2.1最小化協(xié)方差矩陣行列式(MCD)

MCD是一個魯棒的多變量散布估計算法[13]，對于給定的數(shù)據(jù)集χ，MCD的目標(biāo)是尋找一個子集ε?χ，使得ε的協(xié)方差矩陣的行列式最小。然后可以用ε的協(xié)方差矩陣作為χ的協(xié)方差矩陣。MCD具有仿射同變性質(zhì)，即使在有外樣本干擾的情況下，也能夠獲得比M估計和S估計更好的估計值。其基本原理的數(shù)學(xué)描述如下：

設(shè)輸入的d維樣本集為χ={x1,x2,...xn|x∈Rd}，選擇h

(12)

(13)

(14)

MCD是NP問題，在文獻[14]中，作者提出了改進的Fast-MCD算法,大大改進了算法的執(zhí)行效率，使得MCD方法能夠應(yīng)用在各種穩(wěn)健估計中。

2.2利用MCD初始化高斯混合模型

算法1:初始化高斯混合模型的參數(shù)輸入:數(shù)據(jù)集χ={x1,x2,…,xn|x∈Rd},初始樣本子集大小h?N;輸出:成分?jǐn)?shù)ck,每個成分的參數(shù)θk(包含了均值μk和協(xié)方差Σk)1.初始化k=1,χk=χ;2.WHILE |χk|

新生成的子集可以與已生成的子集產(chǎn)生交叉，但是不能包含原有的子集，否則新的子集大小h折半，然后重新生成子集，直到所有的樣本都有屬于特定的子集為止。minNum為每個子集的最少樣本數(shù)，當(dāng)|χk|小于minNum時，不需要再產(chǎn)生新的成分，而是直接將剩余的|χk|個樣本分別分配到距離該樣本最近的成分中。

2.3基于MCD高斯混合模型算法

針對文獻[3]，基于MCD初始化算法的基本步驟如下：

算法2:基于MCD初始化的高斯混合模型算法輸入:數(shù)據(jù)集χ={x1,x2,…,xn|x∈Rd},初始樣本子集大小h?N;輸出:概率密度函數(shù)f(x;ω,θ);1.初始化,需要做一下工作:(1)懲罰系數(shù)β=1;(2)利用算法1初始化成分個數(shù)c及每個成分的協(xié)方差矩陣Σk和均值向量μk;(2)初始化zki;2.REPEAT 利用公式(9)計算混合系數(shù)ωk,如果ωk<1/n,則刪除成分k,同時執(zhí)行(10),(11); 利用(7)計算協(xié)方差矩陣Σk; 利用(4)計算zki; 利用(6)計算均值向量μk;UNTIL max1

3實驗分析

本文針對3個算法進行了實驗比較，分別來自文獻[3]的CA1、文獻[4]中的CA2以及本文的算法CA3，對于本文中的算法，利用MCD進行成分初始化時，設(shè)置h為樣本數(shù)的1/10，minNum=10，即每個初始成分的樣本數(shù)不少于10個。實驗環(huán)境為Windows 8 64位操作系統(tǒng)，Intel(R) Core(TM)i5 2.80 GHz，16 GB內(nèi)存，仿真軟件為Matlab7.10.0.499。 實驗分別在多個人工數(shù)據(jù)集和真實數(shù)據(jù)集上完成。

3.1 人工數(shù)據(jù)集的比較結(jié)果

圖1　兩個人工數(shù)據(jù)集的數(shù)據(jù)分布

每種算法執(zhí)行20次，每次隨機生成測試樣本，最后得到在兩個人工數(shù)據(jù)集上的比較數(shù)據(jù)如表1所示：

表1　人工數(shù)據(jù)集的比較結(jié)果

3.2真實數(shù)據(jù)集上的比較結(jié)果

本組實驗采用的真實數(shù)據(jù)集是來自文獻[15]的跳蚤甲蟲數(shù)據(jù)，數(shù)據(jù)集大小為74，包含了3個物種，分別是concinna(Con)、heikertingeri(Hei)及hetapotamica(Hep)； 每個樣本包含了2個特征值，分別是陽莖前端的最大寬度和前端夾角(其中1單位=7.5°)。采用3種算法進行聚類，隨機執(zhí)行20次后，平均結(jié)果的比較數(shù)據(jù)如表2所示。

表2　真實數(shù)據(jù)集的比較結(jié)果

由表1和表2可以看出，CA2算法的聚類性能相對比較差，且通常會花費較多的迭代次數(shù)和時間，本文算法CA3經(jīng)過MCD成分初始化后，EM算法的迭代次數(shù)及所耗費的時間都比文獻[1]中的CA1算法有大幅度降低，這是因為CA2的初始成分?jǐn)?shù)通常不會超過40，CA1的初始成分?jǐn)?shù)是樣本個數(shù)，遠遠超過了CA2的初始成分?jǐn)?shù)，而算法每次迭代所耗費的時間與成分?jǐn)?shù)呈指數(shù)增長關(guān)系，因此通過MCD方法降低初始成分?jǐn)?shù)后，可以大大加快算法的執(zhí)行速度，而在分類結(jié)果方面，CA3相對于CA1并沒有明顯的變化。這表明本文提出的經(jīng)過MCD初始化的高斯混合模型聚類算法不僅具有很好的魯棒性，同時還具有較快的收斂速度。

4結(jié)束語

本文針對文獻[3]中提出的混合模型聚類算法，提出了一種利用最小協(xié)方差行列式(MCD)進行成分初始化的方法，MCD是一個魯棒的多變量散布估計算法，能夠很好地應(yīng)用于多變量散布估計，通過迭代調(diào)用MCD來獲取混合模型的成分?jǐn)?shù)和每個成分的參數(shù)值，這些成分能夠很好地反映數(shù)據(jù)的分布情況。由于通過MCD初始化大大減少了文獻[3]的初始成分?jǐn)?shù)，使得算法的執(zhí)行速度有很大提高，同時通過實驗表明，用MCD初始化的算法仍然具有很好的魯棒性，算法的精度也沒有降低。

參考文獻

[1]Reynolds DA, Rose RC. Robust text-independent speaker identification using Gaussian mixture speaker models[J]. IEEE Transactions on Speech and Audio Processing, 1995,3(1):72-83.

[2]Ferreira da Silva AR. A Dirichlet process mixture model for brain MRI tissue classification[J]. Medical image analysis, 2007,11(2):169-182.

[3]Yang M S, Lai C Y,Lin C Y. A robust EM clustering algorithm for Gaussian mixture models[J]. Pattern Recognition, 2012,45(11): 3950-3961.

[4]M A T Figueiredo, A K Jain. Unsupervised learning of finite Mixture models[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002(24):381-396.

[5]Jeffrey L Andrews, Paul D McNicholas. Model-based classification via mixtures of multivariate t-distributions[J]. Computational Statistics and Data Analysis, 2010(6): 520-529.

[6]Peel D, McLachlan G J. Robust Mixture Modeling using the t Distribution[J]. Statistics and Computing, 2000(10): 339-348.

[7]Jianyong Sun, Jonathan M. Garibaldi. Robust mixture clustering using Pearson type VII distribution[J].Pattern Recognition Letters, 2010(7):1-8.

[8]Bouguila N,Ziou D,Vaillancourt J. Unsupervised learning of a finite mixture model based on the Dirichlet distribution and its application[J]. IEEE Transactions on Image Processing, 2004 (11): 1533-1543.

[9]Bouguila N，ElGuebaly W. Discrete data clustering using finite mixture models[J]. Pattern Recognition, 2009(1): 33-42．

[10]C Biernacki,G Celeux,G Govaert. Choosing starting values for the EM algorithm for getting the highest likelihood inmultivariate Gaussian mixture models[J]. Computational Statistic&Data Analysis, 2003(41): 561-575.

[11] K Reddy, H D Chiang, B Rajaratnam. TRUST-TECH-based expectation maximization for learning finite mixture models[J]. IEEE Transactionson Pattern Analysis and Machine Intelligence,2008(30):1146-1157.

[12] Richardson, P J Green. On Bayesian analysis of mixtures with an unknown number of components[J]. Journal of the Royal Statistical Society-SeriesB,1997(30): 731-758.

[13] P Rousseeuw, A Leroy. Robust Regression and Outlier Detection[M].JohnWiley&Sons Inc,1987.

[14] Peter J Rousseeuw, Katrien Van Driessen. A Fast Algorithm for the Minimum Covariance Determinant Estimator[J]. Technometrics, 1999,41(3):212-22.

[15]A A Lubischew. On the use of discriminant functions in taxonomy[J]. Biometrics, 1962,18: 455-477.

(責(zé)任編輯陳葵晞)

* 基金項目:廣西高?？蒲兄攸c項目《基于多核學(xué)習(xí)的半監(jiān)督支持向量機相關(guān)技術(shù)研究》(ZD2014147); 桂林航天工業(yè)學(xué)院科研項目《監(jiān)督機器學(xué)習(xí)中的數(shù)據(jù)降維方法研究》(Y12Z028)。

作者簡介：胡慶輝,男,重慶開縣人。 副教授, 博士。 研究方向: 機器學(xué)習(xí)，智能計算。

中圖分類號：TP301.6

文獻標(biāo)志碼：A

文章編號：2095-4859(2016)01-0001-06