K均值聚類算法的研究與優(yōu)化

陶 瑩，楊 鋒，劉 洋，戴 兵

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

數(shù)據(jù)挖掘在實(shí)際應(yīng)用中的主要任務(wù)之一是聚類分析，其是數(shù)據(jù)挖掘中一個(gè)很熱門的研究領(lǐng)域，同時(shí)與其他學(xué)科的研究方向有很大的交叉性[1]。聚類分析可以發(fā)現(xiàn)數(shù)據(jù)隱含的結(jié)構(gòu)，對(duì)數(shù)據(jù)進(jìn)行自動(dòng)歸類，從而得到數(shù)據(jù)的大致分布，在諸多領(lǐng)域?yàn)闆Q策提供支持信息[2]。

K均值聚類算法是聚類分析方法中一種基本的劃分式方法[3]。由于該算法簡便易懂，且計(jì)算速度較快，通常被作為大樣本聚類分析的首選算法[4]。

但是一般的K均值聚類算法初始聚類中心的選擇是隨機(jī)的，這樣會(huì)導(dǎo)致聚類結(jié)果的不穩(wěn)定。而且算法中k的值需要人為提前設(shè)定，k值設(shè)定的合理與否會(huì)直接影響聚類的效果[5]。此外，噪聲和離群點(diǎn)也會(huì)對(duì)聚類效果產(chǎn)生影響，使得聚類中心偏離主要數(shù)據(jù)區(qū)域[6]。因此，文中針對(duì)K均值聚類算法的隨機(jī)性較強(qiáng)的特點(diǎn)進(jìn)行改進(jìn)。

1 K均值聚類算法

1.1 算法基本思想

首先在整個(gè)數(shù)據(jù)集中任意選擇k個(gè)數(shù)據(jù)作為初始聚類中心，然后計(jì)算其他數(shù)據(jù)對(duì)象與k個(gè)聚類中心的距離，將數(shù)據(jù)對(duì)象劃分到距離最近的聚類中心所在的聚類域。所有數(shù)據(jù)劃分好后，重新計(jì)算k個(gè)聚類中每個(gè)聚類的全部數(shù)據(jù)對(duì)象的平均值，該平均值所在的數(shù)據(jù)點(diǎn)成為新的聚類中心。最后進(jìn)行多次迭代，直到連續(xù)兩次的聚類中心相同，說明此時(shí)數(shù)據(jù)對(duì)象類別劃分完畢，即得到k個(gè)聚類[7]。

1.2 算法評(píng)價(jià)準(zhǔn)則—誤差平方和

評(píng)價(jià)聚類效果，可以定義一個(gè)數(shù)據(jù)對(duì)象和其所在聚類域的目標(biāo)函數(shù)。通過目標(biāo)函數(shù)的取值情況評(píng)價(jià)聚類效果[8]。常用的聚類算法評(píng)價(jià)準(zhǔn)則是中心誤差的平方和，即：

(1)

其中，Xu是數(shù)據(jù)u的全部屬性值所構(gòu)成的矢量；k是聚類個(gè)數(shù)；m1,m2,…,mk是k個(gè)聚類中心對(duì)應(yīng)的矢量；cj是聚類中心為mj的聚類域。

聚類中心矢量mj表示為：

(2)

其中，Nj為聚類域cj中數(shù)據(jù)的個(gè)數(shù)。

式1中，目標(biāo)函數(shù)J代表k個(gè)聚類里的全部數(shù)據(jù)與其聚類中心mj之間的誤差平方和，值越小表明聚類中數(shù)據(jù)的集中性越好，即得到的聚類效果越好[9]。

1.3 算法局限性分析

(1)K均值聚類算法中的k值(待聚類簇的個(gè)數(shù))必須由用戶輸入。

k值必須是用戶最先確定，即分為多少個(gè)聚類。但是在一些實(shí)際情況下，合適的聚類數(shù)目k用戶也是未知的，在這種情況下，就需要運(yùn)用其他辦法來獲得到聚類的數(shù)目[10]。

(2)k個(gè)聚類中心的選擇是隨機(jī)的。

一般K均值聚類算法初始中心是隨機(jī)選擇的，然后進(jìn)行聚類和迭代，并最終收斂達(dá)到局部最優(yōu)結(jié)果[11]。因此，聚類結(jié)果對(duì)于初始中心有著嚴(yán)重的依賴，隨機(jī)選擇初始中心會(huì)造成聚類結(jié)果有很大的隨機(jī)性。

(3)K均值聚類算法對(duì)于噪聲和離群點(diǎn)數(shù)據(jù)非常敏感。

K均值聚類算法中每個(gè)聚類的中心都由每個(gè)聚類里所有數(shù)據(jù)求均值得到。當(dāng)有與其他數(shù)據(jù)不一致的數(shù)據(jù)或者差異比較大的數(shù)據(jù)時(shí)，計(jì)算出的聚類的中心易受干擾，偏離主要數(shù)據(jù)區(qū)域，影響聚類效果。因此，K均值聚類算法對(duì)數(shù)據(jù)中的噪聲和離群點(diǎn)非常敏感[12-13]。

2 全局K均值聚類算法

2.1 算法基本思想

全局K均值聚類算法從k=1的聚類開始，即先求出所有數(shù)據(jù)的聚類中心m。當(dāng)k=2時(shí)，將聚類中心m作為其中一個(gè)初始聚類中心，然后依次將數(shù)據(jù)集的每個(gè)點(diǎn)作為另一個(gè)聚類的初始中心，即運(yùn)行n次K均值聚類算法，計(jì)算誤差平方和J后，取值最小的點(diǎn)確定為第二個(gè)聚類中心，其中聚類后得到了新的聚類中心m1，m2。如果k=3,4,…,n，以此類推[14]。

