關(guān)于聚類算法K—means的研究與多種實現(xiàn)

汪美

【摘 要】隨著大數(shù)據(jù)算法的廣泛應用與社會反響越來越大、應用領(lǐng)域越來越廣泛，隨之而來的將是算法的逐步研究優(yōu)化與多種實現(xiàn)。本文將從聚類算法K-means的理論知識為基準，討論其優(yōu)缺點并給出不同實現(xiàn)方式的呈現(xiàn)結(jié)果與差異產(chǎn)生的原因。

【關(guān)鍵詞】大數(shù)據(jù)；K-means；R語言

1、K-means聚類算法簡介

根據(jù)資料表明，聚類可以認為是：一個類簇內(nèi)的實體是相似的，不同類簇的實體是不相似的；一個類簇是測試空間中點的會聚，同一類簇的任意兩個點間的距離小于不同類簇的任意兩個點間的距離；類簇可以描述為一個包含密度相對較高的點集的多維空間中的連通區(qū)域，它們借助包含密度相對較低的點集的區(qū)域與其他區(qū)域（類簇）相分離。[1]簡而言之，聚類是一個根據(jù)某些數(shù)據(jù)集中程度進行分組的構(gòu)造過程，將在某些方面相似的數(shù)據(jù)成員進行分類與組織，聚類技術(shù)經(jīng)常被稱為無監(jiān)督學習。k均值聚類算法是一種著名的聚類算法，因其簡單、便捷和高效率的特點令其成為最廣泛使用的聚類算法。

k均值聚類算法（k-means clustering algorithm）是一種迭代求解的聚類分析算法，其步驟是隨機選取K個對象作為初始的聚類中心，然后計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。每分配一個樣本，聚類的聚類中心會根據(jù)聚類中現(xiàn)有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是沒有（或最小數(shù)目）對象被重新分配給不同的聚類，沒有（或最小數(shù)目）聚類中心再發(fā)生變化，誤差平方和局部最小。

2、K-means的基本思想

K-means算法屬于一種經(jīng)典的聚類算法，一般以歐氏距離作為2 個樣本相似程度的評價指標，基本思想如下：

在數(shù)據(jù)集中任意選擇若干個點作為初始聚類中心點，數(shù)據(jù)集中其他樣本到這些數(shù)據(jù)中心點之間距離，將其歸到距離最小的類中，再通過計算得到所有歸到各個類中的樣本的平均值，然后再更新各個類的中心，直到平方誤差準則函數(shù)穩(wěn)定在最小值范圍內(nèi)為止[2]。也就是對于已給定的樣本集，根據(jù)樣本之間的距離差異區(qū)分樣本集為K個簇，并且讓簇內(nèi)部的點之間盡量緊密連接，而讓簇間的距離盡量的變大。K-means算法設計過程.首先，由用戶確定所要聚類的準確數(shù)目k，并隨機選擇k個對象 （樣本） ，每個對象稱為一個種子，代表一個簇 （類） 的均值或中心，對剩余的每個對象，根據(jù)其與各簇中心的距離將它賦給最近的簇.然后重新計算每個簇內(nèi)對象的平均值形成新的聚類中心，這個過程重復進行，直到準則函數(shù)收斂為止。[3]

3、K-means的優(yōu)缺點

3.1優(yōu)點

K-means算法的原理比較簡單，實現(xiàn)也很容易，并且收斂速度快，聚類效果較優(yōu)，算法的可解釋度也比較強。主要需要的參數(shù)只有是簇數(shù)k。它的計算復雜度也相對低，為O（Nmq），其中N是數(shù)據(jù)總量，q是迭代次數(shù)，m是類別（即k）。一般來講m、q會比N小很多，那么，此時的復雜度相當于O（N），與其它類似的算法相比算是很小的。當然也就意味著它能夠在短時間內(nèi)處理非常多的數(shù)據(jù)，這種特點在如今這個數(shù)據(jù)爆炸的時代是非常重要的。為此，k-means目前仍然被各個企業(yè)廣泛使用。

3.2缺點

