k均值聚類中的EM思想

馬麗娜

（西安財經(jīng)學院行知學院信息系，陜西 西安 710038）

0 引言

在數(shù)據(jù)分析中，根據(jù)數(shù)據(jù)集中有無某些已知類別的樣本，可以分為監(jiān)督學習和無監(jiān)督學習兩種。無監(jiān)督學習是最常見的一種統(tǒng)計學習模式，又稱為聚類分析，已經(jīng)在文本挖掘[1]、遙感圖像[2]、生物醫(yī)學[3]、社交網(wǎng)絡(luò)[4]、安全檢測[5]等領(lǐng)域得到了廣泛的應用。目前已經(jīng)有許多成熟的聚類方法，像k均值聚類，支持向量機，層次聚類，基于密度的聚類等[6]。k均值算法以其簡潔高效的特性，是最受關(guān)注的聚類方法之一。最大期望值算法(EM算法)，是針對缺失數(shù)據(jù)的一種統(tǒng)計學習理論，常常被用來求在含有不完整觀測的數(shù)據(jù)集下的極大似然估計[7]。本文分析了k均值聚類和EM算法思想上的相通之處，指出了兩種方法迭代過程的等價性。

1 相關(guān)理論知識

1.1 k均值聚類

k均值算法中的輸入變量為類個數(shù)k和樣本矩陣X。其中X中存有參與聚類的n個樣本。算法的目標是將n個數(shù)據(jù)對象劃分為k個類，以便使得所獲得的k個子類滿足：同一子類中的對象相似度較高；而不同子類中的對象相似度較小。k均值算法基本步驟如下：

a）從n個樣本中任意選擇 k個對象作為初始類中心；

b）根據(jù)每個子類中樣本的均值，計算每個對象與這些中心樣本點的距離；并將每個樣本分到這樣一個子類，這個子類的中心是所有k個中心點離該樣本最近的；

c）重新計算每個子類的均值；

d）當滿足一定收斂條件(如類中心不再變化)時，則算法終止；如果條件不滿足則回到步驟b)。

1.2 模糊k均值聚類

模糊k均值聚類(FCM)是對傳統(tǒng)k均值聚類的拓展。在FCM中，樣本不再明確地屬于或者不屬于某一類，而是對各個子類有個0和1之間的隸屬度。詳細算法如下：

a）從n個樣本中任意選擇k個對象作為初始類中心；

b）計算每個對象與這些中心點的距離；并根據(jù)這些距離值計算樣本對各單類的隸屬度；

c）根據(jù)樣本的隸屬度重新計算每個子類的均值(找出中心樣本)；

d）當滿足一定收斂條件時，則算法終止；如果條件不滿足則回到步驟 b)。

可以看出傳統(tǒng)k均值其實是一種特殊的FCM，即限制了隸屬度為 0或 1。

1.3 改進模糊k均值聚類

傳統(tǒng)的模糊k均值聚類對噪聲點敏感。這是由于其對隸屬度進行了概率歸一化的限制，使得隸屬度是相對的，而不是絕對的。比如，如果有兩個點A和B，A和B均和兩個類的距離相等。不同的是，A到兩個類中心的距離較小，而B到兩個類中心的距離很大。傳統(tǒng)的模糊k均值不能區(qū)分這兩種情況的不同，都會給A和B賦予0.5的各類隸屬度。為此，目前有許多針對傳統(tǒng)模糊k均值聚類的改進算法([8,9])，如噪聲模糊k均值算法([10])。這種算法在原來的各個類的基礎(chǔ)上，增加了噪聲類。設(shè)定了一個距離閾值t，當樣本到各個類中心的距離都大于t時，則將該樣本歸為噪聲類，算法如下。

a）初始化k個類中心，設(shè)定噪聲類閾值t；

b）計算每個對象與這些類中心點的距離；并根據(jù)這些距離值和閾值t計算樣本對各單類和噪聲類的隸屬度；

c）根據(jù)樣本的隸屬度重新計算每個子類的均值(找出中心樣本)；

d）當滿足一定收斂條件時，則算法終止；如果條件不滿足則回到步驟 b)。

1.4 EM算法

在統(tǒng)計計算中，EM模型中常用來計算在帶有不完全觀測的數(shù)據(jù)集下參數(shù)的最大似然估計。為了方便起見，我們將數(shù)據(jù)集W分為兩部分，可直接觀測部分Y和不可觀測(隱藏)部分Z。EM算法同樣經(jīng)過兩個步驟交替進行計算：

