劉 銘, 于子奇

(長春工業(yè)大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 長春 130012)

期望最大化(expectation-maximum, EM)算法[1]是一種通過迭代進(jìn)行極大似然估計(jì)的優(yōu)化算法, 廣泛應(yīng)用于對含有隱變量的概率密度模型(如混合高斯模型)的參數(shù)估計(jì)中. EM算法作為一個(gè)基于梯度上升的優(yōu)化算法, 在對模型參數(shù)進(jìn)行迭代優(yōu)化的過程中, 其似然函數(shù)值一般情況下是遞增的. 但EM算法在優(yōu)化過程中具有收斂速度較慢、 魯棒性差、 易陷入局部最優(yōu)等問題.

對EM算法存在的上述問題, 目前已有許多改進(jìn)方法. 官國宇等[2]提出了一種基于雙截?cái)嗷旌细咚鼓Ｐ屯茖?dǎo)的EM算法, 并使用Bayes信息準(zhǔn)則優(yōu)化所擬合的混合高斯模型參數(shù)； Castillo-Barnes等[3]提出使用推廣的混合α-stable模型泛化EM算法, 提高了算法的魯棒性； Safarinejadian等[4]結(jié)合分布式平均方法改進(jìn)EM算法, 使其能應(yīng)用于模擬具有網(wǎng)狀拓?fù)浣Y(jié)構(gòu)的任何網(wǎng)絡(luò)中； Ho等[5]利用協(xié)方差修正EM算法中最大化步的偏移量加快了算法的收斂速度； Lin等[6]結(jié)合Krasnoselskii-Mann(KM)算法和EM算法加速算法的收斂, 并避免了圖像重建時(shí)出現(xiàn)的模式崩潰問題； 王衛(wèi)東等[7]提出了使用密度峰值聚類方法初始化混合高斯模型的參數(shù), 并使用相對熵作為EM算法在迭代過程中的終止條件, 其目的是優(yōu)化混合高斯模型的最終參數(shù), 并提高模型的魯棒性； Chaudhari等[8]提出了使用k最大似然估計(jì)器替代傳統(tǒng)EM算法對混合模型進(jìn)行參數(shù)估計(jì), 并實(shí)驗(yàn)驗(yàn)證了該方法能在分類精度與傳統(tǒng)EM算法相差較小的基礎(chǔ)上有效提高模型的收斂速度； Wang等[9]提出使用基于EM算法的Bayes推理方法解決了模型及其參數(shù)的不穩(wěn)定性； He等[10]基于源自低通信號特性的低秩稀疏先驗(yàn)策略提出了一種新型EM算法, 并將其應(yīng)用于多圖推理與聚類問題中, 實(shí)驗(yàn)結(jié)果表明, 該算法能有效改善傳統(tǒng)EM算法的模型穩(wěn)定性.

雖然目前對EM算法的研究成果較豐富, 但其改進(jìn)算法大多數(shù)側(cè)重于解決EM算法的魯棒性差與收斂速度較慢的問題, 對于模型易陷入局部最優(yōu)問題的解決方案仍較少. 針對該問題, 本文通過引入模糊C均值(fuzzyC-means, FCM)算法對EM算法進(jìn)行改進(jìn), 先將FCM算法用于生成EM算法的初始參數(shù), 再將初始參數(shù)作為先驗(yàn)知識導(dǎo)入到模型中輔助算法跳出局部最優(yōu)陷阱. 最后通過實(shí)驗(yàn)證明改進(jìn)EM算法在無監(jiān)督聚類任務(wù)中相比于傳統(tǒng)的聚類算法效果更優(yōu), 且因改進(jìn)后的EM算法跳出了局部最優(yōu)陷阱使其結(jié)果更可靠.

1 基于模糊C均值算法的改進(jìn)EM算法

1.1 EM算法和混合高斯模型

