優化初值的C均值算法

劉 云，康 冰，侯 濤，王 柯，劉 富

(吉林大學 通信工程學院，長春 130022)

0 引 言

C均值算法(C-means method，CM)是一種常用的聚類算法，目前已被廣泛應用于圖像分割[1, 2]、網絡入侵檢測[3]、文本聚類[4]、混合動力汽車能量管理策略[5]等方向。然而，傳統的C均值算法隨機地選擇數據集中的樣本作為初始聚類中心，因此，該算法對初值敏感，易陷入局部最優[6]。

到目前為止，已經有很多方法用于解決傳統C均值算法的初值敏感問題。例如，Krishna等[6]和Laszlo等[7]利用遺傳算法為C均值算法確定初始聚類中心；Likas等[8]提出了一種全局C均值算法，首先以數據集中全體樣本的均值作為第一個聚類中心，然后分別以第一個聚類中心和數據集中任意一個樣本作為初始聚類中心，以2為聚類個數運行C均值算法，選擇具有最好的聚類結果的樣本作為第二個聚類中心，以此類推，直到確定了C個聚類中心。該方法的缺點是在聚類中心的選取過程中需要運行許多次C均值算法，十分費時?；诖?，Bagirov[9]和Bai等[10]分別提出了一種快速的全局C均值算法。

由于C均值算法是一種基于中心的聚類算法，理想的聚類中心應處于樣本密度較大的區域，因此，基于樣本密度的方法是一種有效的確定初始聚類中心的方法。例如，Cao等[11]提出了一種基于鄰域模型的初值選取方法，該方法選擇一組具有最大鄰域緊密度且彼此之間具有一定分離度的樣本作為初始聚類中心，然而由于該方法利用粗糙集理論中鄰域的上下近似集的比值作為某樣本的鄰域密度，因此計算過程比較費時；Fatemi等[12]提出了一種基于密度的初值選取方法，該方法在確定下一個聚類中心時，需要計算每個樣本與現有聚類中心的距離，因此，計算過程比較費時。此外，國內的謝娟英等[13]和賴玉霞等[14]分別提出了基于樣本空間分布密度的初始化方法。這類方法都是選擇具有較大樣本密度且彼此之間相距較遠的樣本作為初始聚類中心，區別之處在于計算樣本密度的方法以及“相距較遠”的定義方法。

為了解決傳統C均值算法對初值敏感的問題，本文提出一種優化初值的C均值算法(Optimal initialization-based CM，OICM)。首先，計算數據集中每個樣本的鄰域及鄰域密度；其次，選擇具有最大鄰域密度的樣本作為第一個聚類中心；然后，從剩余的樣本中選擇具有最大鄰域密度且其鄰域與已有聚類中心的鄰域的連接度滿足一定條件的樣本作為第二個聚類中心，以此類推，直到確定了C個聚類中心；最后，利用C均值算法完成聚類分析。該方法的基本假設是某樣本的鄰域密度越大，表明該樣本所處區域的樣本密度越大，則該樣本處于類中心區域的可能性就越大。同時，為了避免在同一個類中選擇多個聚類中心，各聚類中心的鄰域的連接度應小于某個數值。在仿真數據集和UCI數據集上進行聚類實驗，并與傳統C均值算法和3種典型的全局C均值算法進行對比，實驗結果表明，OICM算法有效地克服了傳統C均值算法對初值敏感的缺點，且在達到收斂需要的迭代次數和運算時間方面具有一定的優勢。

1 C均值算法簡述

C均值算法是一種基于中心的聚類算法，C是聚類個數。對于一個給定數據集X={x1,x2,…,xN}，C均值算法將其中的每一個樣本分配到距離其最近的聚類中。該算法的代價函數為：

(1)

式中：N為樣本數量；d(xi,θj)代表數據集中第i個樣本xi與第j個聚類中心θj之間的距離測度，一般利用歐氏距離。

在C均值算法中，以屬于某一類的所有樣本的均值作為該類的聚類中心，定義為：

(2)

綜上，C均值算法的聚類流程可總結為：

(1)隨機選擇C個樣本作為初始的聚類中心。

(2)將所有樣本分配到距離其最近的聚類中。

(3)根據式(2)更新各個聚類的聚類中心。

(4)重復步驟(2)和(3)直到所有樣本的歸屬不再變化。

2 本文算法

本文算法首先計算每個樣本的鄰域及鄰域密度，從中選擇C個具有最大鄰域密度的樣本作為初始聚類中心，同時聚類中心的鄰域之間應保持較小的結合度，以保證各個聚類中心分別代表不同的類；最后利用C均值算法對數據集進行聚類分析。

