混合 EM算法研究及聚類應用

曹紅麗, 山拜?達拉拜

(新疆大學 信息科學與工程學院,新疆 烏魯木齊 830046)

0 引言

在通信和信號處理中,通常將背景噪聲看成是高斯噪聲,還有看成多模噪聲,混合高斯模型是一種比較常用的參數(shù)化模型,可以擬合任何概率密度函數(shù),給出模擬同質(zhì)性和異質(zhì)性的一個自然框架和半?yún)?shù)框架,研究最多的就是多元高斯模型,它在統(tǒng)計學和模式識別以及數(shù)據(jù)挖掘等等[1]中得到應用。EM算法是基于最大似然估計的一種針對不完全數(shù)據(jù)的可實現(xiàn)的迭代算法,依賴于初始值,容易陷入局部收斂值,協(xié)方差矩陣容易出現(xiàn)奇異。EM算法[2]可以看成是一種貪心的爬山算法,是局部搜索算法,將模擬退火算法[3]應用到EM算法中,修改EM算法,使每一次不都是向梯度最大方向,以一定的概率向非梯度方向迭代,EM算法不能估計混合高斯模型的模型階數(shù),遺傳算法是一種全局搜索算法,將遺傳算法[4]應用到 EM算法中,并將 K-means算法用于EM算法的初始化,形成基于最小信息編碼準則的同時估計模型階數(shù)和參數(shù)的混合算法,同時將這種混合算法應用到聚類算法中。

1 EM算法簡述

EM算法從不完整數(shù)據(jù)估計混合模型的概率密度,這里的不完整數(shù)據(jù)有兩種：①觀測數(shù)據(jù)不完整,②引入隱變量使之成為不完整數(shù)據(jù)。混合高斯模型的概率密度函數(shù),即：

對當前最有個體隨機擾動,產(chǎn)生一個新的最有個體 θ′,計算似然函數(shù)值的增量Δ。如果Δ＞0,則以概率p=exp(-Δ/T0)接受新產(chǎn)生的最優(yōu)點為當前最優(yōu)點,其中T0為設置的初始值,采用經(jīng)驗值。

2 混合 EM算法介紹

EM算法不能同時估計模型的階數(shù)和模型參數(shù),且 EM算法可能會收斂到局部收斂值,因此將模擬退火算法和 EM算法相介乎而,使算法收斂到全局值,同時將遺傳算法應用到上述算法中,此混合算法既能保證收斂到全局收斂值,而且估計混合高斯模型的模型階數(shù),保證協(xié)方差矩陣非奇異。其算法流程如下：

圖 1 混合算法流程

算法步驟如下：

步驟 1：混合算法的參數(shù)設置

步驟 2：對每個個體應用 Annealing-改進EM算法,其停止條件設置如下：

選擇最優(yōu)模型階數(shù)的方法通常是引入一個針對模型階數(shù)的懲罰函數(shù),通常是將似然函數(shù)減去一個用來懲罰 m的項,最小長度描述的 MDL準則[7]的使用的懲罰函數(shù)比較簡單,為：

步驟 3：條件判斷：滿足條件則執(zhí)行下面的操作,并將最后一次迭代的實驗數(shù)據(jù)作為最后的輸出;

步驟 4：選擇簡單的輪盤賭方法;

步驟 5：選擇單點交叉,交叉概率為 0.4;

步驟 6：選擇均勻變異,變異概率為 0.000 1,得到 P(t+1),并轉(zhuǎn)到步驟 2。

基于混合 EM算法的聚類算法[8-9]：

輸入：數(shù)據(jù)集 x={x1,x2,…,xN},

輸出：聚類 C={C1,C2,…,CN}。

步驟 1：對每個數(shù)據(jù)運行混合算法,得到具有最優(yōu) m個高斯分量的混合高斯模型;

步驟 2：計算出每個數(shù)據(jù)對應混合高斯模型里每個高斯分量的概率密度,然后根據(jù)概率密度最高原則分配各個數(shù)據(jù)到混合高斯模型里的各個高斯分量,完成聚類過程,即：

則 xi∈ Ck,其中 j=1,2,…,m。

3 仿真實例

信真實例參考文獻[10],采用 UCI數(shù)據(jù)[11]提供的機器學習數(shù)據(jù)庫中的數(shù)據(jù) Iris對算法進行了聚類算法測試。

TPi：分類器判斷 Ci且實際屬于 Ci的樣本數(shù)目;FPi：分類器判斷屬于 Ci且實際不屬于 Ci的樣本數(shù)目;FNi：分類器判斷不屬于 Ci且實際屬于 Ci的樣本數(shù)目。

查準率和查全率可用下面公式來計算：

4 結(jié)語

通過表 1可以得出,動量因子 lr在 0.5～0.9的取值范圍內(nèi),查準率和查全率較好,且每一次都能精確得到模型的階數(shù),每一次都能避免協(xié)方差矩陣出現(xiàn)奇異,但是此混合算法沒有考慮算法的收斂時間,其中的一些參數(shù)設置都是依賴于經(jīng)驗值。

表 1 UCI數(shù)據(jù)的查準率和查全率(Iris數(shù)據(jù))

[1]劉建明,侯紀周,奚宏生.基于 GMM與 EM算法的呼叫接入控制[J].通信技術(shù),2002(05)：50-53.

[2]DEMPSTER A P,LAIRD N M,RUBIN D B.Maximum Likelihood from Incomplete Data via the EM Algorithm[J].J.R.Statist.Soc.B,1977(39)：1-39.

[3]UEDA N,NAKANO R.Deterministic Annealing EMAlgorithm[J].1998,(11)：271-282.

[4]周明,孫樹棟.遺傳算法原理及應用[M].北京：國防工業(yè)出版社,2005.

[5]孫秀娟,劉希玉.基于初始化中心優(yōu)化的遺傳 Kmeans聚類新算法 [J].計算機工程與應用,2008,44(23)：166-182.

[6]楊綠溪.現(xiàn)代數(shù)字信號處理[M].北京：科學出版社,2007.

[7]Figueiredo M A T,Jain A K.Unsupervised Selection and Estimation of Finite Mixture Models[J].IEEE,2000(02)：87-90.

[8]王維彬,鐘潤添.一種基于貪心 EM算法學習 GMM的聚類算法[J].計算機仿真,2007,24(02)：65-67.

[9]岳佳,王士同.雙重高斯混合模型的 EM算法的聚類問題研究[J].計算機仿真,2007,24(11)：110-113.

[10]飛思科技產(chǎn)品研發(fā)中心.Matlab 7輔助信號處理技術(shù)與應用[M].北京：電子工業(yè)出版社,2005.

[11]Hettich S,Blake C L,Merz C J.UCI Repository of Machine Learing Database[EB/OL].(1998-01-05)[2010-03-01].http：//archive.ics.uci.edu/ml/.