K-means聚類算法研究現(xiàn)狀

陳芳敏

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

關(guān)鍵詞： K-means算法;數(shù)據(jù)挖掘;變體;改進(jìn)優(yōu)化方法

1 前言

隨著互聯(lián)網(wǎng)的迅猛發(fā)展，大數(shù)據(jù)時(shí)代是時(shí)代進(jìn)步的產(chǎn)物，是社會(huì)發(fā)展的必然結(jié)果。大數(shù)據(jù)給我們的生活和工作帶來(lái)了很多便捷。大數(shù)據(jù)使我們的生活變得更加高效、精準(zhǔn)，而這些高效和精準(zhǔn)歸結(jié)于數(shù)據(jù)挖掘，數(shù)據(jù)挖掘的基礎(chǔ)則是算法。因此開(kāi)發(fā)更高效的數(shù)據(jù)挖掘工具和算法來(lái)處理不同類型，不同屬性及不同維度的海量數(shù)據(jù)以支持正確的決策和行動(dòng)成為了重要研究方向。

K-means聚類算法是聚類算法最為經(jīng)典的算法，是數(shù)據(jù)挖掘的重要分支，也是數(shù)據(jù)挖掘的一個(gè)重要研究課題。K-means聚類算法比較容易實(shí)現(xiàn)，能夠處理很大量的數(shù)據(jù)級(jí)別的數(shù)據(jù)，但是也有其確定需要改進(jìn)優(yōu)化，如初值的不確定性導(dǎo)致聚類結(jié)果的不確定性，均值不好把握等。K-means聚類算法被提出來(lái)后，在不同的科學(xué)領(lǐng)域被廣泛應(yīng)用和研究，并不斷發(fā)展出大量不同的改進(jìn)算法和優(yōu)化方法。雖然K-means聚類方法被提出已經(jīng)超過(guò)了50年，但是該方法仍然是目前應(yīng)用最廣泛的數(shù)據(jù)挖掘方法。本文針對(duì)K-means聚類算法進(jìn)行了總結(jié)概括，并對(duì)該方法的發(fā)展進(jìn)行展望。

2 K-means聚類算法的步驟

K-means聚類算法最早是1957年Lloyd 給出標(biāo)準(zhǔn)算法，最后在此基礎(chǔ)上Lloyd于1982給出了數(shù)學(xué)證明和算法的詳細(xì)步驟? [1]。

K-Means算法過(guò)程：

（1）隨機(jī)初始化k個(gè)聚類中心的位置

（2）計(jì)算每一個(gè)點(diǎn)到聚類中心的距離，選取最小值分配給k（i）

（3）移動(dòng)聚類中心（其實(shí)就是對(duì)所屬它的樣本點(diǎn)求平均值，就是它移動(dòng)是位置）

（4）重復(fù)（2），（3）直到損失函數(shù)（也就是所有樣本點(diǎn)到其所歸屬的樣本中心的距離的和最?。?/p>

（5）最后整體分類格局會(huì)變得穩(wěn)定。如下圖1

2.1 K-means算法的優(yōu)化

研究發(fā)現(xiàn)一? [2]基于歐式距離的算法優(yōu)化，是可以使得數(shù)據(jù)表現(xiàn)更佳。該作者認(rèn)為基于歐式距離相似度計(jì)算基礎(chǔ)上，利用現(xiàn)有的一些算法，從聚類值k大小的確定和初始聚類中心的選取這兩方面進(jìn)行相應(yīng)的優(yōu)化。最后進(jìn)行數(shù)據(jù)測(cè)試實(shí)驗(yàn)證明了使用 K-means++算法優(yōu)化時(shí)，相比于優(yōu)化前迭代次數(shù)的不穩(wěn)點(diǎn)性，其迭代次數(shù)會(huì)相對(duì)較小且更趨近于平穩(wěn)。這說(shuō)明優(yōu)化后更具有價(jià)值，減少了 K-means 算法的迭代次數(shù)。如圖2。

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