2.1 初值優化

假設X是歸一化之后的數據集，對于任意的x∈X，其鄰域δ(x)定義為：

δ(x)={xi|xi∈X且d(x,xi)≤ε}

(3)

式中：ε為數據集中樣本之間距離的平均值，定義如下：

(4)

樣本x的鄰域δ(x)的密度Density(δ(x))定義為：

(5)

式中：|δ(x)|是樣本x鄰域中的樣本個數?？煽闯觯瑯颖緓的鄰域密度是指其鄰域中樣本與x的距離的算術平均值的倒數。樣本x的鄰域中樣本與x的平均距離越小，樣本x的鄰域密度就越大，說明該樣本所處區域的樣本密度越大，則該樣本處于聚類中心位置的可能性就越大。因此，本文主要依據樣本的鄰域密度來選擇聚類中心。

如果某樣本具有較大的鄰域密度，那么該樣本附近的樣本同樣具有較大的鄰域密度。為了在一個聚類中只選擇一個聚類中心，兩個聚類中心之間應保持一定的分離程度。本文利用兩個樣本鄰域之間的連接度來衡量兩個樣本的分離程度，樣本xi的鄰域δ(xi)與樣本xj的鄰域δ(xj)之間的連接度Coupling(δ(xi),δ(xj))定義為：

(6)

式中：|A|表示集合A中包含的樣本個數，兩個樣本的鄰域連接度是指這兩個樣本的鄰域交集中的樣本個數與并集中的樣本個數的比值。因此，由式(6)可得：

0≤Coupling(δ(xi),δ(xj))≤1

(7)

兩個樣本鄰域之間的連接度越小，這兩個樣本屬于不同聚類的可能性就越高。在文獻[11]中，數據集中所有樣本間的平均距離被用作閾值來判斷兩個樣本是否屬于同一個聚類。因此，如果Coupling(δ(xi),δ(xj))<ε，則認為xi和xj屬于不同聚類的可能性就越大；反之，則認為xi和xj屬于相同聚類的可能性就越大。

綜上所述，本文算法選擇初始聚類中心的流程可總結為：

(1)將數據集X歸一化到區間[0,1]，初始化聚類中心集合Θ=?。

(2)計算參數ε，每個樣本xi的鄰域δ(xi)以及鄰域密度Density(δ(xi))。

(3)選擇具有最大鄰域密度的樣本x作為第一個聚類中心，Θ={x}。

(4)尋找下一個最大鄰域密度的樣本x′，Density(δ(x′))=max{Density(δ(xi))|xi∈X-Θ}。

(5)如果對于任意的θ∈Θ，都滿足Coupling(δ(x′),δ(θ))<ε，則選擇樣本x′作為下一個聚類中心，Θ=Θ∪x′；否則，Density(f(x′))=0。

(6)重復步驟(4)和(5)，直到|Θ|=C，即選擇了C個聚類中心。

2.2 C均值聚類和算法的復雜度分析

以2.1節中選擇的C個聚類中心作為初始聚類中心，利用C均值算法進行聚類分析。

本文算法的復雜度由初值選擇和C均值算法的復雜度兩部分組成。初值選取過程中的計算量主要來自于N(N-1)/2次距離計算，因此這部分的復雜度為T(N)=o(N2)。C均值算法的算法復雜度是T(N)=o(NCn)，其中n為迭代次數。

因此，本文算法的復雜度為T(N)=o(N2)。

3 實驗結果

3.1 實驗數據

為了驗證本文算法的性能，人工構建了兩個具有高斯分布的2維數據集D1和D2。數據集D1共包含有來自兩個類的1000個點，每個類包含500個點；數據集D2共包含有來自3個類的900個點，每個類包含300個點。此外，從UCI數據庫(http:∥archive.ics.uci.edu/ml/)下載了3個數據集Iris、Liver Disorders和Pima Indians Diabetes。本文使用的數據集的具體信息如表1所示。在這些數據集上進行聚類實驗，以驗證本文算法的性能，并與傳統C均值算法、文獻[8]、文獻[9]和文獻[11]中的方法進行性能對比。

表1 本文選用的數據集信息Table 1 Information of selected datasets in this paper

3.2 評價標準

使用與文獻[9]相同的3個標準來評價本文算法的全局最優性能：

(1)聚類算法最終的代價函數值與理想代價函數值之間的誤差，定義為：

(8)

式中：J是聚類算法最終得到的代價函數值；Jopt是理想的代價函數值。E=0代表某一種算法找到了數據集的全局最優解。一般地，如果0

