silhouette - Medios K: Lloyd, Forgy, MacQueen, Hartigan-Wong

plot k means in r

Question

Estoy trabajando con el algoritmo K-Means en R y quiero descubrir las diferencias de los 4 algoritmos Lloyd, Forgy, MacQueen y Hartigan-Wong que están disponibles para la función "kmeans" en el paquete de estadísticas.

Sin embargo, fui notable para obtener una respuesta suficiente a esta pregunta.

Solo encontré información rara vez: (Visite http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/K-Means )

A partir de esta descripción, Lloyd, Forgy y Hartigan-Wong me parecen lo mismo. Minimizar la suma interna de cuadrados o Minimizar la distancia euclidiana es lo mismo.

MacQueen es diferente en el caso de que actualice los dos grupos involucrados si un objeto se mueve a otro grupo si tengo razón.

Sin embargo, todavía no veo en qué puntos estos Algoritmos son diferentes.

Answer 1

Ir a la página 16-
Esto tiene una explicación clara de los algos de Gorgy / Llyods, MacQueen, Hatigan-Wong.

https://core.ac.uk/download/pdf/27210461.pdf

Answer 2

R proporciona el algoritmo de Lloyd''s como una opción para kmeans (); el algoritmo predeterminado, por Hartigan y Wong (1979) es mucho más inteligente. Al igual que el algoritmo de MacQueen (MacQueen, 1967), actualiza los centroides cada vez que se mueve un punto; también hace elecciones inteligentes (que ahorran tiempo) al verificar el clúster más cercano. Por otro lado, el algoritmo k-means de Lloyd''s es el primero y el más simple de todos estos algoritmos de agrupamiento.

El algoritmo de Lloyd (Lloyd, 1957) toma un conjunto de observaciones o casos (piense: filas de una matriz nxp, o puntos en los reales) y los agrupa en k grupos. Intenta minimizar la suma de cuadrados dentro del cluster.

donde u_i es la media de todos los puntos en el grupo S_i. El algoritmo procede de la siguiente manera (le ahorraré la formalidad de la notación exhaustiva):

Sin embargo, hay un problema con la implementación de R y el problema surge al considerar varios puntos de partida. Debo tener en cuenta que generalmente es prudente considerar varios puntos de partida diferentes, ya que se garantiza que el algoritmo converge, pero no se garantiza que cubra a un óptimo global. Esto es particularmente cierto para problemas grandes y de alta dimensión. Comenzaré con un ejemplo simple (grande, no particularmente difícil).

(Aquí pegaré algunas imágenes ya que no podemos escribir fórmulas matemáticas con látex)

Tenga en cuenta que la solución es muy similar a la obtenida anteriormente, aunque el ordenamiento de los grupos es arbitrario. ¡Más importante aún, el trabajo solo tomó 0.199 segundos en paralelo! Seguramente esto es demasiado bueno para ser verdad: el uso de 3 núcleos de procesador debería, en el mejor de los casos, tomar un tercio del tiempo de nuestra primera ejecución (secuencial). ¿Es esto un problema? Suena como el almuerzo gratis. No hay problema con un almuerzo gratis de vez en cuando, ¿verdad?

Esto no siempre funciona con las funciones R, pero a veces tenemos la oportunidad de ver directamente el código. Éste es uno de esos momentos. Voy a poner este código en el archivo, mykmeans.R, y lo editaré a mano, insertando sentencias cat () en varios lugares. Esta es una forma inteligente de hacerlo, usando sink () (aunque esto parece no funcionar en Sweave, funcionará interactivamente):

> sink("mykmeans.R")
> kmeans
> sink()

Ahora edite el archivo, cambie el nombre de la función y agregue sentencias cat (). Tenga en cuenta que también tiene que eliminar una línea de cola:

Luego podemos repetir nuestras exploraciones, pero usando mykmeans ():

