基于模擬退火與貪心策略的平衡聚類(lèi)算法

唐海波，林煜明，李 優(yōu)，蔡國(guó)永

(1.廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))，廣西 桂林 541004; 2.廣西自動(dòng)檢測(cè)技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))，廣西 桂林 541004)(*通信作者電子郵箱ymlin@guet.edu.cn)

0 引言

隨著知識(shí)化、智能化時(shí)代的到來(lái)，人們已經(jīng)認(rèn)識(shí)到，對(duì)現(xiàn)實(shí)中產(chǎn)生的數(shù)據(jù)利用數(shù)據(jù)挖掘算法可以從中挖掘未知知識(shí)來(lái)獲得巨大價(jià)值。聚類(lèi)作為數(shù)據(jù)挖掘領(lǐng)域的一個(gè)常用算法，也是機(jī)器學(xué)習(xí)中廣泛運(yùn)用的無(wú)監(jiān)督學(xué)習(xí)方法，它可以在無(wú)任何先驗(yàn)知識(shí)數(shù)據(jù)集中發(fā)現(xiàn)其潛在模式。自20世紀(jì)60年代至今，多種不同的聚類(lèi)算法相繼被提出，包括K-Means[1]、層次聚類(lèi)[1]、DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[1-2]、Fuzzy C-Means(FCM)[1,3]、譜聚類(lèi)[1,4]等,并被廣泛應(yīng)用到多個(gè)領(lǐng)域，如模式識(shí)別、圖像處理、信息檢索等[1,5-7]。

平衡聚類(lèi)的任務(wù)是保證聚類(lèi)結(jié)果在傳統(tǒng)聚類(lèi)評(píng)價(jià)指標(biāo)下有較好表現(xiàn)的同時(shí)，讓每個(gè)簇的規(guī)模也盡可能相同, 因此，平衡聚類(lèi)的聚類(lèi)結(jié)果總具有一定的平衡性，這樣可以避免聚類(lèi)產(chǎn)生相對(duì)于多數(shù)簇而言過(guò)大或者過(guò)小的簇。然而傳統(tǒng)的聚類(lèi)算法，如K-Means、DBSCAN、FCM、譜聚類(lèi)等在聚類(lèi)的目標(biāo)簇?cái)?shù)目過(guò)大時(shí)，很難保證聚類(lèi)結(jié)果也能夠有較好的平衡性。

平衡聚類(lèi)在數(shù)據(jù)挖掘中也有著重要的應(yīng)用意義。許多實(shí)際應(yīng)用場(chǎng)景對(duì)聚類(lèi)結(jié)果的平衡性都提出了要求，例如在圖像檢索方面[8]，后臺(tái)應(yīng)用經(jīng)過(guò)分析用戶查詢的語(yǔ)義，需要返回的內(nèi)容可能涵蓋多種類(lèi)別，在沒(méi)有進(jìn)一步過(guò)濾信息情況下，后臺(tái)算法返回的數(shù)據(jù)需要覆蓋每個(gè)類(lèi)并且盡可能平衡；在無(wú)線傳感網(wǎng)中，不均衡的傳感器分布結(jié)構(gòu)可能造成網(wǎng)絡(luò)中不均衡的能源消耗，進(jìn)而影響網(wǎng)絡(luò)的壽命[9]；在課堂教學(xué)分組中，使用聚類(lèi)算法對(duì)班級(jí)學(xué)生進(jìn)行聚類(lèi)，結(jié)果中每個(gè)簇的規(guī)模所代表的小組人數(shù)應(yīng)該盡可能相同。

平衡聚類(lèi)作為聚類(lèi)問(wèn)題的一個(gè)子集也面臨著效率的問(wèn)題。由于許多聚類(lèi)算法都是基于K-Means進(jìn)行的改進(jìn)，對(duì)于K-Means而言，尋找出合適的簇中心點(diǎn)是一個(gè)NP-hard問(wèn)題[10]，無(wú)法在多項(xiàng)式時(shí)間內(nèi)計(jì)算出全局最優(yōu)的解。除了隨機(jī)初始化聚類(lèi)中心點(diǎn)，研究者們提出了不同的初始點(diǎn)選擇策略以降低算法復(fù)雜度，旨在有限的迭代次數(shù)內(nèi)提高傳統(tǒng)聚類(lèi)結(jié)果質(zhì)量。然而，當(dāng)前提出的平衡聚類(lèi)算法時(shí)間復(fù)雜度普遍較高，在較大規(guī)模數(shù)據(jù)集上的平衡聚類(lèi)存在效率較低的問(wèn)題，Malinen等[11]提出的平衡聚類(lèi)算法時(shí)間復(fù)雜度為O(tN3)，Liu等[12]提出的平衡聚類(lèi)算法時(shí)間復(fù)雜度為O(tN2)，其中，t為算法迭代次數(shù)，N為數(shù)據(jù)集中的數(shù)據(jù)總數(shù)。

