關于聚類算法K—means的研究與多種實現

汪美

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

【關鍵詞】大數據；K-means；R語言

1、K-means聚類算法簡介

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

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

2、K-means的基本思想

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

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

3、K-means的優缺點

3.1優點

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

3.2缺點

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

4、兩種實現方式及結果對比展示

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

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

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

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

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

（e）執行結束，得到k個聚類

根據以上步驟繪制mahout聚類點，以及通過R語言實現聚類點的可視化，結果如圖。

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

5、結語

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

【參考文獻】

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

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

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

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