鐘世立 華帥 陳彩鳳 王陳陳

(東莞理工學院 計算機科學與技術學院，廣東東莞 523808)

數據聚類是數據挖掘中的一個重要任務，其目的是根據數據對象之間的相似性確定一組有限的類別來描述數據集。目前，聚類已被廣泛應用于客戶細分、動態(tài)趨勢檢測、生物數據分析和社會網絡分析等領域[1]。對于各種數據處理任務，有許多聚類方法,其中K-Means是最經典的方法之一。在早期的研究中，經典K-Means算法是人們關注的焦點，主要原因是該算法的數學思想簡單、擴展性強，并且它對于問題的任何變量都具有線性漸近執(zhí)行時間。然而，K-Means聚類算法也存在以下缺陷：1)要求預先指定數據集簇數K；2)對初始質心的選擇敏感和缺乏全局搜索能力，大概率導致算法收斂到局部最優(yōu)解；3)隨著樣本維度和樣本數量增加導致計算成本劇增。針以上問題，許多改進算法被提出[2-3,7-13]。

為了克服K-Means算法對初始質心過于敏感的缺點，許多有效的算法被提出[2-3]。Arthur等[2]通過用一種簡單的隨機播種技術對K-Means進行了增廣，降低了K-Means在初始種子選擇中的隨機性。Lasheng等[3]提出了基于最大最小準則和FLANN的初始聚類中心選擇算法，提高了算法的穩(wěn)定性和準確性。上述的算法克服了K-Means聚類對初始質心敏感的缺陷，但是迭代過程仍采用K-Means聚類的框架，缺乏全局搜索能力。受遺傳算法和粒子群優(yōu)化算法等啟發(fā)式算法[4-6]全局搜索能力的影響，許多研究學者結合啟發(fā)式算法對K-Means算法進行了改進。Ahmadyfard等[7]結合粒子群優(yōu)化算法(PSO)和K-Means，提出了一種全局搜索能力更強的混合算法，稱為“PSO-KM”。Du等[8]為了進一步降低陷入局部最優(yōu)解的可能性，提出了一種改進的粒子對優(yōu)化算法(PPO)，并將其與K-Means相結合，稱為“PK-Means”。早期基于遺傳機制的聚類算法要么使用昂貴的交叉算子，要么使用昂貴的適應度函數，或兩者兼而有之。為了避免這些昂貴的操作，Krishna等[9]將遺傳算法與聚類使用的經典梯度下降算法K-Means進行雜交。上述改進算法在一定程度上降低了聚類的總體誤差和計算成本。盡管這些方法是可行的，但是由于使用群體的思想，計算成本明顯高于K-Means。因此，Lam等[10]將簡單的探索向量與K-Means相結合，提出了一種稱為“XK-Means”的聚類算法，該方法從速度、誤差、穩(wěn)定性及復雜度等方面都優(yōu)于現有的基于進化和群體智能的聚類方法。近期，針對K-Means面對高維度和大樣本數據時計算成本劇增的問題，Xia等[13]提出了一種新穎的加速精確K-Means聚類算法，稱為“Ball K-Means”。盡管它可以降低K-Means的計算成本，但它和K-Means都存在對初始質心敏感和缺乏全局搜索能力的缺點。

因此考慮算法的全局搜索能力和計算成本兩個因素，本文結合探索向量和Ball K-Means技術提出一種新的聚類方法，稱為“基于探索向量的Ball K-Means聚類算法”，亦稱為“Ball XK-Means”。Ball XK-Means的目的是提高算法的搜索能力，同時使算法的計算成本盡可能低，其原理是基于這樣一個事實：雖然Ball K-Means可以有效地降低計算成本，但是在探索全局最優(yōu)的途徑上通常是無效的。因此，將一種防止聚類過程過早收斂的探索向量引入到Ball K-Means中，提出了一種更穩(wěn)定、更準確和更高效地針對高維度和大樣本數據的聚類算法。

1 相關工作

本節(jié)首先介紹與本文相關的聚類評價準則，然后介紹K-Means[14]和Ball K-Means[13]聚類技術。

1.1 評價準則

聚類的目標是將數據集分成若干簇，使得簇內的樣本相似度盡可能大，而簇間的樣本相似度盡可能小[15]。該理念有多種實現方式，每種方式對應一種評價指標，可用于檢驗算法的有效性。在本文中，采用如下評價指標對聚類算法進行評估：均方誤差(MSE)[16]。它的定義如下：

(1)

