這篇文章來自於大四系上修的一堂課,主要的練習為用R實做出K-means的概念,那首先我們就得先知道,K-means的核心是甚麼,那就讓我們來看看吧
What is k-means?
K-means是一種機器學習的演算法,其本身屬於非監督式學習,而非監督式學習又是什麼呢?簡單來說,就是你丟給電腦的資料是沒有標記的,就讓演算法自己表現吧類似的概念,關於更詳細的內容之後有機會,在做一個詳細的整理,這裡就先大概帶過,而k-means本身的概念比較像是clustering,以成語來說就是「物以類聚」。
好,這張圖應該有很好的幫助你了解K-means了。沒錯,就是像你看到的一樣,我們拿到一筆資料後,透過K-means演算法,成功的將資料分成了三類,而當我們分成三類後,對們在後續說故事或分析才會更有幫助,若是我們只使用原始資料(左邊),可能就難以看出什麼端倪,但當我們將資料做好cluster後,我們就可以發現,喔~原來是有三種pattern的資料在裡面,也可以幫助我們更好的理解我們的資料,好的,事不宜遲,我們就來用R建立我們的K-means 演算法吧(基本上R裡已經有套件可以使用,這裡實際建置是為了瞭解其運作,並且可以有更多的練習。
我們需要準備什麼
1.給定一個cluster的中心:這點相當的重要,我們可以random尋找,畢竟在這過程中,K-means的中心點會慢慢的移動,直到滿足我們設定的條件,但我們會發現,第一個找的中心點,如果找得不好,最後分出來的群也會受到影響。
2.開始把資料分派到最靠近的中心,對了,K就是你想要幾個中心點的意思,K=3,代表你決定了三個中心點,最終會分成三群。
3.計算新群的新的中心點(取這個群中所有資料的平均)
4.重複 2~3的步驟直到收斂為止(就是達到你要的結果為止),那要怎麼收斂呢?接著就要來看一點數學啦
這個數學式子其實非常的好懂,X_i就是每個資料點,而U_j就是每個新群的中心點(也就是該資料群的mean),我們的目標就是找到,在該群中的資料點,到中心點的距離總和的最小值。 既然已經明白了,那我們就開始吧!
R實作部分
我們使用的資料長得像這樣,資料為txt檔,資料跟資料是
用Tab隔開的
資料點的分布大概長得像這個樣子,用R分常簡單直接的plot函數
接著我們將我們的kmeans寫成函式,Let’s Go,整段的程式碼大概像底下這樣
kmeansfun = function(x,k){
tol=0.0001
l=10
iter=1
dists=matrix(0,nrow = nrow(x),ncol=k)
ini=sample(nrow(x),k,replace = FALSE)
center=matrix(0,ncol=ncol(x),nrow=k)
center=x[ini,]#第一次的中點
nsse=vector()
grp=vector()
sse=vector()
while(l>tol){
for(i in 1 : nrow(x) ){
for(j in 1:k){
dists[i,j]=sqrt(sum((x[i,]-center[j,])^2))
}
}
#分組
for(i in 1:nrow(x)){
grp[i]=which.min(dists[i,])
}
newcenter=matrix(0,ncol=ncol(x),nrow=k) #指定新的中心點為分完群的平均點
for(i in 1:k){
newcenter[i , ] = apply(x[which(grp==i),],2,mean)
sse[i ] = sum((x[which(grp==i),]-newcenter[ i , ])^2)
}
nsse[iter]=sum(sse)
l=sum(center-newcenter)^2
center = newcenter
iter=iter+1
#此處為停止的條件
}
plot(x=c(2:iter-1),y=nsse,type='b',main='SSE圖隨著疊代的變化')
return(list(grp=grp, center=center, sse=nsse[iter-1],iter=iter))
}
但現在讓我們來一段一段的拆解它吧!
一開始的寫法就是R的函式的寫法,tol為我們的容忍值,因為資料不管怎麼算因為公式的關係不會為0,因此我們就必須設定一個容忍值,當我們用公式算出來的值仍然大於容忍值時,我們就繼續指派新的群中心,直到算出小於容忍值的中心點,dists為我們拿來存放跟三個中心點的距離,以我們的資料而言 nrow=100,k=3,所以我們會建出一個100X3的matrix,而ini則是我們以R內建函數sample,從nrow(100)中,挑出k(3)個數字,此處是用位置的方式操作,可以對應到center=x[ini,]這一行,因此我們的步驟1:指派起始中點在這裡就默默完成了,剩下的三個變數是指派以讓後續使用。
kmeansfun = function(x,k){
tol=0.0001
l=10
iter=1
dists=matrix(0,nrow = nrow(x),ncol=k)
ini=sample(nrow(x),k,replace = FALSE)
center=matrix(0,ncol=ncol(x),nrow=k)
center=x[ini,]#第一次的中點
nsse=vector()
grp=vector()
sse=vector()
我們在剛剛將l設為了10,而tol設定0.0001,因此這個while迴圈會成立,那讓我們來看看while迴圈裡有什麼吧
一開始,我們用了兩個for迴圈,而作的事情,就是把每個資料點到起始中心點的距離算出來,並存在dist裡,而我們計算距離的方法,是採用歐幾里德距離。
算好距離之後,非常的直觀,就是選擇離自己最近的中心,加入他們,如此所有的資料就會被分好群(群的數量為你設定的k),這就是步驟2:分群
接著有新的群之後,我們在把新的群的data取平均值,並將其舉派為新的值(感覺就是,喔,我們現在是新團體,啊剛剛好你到我們每個人的距離總和是最近的,那你就是新的中心啦)。於是,我們又默默的完成了步驟3:找新的中心
while(l>tol){
for(i in 1 : nrow(x) ){
for(j in 1:k){
dists[i,j]=sqrt(sum((x[i,]-center[j,])^2))
}
}
#分組
for(i in 1:nrow(x)){
grp[i]=which.min(dists[i,])
}
newcenter=matrix(0,ncol=ncol(x),nrow=k) #指定新的中心點為分完群的平均點
接著就是要把我們計算的新的中心放入我們的newcenter裡啦,這裡有使用一個工具apply,而許多使用R語言的前輩也會建議多使用apply族函數,而原因則是效率問題,因為apply族方法是用C語言寫的,如果操作的當,就能避免使用for迴圈(在R裡用迴圈非常的慢),之後有機會會在特別寫一篇整理apply族的筆記,apply的用法通常會有三個參數apply(data,margin,function),data放資料,margin=1表示按行計算,=2表示按列計算,function就是要套用的算式啦,所以這句code的解讀為,將被分到第i組的資料,按列計算平均。而SSE就是指Sum of Square Errors。
l這個變數,代表了舊的中心點和新找的中心點的距離平方,當它小於我們的容忍值時,代表它的變動不大,我們就可以停止我們的迴圈。到這邊為止,我們的k-means就完成啦。
for(i in 1:k){
newcenter[i , ] = apply(x[which(grp==i),],2,mean)
sse[i ] = sum((x[which(grp==i),]-newcenter[ i , ])^2)
}
nsse[iter]=sum(sse)
l=sum(center-newcenter)^2
center = newcenter
iter=iter+1
#此處為停止的條件
}
plot(x=c(2:iter-1),y=nsse,type='b',main='SSE圖隨著疊代的變化')
return(list(grp=grp, center=center, sse=nsse[iter-1],iter=iter))
}
K-means動起來
#k=3
kmeansfun(hw8_q2_data,3)
我的設計是讓他回傳四個值,第一個是每個資料點的分組,第二個是中心點,第三個是SSE,第四個是共迭代了幾次
我們可以看到SSE隨著迭代次數增加而降低,最後在一個區間震盪
我們的資料點被很好的分組啦!!!
#將值存到cr裡(grp,center...)
cr<-kmeansfun(hw8_q2_data,3)
#割成兩個視窗
par(mfrow=c(1,2))
plot(hw8_q2_data)
plot(hw8_q2_data,col=cr$grp)
points(cr$center,col=1:3,pch=16,cex=1.5)
結論:當你多按幾次的時候,會發現分組有點不太一樣,這是因為K-means會受到選擇的第一個起始點很大的影響,因此,也有許多玩家在討論如何找到最佳起始點,大家可以自己去試試
而k-means由於在算新的中點時,使用了mean,但我們也知道,mean會受到outlier很大的影響而失準;同樣的,也使得k-means會outlier相當的敏感。
簡單的實作,當然k-means還有很多其他的應用,等待發掘,之後有機會再繼續研究~