基于空間分布優(yōu)選初始聚類中心的改進(jìn)K-均值聚類算法

宋仁旺，蘇小杰，石 慧

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

隨著信息行業(yè)的爆炸式發(fā)展，數(shù)據(jù)已成為行各業(yè)重要的生產(chǎn)因素，同時(shí)也對(duì)海量數(shù)據(jù)的挖掘提出新的挑戰(zhàn)。信息爆炸產(chǎn)生的海量數(shù)據(jù)對(duì)從大量數(shù)據(jù)中挖掘有用信息提出挑戰(zhàn)[1-4]。數(shù)據(jù)的聚類是數(shù)據(jù)挖掘?qū)嵤┻^程中的核心技術(shù)[5-6]。MacQueen[7]為解決數(shù)據(jù)挖掘問題提出了一個(gè)局部搜索的算法——K-means聚類算法。該算法原理簡單、運(yùn)算高效、時(shí)間和空間復(fù)雜度較低，至今依然是工業(yè)和社會(huì)科學(xué)中最流行的算法[8]。但該K-means聚類效果對(duì)最初K個(gè)初始中心點(diǎn)的選取和離群值都非常敏感，當(dāng)用于海量數(shù)據(jù)聚類時(shí)，由于其迭代次數(shù)過多且迭代過程涉及多次文件系統(tǒng)的讀寫操作非常費(fèi)時(shí)[9-11]，所以有必要對(duì)K-means聚類算法初始聚類中心點(diǎn)的選取進(jìn)行改進(jìn)以減少聚類過程中的迭代次數(shù)，從而降低聚類所需的時(shí)間并提高聚類效果。

針對(duì)上述問題，學(xué)者從不同角度對(duì)K-means算法進(jìn)行了改進(jìn)。Arthur等[12]在K-means算法的基礎(chǔ)上對(duì)中心點(diǎn)的選擇進(jìn)行改進(jìn)，即基于每個(gè)數(shù)據(jù)點(diǎn)到已有中心點(diǎn)的距離采用線性概率選出下一個(gè)聚類中心點(diǎn)，簡單地說就是數(shù)據(jù)點(diǎn)離現(xiàn)有的中心點(diǎn)距離越遠(yuǎn)就越有可能被選為類簇中心點(diǎn)，該方法能有效解決初始聚類中心點(diǎn)敏感的問題，但是由于類簇中心點(diǎn)的選擇具有有序性，這使得算法無法并行擴(kuò)展，極大地限制了算法在大規(guī)模數(shù)據(jù)集上的應(yīng)用。K-medoids算法是在K-means聚類方法基礎(chǔ)演變而來，該算法的特點(diǎn)是選取的每個(gè)中心點(diǎn)都是樣本點(diǎn)，因此該方法能夠解決K-means算法對(duì)噪聲和離群值敏感問題，但是該算法時(shí)間復(fù)雜度高，不適合應(yīng)用于大批量數(shù)據(jù)集[13]。Goode[14]為了減少聚類的迭代過程提出了X-means算法，該算法利用K-means迭代和基于BIC(Bayesian information criterion)的停止規(guī)則確定聚類的最優(yōu)數(shù)目，但是該算法過程復(fù)雜，增加了算法復(fù)雜度，效果并不理想。

