機器學習-EM演算法(Expectation maximization algorithm)(二)K-means
May 5, 2021
K-means(K均值聚類)是一種基於中心的聚類演算法，透過迭代，將樣本分到K個類中，使每個樣本與其所屬類中心的距離之和最小。
假設我們有一組樣本數為Ｎ的數據集，且每個樣本有m個特徵，然後我們要將資料分類成K個類別。
在Ｋ值給定下，第k個類別的中心定義為
我們需要以相似度找到每個樣本所屬的類別，將相似度最高的歸為同一類。而K-means是用歐式距離的平方來計算樣本間的相似度。
接著，把所有樣本與所屬類中心的距離平方和，定義為損失函式：
在定義完損失函數後，K-means是一種迭代演算法，每次迭代涉及兩個連續步驟，分別對rnk和μk做優化，也對應著EM演算法的Ｅ步(求期望)和Ｍ步(求極大)。
Ｅ步：
初始化μk(K個類別中心)，在μk固定下，最優化rnk，也就是將某個樣本分配到第k個類別，如果該樣本和第k個類別的距離最小那麼rnk=1
Ｍ步：
確定了資料所屬的類別(rnk)後，我們要來最優化μk。
目標式J是μk的二次函數，將目標式J對μk做一次微分並令其導數為零後，就可以得到使目標是達到最小值的μk，即
接著重新為樣本分類，再重新計算每個類別的均值，不斷重複這兩個步驟，直到聚類的結果不再改變。
