KMeans
KMeans是一種無監(jiān)督學習聚類方法, 目的是發(fā)現(xiàn)數(shù)據(jù)中數(shù)據(jù)對象之間的關(guān)系熟丸，將數(shù)據(jù)進行分組，組內(nèi)的相似性越大，組間的差別越大怀大，則聚類效果越好呀闻。
無監(jiān)督學習,也就是沒有對應的標簽,只有數(shù)據(jù)記錄.通過KMeans聚類,可以將數(shù)據(jù)劃分成一個簇,進而發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)系.
[圖片上傳失敗...(image-fa9971-1543240223005)]
原理
KMeans算法是將數(shù)據(jù)聚類成k個簇,其中每個
, 算法具體描述:
- 隨機選擇k個聚類質(zhì)心點:
;
- 重復下面過程直到收斂{
對于每一個數(shù)據(jù)i,計算其屬于的簇:
;
對于每個簇j,重新計算簇質(zhì)心:
}
用語言描述來說,就是:隨機確定k個初始點作為簇中心; 為每個數(shù)據(jù)分配簇[計算每條數(shù)據(jù)和簇中心的相似度,分配到最相似的簇上];根據(jù)簇中的數(shù)據(jù)點對每個簇中心進行更新.反復重復直到收斂為止.
偽代碼:
創(chuàng)建k個點作為起始質(zhì)心;
當任意一個點的簇分配結(jié)果發(fā)生改變時:
對數(shù)據(jù)集中的每個數(shù)據(jù)點:
對每個質(zhì)心:
計算質(zhì)心和當前數(shù)據(jù)點的相似度
將數(shù)據(jù)點分配到最近的質(zhì)心所代表的簇上
對于每個簇,計算簇中所有點的均值,并將均值作為新的簇中心[質(zhì)心]
存在問題及其處理方法
- 必須事先給出k(要生成的簇的數(shù)目),而且對初值敏感捡多，對于不同的初始值，可能會導致不同結(jié)果局服。
- 不適合于發(fā)現(xiàn)非凸面形狀的簇或者大小差別很大的簇。
- 對于“躁聲”和孤立點數(shù)據(jù)是敏感的山涡，因為簇的中心是通過計算數(shù)據(jù)的平均值得到的唆迁，這些數(shù)據(jù)的存在會使聚類的中心發(fā)生很大的偏移;
- 容易陷入到局部最優(yōu)解.
對于局部最優(yōu)解的問題,一方面可以像決策樹一樣,對最后生成的聚類效果進行"剪枝"處理,但有所不同,因為要保證簇數(shù)目不變,所有處理進行"剪枝處理"外,還需要"增枝處理",具體可以依據(jù)某種指標[SSE sum of square errors]選擇指標最大的簇嘗試劃分, 然后選擇兩個進行合并,保證簇的數(shù)目不變.
另一方面,可以對kmeans進行優(yōu)化處理,存在一種二分kMeans處理.
二分k均值:首先將所有數(shù)據(jù)看成一個簇,然后將該簇一分為二,之后選擇其中一個簇繼續(xù)劃分, 如何選擇簇取決于對其劃分是否可以最大程度的降低SSE的值;然后反復重復,直到得到K個簇為止.
代碼實現(xiàn)
github地址: repository