由于現(xiàn)在許多應(yīng)用場(chǎng)景下的數(shù)據(jù)集規(guī)模較大，需要一種更高效的算法來(lái)應(yīng)對(duì)較大規(guī)模數(shù)據(jù)集場(chǎng)景下的平衡聚類(lèi)任務(wù)。針對(duì)平衡聚類(lèi)算法中的這些不足，本文研究中發(fā)現(xiàn)，先通過(guò)初始點(diǎn)選擇算法選擇初始點(diǎn)，隨后在使用基于貪心的方法聚類(lèi)同時(shí)約束簇的均衡度是一個(gè)有效降低平衡聚類(lèi)算法復(fù)雜度的方法。

本文的主要貢獻(xiàn)如下：

1) 提出了一種基于貪心策略的平衡聚類(lèi)算法(Balanced Clustering based on Greedy Strategy, BCGS)用來(lái)分配每個(gè)數(shù)據(jù)點(diǎn)，在真實(shí)數(shù)據(jù)集上實(shí)施對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)該算法保證了聚類(lèi)結(jié)果的平衡性；

2) 提出了適用于BCGS的一種基于模擬退火的初始點(diǎn)選擇算法(Simulated Annealing Clustering Initialization, SACI)用于聚類(lèi)初始點(diǎn)選擇，一系列聚類(lèi)實(shí)驗(yàn)結(jié)果表明該方法能夠高效地定位出合適的聚類(lèi)初始點(diǎn)，同時(shí)與其他平衡聚類(lèi)算法相比降低了平衡聚類(lèi)算法的時(shí)間復(fù)雜度；

3) 在6個(gè)UCI真實(shí)數(shù)據(jù)集和2個(gè)公開(kāi)圖像數(shù)據(jù)集上與其他算法比較了三項(xiàng)聚類(lèi)評(píng)價(jià)指標(biāo)(包括一項(xiàng)平衡性)，實(shí)驗(yàn)結(jié)果表明本文提出的平衡聚類(lèi)算法相比其他平衡聚類(lèi)算法更加高效，而且能夠保證聚類(lèi)結(jié)果的平衡性。

1 相關(guān)工作

目前已有的平衡聚類(lèi)可以分為2大類(lèi)，分別是硬平衡聚類(lèi)與軟平衡聚類(lèi)。硬平衡聚類(lèi)是通過(guò)對(duì)聚類(lèi)結(jié)果中每個(gè)簇規(guī)模進(jìn)行嚴(yán)格限制來(lái)達(dá)到平衡聚類(lèi)的目的。例如，ConstrainedK-Means Clustering方法中通過(guò)對(duì)簇中元素個(gè)數(shù)設(shè)置下限來(lái)避免在算法執(zhí)行過(guò)程中產(chǎn)生過(guò)小的簇[13]； BalancedK-Means[11]是在ConstrainedK-Means Clustering方法上的改進(jìn)，在聚類(lèi)開(kāi)始階段先構(gòu)造一個(gè)由N個(gè)數(shù)據(jù)點(diǎn)以及N個(gè)slot構(gòu)成的二部圖，將N個(gè)slot進(jìn)行K等分形成K個(gè)組，在數(shù)據(jù)點(diǎn)分配階段，使用匈牙利算法[14]將N個(gè)數(shù)據(jù)點(diǎn)絕對(duì)均衡地分配到N個(gè)slot中，slot中的每個(gè)組即對(duì)應(yīng)結(jié)果中的一個(gè)簇，該算法的時(shí)間復(fù)雜度為O(tN3)。

軟平衡聚類(lèi)僅將聚類(lèi)結(jié)果的平衡性作為其中一項(xiàng)約束條件，相較于硬平衡聚類(lèi)，其對(duì)于平衡的約束往往貫穿算法但絕對(duì)的平衡狀態(tài)只作為算法的理想目標(biāo)并不需要必須達(dá)到。在Banerjee等[15]的工作中，他們?cè)O(shè)計(jì)了一個(gè)由三個(gè)步驟組成的平衡聚類(lèi)算法，在數(shù)據(jù)點(diǎn)分配階段將每個(gè)簇中已有數(shù)據(jù)個(gè)數(shù)納入數(shù)據(jù)點(diǎn)加入簇的代價(jià)計(jì)算公式中，另外算法基于stable marriage problems問(wèn)題的思路解決點(diǎn)分配中的穩(wěn)定性問(wèn)題； 在Banerjee等[16]的工作中，算法還可以根據(jù)預(yù)先設(shè)定的閾值對(duì)聚類(lèi)結(jié)果的平衡度實(shí)現(xiàn)彈性控制； 在Liu等[12]的工作中，根據(jù)所設(shè)計(jì)的平衡性約束條件對(duì)聚類(lèi)結(jié)果進(jìn)行約束，其時(shí)間復(fù)雜度為O(tN2)。

總體來(lái)說(shuō)，之前提出的平衡聚類(lèi)算法，無(wú)論是硬平衡還是軟平衡，算法的時(shí)間復(fù)雜度普遍較高，算法運(yùn)行時(shí)間較長(zhǎng)，隨著數(shù)據(jù)規(guī)模的增大，需要一種低復(fù)雜度的算法來(lái)處理平衡聚類(lèi)問(wèn)題。