全局K均值聚類算法最終得到了所有k(k

2.2 實(shí)驗(yàn)數(shù)據(jù)分析

當(dāng)k=2時(shí)，對(duì)40個(gè)數(shù)據(jù)重復(fù)使用K均值聚類算法得到4種不同的結(jié)果，如表1和圖1～4所示。根據(jù)誤差平方和評(píng)價(jià)準(zhǔn)則，最好的實(shí)驗(yàn)結(jié)果是實(shí)驗(yàn)一，其誤差平方和是112.92386462，但K均值聚類算法本身的不穩(wěn)定性使得每次產(chǎn)生不一樣的聚類結(jié)果，不一定是最優(yōu)的，甚至是很差的聚類結(jié)果。

表1 K均值聚類算法4次實(shí)驗(yàn)結(jié)果

圖1 K均值聚類結(jié)果一

圖2 K均值聚類結(jié)果二

圖3 K均值聚類結(jié)5三

圖4 K均值聚類結(jié)果四

下面使用改進(jìn)的K均值聚類算法即全局K均值聚類算法對(duì)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。當(dāng)k=1時(shí)，得到聚類中心m=[-0.20740458，0.0553751]，再用m分別和每一數(shù)據(jù)點(diǎn)為中心進(jìn)行K均值聚類算法。實(shí)驗(yàn)數(shù)據(jù)見表2。

表2 全局K均值聚類算法實(shí)驗(yàn)數(shù)據(jù)

全局K均值聚類的結(jié)果如圖5所示。

圖5 全局K均值算法聚類結(jié)果

與K均值聚類算法相比，全局K均值聚類算法的誤差平方和J=112.923113，改善了K均值聚類算法的隨機(jī)性所導(dǎo)致不理想結(jié)果的可能性。全局K均值聚類算法不受初始聚類中心位置的影響，并且通過一種確定有效的方法能夠最小化誤差平方和。

3 結(jié)束語

聚類算法發(fā)展到今天，已經(jīng)衍生出了多種算法。其中，經(jīng)典的K均值算法作為劃分聚類算法中最基礎(chǔ)的算法，由于其高效性和簡單性被廣泛應(yīng)用于各領(lǐng)域[16]。然而，K均值算法也有其固有的局限性，而很多針對(duì)K均值算法的改進(jìn)都極大地降低了算法本身的性能，這顯然是得不償失的[17]。對(duì)此，文中對(duì)K均值聚類算法進(jìn)行了改進(jìn)，降低了算法的不穩(wěn)定性，提高了聚類的有效性。

參考文獻(xiàn)：

[1] 周 濤,陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(12):100-111.

[2] 盤俊良,石躍祥,李娉婷.一種新的粒子群優(yōu)化聚類方法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(8):179-181.

[3] ABDEYAZDAN M.Data clustering based on hybrid K-harmonic means and modifier imperialist competitive algorithm[J].Journal of Supercomputing,2014,68(2):574-598.

[4] HUNG C H,CHIOU H M,YANG Weining,et al.Candidate groups search for K-harmonic means data clustering[J].Applied Mathematical Modelling,2013,37(24):10123-10128.

[5] 丁祥武,郭 濤,王 梅,等.一種大規(guī)模分類數(shù)據(jù)聚類算法及其并行實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展,2016,53(5):1063-1071.

[6] 萬 靜,張 義,何云斌,等.基于KD-樹和K-means動(dòng)態(tài)聚類方法研究[J].計(jì)算機(jī)應(yīng)用研究,2015,32(12):3590-3595.

[7] 羅軍鋒,鎖志海.一種基于密度的k-means聚類算法[J].微電子學(xué)與計(jì)算機(jī),2014,31(10):28-31.

[8] 王 濤,卿 鵬,魏 迪,等.基于聚類分析的進(jìn)程拓?fù)溆成鋬?yōu)化[J].計(jì)算機(jī)學(xué)報(bào),2015,38(5):1044-1055.

[9] SAHOO A K,ZUO M J,TIWARI M K,et al.A data clustering algorithm for stratified data partitioning in artificial neural network[J].Expert Systems with Applications,2012,39(8):7004-7014.

[10] 賈洪杰,丁世飛,史忠植.求解大規(guī)模譜聚類的近似加權(quán)核k-means算法[J].軟件學(xué)報(bào),2015,26(11):2836-2846.

[11] 朱建宇.K均值算法研究及其應(yīng)用[D].大連:大連理工大學(xué),2013.

[12] GüNG?R E,?ZMEN A.Distance and density based clustering algorithm using Gaussian kernel[J].Expert Systems with Applications,2017,69:10-20.

[13] 趙 麗.全局K-均值聚類算法研究與改進(jìn)[D].西安:西安電子科技大學(xué),2013.

[14] 雷小鋒,謝昆青,林 帆,等.一種基于K-Means局部最優(yōu)性的高效聚類算法[J].軟件學(xué)報(bào),2008,19(7):1683-1692.

[15] 張建萍.基于計(jì)算智能技術(shù)的聚類分析研究與應(yīng)用[D].濟(jì)南:山東師范大學(xué),2014.

[16] AHMAD A,HASHMI S.K-harmonic means type clustering algorithm for mixed datasets[J].Applied Soft Computing,2016,48:39-49.

[17] TU Chunhao,JIAO Shuo,KOH W Y,et al.Comparison of clustering algorithms on generalized propensity score in observational studies:a simulation study[J].Journal of Statistical Computation and Simulation,2013,83(12):2206-2218.