K-means算法研究綜述

叢思安 王星星

摘要

k-means算法是一種非常簡(jiǎn)單并且使用廣泛的聚類(lèi)算法，但是一是k值需要預(yù)先給定，很多情況下k值的佑計(jì)很困難。二是K-Means算法對(duì)初始選取的聚類(lèi)中心點(diǎn)很敏感，不同的中心點(diǎn)聚類(lèi)結(jié)果有很大的不同。也就是說(shuō)，有可能陷入局部最優(yōu)解。三是對(duì)離群點(diǎn)敏感，聚類(lèi)結(jié)果易產(chǎn)生誤差。四是相似性度量的函數(shù)不同也會(huì)對(duì)聚類(lèi)結(jié)果產(chǎn)生影響。本文針對(duì)k-means的缺陷，對(duì)這幾年k-means算法的研究進(jìn)展進(jìn)行了綜述。從初始中心點(diǎn)的選取、離群點(diǎn)的檢測(cè)與去除、相似性度量等幾個(gè)方面進(jìn)行概括、比較最后，對(duì)k-means算法的未來(lái)趨勢(shì)進(jìn)行展望。

【關(guān)鍵詞】k-means算法 初始聚類(lèi)中心 相似性度量 離群點(diǎn)

K-means聚類(lèi)算法是由Steinhaus 1955年、Lloyd 1957年、Ball&Hall; 1965年、McQueen1967年分別在各自的不同的科學(xué)研究領(lǐng)域獨(dú)立的提出。K-means聚類(lèi)算法被提出來(lái)后，經(jīng)過(guò)多年的實(shí)踐證明，k-means算法依然是簡(jiǎn)單、高效的算法，并且被廣泛應(yīng)用在科學(xué)研究以及工業(yè)應(yīng)用中，發(fā)展出大量的改進(jìn)的算法。目前，k-means算法仍然是一個(gè)研究熱點(diǎn)。

K-means算法的改進(jìn)主要從以下幾個(gè)方面：一是如何確定合適的k值，二是如何選取好的初始聚類(lèi)中心，三是離群點(diǎn)的檢測(cè)與去除，四是距離與相似度度量的改進(jìn)以及其他方面的改進(jìn)等等。本文則從以上幾個(gè)方面對(duì)k-means算法的研究進(jìn)展進(jìn)行綜述。本文第一部分介紹傳統(tǒng)的k-means算法，第二部分從各個(gè)方面介紹k-means算法的優(yōu)化，第三部分進(jìn)行總結(jié)以及展望。

1 傳統(tǒng)的k-means算法

K-means算法是一種簡(jiǎn)單、高效的聚類(lèi)算法，并得到了廣泛的應(yīng)用。K-means算法的基本思想是首先隨機(jī)選取初始聚類(lèi)中心，然后計(jì)算每個(gè)樣本點(diǎn)到初始聚類(lèi)中心的歐式距離，按照距離最近的準(zhǔn)則將它們分配給相似度最大的聚類(lèi)中心所代表的類(lèi)。計(jì)算每個(gè)類(lèi)別所有樣本點(diǎn)的均值，更新聚類(lèi)中心，直到目標(biāo)準(zhǔn)則函數(shù)收斂為止。具體算法步驟如下：

（1）用戶(hù)輸入類(lèi)簇?cái)?shù)目的值k，從n個(gè)樣本點(diǎn)中隨機(jī)選取k個(gè)點(diǎn)作為初始聚類(lèi)中心;

（2）遍歷所有的樣本點(diǎn)，計(jì)算每個(gè)樣本點(diǎn)到初始聚類(lèi)中心的歐式距離，歐氏距離的大小作為相似度的評(píng)判標(biāo)準(zhǔn)，歐氏距離越小，相似度越大。按照距離最近的準(zhǔn)則將樣本點(diǎn)分配給相似度最大的聚類(lèi)中心所代表的類(lèi)。

（3）重新確定聚類(lèi)中心。將每個(gè)類(lèi)簇中的所有樣本點(diǎn)的均值作為新的聚類(lèi)中心。

（4）重復(fù)（2）和（3），直到聚類(lèi)中心不再發(fā)生變化。

2 k-means算法的改進(jìn)

2.1 初始聚類(lèi)中心的選取

初始聚類(lèi)中心的選取對(duì)k-means算法聚類(lèi)結(jié)果的影響很大，不同的初始聚類(lèi)中心，可能會(huì)產(chǎn)生不同的聚類(lèi)結(jié)果。也可以說(shuō)，k-means算法是一種貪心算法，容易陷入局部最優(yōu)解。

