最小化誤差平方和k-means初始聚類中心優(yōu)化方法

周本金，陶以政，紀(jì) 斌，謝永輝

中國工程物理研究院 計(jì)算機(jī)應(yīng)用研究所，四川 綿陽 621900

1 引言

聚類是依照某種相似度度量標(biāo)準(zhǔn)，將數(shù)據(jù)集劃分成多個(gè)簇的過程，其目的是最大化簇內(nèi)相似度，最小化簇間相似度。目前聚類已經(jīng)廣泛應(yīng)用于多個(gè)領(lǐng)域，包括商務(wù)智能、模式識別、異常檢測、信息檢索[1]等領(lǐng)域。聚類也可以作為其他算法的預(yù)處理步驟。

k-means作為聚類算法中的一種，自MacQueen于1967年提出以來，因?yàn)槠鋵?shí)現(xiàn)簡單、時(shí)間開銷低并且適合于并行計(jì)算[2]，目前已經(jīng)得到了廣泛應(yīng)用。傳統(tǒng)的k-means算法是一種啟發(fā)式的貪心算法，常常得到的是一個(gè)局部最優(yōu)解，聚類效果很大程度取決于初始中心點(diǎn)的選擇。鑒于上述不足，很多學(xué)者對其提出了優(yōu)化方法。以PAM算法為代表的k-medoids聚類算法以及其改進(jìn)算法[3]，盡管算法能夠取得比較良好的聚類效果，但是時(shí)間開銷過大，不適合大規(guī)模數(shù)據(jù)聚類。最近幾年新興的模擬退火算法[4]和遺傳算法[5]，其目的是獲取全局最優(yōu)解，不過在實(shí)踐中這些方法沒有被廣泛接受。本文主要針對k-means對初始聚類中心敏感進(jìn)行優(yōu)化。目前優(yōu)化方法大體分為兩種，一種是基于距離的，另一種是基于密度的方法?；诰嚯x的方法主要優(yōu)點(diǎn)是時(shí)間開銷較小，不過無法反映數(shù)據(jù)點(diǎn)的分布信息，容易選取到孤立點(diǎn)。常見的有最大最小距離法[6]，該方法選取距離已有聚類中心距離之和最大的數(shù)據(jù)點(diǎn)作為下一個(gè)聚類中心，但是該方法對孤立點(diǎn)過于敏感?；诿芏鹊姆椒ㄍǔＤ軌虮容^準(zhǔn)確地反應(yīng)數(shù)據(jù)的分布情況，不過計(jì)算開銷較大。文獻(xiàn)[7-9]提出了樣本密度的概念，通過選擇密度最大且相互遠(yuǎn)離的數(shù)據(jù)點(diǎn)作為初始聚類中心點(diǎn)，通過設(shè)定參數(shù)調(diào)節(jié)樣本的鄰域半徑，并計(jì)算鄰域內(nèi)樣本數(shù)目作為樣本密度，但是參數(shù)的設(shè)置缺乏客觀性，需要先驗(yàn)知識或者經(jīng)驗(yàn)。文獻(xiàn)[10]通過計(jì)算樣本方差的形式，選擇樣本方差較小數(shù)據(jù)點(diǎn)作為聚類中心，能夠有效地降低誤差平方和；文獻(xiàn)[11]通過計(jì)算所有數(shù)據(jù)點(diǎn)的緊密性，將高緊密型的數(shù)據(jù)點(diǎn)集合作為候選聚類中心集合，選擇緊密性最大的數(shù)據(jù)點(diǎn)作為第一個(gè)聚類中心，之后按照最大最小距離原則，選擇后續(xù)的聚類中心。

2 k-means算法

2.1 經(jīng)典k-means算法

其中k為簇的個(gè)數(shù)，Oi是第i個(gè)簇Ci的聚類中心，dist(x,Oi)指的是數(shù)據(jù)點(diǎn)x與Oi的相異度，不同的相異度計(jì)算常常會導(dǎo)致不同的聚類結(jié)果[12]，通常采用歐式距離度量。

定義2歐式距離

定義3簇Ci的聚類中心Oi

k-means是一種迭代重定位方法，主要有兩個(gè)步驟，步驟1是依據(jù)最近鄰原則將數(shù)據(jù)點(diǎn)分配到距離最近的中心點(diǎn)；步驟2是重定位，即重新計(jì)算聚類中心。如此反復(fù)，直到到達(dá)指定的收斂條件，聚類結(jié)束。

k-means以最小化誤差平方和（簡稱sse）為目的，sse定義如下：

