algorithm - que - algoritmos de agrupamiento clustering

Agrupe n puntos en k grupos de igual tamaño

Question

Posible duplicado:
Variación del algoritmo K-medias con igual tamaño de grupo

EDITAR: como casperOne me lo señala, esta pregunta es un duplicado. De todas formas, aquí hay una pregunta más general que cubre esta: https://stats.stackexchange.com/questions/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points

Mis requerimientos

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

Mis experimentaciones

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

Pero mi problema es que K-medias produce grupos de aproximadamente el mismo tamaño, donde necesito que los grupos sean exactamente del mismo tamaño (o que sean más precisos: necesito que tengan un tamaño entre el piso (n / k) y ceil (n / k)).

Antes de señalarlo, sí, intenté la primera respuesta aquí. Variación del algoritmo K-means con igual tamaño de grupo , lo que parece una buena idea.

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

Aquí está el pseudo código que 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 con este algoritmo es que cerca del final del proceso (cuando me acerco a k), tenemos que elegir un grupo j en c ''(donde j> i porque debemos dejar solo los grupos ya procesados), pero Este grupo j que encontramos puede estar lejos del grupo i, rompiendo así el concepto de grupo.

Mi pregunta

¿Existe un algoritmo posterior de K-medias o una variante de K-medias que pueda cumplir mis requisitos, o estoy equivocado desde el principio y necesito encontrar otro algoritmo de agrupación?

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

Answer 1

Al no ser un experto en el tema, una vez tuve que idear un algoritmo simple para agrupar las ubicaciones en un mapa, donde todos los puntos debían ser parte de un clúster, y los clústeres estaban vinculados de varias maneras (no solo en tamaño). conteo de puntos), pero también en algunas otras medidas que dependían de diversos factores).

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

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

Answer 2

Prueba esta variación de k-medias:

Inicialización :

• Elija k centros del conjunto de datos al azar, o incluso mejor usando la estrategia kmeans ++
• para cada punto, calcule la distancia al centro del clúster más cercano y cree un montón para este
• dibuje puntos del montón, y asignarlos al clúster más cercano, a menos que el clúster ya esté demasiado lleno. Si es así, calcule el siguiente centro de clúster más cercano y vuelva a insertarlo en el montón

Al final, debe tener una partición que satisfaga sus requisitos de la misma cantidad de objetos por grupo (asegúrese de que los últimos grupos también tengan el número correcto. Los primeros grupos deben tener objetos ceil , el resto exactamente floor objetos.) Tenga en cuenta que el uso de un montón garantiza que los grupos permanezcan convexos: si ya no fueran convexos, habría habido un mejor candidato de intercambio.

Paso de iteración :

Requisitos: una lista para cada grupo con "propuestas de intercambio" (objetos que preferirían estar en un grupo diferente).

Paso E : calcular los centros de clúster actualizados como en k-means regulares

Paso M : Iterando a través de todos los puntos (ya sea solo uno o todos en un lote)

Calcule el centro del clúster más cercano al objeto / todos los centros del clúster que estén más cerca que los clústeres actuales. Si es un cluster diferente:

• Si el otro clúster es más pequeño que el clúster actual, simplemente muévalo al nuevo clúster
• Si hay una propuesta de intercambio del otro clúster (o cualquier clúster con una distancia más baja), intercambie las asignaciones de clúster de dos elementos (si hay más de una oferta, elija la que tenga la mayor mejora)
• De lo contrario, indique una propuesta de swap para el otro cluster.

Los tamaños de los grupos permanecen invariables (+ - la diferencia entre el techo y el piso), los objetos solo se mueven de un grupo a otro siempre y cuando resulte en una mejora de la estimación. Por lo tanto, debe converger en algún punto como k-means. Aunque podría ser un poco más lento (es decir, más iteraciones).

No sé si esto ha sido publicado o implementado antes. Es justo lo que intentaría (si intentara k-means. Hay algoritmos de agrupamiento mucho mejores).