李漢波 魏福義 張嘉龍 劉志偉

摘要：K-means算法從樣本集隨機(jī)選取初始聚類中心導(dǎo)致聚類結(jié)果不穩(wěn)定，且聚類性能易受奇異點(diǎn)影響。針對以上缺陷，文章定義基于相異度矩陣的鄰域半徑概念，依次選取最小鄰域半徑對應(yīng)的樣本作為初始聚類中心，直到鄰域半徑達(dá)到樣本集的平均鄰域半徑;若選取的聚類中心數(shù)量不足K個(gè)，逐步縮小鄰域參數(shù)探索，直到選出K個(gè)。隨后給出基于實(shí)驗(yàn)的剔除奇異點(diǎn)公式，得到最終的聚類結(jié)果。實(shí)驗(yàn)結(jié)果表明，算法在準(zhǔn)確度和迭代次數(shù)兩方面均有所改進(jìn)。

關(guān)鍵詞：K-means聚類;相異度;鄰域半徑;初始聚類中心;奇異點(diǎn)

中圖分類號(hào)：TP273.4? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? 文章編號(hào)：2096-4706（2021）07-0067-04

Improved K-means Algorithm Based on Dissimilarity Neighborhood

LI Hanbo，WEI Fuyi，ZHANG Jialong，LIU Zhiwei

（South China Agricultural University，Guangzhou? 510642，China）

Abstract：The K-means algorithm selects the initial clustering centers from the sample set at random，which leads to unstable clustering results，and the clustering performance is easily affected by singularity. In view of above defects，the paper defines the concept of neighborhood radius based on the dissimilarity matrix，and successively selects the samples corresponding to the minimum neighborhood radius as the initial clustering centers，until the neighborhood radius reaches the average neighborhood radius of the sample set;if the number of selected clustering centers is less than K，the neighborhood parameter is gradually reduced to explore，until K initial clustering centers are selected. Then the formula of eliminating singular points based on experiment is given，and the final clustering result is obtained. Experimental results show that the algorithm is improved in accuracy and iteration times.

Keywords：K-means clustering;dissimilarity;neighborhood radius;initial cluster center;singularity

收稿日期：2021-03-24

基金項(xiàng)目：國家自然科學(xué)基金青年項(xiàng)目（117 01189）;廣東省大學(xué)生創(chuàng)新創(chuàng)業(yè)項(xiàng)目（S20201056 4034）;華南農(nóng)業(yè)大學(xué)微達(dá)安產(chǎn)業(yè)學(xué)院項(xiàng)目

0? 引? 言

聚類是衡量數(shù)據(jù)相似性的重要手段，聚類分析是機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘的熱點(diǎn)研究領(lǐng)域。聚類算法是根據(jù)樣本性質(zhì)對數(shù)據(jù)進(jìn)行劃分的一種無監(jiān)督學(xué)習(xí)算法。K-means算法[1]由MacQueen于1967年提出，屬于基于劃分的聚類算法，以其收斂速度快、簡單有效的優(yōu)點(diǎn)得到了廣泛的應(yīng)用[2-4]，但聚類性能易受奇異點(diǎn)影響，且算法隨機(jī)選取初始聚類中心會(huì)導(dǎo)致聚類結(jié)果陷入局部最優(yōu)解。

針對K-means算法隨機(jī)選取初始聚類中心導(dǎo)致聚類結(jié)果不穩(wěn)定的缺陷，一些學(xué)者在K-means算法的基礎(chǔ)上提出了多種改進(jìn)措施[5-9]。文獻(xiàn)[10]基于最近距離的原則，從樣本數(shù)量最多的聚類中選擇離散量最大與最小的兩個(gè)樣本作為初始聚類中心。文獻(xiàn)[11]利用局部方差反映數(shù)據(jù)密集程度的特性，提出一種基于最小局部方差優(yōu)化初始聚類中心的改進(jìn)K-means算法。文獻(xiàn)[6]和文獻(xiàn)[12]通過構(gòu)造樣本集的相異度矩陣，依次選取最大相異度參數(shù)對應(yīng)的樣本作為初始聚類中心。以上算法均能削弱K-means算法對初始聚類中心選取的敏感性，并能取得較為良好的改進(jìn)效果，但未考慮奇異點(diǎn)對算法性能的影響。