通過以上分析，可以發(fā)現(xiàn)現(xiàn)存對(duì)K-means算法改進(jìn)的文獻(xiàn)所提出的算法都是具有代價(jià)的。現(xiàn)擬在分析K-means聚類算法的基礎(chǔ)上不降低K-means算法的準(zhǔn)確性、高魯棒性等性能情況下，提高聚類算法的算法效率和高穩(wěn)定性。為此提出了一種針對(duì)海量數(shù)據(jù)集初始聚類中心點(diǎn)選擇的聚類算法。在該算法中，為了消除數(shù)據(jù)集中孤立的噪聲點(diǎn)對(duì)聚類效果的影響，采用冒泡排序法對(duì)數(shù)據(jù)集進(jìn)行排序，獲取數(shù)據(jù)集的各維中心值組成第一個(gè)初始聚類中心點(diǎn)，為保證所有的聚類中心點(diǎn)均勻地分布在數(shù)據(jù)集密度較大的空間上，余下候選初始聚類中心點(diǎn)的優(yōu)化選擇依據(jù)其與第一個(gè)初始聚類中心點(diǎn)的歐式距離，并且所有聚類中心點(diǎn)兩兩之間設(shè)置一定的距離間隔，以此減少聚類過程中的迭代次數(shù)和提高聚類算法效率。改進(jìn)后的K-means聚類算法能顯著減少聚類的迭代次數(shù)，降低噪聲對(duì)聚類效果的影響，提高算法效率。最后選取UCI(University of California, Irvine)中多個(gè)針對(duì)聚類算法的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，對(duì)比K-means、K-means++聚類算法驗(yàn)證本文算法的高效性和準(zhǔn)確性。

1 K-均值聚類算法理論

聚類通常又被稱為無監(jiān)督學(xué)習(xí)，屬于一種動(dòng)態(tài)算法。數(shù)據(jù)的聚類就是按照某個(gè)特定標(biāo)準(zhǔn)(如距離、密度)把一個(gè)集合分為互不相交的類簇，使得同一個(gè)類簇內(nèi)的對(duì)象的相似性盡可能大，同時(shí)不在同一個(gè)類簇中的對(duì)象的相似性盡可能地小[15-18]。根據(jù)分類對(duì)象和分析計(jì)算方法不同，聚類算法分為小數(shù)據(jù)聚類和大數(shù)據(jù)聚類兩種類型，其中小數(shù)據(jù)聚類包含傳統(tǒng)聚類和智能聚類算法，大數(shù)據(jù)聚類包含的算法分為并行聚類、分布式聚類和高維聚類[19]。

假設(shè)數(shù)據(jù)集X包含n個(gè)d維屬性的數(shù)據(jù)點(diǎn)，即X={x1,x2,…,xn},其中xi∈Rd。K-means聚類的目標(biāo)是將n個(gè)樣本點(diǎn)按照數(shù)據(jù)集間樣本的相似性劃分到指定的K個(gè)類簇中，每個(gè)樣本只屬于到其中一個(gè)中心點(diǎn)距離最小的類簇中。首先K-means聚類算法是隨機(jī)產(chǎn)生K個(gè)聚類中心點(diǎn){c1,c2,…,cn}，然后計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)到所有聚類中心的歐式距離，根據(jù)就近原則，把其余的數(shù)據(jù)點(diǎn)分配給距離最小的類簇中心點(diǎn)，最后通過計(jì)算每個(gè)數(shù)據(jù)點(diǎn)與其類簇中心點(diǎn)距離差的平方和來評(píng)價(jià)聚類的效果。

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

K-means聚類算法初始聚類中心點(diǎn)是隨機(jī)選取的，極有可能存在選取的初始聚類中心點(diǎn)是數(shù)據(jù)集邊緣的噪聲點(diǎn)或孤立點(diǎn)，或者選取的聚類中心點(diǎn)兩兩之間的空間距離十分接近,這可能增加聚類過程的迭代次數(shù)，影響聚類效果。鑒于此，現(xiàn)提出一種改進(jìn)的K-means聚類算法，該算法的核心思想是初始聚類中心點(diǎn)盡可能均勻分布在數(shù)據(jù)集密度較大的一定范圍內(nèi)且各個(gè)中心點(diǎn)的距離足夠大，同時(shí)應(yīng)避免一些極端距離的點(diǎn)被選為中心點(diǎn)，具體步驟如下。

Step1設(shè)置K值，令M=K，掃描數(shù)據(jù)集，采用冒泡排序法把數(shù)據(jù)集各維從小到大進(jìn)行排序，排序后的數(shù)據(jù)集為X1。