式(1)中，N表示數據集樣本總數，K表示數據集簇數，集合Ci表示第i個簇,|Ci|表示第i個簇的樣本數量，ci為簇Ci的質心。

1.2 K-Means聚類

K-Means是最經典的聚類算法之一，由于其簡單的數學思想、易擴展性和快速收斂性等優(yōu)點，已被廣泛用于解決聚類問題。但是，K-Means也存在缺陷，例如需自定義簇數K、對初始質心的敏感性、缺乏全局搜索能力和面對高維度據、大樣本數據時算法的計算成本高等[15]。本質上，K-Means聚類是在D維歐幾里得空間RD中將給定的個數據對象劃分為K個簇的方法，使簇內樣本盡可能相似，簇間樣本盡可能不相似。K-Means代碼如算法1。

算法 1:K-Means聚類

輸入：數據集X=x1,…,xn?Rd,簇數K；

輸出：簇質心C=c1,…,cK；

1. 隨機選擇K個樣本作為初始質心C=c1,c2,…,cK；

2. 將每一個樣本x依據最近距離分配給最近的簇Ci中，i∈1,…,K；

4. 重復步驟2、3直到C不再改變；

1.3 Ball K-Means聚類

考慮到K-Means算法在高維度和大樣本數據下計算成本高的問題，Xia等[13]提出了一種新穎的K-Means聚類算法，稱為“Ball K-Means”。該算法使用“球”的思想來描述每個簇，以減少樣本點和簇質心間的計算次數。Ball K-Means聚類算法代碼如算法2，該算法減少計算次數的核心思路有以下三點。

算法 2:Ball K-Means聚類

輸入：數據集X=1,…,xn?RD,K表示簇的數量，初始簇質心C=c1,…,ck；

輸出：簇質心C=c1,…,ck；

1. 初始化迭次數t=1，進行一步標準的K-Means迭代；

2. flagi=FLASE(i=1,…,K)；//決定簇質心和半徑是否需要被更新；

3. while簇質心發(fā)生改變 do

4. fori=1,…,Kdo

5. if flagi=FALSE then

//其中δ(cit)表示為第i個簇質心第t-1代和第t代的差值，為了找出下一代的鄰居關系；

6. 更新簇質心cit=mean(x|x∈Ci)，記錄δ(cit)=cit-ci(t-1)；

7. 根據式(2)更新當前簇半徑rit；//rit表示第i個簇第t代的半徑；

8. end if

9. end for

10. ift=1 then

11. 計算任意兩個質心的距離dist(cit,cjt)(i,j=1,…,K)；//初始化質心距離矩陣；

12. else

13. 若滿足式(4)，則dist(cit,cjt)=dist(ci(t-1),cj(t-1))-δ(ci(t))-δ(cj(t))；

14. end if

15. fori=1，…，Kdo

16. 設置當前代簇Ci的鄰居質心集合NCi(t)=φ，根據式(3)計算簇的鄰居簇；

17. 根據穩(wěn)定域、活動域和環(huán)域的關系，重新分配樣本點進入簇Ci中；

18. end for

19. fori=1，…，Kdo

20. ifCi穩(wěn)定then

21. flagi=TRUE；

22. else

23. flagi=FALSE；

24. end if

25. end for

26.t=t+1；

27. end while

1)精確地找到每一個簇的鄰居簇，使得樣本點和簇質心間的計算限制在樣本點和它的鄰居簇中而不是所有的簇。Ball K-Means中的簇質心和簇半徑定義如下：

(2)

式(2)中，集合Ci表示為第i個簇，|Ci|表示第i個簇的樣本數量，ci表示為第i個簇Ci的質心，x是屬于簇Ci中的樣本點，ri表示為第i個簇Ci的半徑。其鄰居簇關系定義如下：

(3)

式(3)中，ci和cj分別表示第i和j個簇的質心，此式表明簇Cj是簇Ci的鄰居簇(鄰居簇為非對稱關系)。簇和鄰居簇的關系如圖1。

圖1 簇C1的鄰居簇關系 虛線表示連接兩個簇質心的線段的平分線，菱形和實線分別代表簇質心和簇半徑。根據鄰居的定義可知，簇C1的鄰居簇有：C2和C3。

2)將每一個簇劃分為穩(wěn)定域和活動域，且進一步將活動域切分為多個環(huán)域。經數學上的證明，處于穩(wěn)定域中的樣本點將不再改變，而處于活動域中的樣本將依據距離最近原則重新分配進入某個鄰居簇或原簇，達到減少計算成本的目的。具體關系如圖2。