本文提出的平衡聚類(lèi)算法屬于硬平衡聚類(lèi)，算法分為兩個(gè)環(huán)節(jié)：首先創(chuàng)新性地采用模擬退火的方法在數(shù)據(jù)集中快速定位出合適的K個(gè)點(diǎn)作為平衡聚類(lèi)初始點(diǎn)； 接著基于K個(gè)初始點(diǎn)，通過(guò)設(shè)置的分配規(guī)則貪婪地將其周?chē)罱狞c(diǎn)加入簇中直到達(dá)到簇的規(guī)模上限，在此過(guò)程中每個(gè)點(diǎn)不需要再重新分配簇，所有簇一次性生成，這與現(xiàn)有的硬平衡聚類(lèi)算法有較大的不同。

2 問(wèn)題定義

給定數(shù)據(jù)集D={xi|i=1,2,…,N}，其中，N為數(shù)據(jù)集中數(shù)據(jù)總數(shù)。平衡聚類(lèi)是將數(shù)據(jù)集D按照預(yù)先定義的距離劃分為K個(gè)簇，每個(gè)簇?fù)碛幸粋€(gè)中心點(diǎn)共K個(gè)中心點(diǎn)C={μj|j=1,2,…,K}。每個(gè)簇包含的數(shù)據(jù)點(diǎn)情況存入CSL={Cl1,Cl2,…,ClK}，其中ClK={xi|i=1,2,…,G}表示第K個(gè)簇中所有的數(shù)據(jù)點(diǎn)。α(CSL)表示平衡聚類(lèi)對(duì)于簇的約束條件，如式(2)所示：

(1)

其中：ρ為簇規(guī)模平均值，τ為方差閾值。

平衡聚類(lèi)優(yōu)化的目標(biāo)函數(shù)是讓每個(gè)數(shù)據(jù)點(diǎn)到其所在簇的中心點(diǎn)距離平均值最小，目標(biāo)函數(shù)如式(2)所示：

minMSE(x1,x2,…,xN,μ1,μ2,…,μK);

(2)

s.t.α(CSL)

其中：φ(xi,μe(i))用于計(jì)算數(shù)據(jù)點(diǎn)xi分配至簇e(i)產(chǎn)生的損失值，μK表示第K個(gè)簇的中心，e(i)表示D中第i個(gè)數(shù)據(jù)點(diǎn)被分配到的簇。

3 基于模擬退火的平衡聚類(lèi)初始點(diǎn)選擇

K-Means計(jì)算每個(gè)簇的中心點(diǎn)是一個(gè)NP-Hard問(wèn)題[10]，初始點(diǎn)的計(jì)算對(duì)算法效果有較大影響。由于本文所提出的平衡聚類(lèi)算法也是基于傳統(tǒng)K-Means，因此如何計(jì)算平衡聚類(lèi)初始點(diǎn)也是算法面臨的一個(gè)問(wèn)題。

傳統(tǒng)K-Means等聚類(lèi)算法的迭代終止條件通常為每個(gè)數(shù)據(jù)點(diǎn)到其所在簇中心距離的平均值達(dá)到最小，如式(3)所示:

(3)

或者對(duì)于前后兩次迭代，中心點(diǎn)變化趨于穩(wěn)定，對(duì)于第一種終止條件，由于傳統(tǒng)聚類(lèi)對(duì)于每個(gè)簇的規(guī)模都沒(méi)有限制，因此，較小的代價(jià)函數(shù)值很可能是在較為不平衡的簇分布情形下得到的，即數(shù)據(jù)的局部分布密度會(huì)對(duì)傳統(tǒng)聚類(lèi)算法中心點(diǎn)的選擇以及簇的平衡性有較大的影響。

針對(duì)上述提出的初始點(diǎn)選擇面臨的問(wèn)題，本文提出了SACI算法，該算法基于模擬退火選擇聚類(lèi)初始點(diǎn)。為了讓選擇的初始點(diǎn)形成的簇滿足平衡的約束條件，對(duì)式(4)中每個(gè)簇包含的數(shù)據(jù)個(gè)數(shù)進(jìn)行約束，讓所確定的中心點(diǎn)到簇中所有Z個(gè)點(diǎn)的距離之和最小，如式(4)所示:

(4)

s.t. ?j∈{1,2,…,K}, ‖Clj‖=N/K-1

其中Z=N/K-1為理想平衡狀態(tài)下每個(gè)簇包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)。

由于從數(shù)據(jù)集中選擇出K個(gè)中心點(diǎn)并最小化式(4)過(guò)程與傳統(tǒng)K-Means相似，因此需要一種適用于高效解決該問(wèn)題的可行方法，否則算法效率將由于較低而無(wú)法應(yīng)對(duì)實(shí)際應(yīng)用場(chǎng)景下的平衡聚類(lèi)問(wèn)題。