期望極大算法是一種迭代優(yōu)化算法, 用于對含有隱變量的概率參數(shù)模型進(jìn)行極大似然估計(jì), 以求出能擬合給定數(shù)據(jù)分布的概率模型的最優(yōu)參數(shù). 該算法需先根據(jù)給定的顯性數(shù)據(jù)初步估計(jì)出能擬合該數(shù)據(jù)分布的模型參數(shù), 再根據(jù)已估計(jì)出的模型參數(shù)預(yù)測隱性數(shù)據(jù)的值, 然后根據(jù)估計(jì)出的隱性數(shù)據(jù)及之前給出的顯性數(shù)據(jù)再重新對參數(shù)進(jìn)行估計(jì), 反復(fù)迭代上述步驟直至收斂后結(jié)束迭代.

對于一個(gè)含有隱變量Z的概率模型, 假設(shè)給定顯性數(shù)據(jù)為Y, 則概率模型關(guān)于Y的概率分布為P(Y|θ), 其中θ為要估計(jì)的模型參數(shù).則顯性數(shù)據(jù)Y關(guān)于模型參數(shù)θ的對數(shù)似然函數(shù)為L(θ)=logP(Y|θ)； 假設(shè)顯性數(shù)據(jù)Y和隱變量Z之間的聯(lián)合概率分布為P(Y,Z|θ), 則整體的對數(shù)似然函數(shù)為L′(θ)=logP(Y,Z|θ).EM算法通過迭代求解顯性數(shù)據(jù)Y關(guān)于模型參數(shù)θ的對數(shù)似然函數(shù)L(θ)=logP(Y|θ)的極大近似, 從而得到參數(shù)θ的估計(jì)值, 即

(1)

混合高斯模型(Gaussian mixture model, GMM)是一種基于高斯分布的概率密度模型, 其通過將多個(gè)單高斯模型線性組合, 以克服傳統(tǒng)單高斯模型對復(fù)雜數(shù)據(jù)樣本擬合度較低的缺點(diǎn). 理論上, 一個(gè)混合高斯模型可擬合任意復(fù)雜的數(shù)據(jù)分布, 只要該混合高斯模型擁有足夠多且權(quán)重設(shè)計(jì)合理的單高斯模型. 顯然, 將混合高斯模型應(yīng)用到聚類任務(wù)中時(shí), 需根據(jù)數(shù)據(jù)特征向量推算出混合高斯模型的權(quán)重, 其中混合高斯模型中的各單高斯模型(分量)可視為聚類任務(wù)的目標(biāo)聚類類型. 特別地, 當(dāng)已知目標(biāo)的概率密度函數(shù)時(shí), 求解混合高斯模型的任務(wù)即轉(zhuǎn)化為對高斯概率模型的參數(shù)進(jìn)行估計(jì). 對于已知特征空間X={x1,x2,…,xn}, GMM的概率模型為

(2)

其中:x為自變量; 參數(shù)π,μ,ε分別為混合概率模型的混合系數(shù)、 期望和方差；N(x|μk,εk)表示混合概率模型中第k個(gè)分量, 參數(shù)μk為混合概率模型中第k個(gè)分量的期望, 參數(shù)εk為混合概率模型中第k個(gè)分量的方差；πk為混合系數(shù), 即分量N(x|μk,εk)的權(quán)重, 其滿足約束條件

(3)

由式(2)可見, GMM模型中需要進(jìn)行估計(jì)的參數(shù)分別為μk,εk和πk, 本文使用EM算法估計(jì)混合高斯模型的參數(shù), 其算法流程分為兩步： 首先估計(jì)函數(shù)參數(shù)的粗略值； 其次根據(jù)已知的參數(shù)計(jì)算最大似然函數(shù).假設(shè)參數(shù)已被初步估計(jì), 即可視為參數(shù)已知, 則需根據(jù)其求解參數(shù)的最大似然函數(shù).首先求解任意高斯模型k均值μk的最大似然函數(shù), 先將式(2)中的所有樣本連乘得到關(guān)于π,μ,ε的最大似然函數(shù), 再對式(2)取對數(shù)得到關(guān)于π,μ,ε的對數(shù)似然函數(shù), 最后對μk求導(dǎo)并令導(dǎo)數(shù)為0, 即可得到關(guān)于μk的最大似然函數(shù)：