圖2 簇C1的分區(qū) 虛線表示連接兩個簇質心的線段的平分線。根據定義可知，第1個環(huán)域的樣本點將重新劃分進入簇C1和簇C3, 并且第2環(huán)域中的樣本點將重新劃分進入C1、C2和C3，而處于穩(wěn)定域的樣本將不會被重新劃分。

3) 同時，由于當簇數很大時,尋找每個簇的鄰居簇需要很高的計算成本。因此Ball K-Means通過記錄下任意兩個簇質心的距離，提前找到下一代簇間的關系從而達到減少計算成本的目的。設置Ci和Cj表示第i和j個簇，如果滿足式(4)，意味著在當前迭代中不能是的鄰居簇，因此可以忽略這兩個簇質心間的距離計算。

dist(ci(t-1),cj(t-1))≥2ri(t)+δ(ci(t))+δ(cj(t))，

(4)

式(4)中，ci(t-1)表示第j個簇在第t-1代的質心，dist(ci(t-1),cj(t-1))表示為第i和j個簇在第t-1代的簇質心距離，δ(cit)表示為第i個簇質心第t-1代和第t代的差值。目的是為了找出不可能的鄰居關系。

2 基于探索向量的Ball K-Means聚類算法

本節(jié)首先介紹探索向量在K-Means算法中的作用以及它相關參數，然后提出改進的聚類算法。

2.1 探索向量

受啟發(fā)式算法的影響，Lam等[10]提出了一種稱為“XK-Means”聚類算法，其基本思路是：保留K-Means聚類算法的框架，在算法分配樣本前將探索向量作用到簇質心上，提升算法的全局搜索能力。為了更好地理解探索向量的作用，做了更直觀的描述(如圖3),其數學定義如下：

圖3 探索向量(三角形為簇質心，其他同形狀的樣本表示同簇數據) (a)圖是實驗中由K-Means聚類產生的局部最優(yōu)解，即算法此時已達到終止條件; (b)是在左圖的基礎上加上探索向量后的第一劃分，由于探索向量打破了局部最優(yōu)狀態(tài)，此時算法繼續(xù)迭代，最終收斂到更準確聚類結果。

(5)

vij=rand(aj,bj)*randSign(j),j=1,2,…,D,

(6)

式(6)中，vij表示第i個探索向量第j維的值，aj和bj非0且為正，被稱為是第j維的上下慣性權重。rand(aj,bj)和randSign(j)的功能分別是在aj和bj和之間分配一個隨機值和分配一個隨機負號或正號，這兩個隨機因素是控制算法搜索行為的關鍵隨機因素。其中aj被定義為與bj成比例，如下：

aj=βbj，

(7)

式 (7)中，β∈[0, 1) 為給定的因子。此處為了達到更好的效果，選取的參數值是β=0.5。同時，為了使得探索能夠從更大范圍的開始，并逐步轉向越來越多有效的開發(fā)。因此，隨著迭代的進行將bj定義如下:

(8)

2.2 基于探索向量的Ball K-Means聚類

在高維度和大樣本數據的條件下，盡管Ball K-Means聚類算法提高了K-Means聚類計算效率，但是該算法缺乏全局搜索能力。因此，從全局搜索能力和計算成本兩個因素考慮，結合探索向量和Ball K-Means聚類提出了一種改進的算法，稱為基于探索向量的Ball K-Means聚類算法，亦稱“Ball XK-Means”。

Ball XK-Means聚類算法是基于事實：在整個聚類過程中，將探索向量引入到Ball K-Means聚類算法中，從而提高算法的搜索能力。首先，算法早期，Ball XK-Means聚類算法不會由于隨機的初始質心差而收斂到局部最優(yōu)，而是使算法在更大的解空間內探索更多的潛在解。其次，隨著算法的迭代，不會因為算法框架本身缺乏全局搜索能力而迅速陷入局部最優(yōu)解，而是使Ball XK-Means聚類算法去探索當前解附近更好的解，從而達到增強算法搜索能力的目的。正是因為本算法引入了探索向量，因此與Ball K-Means聚類和K-Means聚類算法相比，它具有更強的搜索能力。同時又因為本算法使用“球”的思想改進了算法，減小了樣本點與質心的計算，在一定程度上克服了K- Means和XK-Means 聚類算在簇數多、數據維度高和數據量大的情況下，計算成本急劇上升的缺點。

