Efficient regionalization techniques for socio-economic geographical units using minimum spanning trees
Efficient regionalization techniques for socio-economic geographical units using minimum spanning trees
复制标题
DOI：
10.1080/13658810600665111
复制
发表时间：
2006-08-01
影响因子：
5.7
通讯作者：
Da Costa Freitas, C.
中科院分区：
文献类型：
--
作者：
Assuncao, R. M.;Neves, M. C.;Da Costa Freitas, C.
区域化是一种应用于具有面表示的空间对象的分类过程，其将空间对象分组为均匀的连续区域。本文提出了一种有效的区域化方法。第一步创建一个连接图，捕捉空间对象之间的邻域关系。图中每条边的成本与它所连接的区域之间的相似性成反比。我们总结的邻域结构的最小生成树（MST），这是一个连接的树没有电路。我们分区的MST连续删除连接不同区域的边缘。其结果是将空间对象划分为具有最大内部均匀性的连通区域。由于MST划分问题是NP-难的，我们提出了一个启发式，以加快树划分显着。我们的研究结果表明，我们提出的方法结合了性能和质量，它是一个很好的替代文献中发现的其他区域化方法。
Regionalization is a classification procedure applied to spatial objects with an areal representation, which groups them into homogeneous contiguous regions. This paper presents an efficient method for regionalization. The first step creates a connectivity graph that captures the neighbourhood relationship between the spatial objects. The cost of each edge in the graph is inversely proportional to the similarity between the regions it joins. We summarize the neighbourhood structure by a minimum spanning tree (MST), which is a connected tree with no circuits. We partition the MST by successive removal of edges that link dissimilar regions. The result is the division of the spatial objects into connected regions that have maximum internal homogeneity. Since the MST partitioning problem is NP-hard, we propose a heuristic to speed up the tree partitioning significantly. Our results show that our proposed method combines performance and quality, and it is a good alternative to other regionalization methods found in the literature.