本文構(gòu)造樣本集的相異度矩陣，定義了可變鄰域參數(shù)τ和鄰域半徑，從最小鄰域半徑開始，按鄰域半徑遞增的原則尋找初始聚類中心，直到當(dāng)前鄰域半徑達(dá)到樣本集的平均鄰域半徑。若選取的初始聚類中心數(shù)量小于K個(gè)，縮小鄰域參數(shù)τ，循環(huán)執(zhí)行以上步驟，直到選出K個(gè)初始聚類中心。在選取初始聚類中心的過程中，尋找鄰域半徑最大的若干個(gè)樣本作為樣本集的奇異點(diǎn)。在K-means算法進(jìn)行迭代時(shí)，先剔除奇異點(diǎn)，以消除奇異點(diǎn)對算法性能的影響，最后再把奇異點(diǎn)按距離最近原則歸類。實(shí)驗(yàn)及其分析結(jié)果表明，該方法對K-means算法的性能具有良好的改進(jìn)效果。

1? 基于相異性鄰域的K-means算法

首先基于相異度矩陣，提出三個(gè)新概念，得到一種改進(jìn)初始聚類中心選取方法;然后定義了剔除奇異點(diǎn)的公式，給出改進(jìn)的K-means算法。

1.1? 改進(jìn)的初始聚類中心選取算法

以相異度矩陣代替樣本的歐式距離，能消除屬性值差異過大對初始聚類中心選取的影響。本文通過相異度矩陣對樣本集中各屬性進(jìn)行歸一化處理，給出基于相異度矩陣的三個(gè)概念，提出一種新的初始聚類中心選取方法。

1.1.1? 相關(guān)概念

設(shè)待聚類的樣本集：X={x1，x2，x3，…，xn}，其中xi=

{xi1，xi2，xi3，…，xim}，n為樣本集的樣本數(shù)量，m為樣本屬性的數(shù)量。

計(jì)算樣本的相異度并構(gòu)造相異度矩陣[6]：

（1）計(jì)算樣本xi與xj之間的相異度rij：

rij=

其中max{xrs}為第s個(gè)屬性的最大值，min{xrs}為第s個(gè)屬性的最小值。

（2）將所有樣本的相異度表示成n×n的相異度矩陣：

在相異度矩陣R的基礎(chǔ)上，引入鄰域參數(shù)τ，將τ初始化為τ=，隨后根據(jù)需要逐步減少，即取值為 -1，-2，-3，…，其中K表示樣本集的分類數(shù)， 表示向下取整。

定義1：對于相異度矩陣R和鄰域參數(shù)τ，將Ri中的元素從小到大排序，第τ個(gè)值稱為樣本xi的τ鄰域半徑，記作Ra（τ，xi）。其中Ri={ri1，ri2，…，rin}表示相異度矩陣的第i（i=1，2，…，n）行。以xi為中心，Ra（τ，xi）為半徑的鄰域中有τ個(gè)樣本。

定義2：對于樣本集X={x1，x2，x3，…，xn}，集合{Ra（τ，x1），Ra（τ，x2），Ra（τ，x3），…，Ra（τ，xn）}稱為對應(yīng)參數(shù)τ的鄰域半徑集合，記為M（τ）。

定義3：集合M（τ）的平均值稱為樣本集的平均鄰域半徑，記為m（τ）。

當(dāng)樣本xi的τ鄰域半徑Ra（τ，xi）大于平均鄰域半徑m（τ）時(shí)，可認(rèn)為樣本xi周圍分布的樣本較為稀疏。

1.1.2? 初始聚類中心選取方法

作為K-means算法初始聚類中心改進(jìn)方法，需要選取周圍樣本分布較密集的樣本，樣本xi的τ鄰域半徑Ra（τ，xi）越小，說明該樣本周圍分布的樣本越密集，即可以選擇xi作為某一類的初始聚類中心。對于樣本集X={x1，x2，x3，…，xn}，已選為初始聚類中心的樣本集合記為Z={z1，z2，…，zk};記集合L={l1，l2，…，lk}，其中l(wèi)i（i=1，2，…，k）表示zi為樣本集X中的第li個(gè)樣本。

設(shè)當(dāng)前已選為初始聚類中心的數(shù)量為k=0，遴選K個(gè)初始聚類中心的具體步驟為：

步驟1：構(gòu)造相異度矩陣，初始化鄰域參數(shù)τ，即令τ=? ;初始化Z集合為空集。

步驟2：構(gòu)造τ鄰域半徑集合M（τ），計(jì)算平均鄰域半徑m（τ）。