本文所提出的SACI算法采取近似算法的思想來(lái)提高聚類(lèi)初始點(diǎn)選擇效率，在計(jì)算機(jī)科學(xué)與運(yùn)籌學(xué)中，近似算法經(jīng)常與解決NP-Hard問(wèn)題關(guān)聯(lián)起來(lái)，它可以找到合理的解決方案并且相當(dāng)快速。

首先定義狀態(tài)集合ζ={ui|i=1,2,…,h}，其中ui表示ζ中的每個(gè)狀態(tài)，即對(duì)應(yīng)不同的初始點(diǎn)選擇方案N(ui)表示在狀態(tài)ui一定鄰域內(nèi)的其他狀態(tài)且N(ui)?ζ。模擬退火中參數(shù)T表示當(dāng)前溫度并且單調(diào)遞減，te為溫度下限。

(5)

目標(biāo)函數(shù)用于計(jì)算每個(gè)狀態(tài)的得分(這里為式(4))。另外，對(duì)于一個(gè)給定的K個(gè)初始點(diǎn)選擇狀態(tài)U0，假設(shè)其在第s次實(shí)驗(yàn)后K個(gè)初始點(diǎn)選擇狀態(tài)為Us，并在嘗試第s+1次實(shí)驗(yàn)結(jié)束后新?tīng)顟B(tài)為Us+1，計(jì)算Us與Us+1的目標(biāo)函數(shù)差E(Us+1)-E(Us)，根據(jù)目標(biāo)函數(shù)差判斷新?tīng)顟B(tài)是否被接受。常用的接受準(zhǔn)則是Metropolis準(zhǔn)則：若E(Us+1)-E(Us)<0則接受新?tīng)顟B(tài)Us+1，否則算法依據(jù)概率ps接受鄰域內(nèi)的新?tīng)顟B(tài)Us+1，即：

模擬退火依據(jù)一定的概率來(lái)決定是否接受每次的調(diào)整，具有漸進(jìn)收斂性[16]，不僅可以避免算法陷入局部最優(yōu)解也可以快速收斂到一個(gè)接近全局最優(yōu)解的初始點(diǎn)集合。

為了更好地描述基于模擬退火的平衡聚類(lèi)初始點(diǎn)選擇算法，現(xiàn)對(duì)算法中函數(shù)與參數(shù)進(jìn)行介紹。E(x1,x2,…,xN,μ1,μ2, …,μK)對(duì)應(yīng)于式(4)的目標(biāo)函數(shù)的計(jì)算過(guò)程，ts為退火過(guò)程初始溫度，te為退火溫度下限，T為當(dāng)前溫度，b為退火算法降溫速率，TC={xj|j=1,2,…,K}為所有中心點(diǎn)一次調(diào)整后新的待選中心點(diǎn)集。本文提出的SACI算法如算法1所示。

算法1 SACI算法。

輸入 數(shù)據(jù)集D，簇?cái)?shù)目K，退火初始溫度ts，溫度下限te，降溫速率b；

輸出 中心點(diǎn)集C。

1)

C=?，SD=?；

2)

T=ts；

3)

從數(shù)據(jù)集D中隨機(jī)選擇K個(gè)點(diǎn)加入C，SD=D，D=D-C

4)

每個(gè)簇從D中將與其歐氏距離最近的Z個(gè)點(diǎn)加入簇；

6)

while (T>te) do

7)

調(diào)整中心點(diǎn)，得到待選中心點(diǎn)集TC；

9)

Δ=nscor-pscor；

10)

企業(yè)的運(yùn)營(yíng)邏輯是將生產(chǎn)要素轉(zhuǎn)化為商品，通過(guò)與市場(chǎng)對(duì)接這部分商品會(huì)被轉(zhuǎn)化為貨幣，利用這些貨幣企業(yè)可重新購(gòu)置生產(chǎn)要素。由此可見(jiàn)，企業(yè)的運(yùn)營(yíng)依賴于要素流轉(zhuǎn)，當(dāng)流轉(zhuǎn)效率提高時(shí)，企業(yè)的收益也將相對(duì)提升。但企業(yè)在合并重組后，管理機(jī)制與資源配置模式會(huì)發(fā)生改變，在磨合的過(guò)程中其要素流轉(zhuǎn)效率將有所降低。資金是計(jì)量生產(chǎn)要素的主要工具，因此生產(chǎn)要素流轉(zhuǎn)必然伴隨著資金流動(dòng)。有鑒于此，流轉(zhuǎn)效率的下降也必然會(huì)降低資金的使用效率。

ifΔ<0

11)

C=TC，pscor=nscor，D=SD，D=D-C，每個(gè)簇從D中將與其歐氏距離最近的Z個(gè)點(diǎn)加入簇；

12)

else

13)

λ=random()；

15)

16)

T=b×T；

17)

end while

18)

returnC

