尋找KMeans的最優K

　　K-Means聚類算法是最為經典的，同時也是使用最為廣泛的一種基於劃分的聚類算法，它屬於基於距離的無監督聚類算法。KMeans算法簡單實用，在機器學習算法中占有重要的地位。對於KMeans算法而言，如何確定K值，確實讓人頭疼的事情。

最近這幾天一直忙於構建公司的推薦引擎。對用戶群體的分類，要使用KMeans聚類算法，就研究了一下。

探索K的選擇

　　對數據進行分析之前，采用一些探索性分析手段還是很有必要的。

　　對於高維空間，我們可以采用降維的方式，把多維向量轉化為二維向量。好在，R語言包裡提供了具體的實現，MDS是個比較好的方式。

多維標度分析(MDS)是一種將多維空間的研究對象簡化到低維空間進行定位、分析和歸類，同時又保留對象間原始關系的數據分析方法。R語言包提供了經典MDS和非度量MDS。

　　通過MDS對數據進行處理後，采用ggplot繪出點圖，看看數據分布的情況，使得我們對要聚類的數據有個直觀的認識。

SSE和Silhouette Coefficient系數

　　我們還可以通過SSE和Silhouette Coefficient系數的方法評估最優K。譬如對K從1到15計算不同的聚類的SSE，由於kmeans算法中的隨機因數，每次結果都不一樣，為了減少時間結果的偶然性，對於每個k值，都重復運行50次，求出平均的SSE，最後繪制出SSE曲線。Silhouette Coefficient也采用同樣做法。

　　　　　　　　　　　　　　SSE結果

　　　　　　　　　　　　　　Silhouette Coefficient結果

　　　　從上圖來看，8和9明顯有一個尖峰。我們大體可以確定K的數目是8。值得注意在有些時候，這種方法有可能無效，但仍然不失為一個很好的方法。

DB INDEX准則

　　DB INdex准則全稱Davies Bouldin index 。類內離散度和類間聚類常被用來判斷聚類的有效性，DB INdex准則同時使用了類間聚類和類內離散度。通過計算這個指數，來確定到底哪個Cluster最合理

R語言代碼如下：

 1 data <- read.csv("a.csv", header = T,
 2 
 3     stringsAsFactors = F)
 4 DB_index <- function(x, cl, k) {
 5     data <- split.data.frame(x, cl$cluster)
 6     # 計算類內離散度
 7 
 8     S <- NULL
 9     for (i in 1:k) {
10         S[i] <- sum(rowSums((data[[i]] - cl$centers[i])^2))/nrow(data[[i]])
11     }
12 
13     # 計算類間聚類
14 
15     D <- as.matrix(dist(cl$centers))
16 
17     # 計算DB index
18 
19     R <- NULL
20     for (i in 1:k) {
21         R <- c(max((S[i] + S[-i])/D[-i, i]), R)
22     }
23     DB <- sum(R)/k
24     return(DB)
25 }
26 
27 # 循環計算不同聚類數的DB_Index指數
28 
29 DB <- NULL
30 for (i in 2:15) {
31 
32     cl <- kmeans(data, i)
33 
34     DB <- c(DB_index(data, cl, i), DB)
35 
36 }
37 plot(2:15, DB)
38 lines(2:15, DB)

CANOPY算法

　　Canopy聚類最大的特點是不需要事先指定k值(即clustering的個數)，與其他聚類算法相比，Canopy聚類雖然精度較低，但其在速度上有很大優勢。

因此可以使用Canopy聚類先對數據進行“粗”聚類，得到k值後再使用K-means進行進一步“細”聚類。這個算法不多說了，mahout聚類裡有具體實現。

參閱：https://en.wikipedia.org/wiki/Davies-Bouldin_index