K-means聚類算法研究現狀

陳芳敏

摘要： K-means算法是聚類算法中基于劃分的一種典型算法，是數據挖掘的一種常用的數據挖掘方法。該聚類算法容易實現，應用廣泛。但是也有一定的缺點，就是均值不好把握，K的取值很難確定，數據集比較難收斂，隱含類別的數據不平衡等，因此該算法有很多變體，從而很多人對其進行各種改進優化。對此，本文從多個方面闡述K-means算法的改進優化方法，并進行概括其優缺點，分析問題。從而對該方法的發展進行展望。

關鍵詞： K-means算法;數據挖掘;變體;改進優化方法

1 前言

隨著互聯網的迅猛發展，大數據時代是時代進步的產物，是社會發展的必然結果。大數據給我們的生活和工作帶來了很多便捷。大數據使我們的生活變得更加高效、精準，而這些高效和精準歸結于數據挖掘，數據挖掘的基礎則是算法。因此開發更高效的數據挖掘工具和算法來處理不同類型，不同屬性及不同維度的海量數據以支持正確的決策和行動成為了重要研究方向。

K-means聚類算法是聚類算法最為經典的算法，是數據挖掘的重要分支，也是數據挖掘的一個重要研究課題。K-means聚類算法比較容易實現，能夠處理很大量的數據級別的數據，但是也有其確定需要改進優化，如初值的不確定性導致聚類結果的不確定性，均值不好把握等。K-means聚類算法被提出來后，在不同的科學領域被廣泛應用和研究，并不斷發展出大量不同的改進算法和優化方法。雖然K-means聚類方法被提出已經超過了50年，但是該方法仍然是目前應用最廣泛的數據挖掘方法。本文針對K-means聚類算法進行了總結概括，并對該方法的發展進行展望。

2 K-means聚類算法的步驟

K-means聚類算法最早是1957年Lloyd 給出標準算法，最后在此基礎上Lloyd于1982給出了數學證明和算法的詳細步驟? [1]。

K-Means算法過程：

（1）隨機初始化k個聚類中心的位置

（2）計算每一個點到聚類中心的距離，選取最小值分配給k（i）

（3）移動聚類中心（其實就是對所屬它的樣本點求平均值，就是它移動是位置）

（4）重復（2），（3）直到損失函數（也就是所有樣本點到其所歸屬的樣本中心的距離的和最小）

（5）最后整體分類格局會變得穩定。如下圖1

2.1 K-means算法的優化

研究發現一? [2]基于歐式距離的算法優化，是可以使得數據表現更佳。該作者認為基于歐式距離相似度計算基礎上，利用現有的一些算法，從聚類值k大小的確定和初始聚類中心的選取這兩方面進行相應的優化。最后進行數據測試實驗證明了使用 K-means++算法優化時，相比于優化前迭代次數的不穩點性，其迭代次數會相對較小且更趨近于平穩。這說明優化后更具有價值，減少了 K-means 算法的迭代次數。如圖2。

此外不僅中國學者在歐式距離上做優化? [3]，還有外國學者也做了相應的研究。該研究為歐幾里得k-means問題設計了新的差分隱私算法，包括集中模型和差分隱私的局部模型。在這兩個模型中，算法實現了比之前最先進的算法更高的誤差保證。在局部模型中，該研究在算法大大減少了交互的數量。盡管這個問題在差分隱私的背景下已經被廣泛研究，但所有的現有的構造只實現了超常的近似系數。提出了首個針對該問題的具有恒定乘法誤差的時間有效的私有算法。此外，還展示了如何修改算法，使其在兩種模型中都能計算出k-means的私有連環網聚類的私密性。

研究發現二? [4]提出了一種優化初始聚類中心選擇的K-means算法。該算法考慮數據集的分布情況，將樣本點分為孤立點、低密度點和核心點，之后剔除孤立點與低密度點，在核心點中選取初始聚類中心，孤立點不參與聚類過程中各類樣本均值的計算。實驗結果表明，改進的K-means算法能提高聚類的準確率，減少迭代次數，得到更好的聚類結果。K-means算法中對于K個中心點的選取是隨機的，而初始點選取的不同會導致不同的聚類結果。為了減少這種隨機選取初始聚類中心而導致的聚類結果的不穩定性，這種優化初始聚類中心優化方法被很多中外學者反復研究優化。