算法1中第7)行調(diào)整中心點(diǎn)的目的是在每個(gè)已確定的中心點(diǎn)“附近”選擇某個(gè)點(diǎn)作為新的備選中心點(diǎn)。為了讓算法能夠具有更好的拓展性，而不是具體地嚴(yán)格要求調(diào)整至距離最相近的第幾個(gè)點(diǎn)，針對(duì)每個(gè)中心點(diǎn)，本文提出了一種中心點(diǎn)選調(diào)策略，可以保證新的中心點(diǎn)在原始中心點(diǎn)不遠(yuǎn)處且較大概率與中心點(diǎn)很靠近。具體地，對(duì)于每個(gè)簇，隨機(jī)選擇簇中Z/3個(gè)數(shù)據(jù)點(diǎn)并記錄下與中心點(diǎn)的距離，從這部分點(diǎn)中選擇其距離最近的點(diǎn)作為該簇的新候選中心點(diǎn)。

4 基于貪心策略的平衡聚類(lèi)

基于第3章所描述的初始點(diǎn)選擇算法所選擇出的K個(gè)初始中心點(diǎn)，本文提出了BCGS算法，算法包括三個(gè)步驟:

在第一個(gè)步驟中，根據(jù)數(shù)據(jù)點(diǎn)與每個(gè)中心點(diǎn)的距離將與每個(gè)簇最接近的一部分點(diǎn)首先加入相應(yīng)的簇中，代價(jià)函數(shù)如式(6)所示：

Le(xi,μj)=‖xi-μj‖2;xi∈CLj

(6)

第二個(gè)步驟中，在決定數(shù)據(jù)點(diǎn)是否加入某個(gè)簇中時(shí)不僅考慮與每個(gè)簇中心點(diǎn)的距離，同時(shí)還考慮了每個(gè)簇目前的規(guī)模，代價(jià)函數(shù)如式(7)所示：

Lt(xi,μj)=‖xi-μj‖2/e×‖rj‖，xi∈CLj

(7)

其中‖rj‖表示第j個(gè)簇中已有的數(shù)據(jù)點(diǎn)數(shù)目。

在前兩個(gè)步驟完成時(shí)，數(shù)據(jù)集中的絕大部分?jǐn)?shù)據(jù)已經(jīng)分配至相應(yīng)的簇中。在第三個(gè)步驟時(shí)，只考慮每個(gè)簇中已有數(shù)據(jù)個(gè)數(shù)來(lái)決定將數(shù)據(jù)點(diǎn)添加至哪個(gè)簇中，代價(jià)函數(shù)如式(8)所示：

Lr(xi,μj)=‖rj‖;xi∈CLj

(8)

其中算法的三個(gè)步驟對(duì)平衡的約束逐漸加強(qiáng)。

為了更好地描述基于貪心策略的平衡聚類(lèi)算法，現(xiàn)對(duì)算法中的參數(shù)與相關(guān)函數(shù)進(jìn)行介紹：μj表示第j個(gè)簇的中心，xi表示每個(gè)簇中除中心點(diǎn)外第i個(gè)點(diǎn)，Le(xi,μj)表示上述步驟1中計(jì)算數(shù)據(jù)點(diǎn)與簇中心點(diǎn)之間的歐氏距離；Lt(xi,μj)代表上述步驟2中在對(duì)簇的平衡性有一定的約束情況下計(jì)算點(diǎn)添加至某個(gè)簇中的代價(jià)；Lr(xi,μj)表示上述步驟3中將剩下的某個(gè)數(shù)據(jù)點(diǎn)作為新點(diǎn)加入某個(gè)簇的代價(jià)值; 參數(shù)p表示在第1個(gè)環(huán)節(jié)中每個(gè)簇的生成比率; 參數(shù)q表示所設(shè)簇之間規(guī)模的方差閾值。

算法2 BCGS算法。

輸入 數(shù)據(jù)集D，簇?cái)?shù)目K，中心點(diǎn)集C；

輸出 簇集合W。

1)

W=?，M=N；

2)

forj← 1 toKDO

3)

fori← 1 toMDO

4)

計(jì)算Le(xi,μj)存入T；

5)

ST=sort(T)；

6)

將ST中的前p×Z個(gè)數(shù)據(jù)點(diǎn)加入第j個(gè)簇Wj中；

7)

重新計(jì)算第j個(gè)簇的中心點(diǎn)；

8)

M=M-p×Z，T=?；

9)

fori← 1 toMDO

10)

forj← 1 toKDO

11)

計(jì)算Lt(xi,μj)存入T；

12)

將xi添加至T中最小值所指的簇Wx；

13)

M=M-1，T=?；

14)

ifα(CSL)

15)

break；

16)

fori← 1 toMDO

17)

forj← 1 toKDO

18)

計(jì)算Lr(xi,μj)存入T；

19)

將xi添加至T中最小值所指的簇Wx；

20)

M=M-1，T=?；

21)

returnW

其中，第7)行中所述的重新計(jì)算中心點(diǎn)方法即將簇中所有點(diǎn)坐標(biāo)相加取算數(shù)平均值獲得。

5 時(shí)間復(fù)雜度分析

