resueltos - Análisis de conglomerados en R: determinar el número óptimo de conglomerados

metodos de clustering

Question

Al ser un novato en R, no estoy seguro de cómo elegir el mejor número de grupos para hacer un análisis de k-means. Después de trazar un subconjunto de datos a continuación, ¿cuántos grupos serán apropiados? ¿Cómo puedo realizar el análisis dendro de cluster?

n = 1000
kk = 10    
x1 = runif(kk)
y1 = runif(kk)
z1 = runif(kk)    
x4 = sample(x1,length(x1))
y4 = sample(y1,length(y1)) 
randObs <- function()
{
  ix = sample( 1:length(x4), 1 )
  iy = sample( 1:length(y4), 1 )
  rx = rnorm( 1, x4[ix], runif(1)/8 )
  ry = rnorm( 1, y4[ix], runif(1)/8 )
  return( c(rx,ry) )
}  
x = c()
y = c()
for ( k in 1:n )
{
  rPair  =  randObs()
  x  =  c( x, rPair[1] )
  y  =  c( y, rPair[2] )
}
z <- rnorm(n)
d <- data.frame( x, y, z )

Answer 1

Con el fin de determinar el k-cluster óptimo en los métodos de agrupamiento. Usualmente uso el método Elbow acompañado por el procesamiento paralelo para evitar consumir tiempo. Este código puede muestrear así:

Metodo de codo

elbow.k <- function(mydata){
dist.obj <- dist(mydata)
hclust.obj <- hclust(dist.obj)
css.obj <- css.hclust(dist.obj,hclust.obj)
elbow.obj <- elbow.batch(css.obj)
k <- elbow.obj$k
return(k)
}

Corriente codo paralelo

no_cores <- detectCores()
    cl<-makeCluster(no_cores)
    clusterEvalQ(cl, library(GMD))
    clusterExport(cl, list("data.clustering", "data.convert", "elbow.k", "clustering.kmeans"))
 start.time <- Sys.time()
 elbow.k.handle(data.clustering))
 k.clusters <- parSapply(cl, 1, function(x) elbow.k(data.clustering))
    end.time <- Sys.time()
    cat(''Time to find k using Elbow method is'',(end.time - start.time),''seconds with k value:'', k.clusters)

Funciona bien.

Answer 2

Es difícil agregar algo también una respuesta tan elaborada. Aunque creo que deberíamos mencionar la identify aquí, particularmente porque @Ben muestra muchos ejemplos de dendrogramas.

d_dist <- dist(as.matrix(d))   # find distance matrix 
plot(hclust(d_dist)) 
clusters <- identify(hclust(d_dist))

identify permite elegir de forma interactiva los grupos de un dendrograma y almacena sus elecciones en una lista. Pulsa Esc para salir del modo interactivo y volver a la consola R. Tenga en cuenta que la lista contiene los índices, no los nombres (en lugar de cutree ).

Answer 3

Espléndida respuesta de Ben. Sin embargo, me sorprende que el método de Propagación de Afinidad (AP) haya sido sugerido aquí solo para encontrar el número de agrupaciones para el método k-means, donde en general AP hace un mejor trabajo agrupando los datos. Por favor, vea el artículo científico que apoya este método en la ciencia aquí:

Frey, Brendan J. y Delbert Dueck. "Agrupación mediante el paso de mensajes entre puntos de datos". science 315.5814 (2007): 972-976.

Entonces, si no está predispuesto hacia k-significa, sugiero usar AP directamente, que agrupará los datos sin necesidad de conocer el número de agrupaciones:

library(apcluster)
apclus = apcluster(negDistMat(r=2), data)
show(apclus)

Si las distancias euclidianas negativas no son apropiadas, entonces puede usar otras medidas de similitud proporcionadas en el mismo paquete. Por ejemplo, para similitudes basadas en correlaciones de Spearman, esto es lo que necesita:

sim = corSimMat(data, method="spearman")
apclus = apcluster(s=sim)

Tenga en cuenta que esas funciones para similitudes en el paquete AP se proporcionan simplemente para simplificar. De hecho, la función apcluster () en R aceptará cualquier matriz de correlaciones. Lo mismo antes con corSimMat () se puede hacer con esto:

sim = cor(data, method="spearman")

o

sim = cor(t(data), method="spearman")

Dependiendo de lo que quieras agrupar en tu matriz (filas o columnas).

Answer 4

Estos métodos son geniales, pero cuando se intenta encontrar k para conjuntos de datos mucho más grandes, estos pueden ser extremadamente lentos en R.