步驟3：從M（τ）選取最小值Ra（τ，xi）的樣本xi作為第一個(gè)初始聚類中心，并標(biāo)記樣本xi，隨后將樣本xi加入集合Z，令k=k+1。

步驟4：從集合M（τ）選取最小值Ra（τ，xj）且未被標(biāo)記的樣本xj作為下一個(gè)初始聚類中心候選樣本，若Ra（τ，xj）≥m（τ），則跳轉(zhuǎn)到步驟6。

步驟5：若Ra（τ，xj）+Ra（τ，zk）

步驟6：清空當(dāng)前已選為初始聚類中心的集合Z，令τ=τ-1，k=0，執(zhí)行步驟2。

步驟7：若k==K，表明K個(gè)初始聚類中心選取完畢，記錄當(dāng)前的鄰域半徑集合M（τ）和初始聚類中心集合Z;否則，執(zhí)行步驟4。

1.2? 剔除奇異點(diǎn)

K-means算法迭代過程中，奇異點(diǎn)的存在會(huì)給聚類結(jié)果帶來誤差[13]。當(dāng)樣本集分布呈現(xiàn)簇狀時(shí)，K-means算法能夠取得很好的聚類效果。在簇狀子集中，距離簇中心越遠(yuǎn)的樣本，該樣本的離散度越大，即越有理由認(rèn)定該樣本為樣本集的奇異點(diǎn)。不同數(shù)據(jù)集大小不一且分類數(shù)量不同。為了合理甄別并剔除奇異點(diǎn)，本文基于樣本集的分布規(guī)律以及樣本集的鄰域半徑性質(zhì)，提出一種新的剔除奇異點(diǎn)方法。根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)，本文定義q=K·個(gè)樣本為樣本集的奇異點(diǎn)。在Iris數(shù)據(jù)集中，選取的奇異點(diǎn)數(shù)量為9個(gè)，占數(shù)據(jù)集的比例為6%;在Seed數(shù)據(jù)集中，選取的奇異點(diǎn)數(shù)量為12個(gè)，占數(shù)據(jù)集的比例為5.7%;在Wine數(shù)據(jù)集中，選取的奇異點(diǎn)數(shù)量為12個(gè)，占數(shù)據(jù)集的比例為6.7%。

奇異點(diǎn)分布在較為稀疏的樣本區(qū)域，被選為奇異點(diǎn)的樣本具有與其他樣本差異顯著的特征[14，15]。由定義1和定義2可知，鄰域半徑Ra（τ，xi）越大，樣本xi周圍分布的樣本越稀疏，表明在樣本集X中，樣本xi與其余樣本差異顯著，即可選取樣本xi作為樣本集的奇異點(diǎn)。因此，有：

（1）本文從遴選初始聚類中心步驟7的M（τ）中選取鄰域半徑最大的前q個(gè)樣本作為樣本集的奇異點(diǎn)，記奇異點(diǎn)集為G={g1，g2，g3，…，gq};

（2）在K-means算法的迭代過程中，參與相似性劃分的樣本集為：Y=X/G={y1，y2，y3，…，yt}，其中t=n-q。

1.3? K-means算法與數(shù)據(jù)聚類

由以上分析可知，本文算法可消除奇異點(diǎn)對聚類中心的影響，改進(jìn)的K-means算法具體執(zhí)行步驟為：

步驟1：集合Z中的K個(gè)樣本Z={z1，z2，…，zk}作為改進(jìn)K-means算法的初始聚類中心。

步驟2：在已剔除奇異點(diǎn)的樣本集合Y中，分別求出樣本yi（i=1，2，…，t）與K個(gè)聚類中心的歐式距離Dis{yi，zj}（j=1，2，…，K），記最小歐式距離為dis（yi，zj）=

Dis{yi，zj}，并將樣本yi劃分到第j個(gè)簇Cj，其中Y=C1? C2?…?CK。

步驟3：計(jì)算新的簇中心，其中ci∈Cj，j=1，2，…，K，N（Cj），表示Cj的樣本數(shù)量。

步驟4：若=zj對于j=1，2，…，K均成立，K-means算法迭代完畢，得到最終的聚類中心集合{z1，z2，…，zk}，跳轉(zhuǎn)到步驟5;否則，將新求得的簇中心作為下一次迭代的聚類中心，即令zj=，其中j=1，2，…，K，重新執(zhí)行步驟2。