定義1誤差平方和

2.2 改進(jìn)算法minSseKmeans

傳統(tǒng)的聚類中心選擇方法由于是隨機(jī)選擇，容易選取到孤立點(diǎn)，或者多個(gè)數(shù)據(jù)點(diǎn)位于同一個(gè)類中，導(dǎo)致聚類結(jié)果質(zhì)量較差。由于數(shù)據(jù)選擇的隨機(jī)性，聚類結(jié)果也不穩(wěn)定。一個(gè)良好的初始聚類中心集合，應(yīng)該使得每一個(gè)類中都有一個(gè)數(shù)據(jù)點(diǎn)被選擇到，并且數(shù)據(jù)點(diǎn)越接近實(shí)際的聚類中心，效果越好。

2.2.1 基本原理

不同于目前已有的k-means初始中心優(yōu)化算法，本文是通過最大化減少sse的值來獲得初始聚類中心集合。k-means算法本身是以最小化sse為目標(biāo)，每次聚類迭代的過程中，實(shí)際上都是sse逐步減少的過程，如果初始聚類中心集合的sse能夠達(dá)到最小，那么不僅能夠減少聚類的迭代時(shí)間，同時(shí)較小的sse一定程度上能夠有效地避免選取到孤立點(diǎn)，后面的人工模擬數(shù)據(jù)能夠充分體現(xiàn)該點(diǎn)。本文提出的minSseKmeans算法就是基于這一原理提出。

為了在聚類初始中心選擇階段獲取較小的sse，Mt表示t次迭代之后所獲得的t個(gè)初始聚類中心數(shù)據(jù)點(diǎn)(t＜k)集合，在選擇第t+1的聚類中心Zt+1的時(shí)候，顯然會降低sse的值，因?yàn)橹辽儆幸粋€(gè)數(shù)據(jù)點(diǎn)（實(shí)際上是Zt+1本身）到Mt中聚類中心的最小距離要大于它到自身的距離?；谶@樣的原則，從數(shù)據(jù)集中選擇初始聚類中心的時(shí)候，選擇能夠最大程度地減少sse的數(shù)據(jù)點(diǎn)作為下一次聚類中心。即在第t+1次迭代的過程中，第t+1個(gè)聚類中心Zt+1應(yīng)該滿足（D是數(shù)據(jù)集集合）。

定義4

定義5

定義6

diffSSE(i)是將第i個(gè)數(shù)據(jù)點(diǎn)xi設(shè)置為聚類中心時(shí)候能夠減少的sse，mdtj是第 j個(gè)數(shù)據(jù)點(diǎn)xj在t次迭代之后到目前選擇到的聚類中心數(shù)據(jù)集合的最小距離。

2.2.2 基本步驟

為了減少不同量綱對聚類的影響，需要對數(shù)據(jù)標(biāo)準(zhǔn)化，采用離差標(biāo)準(zhǔn)化方法，使得數(shù)據(jù)落在[0，1]區(qū)間上。

定義7

其中maxp和minp分別是p屬性上的最大和最小值。

minSseKmeans步驟如下：

（1）利用定義7對數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化，迭代次數(shù)t=0。

（2）計(jì)算數(shù)據(jù)集中數(shù)據(jù)點(diǎn)之間相互距離。

（3）如果t=k，那么算法終止。否則轉(zhuǎn)到步驟（4）。

（4）如果‖ ‖M =0，說明聚類中心集合中還沒有一個(gè)數(shù)據(jù)點(diǎn)，根據(jù)定義1，以數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)作為聚類中心，計(jì)算其所對應(yīng)的sse，選擇最小的sse對應(yīng)的數(shù)據(jù)點(diǎn)作為第一個(gè)初始聚類中心Z1，并加入集合M中，記錄數(shù)據(jù)點(diǎn)xj到Z1的距離md1j；否則，根據(jù)定義6選擇能夠最大程度地減少sse的數(shù)據(jù)點(diǎn)作為第t次迭代的聚類中心Zt，加入集合M 。

（5）更新數(shù)據(jù)集中的所有數(shù)據(jù)點(diǎn)xj到集合M中的最短距離mdtj。迭代次數(shù)t自增1，轉(zhuǎn)至步驟（3）。

2.2.3 算法復(fù)雜度分析