> source("mykmeans.R")
> start.kmeans <- proc.time()[3]
> ans.kmeans <- mykmeans(x, 4, nstart = 3, iter.max = 10, algorithm = "Lloyd")
JJJ statement 1: 0 elapsed time.
JJJ statement 5: 2.424 elapsed time.
JJJ statement 6: 2.425 elapsed time.
JJJ statement 7: 2.52 elapsed time.
JJJ statement 6: 2.52 elapsed time.
JJJ statement 7: 2.563 elapsed time.

Ahora estamos en el negocio: la mayor parte del tiempo se consumió antes de la declaración 5 (lo sabía, por supuesto, razón por la cual la declaración 5 era 5 en lugar de 2) ... Puedes seguir jugando con ella

Aquí está el código:

#######################################################################
# kmeans()

N <- 100000
x <- matrix(0, N, 2)
x[seq(1,N,by=4),] <- rnorm(N/2)
x[seq(2,N,by=4),] <- rnorm(N/2, 3, 1)
x[seq(3,N,by=4),] <- rnorm(N/2, -3, 1)
x[seq(4,N,by=4),1] <- rnorm(N/4, 2, 1)
x[seq(4,N,by=4),2] <- rnorm(N/4, -2.5, 1)
start.kmeans <- proc.time()[3]
ans.kmeans <- kmeans(x, 4, nstart=3, iter.max=10, algorithm="Lloyd")
ans.kmeans$centers
end.kmeans <- proc.time()[3]
end.kmeans - start.kmeans

these <- sample(1:nrow(x), 10000)
plot(x[these,1], x[these,2], pch=".")
points(ans.kmeans$centers, pch=19, cex=2, col=1:4)

library(foreach)
library(doMC)
registerDoMC(3)
start.kmeans <- proc.time()[3]
ans.kmeans.par <- foreach(i=1:3) %dopar% {
  return(kmeans(x, 4, nstart=1, iter.max=10, algorithm="Lloyd"))
}
TSS <- sapply(ans.kmeans.par, function(a) return(sum(a$withinss)))
ans.kmeans.par <- ans.kmeans.par[[which.min(TSS)]]
ans.kmeans.par$centers
end.kmeans <- proc.time()[3]
end.kmeans - start.kmeans

sink("mykmeans.Rfake")
kmeans
sink()

source("mykmeans.R")
start.kmeans <- proc.time()[3]
ans.kmeans <- mykmeans(x, 4, nstart=3, iter.max=10, algorithm="Lloyd")
ans.kmeans$centers
end.kmeans <- proc.time()[3]
end.kmeans - start.kmeans

#######################################################################
# Diving

x <- read.csv("Diving2000.csv", header=TRUE, as.is=TRUE)
library(YaleToolkit)
whatis(x)

x[1:14,c(3,6:9)]

meancol <- function(scores) {
  temp <- matrix(scores, length(scores)/7, ncol=7)
  means <- apply(temp, 1, mean)
  ans <- rep(means,7)
  return(ans)
}
x$panelmean <- meancol(x$JScore)

x[1:14,c(3,6:9,11)]

meancol <- function(scores) {
  browser()
  temp <- matrix(scores, length(scores)/7, ncol=7)
  means <- apply(temp, 1, mean)
  ans <- rep(means,7)
  return(ans)
}

x$panelmean <- meancol(x$JScore)

Aquí está la descripción:

Number of cases: 10,787 scores from 1,541 dives (7 judges score each
dive) performed in four events at the 2000 Olympic Games in Sydney,
Australia.

Number of variables: 10.

Description: A full description and analysis is available in an
article in The American Statistician (publication details to be
announced).

Variables:

Event       Four events, men''s and women''s 3M and 10m.
Round       Preliminary, semifinal, and final rounds.
Diver       The name of the diver.
Country     The country of the diver.
Rank        The final rank of the diver in the event.
DiveNo      The number of the dive in sequence within round.
Difficulty  The degree of difficulty of the dive.
JScore      The score provided for the judge on this dive.
Judge       The name of the judge.
JCountry    The country of the judge.

Y un conjunto de datos para experimentar con él https://www.dropbox.com/s/urgzagv0a22114n/Diving2000.csv