(4)

令

(5)

解得

(7)

(8)

由于模型權(quán)重πk存在約束條件式(3), 因此需加入Lagrange算子：

(9)

解得

(10)

由于使用EM算法對混合高斯模型進(jìn)行參數(shù)估計(jì)時(shí), 需要先驗(yàn)的高斯模型初始值擬合概率分布, 故需先指定π,μ,ε的初始值, 將其代入式(7)計(jì)算出γ(znk), 再將γ(znk)代入式(5),(8),(10)分別求出新的π,μ,ε, 然后用新的π,μ,ε代入式(7)計(jì)算出新的γ(znk), 如此循環(huán)迭代, 直到算法收斂.EM算法流程如下.

算法1期望最大化算法.

輸入：K,π,μ,ε,e；

輸出：πnew,μnew,εnew；

while max{‖lnp(x|π,μ,ε)new-lnp(x|π,μ,ε)old‖2}>edo formula (5) and

1.2 模糊C均值算法

模糊C均值(FCM)算法[11]是一種模糊無監(jiān)督聚類算法, 其為基于劃分的聚類算法, 基本思想是通過對目標(biāo)函數(shù)的迭代, 使隸屬于同一聚類中心的數(shù)據(jù)點(diǎn)之間相似度最大, 而隸屬于不同聚類中心的數(shù)據(jù)點(diǎn)之間相似度最小. 作為K均值算法(K-means)的模糊化改進(jìn), FCM算法在其基礎(chǔ)上引入了基于模糊理論的隸屬度概念[12], 從而將K均值算法對數(shù)據(jù)的硬性劃分轉(zhuǎn)變?yōu)橥ㄟ^隸屬度函數(shù)確定某一數(shù)據(jù)類型的柔性劃分.

作為一種基于目標(biāo)函數(shù)的聚類算法, 根據(jù)其基本思想, 將一組含有n個(gè)向量的特征空間X={x1,x2,…,xn}分為l類, 其聚類中心用C={c1,c2,…,cl}表示, 求解每個(gè)聚類中心, 使距離指標(biāo)的目標(biāo)函數(shù)達(dá)到最小.其目標(biāo)函數(shù)可定義為

(11)

其中：U=(uij)是隸屬度矩陣, 其元素uij表示第i個(gè)向量相對于第j類的隸屬度, 該隸屬度的取值范圍為uij∈[0,1]； 元素dij=‖xi-cj‖表示第i個(gè)特征向量xi與第j個(gè)聚類中心cj之間的歐氏距離, 類似于隸屬度, 該變量通常用于表示特征向量與聚類中心的相似性；m∈[1,+∞)是模糊常數(shù), 表示聚類的模糊程度,m值越大, 表示模糊程度越大.該目標(biāo)函數(shù)的約束條件為對于任意樣本xi, 其對各聚類中心的隸屬度之和為1, 可表示為

(12)

算法通過使用Lagrange乘子法構(gòu)造新的函數(shù)求解給定約束條件下目標(biāo)函數(shù)的最小值：

(13)

其中λ為Lagrange乘子.對函數(shù)F求極值得到最優(yōu)化條件如下：

由極值條件式(12)解得：

(18)

FCM算法流程如下.

算法2模糊C均值算法.

輸入：X,c,m,ε;

輸出：U,C;

1.3 改進(jìn)的期望最大化算法

已知EM算法的迭代策略屬于局部最優(yōu)策略, 且其在迭代過程中極度依賴初始參數(shù)值的選擇, 故在初始值極端化的情況下易陷入局部收斂問題. 為解決上述問題, 本文將FCM算法用于EM算法的初始化過程, 即使用基于柔性劃分的FCM算法. 將數(shù)據(jù)通過模糊聚類算法預(yù)先分配到混合高斯模型的各分量中, 再根據(jù)數(shù)據(jù)在模型中的概率分布, 用期望最大化算法求解混合高斯模型, 最后在聚類中對每個(gè)數(shù)據(jù)點(diǎn)選擇概率較大的類作為最終聚類結(jié)果. 使用基于FCM的混合高斯模型可在保持原有算法收斂速度的同時(shí), 較合理地搜索到最優(yōu)的模型參數(shù).