步驟（2）計(jì)算數(shù)據(jù)點(diǎn)之間距離時(shí)間開銷是O(n2)。步驟（4）最外層循環(huán)是k次，表示需要選擇k個(gè)聚類中心，每次迭代過程中，計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)Z作為下一個(gè)聚類中心能夠減少的sse。由定義4可知，計(jì)算diffSSE的時(shí)候，需要比較數(shù)據(jù)集每個(gè)數(shù)據(jù)點(diǎn)上次迭代的最短距離和Z的距離，所以計(jì)算一個(gè)數(shù)據(jù)點(diǎn)的diffSSE的時(shí)間開銷是O(n)，而每次迭代需要比較所有的數(shù)據(jù)點(diǎn)，所以每次迭代算法復(fù)雜度是O(n2)，步驟（4）總的時(shí)間復(fù)雜度是O(kn2)。結(jié)合步驟（2）和步驟（4），文中minSseKmeans算法復(fù)雜度是O((k+1)n2)。

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

實(shí)驗(yàn)部分?jǐn)?shù)據(jù)集分為人工模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)，對比的兩個(gè)方法分別是文獻(xiàn)[6]中的基于最大距離法以及文獻(xiàn)[10]中基于最小方差優(yōu)化初始聚類中心方法。聚類質(zhì)量評價(jià)目前有很多個(gè)指標(biāo)，當(dāng)事先知道數(shù)據(jù)點(diǎn)所屬分類時(shí)候采用外在方法，當(dāng)數(shù)據(jù)點(diǎn)所屬分類事先未知采用內(nèi)在方法。由于采用的數(shù)據(jù)集已經(jīng)有基準(zhǔn)類別信息，所以采用BCubed[13]外在度量方法，其主要分為兩個(gè)度量指標(biāo)，精準(zhǔn)度Precision和召回率Recall。為了全面地評價(jià)聚類的好壞，采取二者的調(diào)和均值F作為聚類結(jié)果的綜合評價(jià)指標(biāo)。實(shí)驗(yàn)平臺采用Win8.1操作系統(tǒng)、i7-4710MQ 2.5 GHz處理器、Matlab2014。

定義8

定義9

其中L(xi)是基準(zhǔn)確定的xi的類編號，P(xi)代表聚類結(jié)果中xi所屬的簇編號。

定義10

3.1 真實(shí)數(shù)據(jù)集

測試數(shù)據(jù)集描述信息如表1所示（其中CMC數(shù)據(jù)集是Contraceptive Method Choice數(shù)據(jù)集的縮寫）。數(shù)據(jù)集按照樣本數(shù)從低到高排列，覆蓋了多種類型的數(shù)據(jù)分布，包括高維數(shù)據(jù)（屬性個(gè)數(shù)10個(gè)或以上）集、非均勻數(shù)據(jù)集（Indians Diabetes）以及混合型數(shù)據(jù)類型數(shù)據(jù)集（Ecoli）。對分類屬性的均值，采用眾數(shù)計(jì)算方法。聚類評價(jià)的指標(biāo)包括聚類時(shí)間、迭代次數(shù)以及F值，實(shí)驗(yàn)次數(shù)50。

表1 UCI數(shù)據(jù)集描述信息

3.1.1 聚類時(shí)間對比

除了傳統(tǒng)的k-means算法外，其他兩種算法時(shí)間復(fù)雜度和本文相同，都是O(n2)，不過n2對應(yīng)的常數(shù)項(xiàng)要低于本文算法，對于規(guī)模不大的數(shù)據(jù)，彼此之間的時(shí)間差距并不明顯。對于文中的大部分?jǐn)?shù)據(jù)集，本文算法時(shí)間開銷都低于其他兩種算法，主要是因?yàn)闀r(shí)間開銷由兩部分組成，前一部分是初始聚類中心的選擇，后一部分才是真正的聚類，當(dāng)數(shù)據(jù)集較少時(shí)候，后一階段聚類部分時(shí)間開銷占主要成分。由于minSseKmeans以最大程度的減少sse為目的，導(dǎo)致選擇初始聚類中心之后所獲得的sse是4個(gè)算法中最少的，使得后一階段的聚類的迭代次數(shù)減少，所以時(shí)間開銷要低于其他兩種算法。當(dāng)數(shù)據(jù)集規(guī)模較大時(shí)候（比如Letter Recognition數(shù)據(jù)集），本文算法時(shí)間開銷要顯著高于其他算法。Ecoli數(shù)據(jù)集是唯一一個(gè)混合型屬性的數(shù)據(jù)集，時(shí)間開銷較大。主要在于計(jì)算分類屬性距離的時(shí)候，比較的是字符串，而字符串比較的開銷要顯著高于單純的數(shù)值比較。聚類時(shí)間如表2所示。