(2)迭代次數N，指聚類算法達到收斂所需的循環次數。

(3)運行時間t，包括初值選取和聚類所需的運算時間。

3.3 仿真數據集實驗結果

利用本文算法對仿真數據集D1和D2進行聚類分析，結果分別如圖1(a)和(b)所示。在圖1中，相同標記的點被聚為了一類，紅色的五角星是本文算法選取的初始聚類中心，藍色的五角星是最終的聚類中心?？梢钥吹?，利用本文算法所選擇的初始聚類中心都能較好的代表各自所屬的聚類，且與最終的聚類中心相距十分接近。

表2列出了利用本文算法對數據集D1和D2進行聚類分析時，選擇的初始聚類中心、最終聚類中心以及算法的迭代次數。可以看到，由于初始聚類中心和最終聚類中心之間相距十分接近，本文算法分別僅用了2次和3次迭代就在數據集D1和D2上取得了收斂。

表2 初始、最終聚類中心以及達到收斂所需的迭代次數Table 2 Initial and final cluster centers, and iterationnumber

圖1 本文算法在仿真數據集D1和D2上的聚類結果Fig 1 Cluster results of proposed method onsynthetic dataset D1 and D2

將本文算法與未經初值優化的傳統C均值算法進行對比，結果如表3所示。傳統的C均值算法隨意地選擇初始聚類中心，因此，本文運行10次該算法，取迭代次數和運行時間的平均值與本文算法進行對比。從表3可以看到，由于對初值進行了優化，本文算法的迭代次數少于傳統算法，然而，運算時間也長于傳統算法。

表3 仿真數據集中初始聚類中心優化前后的結果對比Table 3 Results comparison of initial cluster centers beforeand after optimization in synthetic datasets

3.4 UCI數據集實驗結果

本文算法在UCI數據集上的聚類結果如表4所示，包含初始、最終聚類中心，算法達到收斂的迭代次數以及分類準確率。由于2或3都是Iris數據集合理的聚類個數，因此本文分別以2和3作為聚類個數進行聚類實驗。在Iris數據集的兩組聚類結果中，本文算法分別僅經歷3次和2次迭代就取得了收斂，分類準確率分別是98%和87.33%。在數據集Live Disorders上，本文算法經歷7次迭代達到收斂，聚類準確率為55.07%；在數據集Pima Indians Diabetes上，本文算法經歷15次迭代達到收斂，分類準確率為66.02%。

表4 本文算法在UCI數據集上的聚類結果Table 4 Clustering results of proposed method on UCI datasets

將本文算法與傳統C均值算法、兩種全局C均值算法GKM[8]和MGKM[9]，以及基于密度的初值選取方法[11]進行對比，結果如表5所示。表5中，N為迭代次數，t為運算時間，單位為秒。所有數據集理想的代價函數值Jopt和GKM、MGKM算法的實驗結果都來自文獻[9]。傳統C均值算法由于隨機地選擇初始聚類中心，因此未能在Iris數據集上尋找到全局最優點，此外其平均的迭代次數也多于本文算法。GKM算法和MGKM算法在數據集Iris和Pima Indians Diabetes上成功地搜索到了全局最優點，然而在Live Disorders數據集上經過60000次迭代依然沒有實現全局最優。本文算法在數據集Iris(C=2)、Pima Indians Diabetes和Live Disorders，都找到了近似的全局最優點。值得注意的是，本文算法達到收斂所需的迭代次數遠小于GKM和MGKM算法，僅需要幾次或十幾次。本文算法與文獻[11]中的算法具有相近的全局最優性能和迭代次數，但是本文算法的運算時間遠遠小于文獻[11]中的算法。

表5 本文算法與傳統C均值算法、GKM算法、MGKM算法以及文獻[11]中算法在UCI數據集上的性能對比Table 5 Comparative results of proposed method, traditional c-means method, GKM, MGKMand method in ref.[11] on UCI datasets

注：xey是科學計數法，表示x×10y；表中所有的小數都保留至小數點后第2位。

4 結束語

為了解決了傳統C均值算法(C-means method，CM)對于初值敏感的問題，本文提出了一種優化初始條件的C均值算法(Optimal Initialization-based CM, OICM)。與傳統的C均值算法隨機選擇初始聚類中心的方式不同，本文算法依據數據點的鄰域密度確定初始聚類中心，被確定為初始聚類中心的數據點具有較大的鄰域密度且彼此之間的鄰域連接度小于數據集中數據點間距離的平均值。本文在2個仿真數據集和3個UCI數據集上進行聚類實驗，實驗結果表明，本文算法有效地克服了傳統C均值算法對初值敏感的缺點。此外，本文還在UCI數據集上與3種全局C均值算法進行性能對比，結果表明本文算法在達到收斂所需的迭代次數和運算時間方面具有一定的優勢。

