基于遺傳算法的K-means初始化EM算法及聚類應用

摘 要:混合高斯模型能夠有效地擬合概率密度函數(shù)，常用的混合高斯概率密度模型參數(shù)估計方法是EM迭代算法，這種算法的缺點是估計精度過分依賴于初始值，而且不能估計模型階數(shù)。基于遺傳算法的K-means初始化EM算法可以同時估計模型階數(shù)和參數(shù)。試驗結果表明，該算法具有更好的聚類效果。關鍵詞:混合高斯模型; 遺傳算法; K-means; 聚類應用

中圖分類號:TN911.72文獻標識碼:A

文章編號:1004-373X(2010)15-0102-02

K-means Initialization EM Algorithm and Its Clustering Application Based on Genetic Algorithm

SENBAI Dalabaev， CAO Hong-li， YOUNUSI Aisha

(School of Information Science Engineering， Xinjiang University， Urumqi 830046， China)

Abstract: The probability density function can be efficiently fitted by Gaussian mixture model. EM iteration algorithm is one of popular algorithms for parameters estimation of Gaussian mixture probability density model. However， this method depends on initial parameters highly and can not estimate the orders of models. K-means initialization EM algorithm based on the genetic algorithms can estimate the orders and parameters of models. The simulation results indicate that this method has a good clustering ability.Keywords: Gaussian mixture model; genetic algorithm; K-means; clustering application

收稿日期:2010-03-30

基金項目:國家自然科學基金資助項目(60971130)

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

1 EM算法簡述

EM算法[1-2]從不完整數(shù)據(jù)估計混合模型的概率密度，這里的不完整數(shù)據(jù)有兩種，一是觀測數(shù)據(jù)不完整，二是引入隱變量使之成為不完整數(shù)據(jù)。混合高斯模型的概率密度函數(shù)，即:



P=∑mi=1αiPi(x|υi)(1)

Pi(x|υi)=(2π)-d2Σ-12i#8226;

exp-12(x-μi)TΣ-1i(x-μi)(2)



式中，υi=(μTi;Σi)T;μi是第i-分支的期望，它是d維向量;Σi是第i-分支的協(xié)方差矩陣，是d階對稱正定矩陣;m是模型的階數(shù)。

觀測數(shù)據(jù){x1，x2，…，xN}，隱變量數(shù)據(jù)標簽向量集{z1，z2，…，zN}，xi的標簽向量為zi={zi1，zi2，…，zim}T，如果xi的所在族確定了(比如xi在第k族中)，那么zik=1，xi在第k族中0，其他，且有p(zik=1|θ)=αk(i=1，2，…，N，k=1，2，…，m)，y=(x，z)完整數(shù)據(jù)的似然函數(shù)為log(y1，y2，…，yN|θ)，其中:



p(y1，y2，…，yN|θ)=∏Ni=1∏mj=1[p(xi|θj)αj]zN

θ=(α1，α2，…，αm，υT1，υT2，…，υTm)T(3)



設置初始值，由完整數(shù)據(jù)y的似然函數(shù)和拉格朗日法求max，b，δ{log(y1，y2，…，yn)}

E步:由上一步估計的參數(shù)值推導隱變量值:



wij=pj|xi，θ(t)=α(t)jp(xi|θ(t)j)∑mk=1α(t)kp(xi|θ(t)k)=

|Σ(t)i-1/2|exp-12xi-μ(t)jTΣ(t)j-1(xi-μ(t)j)∑mk=1|Σ(t)k-1/2|exp-12(xi-μ(t)k)TΣ(t)j-1(xi-μ(t)k)(4)



M步:由隱變量估計參數(shù)值:

j=1N∑Ni=1wij(5)

j=∑Ni=1wijxiNj(6)

j=1Nj∑Ni=1wijxi(xi-j)(xi-j)T(7)

2 混合算法介紹

模型階數(shù)m是一個重要參數(shù)，當樣本數(shù)量很小時，可以利用窮舉法尋找最佳模型階數(shù)，當樣本數(shù)量很大時，窮舉法不可能，因此本文提出一種基于遺傳算法的混合算法，該算法能自動搜索到最佳模型階數(shù)[3]。

(1) 編碼。對于模型階數(shù)m的編碼，m是介于1和最大類別數(shù)Maxclassnum之間的一個整數(shù)，已證明，當數(shù)Maxclassnum≤n(n為樣本個數(shù))[4]，達到最大優(yōu)化。

(2) 初始化種群。隨機生成p個染色體種群，交叉概率pc為0.4~0.99，變異概率pm為0.000 1~0.1[5]。

