Kmeans聚類算法局限性與策略研究

陳文靜

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

【關鍵詞】Kmeans算法 ?局限性 ?解決策略

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

一、Kmeans聚類算法簡介

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

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

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

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

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

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

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

二、Kmeans聚類算法局限性

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

（一）k值的依賴性

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

（二）初始點的依賴性

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

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

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

（四）可擴展性

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

三、Kmeans聚類算法解決策略

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

四、總結

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

參考文獻：

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

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

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

[4]胡威.一種改進的K-means算法在網絡入侵檢測中的應用研究[D].合肥工業大學，2017.

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

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