a）E步：利用對隱藏變量Z的當前估計值(在觀測Y下的條件期望)，計算完全(對數(shù))似然函數(shù) Q；

b）M步：最大化在E步上求得的似然函數(shù)Q來計算參數(shù)的值。

在M步上找到的參數(shù)估計值將被用于下一個E步計算中，這個過程不斷交替進行，直到算法收斂。

2 k均值和EM迭代過程的等價性

EM算法的迭代過程類似于爬山的過程。在E步，為基于完全數(shù)據(jù)的對數(shù)觀測似然函數(shù)確定一個下界函數(shù)。然后在M步，極大化這個下界函數(shù)。接下來就是一個循環(huán)往復的過程。在EM算法剛開始的時候，給定初始點，進行E步，觀測似然函數(shù)值并沒有提升，它只是找到了一個下界函數(shù)Q，并且這個函數(shù)和對數(shù)觀測似然函數(shù)在初始點的值相等。在極大化之后，我們再計算期望，這時的E步才會提升觀測似然函數(shù)值。

E步是對不可觀測的隱藏變量進行猜測。這種猜測是在觀測樣本的基礎(chǔ)上進行的，即在觀測樣本和現(xiàn)有參數(shù)下求條件期望。如果以觀測樣本和現(xiàn)有的參數(shù)為猜測依據(jù)，那么期望就是最靠譜的猜測。所謂的靠譜，就是說在現(xiàn)行的參數(shù)下，目標函數(shù)和猜測函數(shù)Q的值相等，而且猜測函數(shù)在參數(shù)為其他值時也不會超過對應的目標函數(shù)。E步保證了這種猜測是目標函數(shù)的下界，所以M步求得的極大值依然沒有超過目標函數(shù)的最大值。在M步求得極大值后，參數(shù)進行了更新，所以也要將猜測根據(jù)新的參數(shù)進行更新?？梢哉f，下一次迭代的E步提升了上一次迭代M步的值。而這種提升的原因，有兩點：（1）基于上一次E步，猜測函數(shù)的值小于目標函數(shù)。（2）在進行新的E步之后，目標函數(shù)和新的猜測函數(shù)值相同，而新的猜測函數(shù)同樣是目標函數(shù)的下界。

再來看一下k均值的更新過程。k均值通過更新兩種變量來極小化目標函數(shù)，類中心和隸屬度。隸屬度，即類別標簽，相當于不可觀測的隱藏變量。而類中心是可觀測的。在已知觀測變量的條件下，首先猜樣本屬于哪一類。易知通過將樣本分到最近的中心所在的類，就可以實現(xiàn)目標函數(shù)在現(xiàn)有觀測條件下的極小化。所謂的條件期望，在這里其實就是根據(jù)各類幾何中心確定類標簽或隸屬度。接下來就要通過極小化的方法來確定類中心。因此，類中心的更新過程相當于EM中的M步，而隸屬度更新的過程相當于EM中的E步。

對于均值聚類來講，剛開始并不知道每個樣本對應的隱藏變量，即其類別標簽。剛開始的時候可以對類標簽進行一個隨機初始化，然后在類別已知的情況下，極大化目標函數(shù)。接下來發(fā)現(xiàn)會有更好的類標簽的指定辦法。如此往復，直到目標函數(shù)收斂。所以，聚類的目標函數(shù)相當于EM中觀測對數(shù)似然函數(shù)的角色。對于傳統(tǒng)k均值聚類來講，隱藏類別的指定方法比較特殊，屬于非此及彼的硬指派。而對于模糊均值聚類，類別的指派辦法是依賴隸屬度的。

以上的討論不限于傳統(tǒng)k均值聚類，對其各種改進算法，如噪聲k均值聚類同樣適用。

3 k均值聚類的實現(xiàn)

R語言是當前最為流利的一種統(tǒng)計分析語言，它包含一套完整的數(shù)據(jù)處理、計算和制圖軟件系統(tǒng)?，F(xiàn)在已經(jīng)有成熟的R包集成了聚類算法，包含k均值聚類，比如vegclust包。其中，vegclust函數(shù)提供了k均值和模糊k均值聚類的功能。但是，這個函數(shù)并沒有利用R矩陣化運算的特點，這就降低了程序的執(zhí)行效率。R語言作為一種解釋型編譯語言，顯式循環(huán)比較慢是其一個很大的缺點。雖然已經(jīng)有apply系列的函數(shù)來避免顯式循環(huán)，但是在很多情況下還是不能滿足需求。其實，R語言的一個顯著的、優(yōu)點是支持矩陣化運算。如果能用矩陣運算來代替顯式循環(huán)，將會大大提高程序的效率。比如，在隸屬度確定時，利用矩陣化運算的思想，可以通過矩陣乘積來實現(xiàn)。假設(shè)樣本距離矩陣為D,則隸屬度的計算過程為：