Step2篩選數(shù)據(jù)的各維中心值作為第一個(gè)聚類中心點(diǎn)c1，保證第一個(gè)聚類中心點(diǎn)位于數(shù)據(jù)集空間的中心，即

c1=X1,p,p=[n/2]

(1)

式(1)中：[]表示取整運(yùn)算；X1,p表示排序后數(shù)據(jù)集的第p個(gè)樣本。

Step3對(duì)數(shù)據(jù)集中的每個(gè)點(diǎn)xi，通過式(2)計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)到已有聚類中心的歐式距離，即

(2)

式(2)中:xi表示第i個(gè)樣本；cj表示第j個(gè)類簇中心點(diǎn);xit表示第i個(gè)樣本的第t維屬性;cjt表示第j個(gè)聚類中心點(diǎn)的第t維屬性。通過式(2)計(jì)算任意點(diǎn)xi到已有聚類中心點(diǎn)的距離，即

D(xi)=[d(xi,c1),d(xi,c2),…,d(xi,cj)]

(3)

其余k-1個(gè)聚類中心點(diǎn)要滿足以下兩點(diǎn)：

(1)候選的聚類中心點(diǎn)應(yīng)排除在距離指定中心點(diǎn)0.8d之外和0.2d之內(nèi)的空間上(d代表所有數(shù)據(jù)點(diǎn)距第一個(gè)初始聚類中心點(diǎn)的最遠(yuǎn)歐式距離)，即剩下k-1個(gè)聚類中心點(diǎn)分布在數(shù)據(jù)集數(shù)據(jù)密度較大的空間中。

(2)兩兩中心點(diǎn)之間設(shè)置一定的間隔，本文選取間隔為3d/M。

Step5重復(fù)Step 3、Step 4，直到其余k-1個(gè)聚類中心點(diǎn)全選擇出來。

Step6通過式(4)分別計(jì)算數(shù)據(jù)集中的所有數(shù)據(jù)點(diǎn)到K個(gè)類簇中心點(diǎn)的歐氏距離，并依據(jù)式(4)將所有數(shù)據(jù)點(diǎn)分別分配到距離中心點(diǎn)最近的類簇中；如果

(4)

則x∈ci，從而得到k個(gè)類簇{S1,S2,…,Sk}。

Step7在Step 6的基礎(chǔ)上，通過式(5)重新計(jì)算K個(gè)類簇各自的中心點(diǎn)，計(jì)算方法是取類簇中所有元素各自維度的算術(shù)平均值，即

(5)

式(5)中：ni表示類簇Si中數(shù)據(jù)點(diǎn)的個(gè)數(shù)，且xj∈Si。Step8將K個(gè)類簇新的中心點(diǎn)與原有中心點(diǎn)進(jìn)行比較，相鄰最小化平方誤差和不再變化或迭代次數(shù)達(dá)到設(shè)定的最大值，則輸出聚類結(jié)果。假設(shè)數(shù)據(jù)集劃分為{S1,S2,…,Sk}，最終的最佳聚類目標(biāo)是最小化誤差平方和(sum of the squared errors，SSE)，即

(6)

總誤差平方和越小，聚類效果越好。

本文聚類算法流程如圖1所示。

圖1 本文聚類算法流程圖

3 實(shí)驗(yàn)驗(yàn)證

為了說明本文改進(jìn)的算法在減少迭代次數(shù)的同時(shí)不降低聚類的效果，算法高效。本文數(shù)據(jù)樣本包含兩部分：一部分是UCI中針對(duì)驗(yàn)證聚類算法的Iris、Wilt、Avila、letter-recognition、Activity-recognition數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，另一部分?jǐn)?shù)據(jù)集是由MATLAB中標(biāo)準(zhǔn)正態(tài)分布函數(shù)產(chǎn)生的矩陣，并選取了K-means、K-means++聚類算法與本文提出的算法進(jìn)行了對(duì)比實(shí)驗(yàn)，檢驗(yàn)算法效果。

