叢思安 王星星

摘要

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

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

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

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

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

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

（1）用戶輸入類簇數(shù)目的值k，從n個樣本點中隨機(jī)選取k個點作為初始聚類中心;

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

（3）重新確定聚類中心。將每個類簇中的所有樣本點的均值作為新的聚類中心。

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

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

2.1 初始聚類中心的選取

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

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

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

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

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

2.2 距離和相似性度量

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

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

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

2.3 離群點的檢測

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

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

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

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

參考文獻(xiàn)

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

[2]賈瑞玉，李玉功.類簇數(shù)目和初始中心點自確定的K-means算法[.1l.計算機(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]陳磊磊.不同距離測度的K-Means文本聚類研究[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聚類算法的改進(jìn)[J].計算機(jī)工程與應(yīng)用，2014，50（21）：125-128

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