步驟5：在樣本集X中，根據(jù)樣本xi（i=1，2，…，n）與最終聚類中心{z1，z2，…，zk}的最小歐式距離dis（yi，zj），將樣本xi劃分為第j類，其中j=1，2，…，K。算法結(jié)束，得到樣本集X的K類的聚類結(jié)果。

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

為驗(yàn)證改進(jìn)算法的有效性，本文采用UCI[16]數(shù)據(jù)庫中的Iris、Seed和Wine數(shù)據(jù)集作為數(shù)據(jù)集，并將傳統(tǒng)K-means算法[1]、文獻(xiàn)[17]算法和本文算法的實(shí)驗(yàn)結(jié)果進(jìn)行對比分析。

2.1? 實(shí)驗(yàn)評價(jià)指標(biāo)

本文采用準(zhǔn)確度和迭代次數(shù)作為判定聚類算法性能優(yōu)劣的指標(biāo)。設(shè)原始樣本集聚為K類，則聚類準(zhǔn)確度的計(jì)算公式[12]為：

MP=

n為樣本集數(shù)量，ai表示正確劃分為第i類的樣本數(shù)量，MP值越高，表示聚類的準(zhǔn)確度越高。迭代次數(shù)越少，表示聚類的效率性越高。

2.2? 實(shí)驗(yàn)結(jié)果及其分析

由于K-means算法聚類結(jié)果波動(dòng)性較大，實(shí)驗(yàn)對K-means算法采取多次運(yùn)算求平均值，并與文獻(xiàn)[17]算法和本文提出的算法進(jìn)行對比，以提高實(shí)驗(yàn)結(jié)論的合理性。實(shí)驗(yàn)結(jié)果如表1至表3所示。

Iris數(shù)據(jù)集含有150個(gè)樣本，樣本的屬性維度為4，分為3類。由表1可以看出，在Iris數(shù)據(jù)集中，K-means算法的平均準(zhǔn)確率僅為81.43%，文獻(xiàn)[17]算法的準(zhǔn)確率為89.33%，本文算法的準(zhǔn)確率達(dá)到90.00%，高于K-means算法的平均準(zhǔn)確率和文獻(xiàn)[17]算法的準(zhǔn)確率。且本文算法的迭代為3次，均低于K-means算法和文獻(xiàn)[17]算法，聚類效率性較好。

Seed數(shù)據(jù)集含有210個(gè)樣本，樣本的屬性維度為7，分為3類。由表2可以看出，在Seed數(shù)據(jù)集中，本文算法的準(zhǔn)確率達(dá)到90.95%，在三種算法中效果最佳。且本文算法的迭代次數(shù)為7.0次，低于K-means算法的9.1次和文獻(xiàn)[17]算法的8.0次。

Wine數(shù)據(jù)集含有178個(gè)樣本，樣本的屬性維度為13，分為3類。由表3可以看出，在Wine數(shù)據(jù)集中，K-means算法的準(zhǔn)確率為65.08%，本文算法的準(zhǔn)確率為70.22%，與文獻(xiàn)[17]算法相同，但高于K-means算法的準(zhǔn)確度。且本文算法的迭代次數(shù)為3.00次，對比于前兩種算法，本文算法具有最高的聚類效率性?？梢哉f明，本文算法在Wine數(shù)據(jù)集的聚類性能較良好。

由表1至表3、圖1和圖2可見，改進(jìn)之后的算法總體性能優(yōu)于K-means算法和文獻(xiàn)[17]算法。在Iris、Seed和Wine數(shù)據(jù)集中，對比于傳統(tǒng)K-means算法，本文算法的準(zhǔn)確率分別提高了8.57%、1.64%和5.14%，迭代次數(shù)分別減少了5.25次、2.10次和5.55次;對比于文獻(xiàn)[17]算法，本文算法在Iris和Seed數(shù)據(jù)集的準(zhǔn)確度分別提高了0.67%和1.43%，并在Wine數(shù)據(jù)集取得等效的準(zhǔn)確度，且在迭代次數(shù)方面，本文算法分別減少了4次、1次和2次。

綜上所述，與K-means算法和文獻(xiàn)[17]算法相比，本文算法能取得較好的準(zhǔn)確度，且迭代次數(shù)大幅度下降，聚類效率性高。這是由于本文算法在選取初始聚類中心時(shí)，充分考慮樣本集的整體分布，傾向于選取密集程度較大的樣本作為初始聚類中心，且被選為初始聚類中心的各樣本相互距離較遠(yuǎn)，使得選取為初始聚類中心的樣本更接近于局部簇狀樣本集的中心。在K-means算法迭代過程中，消除了奇異點(diǎn)對聚類中心更新的影響，使算法能夠收斂到較優(yōu)的結(jié)果。

