基于相異度與鄰域的K-means初始聚類中心選擇算法

摘 ?要： 針對傳統K-means算法的聚類不穩定性，提出一種基于相異度與鄰域的初始聚類中心選擇算法。該算法首先構造相異度矩陣，建立每個樣本點的鄰域，選取K個相互距離較遠且鄰域內樣本點較密集的初始聚類中心。采用K-means算法思想，利用UCI中的三種數據集進行實驗。結果表明，相比傳統K-means算法，新算法有穩定的聚類結果，且對比于已經提出的兩種改進算法，新的算法在保持準確率的前提下，迭代次數有較大程度的減少。

關鍵詞： 相異度; 聚類; 初始聚類中心; K-means

中圖分類號：TP31 ? ? ? ? ?文獻標識碼：A ? 文章編號：1006-8228（2021）08-57-03

K-means initial clustering center selection algorithm based on

dissimilarity and neighborhood

Zhang Jialong

（College of Mathematics and Information， South China Agricultural University， Guangzhou， Guangdong 510642， China）

Abstract： Aiming at the clustering instability of traditional K-means algorithm， an initial cluster center selection algorithm based on dissimilarity and neighborhood is proposed. The algorithm constructs a dissimilarity matrix， establishes the neighborhood of each sample point， and selects K initial cluster centers that are far apart from each other and the sample points are denser in the neighborhood. The idea of K-means algorithm is adopted， and three data sets in UCI are used for experiment. The results show that compared to the traditional K-means algorithm， the new algorithm has stable clustering results， and compared to the two improved algorithms that had been proposed， the new algorithm has a greater reduction in the number of iterations while maintaining accuracy.

Key words： dissimilarity; clustering; initial cluster centers; K-means

0 引言

機器學習是目前非常火熱的一門學科，聚類作為機器學習的其中一種算法，廣泛應用于農業[1]、圖像處理[2-3]和社會調查[4]等領域。其中K-means聚類因算法易懂和容易實現的優點，使其受到眾多研究人員的使用和關注。

K-means[5-7]算法最早由Macqueen提出，是一種基于劃分的無監督學習算法。但最初的K-means算法在進行聚類時，不僅不能得到穩定的聚類結果，且容易陷入局部最優解的情況。因此，提出一種具有穩定聚類效果且快速的改進算法是非常必要的。

本文提出的新算法假設聚類個數為K，通過構造相異度矩陣[8-10]，建立每個樣本點的鄰域，根據不同類別的樣本點距離不應靠近且鄰域內點較密集的原則，選取K個合適的樣本點作為初始聚類中心，隨后采用K-means算法的思想對數據集進行聚類，得到穩定的聚類結果。

本文采用UCI數據集中的三種數據集進行實驗。通過比較新算法與傳統K-means算法和兩種改進的算法[11-12]的實驗結果，體現了本文算法的優越性。其中，文獻[11]提出了一種自適應聚類算法，根據誤差平方和（SSE）趨勢自動確定簇數，在不增加迭代次數的情況下得到了準確聚類結果。文獻[12]則是在文獻[11]提出的算法上進行改進，并且最終實驗結果在準確率上有所提升。而本文的算法對比于兩種算法，在保持準確率的情況下，迭代次數大幅下降。對比于傳統K-means算法，新算法同時具備準確率高和迭代次數少的優點。

1 算法綜述

1.1 算法相關定義

1.2 算法思想描述

首先設需要聚類的類別數為K。

根據數據集X構造相異度矩陣R，然后建立初始化許可集合S，S包含X中每個樣本點的下標，即第1個樣本點對應S中的1。

對存在于集合S當中樣本點的鄰域U_i，計算樣本點間的平均相異度，平均相異度最小的K個鄰域對應的中心樣本點即作為候選的初始聚類中心。此時，按平均相異度從小到大的趨勢，依次判斷其余中心樣本點是否存在于第一個中心樣本點的鄰域當中，若不存在，則判斷后續中心樣本點是否存在于第二個中心樣本點的鄰域中，以此類推，找到首個存在于前者中心樣本點鄰域中的樣本點，將該樣本點對應的下標從集合S中刪除，重新執行本段的算法;否則，若這K個樣本點間互不存在于彼此的鄰域當中，則將這K個樣本點作為最終的初始聚類中心。

將得到的初始聚類中心作為參數，采用K-means算法進行聚類，即可得到K類樣本點。對比于UCI數據集已劃分的類別，判斷每個樣本點是否準確分到各類當中，由此計算分類的準確率。

1.3 算法步驟

⑴ 根據數據集X建立相異度矩陣R，同時構造初始許可集合S;

⑵ 對R中的每一行進行排序，并記錄對應的索引下標，取前元素建立Rr_jki;

