楊 柳

(西安電子工程研究所 西安 710100)

0 引言

隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)對社會生產(chǎn)與生活中諸多領(lǐng)域的影響越來越突出，大量的數(shù)據(jù)應(yīng)用于軍事及民用領(lǐng)域中，數(shù)據(jù)與生產(chǎn)生活的關(guān)系愈發(fā)緊密。如何從海量數(shù)據(jù)中提煉出有用的信息使其更好地服務(wù)生活，成為當(dāng)前面臨的難題。因此，數(shù)據(jù)挖掘技術(shù)在各行各業(yè)得到迅速地發(fā)展。數(shù)據(jù)挖掘技術(shù)是指從大量、無規(guī)則、有噪聲數(shù)據(jù)中挖掘出有價值的信息。聚類算法是數(shù)據(jù)挖掘的重要組成部分，是將數(shù)據(jù)以無監(jiān)督方法，根據(jù)數(shù)據(jù)的特征劃分成多個簇，數(shù)據(jù)聚類分析是對數(shù)據(jù)進(jìn)一步處理的基礎(chǔ)。常見的聚類的方法包括層次方法、劃分方法、網(wǎng)格方法、密度方法、模型方法[1]。

K-means聚類算法屬于劃分方法，是一種經(jīng)典的聚類算法，具有簡潔易懂、快速有效等優(yōu)勢，近年來受到廣泛關(guān)注。本文介紹了K-means算法的原理和實現(xiàn)過程，分析了K-means聚類算法的性能以及不同因子對K-means聚類算法的影響機理，為無監(jiān)督聚類過程的設(shè)計與應(yīng)用提供了理論指導(dǎo)。

1 數(shù)據(jù)聚類問題概述

聚類是指將數(shù)據(jù)集分成若干個不同的簇，同一簇內(nèi)的數(shù)據(jù)相似度盡可能大，不同簇的相似度盡可能小。假設(shè)數(shù)據(jù)集A，A={a1,a2…aN}，其中N代表數(shù)據(jù)集中數(shù)據(jù)對象個數(shù)。聚類是把A中N個數(shù)據(jù)對象劃分成k個簇{C1,C2…Ci…Ck}，Ci表示第i個簇。聚類后的結(jié)果集表示為X[2]：

(1)

聚類問題的基本流程是，首先提取對象特征，判斷特征之間的相似程度。然后選取合適的聚類算法進(jìn)行聚類，最后進(jìn)行結(jié)果驗證。聚類分析是在無先驗知識的前提下進(jìn)行聚類，在沒有訓(xùn)練集條件下以數(shù)據(jù)之間的相似度差異將數(shù)據(jù)劃分成若干簇。數(shù)據(jù)差異性一般取決于數(shù)據(jù)之間的某種距離，依據(jù)數(shù)據(jù)的性質(zhì)可以采用不同的距離，常用的歐式距離表示如下：

d(ai,aj)=

(2)

其中d(ai,aj)表示數(shù)據(jù)ai和aj之間的歐式距離，p表示數(shù)據(jù)ai的維度。

準(zhǔn)則函數(shù)通常用來評價聚類質(zhì)量，恰當(dāng)?shù)臏?zhǔn)則函數(shù)能夠有效促使相似度大的數(shù)據(jù)分配到同一個簇中，相似度低的數(shù)據(jù)分配到不同的簇。聚類算法中常見的準(zhǔn)則函數(shù)包括誤差平方和準(zhǔn)則、加權(quán)平均平方距離和及類間距離和準(zhǔn)則等，其中誤差平方和準(zhǔn)則Jc表示為：

(3)

式中nj是類Cj中對象的個數(shù)，mj類Cj的平均值，定義為

(4)

Jc可以用來描述N個數(shù)據(jù)對象需要劃分成k個類時，所產(chǎn)生的總的誤差平方和。Jc越大說明總的誤差平方和越大，表示聚類效果不好，所以應(yīng)讓其值盡可能小。當(dāng)各類樣本比較密集且樣本數(shù)目懸殊不大時使用誤差平方和準(zhǔn)則較合適。

2 K-means聚類算法