本文提出的平衡聚類(lèi)算法包括計(jì)算初始中心點(diǎn)與平衡聚類(lèi)2個(gè)步驟，在初始點(diǎn)計(jì)算算法的每一次迭代中，計(jì)算除中心點(diǎn)以外的每個(gè)數(shù)據(jù)點(diǎn)與每個(gè)中心點(diǎn)的距離，時(shí)間復(fù)雜度為O(N)，隨后每個(gè)中心點(diǎn)依次將距離每個(gè)簇中心最近的Z個(gè)數(shù)據(jù)點(diǎn)加入到相應(yīng)的簇中。取距離最近Z個(gè)點(diǎn)加入到簇中需要對(duì)距離排序，本文使用歸并排序?qū)ζ溥M(jìn)行排序，歸并排序算法在最壞情況下的時(shí)間復(fù)雜度為O(NlogN)，因此模擬退火選點(diǎn)算法時(shí)間復(fù)雜度為O(tNlogN)。

在第二個(gè)步驟中，算法的第1個(gè)環(huán)節(jié)需要計(jì)算每個(gè)中心點(diǎn)最近的p×Z個(gè)數(shù)據(jù)點(diǎn)，其中涉及一次排序，使用歸并排序的時(shí)間復(fù)雜度為O(NlogN);在第2個(gè)環(huán)節(jié)中需要計(jì)算剩下的數(shù)據(jù)點(diǎn)加入每個(gè)中心點(diǎn)的代價(jià)，時(shí)間復(fù)雜度為O(N);在第3個(gè)環(huán)節(jié)中，依次將剩余的極少數(shù)數(shù)據(jù)點(diǎn)加入當(dāng)前規(guī)模最小的簇中，時(shí)間復(fù)雜度為O(N),因此,貪心平衡聚類(lèi)算法時(shí)間復(fù)雜度為O(tNlogN)。在前面分析過(guò)，初始中心點(diǎn)選擇算法單次迭代時(shí)間復(fù)雜度也為O(tNlogN)，因此本文所提出的平衡聚類(lèi)算法的時(shí)間復(fù)雜度為O(tNlogN)。

6 實(shí)驗(yàn)與分析

本章中在6個(gè)UCI真實(shí)數(shù)據(jù)集與2個(gè)公開(kāi)圖像數(shù)據(jù)集上將提出的平衡聚類(lèi)算法與其他五種聚類(lèi)算法相比較，分別是K-Means、FCM、Spectral Clustering (SC)、BalancedK-Means、BCLS(Balanced Clustering with Least Square regression)。其中K-Means與 FCM是2種經(jīng)典的聚類(lèi)算法;K-Means是很典型基于距離的聚類(lèi)方法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，把得到緊湊且獨(dú)立的簇作為最終目標(biāo); FCM是一種無(wú)監(jiān)督的模糊聚類(lèi)方法，該算法是基于對(duì)目標(biāo)函數(shù)的優(yōu)化基礎(chǔ)上提出的一種聚類(lèi)方法，常用于模式識(shí)別中; SC算法建立在譜圖理論基礎(chǔ)上，其本質(zhì)是將聚類(lèi)問(wèn)題轉(zhuǎn)化為圖的最優(yōu)劃分問(wèn)題，能在任意形狀的樣本空間上聚類(lèi)且收斂于全局最優(yōu)解; BalancedK-Means是一種硬平衡聚類(lèi)算法，通過(guò)在由節(jié)點(diǎn)與slot組成的2部圖上使用匈牙利算法進(jìn)行簇分配，可以將數(shù)據(jù)點(diǎn)絕對(duì)平衡地分配到所有簇中去; BCLS是一種基于對(duì)平衡聚類(lèi)目標(biāo)函數(shù)優(yōu)化基礎(chǔ)上提出的一種高效平衡聚類(lèi)算法。

6.1 實(shí)驗(yàn)設(shè)置

6.1.1 數(shù)據(jù)集與預(yù)處理

本實(shí)驗(yàn)選取了6個(gè)UCI真實(shí)數(shù)據(jù)集與2個(gè)公開(kāi)圖像數(shù)據(jù)集，分別是Wine、Lonosphere、Iris、Cryotherapy、User Model、Vechicel、UMIST、YALE-B。為了更好地測(cè)試每個(gè)算法的平衡聚類(lèi)性能，將所有數(shù)據(jù)集中每種類(lèi)別的數(shù)據(jù)個(gè)數(shù)刪減至相同，即在平衡的數(shù)據(jù)集下聚類(lèi)測(cè)試聚類(lèi)結(jié)果的均衡度，所有算法運(yùn)行20次，取目標(biāo)函數(shù)值最低的結(jié)果，這與文獻(xiàn)[12]中的實(shí)驗(yàn)設(shè)置類(lèi)似。調(diào)整后的每個(gè)數(shù)據(jù)集信息如下：Wine中數(shù)據(jù)總數(shù)144，包含3類(lèi)；Lonosphere中數(shù)據(jù)總數(shù)252，包含2類(lèi)；Iris中數(shù)據(jù)總數(shù)150，包含3類(lèi)；Cryotherapy中數(shù)據(jù)總數(shù)84，包含2類(lèi)；User Model中數(shù)據(jù)總數(shù)200，包含4類(lèi)；Vechial中數(shù)據(jù)總數(shù)796，包含4類(lèi)，UMIST總數(shù)據(jù)數(shù)380，包含20類(lèi)；YALE-B總數(shù)據(jù)數(shù)2 204，包含38類(lèi)。為了提高實(shí)驗(yàn)效率，將維度較高的數(shù)據(jù)集UMIST與YALE-B使用主成分分析(Principal Component Analysis, PCA)進(jìn)行了降維處理，保留95%的信息。