還有基于密度優化初始聚類中心的。步驟首先給定所需的數據集，并確定聚類個數K;其次計算數據集內所有數據對象的密度，并根據得到數據對象的密度計算數據集的平均密度;然后計算數據集內每個數據對象的最小密度距離值;再者對數據集內數據對象的最小密度距離值進行降序排序，根據確定的聚類個數K，選擇與前K個最小密度距離值對應并且密度大于平均密度的數據對象最為初始聚類中心;最后根據上述獲得的初始聚類中心，利用K-means聚類方法對數據集進行聚類，直至輸出聚類結果。該研究降低計算復雜度，提高分類的準確率，穩定性高，提高快速收斂。以上這些已有研究都圍繞了同一個出發點進行研究改進，都是在解決各自領域上的優化。

研究發現三? [5]提出了各種變體化的研究。如新的差異個體算法，包括集中式模型和差異個體的局部模型。算法實現了比以前最先進的算法有明顯改善的誤差保證。還有量化壓縮的K-Means研究，它旨在從匯集的數據集群中估計出中心點。是將CKM草圖程序推廣到一大類周期性非線性中去，以壓縮的方式獲取整個數據集。 還有極端值的聚類研究，該研究者探討了如何將球形K-means算法應用于分析數據集中的極端觀測值。通過使用多變量極值分析，展示了如何采用它來尋找極值依賴的 "原型"，并為估計器推導出一個一致性結果。更有在波爾上對K-means的算法進行優化。該項研究減少點-中心點距離的計算。另還有研究者通過Ball k-means可以準確地找到每個簇的鄰居球k-means可以準確地找到每個聚類的鄰居聚類，從而只計算一個點和其鄰居中心點。Ball k-means的速度快，沒有額外的參數，設計簡單，研究者認為基于其特點，Ball k-means可以成為k-means算法的全面替代品。但是這是非常片面的，雖然該研究者所研究的Ball k-means方法論中沒有上限或下限的限制，且也減少迭代之間的中心點-中心點距離的計算使得它在大k聚類的效率高，但是該方法是基于所有鄰居球簇都是穩定的，那么穩定區和環形區的劃分與上一次迭代中的劃分相同。在k-means算法的迭代過程中，那就得要求球簇將變得穩定。因為穩定，所以而這些穩定的球簇中的數據點將不會參與到任何距離計算。Ball k-means的時間復雜度每次迭代的時間復雜度將變為亞線性，ball k-means每一次迭代的運行速度會越來越快，這樣會導致很多誤差的存在，甚至影響數據結論。

3 結語

以上研究均是基于K-means的聚類方法上對于相應的研究領域和目的實現了各種優化，使得研究更為高效有效。對已經有幾十年歷史的聚類方法k-means，現在被重新審視，重新優化。K-means和它的許多變種，基本上重新定義了一個k-means。目前本文只是總結了部分關于K-means的優化方法，并沒有很全的參考已有研究的文獻。

在商務上，k-means聚類能幫助市場分析人員從客戶基本庫中發現不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。在生物遺傳學上，k-means聚類能用于推導植物和動物的分類，對基因進行分類，獲得對種群中固有結構的認識。k-means聚類在汽車行業也有很大的幫助分析，在金融行業也發揮了很大的作用。此外還有計算機領域中，也如此。諸如此類，k-means聚類有著廣泛的實際應用。

總體上來說，該方法的優點：屬于無監督學習，無須準備訓練集，原理簡單，實現起來較為容易，結果可解釋性較好。缺點：聚類數目k是一個輸入參數。選擇不恰當的k值可能會導致糟糕的聚類結果。這也是為什么要進行特征檢查來決定數據集的聚類數目了。可能收斂到局部最小值， 在大規模數據集上收斂較慢，對于異常點、離群點敏感。而且k-means聚類算法目前實驗數據都是在小規模的例子上運行，這樣是遠遠不夠的。現在是大數據發展時代，數據量非常龐大，我們必須要求k-means聚類算法的性能能延伸到大的數據集上，要高效的算法。

本文通過對K-means算法應用廣泛總結，分別對依賴于初始化，聚類結果隨初始中心的變化而波動，難以保證優良的性能，基于密度，有效改進了初始中心點的選取，克服了傳統算法敏感且聚類效果容易陷入局部最優的缺陷等一系列關于K-means的研究總結。總結出了K-means的優缺點。

參考文獻

[1]? LLOYD S.Least squares quantization in PCM[J].IEEE Transaction Information Theory，1982，28（2）：129-137.

[2] 李輪，宋文廣，沈翀，張偉委，鄧健.基于歐氏距離K-means算法優化[J].中國科技論文在線精品論文，2019，12（06）：889-895.

[3] Haim Kaplan，Uri Stemmer.Differentially Private k-Means with Constant Multiplicative Error.[J]

[4] 楊一帆，賀國先，李永定. 優化初始聚類中心選擇的K-means算法[J].電腦知識與技術，2021，17（05）：252-255.

[5] Vincent Schellekens，Laurent Jacques. Quantized Compressive K-Means[J]，2018.6