Einfacher Ansatz zum Zuweisen von Clustern für neue Daten nach k-Means Clustering

Question

Ich bin k-Means Clustering auf einem Datenrahmen df1, und ich bin auf der Suche nach einem einfachen Ansatz zur Berechnung der nächsten Cluster-Zentrum für jede Beobachtung in a neuer Datenrahmen df2 (mit den gleichen Variablennamen). Stellen Sie sich df1 als Trainingssatz und df2 im Testset vor; Ich möchte auf dem Trainingssatz clustern und jeden Testpunkt dem richtigen Cluster zuweisen.

Ich weiß, wie dies zu tun mit der apply Funktion und ein paar einfachen benutzerdefinierten Funktionen (iV Beiträge zum Thema haben in der Regel vorgeschlagen, so ähnlich):

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) 

Allerdings bin ich der Vorbereitung dieses Clustering Beispiel für einen Kurs, in dem Studenten mit der apply Funktion nicht vertraut sind, also würde ich viel bevorzugen, wenn ich die Cluster zu df2 mit einer eingebauten Funktion zuweisen könnte. Gibt es irgendwelche praktischen eingebauten Funktionen, um den nächsten Cluster zu finden?

Answer 1

könnten Sie verwenden das flexclust-Paket, das ein implementiertes predict Methode für k-Mittel hat:

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") 

Es gibt auch Konvertierungsmethoden, die Ergebnisse von Cluster-Funktionen wie stats::kmeans oder cluster::pam zu konvertieren zu Objekten der Klasse kcca und umgekehrt:

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

Etwas, das mir sowohl in der Frage als auch in den Flexclust-Ansätzen aufgefallen ist, ist, dass sie eher langsam sind (hier ein Benchmark für ein Trainings- und Testset mit 1 Million Beobachtungen mit je 2 Merkmalen).

Montage des ursprünglichen Modells recht schnell ist:

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 

Die Lösung, die ich in der Frage gestellt ist langsam auf die Testsatz-Cluster-Zuordnungen zu berechnen, da sie separat ruft closest.cluster für jeden Test-Sollwert:

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

Inzwischen scheint das flexclust Paket eine Menge Aufwand hinzufügen, unabhängig davon, ob wir das angepasste Modell mit as.kcca konvertieren oder einem neu sie mit kcca passen (obwohl der pr ediction am Ende viel schneller)

# 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 

Es scheint, dass es hier eine andere sinnvoller Ansatz ist: eine schnelle k-nächsten Nachbarn Lösung wie ein kd-Baum mit dem nächsten Nachbarn jedes Testsatz Beobachtung zu finden innerhalb der Satz von Clusterschwerpunkten. Dies kann kompakt geschrieben werden und ist relativ zügigen:

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