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

曹紅麗, 山拜?達拉拜

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

0 引言

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

1 EM算法簡述

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

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

2 混合 EM算法介紹

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

圖 1 混合算法流程

算法步驟如下：

步驟 1：混合算法的參數設置

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

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

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

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

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

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

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

輸入：數據集 x={x1,x2,…,xN},

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

步驟 1：對每個數據運行混合算法,得到具有最優 m個高斯分量的混合高斯模型;

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

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

3 仿真實例

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

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

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

4 結語

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

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

[1]劉建明,侯紀周,奚宏生.基于 GMM與 EM算法的呼叫接入控制[J].通信技術,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].北京：國防工業出版社,2005.

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

[6]楊綠溪.現代數字信號處理[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]飛思科技產品研發中心.Matlab 7輔助信號處理技術與應用[M].北京：電子工業出版社,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/.