賈瑞玉等人[2]主要運(yùn)用了Rodriguez A等人[3]提出的類(lèi)簇中心都處在局部密度比較大的位置，且距離具有比它更大的局部密度的對(duì)象相對(duì)較遠(yuǎn)的思想。運(yùn)用此思想可以確定最佳初始聚類(lèi)中心及數(shù)據(jù)集的最佳類(lèi)簇?cái)?shù)目。賈瑞玉等人在這個(gè)思想的基礎(chǔ)上，為了避免密度對(duì)截?cái)嗑嚯x的依賴(lài)性，重新定義了計(jì)算樣本局部密度ρ_i的方法，計(jì)算樣本點(diǎn)到具有比它更高的局部密度數(shù)據(jù)對(duì)象的最近距離δ_i（當(dāng)樣本點(diǎn)x_i是數(shù)據(jù)集中具有最大局部密度的樣本點(diǎn)時(shí)，δ_i定義為x_i和距離他最遠(yuǎn)的樣本點(diǎn)之間的歐氏距離）。根據(jù)ρ_i和δ_i構(gòu)造決策圖，運(yùn)用統(tǒng)計(jì)學(xué)中殘差分析的方法，選取殘差絕對(duì)值大于閾值的異常點(diǎn)，即為聚類(lèi)中心。在二維以及高維數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果均驗(yàn)證了該算法的有效性。但是不足之處在于這個(gè)算法適用于比較集中的數(shù)據(jù)集，稀疏的數(shù)據(jù)集結(jié)果并不理想。

Lei Gu[4]等人采用減法聚類(lèi)的算法確定初始聚類(lèi)中心。首先是計(jì)算每個(gè)樣本點(diǎn)的山峰函數(shù)值，選取山峰函數(shù)值最大的點(diǎn)作為聚類(lèi)中心。選取下一個(gè)聚類(lèi)中心時(shí)要消除已經(jīng)確定的聚類(lèi)中心的影響，就修改山峰函數(shù)，減去上一個(gè)確定的聚類(lèi)中心的比例高斯函數(shù)，如此反復(fù)，直到得到足夠多的聚類(lèi)中心。這個(gè)方法的缺點(diǎn)在于對(duì)于離群點(diǎn)、異常值抗干擾能力比較弱，且需要設(shè)置的參數(shù)較多（一般需要3個(gè)）。

M.S.Premkumar等人[5]采用了四分位數(shù)的概念來(lái)確定初始聚類(lèi)中心。首先采用特征選擇的方法選取數(shù)據(jù)有意義的屬性。然后將將屬性的值按照順序排列，以分成兩類(lèi)為例，將數(shù)據(jù)集的上四分位點(diǎn)和下四分位點(diǎn)作為初始聚類(lèi)中心，計(jì)算所有樣本點(diǎn)到到這兩個(gè)聚類(lèi)中心的距離，進(jìn)行分類(lèi);接下來(lái)更新聚類(lèi)中心，將每類(lèi)所有樣本點(diǎn)的均值作為新的聚類(lèi)中心，直到類(lèi)簇不再發(fā)生變化。這個(gè)方法不足之處是當(dāng)數(shù)據(jù)集比較大時(shí)，花費(fèi)時(shí)間會(huì)比較長(zhǎng)。

C.Lasheng等人[6]首先是采用最大一最小準(zhǔn)則算法初步確定初始聚類(lèi)中心，然后通過(guò)FLANT（快速最近鄰搜索庫(kù)）將聚類(lèi)中心偏移到盡可能地靠近實(shí)際的聚類(lèi)中心。最大一最小準(zhǔn)則算法是首先隨機(jī)選取一個(gè)點(diǎn)作為第一個(gè)聚類(lèi)中心，選取距離這個(gè)點(diǎn)最遠(yuǎn)的點(diǎn)作為第二個(gè)聚類(lèi)中心，然后計(jì)算每個(gè)點(diǎn)到這兩個(gè)聚類(lèi)中心的距離，選取較小的距離加入到集合V中，在集合V中選取距離最遠(yuǎn)的點(diǎn)作為下一個(gè)聚類(lèi)中心，依次類(lèi)推，直到最大最小距離不大于θ·D_1，2（C_1，2為第一個(gè)和第二個(gè)聚類(lèi)中心的距離）。FLANT是一個(gè)在高維空間中快速搜索k個(gè)最近鄰居的庫(kù)。使用FLANT找到聚類(lèi)中心的k近鄰，計(jì)算中心點(diǎn)即為新的聚類(lèi)中心。