FCM算法初始化EM算法參數(shù)的過程如下： 首先, 為初始化聚類中心C, 需要隨機(jī)從輸入的數(shù)據(jù)集合X中選取K個(gè)特征向量作為初始聚類中心； 然后, 根據(jù)該聚類中心集合對每個(gè)數(shù)據(jù)點(diǎn)使用目標(biāo)函數(shù)計(jì)算隸屬度矩陣U； 再通過更新后的隸屬度矩陣U重新計(jì)算新的聚類中心; 迭代計(jì)算該流程直到收斂, 最后將聚類中心C輸出并作為EM算法中的初始μ輸入.

獲得初始μ后根據(jù)初始μ={μ1,μ2,…,μn}和特征向量X={x1,x2,…,xn}計(jì)算

即完成了EM算法的初始化.

改進(jìn)的期望最大化算法(IEM)流程如下.

算法3改進(jìn)的期望最大化算法.

輸入：X,c,m,e;

輸出：πnew,μnew,εnew;

whileU,C=FCM(X,c,m,e) do formula (5),(10) and

2 IEM在用戶知識模型中的應(yīng)用

2.1 數(shù)據(jù)屬性

本文采用數(shù)據(jù)集UCI User Knowledge Modeling(http://archive.ics.uci.edu/ml/datasets/User+Knowledge+Modeling), 其通過數(shù)據(jù)集下5個(gè)相關(guān)屬性(STG,SCG,STR,LPR,PEG)衡量直流電機(jī)學(xué)科學(xué)生的學(xué)習(xí)狀況[13]. 該數(shù)據(jù)集相關(guān)屬性列于表1. 將數(shù)據(jù)集中的5個(gè)屬性作為特征向量X={x1,x2,…,x5}輸入到FCM,K-means,EM和IEM模型中, 對用戶知識水平進(jìn)行聚類分析.

表1 數(shù)據(jù)集UCI User Knowledge Modeling相關(guān)屬性

2.2 模型與數(shù)據(jù)的結(jié)合

針對本文的研究目標(biāo), 即對用戶知識水平的聚類分析, 本文在測試這些算法的聚類效果時(shí), 將數(shù)據(jù)集的5個(gè)屬性作為特征向量輸入到模型中. 由于數(shù)據(jù)集中所有數(shù)據(jù)按標(biāo)簽列(UNS列)分為4類, 即所有數(shù)據(jù)共有4種類型, 故將算法的聚類中心數(shù)目設(shè)為4個(gè).

考慮EM算法參數(shù), 由于π,μ,ε在初始狀態(tài)下未知, 因此本文在測試原始EM算法時(shí)使用隨機(jī)分配的π,μ,ε值初始化EM算法. 根據(jù)FCM算法的參數(shù), 除固定的特征向量空間X、 聚類中心個(gè)數(shù)C外, 模糊常數(shù)m也會影響其最終的分類效果, 考慮到模糊常數(shù)m是一種與實(shí)際數(shù)據(jù)相關(guān)的經(jīng)驗(yàn)變量, 雖然從聚類有效性角度得出m的取值范圍為1.5≤m≤2.5, 但具體的最優(yōu)值只能通過測試尋找.

對于模型結(jié)果的評價(jià), 考慮到本文所使用的數(shù)據(jù)集具有參考類別, 故可使用外部聚類指標(biāo)進(jìn)行評價(jià), 選取JC,FMI,RI三個(gè)主流的外部指標(biāo)作為本文結(jié)果的評價(jià)指標(biāo)[14]. 其中： JC表示Jaccard系數(shù), 其含義為參考集合與聚類集合的交集大小與并集大小的比值, 即所有屬于同一參考類中的樣本與在聚類結(jié)果中屬于同類樣本對所占比例, 其公式為

(19)

FMI表示聚類結(jié)果中和參考集合同類的樣本比例與參考集合中和聚類結(jié)果同類的樣本比例的幾何平均數(shù), 其公式為

(20)

RI表示聚類結(jié)果和參考集合中屬于同類樣本與不屬于同類樣本占所有樣本的比例, 其公式為

(21)

這里a表示在聚類結(jié)果中與參考集合和真實(shí)集合中屬于同類的數(shù)據(jù)樣本數(shù)量,b表示在聚類結(jié)果中與參考集合不屬于同類且聚類結(jié)果與真實(shí)集合同類的數(shù)據(jù)樣本數(shù)量,c表示在聚類結(jié)果中與參考集合不屬于同類且參考集合與真實(shí)集合同類的數(shù)據(jù)樣本數(shù)量,d表示聚類結(jié)果中既不和參考集合同類又不和真實(shí)集合同類的數(shù)據(jù)樣本數(shù)量,m(m-1)/2表示樣本的總數(shù)量. 上述3個(gè)外部指標(biāo)的取值范圍均為[0,1], 且其值越大表示聚類的效果越貼近真實(shí)集合的類別分布.

本文在以聚類中心數(shù)為4的前提下, 使用數(shù)據(jù)集UCI User Knowledge Modeling作為樣本, 分別在m=1.5,2,2.5情形下重復(fù)測試100次, 評價(jià)指標(biāo)JC,FMI,RI的平均值列于表2. 由表2可見, 在特征向量、 聚類中心數(shù)不變的情形下,m=1.5和m=2的JC,FMI,RI值相差較小, 且其JC,FMI值均明顯低于m=2.5的JC,FMI值, 僅有RI值略高于m=2.5, 因此當(dāng)m=2.5時(shí)FCM模型的性能達(dá)到最優(yōu), 故本文在實(shí)例仿真時(shí)模糊常數(shù)m取值為2.5.

表2 不同模糊常數(shù)下的FCM模型平均指標(biāo)

2.3 實(shí)例仿真與結(jié)果分析

將數(shù)據(jù)集UCI User Knowledge Modeling的數(shù)據(jù)樣本輸入FCM,K-means,EM,IEM 4種無監(jiān)督聚類算法中進(jìn)行實(shí)例仿真實(shí)驗(yàn), 仿真結(jié)果列于表3. 由表3可見: 本文IEM算法在JC指標(biāo)上， 高于FCM和EM算法約19%, 高于K-means算法約30%； 在FMI指數(shù)上， IEM算法高于FCM和EM算法約13%, 高于K-means算法約23%； 在RI指數(shù)上, IEM算法高于FCM和K-mean算法約9%, 高于EM算法約5%. 從而驗(yàn)證了本文IEM算法在用戶知識建模的聚類任務(wù)中效果明顯優(yōu)于其他傳統(tǒng)聚類算法, 其主要原因是本文算法結(jié)合了FCM算法柔性劃分的特性, 能根據(jù)數(shù)據(jù)分布最優(yōu)化混合高斯模型的初始參數(shù), 使其在最大程度上避免陷入局部最優(yōu)的陷阱.

表3 不同算法對數(shù)據(jù)集UCI User Knowledge Modeling的仿真結(jié)果

綜上所述, 本文針對使用傳統(tǒng)期望最大化算法進(jìn)行參數(shù)估計(jì)的混合高斯模型的最終聚類效果過于依賴初始概率密度中心的問題, 使用模糊C均值初始化EM算法的模型參數(shù)改進(jìn)EM算法, 并將改進(jìn)后的EM算法應(yīng)用于無監(jiān)督聚類任務(wù)中, 最后通過無監(jiān)督聚類的性能評價(jià)指標(biāo)JC,FMI和RI驗(yàn)證該改進(jìn)算法的性能. 通過數(shù)據(jù)集UCI的仿真實(shí)驗(yàn)結(jié)果表明, 本文算法的JC,FMI,RI指標(biāo)均較原始FCM和EM算法有較大提高, 從而驗(yàn)證了IEM算法在無監(jiān)督聚類任務(wù)中效果較傳統(tǒng)聚類算法更優(yōu).