魯納納，余旌胡，丁立新，林廣明

（1. 武漢理工大學(xué)，湖北 武漢 430072；2. 武漢大學(xué) 計(jì)算機(jī)學(xué)院, 湖北 武漢 430070；3. 深圳信息職業(yè)技術(shù)學(xué)院 信息技術(shù)研究所，廣東 深圳 518172）

引言

EM算法是處理非完整數(shù)據(jù)未知參數(shù)的一種迭代方法，由Dempster[1]等人提出，用來估計(jì)出非完整數(shù)據(jù)條件下(包括隱含數(shù)據(jù)和缺失數(shù)據(jù)等)的模型參數(shù)值，廣泛應(yīng)用于截尾數(shù)據(jù)、刪失數(shù)據(jù)、成群數(shù)據(jù)等，每次迭代由E步(期望步)和M步(極大步)組成。E步是計(jì)算不完整數(shù)據(jù)的條件期望來填充不完整數(shù)據(jù)，M步是在E步的基礎(chǔ)上求解未知參數(shù)的極大似然估計(jì)。

自Dempster等人提出解決不完整數(shù)據(jù)參數(shù)估計(jì)的EM算法以來，國內(nèi)外有許多研究者對EM算法進(jìn)行了更進(jìn)一步的研究。如Wu和Xu[2-3]總結(jié)出EM算法的一些收斂性質(zhì)。Meng和Rubin[4]提出條件期望最大化方法（ECM）來優(yōu)化M步，使得條件期望的極大化更加簡潔。Liu和Rubin[5]提出了ECM方法擴(kuò)展ECME方法，這種方法對ECM算法中的CM步中對數(shù)似然函數(shù)的極大化條件進(jìn)行了修改，加快了EM算法和ECM算法的收斂，此外，還提出了交替ECM算法；而當(dāng)期望解析表達(dá)式難以得到時(shí)，Wei和Tanner[6]提出了蒙塔卡羅EM算法，改進(jìn)了EM算法中的E步，使得E步更易實(shí)現(xiàn)。但當(dāng)未知數(shù)據(jù)較多時(shí)，收斂速度會變慢。為了提高EM算法的收斂速度，Jamshidian和Jennrich[7]提出了一種基于共軛梯度的加速算法，使用擬牛頓法加速了EM算法。因?yàn)槭褂门ｎD法加速需要在每輪迭代中計(jì)算矩陣的逆，當(dāng)參數(shù)變多時(shí)，其計(jì)算量會變得非常復(fù)雜，計(jì)算結(jié)果也會不穩(wěn)定。而Kuroda等人[8]提出的用ε-加速EM算法在解決二維列聯(lián)表中缺失數(shù)據(jù)時(shí)表現(xiàn)比較優(yōu)異，能在加速EM序列收斂速度的同時(shí)，不影響其穩(wěn)定性、靈活性和簡單性，但是未涉及到初始值的影響以及在有限混合模型下的靈敏度分析。近幾年一些研究者研究了其它加速算法[9-11]并分析了加速算法在高維混合模型中的EM算法的迭代性能。EM算法易受初始值影響，不能保證找到全局最優(yōu)，往往容易陷入局部最優(yōu)，因此關(guān)于初始值設(shè)置提出了許多方法，Zhai[12]選取最遠(yuǎn)點(diǎn)為初始值，易使邊界點(diǎn)收斂效果受到影響；Li和Chen[13]使用k-最近鄰法刪除異常值，然后用K-means來初始化，此估計(jì)效果顯著優(yōu)于原始效果。

關(guān)于EM算法的初始值設(shè)置和收斂速度方面，研究者們已提出許多改進(jìn)的方法，但對有限混合模型參數(shù)求解方法的研究方面，在保留EM算法的各種優(yōu)點(diǎn)的同時(shí)，又能加快收斂速度的方法及其有效性分析的工作并不多。因此，本文首先運(yùn)用k-means方法對原始數(shù)據(jù)進(jìn)行聚類，從而選取合適的初始值；其次運(yùn)用數(shù)值分析中的ε-加速算法對EM算法得到的迭代序列進(jìn)行變換，進(jìn)一步加快其收斂速度(K-means+ε-加速EM算法)。因高斯分布具有靈活、高效擬合的特點(diǎn)，并且很多隨機(jī)現(xiàn)象在足夠大樣本下都可以用此分布來逼近[14]，本文設(shè)計(jì)數(shù)值實(shí)驗(yàn)，比較加速前后EM算法在高斯混合模型參數(shù)估計(jì)中的時(shí)間成本與精度誤差。在靈敏度分析方面，分析在不同條件下加速前后EM算法的參數(shù)估計(jì)效果。

1 EM算法和有限混合模型相關(guān)原理

1.1 EM算法的基本原理與收斂性

反復(fù)進(jìn)行E步和M步，直至收斂。

關(guān)于EM算法的收斂性有如下結(jié)果：

由于

