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

摘 ?要： 針對(duì)傳統(tǒng)K-means算法的聚類不穩(wěn)定性，提出一種基于相異度與鄰域的初始聚類中心選擇算法。該算法首先構(gòu)造相異度矩陣，建立每個(gè)樣本點(diǎn)的鄰域，選取K個(gè)相互距離較遠(yuǎn)且鄰域內(nèi)樣本點(diǎn)較密集的初始聚類中心。采用K-means算法思想，利用UCI中的三種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。結(jié)果表明，相比傳統(tǒng)K-means算法，新算法有穩(wěn)定的聚類結(jié)果，且對(duì)比于已經(jīng)提出的兩種改進(jìn)算法，新的算法在保持準(zhǔn)確率的前提下，迭代次數(shù)有較大程度的減少。

關(guān)鍵詞： 相異度; 聚類; 初始聚類中心; K-means

中圖分類號(hào)：TP31 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? 文章編號(hào)：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 引言

機(jī)器學(xué)習(xí)是目前非?；馃岬囊婚T學(xué)科，聚類作為機(jī)器學(xué)習(xí)的其中一種算法，廣泛應(yīng)用于農(nóng)業(yè)[1]、圖像處理[2-3]和社會(huì)調(diào)查[4]等領(lǐng)域。其中K-means聚類因算法易懂和容易實(shí)現(xiàn)的優(yōu)點(diǎn)，使其受到眾多研究人員的使用和關(guān)注。

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

本文提出的新算法假設(shè)聚類個(gè)數(shù)為K，通過構(gòu)造相異度矩陣[8-10]，建立每個(gè)樣本點(diǎn)的鄰域，根據(jù)不同類別的樣本點(diǎn)距離不應(yīng)靠近且鄰域內(nèi)點(diǎn)較密集的原則，選取K個(gè)合適的樣本點(diǎn)作為初始聚類中心，隨后采用K-means算法的思想對(duì)數(shù)據(jù)集進(jìn)行聚類，得到穩(wěn)定的聚類結(jié)果。

本文采用UCI數(shù)據(jù)集中的三種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。通過比較新算法與傳統(tǒng)K-means算法和兩種改進(jìn)的算法[11-12]的實(shí)驗(yàn)結(jié)果，體現(xiàn)了本文算法的優(yōu)越性。其中，文獻(xiàn)[11]提出了一種自適應(yīng)聚類算法，根據(jù)誤差平方和（SSE）趨勢自動(dòng)確定簇?cái)?shù)，在不增加迭代次數(shù)的情況下得到了準(zhǔn)確聚類結(jié)果。文獻(xiàn)[12]則是在文獻(xiàn)[11]提出的算法上進(jìn)行改進(jìn)，并且最終實(shí)驗(yàn)結(jié)果在準(zhǔn)確率上有所提升。而本文的算法對(duì)比于兩種算法，在保持準(zhǔn)確率的情況下，迭代次數(shù)大幅下降。對(duì)比于傳統(tǒng)K-means算法，新算法同時(shí)具備準(zhǔn)確率高和迭代次數(shù)少的優(yōu)點(diǎn)。

1 算法綜述

1.1 算法相關(guān)定義

1.2 算法思想描述

首先設(shè)需要聚類的類別數(shù)為K。

根據(jù)數(shù)據(jù)集X構(gòu)造相異度矩陣R，然后建立初始化許可集合S，S包含X中每個(gè)樣本點(diǎn)的下標(biāo)，即第1個(gè)樣本點(diǎn)對(duì)應(yīng)S中的1。

對(duì)存在于集合S當(dāng)中樣本點(diǎn)的鄰域U_i，計(jì)算樣本點(diǎn)間的平均相異度，平均相異度最小的K個(gè)鄰域?qū)?yīng)的中心樣本點(diǎn)即作為候選的初始聚類中心。此時(shí)，按平均相異度從小到大的趨勢，依次判斷其余中心樣本點(diǎn)是否存在于第一個(gè)中心樣本點(diǎn)的鄰域當(dāng)中，若不存在，則判斷后續(xù)中心樣本點(diǎn)是否存在于第二個(gè)中心樣本點(diǎn)的鄰域中，以此類推，找到首個(gè)存在于前者中心樣本點(diǎn)鄰域中的樣本點(diǎn)，將該樣本點(diǎn)對(duì)應(yīng)的下標(biāo)從集合S中刪除，重新執(zhí)行本段的算法;否則，若這K個(gè)樣本點(diǎn)間互不存在于彼此的鄰域當(dāng)中，則將這K個(gè)樣本點(diǎn)作為最終的初始聚類中心。