表2 聚類時(shí)間 s

3.1.2 F值比較

實(shí)驗(yàn)結(jié)果如圖1所示，4種聚類方法在Letter Recognition上的F值都不到17%，說明該數(shù)據(jù)集聚類趨勢不明顯。另一方面，Letter Recognition本身類的數(shù)目和屬性較多，由于文中采用的是歐幾里德距離度量方法，而該度量方式容易受變量多重相關(guān)性[14]和噪聲影響[15]，當(dāng)對高維數(shù)據(jù)進(jìn)行聚類的時(shí)候，由于變量相關(guān)性影響會出現(xiàn)維度災(zāi)難[16]，使得不同簇之間區(qū)分度進(jìn)一步下降，所以導(dǎo)致最終聚類效果較差。鑒于此，在聚類開始前需要對高維數(shù)據(jù)進(jìn)行降維[17]。由于F值過低，沒有實(shí)際的對比價(jià)值，后面的驗(yàn)證部分不再使用Letter Recognition數(shù)據(jù)集。5個(gè)數(shù)據(jù)集中，只有Ecoli數(shù)據(jù)集，minSseKmeans算法所對應(yīng)F值不是最高。主要原因在于Ecoli有一個(gè)分類屬性，在對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化之后，會導(dǎo)致數(shù)值型屬性所占的權(quán)重低于分類屬性，致使分類屬性對數(shù)據(jù)集的聚類效果的貢獻(xiàn)程度大于其他數(shù)值型屬性。

圖1 聚類效果F值比較

盡管本文算法相較于其他三種算法聚類質(zhì)量提升程度不明顯，不過相較于其他兩種優(yōu)化初始聚類中心算法，本文算法相對于傳統(tǒng)的k-means算法在5個(gè)數(shù)據(jù)集上聚類質(zhì)量都有所改善，平均F值提升8%，而其他兩種算法往往只是針對于某種類型的數(shù)據(jù)的聚類質(zhì)量好于傳統(tǒng)k-means。盡管本文算法時(shí)間復(fù)雜度高于其他兩種算法，但是當(dāng)簇的個(gè)數(shù)相對較少，數(shù)據(jù)集規(guī)模不大的情況下，本文算法時(shí)間復(fù)雜度和其他兩種算法時(shí)間差異并不明顯。

3.1.3 迭代次數(shù)以及sse比較

一個(gè)好的初始聚類中心應(yīng)該盡可能地靠近真實(shí)聚類數(shù)據(jù)的聚類中心，同時(shí)能夠很大程度減少后續(xù)聚類階段迭代次數(shù)。因此迭代次數(shù)一定程度能夠體現(xiàn)初始聚類中心的優(yōu)劣。由圖2可以看出，在5個(gè)數(shù)據(jù)集中，本文算法中的迭代次數(shù)總是最少的，主要是因?yàn)閙inSseK-means方法在獲得初始聚類中心所對應(yīng)的sse是4個(gè)算法中最小的，在后期聚類階段達(dá)到收斂條件所需要的迭代次數(shù)自然較少。

圖2 迭代次數(shù)對比

最終聚類結(jié)束之后各個(gè)算法的sse如表3所示，對于大部分?jǐn)?shù)據(jù)集來說，本文算法的sse較小。

表3 真實(shí)數(shù)據(jù)集sse對比

3.2 人工模擬數(shù)據(jù)

為了測試該算法相對于其他兩種算法對孤立點(diǎn)不敏感，不需要像其他基于密度的算法[18]需要事先選擇高密度的數(shù)據(jù)點(diǎn)作為候選初始聚類中心。為此人工生成了一些模擬數(shù)據(jù)。

由minSseKmeans的步驟中不難看出，該方法不太可能選取到孤立點(diǎn)。在初始聚類中心選擇階段，當(dāng)選中當(dāng)前數(shù)據(jù)點(diǎn) pi作為聚類中心的時(shí)候，計(jì)算該數(shù)據(jù)點(diǎn)到數(shù)據(jù)集中的其他數(shù)據(jù)點(diǎn) pj的距離dist(i,j)，設(shè)當(dāng)前pj距離當(dāng)前聚類中心集合的最短距離為dmin，只有當(dāng)dist(i,j)小于dmin的時(shí)候，才能夠減少當(dāng)前sse。而k-means中孤立點(diǎn)通常指的是全局離群點(diǎn)，全局離群點(diǎn)定義為顯著偏離數(shù)據(jù)集中的大部分?jǐn)?shù)據(jù)點(diǎn)。假設(shè)選擇孤立點(diǎn)作為聚類中心，由于大部分的數(shù)據(jù)點(diǎn)都遠(yuǎn)離孤立點(diǎn)，會導(dǎo)致diffSSE(i)較小，相對于數(shù)據(jù)集中的正常點(diǎn)，孤立點(diǎn)不太可能作為聚類中心。

