基于相異性鄰域的改進K-means算法

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

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

關鍵詞：K-means聚類;相異度;鄰域半徑;初始聚類中心;奇異點

中圖分類號：TP273.4? ? 文獻標識碼：A? ? 文章編號：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

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

0? 引? 言

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

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

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

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

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

1.1? 改進的初始聚類中心選取算法

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

1.1.1? 相關概念

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

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

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

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

rij=

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

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

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

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

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

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

當樣本xi的τ鄰域半徑Ra（τ，xi）大于平均鄰域半徑m（τ）時，可認為樣本xi周圍分布的樣本較為稀疏。

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

作為K-means算法初始聚類中心改進方法，需要選取周圍樣本分布較密集的樣本，樣本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個樣本。

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

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

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

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

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

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

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

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

1.2? 剔除奇異點

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

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

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

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

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

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

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

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

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

步驟3：計算新的簇中心，其中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? 實驗結(jié)果與分析

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

2.1? 實驗評價指標

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

MP=

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

2.2? 實驗結(jié)果及其分析

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

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

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

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

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

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

3? 結(jié)? 論

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

參考文獻：

[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平臺下的Canopy-Kmeans高效算法 [J].電子科技，2014，27（2）：29-31.

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

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

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

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

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

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

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

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

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

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

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

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

[15] 張碩，金鑫，李兆峰，等.基于網(wǎng)絡LOF和自適應K-means的離群點檢測算法 [J].指揮信息系統(tǒng)與技術，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)化初始聚類中心的自適應聚類算法 [J].軟件導刊，2020，19（7）：28-31.

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

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