1 k-means算法原理分析

k-means算法是聚類分析中使用最廣泛的算法之一。它把n個對象根據它們的屬性分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。

k-means算法的基本過程如下所示：

• （4）計算標準測度函數，當滿足一定條件，如函數收斂時，則算法終止；如果條件不滿足則重復步驟

1.1 k-means算法的缺點

k-means算法雖然簡單快速，但是存在下面的缺點：

• 聚類中心的個數K需要事先給定，但在實際中K值的選定是非常困難的，很多時候我們并不知道給定的數據集應該分成多少個類別才最合適。

• k-means算法需要隨機地確定初始聚類中心，不同的初始聚類中心可能導致完全不同的聚類結果。

第一個缺陷我們很難在k-means算法以及其改進算法中解決，但是我們可以通過k-means++算法來解決第二個缺陷。

2 k-means++算法原理分析

k-means++算法選擇初始聚類中心的基本原則是：初始的聚類中心之間的相互距離要盡可能的遠。它選擇初始聚類中心的步驟是：

第(2)步中，依次計算每個數據點與最近的種子點（聚類中心）的距離，依次得到D(1)、D(2)、...、D(n)構成的集合D，其中n表示數據集的大小。在D中，為了避免噪聲，不能直接選取值最大的元素，應該選擇值較大的元素，然后將其對應的數據點作為種子點。 如何選擇值較大的元素呢，下面是spark中實現的思路。

• 求所有的距離和Sum(D(x))

• 取一個隨機值，用權重的方式來取計算下一個“種子點”。這個算法的實現是，先用Sum(D(x))乘以隨機值Random得到值r，然后用currSum += D(x)，直到其currSum > r，此時的點就是下一個“種子點”。

為什么用這樣的方式呢？我們換一種比較好理解的方式來說明。把集合D中的每個元素D(x)想象為一根線L(x)，線的長度就是元素的值。將這些線依次按照L(1)、L(2)、...、L(n)的順序連接起來，組成長線L。L(1)、L(2)、…、L(n)稱為L的子線。 根據概率的相關知識，如果我們在L上隨機選擇一個點，那么這個點所在的子線很有可能是比較長的子線，而這個子線對應的數據點就可以作為種子點。

2.1 k-means++算法的缺點

雖然k-means++算法可以確定地初始化聚類中心，但是從可擴展性來看，它存在一個缺點，那就是它內在的有序性特性：下一個中心點的選擇依賴于已經選擇的中心點。 針對這種缺陷，k-means||算法提供了解決方法。

3 k-means||算法原理分析

第1步隨機初始化一個中心點，第2-6步計算出滿足概率條件的多個候選中心點C，候選中心點的個數可能大于k個，所以通過第7-8步來處理。第7步給C中所有點賦予一個權重值 Wx ，這個權重值表示距離x點最近的點的個數。 第8步使用本地k-means++算法聚類出這些候選點的k個聚類中心。在spark的源碼中，迭代次數是人為設定的，默認是5。

該算法與k-means++算法不同的地方是它每次迭代都會抽樣出多個中心點而不是一個中心點，且每次迭代不互相依賴，這樣我們可以并行的處理這個迭代過程。由于該過程產生出來的中心點的數量遠遠小于輸入數據點的數量， 所以第8步可以通過本地k-means++算法很快的找出k個初始化中心點。何為本地k-means++算法？就是運行在單個機器節點上的k-means++。

下面我們詳細分析上述三個算法的代碼實現。

4 源代碼分析

在spark中，org.apache.spark.mllib.clustering.KMeans文件實現了k-means算法以及k-means||算法，org.apache.spark.mllib.clustering.LocalKMeans文件實現了k-means++算法。 在分步驟分析spark中的源碼之前我們先來了解KMeans類中參數的含義。

在上面的定義中，k表示聚類的個數，maxIterations表示最大的迭代次數，runs表示運行KMeans算法的次數，在spark 2.0。0開始，該參數已經不起作用了。為了更清楚的理解算法我們可以認為它為1。 initializationMode表示初始化模式，有兩種選擇：隨機初始化和通過k-means||初始化，默認是通過k-means||初始化。initializationSteps表示通過k-means||初始化時的迭代步驟，默認是5，這是spark實現與第三章的算法步驟不一樣的地方，這里迭代次數人為指定， 而第三章的算法是根據距離得到的迭代次數，為log(phi)。epsilon是判斷算法是否已經收斂的閾值。

下面將分步驟分析k-means算法、k-means||算法的實現過程。

4.1 處理數據，轉換為VectorWithNorm集

4.2 初始化中心點

初始化中心點根據initializationMode的值來判斷，如果initializationMode等于KMeans.RANDOM，那么隨機初始化k個中心點，否則使用k-means||初始化k個中心點。

• （1）隨機初始化中心點

隨機初始化k個中心點很簡單，具體代碼如下：

• （2）通過k-means||初始化中心點

相比于隨機初始化中心點，通過k-means||初始化k個中心點會麻煩很多，它需要依賴第三章的原理來實現。它的實現方法是initKMeansParallel。 下面按照第三章的實現步驟來分析。

• 第一步，我們要隨機初始化第一個中心點。

  

• 第二步，通過已知的中心點，循環迭代求得其它的中心點。

  

• 在這段代碼中，我們并沒有選擇使用log(pha)的大小作為迭代的次數，而是直接使用了人為確定的initializationSteps，這是與論文中不一致的地方。 在迭代內部我們使用概率公式

來計算滿足要求的點，其中，l=2k。公式的實現如代碼rand.nextDouble() < 2.0 * c(r) * k / sumCosts(r)。sumCosts表示所有點距離它所屬類別的中心點的歐式距離之和。 上述代碼通過aggregate方法并行計算獲得該值。

• 第三步，求最終的k個點。

通過以上步驟求得的候選中心點的個數可能會多于k個，這樣怎么辦呢？我們給每個中心點賦一個權重，權重值是數據集中屬于該中心點所在類別的數據點的個數。 然后我們使用本地k-means++來得到這k個初始化點。具體的實現代碼如下：

上述代碼的關鍵點時通過本地k-means++算法求最終的初始化點。它是通過LocalKMeans.kMeansPlusPlus來實現的。它使用k-means++來處理。

上述代碼中，points指的是候選的中心點，weights指這些點相應地權重。尋找概率最大的點的方式就是第二章提到的方式。初始化k個中心點后， 就可以通過一般的k-means流程來求最終的k個中心點了。具體的過程4.3會講到。

4.3 確定數據點所屬類別

找到中心點后，我們就需要根據距離確定數據點的聚類，即數據點和哪個中心點最近。具體代碼如下：

4.4 重新確定中心點

找到類別中包含的數據點以及它們距離中心點的距離，我們可以重新計算中心點。代碼如下：