kmeans聚類理論篇

前言

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

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

?

算法原理

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

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

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

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

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

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

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

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

?

算法收斂

從kmeans的算法可以發(fā)現(xiàn)，SSE其實(shí)是一個嚴(yán)格的坐標(biāo)下降（Coordinate Decendet）過程。設(shè)目標(biāo)函數(shù)SSE如下：

SSE(,,…,) =?

采用歐式距離作為變量之間的聚類函數(shù)。每次朝一個變量的方向找到最優(yōu)解，也就是求偏倒數(shù)，然后等于0，可得

c_i=?其中m是c_i所在的簇的元素的個數(shù)

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

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

?

0-1規(guī)格化

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

其中屬于A。

輪廓系數(shù)

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

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

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

對于元素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，說明x_i與其簇內(nèi)元素的平均距離小于最近的其他簇，表示聚類效果不好。如果a_i趨于0，或者b_i足夠大，那么s_i趨近與1，說明聚類效果比較好。

?

K值選取

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

?

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

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

1 2 3

library(fpc)?# install.packages("fpc") data(iris) head(iris)

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

1 2 3 4 5 6 7 8 9

# 0-1 正規(guī)化數(shù)據(jù) min.max.norm <-?function(x){ ????(x-min(x))/(max(x)-min(x)) } raw.data <- iris[,1:4] norm.data <- data.frame(sl = min.max.norm(raw.data[,1]), ????????????????????????????????????????sw = min.max.norm(raw.data[,2]), ????????????????????????????????????????pl = min.max.norm(raw.data[,3]), ????????????????????????????????????????pw = min.max.norm(raw.data[,4]))

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

1 2 3 4 5 6 7 8 9 10 11 12 13

# k取2到8，評估K K <- 2:8 round <- 30?# 每次迭代30次，避免局部最優(yōu) rst <- sapply(K,?function(i){ ????print(paste("K=",i)) ????mean(sapply(1:round,function(r){ ????????print(paste("Round",r)) ????????result <- kmeans(norm.data, i) ????????stats <- cluster.stats(dist(norm.data), result$cluster) ????????stats$avg.silwidth ????})) }) plot(K,rst,type='l',main='輪廓系數(shù)與K的關(guān)系', ylab='輪廓系數(shù)')

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

?

?

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

1 2 3 4 5 6 7 8

# 降緯度觀察 old.par <- par(mfrow = c(1,2)) k = 2?# 根據(jù)上面的評估 k=2最優(yōu) clu <- kmeans(norm.data,k) mds = cmdscale(dist(norm.data,method="euclidean")) plot(mds, col=clu$cluster, main='kmeans聚類 k=2', pch = 19) plot(mds, col=iris$Species, main='原始聚類', pch = 19) par(old.par)

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

?

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

?

kmeans最佳實(shí)踐

1. 隨機(jī)選取訓(xùn)練數(shù)據(jù)中的k個點(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值有時候需要根據(jù)應(yīng)用場景選取，而不能完全的依據(jù)評估參數(shù)選取。

?

K-Means小結(jié)

　　　　K-Means是個簡單實(shí)用的聚類算法，這里對K-Means的優(yōu)缺點(diǎn)做一個總結(jié)。

　　　　K-Means的主要優(yōu)點(diǎn)有：

　　　　1）原理比較簡單，實(shí)現(xiàn)也是很容易，收斂速度快。

　　　　2）聚類效果較優(yōu)。

　　　　3）算法的可解釋度比較強(qiáng)。

　　　　4）主要需要調(diào)參的參數(shù)僅僅是簇?cái)?shù)k。

　　　　K-Means的主要缺點(diǎn)有：

　　　　1）K值的選取不好把握(改進(jìn)：可以通過在一開始給定一個適合的數(shù)值給k，通過一次K-means算法得到一次聚類中心。對于得到的聚類中心，根據(jù)得到的k個聚類的距離情況，合并距離最近的類，因此聚類中心數(shù)減小，當(dāng)將其用于下次聚類時，相應(yīng)的聚類數(shù)目也減小了，最終得到合適數(shù)目的聚類數(shù)?？梢酝ㄟ^一個評判值E來確定聚類數(shù)得到一個合適的位置停下來，而不繼續(xù)合并聚類中心。重復(fù)上述循環(huán)，直至評判函數(shù)收斂為止，最終得到較優(yōu)聚類數(shù)的聚類結(jié)果)。

　　　　2）對于不是凸的數(shù)據(jù)集比較難收斂(改進(jìn)：基于密度的聚類算法更加適合，比如DESCAN算法)

　　　　3）如果各隱含類別的數(shù)據(jù)不平衡，比如各隱含類別的數(shù)據(jù)量嚴(yán)重失衡，或者各隱含類別的方差不同，則聚類效果不佳。

　　　　4） 采用迭代方法，得到的結(jié)果只是局部最優(yōu)。

　　　　5） 對噪音和異常點(diǎn)比較的敏感(改進(jìn)1：離群點(diǎn)檢測的LOF算法，通過去除離群點(diǎn)后再聚類，可以減少離群點(diǎn)和孤立點(diǎn)對于聚類效果的影響；改進(jìn)2：改成求點(diǎn)的中位數(shù)，這種聚類方式即K-Mediods聚類（K中值）)。

? ? ? ? ? ?6）初始聚類中心的選擇(改進(jìn)1：k-means++;改進(jìn)2：二分K-means)。

?

轉(zhuǎn)載于:https://www.cnblogs.com/yumoye/p/10328134.html

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的十大经典数据挖掘算法之k-means的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。