⑶ 對于樣本點x_i，計算鄰域內其余樣本點與x_i的相異度平均值，記為mean_Rr_i，i∈1，2，…，n，若i?S，則令mean_Rr_i=∞;

⑷ 找到mean_Rr_i中最小的K個值，對應的下標逐個添加到集合idx中;

⑸ 按j從小到大的順序判斷x_（idx（j））是否存在于鄰域U_（idx（i））中，j∈{2，3，…，K};i=min{j}-1，當找到第一個滿足的樣本點時，進入⑹，若不存在，刪去集合j中的第一個元素，令i=i+1，繼續按j從小到大的順序判斷x_（idx（j））是否存在于鄰域U_（idx（i））中，按上述的方法循環判斷，若出現j為空，則進入⑺;

⑹ 將該樣本點從許可集合S中除去，重新從⑵開始執行;

⑺ 將集合idx中元素對應的樣本點作為初始聚類中心;

⑻ 利用K-means算法得到聚類結果，并計算準確率。

2 實驗

本文實驗采用UCI數據集中的三種數據集進行實驗，數據集分別為Iris，Wine，Seeds，對應的描述如表1。

對比的算法包括傳統K-means算法、文獻[11]和文獻[12]的算法。其中，由于K-means的不穩定性，本文實驗中將對其運行十次得到的結果取平均作為對比數據。

不同算法的實驗結果如表2-表4所示。

根據表2-表4的結果可以看出，與傳統的K-means算法對比，本文算法的運行結果在準確率和迭代次數上都有所優化。在Iris數據集中，平均迭代次數下降4.5次，平均準確率則是提高2.8%;在Wine數據集中，平均迭代次數下降3.2次，平均準確率提高約1.3%;而在Seeds數據集中，平均迭代次數下降最多，為5.1次，同時準確率提高約0.14%。

另一方面，與改進的兩種算法進行比較，新算法在保持準確率幾乎不變的情況下，迭代次數有較大幅度的下降。在Iris數據集中，新算法迭代次數比以往最優的算法還要少4次，準確率雖有所下降，但下降幅度可忽略;在Wine數據集中，新算法準確率與改進算法持平，而迭代次數卻有下降至少1次;最后在Seeds數據集中，本文算法在保持準確率的前提下，迭代次數大幅度下降，由原來的12次和8次下降到3次，下降程度明顯。

由圖1可見，本文算法的迭代次數明顯低于其余算法，在該方面有較大的改進。

3 結束語

針對傳統K-means算法聚類不穩定以及兩種改進算法迭代次數較多的缺陷，提出了一種新的具有穩定聚類效果且迭代次數較少的算法，該算法基于相異度和鄰域，選取K個相互距離較遠且鄰域內樣本點較密集的初始聚類中心。

實驗結果表明，新算法不僅準確率較高，還彌補了迭代次數較多的缺陷，大幅度減少了K-means算法所需的迭代次數，具有更好的應用前景。

參考文獻（References）：

[1] 陳歡，曹承富，張存嶺，李瑋，喬玉強，杜世州，趙竹.基于主成分-聚類分析評價長期施肥對砂姜黑土肥力的影響[J].土壤學報，2014.51（3）：609-617

[2] 唐利明，王洪珂，陳照輝，黃大榮.基于變分水平集的圖像模糊聚類分割[J].軟件學報，2014.25（7）：1570-1582

[3] 雍玉潔，顧華.基于空間聚類和邊緣梯度的圖像分割算法[J].計算機與現代化，2021.2）：13-17

[4] 陳磊，周麗蘋，班茂盛，鄭運鴻.基于聚類分析的中國低齡老年人力資源水平區域差異研究[J].人口學刊，2015.37（4）：55-65

[5] 楊俊闖，趙超.K-Means聚類算法研究綜述[J].計算機工程與應用，2019.55（23）：7-14，63

[6] 李薈嬈. K-means聚類方法的改進及其應用[D].東北農業大學，2014.

[7] 崔丹丹.K-Means聚類算法的研究與改進[D].安徽大學，2012.

[8] 孟子健，馬江洪.一種可選初始聚類中心的改進k均值算法[J].統計與決策，2014.12：12-14

[9] 董秋仙，朱贊生.一種新的選取初始聚類中心的K-means算法[J].統計與決策，2020.36（16）：32-35

[10] 趙明清，蔣昌俊，陶樹平.基于等價相異度矩陣的聚類[J].計算機科學，2004.7：183-184

[11] 成衛青，盧艷紅.一種基于最大最小距離和SSE的自適應聚類算法[J].南京郵電大學學報（自然科學版），2015.35（2）：102-107

[12] 曹端喜，唐加山，陳香.一種優化初始聚類中心的自適應聚類算法[J].軟件導刊，2020.19（7）：28-31

收稿日期：2021-03-29

作者簡介：張嘉龍（2000-），男，廣東梅州人，本科，主要研究方向：機器學習。