Una buena solución que he encontrado es el paquete "RWeka", que tiene una implementación eficiente del algoritmo X-Means, una versión extendida de K-Means que se adapta mejor y determinará el número óptimo de clusters para usted.

Primero querrá asegurarse de que Weka esté instalado en su sistema y de que XMeans esté instalado a través de la herramienta de administración de paquetes de Weka.

library(RWeka)

# Print a list of available options for the X-Means algorithm
WOW("XMeans")

# Create a Weka_control object which will specify our parameters
weka_ctrl <- Weka_control(
    I = 1000,                          # max no. of overall iterations
    M = 1000,                          # max no. of iterations in the kMeans loop
    L = 20,                            # min no. of clusters
    H = 150,                           # max no. of clusters
    D = "weka.core.EuclideanDistance", # distance metric Euclidean
    C = 0.4,                           # cutoff factor ???
    S = 12                             # random number seed (for reproducibility)
)

# Run the algorithm on your data, d
x_means <- XMeans(d, control = weka_ctrl)

# Assign cluster IDs to original data set
d$xmeans.cluster <- x_means$class_ids

Answer 5

Las respuestas son geniales. Si desea darle una oportunidad a otro método de agrupación en clústeres, puede utilizar la agrupación jerárquica y ver cómo se dividen los datos.

> set.seed(2)
> x=matrix(rnorm(50*2), ncol=2)
> hc.complete = hclust(dist(x), method="complete")
> plot(hc.complete)

Dependiendo de cuántas clases necesites, puedes cortar tu dendrograma como;

> cutree(hc.complete,k = 2)
 [1] 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 2 1 1 1
[26] 2 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 2 1 1 1 1 1 1 1 2

Si ?cutree verás las definiciones. Si su conjunto de datos tiene tres clases, será simplemente cutree(hc.complete, k = 3) . El equivalente para cutree(hc.complete,k = 2) es cutree(hc.complete,h = 4.9) .

Answer 6

Si su pregunta es how can I determine how many clusters are appropriate for a kmeans analysis of my data? , entonces aquí hay algunas opciones. El artículo de wikipedia sobre la determinación de números de grupos tiene una buena revisión de algunos de estos métodos.

Primero, algunos datos reproducibles (los datos en la Q son ... poco claros para mí):

n = 100
g = 6 
set.seed(g)
d <- data.frame(x = unlist(lapply(1:g, function(i) rnorm(n/g, runif(1)*i^2))), 
                y = unlist(lapply(1:g, function(i) rnorm(n/g, runif(1)*i^2))))
plot(d)

Uno Busque una curva o codo en la suma de la cuadrícula de error de cuadrado (SSE). Consulte http://www.statmethods.net/advstats/cluster.html & http://www.mattpeeples.net/kmeans.html para obtener más información. La ubicación del codo en la trama resultante sugiere un número adecuado de grupos para los kmeans:

mydata <- d
wss <- (nrow(mydata)-1)*sum(apply(mydata,2,var))
  for (i in 2:15) wss[i] <- sum(kmeans(mydata,
                                       centers=i)$withinss)
plot(1:15, wss, type="b", xlab="Number of Clusters",
     ylab="Within groups sum of squares")

Podríamos concluir que este método indicaría 4 grupos:

Dos Puede hacer una partición alrededor de los medoides para estimar el número de agrupaciones utilizando la función pamk en el paquete fpc.

library(fpc)
pamk.best <- pamk(d)
cat("number of clusters estimated by optimum average silhouette width:", pamk.best$nc, "/n")
plot(pam(d, pamk.best$nc))

# we could also do:
library(fpc)
asw <- numeric(20)
for (k in 2:20)
  asw[[k]] <- pam(d, k) $ silinfo $ avg.width
k.best <- which.max(asw)
cat("silhouette-optimal number of clusters:", k.best, "/n")
# still 4

Tres Criterio de Calinsky: otro enfoque para diagnosticar cuántos grupos se adaptan a los datos. En este caso tratamos de 1 a 10 grupos.

require(vegan)
fit <- cascadeKM(scale(d, center = TRUE,  scale = TRUE), 1, 10, iter = 1000)
plot(fit, sortg = TRUE, grpmts.plot = TRUE)
calinski.best <- as.numeric(which.max(fit$results[2,]))
cat("Calinski criterion optimal number of clusters:", calinski.best, "/n")
# 5 clusters!

Cuatro Determine el modelo óptimo y la cantidad de conglomerados según el Criterio de Información Bayesiano para la expectativa-maximización, inicializado por agrupamiento jerárquico para modelos de mezcla Gaussianos parametrizados

