K-Means聚類演算法是最為經典的，同時也是使用最為廣泛的一種基於劃分的聚類演算法，它屬於基於距離的無監督聚類演算法。KMeans演算法簡單實用，在機器學習演算法中占有重要的地位。對於KMeans演算法而言，如何確定K值，確實讓人頭疼的事情。 最近這幾天一直忙於構建公司的推薦引擎。對用戶群體的分類，要使用KM ...
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