將得到的初始聚類中心作為參數(shù)，采用K-means算法進(jìn)行聚類，即可得到K類樣本點(diǎn)。對(duì)比于UCI數(shù)據(jù)集已劃分的類別，判斷每個(gè)樣本點(diǎn)是否準(zhǔn)確分到各類當(dāng)中，由此計(jì)算分類的準(zhǔn)確率。

1.3 算法步驟

⑴ 根據(jù)數(shù)據(jù)集X建立相異度矩陣R，同時(shí)構(gòu)造初始許可集合S;

⑵ 對(duì)R中的每一行進(jìn)行排序，并記錄對(duì)應(yīng)的索引下標(biāo)，取前元素建立Rr_jki;

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

⑷ 找到mean_Rr_i中最小的K個(gè)值，對(duì)應(yīng)的下標(biāo)逐個(gè)添加到集合idx中;

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

⑹ 將該樣本點(diǎn)從許可集合S中除去，重新從⑵開始執(zhí)行;

⑺ 將集合idx中元素對(duì)應(yīng)的樣本點(diǎn)作為初始聚類中心;

⑻ 利用K-means算法得到聚類結(jié)果，并計(jì)算準(zhǔn)確率。

2 實(shí)驗(yàn)

本文實(shí)驗(yàn)采用UCI數(shù)據(jù)集中的三種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集分別為Iris，Wine，Seeds，對(duì)應(yīng)的描述如表1。

對(duì)比的算法包括傳統(tǒng)K-means算法、文獻(xiàn)[11]和文獻(xiàn)[12]的算法。其中，由于K-means的不穩(wěn)定性，本文實(shí)驗(yàn)中將對(duì)其運(yùn)行十次得到的結(jié)果取平均作為對(duì)比數(shù)據(jù)。

不同算法的實(shí)驗(yàn)結(jié)果如表2-表4所示。

根據(jù)表2-表4的結(jié)果可以看出，與傳統(tǒng)的K-means算法對(duì)比，本文算法的運(yùn)行結(jié)果在準(zhǔn)確率和迭代次數(shù)上都有所優(yōu)化。在Iris數(shù)據(jù)集中，平均迭代次數(shù)下降4.5次，平均準(zhǔn)確率則是提高2.8%;在Wine數(shù)據(jù)集中，平均迭代次數(shù)下降3.2次，平均準(zhǔn)確率提高約1.3%;而在Seeds數(shù)據(jù)集中，平均迭代次數(shù)下降最多，為5.1次，同時(shí)準(zhǔn)確率提高約0.14%。

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

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

3 結(jié)束語

針對(duì)傳統(tǒng)K-means算法聚類不穩(wěn)定以及兩種改進(jìn)算法迭代次數(shù)較多的缺陷，提出了一種新的具有穩(wěn)定聚類效果且迭代次數(shù)較少的算法，該算法基于相異度和鄰域，選取K個(gè)相互距離較遠(yuǎn)且鄰域內(nèi)樣本點(diǎn)較密集的初始聚類中心。

實(shí)驗(yàn)結(jié)果表明，新算法不僅準(zhǔn)確率較高，還彌補(bǔ)了迭代次數(shù)較多的缺陷，大幅度減少了K-means算法所需的迭代次數(shù)，具有更好的應(yīng)用前景。

參考文獻(xiàn)（References）：

[1] 陳歡，曹承富，張存嶺，李瑋，喬玉強(qiáng)，杜世州，趙竹.基于主成分-聚類分析評(píng)價(jià)長期施肥對(duì)砂姜黑土肥力的影響[J].土壤學(xué)報(bào)，2014.51（3）：609-617

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

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

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

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

[6] 李薈嬈. K-means聚類方法的改進(jìn)及其應(yīng)用[D].東北農(nóng)業(yè)大學(xué)，2014.

[7] 崔丹丹.K-Means聚類算法的研究與改進(jìn)[D].安徽大學(xué)，2012.

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

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

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

[11] 成衛(wèi)青，盧艷紅.一種基于最大最小距離和SSE的自適應(yīng)聚類算法[J].南京郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2015.35（2）：102-107

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

收稿日期：2021-03-29

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