Ponderado en el algoritmo de agrupamiento

Question

Estoy buscando dividir a los 50 estados de los estados unidos en n regiones. Los requisitos de la división son:

• A cada estado se le asigna un valor
• Los valores de estado en cada región, deben sumar para hacer que incluso los totales de grupo (tan cerca como sea posible). Que parece hacer de esta una bandeja de embalaje problema de la variación.
• Los estados de cada región deben estar geográficamente agrupados, Por ejemplo, CA+O+WA deben ser agrupados a pesar de CA+GA+RI produce una menor desviación estándar de valor regionales totales.

Este post le pregunta a una pregunta similar. K-means clustering parece una exageración ya que los estados sólo tienen que ser los vecinos, sin embargo, estoy bastante verde para las estadísticas.

Como nota al margen, estoy en última instancia, buscan implementar esto en Ruby (que tiene un R de la biblioteca plugin).

ACTUALIZACIÓN

La motivación detrás de la agrupación es para facilidad de los viajes, por lo tanto clúster de compacidad es más importante que el estado de adyacencia (es decir, larga, estrecha, de cadena en forma de racimos que deben evitarse).

Answer 1

Realmente estás dado un plano gráfico y quieres encontrar los componentes conectados que tienen el mínimo de "propagación" en valores. Aunque no sé cómo obtener una respuesta con la que probablemente se encuentre garantías, la siguiente heurística puede trabajar bien.

Suponga que todos los estados tienen pesos entre 0 y $2^k$ decir (para algunos $k$). La etiqueta de todos los estados con pesos entre 0 y $2^{k-1}-1$ "0" y el resto como "1". Encontrar los componentes conectados de la gráfica con la misma etiqueta. Ahora recurse en cada componente.

Básicamente lo que estamos haciendo es encontrar los componentes conectados de tal manera que en cada componente, los valores no varían demasiado. Si 2 es demasiado gruesa una granularidad para usted, usted puede elegir algún otro factor entre 1 y 2.

El punto de parada para la recursividad es cuando la varianza dentro de un grupo así formado es lo suficientemente pequeño. Usted va a terminar con una agrupación jerárquica en la que las hojas son el deseado grupos.

Answer 2

Esto se ve como un estándar de la variación de bin packing problema con restricciones para mí.

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

Hace no tanto como la agrupación para mí: las distancias parece ser únicamente una restricción que sólo los estados adyacentes debe ser seleccionado. Así que ninguna de las cosas que se encuentran bajo el término de "análisis de cluster" te ayudará mucho. Es una restricción de optimización que usted está tratando de hacer.

Answer 3

¿Qué acerca del uso de Partición de Gráfico (http://en.wikipedia.org/wiki/Graph_partition)?

Donde el gráfico de aquí sería el de Estados Unidos, donde los nodos son los estados, los bordes son las conexiones entre los estados (es decir, no existe una arista entre dos estados si son adyacentes el uno al otro). Los subdiagramas, o las particiones se los territorios. Quieres que se divida en uniforme de los componentes (la igualdad de ingresos y tal vez otras restricciones), por lo que tendría una variación de uniforme de partición de gráfico.