李豐兵

摘 ?要：K均值算法是以隨機的方式選擇初始聚類中心，這使得K均值算法容易陷入局部最優(yōu)，收斂性能不穩(wěn)定。針對這一缺陷，該文對K均值算法進行改進，提出一種逐步選擇距離差異極大的個體作為初始聚類中心的算法。實驗結(jié)果表明，改進后的算法收斂性能確實比K均值算法優(yōu)越。

關(guān)鍵詞：K均值算法 ?聚類中心 ?局部最優(yōu) ?收斂性

中圖分類號：TP311.13 ? 文獻標(biāo)識碼：A ? ? ? ? ? ? 文章編號：1672-3791（2019）05（c）-0185-03

Abstract： K-means algorithm chooses initial clustering centers randomly， which makes K-means algorithm easy to fall into local optimum and its convergence performance unstable. In order to overcome this shortcoming， an improved K-means algorithm has been proposed in this paper， which chooses gradually individuals with great distance difference as the initial clustering center. The experimental results show that the improved algorithm has better convergence performance than K-means algorithm.

Key Words： K-means algorithm; Clustering center; Local optimum; Convergence

K均值算法是21世紀(jì)十大機器學(xué)習(xí)算法之一，是1967年由麥奎因（MacQueen）提出并命名的一種簡單、高效的快速聚類算法，廣泛地應(yīng)用于數(shù)據(jù)挖掘、模式識別及計算機視覺等領(lǐng)域[1-3]。目前，K均值算法仍然是人工智能及機器學(xué)習(xí)領(lǐng)域的一個研究熱點，國內(nèi)外已存在諸多與K均值算法密切相關(guān)的研究工作，其中，有部分研究工作集中在K均值算法的改進問題上[4-8]。眾所周知，K均值算法存在兩個主要的缺陷，其中一個缺陷就是以隨機的方式選擇初始聚類中心，而不同的初始聚類中心可能會導(dǎo)致不同的聚類結(jié)果，即K均值算法容易陷入局部最優(yōu)，聚類效果依賴于初始聚類中心的選擇，這種情況如圖1所示。

在圖1中，左上圖和左下圖分別表示兩種不同的初始聚類中心的選擇，這里所用的數(shù)據(jù)集是相同的，劃分類別數(shù)均為3，右上圖和右下圖則分別表示對應(yīng)的聚類結(jié)果。顯然，由圖1可直觀地看出，選擇不同初始聚類中心導(dǎo)致K均值算法聚類結(jié)果不同。因此，K均值算法是一種局部收斂算法，穩(wěn)定性及精確性都有待于進一步提高和完善。

1 ?K均值算法的改進

為改善K均值算法（為避免混淆，以下稱經(jīng)典K均值算法）的上述缺陷，該文提出一種新的初始聚類中心的選擇算法。該算法的思想是以類與類之間存在較大差異為根據(jù)，通過迭代搜索逐步確定具有較大距離間隔的初始聚類中心，具體步驟如下。

步4：確定集合C中所有個體與重心的最小距離dmin=min{di|i∈IC}及集合中所有個體與重心的最大距離dmax=min{di|i∈I}。

步5：若dmax-dmin<δ中，則算法停止迭代，集合C中的個體即為K均值算法的初始聚類中心，否則將集合C中個體Xmin與集合中個體Xmax互換，并轉(zhuǎn)第3步。

以圖1中的數(shù)據(jù)集為例，利用該改進方法，可求得初始聚類中心，如圖2所示。

從圖2中可直觀看出，改進算法確定3個初始聚類中心從位置分布上看非常分散。以這種極度分散的初始聚類中心進行聚類，可以減緩K均值算法陷入局部最優(yōu)的可能，下面的實驗仿真可以說明這一問題。

2 ?實驗仿真

