陳文靜

【摘要】由于Kmeans聚類算法具有簡單且聚類速度較快的特點因而在很多場景中被使用。本文從Kmeans聚類算法出發(fā)，首先對該算法的算法步驟進行簡要描述;然后對該算法存在的局限性進行全面分析;最后針對相應(yīng)的局限性提出對應(yīng)的解決策略。

【關(guān)鍵詞】Kmeans算法 ?局限性 ?解決策略

傳統(tǒng)聚類算法中由于Kmeans聚類算法具有出色的速度和良好的可擴展性，從而使其成為應(yīng)用最廣泛的聚類算法之一。

一、Kmeans聚類算法簡介

Kmeans聚類算法是一個重復(fù)移動類中心點的過程，把類的中心點，也稱重心（centroids），移動到其包含成員的平均位置，然后重新劃分其內(nèi)部成員。Kmeans算法步驟如下：

輸入：樣本集為D={x1，x2，…，xn}，聚類個數(shù)k;

輸出：滿足條件的k個聚類。

（1）從n個數(shù)據(jù)對象中隨機選取k個對象作為初始的聚類中心;

（2）根據(jù)聚類均值（中心對象），計算每個對象與這些聚類中心的距離，并根據(jù)最小距離對相應(yīng)的數(shù)據(jù)對象重新劃分聚類;

（3）更新聚類的均值（中心對象）;

（4）計算適應(yīng)度函數(shù)，并驗證函數(shù)是否收斂或者算法是否終止，如果函數(shù)未收斂或者算法未達到終止次數(shù)，則返回到步驟（2）。

二、Kmeans聚類算法局限性

聚類算法由于算法簡潔易懂，理論可靠、可以處理不同類型的數(shù)據(jù)集等特點使其在人工智能、模式識別、圖像處理、深度學(xué)習(xí)、醫(yī)療、生物工程以及政府等領(lǐng)域被廣泛應(yīng)用。目前聚類算法的分類方式可以采用層次法、劃分法、密度法等進行。然而Kmeans聚類算法仍然存在一定的局限性。分別如下：

（一）k值的依賴性

一般Kmeans算法中k值的選取由用戶自己選定，不同的k值決定了不同的聚類效果。因此，如何選擇合適的k值成為聚類算法準確性的一個因素。如果數(shù)據(jù)集有一定的規(guī)律這對于k值的選取也較為容易。但是如果數(shù)據(jù)集較大且數(shù)據(jù)之間沒有規(guī)律可循則對于k值的選取也就無法準確判斷。研究學(xué)者針對k值的不確定性選取提出了多種改進方法，這為Kmeans算法的深入研究提供了基礎(chǔ)。

（二）初始點的依賴性

Kmeans算法不僅對k值的選取有局限性，同時對聚類算法的初始聚類中心的選取也具有敏感性。如果初始聚類中心選擇不恰當(dāng)，則會使得算法陷入局部最優(yōu)解亦或是算法的適應(yīng)度函數(shù)達不到收斂條件，則會導(dǎo)致算法的迭代次數(shù)增加從而降低了算法的執(zhí)行效率。因此，如何選擇算法的初始聚類中心成為了科研專家的又一研究問題，本文正是基于此問題對Kmeans算法進行改進和優(yōu)化。

（三）對離群點具有敏感性

這里我們將數(shù)據(jù)集中的某條數(shù)據(jù)到數(shù)據(jù)集中的其他數(shù)據(jù)的距離相對較遠的數(shù)據(jù)點稱為離群點。當(dāng)運用離群點計算更新聚類中心時，由于離群點距離聚類中心點的距離較遠，會導(dǎo)致聚類中心更新次數(shù)增加。同時，影響最終聚類結(jié)果的準確性。如果我們選擇將離群點作為Kmeans算法的初始聚類中心則會使算法陷入局部最優(yōu)，而達不到全局最優(yōu)的結(jié)果。

（四）可擴展性

隨著數(shù)據(jù)集不斷增大，Kmeans算法需要更多的迭代次數(shù)以及更多的時間去計算數(shù)據(jù)之間的相似度，這種時間復(fù)雜度以線性方式增長的趨勢對如何處理大規(guī)模的數(shù)據(jù)集提出了挑戰(zhàn)。

三、Kmeans聚類算法解決策略

由于Kmeans聚類算法存在一定的局限性，因此針對Kmeans聚類算法初始聚類中心敏感性問題，研究人員提出了許多改進初始聚類中心的算法。針對Kmeans聚類算法中的聚類K值及初始聚類中心點的敏感性問題，胡威通過研究Kmeans聚類算法的優(yōu)缺點，提出了一種優(yōu)化Kmeans初始聚類中心的方法，并將此方法應(yīng)用于網(wǎng)絡(luò)入侵檢測，實驗證明該檢測結(jié)果相對于傳統(tǒng)的Kmeans聚類算法具有更好的入侵檢測結(jié)果。針對離群點敏感性問題，唐東凱等人使用基于密度的離群點的檢測算法對數(shù)據(jù)的離群點進行篩除，并將最大最小距離算法進行結(jié)合進而在篩選后的樣本選取初始中心。針對算法的可擴展性，魏杰通過借鑒Kmeans聚類算法的思想，為了讓Kmeans算法有更好的擴展性，提出了NCA聚類算法，從而使得該算法可以脫離Kmeans獨立運行。

四、總結(jié)

在眾多聚類算法中，Kmeans聚算法由于其聚類簡單且速度快的優(yōu)勢在許多場景中被使用。本文對Kmeans聚類算法進行了詳細描述，并就算法的局限性及對應(yīng)的解決策略給出了闡述。通過文章的敘述使我們對Kmeans聚類算法有了更詳細的認識并對改進策略有了更多的了解。

參考文獻：

[1]彭長生.基于Fisher判別的分布式K-Means聚類算法[J].江蘇大學(xué)學(xué)報（自然科學(xué)版），2014，（04）.

[2]謝秀華，李陶深.一種基于改進PSO的K-means優(yōu)化聚類算法[J].計算機技術(shù)與發(fā)展，2014，（02）.

[3]劉興亮.基于Hadoop的海量圖書流通數(shù)據(jù)的kmeans分析[D].東華理工大學(xué)， 2015.

[4]胡威.一種改進的K-means算法在網(wǎng)絡(luò)入侵檢測中的應(yīng)用研究[D].合肥工業(yè)大學(xué)，2017.

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

[6]魏杰.基于K-means聚類算法改進算法的研究[J].信息通信，2018，（05）.