實(shí)驗(yàn)環(huán)境:LenovoG40-80筆記本、Windows10專業(yè)版、系統(tǒng)類型為64位操作系統(tǒng)、基于X64的處理器、Intel(R)Core(TM)i5-5200U CPU @ 2.20 GHz、4 G RAM、MATLABR2018a 集成開發(fā)環(huán)境。

為了能直觀地顯示本文算法的聚類效果，首先在由MATLAB中標(biāo)準(zhǔn)正態(tài)分布函數(shù)產(chǎn)生的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)分別在K-means、K-means++和本文提出的聚類算法上進(jìn)行。該二維數(shù)據(jù)集分為5個(gè)類簇，共400個(gè)數(shù)據(jù)點(diǎn)。聚類結(jié)果如圖2～圖5所示。

圖2 K-means算法聚類效果

圖2中五個(gè)黑色標(biāo)記是K-means算法聚類的最終類簇中心點(diǎn)，坐標(biāo)分別是(0.618,-1.749)(-0.388,-0.101)(-1.617,-1.288)(1.722,-0.075)(0.794,1.654)。

圖3中五個(gè)黑色標(biāo)記是K-means++算法聚類的最終類簇中心點(diǎn)，坐標(biāo)分別為(0.597,-1.718)(-0.677,-0.260)(-1.769,-1.518)(1.569,-0.088)(0.780,1.618)。

圖3 K-means++算法聚類效果圖

圖4中紅色的標(biāo)記點(diǎn)是本文算法通過采用冒泡排序法自動(dòng)選取數(shù)據(jù)集的各維中心點(diǎn)作為第一個(gè)初始聚類中心點(diǎn)，其余四個(gè)黑色的標(biāo)記點(diǎn)是另外四個(gè)初始聚類中心點(diǎn)，坐標(biāo)分別為(0.141,-0.453)(1.382,1.879)(2.081,-0.774)(-1.743,-0.294)(0.255,-2.326)，每個(gè)藍(lán)色圓圈表示一個(gè)數(shù)據(jù)點(diǎn)，可以直觀看出本文算法選取的五個(gè)初始的聚類中心點(diǎn)可以離散均勻分布在數(shù)據(jù)集中數(shù)據(jù)點(diǎn)密度相對(duì)大的空間上。

圖4 本文算法產(chǎn)生的初始簇心

在圖5中五個(gè)黑色標(biāo)記是本文算法聚類的最終類簇中心點(diǎn)，坐標(biāo)分別為(-0.294,-0.046)(0.991,1.591)(-1.722,-1.047)(1.629,-0.478)(0.132,-1.909)，相同顏色的點(diǎn)屬于同一類簇。

圖5 本文算法產(chǎn)生的聚類效果圖

通過對(duì)比圖2～圖5的類簇中心點(diǎn)坐標(biāo)可以得出，三個(gè)聚類算法的最終類簇中心點(diǎn)的坐標(biāo)的比較接近，而本文聚類算法自動(dòng)選擇的5個(gè)初始聚類中心點(diǎn)的坐標(biāo)與最終形成的類簇中心點(diǎn)坐標(biāo)的位置十分接近，由此可以直觀地看出本文算法可以達(dá)到減少聚類過程中的迭代次數(shù)，提高聚類算法效率預(yù)期效果。

