我希望将美国 50 个州划分为n区域。划分的要求是：
这篇文章提出了类似的问题。K-Means 聚类似乎有点矫枉过正，因为州只需要成为邻居，但我对统计数据很陌生。
作为旁注，我最终希望在 Ruby（它有一个 R 库插件）中实现它。
更新
集群背后的动机是为了方便旅行，因此集群紧凑性比状态邻接更重要（即应避免长、窄、串形的集群）。
您确实得到了一个平面图，并且您想要找到具有最小“分布”值的连接组件。虽然我不知道如何通过可证明的保证得到答案，但以下启发式可能会很好。
假设所有状态的权重都在 0 到之间（对于某些）。将权重在 0 到之间的所有状态标记为“0”，其余的标记为“1”。找到具有相同标签的图形的连通分量。现在在每个组件中递归。
本质上，您所做的是找到连接的组件，以便在每个组件中，值不会“变化太多”。如果 2 对您来说粒度太粗，您可以在 1 和 2 之间选择其他因素。
递归的停止点是当这样形成的簇内的方差足够小时。您最终会得到一个层次聚类，其中叶子是所需的聚类。
这看起来像是装箱问题的标准变体，对我来说是有限制的。
https://en.wikipedia.org/wiki/Bin_packing_problem
对我来说，它不太喜欢聚类：距离似乎只是一个必须选择相邻状态的约束。因此，您在“聚类分析”一词下找到的任何东西都不会对您有太大帮助。这是您正在尝试做的约束优化。
使用 Graph Partition ( http://en.wikipedia.org/wiki/Graph_partition ) 怎么样？
这里的图表是美国，节点是州，边是州之间的连接（即，如果两个州彼此相邻，则在两个州之间存在边）。子图或分区将是领土。您想将其划分为统一的组件（相等的收入和可能的其他约束），因此您将有一些统一的图形分区的变体。