在k均值聚类之后为新数据分配聚类的简单方法

Question

我在数据帧df1上运行k-means聚类,我正在寻找一种简单的方法来计算新数据帧df2(具有相同变量名称)中每个观察点的最近聚类中心.将df1视为训练集,将df2视为测试集; 我想在训练集上进行聚类,并将每个测试点分配给正确的聚类.

我知道如何使用apply函数和一些简单的用户定义函数(关于该主题的先前帖子通常提出类似的东西):

df1 <- data.frame(x=runif(100), y=runif(100))
df2 <- data.frame(x=runif(100), y=runif(100))
km <- kmeans(df1, centers=3)
closest.cluster <- function(x) {
  cluster.dist <- apply(km$centers, 1, function(y) sqrt(sum((x-y)^2)))
  return(which.min(cluster.dist)[1])
}
clusters2 <- apply(df2, 1, closest.cluster)

但是,我正在为一个学生将不熟悉该apply功能的课程准备这个聚类示例,所以我更喜欢我是否可以使用内置函数将聚类分配给df2.有没有方便的内置函数来查找最近的集群？

Answer 1

您可以使用flexclust包,它具有predictk-means 的实现方法:

library("flexclust")
data("Nclus")

set.seed(1)
dat <- as.data.frame(Nclus)
ind <- sample(nrow(dat), 50)

dat[["train"]] <- TRUE
dat[["train"]][ind] <- FALSE

cl1 = kcca(dat[dat[["train"]]==TRUE, 1:2], k=4, kccaFamily("kmeans"))
cl1    
#
# call:
# kcca(x = dat[dat[["train"]] == TRUE, 1:2], k = 4)
#
# cluster sizes:
#
#  1   2   3   4 
#130 181  98  91 

pred_train <- predict(cl1)
pred_test <- predict(cl1, newdata=dat[dat[["train"]]==FALSE, 1:2])

image(cl1)
points(dat[dat[["train"]]==TRUE, 1:2], col=pred_train, pch=19, cex=0.3)
points(dat[dat[["train"]]==FALSE, 1:2], col=pred_test, pch=22, bg="orange")

还有转换方法将结果从集群函数转换为类stats::kmeans或cluster::pam对象的对象,kcca反之亦然:

as.kcca(cl, data=x)
# kcca object of family ‘kmeans’ 
#
# call:
# as.kcca(object = cl, data = x)
#
# cluster sizes:
#
#  1  2 
#  50 50 

Answer 2

关于问题中的方法和灵活方法,我注意到的一点是它们相当缓慢(在此基准测试用于训练和测试集,其中100万个观测值各有2个特征).

适合原始模型的速度相当快:

set.seed(144)
df1 <- data.frame(x=runif(1e6), y=runif(1e6))
df2 <- data.frame(x=runif(1e6), y=runif(1e6))
system.time(km <- kmeans(df1, centers=3))
#    user  system elapsed 
#   1.204   0.077   1.295 

我在问题中发布的解决方案在计算测试集群分配时很慢,因为它单独调用closest.cluster每个测试设置点:

system.time(pred.test <- apply(df2, 1, closest.cluster))
#    user  system elapsed 
#  42.064   0.251  42.586 

同时,flexclust软件包似乎增加了很多开销,无论我们是否将自己的模型转换为as.kcca适合自己的模型kcca(尽管最后的预测要快得多)

# APPROACH #1: Convert from the kmeans() output
system.time(km.flexclust <- as.kcca(km, data=df1))
#    user  system elapsed 
#  87.562   1.216  89.495 
system.time(pred.flexclust <- predict(km.flexclust, newdata=df2))
#    user  system elapsed 
#   0.182   0.065   0.250 

# Approach #2: Fit the k-means clustering model in the flexclust package
system.time(km.flexclust2 <- kcca(df1, k=3, kccaFamily("kmeans")))
#    user  system elapsed 
# 125.193   7.182 133.519 
system.time(pred.flexclust2 <- predict(km.flexclust2, newdata=df2))
#    user  system elapsed 
#   0.198   0.084   0.302 

似乎这里还有另一种明智的方法:使用像kd树这样的快速k近邻解决方案来找到群集质心集中每个测试集观察的最近邻居.这可以紧凑地编写并且相对快速:

library(FNN)
system.time(pred.knn <- get.knnx(km$center, df2, 1)$nn.index[,1])
#    user  system elapsed 
#   0.315   0.013   0.345 
all(pred.test == pred.knn)
# [1] TRUE