優(yōu)化初值的C均值算法

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

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

0 引 言

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

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

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

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

1 C均值算法簡述

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

(1)

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

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

(2)

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

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

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

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

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

2 本文算法

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

2.1 初值優(yōu)化

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

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

(3)

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

(4)

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

(5)

式中：|δ(x)|是樣本x鄰域中的樣本個(gè)數(shù)。可看出，樣本x的鄰域密度是指其鄰域中樣本與x的距離的算術(shù)平均值的倒數(shù)。樣本x的鄰域中樣本與x的平均距離越小，樣本x的鄰域密度就越大，說明該樣本所處區(qū)域的樣本密度越大，則該樣本處于聚類中心位置的可能性就越大。因此，本文主要依據(jù)樣本的鄰域密度來選擇聚類中心。

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

(6)

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

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

(7)

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

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

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

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

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

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

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

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

2.2 C均值聚類和算法的復(fù)雜度分析

以2.1節(jié)中選擇的C個(gè)聚類中心作為初始聚類中心，利用C均值算法進(jìn)行聚類分析。

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

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

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

使用與文獻(xiàn)[9]相同的3個(gè)標(biāo)準(zhǔn)來評(píng)價(jià)本文算法的全局最優(yōu)性能：

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

(8)

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

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

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

3.3 仿真數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

利用本文算法對(duì)仿真數(shù)據(jù)集D1和D2進(jìn)行聚類分析，結(jié)果分別如圖1(a)和(b)所示。在圖1中，相同標(biāo)記的點(diǎn)被聚為了一類，紅色的五角星是本文算法選取的初始聚類中心，藍(lán)色的五角星是最終的聚類中心。可以看到，利用本文算法所選擇的初始聚類中心都能較好的代表各自所屬的聚類，且與最終的聚類中心相距十分接近。

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

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

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

將本文算法與未經(jīng)初值優(yōu)化的傳統(tǒng)C均值算法進(jìn)行對(duì)比，結(jié)果如表3所示。傳統(tǒng)的C均值算法隨意地選擇初始聚類中心，因此，本文運(yùn)行10次該算法，取迭代次數(shù)和運(yùn)行時(shí)間的平均值與本文算法進(jìn)行對(duì)比。從表3可以看到，由于對(duì)初值進(jìn)行了優(yōu)化，本文算法的迭代次數(shù)少于傳統(tǒng)算法，然而，運(yùn)算時(shí)間也長于傳統(tǒng)算法。

表3 仿真數(shù)據(jù)集中初始聚類中心優(yōu)化前后的結(jié)果對(duì)比Table 3 Results comparison of initial cluster centers beforeand after optimization in synthetic datasets

3.4 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

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

表4 本文算法在UCI數(shù)據(jù)集上的聚類結(jié)果Table 4 Clustering results of proposed method on UCI datasets

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

表5 本文算法與傳統(tǒng)C均值算法、GKM算法、MGKM算法以及文獻(xiàn)[11]中算法在UCI數(shù)據(jù)集上的性能對(duì)比Table 5 Comparative results of proposed method, traditional c-means method, GKM, MGKMand method in ref.[11] on UCI datasets

注：xey是科學(xué)計(jì)數(shù)法，表示x×10y；表中所有的小數(shù)都保留至小數(shù)點(diǎn)后第2位。

4 結(jié)束語

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

[1] 邢濤, 黃友紅, 胡慶榮, 等. 基于動(dòng)態(tài)K均值聚類算法的SAR圖像分割 [J]. 中國科學(xué)院大學(xué)學(xué)報(bào), 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ìn)[J]. 傳感器與微系統(tǒng), 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] 劉華春, 候向?qū)? 楊忠. 基于改進(jìn)K均值算法的入侵檢測系統(tǒng)設(shè)計(jì)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 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] 徐森, 盧志茂, 顧國昌. 結(jié)合K均值和非負(fù)矩陣分解集成文本聚類算法 [J]. 吉林大學(xué)學(xué)報(bào)：工學(xué)版, 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] 詹森, 秦大同, 曾育平. 基于遺傳優(yōu)化K均值聚類算法工況識(shí)別的混合動(dòng)力汽車能量管理策略 [J]. 中國公路學(xué)報(bào), 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] 謝娟英, 郭文娟, 謝維信, 等. 基于樣本空間分布密度的初始聚類中心優(yōu)化K-均值算法[J]. 計(jì)算機(jī)應(yīng)用研究, 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算法的初始聚類中心的優(yōu)化[J]. 計(jì)算機(jī)工程與應(yīng)用, 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.