兩邊取對數(shù)得到

令

于是對數(shù)似然函數(shù)可以寫成

從而

要證明

EM算法是一個(gè)一階逐次替代方法并隱性地定義了從參數(shù)空間Θ到Θ的一個(gè)映射()Mθθ→使得

這里λ是*J的最大特征值。從上式可以看出：迭代序列其中c是一個(gè)常數(shù)，且01c＜＜。這里λ對應(yīng)c，因此EM序列線性收斂。

1.2 有限混合模型

case1：兩分量高斯混合模型的一般框架的推導(dǎo)：

（2）混合模型的形式

(,)Y Δ 的聯(lián)合概率函數(shù)為

其中yk對應(yīng)的類別為取值為0 1-。

若將（1）為目標(biāo)函數(shù)，由Jensen不等式知下式成立：

若將（15）為目標(biāo)函數(shù)，由Jensen不等式知：

case2：用類似的方法可以求出三分量高斯混合模型的迭代公式：

1.3 針對有限混合模型的k-means方法

EM算法對初始值十分敏感，如果初始值選取不當(dāng)，不僅可能陷入局部極值，不能得到全局最優(yōu)解，甚至有可能無法正常進(jìn)行迭代。在EM算法初始值選取上，常用的方法是選取幾個(gè)不同的初值進(jìn)行迭代，然后對得到的各個(gè)結(jié)果進(jìn)行比較，從中選取最優(yōu)的估計(jì)值。然而這種方法是任意給定的，不僅會影響算法效率，也有可能仍然找不到全局最優(yōu)解。為了提升效率，考慮在給定初始值之前進(jìn)行聚類，把兩種類型的數(shù)據(jù)分開，再用聚類后的中心賦值給初值。

本文采用K-means進(jìn)行聚類，其相似性度量采用歐氏距離，具體步驟如下：

則

（3）計(jì)算重新分類之后的類心

1.4 EM算法的ε-加速

（1）ε-加速方法

Wynn[16]提出ε-算法來加速收斂緩慢的序列，此算法對于線性收斂的序列非常有效。具體流程為：

一般情況下，上式中 0r=

（當(dāng)i趨于無窮大）。注意，在每一次迭代中，ε-加速算法只需要次運(yùn)算，而Newton-Raphson算法和擬牛頓算法分別需要次運(yùn)算，隨著維數(shù)d變高，計(jì)算成本也會變大。

（2）EM算法的ε-加速算法

ε-加速步：計(jì)算

終止條件

這里δ是預(yù)期精度。注意到ε-加速EM算法并沒有改善E和M步，而是通過ε-加速過程加速EM序列收斂。

為了比較EM算法和ε-加速EM算法的收斂速度，引用以下概念[17]：

Traub[18]證明了因此，ε-EM算法加快了原始的EM序列。

ε-加速EM算法通常用不依賴統(tǒng)計(jì)模型的（31）式。而牛頓加速方法需要對每一個(gè)統(tǒng)計(jì)模型推導(dǎo)出加速公式。因此，ε-加速EM算法相對而言較簡單。但如果初始值再引入K-means聚類的話，ε-加速EM算法和K-means+ε-加速EM算法的時(shí)間成本、誤差精度以及靈敏度的未涉及，因此，本文進(jìn)行更進(jìn)一步的分析。

2 數(shù)值實(shí)驗(yàn)

本文采用兩分量、三分量高斯混合模型為例，對EM算法、ε-加速EM算法以及本文提出的K-means+ε-加速EM算法對混合模型參數(shù)迭代求解效果進(jìn)行分析。同一模型下，算法各運(yùn)行100次，然后求其平均值，通過研究算法迭代次數(shù)c和值估計(jì)值與真實(shí)值的最低匹配位數(shù)m來進(jìn)行時(shí)間成本和精度等多方面影響分析。

2.1 樣本數(shù)量與模型分量大小對迭代效果的影響分析

表1 樣本分量 6000,=4000Tab.1 Sample component 6000,=4000

表1 樣本分量 6000,=4000Tab.1 Sample component 6000,=4000

1 a 1m1σ2a2m2σ真實(shí)值 0.6 3 4■■■■■■5 0 0 0.2■ ■■ ■■ ■0.4 5 3■■■■■■0.1 0 0 0.1■ ■■ ■■ ■初始值0.6637 1.9635 5.0193-■ ■■ ■■ ■0.5320 0.0129 0.0129 0.1871-■■■■■-■0.3363 3.5218 4.1807■ ■■ ■■ ■2.7555 0.4004 0.4004 1.1223-■■■■■-■

表2 加速前后參數(shù)估計(jì)對比表Tab.2 Comparison table of parameter estimation before and after acceleration

表3 迭代次數(shù)和匹配位數(shù)比對表Tab.3 Iteration number and matching digit alignment

