景 源，郝金山

(遼寧大學 信息學院，遼寧 沈陽 110036)

0 引言

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

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

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

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

1 K-means算法

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

K-means算法步驟：

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

2)求每個數(shù)據(jù)點與初始聚類中心的距離.

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

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

5)設置聚類迭代上限，或者準則函數(shù).

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

2 K-means算法的改進

2.1 初始聚類中心的選擇

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

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

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

(1)

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

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

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

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

1)對θ={u，Y}賦初值，不同的類賦不同的初值.

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

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

(2)

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

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

先簡化公式參數(shù)的似然函數(shù)如下所示，求導過程中Q1i(z)是個常數(shù)可以被省略

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

則L1(x)求導可以簡化為R求導，分別對u1求導和Y1求導，當導數(shù)為零可得到，

(3)

(4)

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

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

2.2 距離公式

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

(5)

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

以下是k-means算法的改進具體流程：

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

2)在遞歸過程中采用EM算法計算出初始聚類中心，并用于計算出在第一次遞歸中的聚類計算.

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

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

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

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

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

3 仿真與實驗

3.1 實驗描述

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

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

3.2 實驗描述

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

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

表2 聚類的CA值

表3 運行時間(t/s)

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

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

4 總結(jié)

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