基于模擬退火與貪心策略的平衡聚類算法

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

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

0 引言

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

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

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

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

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

本文的主要貢獻如下：

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

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

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

1 相關(guān)工作

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

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

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

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

2 問題定義

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

(1)

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

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

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

(2)

s.t.α(CSL)

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

3 基于模擬退火的平衡聚類初始點選擇

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

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

(3)

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

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

(4)

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

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

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

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

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

(5)

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

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

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

算法1 SACI算法。

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

輸出 中心點集C。

1)

C=?，SD=?；

2)

T=ts；

3)

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

4)

每個簇從D中將與其歐氏距離最近的Z個點加入簇；

6)

while (T>te) do

7)

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

9)

Δ=nscor-pscor；

10)

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

ifΔ<0

11)

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

12)

else

13)

λ=random()；

15)

16)

T=b×T；

17)

end while

18)

returnC

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

4 基于貪心策略的平衡聚類

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

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

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

(6)

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

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

(7)

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

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

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

(8)

其中算法的三個步驟對平衡的約束逐漸加強。

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

算法2 BCGS算法。

輸入 數(shù)據(jù)集D，簇數(shù)目K，中心點集C；

輸出 簇集合W。

1)

W=?，M=N；

2)

forj← 1 toKDO

3)

fori← 1 toMDO

4)

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

5)

ST=sort(T)；

6)

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

7)

重新計算第j個簇的中心點；

8)

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

9)

fori← 1 toMDO

10)

forj← 1 toKDO

11)

計算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)

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

19)

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

20)

M=M-1，T=?；

21)

returnW

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

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

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

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

6 實驗與分析

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

6.1 實驗設(shè)置

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

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

6.1.2 評價體系

使用平衡聚類常用的三種評價方法對提出的方法進行評估，包括：

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

(9)

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

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

(10)

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

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

(11)

其中rk表示第K個簇中的數(shù)據(jù)點個數(shù)。

6.2 實驗結(jié)果與分析

實驗中每個算法的聚類結(jié)果質(zhì)量及其平衡性如表1所示，主要的對比結(jié)果如下：

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

歸一化互信息比BCSG高。

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

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

表1 六種聚類算法在八個數(shù)據(jù)集上的實驗結(jié)果

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

表2 三種算法實際運行時間對比 s

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

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

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

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

表3 不同初始點選擇算法對聚類結(jié)果的影響

圖1 p的不同取值對不同聚類評價指標(biāo)的影響

圖2 q的不同取值對不同聚類評價指標(biāo)的影響

7 結(jié)語

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