3? 結(jié)? 論

本文提出基于相異性鄰域的改進(jìn)K-means算法，綜合了相異度與歐式距離優(yōu)化數(shù)據(jù)聚類的優(yōu)點(diǎn)，并剔除奇異點(diǎn)的影響，使得算法在準(zhǔn)確度與迭代次數(shù)兩方面的性能提升顯著，具有良好的聚類效果。實(shí)驗(yàn)結(jié)果表明，該算法有效地削弱K-means算法選取初始聚類中心的盲目性，且能消除奇異點(diǎn)對聚類性能的影響，對比于K-means算法，改進(jìn)之后的算法準(zhǔn)確率分別提高了8.57%、1.64%和5.14%，迭代次數(shù)分別減少了5.25次、2.10次和5.55次。

參考文獻(xiàn)：

[1] MACQUEEN J B. Some Methods for Classification and Analysis of Multivariate Observations [C]//Proc. of 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley：Univ.California Press，1967：281-297.

[2] 趙慶.基于Hadoop平臺(tái)下的Canopy-Kmeans高效算法 [J].電子科技，2014，27（2）：29-31.

[3] 高國琴，李明.基于K-means算法的溫室移動(dòng)機(jī)器人導(dǎo)航路徑識(shí)別 [J].農(nóng)業(yè)工程學(xué)報(bào)，2014，30（7）：25-33.

[4] 彭育輝，楊輝寶，李孟良，等.基于K-均值聚類分析的城市道路汽車行駛工況構(gòu)建方法研究 [J].汽車技術(shù)，2017（11）：13-18.

[5] 韓凌波，王強(qiáng)，蔣正鋒，等.一種改進(jìn)的K-means初始聚類中心選取算法 [J].計(jì)算機(jī)工程與應(yīng)用，2010，46（17）：150-152.

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

[7] 唐東凱，王紅梅，胡明.優(yōu)化初始聚類中心的改進(jìn)K-means算法 [J].小型微型計(jì)算機(jī)系統(tǒng)，2018，39（8）：1819-1823.

[8] 李武，趙嬌燕，嚴(yán)太山.基于平均差異度優(yōu)選聚類中心的改進(jìn)K-均值聚類算法 [J].控制與決策，2017，32（4）：759-762.

[9] 楊華暉，孟晨，王成，等.基于目標(biāo)特征選擇和去除的改進(jìn)K-means聚類算法 [J].控制與決策，2019，34（6）：1219-1226.

[10] 劉美玲，黃名選，湯衛(wèi)東.基于離散量優(yōu)化初始聚類中心的K-means算法 [J].計(jì)算機(jī)工程與科學(xué)，2017，39（6）：1164-1170.

[11] 王世其，張文斌，蔡潮森，等.最小局部方差優(yōu)化初始聚類中心的K-means算法 [J].軟件導(dǎo)刊，2020，19（6）：196-200.

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

[13] 蔣麗，薛善良.優(yōu)化初始聚類中心及確定K值的K-means算法 [J].計(jì)算機(jī)與數(shù)字工程，2018，46（1）：21-24+113.

[14] 左進(jìn)，陳澤茂.基于改進(jìn)K均值聚類的異常檢測算法 [J].計(jì)算機(jī)科學(xué)，2016，43（8）：258-261.

[15] 張碩，金鑫，李兆峰，等.基于網(wǎng)絡(luò)LOF和自適應(yīng)K-means的離群點(diǎn)檢測算法 [J].指揮信息系統(tǒng)與技術(shù)，2019，10（1）：90-94.

[16] ASUNCION A，NEWMAN D.UCI Machine Learning Respository [EB/OL].[2015-06-01].http：//archive.ics.uci.edu.

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

作者簡介：李漢波（1999—），男，漢族，廣東茂名人，本科

在讀，研究方向：數(shù)據(jù)挖掘;通訊作者：魏福義（1964—），男，漢族，山西陽泉人，教授，碩士，研究方向：組合矩陣論、人工智能;張嘉龍（2000—），男，漢族，廣東梅州人，本科在讀，研究方向：人工智能;劉志偉（2001—），男，漢族，廣東茂名人，本科在讀，研究方向：人工智能。