基于空間分布優選初始聚類中心的改進K-均值聚類算法

宋仁旺，蘇小杰，石 慧

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

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

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

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

1 K-均值聚類算法理論

聚類通常又被稱為無監督學習，屬于一種動態算法。數據的聚類就是按照某個特定標準(如距離、密度)把一個集合分為互不相交的類簇，使得同一個類簇內的對象的相似性盡可能大，同時不在同一個類簇中的對象的相似性盡可能地小[15-18]。根據分類對象和分析計算方法不同，聚類算法分為小數據聚類和大數據聚類兩種類型，其中小數據聚類包含傳統聚類和智能聚類算法，大數據聚類包含的算法分為并行聚類、分布式聚類和高維聚類[19]。

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

2 改進的K-means聚類算法

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

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

Step2篩選數據的各維中心值作為第一個聚類中心點c1，保證第一個聚類中心點位于數據集空間的中心，即

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

(1)

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

Step3對數據集中的每個點xi，通過式(2)計算每一個數據點到已有聚類中心的歐式距離，即

(2)

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

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

(3)

其余k-1個聚類中心點要滿足以下兩點：

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

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

Step5重復Step 3、Step 4，直到其余k-1個聚類中心點全選擇出來。

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

(4)

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

Step7在Step 6的基礎上，通過式(5)重新計算K個類簇各自的中心點，計算方法是取類簇中所有元素各自維度的算術平均值，即

(5)

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

(6)

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

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

圖1 本文聚類算法流程圖

3 實驗驗證

為了說明本文改進的算法在減少迭代次數的同時不降低聚類的效果，算法高效。本文數據樣本包含兩部分：一部分是UCI中針對驗證聚類算法的Iris、Wilt、Avila、letter-recognition、Activity-recognition數據集作為實驗數據集，另一部分數據集是由MATLAB中標準正態分布函數產生的矩陣，并選取了K-means、K-means++聚類算法與本文提出的算法進行了對比實驗，檢驗算法效果。

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

為了能直觀地顯示本文算法的聚類效果，首先在由MATLAB中標準正態分布函數產生的數據集上進行實驗，實驗分別在K-means、K-means++和本文提出的聚類算法上進行。該二維數據集分為5個類簇，共400個數據點。聚類結果如圖2～圖5所示。

圖2 K-means算法聚類效果

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

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

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

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

圖4 本文算法產生的初始簇心

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

圖5 本文算法產生的聚類效果圖

通過對比圖2～圖5的類簇中心點坐標可以得出，三個聚類算法的最終類簇中心點的坐標的比較接近，而本文聚類算法自動選擇的5個初始聚類中心點的坐標與最終形成的類簇中心點坐標的位置十分接近，由此可以直觀地看出本文算法可以達到減少聚類過程中的迭代次數，提高聚類算法效率預期效果。

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

表1 針對人造二維數據集各算法的聚類性能結果

為了進一步檢驗本文算法在多維數據集上的聚類效果，驗證算法在聚類過程中減少迭代次數和提高聚類算法效率，現選取UCI中多個針對聚類算法的數據集進行聚類對比實驗。

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

表2 UCI中針對聚類數據集的性質

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

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

表3 各算法迭代次數

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

表4 各算法的誤差平方和

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

表5 各個算法的時間

針對驗證本文算法在實際實驗中的應用，本文又選取了西安交通大學XJTU-SY滾動軸承加速壽命試驗數據中工況為1的第五個軸承的數據進行聚類，該數據集包含垂直和水平振動信號，共有1 638 400個數據點，失效位置分為內圈和外圈兩類[20]。該數據集的具體聚類效果如表6所示。

通過對表6的分析可以看出，本文算法對滾動軸承加速壽命試驗數據實際的應用效果中，迭代次數，算法運行的時間均小于K-means、K-means++算法，即本文算法整體實驗效果優于K-means，K-means++算法。

表6 針對XJTU-SY滾動軸承加速壽命試驗數據集各算法的聚類性能結果

4 結論

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