6.1.2 評(píng)價(jià)體系

使用平衡聚類(lèi)常用的三種評(píng)價(jià)方法對(duì)提出的方法進(jìn)行評(píng)估，包括：

1) 聚類(lèi)準(zhǔn)確率(Accuracy，ACC)[17]。該指標(biāo)衡量數(shù)據(jù)所有數(shù)據(jù)元素在聚類(lèi)后的標(biāo)簽相較于先驗(yàn)知識(shí)中真實(shí)標(biāo)簽的準(zhǔn)確率，如式(9)所示:

(9)

其中:N為數(shù)據(jù)集中元素總數(shù)，若si=map(ri)，值為1，否則為0; map()為一個(gè)映射函數(shù)，將聚類(lèi)結(jié)果的數(shù)據(jù)標(biāo)簽映射至原數(shù)據(jù)集中相應(yīng)的標(biāo)簽。

2) 歸一化互信息(Normalized Mutual Information，NMI)[18]，用于評(píng)價(jià)聚類(lèi)結(jié)果與數(shù)據(jù)集原分布近似程度，如式(10)所示:

(10)

其中：I(X,Y)表示分布X與Y的互信息，H(X)表示分布X的信息熵。

3) 標(biāo)準(zhǔn)信息熵(Normalized Entropy, Nentro)[12]，用于衡量簇之間的平衡度，值越接近1表示所有簇之間越平衡，計(jì)算公式如式(11)所示：

(11)

其中rk表示第K個(gè)簇中的數(shù)據(jù)點(diǎn)個(gè)數(shù)。

6.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中每個(gè)算法的聚類(lèi)結(jié)果質(zhì)量及其平衡性如表1所示，主要的對(duì)比結(jié)果如下：

1) 對(duì)于規(guī)模或簇?cái)?shù)目較小的數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果表明，本文提出的平衡聚類(lèi)算法不僅能夠獲得更加平衡的聚類(lèi)結(jié)果，同時(shí)聚類(lèi)結(jié)果的準(zhǔn)確率與標(biāo)準(zhǔn)化互信息也普遍比其他算法要高。相較于BalancedK-Means、BCLS這兩種聚類(lèi)結(jié)果平衡性較好的算法，BCSG在每個(gè)數(shù)據(jù)集上的聚類(lèi)結(jié)果準(zhǔn)確率相比BalancedK-Means平均提高了4個(gè)百分點(diǎn)，歸一化互信息也平均提高了4個(gè)百分點(diǎn)，BalancedK-Means由于是一種硬平衡聚類(lèi)算法，因此聚類(lèi)的結(jié)果可以每次都達(dá)到絕對(duì)的平衡；相比BCLS準(zhǔn)確率平均提高了3個(gè)百分點(diǎn)，歸一化互信息也平均提高了1個(gè)百分點(diǎn)，而在傳統(tǒng)的聚類(lèi)算法上，BCSG結(jié)果的平衡性屬于最高；另外，只有在少數(shù)數(shù)據(jù)集上其他算法的準(zhǔn)確率與

歸一化互信息比BCSG高。

2) 對(duì)于規(guī)模或簇?cái)?shù)目較大的數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果表明，本文提出的平衡聚類(lèi)算法依然能夠保持聚類(lèi)結(jié)果很好的平衡性，同時(shí)聚類(lèi)結(jié)果也具有較高的準(zhǔn)確率與歸一化互信息，準(zhǔn)確率和歸一化互信息與BalancedK-Means相近。其中，BCLS由于是一種基于對(duì)目標(biāo)函數(shù)優(yōu)化的平衡聚類(lèi)算法，在數(shù)據(jù)集規(guī)模或者簇?cái)?shù)目過(guò)大時(shí)，聚類(lèi)結(jié)果的平衡性會(huì)有所降低。BalancedK-Means由于其時(shí)間復(fù)雜度過(guò)高，在大規(guī)模數(shù)據(jù)集上的運(yùn)行效率較低，如表1所示，BalancedK-Means在數(shù)據(jù)集YALE-B上較長(zhǎng)時(shí)間內(nèi)未得出聚類(lèi)結(jié)果。另外，由于SC算法考慮數(shù)據(jù)集的全局分布，因此在較大規(guī)模數(shù)據(jù)集上聚類(lèi)結(jié)果的準(zhǔn)確率與歸一化互信息相較于其他算法會(huì)較高。

