基于期望最大化的K-Means聚類(lèi)算法

景 源，郝金山

(遼寧大學(xué) 信息學(xué)院，遼寧 沈陽(yáng) 110036)

0 引言

在數(shù)據(jù)挖掘領(lǐng)域中，聚類(lèi)技術(shù)是應(yīng)用廣泛且十分重要的技術(shù).聚類(lèi)分析已經(jīng)應(yīng)用在各種方面，比如其在機(jī)器學(xué)習(xí)，文本分類(lèi)，圖像處理，語(yǔ)音處理，模式識(shí)別等領(lǐng)域.

常見(jiàn)的聚類(lèi)方法有模型方法，密度方法[1]，網(wǎng)格方法[2]，層次劃分方法[3]和劃分的方法.其中EM算法[4-10]屬于模型方法.K-means算法[11-17]屬于劃分的方法.在這些方法中最著名的就是kmeans方法，kmeans方法具有簡(jiǎn)單，快速，有效等諸多優(yōu)點(diǎn)，但它也有非常明顯的不足.Kmeans算法過(guò)于依賴(lài)于初始聚類(lèi)中心.

文獻(xiàn)[8]中，提出一種基于稀疏約束非負(fù)矩陣分解的kmeans聚類(lèi)方法，通過(guò)在在非負(fù)矩陣分解過(guò)程中對(duì)基矩陣列向量施加l1和l2范數(shù)稀疏約束，實(shí)現(xiàn)高維數(shù)據(jù)的低維表示，然后利用在低維數(shù)據(jù)聚類(lèi)中性能良好的kmeans算法對(duì)稀疏降維后的數(shù)據(jù)進(jìn)行聚類(lèi).該方法適合于高維數(shù)據(jù)，并有良好的性能.但缺點(diǎn)是需要消耗的時(shí)間較長(zhǎng).文獻(xiàn)[9]中先根據(jù)類(lèi)簇指標(biāo)確定需要聚類(lèi)的數(shù)k，之后采用基于密度的思想，首先將聚類(lèi)樣本分為核心點(diǎn)、邊界點(diǎn)和孤立點(diǎn)，之后排除孤立點(diǎn)和邊界點(diǎn)并取核心點(diǎn)的中心點(diǎn)作為k個(gè)聚類(lèi)中心后再進(jìn)行kmeans聚類(lèi).雖然算法比原始的kmeans算法準(zhǔn)確率得到提高，但同樣耗時(shí)較長(zhǎng)，而且在已知k值的情況下，有可能出現(xiàn)k值對(duì)不上的情況.文獻(xiàn)[10]通過(guò)定義的平均類(lèi)間最大相似度指標(biāo)值來(lái)確定最佳的k值，將所有數(shù)據(jù)點(diǎn)中密度較高的點(diǎn)作為備選聚類(lèi)中心，將備選點(diǎn)中密度最大的兩個(gè)點(diǎn)作為聚類(lèi)中心進(jìn)行初步聚類(lèi)計(jì)算并更新當(dāng)前聚類(lèi)中心.根據(jù)平均類(lèi)間最大相似度來(lái)決定是否添加新的聚類(lèi)中心，結(jié)果表明該算法可以有效的提高聚類(lèi)的精確性與穩(wěn)定性，而且還能在一定程度上縮短聚類(lèi)時(shí)間，但隨著數(shù)據(jù)量的增大，特別是對(duì)高維數(shù)據(jù)而言，這些優(yōu)勢(shì)會(huì)極大的減弱.

針對(duì)以上出現(xiàn)的問(wèn)題，本文提出一種新的初始化方法，用EM方法初始化k-means方法，代替?zhèn)鹘y(tǒng)意義上的隨機(jī)初始化，讓初始聚類(lèi)中心離最終的聚類(lèi)結(jié)果更近一些并且適合高維數(shù)據(jù).

1 K-means算法

經(jīng)典的k-means算法思想是隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)作為初始聚類(lèi)中心，然后根據(jù)一定的距離算法(歐式距離)迭代計(jì)算聚類(lèi)中心，每次計(jì)算類(lèi)內(nèi)平均值作為新的聚類(lèi)中心，直到滿(mǎn)足聚類(lèi)要求，最后返回k個(gè)聚類(lèi)中心和最終的蔟類(lèi).

K-means算法步驟：

1)從數(shù)據(jù)集A中隨機(jī)選取k個(gè)數(shù)據(jù)對(duì)象作為初始聚類(lèi)中心.

2)求每個(gè)數(shù)據(jù)點(diǎn)與初始聚類(lèi)中心的距離.

3)根據(jù)距離，將每個(gè)數(shù)據(jù)點(diǎn)分配到距離其最近的聚類(lèi)中心.

4)求每個(gè)類(lèi)內(nèi)平均值，作為每個(gè)蔟的新的聚類(lèi)中心.

5)設(shè)置聚類(lèi)迭代上限，或者準(zhǔn)則函數(shù).

