grupo N puntos en k grupos de igual tamaño

Question

posible duplicado:
K-means algorithm variation with equal cluster size

EDIT: como casperOne punto que a mí esta pregunta es un duplicado. De todas formas aquí hay una cuestión más generalizada que cubren esta: https://stats.stackexchange.com/questions/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points

Mis requisitos

En un proyecto que necesito grupo n puntos (x, y) en k grupos de igual tamaño (n/k) . Donde xey son números flotantes dobles, n puede oscilar entre 100 y 10000 y k puede variar de 2 a 100. También se conoce k antes de que se ejecute el algoritmo.

Mis experimentos

empecé a resolver el problema utilizando el algoritmo http://en.wikipedia.org/wiki/K-means_clustering, que funcionan muy bien y rápido para producir exactamente k grupos de aproximadamente el mismo tamaño.

Pero mi problema es esto, los K-means producen grupos de aproximadamente el mismo tamaño, donde necesito que los conglomerados sean exactamente del mismo tamaño (o para ser más precisos: los necesito para tener un tamaño entre el piso/k) y ceil (n/k)).

Antes de que me lo digas, sí, probé la primera respuesta aquí K-means algorithm variation with equal cluster size, lo cual parece una buena idea.

La idea principal es postprocesar la matriz de producción de clúster mediante K-means. Desde el clúster más grande hasta el más pequeño. Reducimos el tamaño de los clusters que tienen más de n/k miembros moviendo puntos extra a otro clúster más cercano. Dejando solos los grupos que ya están reducidos.

Aquí es el pseudo código Implementé:

n is the number of point 
k is the number of cluster 
m = n/k (the ideal cluster size) 
c is the array of cluster after K-means 
c' = c sorted by size in descending order 
for each cluster i in c' where i = 1 to k - 1 
    n = size of cluster i - m (the number of point to move) 
    loop n times 
     find a point p in cluster i with minimal distance to a cluster j in c' where j > i 
     move point p from cluster i to cluster j 
    end loop 
    recalculate centroids 
end for each 

El problema de este algoritmo es que cerca del final del proceso (cuando i se acercan a k), tenemos que elegir un j clúster en c '(donde j> i porque tenemos que dejar solos los clústers ya procesados), pero este clúster j que encontramos puede estar lejos del clúster i, lo que rompe el concepto de clúster.

Mi pregunta

¿Hay un post algoritmo k-medias o una variante K-significa que puede satisfacer mis necesidades, o estoy mal desde el principio y tengo que encontrar otro algoritmo de agrupamiento?

PD: No me importa implementar la solución yo mismo, pero sería genial si puedo usar una biblioteca, e idealmente en JAVA.

Answer 1

Al no ser un experto en el tema, una vez tuve que encontrar un algoritmo simple para agrupar ubicaciones en un mapa, donde cada punto necesitaba ser parte de un clúster, y los clústeres estaban atados de varias maneras (no solo en tamaño (es decir, conteo de puntos), pero también en algunas otras medidas que dependen de factores variables).

Al encontrar primero los puntos "difíciles", y luego crecer en grupos desde allí, obtuve los mejores resultados. puntos "difíciles" serían los puntos que son difíciles de alcanzar, p.porque estarían solos en las afueras del área total, o porque ayudarían a golpear otra condición de límite del clúster más que otros puntos. Esto ayudó a crecer agrupamientos perfectamente alineados, dejando muy poco solitarios y el trabajo manual correspondiente para colocarlos.

Esto puede ayudarlo si su algoritmo actual normalmente encuentra estos puntos difíciles al final.

Answer 2

probar este KMeans variación:

Inicialización:

• elegir k centros del conjunto de datos al azar, o incluso mejor usando kmeans ++ estrategia
• para cada punto, calcular la distancia a su centro de clúster más cercano y crear un montón para este
• puntos de extracción del montón, y asignarlos al clúster más cercano, a menos que el clúster ya esté sobrecargado Si es así, calcular el centro del cúmulo más cercano al lado y vuelva a insertar en el montón

Al final, usted debe tener una Paritioning que satisfaga sus requisitos del + -1 mismo número de objetos por grupo (asegúrese de que la última unos pocos los clústeres también tienen el número correcto. Los primeros clústeres m deben tener objetos ceil, el resto exactamente floor objetos). Tenga en cuenta que el uso de un montón asegura que los conglomerados permanezcan convexos: si ya no fueran convexos, habría un mejor candidato de intercambio .

paso de iteración:

requisitos: una lista para cada cluster con "propuestas Swap" (objetos que prefieren estar en un clúster diferente).

E paso: calcular los centros de los conglomerados actualizados como en regular de k-medias

M paso: iterar a través de todos los puntos (o bien sólo uno, o todos en un solo lote)

Compute más cercana centro de clúster para objetar/todos los centros de clúster que están más cerca que los clústeres actuales. Si se trata de un clúster diferente:

• Si el otro grupo es más pequeño que el clúster actual, sólo se mueven a la nueva agrupación
• Si hay una propuesta de canje de la otra agrupación (o cualquier grupo con una distancia inferior), intercambie las dos asignaciones de racimo elemento (si hay más de una oferta, elegir el que tenga la mayor mejora)
• lo contrario, indicar una propuesta de canje para el otro grupo se mantienen

los tamaños de clúster invariante (+ - la diferencia ceil/piso), son objetos solo se movió de un clúster a otro siempre que produzca una mejora de la estimación. Por lo tanto, debería converger en algún punto como k-means. Sin embargo, podría ser un poco más lento (es decir, más iteraciones).

No sé si esto se ha publicado o implementado anteriormente. Es lo que probaría (si intentara k-means. Hay algoritmos de agrupación mucho mejores.)