基于劃分方法的聚類算法是將數(shù)據(jù)點的中心作為簇的質(zhì)心，根據(jù)數(shù)據(jù)之間的相似性度為標(biāo)準(zhǔn)，使同一個簇內(nèi)數(shù)據(jù)盡可能相似。劃分方法首先任意分配初始聚類，然后不斷地迭代改變每一次聚類分結(jié)果，但是要求每一迭代的聚類效果要優(yōu)于上一次。劃分方法運行速度快，原理簡單，容易實現(xiàn)。K-means聚類算法是基于劃分方法的一種典型代表[2-4]。

K-means是一種動態(tài)迭代聚類算法，其中K表示類別(簇個數(shù))，Means表示均值。K-Means利用數(shù)據(jù)點均值進(jìn)行聚類。K-means算法開始執(zhí)行之前需要給定參數(shù)K，確定數(shù)據(jù)集中簇的個數(shù)。然后確定K個類的質(zhì)心，一般隨機選取K個數(shù)據(jù)作為簇的初始質(zhì)心。接著執(zhí)行數(shù)據(jù)聚類進(jìn)程，計算剩余數(shù)據(jù)點到初始簇質(zhì)點的相似程度，該相似程度可以使用距離或其他數(shù)據(jù)屬性特征，根據(jù)相似程度分配數(shù)據(jù)點到距離最近的簇中，接著重新計算當(dāng)前簇中的所有數(shù)據(jù)點的均值，并依此均值作為簇的新質(zhì)心，重復(fù)計算每個數(shù)據(jù)點到當(dāng)前簇質(zhì)心的距離，直到聚類中元素不再改變或是準(zhǔn)則函數(shù)收斂到某一個值，算法結(jié)束迭代。

3 K-means算法的具體流程

1)在所有數(shù)據(jù)樣本中隨機選取K個數(shù)據(jù)對象作為初始聚類中心，c1,c2…ck；

2)遍歷所有數(shù)據(jù)，計算每個數(shù)據(jù)點相對各個聚類中心的歐氏距離d(ai,cj)(1≤i≤N,1≤j≤K)；

3)根據(jù)距離d(ai,cj)，將每個數(shù)據(jù)劃分到距離最近的中心點所屬類中；

4)計算每個簇的平均值，并作為新的中心點，參考公式(4)；

5)重復(fù)步驟2)～ 4)，直至準(zhǔn)則函數(shù)收斂，或執(zhí)行了足夠多的迭代。

4 聚類初始質(zhì)心對聚類的影響

在K-means算法中，動態(tài)迭代依賴于隨機選取的K個初始聚類質(zhì)心，算法每一次聚類結(jié)果都不相同。當(dāng)K個質(zhì)心分布在數(shù)據(jù)點集的各個簇中時，聚類效果良好。當(dāng)某個簇中包含兩個聚類質(zhì)心，且簇間離較遠(yuǎn)時，就會導(dǎo)致簇的分裂以及另外兩個簇的錯誤合并，聚類效果較差。

針對K-means聚類算法中隨機選取初始質(zhì)心的導(dǎo)致聚類質(zhì)量不穩(wěn)定的問題， K-means++算法對初始聚類中心進(jìn)行了修正。K-means++算法與K-means算法都采用動態(tài)迭代的思想，主要改進(jìn)是如何初始選取K個初始聚類質(zhì)心。K-means++算法選取初始聚類中心時，假設(shè)當(dāng)前已選取了n個初始聚類中心(0

K-means聚類算法的選擇初始質(zhì)心的流程如下：

1)從數(shù)據(jù)點集中選取一個數(shù)據(jù)點作為初始聚類中心；

2)計算每個數(shù)據(jù)與當(dāng)前已有聚類中心之間的最短距離D(i)；

3)選擇新的聚類中心，D(i)較大者成為聚類中心的概率越大；

4)重復(fù)2)和3)，直到選擇出K個聚類中心。

其中，步驟3)的具體實施方法是：

①累加每個數(shù)據(jù)點與距離最近的聚類中心點距離，累加和表示為sum(D(i))；

