K-means演算法優化

（1）k-means演算法缺點

上一篇文章《聚類演算法之K-means演算法》中介紹了K-means演算法所有知識點並指出K-means演算法的缺點。今天我們來回顧一下K-means的這些缺點：

對雜訊和孤立點數據比較敏感。表現為：K-means將簇中所有點的均值作為新質心，若簇中含有異常點，將導致均值偏離嚴重，容易陷入局部最小值。

必須事先給出K值。

在K-均值聚類中簇的數目k是一個用戶預先定義的參數，那麼用戶如何才能知道k的選擇是否正確呢？如何才能知道生成的簇比較好呢？在包含簇分配結果的矩陣中保存著每個樣本的誤差，即該樣本到簇質心的距離平方值。這一點在《聚類演算法之K-means演算法》中有用Python實現。下面會討論利用該誤差來評價聚類質量的方法。

圖1：K-means演算法實現西瓜數據集4.0聚成3簇

考慮圖1的聚類結果，這是在一個包含三個簇的數據集上運行k-means演算法之後的結果，但是點的簇分結果值沒有那麼準確。K-means演算法收斂但聚類效果較差的原因是，k-means演算法收斂到了局部最小值，而非全局最小值（局部最小值指結果還可以但並非最好結果，全局最小值是可能的最好結果）。

一種用於度量聚類效果的指標是SSE(Sum of Squared Error,誤差平方和)，對應《聚類演算法之K-means演算法》的Python程序代碼，如圖2所示。SSE值越小表示數據點越接近於它們的質心，聚類效果也越好。因為對誤差取了平方，因此更加重視那些遠離中心的點。一種肯定可以降低SSE值的方法是增加簇的個數，但這違背了聚類的目標。聚類的目標是在保持簇數目不變的情況下提高簇的質量。

圖2：Python實現SSE

那麼如何對圖1的結果進行改進呢？你可以對生成的簇進行後處理，一種方法是將具有最大SSE值的簇劃分成兩個簇。具體實現時可以將最大簇包含的點過濾出來並在這些點上運行K-means演算法，其中的K設置為2。

圖3：由於質心隨機初始化導致K-means演算法效果不好的一個例子，這需要額外的後處理操作來清理聚類結果

為了保持簇總數不變，可以將某兩個簇進行合併。從圖3中很明顯就可以看出，應該將圖下部兩個出錯的簇質心進行合併。可以很容易對二維數據上的聚類進行可視化，知道哪幾個簇可以合併，但是如果遇到40維的數據應該如何去做？

有兩種可以量化的辦法：合併最近的質心，或者合併兩個使得SSE增幅最小的質心。第一種思路通過計算所有質心之間的距離，然後合併距離最近的兩個點來實現。第二種方法需要合併兩個簇然後計算總SSE值。必須在所有可能的兩個簇上重複上述處理過程，直到找到合併最佳的兩個簇為止。接下來將討論利用上述簇劃分技術得到更好的聚類結果的方法。

為克服K-均值演算法收斂於局部最小值的問題，有人提出了另一個稱為二分K-均值（bisecting K-means）的演算法。該演算法首先將所有點作為一個簇，然後將該簇一分為二。之後選擇其中一個簇繼續進行劃分，選擇哪一個簇進行劃分取決於對其劃分是否可以最大程度降低SSE的值。上述基於SSE的劃分過程不斷重複，直到得到用戶指定的簇數目為止。

二分K-means演算法的偽代碼形式如下：