2.2 距離和相似性度量

傳統(tǒng)的k-means算法使用歐幾里得距離來(lái)度量相似度。陳磊磊[7]采用了歐式距離、平方歐式距離、曼哈頓距離、余弦距離、谷本距離分別作為相似度度量對(duì)文本數(shù)據(jù)進(jìn)行處理，實(shí)驗(yàn)結(jié)果顯示余弦距離、谷本距離者在文本聚類(lèi)中的表現(xiàn)更優(yōu)。不同的測(cè)度距離作為相似性度量對(duì)聚類(lèi)結(jié)果會(huì)產(chǎn)生不同的影響，對(duì)于不同類(lèi)型的數(shù)據(jù)也應(yīng)采用不同的距離函數(shù)作為相似度度量。

W.Xue等人[8]針對(duì)k-means算法不能求解非線性流形聚類(lèi)的缺陷，提出了用空間密度相似性度量來(lái)代替歐幾里得距離，使k-means算法能夠適應(yīng)數(shù)據(jù)集的分布。同一簇中的數(shù)據(jù)點(diǎn)應(yīng)位于高密度區(qū)域，不同簇中的數(shù)據(jù)點(diǎn)應(yīng)該用低密度區(qū)域分隔開(kāi)來(lái)。所以需要壓縮高密度區(qū)域的距離，放大低密度區(qū)域的距離。作者在文中定義了空間密度長(zhǎng)度公式L（i，j）。通過(guò)連接點(diǎn)i和j定義圖G，其中點(diǎn)i為j的k近鄰點(diǎn)。對(duì)于近距離的兩個(gè)點(diǎn)，使用L（i，j）的值作為邊長(zhǎng)，對(duì)于遠(yuǎn)距離的兩個(gè)點(diǎn)，則設(shè)置短跳（i通過(guò)一個(gè)或者多個(gè)中間點(diǎn)到達(dá)j），求最短路徑為遠(yuǎn)距離兩個(gè)點(diǎn)的距離值。這種方法能夠有效的對(duì)非線性聚類(lèi)中心進(jìn)行求解。

J.P.Singh和N.Bouguila[9]針對(duì)比例數(shù)據(jù)，提出用Aitchison距離度量來(lái)對(duì)比例數(shù)據(jù)進(jìn)行聚類(lèi)。作者使用Aitchison距離、歐幾里德對(duì)數(shù)距離、余弦距離、Kullback距離、Matisuita距離進(jìn)行了對(duì)比實(shí)驗(yàn)，文本聚類(lèi)結(jié)果顯示Aitchison距離度量最適合所有，因?yàn)檩^高的輪廓值，聚類(lèi)更合適。對(duì)于圖像比例數(shù)據(jù)聚類(lèi)，使用Aitchison距離作為初始化步驟可以提供適用于比例數(shù)據(jù)的更好的混合結(jié)果。

2.3 離群點(diǎn)的檢測(cè)

K-means算法對(duì)于離群點(diǎn)敏感，對(duì)聚類(lèi)結(jié)果產(chǎn)生很大的影響，因此離群點(diǎn)的檢測(cè)與刪除極為重要。

Breunig等人[10]的基于密度的方法是一種流行的異常值檢測(cè)方法。它計(jì)算每個(gè)點(diǎn)的局部離群因子（LOF）。一個(gè)點(diǎn)的LOF是基于該點(diǎn)附近區(qū)域的密度和它的鄰居的局部密度的比值。LOF方法依賴(lài)于用戶(hù)提供的最小數(shù)量點(diǎn)，用于確定鄰居的大小。

K.Zhang等人[11]建立了一個(gè)基于本地距離的離群因子（LDOF）來(lái)測(cè)量分散的數(shù)據(jù)集對(duì)象的離群程度。LDOF使用一個(gè)對(duì)象到它的鄰居的相對(duì)位置，以確定物體偏離其鄰近區(qū)域的程度。為了方便實(shí)際應(yīng)用中的參數(shù)設(shè)置，作者在離群值檢測(cè)方法中使用了一種top-n技術(shù)，其中只有具有最高值的對(duì)象才被視為離群值。與傳統(tǒng)的方法（如前n和頂n）相比，方法是在分散的數(shù)據(jù)中檢測(cè)出離群值。