首先從表2知，EM算法、ε-加速EM算法以及K-means+ε-加速EM算法均可以收斂到穩(wěn)定點(diǎn)；其次從表3知，EM算法、ε-加速EM算法、K-means+ε-加速EM算法的迭代次數(shù)是遞減的，并且ε-加速EM算法平均迭代次數(shù)為14次，而K-means+ε-加速EM算法僅需要ε-加速EM算法中的4個(gè)點(diǎn)就可以達(dá)到收斂的效果；最后從精度來分析，各種情形下的m值與真實(shí)值的匹配位數(shù)均相同，而ε-加速EM算法需要的迭代次數(shù)是K-means+ε-加速EM算法的3倍左右。

表4 樣本分量600000,=400000Tab.4 Sample component 600000,=400000

表4 樣本分量600000,=400000Tab.4 Sample component 600000,=400000

1 a 1m1σ2a2m2σ真實(shí)值0.6 3 4■■■■■■5 0 0 0.2■ ■■ ■■ ■0.4 5 3■■■■■■0.1 0 0 0.1■ ■■ ■■ ■初始值0.7616 1.7674 5.0236-■ ■■ ■■ ■0.5962 0.0135 0.0135 0.1863-■■■■■-■0.2383 3.5695 4.3256■ ■■ ■■ ■2.7965 0.3014 0.3014 1.2563-■■■■■-■

表5 加速前后參數(shù)估計(jì)對比表Tab.5 Comparison table of parameter estimation before and after acceleration

表6 迭代次數(shù)和匹配位數(shù)比對表Tab. 6 Iteration number and matching digit alignment

表7 三分量高斯混合模型迭代次數(shù)對比表Tab.7 Three-component Gaussian mixture model iteration number comparison

將兩分量增加到三分量之后，ε-加速EM算法以及K-means+ε-加速EM算法仍可以收斂到穩(wěn)定點(diǎn)，但二者平均迭代次數(shù)都有明顯增加，精度也是均有下降。在這種情況下，ε-加速EM算法平均迭代次數(shù)從14次增加到24次， K-means+ε-加速EM算法的平均迭代次數(shù)從5次增加到9次。正如我們前面介紹的，當(dāng)模型未知變量比例較高時(shí)，EM算法的收斂速度會明顯變慢。同時(shí)兩分量增加到三分量后，本文提出的K-means+ε-加速EM算法的效果仍然十分明顯。

2.2 精度設(shè)置對迭代效果的影響分析

表8 加速前后參數(shù)估計(jì)對比表Tab.8 Comparison table of parameter estimation before and after acceleration

表9 迭代次數(shù)對比表Tab.9 Iteration number comparison table

從表9可知，隨著精度增加，ε-加速EM算法和K-means+ε-加速EM算法的估計(jì)值仍然比較接近真實(shí)值，但是ε-加速EM算法估計(jì)值的匹配位數(shù)卻要比K-means+ε-加速EM算法估計(jì)值匹配位數(shù)差了1位。從迭代次數(shù)來看，EM算法的平均迭代次數(shù)從14次增加到了17次；而ε-加速EM算法的平均迭代次數(shù)卻穩(wěn)定在4次左右。精度提升后，EM算法的平均迭代次數(shù)有明顯增加，而ε-加速EM算法的平均迭代次數(shù)仍然變化不大。這說明了隨著收斂精度增加，ε-加速EM算法加速效果越明顯，且迭代結(jié)果更加精確。

2.3 初始值的靈敏度分析

表10 三種方法的迭代效果Tab.10 Iterative effect of three methods

由表10可知，通過K-means算法和EM算法迭代得到的估計(jì)值與真實(shí)值有較大差別，即它們的聚類效果受到了類間重疊的影響。而K+EM算法的迭代效果與真實(shí)值比較接近，說明本文用K-means方法聚類是可行的。

3 總結(jié)

評價(jià)一個(gè)算法的優(yōu)越性通常有簡單性、計(jì)算速度、迭代效率。對于EM算法這類迭代算法，其迭代效率備受關(guān)注，而影響迭代效率的主要因素是初始值的設(shè)置和收斂速度。本文針對EM算法初始值設(shè)置和收斂速度兩個(gè)方面進(jìn)行分析，通過使用K-means聚類方法進(jìn)行初始值的選取，并運(yùn)用ε-加速EM算法進(jìn)行加速(即K-means+ε-加速EM算法)。研究了ε-加速EM算法和K-means+ε-加速EM算法在有限混合分布模型中的應(yīng)用，將為混合模型參數(shù)迭代算法提供改進(jìn)思路并進(jìn)行有效擴(kuò)充，數(shù)值實(shí)驗(yàn)表明，在改變觀測數(shù)據(jù)量大小，收斂精度大小和分模型個(gè)數(shù)的情況下，K-means+ε-加速EM算法均比ε-加速EM算法達(dá)到更好的收斂效果，此外，從迭代次數(shù)和靈敏度兩方面，驗(yàn)證了K-means+ε-加速EM算法是可行的。