• （3）使用k-means算法將可分裂的簇分為兩簇。

• （4）一直重復（2）（3）步，直到滿足迭代結束條件。

以上過程隱含著一個原則是：因為聚類的誤差平方和能夠衡量聚類性能，該值越小表示數據點越接近于它們的質心，聚類效果就越好。 所以我們就需要對誤差平方和最大的簇進行再一次的劃分，因為誤差平方和越大，表示該簇聚類越不好，越有可能是多個簇被當成一個簇了，所以我們首先需要對這個簇進行劃分。

二分k-means的源碼分析

spark在文件org.apache.spark.mllib.clustering.BisectingKMeans中實現了二分k-means算法。在分步驟分析算法實現之前，我們先來了解BisectingKMeans類中參數代表的含義。

上面代碼中，k表示葉子簇的期望數，默認情況下為4。如果沒有可被切分的葉子簇，實際值會更小。maxIterations表示切分簇的k-means算法的最大迭代次數，默認為20。 minDivisibleClusterSize的值如果大于等于1，它表示一個可切分簇的最小點數量；如果值小于1，它表示可切分簇的點數量占總數的最小比例，該值默認為1。

BisectingKMeans的run方法實現了二分k-means算法，下面將一步步分析該方法的實現過程。

（1）初始化數據

（2）將所有數據初始化為一個簇，并計算代價

在上述代碼中，第一行給每個向量加上一個索引，用以標明簇在最終生成的樹上的深度，ROOT_INDEX的值為1。summarize方法計算誤差平方和，我們來看看它的實現。

這里的d表示特征維度，代碼對assignments使用aggregateByKey操作，根據key值在分區內循環添加（add）數據，在分區間合并（merge）數據集，轉換成最終ClusterSummaryAggregator對象，然后針對每個key，調用summary方法，計算。 ClusterSummaryAggregator包含三個很簡單的方法，分別是add，merge以及summary。

這里計算誤差平方和與第一章的公式有所不同，但是效果一致。這里計算聚類代價函數的公式如下所示：

獲取第一個簇之后，我們需要做的就是迭代分裂可分裂的簇，直到滿足我們的要求。迭代停止的條件是activeClusters為空，或者numLeafClustersNeeded為0（即沒有分裂的葉子簇）,或者迭代深度大于LEVEL_LIMIT。

這里，LEVEL_LIMIT是一個較大的值，計算方法如下。

（3）獲取需要分裂的簇

在每一次迭代中，我們首先要做的是獲取滿足條件的可以分裂的簇。

這里選擇分裂的簇用到了兩個條件，即數據點的數量大于規定的最小數量以及代價小于等于MLUtils.EPSILON * summary.size。并且如果可分解的簇的個數多余我們規定的個數numLeafClustersNeeded即(k-1)， 那么我們取包含數量最多的numLeafClustersNeeded個簇用于分裂。

（4）使用k-means算法將可分裂的簇分解為兩簇

我們知道，k-means算法分為兩步，第一步是初始化中心點，第二步是迭代更新中心點直至滿足最大迭代數或者收斂。下面就分兩步來說明。

• 第一步，隨機的選擇中心點，將可分裂簇分為兩簇

在上面的代碼中，用splitCenter方法將簇隨機地分為了兩簇，并返回相應的中心點，它的實現如下所示。

• 第二步，迭代更新中心點

這段代碼中，updateAssignments會根據更新的中心點將數據分配給距離其最短的中心點所在的簇，即重新分配簇。代碼如下：

重新分配簇之后，利用summarize方法重新計算中心點以及代價值。

（5）處理變量值為下次迭代作準備