(3) 固定次數(shù)的K-means初始化EM算法。K-means初始化的具體過程如下:

μi的初始化過程:隨機將m個觀測數(shù)據(jù)作為初始K-means聚類中心，再將所有觀測數(shù)據(jù)按照距上一步聚類中心最短距離重新聚類并計算新的聚類中心，直到達到規(guī)定的目標函數(shù)為止，最后將聚類中心作為μi的初始值。

Σi的初始化過程[4]:觀測數(shù)據(jù)xi={xi1，xi2，…，xid}，μi={μi1，μi2，…，μid}，則Σij=∑Nk=1(xki-μki)(xkj-μkj)，其中i=1，2，…，d;j=1，2，…，d。

(4) 適應度值計算。選擇最優(yōu)模型階數(shù)的方法通常是引入一個針對模型階數(shù)的懲罰形式的似然函數(shù)，因為似然函數(shù)是非降的函數(shù)，通常是將似然函數(shù)減去一個用來懲罰m的項，最小長度描述的MDL準則[6]的遠離使用的懲罰函數(shù)比較簡單，為:

MDL=log p(x|θ)-m(l+1)2log N

式中:m為模型階數(shù);l=d+d(d+1)2。

算法流程圖如圖1所示。

基于混合算法的聚類算法[7-8]如下:

輸入:數(shù)據(jù)集x={x1，x2，…，xN};

輸出:聚類C={c1，c2，…，cN};

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

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

圖1 算法流程

3 仿真實例

仿真數(shù)據(jù)[9]選取三分支二維數(shù)據(jù)，其序列波形如圖2所示，仿真結果見表1。本文采用UCI提供的機器學習數(shù)據(jù)庫中的數(shù)據(jù)Iris對算法進行了聚類算法測試[10]，仿真結果如表2所示。

圖2 三分支二維仿真序列波形

表1 三分支二維數(shù)據(jù)的仿真結果

參數(shù)真值算法結果

α(0.2，0.3，0.5)′(0.200，0.299 5，0.500 5)′查準率查全率

μ1(2，8)′(1.981 9，7.888 9)′

Σ142234.022 61.829 31.829 32.758 3

1.000 01.000 0

μ2(10，2)′(10.190 0，1.895 9)′

Σ240014.302 30.098 90.098 90.987 8

0.998 00.996 0

μ3(15，10)′(15.062 5，9.896 3)′

Σ32-1-151.885 8-0.900 8-0.900 84.861 1

0.993 40.996 7

表2 Iris數(shù)據(jù)的仿真結果

分支查準率查全率

10.900 01.000 0

21.000 00.909 1

31.000 01.000 0

4 結 語

用K-means初始化混合高斯模型的模型參數(shù)，將遺傳算法應用到EM算法中估計混合高斯模型的模型階數(shù)，并將此混合算法應用到聚類算法中，通過差準率和查全率驗證該混合算法的性能。通過表1的仿真結果，混合算法準確估計了三分支的模型階數(shù)，參數(shù)估計比較準確，查全率和差準率比較高，通過UCI數(shù)據(jù)仿真，表2的結果顯示查全率和差準率好，其聚類效果好。該混合算法有一個缺點，由于混合算法不能保證每一次仿真Σi都是非奇異矩陣，實驗有時得到錯誤的仿真結果，故該混合算法有待改進。

參考文獻

[1]王平波，蔡志明，劉旺鎖.混合高斯概率密度模型參數(shù)的期望最大化估計[J].聲學技術，2007，26(3):498-502.

[2]衛(wèi)紅凱，王平波，蔡志明，等.混響的混合高斯概率密度建模[J].聲學技術，2007，26(3):514-518.

[3]孫秀娟，劉希玉.基于初始化中心優(yōu)化的遺傳K-means聚類新算法[J].計算機工程與應用，2008，44(23):52-56.

[4]蘇奪寶，劉仁金.基于佳點集遺傳算法的聚類技術[J].計算機應用，2005，25(3):644-655.

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

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

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

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

[9]飛思科技產品研發(fā)中心.Matlab 7輔助信號處理技術與應用[M].北京:電子工業(yè)出版社，2005.

[10]HETTICH S， BLAKE C L， MERZ C J. UCI repository of machine learing database[J/OL]. [1998-03-27]. http://citeseerx.ist.psu.edu/showciting.

[11]張帥欽，張波濤.基于層次的K-均值聚類[J].現(xiàn)代電子技術，2008，31(16):163-165.