[1] 邢濤, 黃友紅, 胡慶榮, 等. 基于動態K均值聚類算法的SAR圖像分割 [J]. 中國科學院大學學報, 2016, 33 (5): 674-678.

Xing Tao, Huang You-hong, Hu Qing-rong, et al. SAR image segmentation based on dynamicalK-means clustering algorithm [J]. Journal of University of Chinese Academy of Sciences, 2016, 33 (5): 674-678.

[2] 李昌興, 黃艷虎, 支曉斌, 等. 基于加速k均值的譜聚類圖像分割算法改進[J]. 傳感器與微系統, 2016, 35(9): 137-140.

Li Chang-xing, Huang Yan-hu, Zhi Xiao-bin, et al. Improvements of accelerationk-means based spectral clustering algorithm for image segmentation [J]. Transducer and Microsystem Technologies, 2016, 35(9): 137-140.

[3] 劉華春, 候向寧, 楊忠. 基于改進K均值算法的入侵檢測系統設計[J]. 計算機技術與發展, 2016, 26 (1): 101-105.

Liu Hua-chun, Hou Xiang-ning, Yang Zhong. Design of intrusion detection system based on improvedK-means algorithm[J]. Computer Technology and Development, 2016, 26(1): 101-105.

[4] 徐森, 盧志茂, 顧國昌. 結合K均值和非負矩陣分解集成文本聚類算法 [J]. 吉林大學學報：工學版, 2011, 41(4): 1077-1082.

Xu Sen, Lu Zhi-mao, Gu Guo-chang. IntegratingK-means and non-negative matrix factorization to ensemble document clustering [J]. Journal of Jilin University (Engineering and Technology Edition), 2011, 41(4): 1077-1082.

[5] 詹森, 秦大同, 曾育平. 基于遺傳優化K均值聚類算法工況識別的混合動力汽車能量管理策略 [J]. 中國公路學報, 2016, 29(4): 130-137，152.

Zhan Sen, Qin Da-tong, Zeng Yu-ping. Energy management strategy of HEV based on driving cycle recognition using genetic optimizedK-means clustering algorithm [J]. China Journal of Highway and Transport, 2016, 29(4): 130-137，152.

[6] Krishna K, Murty M N. GeneticK-means algorithm [J]. IEEE Transactions on Systems Man & Cybernetics Part B: Cybernetics, 1999, 29(3): 433-439.

[7] Laszlo M, Mukherjee S. A genetic algorithm using hyper-quadtrees for low-dimensionalK-means clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(4): 533-543.

[8] Likas A, Vlassis N, Verbeek J J. The globalK-means clustering algorithm [J]. Pattern Recognition, 2002, 36(2): 451-461.

[9] Bagirov A M. Modified globalK-means algorithm for minimum sum-of-squares clustering problems [J]. Pattern Recognition, 2008, 41(10): 3192-3199.

[10] Bai L, Liang J, Sui C, et al. Fast globalK-means clustering based on local geometrical information [J]. Information Sciences, 2013, 245(10): 168-180.

[11] Cao F, Liang J, Jiang G. An initialization method for theK-means algorithm using neighborhood model [J]. Computers & Mathematics with Applications, 2009, 58(3): 474-483.

[12] Fatemi S B, Mobasheri M R, Abkar A A. Improving the accuracy of multispectral image clustering by means of a new initializing method [J]. Journal of the Indian Society of Remote Sensing, 2016, 44(4): 643-650.

[13] 謝娟英, 郭文娟, 謝維信, 等. 基于樣本空間分布密度的初始聚類中心優化K-均值算法[J]. 計算機應用研究, 2012, 29(3): 888-892.

Xie Juan-ying, Guo Wen-juan, Xie Wei-xin, et al.K-means clustering algorithm based on optimal initial centers related to pattern distribution of samples in space [J]. Application Research of Computers, 2012,29(3): 888-892.

[14] 賴玉霞, 劉建平.K-means算法的初始聚類中心的優化[J]. 計算機工程與應用, 2008, 44(10): 147-149.

Lai Yu-xia, Liu Jian-ping. Optimization study on initial center ofK-means algorithm [J]. Computer Engineering and Applications, 2008,44(10): 147-149.