來(lái)源 | bourneli(李伯韜)的技術(shù)博客

前言

kmeans是最簡(jiǎn)單的聚類算法之一,，但是運(yùn)用十分廣泛。最近在工作中也經(jīng)常遇到這個(gè)算法,。kmeans一般在數(shù)據(jù)分析前期使用,，選取適當(dāng)?shù)膋，將數(shù)據(jù)分類后,，然后分類研究不同聚類下數(shù)據(jù)的特點(diǎn),。

本文記錄學(xué)習(xí)kmeans算法相關(guān)的內(nèi)容，包括算法原理,，收斂性,，效果評(píng)估聚，最后帶上R語(yǔ)言的例子,，作為備忘,。
 

算法原理

kmeans的計(jì)算方法如下：

1 隨機(jī)選取k個(gè)中心點(diǎn)

2 遍歷所有數(shù)據(jù)，將每個(gè)數(shù)據(jù)劃分到最近的中心點(diǎn)中

3 計(jì)算每個(gè)聚類的平均值,，并作為新的中心點(diǎn)

4 重復(fù)2-3,，直到這k個(gè)中線點(diǎn)不再變化（收斂了），或執(zhí)行了足夠多的迭代

時(shí)間復(fù)雜度：O(I*n*k*m)

空間復(fù)雜度：O(n*m)

其中m為每個(gè)元素字段個(gè)數(shù),，n為數(shù)據(jù)量,，I為跌打個(gè)數(shù)。一般I,，k,，m均可認(rèn)為是常量，所以時(shí)間和空間復(fù)雜度可以簡(jiǎn)化為O(n),，即線性的,。
 

算法收斂

也就是當(dāng)前聚類的均值就是當(dāng)前方向的最優(yōu)解（最小值），這與kmeans的每一次迭代過(guò)程一樣,。所以,，這樣保證SSE每一次迭代時(shí)，都會(huì)減小,，最終使SSE收斂,。

由于SSE是一個(gè)非凸函數(shù)（non-convex function），所以SSE不能保證找到全局最優(yōu)解,，只能確保局部最優(yōu)解,。但是可以重復(fù)執(zhí)行幾次kmeans，選取SSE最小的一次作為最終的聚類結(jié)果,。
 

0-1規(guī)格化

由于數(shù)據(jù)之間量綱的不相同,，不方便比較。舉個(gè)例子,，比如游戲用戶的在線時(shí)長(zhǎng)和活躍天數(shù),，前者單位是秒,，數(shù)值一般都是幾千，而后者單位是天,，數(shù)值一般在個(gè)位或十位,，如果用這兩個(gè)變量來(lái)表征用戶的活躍情況，顯然活躍天數(shù)的作用基本上可以忽略,。所以,，需要將數(shù)據(jù)統(tǒng)一放到0~1的范圍，將其轉(zhuǎn)化為無(wú)量綱的純數(shù)值,，便于不同單位或量級(jí)的指標(biāo)能夠進(jìn)行比較和加權(quán),。具體計(jì)算方法如下：

輪廓系數(shù)

輪廓系數(shù)（Silhouette Coefficient）結(jié)合了聚類的凝聚度（Cohesion）和分離度（Separation），用于評(píng)估聚類的效果,。該值處于-1~1之間,，值越大，表示聚類效果越好,。具體計(jì)算方法如下：

對(duì)于第i個(gè)元素x_i,，計(jì)算x_i與其同一個(gè)簇內(nèi)的所有其他元素距離的平均值，記作a_i,，用于量化簇內(nèi)的凝聚度,。

選取x_i外的一個(gè)簇b，計(jì)算x_i與b中所有點(diǎn)的平均距離,，遍歷所有其他簇,，找到最近的這個(gè)平均距離，記作b_i,，用于量化簇之間分離度,。

對(duì)于元素x_i，輪廓系數(shù)s_i = (b_i – a_i)/max(a_i,，b_i)

計(jì)算所有x的輪廓系數(shù),，求出平均值即為當(dāng)前聚類的整體輪廓系數(shù)

從上面的公式，不難發(fā)現(xiàn)若s_i小于0,，說(shuō)明x_i與其簇內(nèi)元素的平均距離小于最近的其他簇,，表示聚類效果不好。如果a_i趨于0,，或者b_i足夠大，那么s_i趨近與1,，說(shuō)明聚類效果比較好,。
 

K值選取

在實(shí)際應(yīng)用中，由于Kmean一般作為數(shù)據(jù)預(yù)處理,，或者用于輔助分類貼標(biāo)簽,。所以k一般不會(huì)設(shè)置很大,。可以通過(guò)枚舉,，令k從2到一個(gè)固定值如10,，在每個(gè)k值上重復(fù)運(yùn)行數(shù)次kmeans(避免局部最優(yōu)解)，并計(jì)算當(dāng)前k的平均輪廓系數(shù),，最后選取輪廓系數(shù)最大的值對(duì)應(yīng)的k作為最終的集群數(shù)目,。
 