②在0到sum(D(i))之間取一個隨機值R，然后循環(huán)計算R=R-D(i)(i=i+1)，直到R≤0。此時的數(shù)據(jù)集A中的第i個數(shù)據(jù)點即為下一個聚類中心。

為了說明初始聚類質(zhì)心對聚類結(jié)果的影響，本文隨機產(chǎn)生了一組數(shù)據(jù)點集，分別采用K-means算法和K-means++算法進(jìn)行聚類。以數(shù)據(jù)點之間的歐式距離為標(biāo)準(zhǔn)，采用誤差平方和為準(zhǔn)則函數(shù)。數(shù)據(jù)點集個數(shù)N=800，聚類個數(shù)K=6。

圖1 K-means算法聚類結(jié)果-隨機初始質(zhì)心(a)

圖2 K-means算法聚類結(jié)果-隨機初始質(zhì)心(b)

圖1和圖2給出了采用隨機初始質(zhì)心時聚類結(jié)果，其中(a)和(b)代表不同的隨機值。對比圖1和圖2可以明顯地看出，當(dāng)給定不同的初始聚類質(zhì)心時，得到的聚類結(jié)果也不盡相同，且聚類效果并不理想，尤其是圖1的聚類結(jié)果。 圖3給出了K-means++算法聚類結(jié)果，對比原始數(shù)據(jù)點的分布可以看出，K-means++算法聚類結(jié)果更為合理。

圖3 K-means++算法聚類結(jié)果

5 聚類個數(shù)對聚類性能的影響

K-means聚類算法要求算法開始之前必須確定聚類個數(shù) K值，該設(shè)置會對聚類結(jié)果產(chǎn)生一定的影響，同時也限制了其無監(jiān)督聚類算法的應(yīng)用。

一般化的聚類方法歸納為：

3)計算不同K值下的準(zhǔn)則函數(shù)輸出；

4)搜尋準(zhǔn)則函數(shù)的最大(最小值)對應(yīng)的K值及聚類結(jié)果，或者尋找準(zhǔn)則函數(shù)輸出轉(zhuǎn)折點對應(yīng)的K值及聚類結(jié)果。

圖4 K-means++算法聚類結(jié)果-K=4

有效性值根據(jù)實際應(yīng)用的不同可以采用不同的有效性值，常見的有效性函數(shù)可參考[6]。為了說明K值對聚類結(jié)果的影響，本文隨機產(chǎn)生了一組數(shù)據(jù)點集，采用K-means++算法進(jìn)行聚類。以數(shù)據(jù)點之間的歐式距離為標(biāo)準(zhǔn)，采用誤差平方和為準(zhǔn)則函數(shù)。數(shù)據(jù)點集個數(shù)N=800。

圖5 誤差平方和隨K值變化

從圖5給出的誤差平方和隨K值變化的趨勢可以看出，隨著聚類個數(shù)的不斷增加，整個聚類結(jié)果的誤差平方和不斷的減小。此時誤差平方和并不能完全反應(yīng)聚類的效果。同時，大范圍的搜索也會導(dǎo)致資源的浪費，一種可行的方法是觀察誤差平方和的變化趨勢，當(dāng)誤差平方和逐漸收斂時即可停止搜索過程。圖5中，當(dāng)K≥4時，誤差平方和逐漸收斂，故K=4是一個相對合理的聚類個數(shù)，對應(yīng)的聚類結(jié)果如圖4所示，與原始數(shù)據(jù)集分布可以看出，聚類結(jié)果基本有效的反映了原始數(shù)據(jù)集的分布特征。

6 結(jié)束語

本文首先回顧了聚類問題的相關(guān)理論基礎(chǔ)，然后針對基于劃分的聚類思想展開了討論，重點介紹了K-means和K-means++兩種聚類算法方法，并且討論了影響聚類性能的兩個重要問題，聚類初始質(zhì)心和聚類個數(shù)對聚類性能的影響，通過仿真研究驗證了本文的觀點，下一步工作將深入開展無監(jiān)督聚類算法在實際應(yīng)用中的優(yōu)化問題，包括算法收斂速度、相似度量函數(shù)選擇等。