利用模擬退火提高Kmeans的聚類精度

Kmeans算法是一種非監督聚類算法，由于原理簡單而在業界被廣泛使用，一般在實踐中遇到聚類問題往往會優先使用Kmeans嘗試一把看看結 果。本人在工作中對Kmeans有過多次實踐，進行過用戶行為聚類（MapReduce版本）、圖像聚類（MPI版本）等。然而在實踐中發現初始點選擇與 聚類結果密切相關，如果初始點選取不當，聚類結果將很差。為解決這一問題，本博文嘗試將模擬退火這一啟發式算法與Kmeans聚類相結合，實踐表明這種方 法具有較好效果，已經在實際工作中推廣使用。

1 Kmeans算法原理

K-MEANS算法: 輸入：聚類個數k，以及包含 n個數據對象的數據。 輸出：滿足方差最小標準的k個聚類。
 處理流程：        
 （1）  從 n個數據對象選擇 k 個對象作為初始聚類中心；
（2）  循環（3）到（4）直到每個聚類不再發生變化為止
（3）  根據每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據最小距離重新對相應對象進行劃分；
（4）  重新計算每個（有變化）聚類的均值（中心對象）

1.1 Step 1

1.2 Step 2

1.3 Step 3

1.4 Step 4

1.5 Step 5

2 初始點與聚類結果的關系

K means的結果與初始點的選擇密切相關，往往陷于局部最優。

2.1 例子

下面以一個實際例子來講初始點的選擇將影響聚類結果。首先3個中心點（分別是紅綠藍三點）被隨機初始化，所有的數據點都還沒有進行聚類，默認全部都標記為紅色，如下圖所示：

迭代最終結果如下：

如果初始點為如下：

最終會收斂到這樣的結果：

3 解決方法

那怎么解決呢？一般在實際使用中，我們會隨機初始化多批初始中心點，然后對不同批次的初始中心點進行聚類，運行完后選擇一個相對較優的結果。這種 方法不僅不夠自動，而且有較大概率得不到較優的結果。目前，研究較多的是將模擬退火、遺傳算法等啟發式算法與Kmeans聚類相結合，這樣能大大降低陷于 局部最優的困境。下圖就是模擬退火的算法流程圖。

4 實戰

“紙上得來終覺淺，絕知此事要躬行”，僅知道原理而不去實踐永遠不能深刻掌握某一知識。本人實現了基于模擬退火的Kmeans算法以及普通的Kmeans算法，以便進行比較分析。

4.1 實驗步驟

1）首先我們隨機生成二維數據點以便用于聚類。

2）基于原生的Kmeans得到的結果。

3）基于模擬退火的Kmeans得到的結果

4.2 結論

由上圖的實驗結果可以看出，基于模擬退火的Kmeans所得的總體誤差準則結果為：19309.9。

而普通的Kmeans所得的總體誤差準則結果為：23678.8。

可以看出基于模擬退火的Kmeans所得的結果較好，當然，此算法的復雜度較高，收斂所需的時間較長。