a）計算D的倒數(shù)的1/(m-1)次方，其中m為模糊化因子，計算結(jié)果記為S。

b）用S除以S和k維全1矩陣的矩陣乘積。

經(jīng)過上述兩個步驟，就得到了各個樣本的隸屬度。同樣的，可以設(shè)計更新樣本中心時的矩陣化方法。記隸屬度矩陣為U，中心更新算法如下。

a）計算U的m次方和樣本矩陣的矩陣乘積。

b）計算U的m次方和n*d維全1矩陣的矩陣乘積。其中n為樣本的個數(shù)，d為樣本的維數(shù)。

c）將上面兩個步驟得到的矩陣向量相除得到中心矩陣V。

噪聲k均值聚類算法的隸屬度更新可類似進行：

a）計算D的倒數(shù)的1/(m-1)次方，同樣將計算結(jié)果記為S。

b）用S除以S與k維全1矩陣的矩陣乘積和t的倒數(shù)的1/(m-1)次方的和。

增加的噪聲類對各個類中心的計算無影響，所以中心的更新過程和上面模糊k均值聚類是完全一樣的。有了隸屬度和中心更新的主程序，不同k均值聚類均可依下流程進行。

a）初始化k個類中心，指定需要的附加參數(shù)。

b）依如上介紹的隸屬度更新算法計算矩陣U。

c）依如上介紹的中心確定算法計算矩陣V。

d）判斷算法收斂條件，如不滿足收斂條件，返回b)。如滿足，則算法結(jié)束。

算法的收斂條件可以根據(jù)需要設(shè)計，可以為相鄰兩次迭代目標函數(shù)的值變化不大，或相鄰兩次迭代確定的類中心完全相同。

為了顯示矩陣化后的程序的優(yōu)勢，我們以Iris數(shù)據(jù)集為例，用vegclust和本文設(shè)計的算法FCM分別執(zhí)行模糊k均值聚類，將實驗以不同的隨機初始點重復進行1000次，比較系統(tǒng)運行的時間，結(jié)果如表1所示。

表1 運行時間對比

從上表可以看出，矩陣化運算可以使程序的運行時間大大縮短，這就極大地提高了算法的效率。尤其在海量數(shù)據(jù)的時代，更具有實際應用價值。

4 結(jié)論

本文討論了k均值聚類中包含的EM思想，并指出了兩個算法在迭代過程中的等價性。k均值中樣本隸屬度更新和類中心更新分別與EM算法中的E步和M步的等價，兩個不同領(lǐng)域的方法在思想上是相通的。同時，介紹了如何基于矩陣化運算進行k均值聚類的程序設(shè)計。并用數(shù)值實例證明了矩陣化算法可以使R程序的執(zhí)行效率大大提高。

［1］任江濤,孫婧昊,施瀟瀟,等.一種用于文本聚類的改進的k均值算法[J].計算機應用,2006,26(B06):73-75.

［2］王易循,趙勛杰.基于k均值聚類分割彩色圖像算法的改進[J].計算機應用與軟件,2010,27(8):127-130.

［3］王興偉,沈蘭蓀.基于改進的k均值聚類和數(shù)學形態(tài)學的彩色眼科圖像病灶分割[J].中國生物醫(yī)學工程學報,2002,21(5):443-448.

［4］楊建新,周獻中,葛銀茂.基于拉普拉斯圖譜和k均值的多社團發(fā)現(xiàn)方法[J].計算機工程,2008,34(12):178-180.

［5］胡艷維,秦拯,張忠志.基于模擬退火與k均值聚類的入侵檢測算法[J].計算機科學,2010,37(6):122-124.

［6］湯效琴,戴汝源.數(shù)據(jù)挖掘中聚類分析的技術(shù)方法[J].微計算機信息,2003,19(1):3-4.

［7］王愛平,張功營,劉方.EM算法研究與應用[J].計算機技術(shù)與發(fā)展,2009,19(9):108-110.

［8］傅德勝,周辰.基于密度的改進k均值算法及實現(xiàn)[J].計算機應用,2011,31(2):432-434.

［9］孔銳,張國宣,施澤生,等.基于核的 k-均值聚類[J].計算機工程,2004,30(11):12-13.

［10］謝志偉,王志明.基于上下文約束的噪聲模糊聚類算法[J].計算機工程與應用,2012,48(5):143-145.