人工生成了3個(gè)符合高斯分布的二維數(shù)據(jù)點(diǎn)，每個(gè)簇有100個(gè)數(shù)據(jù)點(diǎn)。然后人工添加指定比率的孤立點(diǎn)，表4是模擬數(shù)據(jù)參數(shù)信息。其中σo表示孤立點(diǎn)數(shù)據(jù)高斯分布所對應(yīng)的標(biāo)準(zhǔn)差。

表4 人工模擬數(shù)據(jù)點(diǎn)參數(shù)信息

為了更清楚地顯示聚類中心選擇的最終結(jié)果，從多個(gè)模擬數(shù)據(jù)集中選取了一組孤立點(diǎn)比例為0.1的數(shù)據(jù)點(diǎn)集合進(jìn)行分析。圖3是數(shù)據(jù)點(diǎn)二維分布。其中+號代表實(shí)際的聚類中心。

圖3 模擬數(shù)據(jù)二維空間分布

采用不同比例的孤立點(diǎn)數(shù)據(jù)，分別使用最大距離法、最小方差法以及本文的minSseKmeans算法對人工模擬數(shù)據(jù)進(jìn)行聚類，獲得初始聚類中心。比較sse，結(jié)果如表5所示。

表5 模擬數(shù)據(jù)聚類最終sse

由表5容易看出，三種方法中，minSseKmeans總是能夠獲得最小的sse。sse最大的總是最大距離方法，因?yàn)樵摲椒ǔ跏純蓚€(gè)聚類中心選擇的是數(shù)據(jù)集中距離最大的兩個(gè)數(shù)據(jù)點(diǎn)，這種方式很容易選取到位于兩個(gè)相距較遠(yuǎn)的孤立點(diǎn)。

初始聚類中心結(jié)果如圖4所示。三種算法都受到了孤立點(diǎn)的影響，導(dǎo)致它們所獲得初始聚類中心都較大程度地偏離實(shí)際的聚類中心，其中最大距離法選取的初始聚類中心偏離程度最大，甚至有兩個(gè)聚類中心是孤立點(diǎn)，另一個(gè)聚類中心偏移實(shí)際簇中心較遠(yuǎn)。最小方差方法聚類效果相對次之，只選取到一個(gè)孤立點(diǎn)。minSseK-means效果最好，從圖中容易看出三個(gè)聚類中心彼此遠(yuǎn)離，并且有兩個(gè)聚類中心比較接近實(shí)際的聚類中心。

圖4 孤立點(diǎn)比例0.1聚類初始中心結(jié)果

4 結(jié)束語

針對k-means算法對初始聚類中心敏感問題，以最大程度減少當(dāng)前sse為思想，提出了minSseKmeans方法，該方法簡單而且容易理解。使用UCI真實(shí)數(shù)據(jù)集和人工模擬數(shù)據(jù)集，同其他已知的優(yōu)化k-means初始聚類中心的算法進(jìn)行對比，結(jié)果顯示該算法在選擇初始聚類中心方面不僅減少了聚類的迭代次數(shù)，而且提高了聚類質(zhì)量，同時(shí)該算法對孤立點(diǎn)不敏感。不過該方法算法復(fù)雜度較高，當(dāng)數(shù)據(jù)集規(guī)模較大的時(shí)候可以采取多次隨機(jī)取樣的方式，計(jì)算每個(gè)樣本的sse，選擇具有最小sse的樣本所對應(yīng)的聚類中心作為初始聚類中心。

盡管該方法能夠有效的選擇合適的初始聚類中心，但k-means的聚類質(zhì)量還和后面的重定位階段有關(guān)。單純擁有好的初始聚類中心，并不能保證聚類效果一定較好。主要是因?yàn)樵谥囟ㄎ浑A段新的聚類中心的計(jì)算對孤立點(diǎn)過于敏感，在進(jìn)行均值計(jì)算的時(shí)候，孤立點(diǎn)很可能使聚類中心偏離實(shí)際的聚類中心。所以后續(xù)階段還需要對k-means重定位階段進(jìn)行優(yōu)化，能夠?qū)⒐铝Ⅻc(diǎn)有效地篩選出來。