6)判斷，如果滿(mǎn)足或者達(dá)到最大迭代次數(shù)，表示迭代結(jié)束，否則返回步驟2.

2 K-means算法的改進(jìn)

2.1 初始聚類(lèi)中心的選擇

針對(duì)k-means算法中，初始聚類(lèi)中心對(duì)最終聚類(lèi)結(jié)果影響較大，但初始聚類(lèi)中心又是隨機(jī)的，不確定性太大，對(duì)于這種問(wèn)題，把EM算法與k-means算法相結(jié)合，用EM算法來(lái)求解k-means算法的初始聚類(lèi)中心.

EM算法的好處在于它可以根據(jù)已知數(shù)據(jù)和數(shù)據(jù)分布模型得到每一個(gè)樣本屬于哪一個(gè)分布和模型分布的參數(shù).為了對(duì)高緯數(shù)據(jù)進(jìn)行聚類(lèi)，考慮到自然界中大部分?jǐn)?shù)據(jù)都符合高斯分布，所以這里采用的是多維高斯分布模型，因?yàn)檫@里用的是向量，所以需要考慮向量與向量之間的關(guān)系.

多維向量的高斯概率密度函數(shù)是：

(1)

假設(shè)要把數(shù)據(jù)分成k類(lèi)，每類(lèi)分別服從多維高斯分布.讓原數(shù)據(jù)以列向量的形式存在.

第t類(lèi)的高斯概率密度函數(shù)是：

EM算法中存在如下Jensen不等式：

隱含變量z即為所對(duì)應(yīng)的類(lèi)別，Qi是條件概率，在這里可以用概率密度函數(shù)代替，表示屬于對(duì)應(yīng)變量z的概率.隱含變量z即為所對(duì)應(yīng)的類(lèi)別就是要找到k-means初始聚類(lèi)的聚類(lèi)所對(duì)應(yīng)的種類(lèi).未知參數(shù)為θ={u，Y}，u為均值，Y為協(xié)方差矩陣，應(yīng)用的EM算法的具體流程如下：

1)對(duì)θ={u，Y}賦初值，不同的類(lèi)賦不同的初值.

2)根據(jù)θ的值求：

3)根據(jù)Qi的值確定分布的類(lèi)型，找到Qi最大的值所對(duì)應(yīng)的種類(lèi)c，若服從第一類(lèi)的分布模型，則把第一類(lèi)的概率密度函數(shù)代入，若服從第二類(lèi)的分布模型，則把第二類(lèi)的概率密度函數(shù)帶入.若k的值大于2，則找到Qi所對(duì)應(yīng)種類(lèi)的模型.

(2)

EM算法的E步：初始化θt或者根據(jù)更新后θt的求Qti代入Lt(x).

M步：讓Lt(x)最大化，即分別對(duì)Lt(x)求導(dǎo)，讓導(dǎo)數(shù)為零，如讓L1(x)分別對(duì)，Y1，u1求導(dǎo)數(shù)，讓導(dǎo)數(shù)為零，下面為具體的推導(dǎo)過(guò)程.

先簡(jiǎn)化公式參數(shù)的似然函數(shù)如下所示，求導(dǎo)過(guò)程中Q1i(z)是個(gè)常數(shù)可以被省略

n為維數(shù)，構(gòu)造公式R為：

則L1(x)求導(dǎo)可以簡(jiǎn)化為R求導(dǎo)，分別對(duì)u1求導(dǎo)和Y1求導(dǎo)，當(dāng)導(dǎo)數(shù)為零可得到，

(3)

(4)

根據(jù)公式(3)和公式(4)求得均值和協(xié)方差矩陣：

公式中的n1是指服從第1類(lèi)的數(shù)據(jù)的數(shù)量，如此就求出了第一類(lèi)概率模型參數(shù)的值，之后每一類(lèi)的概率模型參數(shù)的值同理可求，最后得到的參數(shù)值代入E步，依次在E步和M 步之間循環(huán)，直到參數(shù)不再變化為止，如此就求出了每個(gè)模型的參數(shù).知道了每個(gè)數(shù)據(jù)的隱含類(lèi)別Z，根據(jù)隱含類(lèi)別，將數(shù)據(jù)歸類(lèi)，求每個(gè)類(lèi)別的均值，作為k-means算法的初始值.這樣就是把EM算法用于k-means算法初始聚類(lèi)中心的選擇.

2.2 距離公式

一般k-means算法所采用的距離公式多為傳統(tǒng)的歐式距離，對(duì)于高維數(shù)據(jù)而言，歐式距離的性能收到限制，特別是不同維度的差異較大時(shí)，故本文采用一種新的公式作為距離算法，以?xún)蓚€(gè)列向量的比值為基礎(chǔ)，作為兩個(gè)數(shù)據(jù)的距離度量.

(5)

其中a和b可以看出分別為兩個(gè)維度為n的列向量，dab值越小表示距離越近.

