【Bisecting K-Means算法】{0} —— Bisecting K-Means算法的簡單介紹

K-Means算法通常隻能收斂于局部最小值，這可能導緻“反直覺”的錯誤結果。

是以，為了優化K-Means算法，提出了

Bisecting K-Means算法

，也就是二分K-Means算法。

Bisecting K-Means算法 是一種層次聚類方法。

層次聚類（Hierarchical Clustering）是聚類算法的一種，通過計算不同類别的相似度類建立一個有層次的嵌套的樹。

Bisecting K-Means算法 和 K-Means算法 有什麼不同？

Bisecting K-Means算法 并不是一開始就随機選擇 K 個中心點，而是先把所有點歸為一個簇，然後将該簇一分為二。計算各個所得簇的代價函數（SSE），選擇SSE最大的簇再進行劃分以盡可能地減小誤差，重複上述基于SSE劃分過程，直到得到使用者指定的簇數目為止。

Bisecting K-Means算法 通常比 K-Means算法運算快一些。

聚類算法的代價函數SSE能夠衡量聚類性能，該值越小表示資料點越接近于它們的質心，聚類效果就越好。是以需要對SSE最大的簇進行再一次劃分，因為誤差平方和越大，表示該簇聚類越不好，越有可能是多個簇被當成一個簇了，是以首先需要對SSE最大的簇進行劃分。

Bisecting K-Means算法的僞代碼如下:

将所有點看成一個簇
當簇數目小于k時:
	對于每一個簇:
		計算總誤差
		在給定的簇上面進行K-均值聚類(k=2)
		計算将該簇一分為二之後的總誤差
	選擇使得誤差最小的那個簇進行劃分操作
           

參考資料：《機器學習實戰》