實(shí)際應(yīng)用

下面通過(guò)例子（R實(shí)現(xiàn)，完整代碼見附件）講解kmeans使用方法,，會(huì)將上面提到的內(nèi)容全部串起來(lái)

1 library(fpc) # install.packages("fpc")

2 data(iris)

3 head(iris)

加載實(shí)驗(yàn)數(shù)據(jù)iris,，這個(gè)數(shù)據(jù)在機(jī)器學(xué)習(xí)領(lǐng)域使用比較頻繁，主要是通過(guò)畫的幾個(gè)部分的大小,，對(duì)花的品種分類,，實(shí)驗(yàn)中需要使用fpc庫(kù)估計(jì)輪廓系數(shù)，如果沒(méi)有可以通過(guò)install.packages安裝,。

1 # 0-1 正規(guī)化數(shù)據(jù)

2 min.max.norm <- function(x){

3 (x-min(x))/(max(x)-min(x))

4 }

5 raw.data <- iris[,，1：4]

6 norm.data <- data.frame(sl = min.max.norm(raw.data[，1]),，

7 sw = min.max.norm(raw.data[,，2])，

8 pl = min.max.norm(raw.data[,，3]),，

9 pw = min.max.norm(raw.data[，4]))

對(duì)iris的4個(gè)feature做數(shù)據(jù)正規(guī)化,，每個(gè)feature均是花的某個(gè)不為的尺寸,。

1 # k取2到8，評(píng)估K

2 K <- 2：8

3 round <- 30 # 每次迭代30次,，避免局部最優(yōu)

4 rst <- sapply(K,， function(i){

5 print(paste("K="，i))

6 mean(sapply(1：round,，function(r){

7 print(paste("Round",，r))

8 result <- kmeans(norm.data， i)

9 stats <- cluster.stats(dist(norm.data),， result$cluster)

10 stats$avg.silwidth

11 }))

12 })

13 plot(K,，rst，type='l',，main='輪廓系數(shù)與K的關(guān)系',， ylab='輪廓系數(shù)')

評(píng)估k，由于一般K不會(huì)太大,，太大了也不易于理解,，所以遍歷K為2到8,。由于kmeans具有一定隨機(jī)性，并不是每次都收斂到全局最小,，所以針對(duì)每一個(gè)k值,，重復(fù)執(zhí)行30次，取并計(jì)算輪廓系數(shù),，最終取平均作為最終評(píng)價(jià)標(biāo)準(zhǔn),，可以看到如下的示意圖，

當(dāng)k取2時(shí),，有最大的輪廓系數(shù),，雖然實(shí)際上有3個(gè)種類。

1 # 降緯度觀察

2 old.par <- par(mfrow = c(1,，2))

3 k = 2 # 根據(jù)上面的評(píng)估 k=2最優(yōu)

4 clu <- kmeans(norm.data,，k)

5 mds = cmdscale(dist(norm.data，method="euclidean"))

6 plot(mds,， col=clu$cluster,， main='kmeans聚類 k=2'， pch = 19)

7 plot(mds,， col=iris$Species,， main='原始聚類'， pch = 19)

8 par(old.par)

聚類完成后,，有源原始數(shù)據(jù)是4緯,，無(wú)法可視化，所以通過(guò)多維定標(biāo)(Multidimensional scaling)將緯度將至2為,，查看聚類效果,，如下

可以發(fā)現(xiàn)原始分類中和聚類中左邊那一簇的效果還是擬合的很好的，右測(cè)原始數(shù)據(jù)就連在一起,，kmeans無(wú)法很好的區(qū)分,，需要尋求其他方法。
 

kmeans最佳實(shí)踐

1. 隨機(jī)選取訓(xùn)練數(shù)據(jù)中的k個(gè)點(diǎn)作為起始點(diǎn)

2. 當(dāng)k值選定后,，隨機(jī)計(jì)算n次,，取得到最小開銷函數(shù)值的k作為最終聚類結(jié)果，避免隨機(jī)引起的局部最優(yōu)解

3. 手肘法選取k值：繪制出k--開銷函數(shù)閃點(diǎn)圖,，看到有明顯拐點(diǎn)（如下）的地方,，設(shè)為k值，可以結(jié)合輪廓系數(shù),。

4. k值有時(shí)候需要根據(jù)應(yīng)用場(chǎng)景選取,，而不能完全的依據(jù)評(píng)估參數(shù)選取。

參考

[1] kmeans 講義by Andrew NG

[2] 坐標(biāo)下降法（Coordinate Decendent）

[3] 數(shù)據(jù)規(guī)格化

[4] 維基百科--輪廓系數(shù)

[5] kmeans算法介紹

[6] 降為方法—多維定標(biāo)

[7] Week 8 in Machine Learning， by Andrew NG,， Coursera