為了驗證改進的K均值算法的有效性，下面采用UCI數(shù)據(jù)庫中的標(biāo)準(zhǔn)數(shù)據(jù)Iris對經(jīng)典K均值算法和改進的K均值算法進行對比實驗。Iris數(shù)據(jù)也稱為鳶尾花卉數(shù)據(jù)，是Fisher于1936收集整理的，常用來作為模式分類實驗數(shù)據(jù)集。Iris數(shù)據(jù)集共包含3類鳶尾花卉數(shù)據(jù)（Setosa，Versicolour，Virginica），每一類均包含50個樣本個體數(shù)據(jù)，每個個體數(shù)據(jù)又包含4個屬性，分別為：Sepal.Length、Sepal.Width、Petal.Length及Petal.Width。實驗方法如下，取劃分類別數(shù)k=3，計算精度值δ=0.01，分別對經(jīng)典K均值算法和改進的K均值算法進行50次實驗，記錄每次實驗的分類結(jié)果及錯分個體數(shù)。

實驗結(jié)果如下，經(jīng)典K均值算法共出現(xiàn)兩種聚類結(jié)果，其中有37次實驗結(jié)果如圖3的左圖所示，其余13次實驗結(jié)果如圖3的右圖所示，而改進的K均值算法只有圖3的左圖一種結(jié)果（這里為了演示方便、簡潔，只畫出鳶尾花卉數(shù)據(jù)的兩種屬性平面圖）。由此可知，改進的K均值算法比經(jīng)典K均值算法穩(wěn)定性要好。另外，從聚類精度來看，改進的K均值算法每次錯分樣本個體數(shù)均為18，而經(jīng)典K均值算法有37次實驗中錯分個體數(shù)為18，其余13次錯分個體數(shù)達到92，總共150個個體數(shù)據(jù)，換算成錯分率后結(jié)果如圖4所示。

從圖4中可直觀看出，改進的K均值算法錯分率穩(wěn)定在10%附近，而經(jīng)典K均值算法竟然有13次錯分率超過50%，由此可知，改進的K均值算法比經(jīng)典K均值算法聚類結(jié)果更加準(zhǔn)確。

3 ?結(jié)語

該文針對經(jīng)典K均值算法隨機選擇初始聚類中心的缺陷進行改進，提出一種利用逐步迭代的方式選擇距離差異極大的個體作為初始聚類中心的算法。利用UCI數(shù)據(jù)庫中的標(biāo)準(zhǔn)數(shù)據(jù)Iris進行50次對比實驗，結(jié)果表明改進的K均值算法不但穩(wěn)定性比經(jīng)典K均值算法要好，而且聚類精度也比經(jīng)典K均值算法要高。盡管如此，改進的K均值算法仍需做進一步研究，算法的收斂性能有待于進一步提高。

參考文獻

[1] Mourade Azrour， Yousef Farhaoui， Mohammed Ouanan， et al.SPIT Detection in Telephony over IP Using K-Means Algorithm[J].Procedia Computer Science， 2019（148）：542-551.

[2] Tanvir Habib Sardar， Zahid Ansari.An analysis of MapReduce efficiency in document clustering using parallel K-means algorithm[J].Future Computing and Informatics Journal，2018，3（2）：200-209.

[3] Kisoo Kwon， Jong Won Shin， Nam Soo Kim. Incremental basis estimation adopting global k-means algorithm for NMF-based noise reduction[J].Applied Acoustics， 2018（129）：277-283.

[4] 賈瑞玉，李玉功.類簇數(shù)目和初始中心點自確定的K-means算法[J].計算機工程與應(yīng)用，2018，54（7）：152-158.

[5] Shyr Shen Yu， Shao Wei Chu， Chuin Mu Wang， et al.Two improved k-means algorithms[J].Applied Soft Computing，2018（68）：747-755.

[6] Geng Zhang，Chengchang Zhang， Huayu Zhang.Improved K-means algorithm based on density Canopy[J].Knowledge-Based Systems，2018（145）：289-297.

[7] 謝娟英，王艷娥.最小方差優(yōu)化初始聚類中心的K-means算法[J].計算機工程，2014，40（8）：205-211，223.

[8] 邢長征，谷浩.基于平均密度優(yōu)化初始聚類中心的k-means算法[J].計算機工程與應(yīng)用，2014，50（20）：135-138.