以下是k-means算法的改進(jìn)具體流程：

1)從已有的數(shù)據(jù)集中選取一定量的數(shù)據(jù)進(jìn)行一次遞歸.

2)在遞歸過(guò)程中采用EM算法計(jì)算出初始聚類(lèi)中心，并用于計(jì)算出在第一次遞歸中的聚類(lèi)計(jì)算.

3)利用鄰近原則和提出的距離算法，根據(jù)距離的遠(yuǎn)近分配到就最近的簇中.

4)根據(jù)計(jì)算，得到每個(gè)簇中的平均值作為新的聚類(lèi)中心.

5)判斷聚類(lèi)函數(shù)是否收斂，如果收斂，則返回聚類(lèi)結(jié)果.若不收斂，則轉(zhuǎn)到步驟(3)，繼續(xù)計(jì)算，直到收斂為止.

6)把遞歸回的結(jié)果，作為全部數(shù)據(jù)的初始聚類(lèi)中心，以相同的原理利用步驟(3)至步驟(5)，并得到最終的聚類(lèi)結(jié)果并返回.

通過(guò)部分?jǐn)?shù)據(jù)遞歸EM算法，得到的聚類(lèi)結(jié)果作為真正的初始聚類(lèi)中心，從而讓初始聚類(lèi)中心離最終理想的聚類(lèi)結(jié)果更近一些，提升算法準(zhǔn)確性.

3 仿真與實(shí)驗(yàn)

3.1 實(shí)驗(yàn)描述

表1 數(shù)據(jù)集分布

為了驗(yàn)證算法的準(zhǔn)確性和穩(wěn)定性，本文從UCI數(shù)據(jù)集中選取Iris，wine，Ionosphere，Soybean，Sonar等5個(gè)經(jīng)典數(shù)據(jù)集進(jìn)行測(cè)試.UCI數(shù)據(jù)集是經(jīng)典的用于測(cè)試機(jī)器學(xué)習(xí)和數(shù)據(jù)挖據(jù)的數(shù)據(jù)集，其中的數(shù)據(jù)有明確的分類(lèi).關(guān)于分類(lèi)準(zhǔn)確率問(wèn)題上，在數(shù)據(jù)集上分別運(yùn)行k-means算法，NMFS-K算法[8]和本文算法各10次，每次迭代次數(shù)不超過(guò)100次，隨后取均值進(jìn)行比較，其中遞歸時(shí)取其中1/4的數(shù)據(jù).數(shù)據(jù)集的分布如表1所示.

3.2 實(shí)驗(yàn)描述

基于表1所示的UCI數(shù)據(jù)集，對(duì)k-means算法，NMFS-K算法和本文算法的聚類(lèi)結(jié)果進(jìn)行對(duì)比分析，用分類(lèi)準(zhǔn)確率對(duì)結(jié)果進(jìn)行評(píng)價(jià)，分類(lèi)準(zhǔn)確率按如下公式：

其中ai為每個(gè)類(lèi)中正確聚類(lèi)的數(shù)據(jù)個(gè)數(shù)，k為聚類(lèi)個(gè)數(shù)，n為數(shù)據(jù)總數(shù)，CA的值越高聚類(lèi)的效果越好，實(shí)驗(yàn)所得的CA值如表2所示：

表2 聚類(lèi)的CA值

表3 運(yùn)行時(shí)間(t/s)

從表2可以看出傳統(tǒng)算法相對(duì)于高維和數(shù)據(jù)量大的數(shù)據(jù)而言，聚類(lèi)的效果不是很好，NMFS-K算法相比于傳統(tǒng)的算法，除了在低維數(shù)據(jù)上表現(xiàn)不好外，其他相比于傳統(tǒng)算法要好一些，本文方法雖然同樣在低維數(shù)據(jù)表現(xiàn)不好，但在高維數(shù)據(jù)上要比前兩種方法要更好上一些.故本文方法比較適合于高維數(shù)據(jù).

為了從時(shí)間上對(duì)比分析算法的效率，記錄了各個(gè)數(shù)據(jù)集的運(yùn)行時(shí)間.如表3所示，本文方法相比于前兩種方法而言，需要消耗更多的時(shí)間.

4 總結(jié)

針對(duì)高維數(shù)據(jù)的數(shù)據(jù)集，提出了聚類(lèi)算法改進(jìn)，把EM算法和k-means算法相結(jié)合，使EM算法用于遞歸中來(lái)確定初始聚類(lèi)中心，讓初始聚類(lèi)中心離最終聚類(lèi)結(jié)果更近一些.并為了更好地提升算法的準(zhǔn)確性，提出一種新的距離算法.通過(guò)實(shí)驗(yàn)證明，提高了算法的準(zhǔn)確性，并且適合于高維的大數(shù)據(jù)量的處理，證明了算法的有效性，但是缺點(diǎn)是所需計(jì)算的時(shí)間延長(zhǎng)，需要更好的改進(jìn).