Problema de la "agrupación" en los grupos más similares

Question

No creo que el siguiente problema pueda resolverse con la agrupación de k-means. Sin embargo, no estoy seguro. Bien, déjame describir el problema. Necesito encontrar una forma o un algoritmo que agrupe a los miembros de un conjunto de datos dado (de enteros positivos) de manera que la diferencia entre las medias de los grupos sea minimizado (no maximizado, como siempre). Hay dos restricciones:

1. El número de grupos no debe superar log(N) base 2. N es el tamaño del array de entrada. Supongamos que N = 16, siempre.

2. El tamaño del grupo debe ser al menos log(N) de base 2. Aquí es 4.

Vea el ejemplo siguiente. Se agradece la orientación para la solución de este problema.

   for input array = (12, 14, 16, 16, 18, 19, 20, 21, 24, 26, 27, 29, 29, 30, 31, 32)

Una de las soluciones podría ser la siguiente:

set    group           mean
1   (12, 14, 31, 32)    22.25
2   (16, 16, 29, 30)    22.75
3   (18, 19, 27, 29)    23.25
4   (20, 21, 24, 26)    22.75

Answer 1

He aquí una idea no probada de cómo adaptar el algo de K-means para intentar resolver su tarea. Usted debe saber que la mayoría de las implementaciones estándar de K-means clustering incluyen el llamado medios para correr opción. Con esta opción, en cada iteración se actualiza el centro del clúster (se recalcula) inmediatamente después de asignar un punto a ese clúster (en lugar de después de asignar todos los puntos a sus clústeres más cercanos, como en el modo típico). Si se utilizan los medios de ejecución junto con dicha modificación del algo que se asigna un punto al más lejos (y no el más cercano), el centro, entonces se espera que los centros de los clústeres converjan durante todo el proceso, y se termine con clústeres que se superpongan al máximo.

Answer 2

Esto no es realmente una agrupación. Me recuerda al clásico problema de empaquetado de cubos, que desgraciadamente es NP-difícil.

https://en.wikipedia.org/wiki/Bin_packing_problem

En serio, evite el término "cluster". Cluster suele referirse a objetos "similares", aquí son muy disímiles.

Una estrategia clásica sería calcular primero la media óptima (= media de todos los datos). A continuación, utilizar una estrategia codiciosa para crear grupos razonablemente cercanos a esta media, por ejemplo, combinando valores altos y bajos. Por último, intente optimizar el resultado moviendo o intercambiando objetos para mejorar el criterio objetivo hasta la convergencia. Para ello, podrías incluso probar con un algoritmo genético.