楊 柳

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

0 引言

隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)對(duì)社會(huì)生產(chǎn)與生活中諸多領(lǐng)域的影響越來(lái)越突出，大量的數(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ù)是指從大量、無(wú)規(guī)則、有噪聲數(shù)據(jù)中挖掘出有價(jià)值的信息。聚類算法是數(shù)據(jù)挖掘的重要組成部分，是將數(shù)據(jù)以無(wú)監(jiān)督方法，根據(jù)數(shù)據(jù)的特征劃分成多個(gè)簇，數(shù)據(jù)聚類分析是對(duì)數(shù)據(jù)進(jìn)一步處理的基礎(chǔ)。常見的聚類的方法包括層次方法、劃分方法、網(wǎng)格方法、密度方法、模型方法[1]。

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

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

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

(1)

聚類問(wèn)題的基本流程是，首先提取對(duì)象特征，判斷特征之間的相似程度。然后選取合適的聚類算法進(jìn)行聚類，最后進(jìn)行結(jié)果驗(yàn)證。聚類分析是在無(wú)先驗(yàn)知識(shí)的前提下進(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ù)通常用來(lái)評(píng)價(jià)聚類質(zhì)量，恰當(dāng)?shù)臏?zhǔn)則函數(shù)能夠有效促使相似度大的數(shù)據(jù)分配到同一個(gè)簇中，相似度低的數(shù)據(jù)分配到不同的簇。聚類算法中常見的準(zhǔn)則函數(shù)包括誤差平方和準(zhǔn)則、加權(quán)平均平方距離和及類間距離和準(zhǔn)則等，其中誤差平方和準(zhǔn)則Jc表示為：

(3)

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

(4)

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

2 K-means聚類算法

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

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

3 K-means算法的具體流程

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

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

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

4)計(jì)算每個(gè)簇的平均值，并作為新的中心點(diǎn)，參考公式(4)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 聚類個(gè)數(shù)對(duì)聚類性能的影響

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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