通過分析表1可以發(fā)現(xiàn)：和經(jīng)典的聚類算法相比較，本文提出的改進(jìn)的聚類算法的迭代次數(shù)為10次，而K-means、K-means++的迭代次數(shù)分別為19和17次，可以看出本文算法在聚類過程中的迭代次數(shù)顯著的減少，這由于本文算法選擇的初始類簇中心點(diǎn)能夠離散均勻地分布在數(shù)據(jù)集中數(shù)據(jù)點(diǎn)相對(duì)集中的地方，即提高了算法的運(yùn)行效率；通過對(duì)比三個(gè)聚類算法的運(yùn)行時(shí)間，可以看出K-means++算法的聚類時(shí)間較大，而K-means算法和本文算法的時(shí)間相差不大，主要時(shí)由于K-means++算法選擇K個(gè)初始聚類中心點(diǎn)時(shí)同時(shí)采用串行的方式比較消耗時(shí)間；通過對(duì)比三個(gè)算法的誤差平方和可以發(fā)現(xiàn)，本文算法的類簇內(nèi)的誤差平方和相比于其他算法也有所下降，即本文算法的聚類效果優(yōu)于K-means、K-means++聚類算法。主要原因是，傳統(tǒng)的聚類算法的中心點(diǎn)是在全數(shù)據(jù)集上隨機(jī)選取的，那么選取的中心點(diǎn)可能處于極端的孤立點(diǎn)或兩兩中心點(diǎn)之間間隔過大或過小，而本文提出的改進(jìn)聚類算法所選擇的初始中心點(diǎn)是均勻地分布在數(shù)據(jù)點(diǎn)密度較大的空間中，這些初始中心點(diǎn)能非常好地貼近最終的聚類中心點(diǎn)。

表1 針對(duì)人造二維數(shù)據(jù)集各算法的聚類性能結(jié)果

為了進(jìn)一步檢驗(yàn)本文算法在多維數(shù)據(jù)集上的聚類效果，驗(yàn)證算法在聚類過程中減少迭代次數(shù)和提高聚類算法效率，現(xiàn)選取UCI中多個(gè)針對(duì)聚類算法的數(shù)據(jù)集進(jìn)行聚類對(duì)比實(shí)驗(yàn)。

數(shù)據(jù)預(yù)處理:由于UCI中的數(shù)據(jù)集中有一些原始數(shù)據(jù)中帶有數(shù)據(jù)的類別標(biāo)識(shí)字母或數(shù)字，而我們進(jìn)行實(shí)驗(yàn)時(shí)是不需要將類別標(biāo)識(shí)放入算法中，所以在進(jìn)行實(shí)驗(yàn)之前需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，去掉數(shù)據(jù)集的標(biāo)識(shí)部分。其中Activity-recognition數(shù)據(jù)集的采集包含房間1和房間2兩個(gè)數(shù)據(jù)集，本文選取的房間1采集的數(shù)據(jù)集。實(shí)驗(yàn)數(shù)據(jù)集性質(zhì)如表2所示。

表2 UCI中針對(duì)聚類數(shù)據(jù)集的性質(zhì)

為了使本文選擇的數(shù)據(jù)集具有多樣性、代表性、說服力。本文選擇的數(shù)據(jù)集維數(shù)最低的是4維，最高的是16維，樣本數(shù)最少的是150個(gè)，最大的54 568，數(shù)據(jù)集的分類數(shù)也各不等，總的數(shù)據(jù)點(diǎn)最高的數(shù)據(jù)集Activity-recognition達(dá)436 544個(gè)，Iris數(shù)據(jù)集的最少數(shù)據(jù)點(diǎn)也達(dá)到600個(gè)。

通過對(duì)表3的分析可得：針對(duì)Iris、Wilt、Avila、letter-recognition、Activity-recognition多個(gè)不同的多維數(shù)據(jù)集的聚類，本文提出的聚類算法的迭代次數(shù)均小于K-means、K-means++聚類算法，特別是針對(duì)Iris、Activity-recognition數(shù)據(jù)集的迭代次數(shù)，K-means、K-means++算法的迭代次數(shù)均2倍于本文算法的迭代次數(shù)，針對(duì)letter-recognition,Avila數(shù)據(jù)集的迭代次數(shù)，K-means算法的迭代次數(shù)也接近與本文算法迭代次數(shù)的2倍。由上可以看出本文的算法在迭代次數(shù)方面的性能較優(yōu)于K-means、K-means++聚類算法，特別是相對(duì)于K-means算法，本文算法更勝一籌。

