[ML] K-means algorithm (revision 1)
這次來講個非supervised learning, K-means algorithm
大概算是unsupervised 演算法中, 數一數二簡單的
unsupervised 的意思就是, 給你的training data沒有答案
以前(大學)在DM的書上還看過說, 沒有專家跟你說答案
這DM的解釋讓我當初超莫名奇妙的, 不過後來想想, 其實也不算有問題
因為 data 可能就是沒有答案, 只是一坨混亂, 但是可以用一些演算法找出些許規則
Unsupervised 常見的運用有找出 data 中的特例, 將 data 區分成不同類別, 甚至是壓縮技術
首先, 因為 data 沒有 label, 所以只能從 feature 上下手找規則
如下圖 (我用random normal distribution 隨機建立出來三個 group)
如果我說, 請把這張圖的點, 分成三堆, 應該很多人都會分成右上, 左下跟中間三堆
可是如果我想要電腦自己也可以這樣區分呢? 該如何是好?事情為甚麼會變成這樣?
因為在現代的現實生活中, 我們因為電腦的關係, 可以收集相當相當龐大的資料
有些人會根據目的, 整理成有用的資訊, 但是沒整理過得一樣還是龐雜的資料
而到了現在最火紅的資料時代, 人們會希望從資料中, 找尋許多有用的資訊
甚至整理成智慧, 加以吸收
然後面對成千上百數萬的資料, 有時候我們無從下手
或者講, 太多事情隱藏在資料中了, 或者有些東西其實一開始根本沒記載
只能透過間接的關係去推導出來 (所以也不會有label class...etc)
當你今天身為一名 Data Scientist, 你被囑咐去對這些龐大的資料做分析
就很有可能會碰到, 只有 feature, 卻沒有任何 class 的狀況
因為收集資料的時候不一定會想到之後會需要那樣的用途
所以 unsupervised learning 要幫助的事情是, 他可以從 data 中"自動的"找尋關係
或者講, 他可以幫我把相近關係的資料做區別出來
跟 classification 很像, 只是差在, 你不用跟我講答案, 我靠你給我的資料做猜測就好
我要提的 k-means 就是一種相當 trivial 的演算法
(k-means 強者請不要打我臉 我只是在我blog打嘴泡)
wiki: K-means
k-means 的方法就可以幫忙區分, 事情很簡單
k-means, k 是由使用者設定的, 就是他會找出 k 個 cluster 出來, 也就是可以分成 k class
每個聚集的類別, 都會有個中心點 (centroid), 顧名思義, 也就是這個 class 的中心點
一開始並不知道中心點會在哪邊, 所以在最一開始的時候, 我隨機找 k 點當中心點
(注意, 並不用找 data 上有的點, 點中心不一定會在 data 裡面)
但不用擔心, 這中心點是會變得, 也就是其實不管你設定在哪裡起始
中心點都會慢慢的移動到最後比較像是一堆點的中心處!!
也就是說, 假設我是一筆資料, 我旁邊有兩個不同類別的中心點
誰比較靠近我, 我就是那個類別的, 簡單吧, 通常是用點距離的方式去計算
(只要可以計算距離的都可以拿來運用)
全部點都決定過中心點之後, 就要調整中心點了
也就是說, 假設某中心點有三筆 data, (1,3), (2, 3), (3, 0)
則新的中心點為: (1 + 2 + 3) / 3, (3 + 3 + 0)/ 3 = (2, 2)
所有類別中心點都調整過後, 再繼續回到第2步驟 - > 第3步驟 - > 第2步驟 -> 第3步驟 ...etc
一直做到沒有點會被更換為止, 或者, 做個 100 次, 並且透過 cost 來決定
下面我用多一點的圖形來解釋流程
首先我這張設定為 3 class, 所以隨機挑選三個點, 如畫面上的紅, 藍, 綠三個 X
再來就是要 assign class to point, 根據距離公式的結果, 會如下圖所示
左下角大多是藍色, 中間一小部分是紅色, 右上大約是綠色
跟中心點鄰近的點都改成相對應的顏色了
然後是移動中心點到新的中心位置, 如下圖
這樣, 就基本上完成了第一回合
因為這圖滿簡單的, 才大概再 2 個回合, 很快就會變成下圖所示
就很輕易的把三種 class 給分出來了 !! 厲害吧 ~ !
不過 k-means 會 suffering 在local minimum (也就是不一定會是最佳解)
根據這篇 stackoverflow, 可以看到一個很好的例子說明為甚麼
http://stackoverflow.com/questions/14577329/why-doesnt-k-means-give-the-global-minima
那要解決 local minimum 則是一件 NP-Hard 的事情...嗯......悲劇XD
其實有加強版演算法 - bisecting k-means, 但是...等我有空再補強了...
那另外常見的問題是, 我怎麼知道我要找幾個類別?
wiki: cluster 需要幾個 class
其實常見的有3種作法
1. Rule of thumb
就只是個慣例, 用不用見仁見智
2. Elbow method, 手軸定理
這則是很單純的把 Cost 跟 number of cluster 圖表畫出來, 也就是要嘗試多種 class 然後繪出圖表
手軸定理意思就是, 如果今天 Cost 的走勢跟上圖類似, 像是一個人的手臂彎曲
則彎曲最大處, 即很有可能此份 data 最適合的 class 數量, 但這也只是一種嘗試的方式
3. according to the purpose
當然最後還是要回歸, 你到底想要從這份 data 找出怎樣的 class 來決定到底要分幾個 cluster
大概算是unsupervised 演算法中, 數一數二簡單的
unsupervised 的意思就是, 給你的training data沒有答案
以前(大學)在DM的書上還看過說, 沒有專家跟你說答案
這DM的解釋讓我當初超莫名奇妙的, 不過後來想想, 其實也不算有問題
因為 data 可能就是沒有答案, 只是一坨混亂, 但是可以用一些演算法找出些許規則
Unsupervised 常見的運用有找出 data 中的特例, 將 data 區分成不同類別, 甚至是壓縮技術
首先, 因為 data 沒有 label, 所以只能從 feature 上下手找規則
如下圖 (我用random normal distribution 隨機建立出來三個 group)
如果我說, 請把這張圖的點, 分成三堆, 應該很多人都會分成右上, 左下跟中間三堆
可是如果我想要電腦自己也可以這樣區分呢? 該如何是好?事情為甚麼會變成這樣?
因為在現代的現實生活中, 我們因為電腦的關係, 可以收集相當相當龐大的資料
有些人會根據目的, 整理成有用的資訊, 但是沒整理過得一樣還是龐雜的資料
而到了現在最火紅的資料時代, 人們會希望從資料中, 找尋許多有用的資訊
甚至整理成智慧, 加以吸收
然後面對成千上百數萬的資料, 有時候我們無從下手
或者講, 太多事情隱藏在資料中了, 或者有些東西其實一開始根本沒記載
只能透過間接的關係去推導出來 (所以也不會有label class...etc)
當你今天身為一名 Data Scientist, 你被囑咐去對這些龐大的資料做分析
就很有可能會碰到, 只有 feature, 卻沒有任何 class 的狀況
因為收集資料的時候不一定會想到之後會需要那樣的用途
所以 unsupervised learning 要幫助的事情是, 他可以從 data 中"自動的"找尋關係
或者講, 他可以幫我把相近關係的資料做區別出來
跟 classification 很像, 只是差在, 你不用跟我講答案, 我靠你給我的資料做猜測就好
K-Means
我要提的 k-means 就是一種相當 trivial 的演算法
(k-means 強者請不要打我臉 我只是在我blog打嘴泡)
wiki: K-means
k-means 的方法就可以幫忙區分, 事情很簡單
k-means, k 是由使用者設定的, 就是他會找出 k 個 cluster 出來, 也就是可以分成 k class
每個聚集的類別, 都會有個中心點 (centroid), 顧名思義, 也就是這個 class 的中心點
1. 隨機設定中心點, k 個
一開始並不知道中心點會在哪邊, 所以在最一開始的時候, 我隨機找 k 點當中心點
(注意, 並不用找 data 上有的點, 點中心不一定會在 data 裡面)
但不用擔心, 這中心點是會變得, 也就是其實不管你設定在哪裡起始
中心點都會慢慢的移動到最後比較像是一堆點的中心處!!
2. 將所有點都要根據中心點, 來決定這些點是哪些類別
也就是說, 假設我是一筆資料, 我旁邊有兩個不同類別的中心點
誰比較靠近我, 我就是那個類別的, 簡單吧, 通常是用點距離的方式去計算
(只要可以計算距離的都可以拿來運用)
全部點都決定過中心點之後, 就要調整中心點了
2.1. 針對同一個 class 的 data, 平均這些點的 feature, 當作新的中心點
也就是說, 假設某中心點有三筆 data, (1,3), (2, 3), (3, 0)
則新的中心點為: (1 + 2 + 3) / 3, (3 + 3 + 0)/ 3 = (2, 2)
所有類別中心點都調整過後, 再繼續回到第2步驟 - > 第3步驟 - > 第2步驟 -> 第3步驟 ...etc
一直做到沒有點會被更換為止, 或者, 做個 100 次, 並且透過 cost 來決定
下面我用多一點的圖形來解釋流程
首先我這張設定為 3 class, 所以隨機挑選三個點, 如畫面上的紅, 藍, 綠三個 X
再來就是要 assign class to point, 根據距離公式的結果, 會如下圖所示
左下角大多是藍色, 中間一小部分是紅色, 右上大約是綠色
跟中心點鄰近的點都改成相對應的顏色了
然後是移動中心點到新的中心位置, 如下圖
這樣, 就基本上完成了第一回合
因為這圖滿簡單的, 才大概再 2 個回合, 很快就會變成下圖所示
就很輕易的把三種 class 給分出來了 !! 厲害吧 ~ !
不過 k-means 會 suffering 在local minimum (也就是不一定會是最佳解)
根據這篇 stackoverflow, 可以看到一個很好的例子說明為甚麼
http://stackoverflow.com/questions/14577329/why-doesnt-k-means-give-the-global-minima
那要解決 local minimum 則是一件 NP-Hard 的事情...嗯......悲劇XD
其實有加強版演算法 - bisecting k-means, 但是...等我有空再補強了...
那另外常見的問題是, 我怎麼知道我要找幾個類別?
wiki: cluster 需要幾個 class
其實常見的有3種作法
1. Rule of thumb
就只是個慣例, 用不用見仁見智
2. Elbow method, 手軸定理
這則是很單純的把 Cost 跟 number of cluster 圖表畫出來, 也就是要嘗試多種 class 然後繪出圖表
手軸定理意思就是, 如果今天 Cost 的走勢跟上圖類似, 像是一個人的手臂彎曲
則彎曲最大處, 即很有可能此份 data 最適合的 class 數量, 但這也只是一種嘗試的方式
3. according to the purpose
當然最後還是要回歸, 你到底想要從這份 data 找出怎樣的 class 來決定到底要分幾個 cluster
留言
張貼留言