你的位置:首页 > 数据库

[数据库]寻找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 index18 19   R <- NULL20   for (i in 1:k) {21     R <- c(max((S[i] + S[-i])/D[-i, i]), R)22   }23   DB <- sum(R)/k24   return(DB)25 }26 27 # 循环计算不同聚类数的DB_Index指数28 29 DB <- NULL30 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