1. Intro
聚類算法中最經(jīng)典的要算是 K-means 了螺捐。其中 K 代表劃分的 cluster 的 數(shù)目，而 means 則是算法的核心概念——centroid（質(zhì)心）
2. Basic K-means
K-means 是一個迭代算法材部，以最終 converge 為終止條件。
pseudo code：
SELECT K INITIAL CENTROIDS;
while(true)
foreach point:
Compute the distance to every centroid;
Label this point as the cluster corresponding to the nearest centroid;
re-calculate K centroids;
if (all centroids no longer change)
break;
1. 初始選取K 個 centroid；
2. 以 centroid 代表 cluster。計(jì)算每個點(diǎn)距離哪個 centroid 最近鸵鸥，
將該點(diǎn)標(biāo)記為屬于最近 centroid 對應(yīng)的 cluster。然后計(jì)算每一個 cluster 的新的 centroid丹皱。
3. 重復(fù)2直到所有 centroid 不再改變
(對于歐氏空間妒穴？) 衡量聚類效果的好壞以平方誤差和（sum of the square error, SSE）作為目標(biāo)函數(shù):
可以將第一個求和號右邊部分視為求每一個簇的簇SSE, 對所有的簇SSE求和，就得到總 SSE摊崭。
3. k-means存在缺點(diǎn)：
k-means是局部最優(yōu)的讼油，容易受到初始質(zhì)心的影響；比如在下圖中呢簸，因選擇初始質(zhì)心不恰當(dāng)而造成次優(yōu)的聚類結(jié)果（SSE較大）：
另外 basic K-means 容易形成 empty cluster
4. 優(yōu)化
對于empty cluster 我們的策略是當(dāng)選取 initial centroid 的時候矮台，隨機(jī)選取真實(shí)的點(diǎn)作為initial centroid乏屯，這樣就有效避免出現(xiàn)某個 cluster 里面沒有點(diǎn)。
對于收斂于局部最優(yōu)的缺點(diǎn)瘦赫，我們通過 bisecting K-means 來解決辰晕。其基本思想是：
初始只有一個cluster包含所有樣本點(diǎn)；
repeat for (K-1) times: //(k-1)次后就得到 k 個 clusters
從待分裂的clusters中選擇一個進(jìn)行二元分裂耸彪，所選的cluster是具有最大的 簇SSE 的簇伞芹；
這里選取待分裂簇的判斷標(biāo)準(zhǔn)我不同意http://www.cnblogs.com/en-heng/p/5173704.html 這篇博客里面的說法，所選的 cluster 應(yīng)使得 SSE 最小蝉娜，這樣的說法太過于籠統(tǒng)唱较。
直接參考《數(shù)據(jù)挖掘?qū)д摗?16頁結(jié)論就好：分裂一個簇通常選取 SSE 最大的簇。因?yàn)橐粋€簇的 簇SSE 越大召川，說明這個簇越離散南缓，需要進(jìn)一步分解。