Ting Zhang等人[12]提出了通過(guò)添加上限范數(shù)和一種有效的迭代重加權(quán)算法，來(lái)減小離群點(diǎn)的影響。離群點(diǎn)的檢測(cè)發(fā)生在每次聚類(lèi)中心迭代時(shí)，每個(gè)樣本點(diǎn)到聚類(lèi)中心的距離大于給定的參數(shù)ε，便會(huì)被去除。并且重新給樣本分配權(quán)重，低錯(cuò)誤率的樣本具有更高的權(quán)重。這個(gè)方面的缺陷在于參數(shù)ε需要人為的設(shè)置與調(diào)整，不同的ε值導(dǎo)致的聚類(lèi)結(jié)果準(zhǔn)確率不同。

P.O.Olukanmi and B.Twala[13]提出了k-means-sharp算法，通過(guò)從點(diǎn)到質(zhì)心距離的分布得到的全局閾值自動(dòng)檢測(cè)離群點(diǎn)。離群點(diǎn)檢測(cè)過(guò)程和聚類(lèi)過(guò)程同時(shí)完成。假設(shè)k-means的數(shù)據(jù)呈高斯分布，離群點(diǎn)檢測(cè)發(fā)生在每次聚類(lèi)中心更新時(shí)，計(jì)算每個(gè)樣本點(diǎn)到聚類(lèi)中心的距離，如果距離大于3σ，則為離群點(diǎn)，其中σ=1.4826MADe，MADe為每個(gè)點(diǎn)到中值點(diǎn)的距離組成的所有數(shù)據(jù)的中值點(diǎn)。因此，每次更新聚類(lèi)中心時(shí)，就會(huì)去除一部分離群點(diǎn)。

2.4 k-means算法的其他改進(jìn)

最近幾年出現(xiàn)了遺傳算法、粒子群算法、螢火蟲(chóng)算法、蟻群算法等與傳統(tǒng)的kmeans算法相結(jié)合的改進(jìn)算法，這幾類(lèi)算法的共同點(diǎn)是具有一定的全局優(yōu)化能力，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。通常是使用這些算法來(lái)尋找k-means算法的初始聚類(lèi)中心。

Kapil等人[14]的實(shí)驗(yàn)結(jié)果顯示，和遺傳算法結(jié)合的k-means算法優(yōu)于k-means算法。遺傳k-means算法就是把每個(gè)聚類(lèi)中心坐標(biāo)當(dāng)成染色體基因。聚類(lèi)中心個(gè)數(shù)就是染色體長(zhǎng)度，對(duì)若干相異染色體進(jìn)行初始化操作并將其當(dāng)成一個(gè)種群進(jìn)行遺傳操作，最終獲得適應(yīng)度最大染色體，而最優(yōu)聚類(lèi)中心坐標(biāo)就是解析出的各中心點(diǎn)坐標(biāo)。

沈艷等人[15]將粒子群算法與k-means算法結(jié)合，提出多子群多于多子群粒子群偽均值（PK-means）聚類(lèi)算法，理論分析和實(shí)驗(yàn)表明，該算法不但可以防止空類(lèi)出現(xiàn)，而且同時(shí)還具有非常好的全局收斂性和局部尋優(yōu)能力，并且在孤立點(diǎn)問(wèn)題的處理上也具有很好的效果。

陳小雪等人[16]提出了一種基于螢火蟲(chóng)優(yōu)化的加權(quán)K-means算法。該算法在提升聚類(lèi)性能的同時(shí)，有效增強(qiáng)了算法的收斂速度。在實(shí)驗(yàn)階段，通過(guò)UCI數(shù)據(jù)集中的幾組數(shù)據(jù)對(duì)該算法進(jìn)行了聚類(lèi)實(shí)驗(yàn)及有效性測(cè)試，實(shí)驗(yàn)結(jié)果充分表明了該算法的有效性及優(yōu)越性。

可見(jiàn)，將k-means算法與其他算法相結(jié)合，可以彌補(bǔ)k-means算法的不足，獲得更好的聚類(lèi)效果。

3 結(jié)束語(yǔ)

K-means的發(fā)展已經(jīng)經(jīng)歷了很長(zhǎng)的一段時(shí)間，它所具有的獨(dú)特優(yōu)勢(shì)使得其被廣大研究者不斷地優(yōu)化和使用。本文從k-means算法中心點(diǎn)的選取、離群點(diǎn)的檢測(cè)與去除、距離與相似性度量等方面進(jìn)行了綜述，可以看出k-means算法在這幾方面的改進(jìn)依然需要進(jìn)行深入的研究。對(duì)k-means的研究和改進(jìn)還應(yīng)注意以下幾點(diǎn)：