# See http://www.jstatsoft.org/v18/i06/paper
# http://www.stat.washington.edu/research/reports/2006/tr504.pdf
#
library(mclust)
# Run the function to see how many clusters
# it finds to be optimal, set it to search for
# at least 1 model and up 20.
d_clust <- Mclust(as.matrix(d), G=1:20)
m.best <- dim(d_clust$z)[2]
cat("model-based optimal number of clusters:", m.best, "/n")
# 4 clusters
plot(d_clust)

Cinco Agrupación de propagación de afinidad (AP), ver http://dx.doi.org/10.1126/science.1136800

library(apcluster)
d.apclus <- apcluster(negDistMat(r=2), d)
cat("affinity propogation optimal number of clusters:", length(d.apclus@clusters), "/n")
# 4
heatmap(d.apclus)
plot(d.apclus, d)

Seis Estadística de brechas para estimar el número de conglomerados. Ver también algunos códigos para una salida gráfica agradable . Tratando de 2-10 grupos aquí:

library(cluster)
clusGap(d, kmeans, 10, B = 100, verbose = interactive())

Clustering k = 1,2,..., K.max (= 10): .. done
Bootstrapping, b = 1,2,..., B (= 100)  [one "." per sample]:
.................................................. 50 
.................................................. 100 
Clustering Gap statistic ["clusGap"].
B=100 simulated reference sets, k = 1..10
 --> Number of clusters (method ''firstSEmax'', SE.factor=1): 4
          logW   E.logW        gap     SE.sim
 [1,] 5.991701 5.970454 -0.0212471 0.04388506
 [2,] 5.152666 5.367256  0.2145907 0.04057451
 [3,] 4.557779 5.069601  0.5118225 0.03215540
 [4,] 3.928959 4.880453  0.9514943 0.04630399
 [5,] 3.789319 4.766903  0.9775842 0.04826191
 [6,] 3.747539 4.670100  0.9225607 0.03898850
 [7,] 3.582373 4.590136  1.0077628 0.04892236
 [8,] 3.528791 4.509247  0.9804556 0.04701930
 [9,] 3.442481 4.433200  0.9907197 0.04935647
[10,] 3.445291 4.369232  0.9239414 0.05055486

Aquí está el resultado de la implementación de la estadística de la brecha de Edwin Chen:

Siete También puede resultarle útil explorar sus datos con clustergrams para visualizar la asignación de clústeres, consulte http://www.r-statistics.com/2010/06/clustergram-visualization-and-diagnostics-for-cluster-analysis-r-code/ para más detalles.

Ocho El paquete NbClust proporciona 30 índices para determinar el número de grupos en un conjunto de datos.

library(NbClust)
nb <- NbClust(d, diss="NULL", distance = "euclidean", 
        min.nc=2, max.nc=15, method = "kmeans", 
        index = "alllong", alphaBeale = 0.1)
hist(nb$Best.nc[1,], breaks = max(na.omit(nb$Best.nc[1,])))
# Looks like 3 is the most frequently determined number of clusters
# and curiously, four clusters is not in the output at all!

Si su pregunta es how can I produce a dendrogram to visualize the results of my cluster analysis , entonces debe comenzar con estos: http://www.statmethods.net/advstats/cluster.html http://www.r-tutor.com/gpu-computing/clustering/hierarchical-cluster-analysis http://gastonsanchez.wordpress.com/2012/10/03/7-ways-to-plot-dendrograms-in-r/ Y vea aquí para más exóticos métodos: http://cran.r-project.org/web/views/Cluster.html

Aquí están algunos ejemplos:

d_dist <- dist(as.matrix(d))   # find distance matrix 
plot(hclust(d_dist))           # apply hirarchical clustering and plot

# a Bayesian clustering method, good for high-dimension data, more details:
# http://vahid.probstat.ca/paper/2012-bclust.pdf
install.packages("bclust")
library(bclust)
x <- as.matrix(d)
d.bclus <- bclust(x, transformed.par = c(0, -50, log(16), 0, 0, 0))
viplot(imp(d.bclus)$var); plot(d.bclus); ditplot(d.bclus)
dptplot(d.bclus, scale = 20, horizbar.plot = TRUE,varimp = imp(d.bclus)$var, horizbar.distance = 0, dendrogram.lwd = 2)
# I just include the dendrogram here

También para datos de alta dimensión está la biblioteca pvclust que calcula los valores p para el agrupamiento jerárquico a través del remuestreo de bootstrap multiescala. Aquí está el ejemplo de la documentación (no funcionará en datos de dimensiones tan bajas como en mi ejemplo):

library(pvclust)
library(MASS)
data(Boston)
boston.pv <- pvclust(Boston)
plot(boston.pv)

¿Algo de eso ayuda?