研究發(fā)現(xiàn)二? [4]提出了一種優(yōu)化初始聚類中心選擇的K-means算法。該算法考慮數(shù)據(jù)集的分布情況，將樣本點(diǎn)分為孤立點(diǎn)、低密度點(diǎn)和核心點(diǎn)，之后剔除孤立點(diǎn)與低密度點(diǎn)，在核心點(diǎn)中選取初始聚類中心，孤立點(diǎn)不參與聚類過(guò)程中各類樣本均值的計(jì)算。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的K-means算法能提高聚類的準(zhǔn)確率，減少迭代次數(shù)，得到更好的聚類結(jié)果。K-means算法中對(duì)于K個(gè)中心點(diǎn)的選取是隨機(jī)的，而初始點(diǎn)選取的不同會(huì)導(dǎo)致不同的聚類結(jié)果。為了減少這種隨機(jī)選取初始聚類中心而導(dǎo)致的聚類結(jié)果的不穩(wěn)定性，這種優(yōu)化初始聚類中心優(yōu)化方法被很多中外學(xué)者反復(fù)研究?jī)?yōu)化。

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

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

3 結(jié)語(yǔ)

以上研究均是基于K-means的聚類方法上對(duì)于相應(yīng)的研究領(lǐng)域和目的實(shí)現(xiàn)了各種優(yōu)化，使得研究更為高效有效。對(duì)已經(jīng)有幾十年歷史的聚類方法k-means，現(xiàn)在被重新審視，重新優(yōu)化。K-means和它的許多變種，基本上重新定義了一個(gè)k-means。目前本文只是總結(jié)了部分關(guān)于K-means的優(yōu)化方法，并沒(méi)有很全的參考已有研究的文獻(xiàn)。

在商務(wù)上，k-means聚類能幫助市場(chǎng)分析人員從客戶基本庫(kù)中發(fā)現(xiàn)不同的客戶群，并且用購(gòu)買模式來(lái)刻畫(huà)不同的客戶群的特征。在生物遺傳學(xué)上，k-means聚類能用于推導(dǎo)植物和動(dòng)物的分類，對(duì)基因進(jìn)行分類，獲得對(duì)種群中固有結(jié)構(gòu)的認(rèn)識(shí)。k-means聚類在汽車行業(yè)也有很大的幫助分析，在金融行業(yè)也發(fā)揮了很大的作用。此外還有計(jì)算機(jī)領(lǐng)域中，也如此。諸如此類，k-means聚類有著廣泛的實(shí)際應(yīng)用。

總體上來(lái)說(shuō)，該方法的優(yōu)點(diǎn)：屬于無(wú)監(jiān)督學(xué)習(xí)，無(wú)須準(zhǔn)備訓(xùn)練集，原理簡(jiǎn)單，實(shí)現(xiàn)起來(lái)較為容易，結(jié)果可解釋性較好。缺點(diǎn)：聚類數(shù)目k是一個(gè)輸入?yún)?shù)。選擇不恰當(dāng)?shù)膋值可能會(huì)導(dǎo)致糟糕的聚類結(jié)果。這也是為什么要進(jìn)行特征檢查來(lái)決定數(shù)據(jù)集的聚類數(shù)目了?？赡苁諗康骄植孔钚≈担?在大規(guī)模數(shù)據(jù)集上收斂較慢，對(duì)于異常點(diǎn)、離群點(diǎn)敏感。而且k-means聚類算法目前實(shí)驗(yàn)數(shù)據(jù)都是在小規(guī)模的例子上運(yùn)行，這樣是遠(yuǎn)遠(yuǎn)不夠的?，F(xiàn)在是大數(shù)據(jù)發(fā)展時(shí)代，數(shù)據(jù)量非常龐大，我們必須要求k-means聚類算法的性能能延伸到大的數(shù)據(jù)集上，要高效的算法。

本文通過(guò)對(duì)K-means算法應(yīng)用廣泛總結(jié)，分別對(duì)依賴于初始化，聚類結(jié)果隨初始中心的變化而波動(dòng)，難以保證優(yōu)良的性能，基于密度，有效改進(jìn)了初始中心點(diǎn)的選取，克服了傳統(tǒng)算法敏感且聚類效果容易陷入局部最優(yōu)的缺陷等一系列關(guān)于K-means的研究總結(jié)?？偨Y(jié)出了K-means的優(yōu)缺點(diǎn)。

參考文獻(xiàn)

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

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

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

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

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