Ball XK-Means聚類算法的基本思路如下：1)首先初始化簇數和慣性權重等參數，并且進行一次K-Means聚類算法迭代；2)更新質心并記錄簇的半徑；3)在更新后的質心上增加探索向量，并根據(7)、式(8)更新權重參數，評價MSE值；4)計算兩個簇質心間的距離和計算每個簇的鄰居簇，并依據穩(wěn)定域、活動域和環(huán)域的關系重新分配樣本。依次重復上述2)、3)、4)三個步驟，直到算法達到終止條件。該算法流程如圖4。

圖4 基于探索向量的Ball K-Means聚類算法的流程圖

3 數值實驗與結果討論

本節(jié)首先介紹實驗采用的數據集以及相關的參數設置，然后從算法的精確度和穩(wěn)定性、計算成本和收斂速度四個方面對實驗結果進行分析與討論。

3.1 數據集和參數設置

如表1所示，第5、6個數據集Sporulation、Yeast Cell Cycle是基因表達數據集[17]，另外6個來自于UCI數據集。由于Yeast Cell Cycle數據集的部分樣本存在缺失分量，為了糾正這些缺失數據，采用了文獻[8]中的策略：首先，刪除數據集中缺失分量超過的樣本。然后，采用k=15的KNN算法[18]估計其他缺失的分量值，其中k是相鄰樣本的個數。特別指出，這里的k值和本文提到的簇數K不是同一個。

表1 數據集信息

要達到數值實驗條件統(tǒng)一的原則。首先，由于Ball XK-Means聚類算法和XK-Means聚類算法都引入了探索向量，因此統(tǒng)一設置給定因子α=0.95,β=0.5。其次，將實驗所有聚類算法的停止準則替換為式(8)[10]，且因為每次迭代都使用探索向量來探索質心，所以在一次迭代之后評價結果可能有時不會提升。為確保算法有效性，讓該停止準則連續(xù)滿足10次即為終止條件。其中式(8)停止準則被定義如下：

(8)

其中，MSEt和MSEt-1分別代表當前代和上一代的MSE值。

在實驗中，在具有4核心Intel Core i7與16 GB 1600 MHz DDR3的筆記本電腦上，采用C++編程語言實現了K-Means、XK-Means、Ball K-Means及Ball XK-Means聚類算法。

3.2 實驗結果分析和討論

實驗中，8個數據集的簇數K設置如表1，且4種算法都采用隨機初始化質心的方式。記錄下評估這4種算法在8個真實數據集上運行20次的實驗指標數值，分別是：1)MSE平均值(值越小聚類效果越好)；2)MSE值的標準差(值越小算法越穩(wěn)定)；3)平均迭代次數(取整后)和平均每代的計算次數(樣本點和質心間的計算次數)；4)CPU平均執(zhí)行時間。以上列舉的實驗指標分別反映了算法的精確度、穩(wěn)定性、計算成本以及收斂速度。實驗數值列在表2中，并繪制4個算法在8個數據集上運行20次的MSE、平均每代的計算次數以及隨CPU執(zhí)行時間收斂結果(隨機選取20次中的1次)的圖像，分別為圖5和圖6、圖7、以及圖8和圖9。為了更好地體現本算法在高維度和大樣本數據下的有效性，將圖5和圖8繪制為低維度或小樣本數據集的實驗結果，將圖6和圖9繪制為高維度或大樣本數據集的實驗結果。

圖7 4種算法在8個數據集上平均每代的計算次數

比較表2中MSE平均值，Ball XK-Means和XK-Means獲得的MSE平均值均小于K-Means和Ball K-Means。從圖5、圖6可以更直觀地看出在20次的運行中Ball XK-Means和XK-Means多次優(yōu)于K-Means和Ball K-Means的MSE值，尤其隨著樣本維度和數量增加，這種差距更加明顯。盡管與XK-Means相比，Ball XK-Means并不總是能夠獲得最小的MSE值，但Ball XK-Means始終可以收斂到與XK-Means具有近似相同的聚類結果。因此，以上分析結果意味著提出的Ball XK-Means算法比K-Means和Ball K-Means算法具有更強的搜索能力，能收斂到更精確的解。主要原因是將探索向量引入到Ball K-Means聚類算法中，克服了它容易陷入局部最優(yōu)的缺點，進而提高了算法的搜索能力。

表2 MSE平均值和MSE標準差

圖5 4種算法分別在前4個數據集(低維度或小樣本)上運行20次的MSE值

圖6 4種算法分別在后4種數據集(高維度或大樣本)上運行20次的MSE值