表3 各算法迭代次數(shù)

在誤差平方和方面，通過對(duì)表4的分析可得：三個(gè)聚類算法針對(duì)Iris、Wilt、Activity-recognition數(shù)據(jù)集的誤差平方和十分接近，聚類的效果相差不大，本文算法針對(duì)letter-recognition數(shù)據(jù)集的聚類效果略優(yōu)于K-means、K-means++算法，而K-means算法針對(duì) Avila數(shù)據(jù)集的誤差平方和卻遠(yuǎn)遠(yuǎn)高于K-means++和本文算法，主要原因是K-means算法選取了數(shù)據(jù)集邊緣的噪聲點(diǎn)為類簇中心，使算法陷入局部最優(yōu)的狀態(tài)，影響了聚類效果。

表4 各算法的誤差平方和

通過表5對(duì)比三個(gè)聚類算法針對(duì)相同數(shù)據(jù)集所需的時(shí)間，可以發(fā)現(xiàn)，K-means算法的時(shí)間略低于K-means++算法，主要是由于K-means算法選取K個(gè)聚類中心點(diǎn)采用并行算法，而K-means++選用效率較低的串行算法，本文算法所用的時(shí)間最短，主要是本文算法的迭代次數(shù)顯著低于K-means、K-means++算法，從而縮短程序運(yùn)行的時(shí)間，進(jìn)而證明本文算法達(dá)到了減少聚類過程中的迭代次數(shù)和提高聚類算法效率的預(yù)期效果。

表5 各個(gè)算法的時(shí)間

針對(duì)驗(yàn)證本文算法在實(shí)際實(shí)驗(yàn)中的應(yīng)用，本文又選取了西安交通大學(xué)XJTU-SY滾動(dòng)軸承加速壽命試驗(yàn)數(shù)據(jù)中工況為1的第五個(gè)軸承的數(shù)據(jù)進(jìn)行聚類，該數(shù)據(jù)集包含垂直和水平振動(dòng)信號(hào)，共有1 638 400個(gè)數(shù)據(jù)點(diǎn)，失效位置分為內(nèi)圈和外圈兩類[20]。該數(shù)據(jù)集的具體聚類效果如表6所示。

通過對(duì)表6的分析可以看出，本文算法對(duì)滾動(dòng)軸承加速壽命試驗(yàn)數(shù)據(jù)實(shí)際的應(yīng)用效果中，迭代次數(shù)，算法運(yùn)行的時(shí)間均小于K-means、K-means++算法，即本文算法整體實(shí)驗(yàn)效果優(yōu)于K-means，K-means++算法。

表6 針對(duì)XJTU-SY滾動(dòng)軸承加速壽命試驗(yàn)數(shù)據(jù)集各算法的聚類性能結(jié)果

4 結(jié)論

K-means算法是一種原理十分簡單和應(yīng)用十分廣泛的聚類算法，但是它存在著初始中心點(diǎn)不穩(wěn)定的問題。本文在分析了經(jīng)典的K-means聚類算法的基礎(chǔ)上，對(duì)傳統(tǒng)的聚類算法進(jìn)行了改進(jìn)，本文算法基于人工數(shù)據(jù)集和UCI數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果與經(jīng)典的聚類算法結(jié)果相比較表明，本文算法的迭代次數(shù)可以降低50%，甚至更高，所需的時(shí)間也顯著降低了10%，不僅解決初始中心點(diǎn)不穩(wěn)定對(duì)聚類效果帶來的影響，還改善了聚類效率，效果十分顯著。在下一步的工作中，針對(duì)一些數(shù)據(jù)波動(dòng)范圍較大的數(shù)據(jù)集，考慮在本文的算法中加入數(shù)據(jù)的預(yù)處理，如歸一化的處理等，此外對(duì)初始聚類中心點(diǎn)的限制空間可以進(jìn)一步進(jìn)行優(yōu)化。