（1）隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，數(shù)據(jù)量呈現(xiàn)出一種指數(shù)級(jí)增長(zhǎng)。如何高效地對(duì)這些海量數(shù)據(jù)進(jìn)行處理和分析己成為當(dāng)前研究熱點(diǎn)。傳統(tǒng)的k-means算法難以有效處理大的數(shù)據(jù)集。所以將并行計(jì)算和k-means算法結(jié)合，并不斷地對(duì)其加以改進(jìn)和優(yōu)化，是處理海量數(shù)據(jù)的有效途徑。

（2）k-means聚類(lèi)算法的改進(jìn)有許多依然需要用戶(hù)輸入?yún)?shù)，傳統(tǒng)的k-means算法的k值的確定研究不多。所以參數(shù)的自確定是一個(gè)不斷需要發(fā)展研究的問(wèn)題。

（3）從文中可以看出，現(xiàn)在存在著各種各樣的數(shù)據(jù)類(lèi)型，文本、圖像、混合型數(shù)據(jù)等等，現(xiàn)有的多是處理二維數(shù)據(jù)，對(duì)高維數(shù)據(jù)處理的研究不多，需要對(duì)k-means算法進(jìn)行擴(kuò)展，以得到一個(gè)能夠適應(yīng)大多數(shù)類(lèi)型數(shù)據(jù)類(lèi)型的k-means算法模型。

參考文獻(xiàn)

[1]王千，王成，馮振元，葉金鳳.K-means聚類(lèi)算法研究綜述[d].電子設(shè)計(jì)工程，2012，20（07）：21-24.

[2]賈瑞玉，李玉功.類(lèi)簇?cái)?shù)目和初始中心點(diǎn)自確定的K-means算法[.1l.計(jì)算機(jī)工程與應(yīng)用，2018，54（07）：152-158.

[3]Rodriguez A，Laio A.Clustering byfast search and findof densitypeaks[J].Science，2014，344：1492-1496.

[4]Lei Gu.A novel locality sensitivek-means clustering algorithm basedon subtractive clustering[C].IEEEInternational Conference on SoftwareEngineering and Service Science.IEEE，2017：836-839.

[5]M.S.Premkumar and S.H.Ganesh，.A Median Based External InitialCentroid Selection Method forK-Means Clustering[C].World Congresson Computing and CommunicationTechnologies.IEEE Computer Society，2017：143-146.

[6]C.Lasheng and L.Yuqiang.Improvedinitial clustering center selectionalgorithm for K-means[C].2017 SignalProcessing：Algorithms，Architectures，Arrangements，and Applications（SPA），Poznan，2017：275-279.

[7]陳磊磊.不同距離測(cè)度的K-Means文本聚類(lèi)研究[J].軟件，2015，36（01）：56-61.

[8] W.Xue，R.1.Yang，X.y.Hong，et al.A novelk-Means based on spatial densitysimilarity measurement[C].Control andDecision Conference.IEEE，2017：7782-7784

[9]J.P.Singh and N.Bouguila.Proportional data clustering usingK-means algorithm：A comparisonof different distances[C].IEEE International Conferenceon Industrial Technology.IEEE，2017：1048-1052.

[10]Breunig M M.LOF：identifyingdensity-based local outliers[C].ACMSIGMOD International Conference onManagement of Data.ACM，2000：93-104.

[11]K.Zhang，M.Hutter，and H.J in.Anew local distance-based outlierdetection approach for scatteredreal-world data[C].Proceedings ofthe 13th Pacific-Asia Conference onAdvances in Knowledge Discovery andData Mining，2009：813-822.

[12]T.Zhang，F(xiàn).Yuan and L.Yang.CappedRobust K-means Algorithm[C].International Conference onMachine Learning and Cybernetics.IEEE，2017：150-155.

[13]P.O.Olukanmi and B.Twala.K-means-sharp：Modified centroid update foroutlier-robust k-means clustering[C].2017 Pattern Recognition Associationof South Africa and Robotics andMechatronics（PRASA一RobMech），Bloemfontein，2017：14-19.

[14]Kapil S，Chawla M，Ansari M D.OnK-means data clustering algorithmwith genetic algorithm[C].FourthInternational Conference on Parallel，Distributed and Grid Computing.IEEE，2017：202-206.

[14]沈艷，余冬華，王昊雷.粒子群K-means聚類(lèi)算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（21）：125-128

[15]陳小雪，尉永清，任敏，孟媛媛.基于螢火蟲(chóng)優(yōu)化的加權(quán)K-means算法[J].計(jì)算機(jī)應(yīng)用研究，2018，35（02）：466-470.