同時，由于實驗中的4種聚類算法都具有隨機性，尤其是基于探索向量的聚類算法，因此穩(wěn)定性也是影響算法質量的一個相對重要的因素。比較表2中的MSE標準差，Ball XK-Means在Svmguide1、Codrna、Yeast Cell Cycle、Epileptic數據集上獲得了最小的值，在其它的數據集中也總是能夠獲得與其他算法相差不大的MSE標準差。從圖5和圖6也可以看出，與K-Means和Ball K-Means相比，Ball XK-Means和XK-Means在20次的MSE上多次獲得最小的MSE值和具有更小的波動，并且隨著樣本維度和數量增加，Ball XK-Means算法的優(yōu)勢更加明顯。因此，綜合表2、圖5及圖6中的實驗結果可以得出，Ball XK-Means相比于K-Means和Ball K-Means具有更好的穩(wěn)定性。

計算成本一直是影響算法效率的重要因素，比較表2中平均每代計算次數可以看出，Ball XK-Means和Ball K-Means比K-Means和XK-Means的平均每代計算次數少。從圖7也可以直觀的看出，與K-Means和XK-Means相比，在計算成本上，Ball XK-Means和Ball K-Means取得了更好的結果。更重要的是，Ball XK-Means和Ball K-Means與K-Means和XK-Means相比，在平均每代計算次數上的差距，將會隨著樣本維度和數量的增加而增加。這反映了面對高維度和大樣本數據時Ball XK-Means和Ball K-Means的有效性,主要是因為在算法引入了“球”的思想，有效地減少樣本點與簇質心間的計算次數。但是，由于Ball XK-Means在Ball K-Means的基礎上增加了防止算法過早收斂的探索向量，從而在平均意義上增加了算法的計算成本。因此，Ball XK-Means的計算成本將高于Ball K-Means。

同時，從表2中的CPU平均執(zhí)行時間參數可以得出，Ball XK-Means和Ball K-Means比K-Means和XK-Means具有更少的CPU執(zhí)行時間。從圖8和圖9中也可以直觀地看出，Ball XK-Means和Ball K-Means在CPU執(zhí)行時間(即收斂速度)上要優(yōu)于K-Means和XK-Means。尤其是隨著樣本維度或樣本數的增加，與K-Means和XK-Means相比，Ball XK-Means和Ball K-Means在CPU執(zhí)行時間上有更明顯的提升，充分體現了Ball XK-Means和Ball K-Means面對高維和大樣本數據時的高效性，主要是因為Ball XK-Means和Ball K-Means算法引入了“球”的思想，減少了計算量，提升了CPU執(zhí)行速度。同理，也是因為引入了探索向量來增強全局搜索能力，使得在Ball XK-Means的基礎上增加了計算成本，因此就CPU執(zhí)行速度而言，Ball XK-Means不如Ball K-Means聚類算法。

圖8 4種算法在前4個數據集(低維度或小樣本)上隨時間的收斂效果

圖9 4種算法在后4個數據集(高維度或大樣本)上隨時間的收斂效果

4 結語

筆者主要關注K-Means和Ball K-Means聚類算法存在的問題，K-Means和Ball K-Means在劃分數據集時具有很好的收斂速度，但是它們往往只收斂到局部最優(yōu)解。雖然XK-Means算法增強了K-Means算法的搜索能力，獲得了更精確的聚類結果，但是隨著樣本維度和樣本數量的增加，XK-Means的計算成本也會急劇增加。因此，綜合考慮算法搜索能力和計算成本這兩個因素，結合探索向量和“球”的思想，針對高維度、大樣本數據提出了一種更穩(wěn)定、更精確及更高效的基于探索向量的Ball K-Means聚類算法，稱為“Ball XK-Means”。對K-Means、Ball K-Means、XK-Means和Ball XK-Means算法進行了數值實驗。主要從四個方面評價算法的性能：1)均方誤差(MSE)越小表明算法越精確(搜索能力越強)；2)MSE標準差越小表明算法越算法越穩(wěn)定；3)平均每代的計算次數越小表明算法的計算成本越低；4)CPU執(zhí)行時間越小表明算法收斂速度越快。

實驗結果表明：首先，與Ball K-Means和K-Means相比，Ball XK-Means能夠獲得更穩(wěn)定、更精確的聚類結果，說明引入探索向量的有效性。其次，與K-Means和XK-Means相比，Ball XK-Means在平均每代計算次數和CPU執(zhí)行時間有更小的值，表明了算法的高效性，這說明了引入“球”思想的有效性。更重要的是，隨著樣本維度和樣本數量的增加，筆者提出的Ball XK-Means在聚類的穩(wěn)定性、精確性和執(zhí)行效率上有更明顯的優(yōu)勢。