曹紅麗, 山拜?達(dá)拉拜

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

0 引言

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

1 EM算法簡(jiǎn)述

EM算法從不完整數(shù)據(jù)估計(jì)混合模型的概率密度,這里的不完整數(shù)據(jù)有兩種：①觀測(cè)數(shù)據(jù)不完整,②引入隱變量使之成為不完整數(shù)據(jù)?；旌细咚鼓Ｐ偷母怕拭芏群瘮?shù),即：

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

2 混合 EM算法介紹

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

圖 1 混合算法流程

算法步驟如下：

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

步驟 2：對(duì)每個(gè)個(gè)體應(yīng)用 Annealing-改進(jìn)EM算法,其停止條件設(shè)置如下：

選擇最優(yōu)模型階數(shù)的方法通常是引入一個(gè)針對(duì)模型階數(shù)的懲罰函數(shù),通常是將似然函數(shù)減去一個(gè)用來(lái)懲罰 m的項(xiàng),最小長(zhǎng)度描述的 MDL準(zhǔn)則[7]的使用的懲罰函數(shù)比較簡(jiǎn)單,為：

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

步驟 4：選擇簡(jiǎn)單的輪盤(pán)賭方法;

步驟 5：選擇單點(diǎn)交叉,交叉概率為 0.4;

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

基于混合 EM算法的聚類(lèi)算法[8-9]：

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

輸出：聚類(lèi) C={C1,C2,…,CN}。

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

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

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

3 仿真實(shí)例

信真實(shí)例參考文獻(xiàn)[10],采用 UCI數(shù)據(jù)[11]提供的機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的數(shù)據(jù) Iris對(duì)算法進(jìn)行了聚類(lèi)算法測(cè)試。

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

查準(zhǔn)率和查全率可用下面公式來(lái)計(jì)算：

4 結(jié)語(yǔ)

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

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

[1]劉建明,侯紀(jì)周,奚宏生.基于 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]周明,孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社,2005.

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

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

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

[8]王維彬,鐘潤(rùn)添.一種基于貪心 EM算法學(xué)習(xí) GMM的聚類(lèi)算法[J].計(jì)算機(jī)仿真,2007,24(02)：65-67.

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

[10]飛思科技產(chǎn)品研發(fā)中心.Matlab 7輔助信號(hào)處理技術(shù)與應(yīng)用[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/.