接下來(lái)的實(shí)驗(yàn)主要關(guān)注不同聚類(lèi)方法的時(shí)間性能，主要結(jié)果如表2所示。在真實(shí)的6個(gè)UCI數(shù)據(jù)集與2個(gè)公開(kāi)圖像數(shù)據(jù)集上平衡聚類(lèi)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文提出的BCSG算法運(yùn)行時(shí)間比其他兩種性能較好的平衡聚類(lèi)算法BalancedK-Means與BCLS都短，其中BalancedK-Means的運(yùn)行時(shí)間最長(zhǎng)，BCLS其次，在較大規(guī)模的數(shù)據(jù)集上(YALE-B)運(yùn)行時(shí)間最高減少了40%，BalancedK-Means較長(zhǎng)時(shí)間內(nèi)未能計(jì)算出結(jié)果，BCSG算法具有更好的時(shí)間性能。

表1 六種聚類(lèi)算法在八個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

注：“—”表示算法在較長(zhǎng)時(shí)間內(nèi)未能得出聚類(lèi)結(jié)果。

表2 三種算法實(shí)際運(yùn)行時(shí)間對(duì)比 s

為了驗(yàn)證初始點(diǎn)選擇算法對(duì)算法結(jié)果的影響，實(shí)驗(yàn)設(shè)計(jì)將本文提出的BCSG算法使用不同的初始點(diǎn)選擇算法進(jìn)行對(duì)比，分為隨機(jī)取初始點(diǎn)與基于模擬退火取初始點(diǎn)，在6個(gè)UCI數(shù)據(jù)集與2個(gè)圖像數(shù)據(jù)集上的聚類(lèi)結(jié)果如表3所示，實(shí)驗(yàn)結(jié)果表明，雖然使用不同的初始點(diǎn)選擇算法對(duì)聚類(lèi)結(jié)果的平衡性影響非常小，但對(duì)聚類(lèi)結(jié)果的準(zhǔn)確率與歸一化互信息具有較大的影響； 因?yàn)锽CSG算法中的貪心聚類(lèi)環(huán)節(jié)主要用于約束簇的平衡度，初始點(diǎn)選擇算法在于選取出準(zhǔn)確的中心點(diǎn)使得簇分布與數(shù)據(jù)真實(shí)情況相近。實(shí)驗(yàn)進(jìn)一步驗(yàn)證了BCSG算

法中兩個(gè)環(huán)節(jié)的有效性。

圖1給出了不同p值對(duì)于不同聚類(lèi)評(píng)價(jià)指標(biāo)的影響。從圖1可以看出，算法2中的參數(shù)p影響平衡聚類(lèi)的結(jié)果質(zhì)量，其中，參數(shù)p對(duì)歸一化互信息(NMI)有較大影響，對(duì)正確率(ACC)的影響較小，對(duì)標(biāo)準(zhǔn)信息熵(Nentro)影響非常小。

圖2給出了不同q值對(duì)于不同聚類(lèi)評(píng)價(jià)指標(biāo)的影響。從圖2可以看出，算法2中的參數(shù)q也影響平衡聚類(lèi)的結(jié)果質(zhì)量，除個(gè)別數(shù)據(jù)集外，對(duì)準(zhǔn)確率(ACC)與歸一化信息(NMI)的影響都較小，對(duì)標(biāo)準(zhǔn)信息熵(Nentro)影響非常小。

表3 不同初始點(diǎn)選擇算法對(duì)聚類(lèi)結(jié)果的影響

圖1 p的不同取值對(duì)不同聚類(lèi)評(píng)價(jià)指標(biāo)的影響

圖2 q的不同取值對(duì)不同聚類(lèi)評(píng)價(jià)指標(biāo)的影響

7 結(jié)語(yǔ)

為了提高現(xiàn)有平衡聚類(lèi)算法的聚類(lèi)效果與時(shí)間性能，本文提出了一種低時(shí)間復(fù)雜度、高效的平衡聚類(lèi)算法，該算法采用模擬退火策略在數(shù)據(jù)集中首先快速找到合適的平衡聚類(lèi)初始點(diǎn)，模擬退火作為一種近似算法可以在較短時(shí)間內(nèi)獲得NP-Hard問(wèn)題的一個(gè)高質(zhì)量的解決方案代替最優(yōu)解，降低了算法的時(shí)間復(fù)雜度。接著，基于模擬退火選擇出的初始點(diǎn)，算法使用貪心的策略形成K個(gè)簇，具有較低的時(shí)間復(fù)雜度，在6個(gè)UCI真實(shí)數(shù)據(jù)集與2個(gè)公開(kāi)圖像數(shù)據(jù)集上實(shí)施對(duì)比實(shí)驗(yàn)的結(jié)果表明，本文提出的BCSG不僅比其他平衡聚類(lèi)算法高效，而且能夠保證聚類(lèi)結(jié)果的平衡性。在之后的工作中，可能將平衡聚類(lèi)應(yīng)用于分布式數(shù)據(jù)庫(kù)的節(jié)點(diǎn)數(shù)據(jù)分配任務(wù)中。