Tommy Huang
2 min readApr 25, 2019

--

這邊距離公式就只是算歐式距離,整個k-means不需要用到EM
硬要用EM也沒有意義,因為那就不是k-means,而是GMM的case,GMM也不是強調在歐式距離,而是算馬氏距離(更新常態分佈的平均數和變異數),然後還有和隱藏變數的關係,跟k-means有很大的差異。

收斂部分: 收斂方式,這些群心的值不在變動或是差異不大時就收斂了

我舉例子說明:假設有100個點,群心初始設定兩個(群心1和群心2)。
1. 這100個點要分別跟這兩個群心算歐式距離,點跟哪個群心近這個點就判給哪一類,假設群心1有30個點跟他很近(就用這30個點來更新這個群心1),群心2有70個點跟他很近(就用這70點來更新這個群心),就會得到新的群心1和群心2。
2. 這時候要算「群心1和新的群心1的差異值」以及「群心2和新的群心2的差異值」,這個差異值最簡單也是算歐式距離,兩個差異值相加當作cost function output =算mean square error (MSE)。
每更新一次群心就算一次MSE
3. repeat 1和2,可以得到不同次更新的MSE,這個MSE的值越來越小直到MSE不在變動或是差異非常小就是演算法收斂(前一次MSE和這一次MSE差異值<0.0000000001之類的)

k-means因為算法的特性,群心容易更新到後面會不在變動(就是更新後的群心跟前一次的完全一樣)。Fuzzy c-means因為membership的關係就比較不會發生群心更新到後面會不在變動,在怎麼樣都會有非常微小的更動。

當然也可以直接手動設定k-means算法強制更新1000次就結束算法。
這樣的好處是
1. 可能算法可能不收斂,你可以強制停止更新。
2. 算法可能在第150次收斂,後面在更新也不影響結果。

Note: 所有群心的MSE就是k-means的cost function

其實說這麼多重點都不是在怎麼更新和收斂,k-means最大的問題是initial群心怎麼給,initial給不好算法就會收斂到很奇怪的地方,我就邊就不探討這個問題。

--

--

Tommy Huang
Tommy Huang

Written by Tommy Huang

怕老了忘記這些吃飯的知識,開始寫文章記錄機器/深度學習相關內容。Medium現在有打賞功能(每篇文章最後面都有連結),如果覺得寫的文章不錯,也可以Donate給個Tipping吧。黃志勝 Chih-Sheng Huang (Tommy), mail: chih.sheng.huang821@gmail.com

No responses yet