機器學習: 集群分析 K-means Clustering
K-means 集群分析(又稱c-means Clustering，中文: k-平均演算法，我可以跟你保證在做機器學習的人絕對不會將K-means翻成中文來說，除非是講給不懂的人聽)，基本上Clustering的方法大都是非監督式學習(Unsupervised learning)，K-means也是非監督式學習。
什麼是非監督式學習? 就是你得到的資料你沒有任何Ground truth，你只有資料本身。
舉例，我給你一組身高和體重的資料，但我沒有跟你說這組資料哪些是男生哪些是女生。我希望你用這組資料分出男生女生，這種時候就是用非監督式學習。
Note: 非監督式學習出來的效果基本上會比同類型的監督式學習來的差，因為模型在學的時候沒有答案，所以基本上在misclassifiaction的資料(通常在分類的boundary)分類效果不會很好。
K-means Clustering這個方法概念很簡單，一個概念「物以類聚」。男生就是男生，女生就是女生，男生會自己聚成一群，女生也會自己聚成一群。
但在這群男生自己不會動成一群，女生也不會動成一群，在機器學習內，我們有的就是一組不會動的身高和體重的資料。那是什麼會動，讓男生女生可以區隔開的是什麼? 回頭看看演算法的名字，k-means，這邊的k是你想分成幾群，means就是每一群群心，所以會動的東西就是群心。這邊很懸，什麼是會動的群心??????
如果用實際的例子說，大家到新學校上學的時候有沒有一種感覺，第一天到的時候基本上大家都不熟，一個兩個人是一群，後來慢慢會有一群人聚在一起，沒幾天就分成兩群、三群，慢慢的到上學後一個月，基本上班上的小團體都分好了，每個團體都有一個key-man，你可以把這個key-man當作是群心，基本上大家都是因為有這個key-man聚在一起的(如果變節又是另一件事情)。那這個key-man在開學到小團體分好之前，基本上有可能會一直換來換去的，甚至多出一個key-man或是少一個key-man(演算法:ISODATA)，或是這個團體的key-man會因為別人的強勢而換掉，這就是會動=換掉的群心。
K-means運作概念步驟:
1. 我們先設定好要分成多少(k)群。
2. 然後在feature space(x軸身高和y軸體重組出來的2維空間，假設資料是d維，則會組出d維空間)隨機給k個群心。
3. 每個資料都會所有k個群心算歐式距離(歐基李德距離Euclidean distance，其實就是直線距離公式，從小學到大的那個距離公式，這邊距離當然也可以換成別種距離公式，但基本上都還是以歐式距離為主)。
4. 將每筆資料分類判給距離最近的那個群心。
5. 每個群心內都會有被分類過來的資料，用這些資料更新一次新的群心。
6. 一直重複3–5，直到所有群心不在有太大的變動(收斂)，結束。
K-means運作概念圖解:
繼續剛剛的例子(身高和體重分成兩類)，兩類也比較好圖解(圖1→8)。
基本上就是先做initial群心(圖2)，然後一直重複做圖3–5，直到群心不太變動(收斂)。
讓你讀到不要不要的K-means數學公式:
假設有一組n個d維的資料
設定有K(必須≤n)個Clusters {S1,S2,…,Sk}，K-means clustering就是希望可以最小化群內的資料和群心的誤差平方和越小越好，數學公式如下:
μc就是群心，‖x-y‖就是算歐基李德距離(Euclidean distance)
演算法為
1. 初始隨機設定k個群心.
2. 計算分類到每一群體的樣本，(t)為第t次運算
3. 更新群心(nc個資料在第c群內。)
4. 重複2–3，直到群心不變動，也就是
基本上K-Means的數學跟其他算法比還算滿簡單的。
我放兩段Initial不同的狀態下，K-means的群心變化的效果。雖然資料有分顏色，但那不是K-means判出來的類別，那是我的資料的Ground Truth。