聚類分析是數(shù)據(jù)挖掘中的重要分支，其原理是根據(jù)數(shù)據(jù)的相似性將數(shù)據(jù)分配到有差異的類中。聚類分析的應用廣泛，為機器學習、人工智能、醫(yī)學、網(wǎng)絡安全等領(lǐng)域提供了重要的技術(shù)支持?；趧澐值木垲愂蔷垲愃惴ㄖ休^為常見的算法，由于其簡單高效的特點得到了各領(lǐng)域廣泛應用。其中，較為常見的是K-means聚類算法，其實現(xiàn)原理簡單，而且算法效率較高。但是由于K-means算法易受限于初始聚類中心，其應用也受到了很多限制。[4]除此之外，K值的選取也不好把握，對于區(qū)別步兵師很明顯的數(shù)據(jù)集來說比較難以收斂。如果各隱含類別的數(shù)據(jù)不平衡、嚴重失衡或者各類別的方差不同，那么，聚類效果將會不佳。采用迭代方法，得到的結(jié)果只是局部最優(yōu)。此外，對噪音和異常點比較的敏感。分類結(jié)果依賴于分類中心的初始化。對類別規(guī)模差異大的數(shù)據(jù)效果不友好。K-means對于距離非常近的類別的分類效果也不好。不適用于categorical的分類?？茖W家、工程師等也一直在研究不同的方法去克服k-means的缺點。

4、兩種實現(xiàn)方式及結(jié)果對比展示

對于K-means算法，最先要注意的就是k值的選擇。一般來說，我們對k值的選擇可以依據(jù)對數(shù)據(jù)的先驗經(jīng)驗，如果沒有相應的先驗經(jīng)驗知識，還可以通過交叉驗證選擇一個相對合適的k值。在確定了k的個數(shù)后，我們需要選擇k個初始化的隨機質(zhì)心，這k個初始化質(zhì)心的位置數(shù)據(jù)對最后的聚類分析的結(jié)果和運行時間的長短以及效率都會有很大的影響，因此需要選擇合適的k個質(zhì)心，這些質(zhì)心最好不能距離太近。實現(xiàn)過程為：

（a）選擇k個聚類中心點作為初始值

（b）分別計算數(shù)據(jù)點與這k個中心各自的距離，按照最小距離原則將其分配到最鄰近聚類

（c）使用每個聚類中的樣本均值作為新的聚類中心

（d）重復執(zhí)行步驟（b）和（c），直到聚類中心收斂，不再發(fā)生變化

（e）執(zhí)行結(jié)束，得到k個聚類

根據(jù)以上步驟繪制mahout聚類點，以及通過R語言實現(xiàn)聚類點的可視化，結(jié)果如圖。

從圖中可以看到有黑、藍、綠三種顏色的空心點，這些空心點代表原始的數(shù)據(jù)。圖中的3個紅色實點，是R語言kmeans后生成的3個中心。3個紫色實點，是Mahout的kmeans后生成的3個中心。R語言和Mahout生成的點，并不是重合的，原因可能有：距離算法不一樣，Mahout中，利用的是 “歐氏距離（EuclideanDistanceMeasure）”，而R語言中，默認是”Hartigan and Wong”。此外，初始化的中心、迭代次數(shù)不一樣，點合并時，判斷的”閾值（threshold）”是不一樣的。

5、結(jié)語

本文從對K-means聚類算法的理論入手，通過總結(jié)、研究并給出本算法的基本思想，并通過圖示表示出來。緊接著，作者對K-means算法的優(yōu)缺點進行了詳細的分析與鮮明的對比，本算法雖然存在若干缺點但仍在各個領(lǐng)域充分應用，是因為算法的復雜度低，也就意味著它能夠在短時間內(nèi)處理非常多的數(shù)據(jù)，這在如今這個大數(shù)據(jù)時代是非常重要的。本文還提供了mahout聚類點的繪制和通過R語言實現(xiàn)，并介紹了二者得出不同結(jié)果的原因，也體現(xiàn)了不同算法只能得出在一定范圍內(nèi)相對正確的結(jié)果。

【參考文獻】

[1]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學報，2008（01）：48-61.

[2]張建輝. K-means 聚類算法研究及應用[D]. 武漢理工大 學， 2007.

[3]楊善林，李永森，胡笑旋，潘若愚.K-MEANS算法中的K值優(yōu)化問題研究[J].系統(tǒng)工程理論與實踐，2006（02）：97-101.

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