Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 5 down vote favorite
2

I am looking to divide the 50 US states into n regions. The requirements in dividing are:

  • Each state will be assigned a value
  • The state values in each region should sum to make even group totals (as closely as possible). Which seems to make this a bin packing problem variation.
  • The states in each region need to be geographically clustered, For example, CA+OR+WA should be clustered even though CA+GA+RI produces a smaller standard deviation of regional value totals.

This post asks a similar question. K-Means clustering seems overkill as states just need to be neighbors, however I am pretty green to stats.

As a side-note, I am ultimately looking to implement this in Ruby (which has a R library plugin).

UPDATE

The motivation behind the clustering is for ease of travel, therefore cluster compactness is more important than state adjacency (i.e. long, narrow, string-shaped clusters should be avoided).

share|improve this question
One difficulty with problems like this is that often several--or many--alternative solutions can be found, none of which is perfect. To make progress, you need to stipulate how to make trade-offs. In this case, could you tell us how to balance a poorer clustering of states against a potential improvement in achieving equality of total group values? – whuber♦ May 29 '12 at 14:25
@whuber Good question. I am still working through the best trade-offs in balancing. Ideally it would be to just reduce or increase the number of states in a region, though I don't think that will be enough. An example use-case would be using population for each state value. For many values of n, CA would end up being the only state in its region. Regions don't have to be perfectly balanced, just looking for closest. Next I would sacrifice region shape ('s' shaped regions vs nice blocks). The geo clustering is for easy travel within a region. CA+OR+WA = perfect. OR+NV+AZ = ok. CA+GA+RI = bad. – Jeremy Hageman May 29 '12 at 16:22
Thanks, Jeremy: that's a start. It suggests, for example, that a hierarchical constrained clustering algorithm might be suitable (and certainly efficient). E.g., split the US nearly in half geographically (with a line sweep, for instance), split $n$ into the two halves as evenly as possible, and recursively solve the problem. When you alternate line-sweep directions you tend to get compact regions (as I found years ago in experimenting with this related algorithm). – whuber♦ May 29 '12 at 16:34

3 Answers

up vote 1 down vote

You're really given a planar graph and you want to find connected components that have the smallest "spread" in values. While I don't know how to get an answer with provably guarantees, the following heuristic might work well.

Assume all states have weights between 0 and $2^k$ say (for some $k$). Label all states with weights between 0 and $2^{k-1}-1$ as "0" and the rest as "1". Find the connected components of the graph with the same label. Now recurse in each component.

Essentially what you're doing is finding connected components such that in each component, the values don't vary "too much". If 2 is too coarse a granularity for you, you can choose some other factor between 1 and 2.

The stopping point for the recursion is when the variance within a cluster thus formed is small enough. You'll end up with a hierarchical clustering in which the leaves are the desired clusters.

share|improve this answer
Could you explain why this algorithm might produce an "intuitive" looking solution? It seems to me that after the first one or two steps your graph easily could be split into 50 isolated vertices. Why won't that happen? And how do you handle the (somewhat challenging!) requirement that exactly $n$ clusters be produced? – whuber♦ May 29 '12 at 14:12
1  
The second requirement is easier to manage: as with any hierarchical clustering method, you can keep pushing down the "cut frontier" through the tree to get the desired number of leaves. The first issue is harder to deal with - it might depend on the distribution of values. Given that connected component algorithms are easy to come by, I'd probably just try it first and see what happened. – Suresh Venkatasubramanian May 29 '12 at 15:08
2  
Right. So another way to formulate the problem is in a bicriteria fashion: Fix a parameter R, and an integer k. The goal is to partition a set of weighted points in the plane into k regions such that each region has diameter at most R (the nearness condition) and the variance of weights within each region is minimized. Would this be a reasonable formulation @JeremyHageman – Suresh Venkatasubramanian May 29 '12 at 17:22
1  
I think that's on the right track. It would be more flexible, though, not to use hard constraints but to combine them into a single objective function that expresses the trade-off between (lack of) nearness and equality of clustering. (One might keep the requirement for exactly $n$ clusters as a hard constraint.) BTW, I don't think variance of weights within clusters is of concern: it sounds like the dispersion of the cluster totals should be made low. – whuber♦ May 29 '12 at 17:26
1  
@whuber - I don't think an 'island' would be so bad. I guess it comes down to what is worse, a string or donut shaped cluster? I had also begun to look at the approach of each state knowing their neighboring states (‘1’ for shared border, else ‘0’) as opposed to minimizing the distances from the centers of each state. However this could produce long string shaped clusters. Since compactness lends itself better to travel, I believe horseshoes, donuts, etc. are ok if compactness is somehow maximized. – Jeremy Hageman May 31 '12 at 23:34
show 7 more comments
up vote 0 down vote

This looks like a standard variation of bin packing problem with constraints to me.

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

It does not so much like clustering to me: the distances seems to be solely a constraint that only adjacent states must be selected. So none of the stuff you find under the term of "cluster analysis" will help you much. It's a constraint optimization that you are trying to do.

share|improve this answer
Initially I was hoping this solution would be the one that arose. However, I'm thinking the shapes produced by only taking into account adjacency, as apposed to cluster compactness, would be undesirable. Since travel is the motivation, narrow string-shaped clusters should be avoided. – Jeremy Hageman Jun 5 '12 at 17:43
1  
Then add another constraint. This should be quite efficient to compute using a classic A*-search, too. Plus it depends a lot on what data you have available: adjacency lists, polygons, centroids, ... - how do you intend to measure compactness? – Anony-Mousse Jun 5 '12 at 20:33
Lets assume that adjacency lists and centroid data exists for each state. Compactness could be the regions with the smallest centroid distance sums. Would this essentially be a weighted k-means problem? – Jeremy Hageman Jun 5 '12 at 22:07
No, k-means can't handle additional constraints. Try constraint optimization, not clustering. You need to balance two objectives: finding the best partitioning and keeping the partitions compact. – Anony-Mousse Jun 5 '12 at 22:58
up vote 0 down vote

What about using Graph Partition (http://en.wikipedia.org/wiki/Graph_partition)?

Where the graph here would be the USA, where the nodes are the states, the edges are the connections between states (i.e. there is an edge between two states if they are adjacent to each other). The subgraphs, or partitions would be the territories. You want to divide it into uniform components (equal revenue and maybe other constraints), so you would have some variation of uniform graph partition.

share|improve this answer
Well, that's exactly the question, isn't it? Precisely how should the algorithm be varied? (It isn't comforting that the Wikipedia article characterizes these problems as typically being NP hard!) – whuber♦ May 31 '12 at 13:33
With $n=50$, NP-hard isn't really worse than polynomial. – Anony-Mousse Jun 5 '12 at 20:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.