Chapter 14: Clustering and Regionalization¶
Part II — Geographic Data Science
Learning Objectives¶
By the end of this chapter you will be able to:
- Group observations into types using ordinary K-Means, and explain why the resulting clusters ignore geography entirely
- Build spatially contiguous regions with
spopt, and verify contiguity directly rather than taking it on faith - Explain when each approach is the right tool, instead of defaulting to whichever one is more familiar
From Detecting Patterns to Grouping Observations¶
Chapters 12 and 13 both worked with a single variable at a time: does it cluster in space (Moran's I, LISA), and does a regression on it need to account for that clustering (spatial lag, spatial error)? This chapter shifts the question. Given several variables at once — say, income and population density for every municipality — which observations resemble each other overall, as a type?
That question has two different honest answers, and conflating them is a common mistake. One answer groups by similarity alone, wherever the similar observations happen to sit on the map. The other insists that a group must also be a contiguous block of territory — a legitimate region, not just a shared label scattered across the map. Both are useful; they answer different questions.
# Standard imports
import numpy as np
import pandas as pd
import geopandas as gpd
import matplotlib.pyplot as plt
from shapely.geometry import box
from libpysal.weights import Queen
from sklearn.cluster import KMeans
from spopt.region import RegionKMeansHeuristic
import networkx as nx
np.random.seed(7)
A Synthetic Multivariate Dataset¶
Following the same reasoning as Chapter 13's synthetic grid, this chapter builds two features — income and density — with a known spatial gradient: both increase smoothly across the grid, plus noise. Real geodemographic variables behave this way constantly (income, health outcomes, housing cost all tend to vary smoothly across a city or state), which is exactly what makes the geography-blind-versus-geography-aware distinction below worth taking seriously rather than treating as a technicality.
n_side = 15
cells_geom = [box(j, i, j + 1, i + 1) for i in range(n_side) for j in range(n_side)]
grid = gpd.GeoDataFrame({"geometry": cells_geom})
xs = np.array([c.centroid.x for c in cells_geom])
ys = np.array([c.centroid.y for c in cells_geom])
grid["income"] = 50 + 3 * xs + np.random.normal(0, 5, len(grid))
grid["density"] = 20 + 2 * ys + np.random.normal(0, 4, len(grid))
w = Queen.from_dataframe(grid, use_index=False)
Ordinary K-Means: Clusters Blind to Geography¶
sklearn.cluster.KMeans groups rows by distance in feature space — income and density here — with no idea that grid has a geometry column at all. Four clusters, k=4, is a deliberately round number here; Chapter 13's exercises already covered choosing between competing model specifications from diagnostics, and the same spirit (compare against a criterion, don't just pick a number) applies to choosing k too, left as an exercise below.
km = KMeans(n_clusters=4, n_init=10, random_state=0).fit(grid[["income", "density"]])
grid["kmeans_cluster"] = km.labels_
fig, ax = plt.subplots(figsize=(6, 6))
grid.plot(column="kmeans_cluster", categorical=True, cmap="tab10", ax=ax, legend=True)
ax.set_title("K-Means clusters (feature space only)")
ax.set_axis_off()
The map answers the question K-Means was actually asked — which cells are similar in income and density — and nothing more. Whether those similar cells happen to sit next to each other on the map was never part of the objective, so checking it honestly requires actually checking it, not assuming a clustering algorithm run on spatial data automatically produces spatial regions.
# Convert the weights object into a graph and check, cluster by cluster,
# whether its cells form a single connected block
G = w.to_networkx()
contiguous_count = 0
for c in sorted(grid["kmeans_cluster"].unique()):
idx = np.where(grid["kmeans_cluster"] == c)[0]
is_contiguous = nx.is_connected(G.subgraph(idx))
contiguous_count += int(is_contiguous)
print(f"cluster {c}: n={len(idx)}, contiguous={is_contiguous}")
print(f"\n{contiguous_count} / {grid['kmeans_cluster'].nunique()} K-Means clusters are contiguous")
cluster 0: n=54, contiguous=True cluster 1: n=66, contiguous=False cluster 2: n=52, contiguous=False cluster 3: n=53, contiguous=False 1 / 4 K-Means clusters are contiguous
Only one of the four clusters turns out to be a single connected block — the rest are scattered across two or more separate pieces of the grid, purely because K-Means never had geography as an input in the first place. That is not a bug in K-Means; it is doing exactly what it was asked. It is, however, the wrong tool the moment the actual goal is to draw defensible planning regions, sales territories, or administrative zones.
Regionalization: Clusters That Respect the Map¶
Regionalization adds the constraint K-Means never had: every group must be spatially contiguous. spopt.region.RegionKMeansHeuristic takes the same feature matrix and the same w weights object already built in Chapters 10–13, and searches for clusters under that constraint directly, rather than hoping contiguity shows up by chance.
region_model = RegionKMeansHeuristic(grid[["income", "density"]].values, 4, w)
region_model.solve()
grid["region"] = region_model.labels_
fig, ax = plt.subplots(figsize=(6, 6))
grid.plot(column="region", categorical=True, cmap="tab10", ax=ax, legend=True)
ax.set_title("Regionalization (spatially constrained)")
ax.set_axis_off()
all_contiguous = True
for r in sorted(grid["region"].unique()):
idx = np.where(grid["region"] == r)[0]
is_contiguous = nx.is_connected(G.subgraph(idx))
all_contiguous = all_contiguous and is_contiguous
print(f"region {r}: n={len(idx)}, contiguous={is_contiguous}")
print(f"\nAll regions contiguous: {all_contiguous}")
region 0: n=62, contiguous=True region 1: n=57, contiguous=True region 2: n=54, contiguous=True region 3: n=52, contiguous=True All regions contiguous: True
Four regions, four contiguous blocks — every time, by construction, not by luck. The trade-off is visible in the map itself: a region absorbs some cells that fit its income/density profile only loosely, because keeping the group in one connected piece sometimes means accepting a slightly worse within-group fit than K-Means would allow. That trade-off is the entire point of regionalization — it optimizes similarity subject to contiguity, not similarity alone.
When to Use Which¶
The two methods answer genuinely different questions, and the map above makes the difference visible rather than abstract:
- K-Means — "Which municipalities are similar, regardless of where they are?" Use it for typologies and market segments: municipalities that behave alike for policy or business purposes, even scattered across a state.
- Regionalization — "How do I partition this territory into contiguous zones that are each internally similar?" Use it whenever the output needs to be an actual region someone could draw a boundary around: school districts, sales territories, administrative zones, or — closer to this book's own concerns — spatial units for a simulation model.
A Bridge to DisSModel's Neighborhoods¶
Chapter 10 built Queen and Rook contiguity weights to answer "which cells are neighbors?" for a single cell at a time. Regionalization asks a related but different question at a coarser scale: not a cell's immediate neighbors, but how to partition an entire territory into contiguous, internally coherent blocks. When Chapter 21 introduces create_neighborhood() on a CellularAutomaton, it is solving a simpler version of exactly this problem — deciding which cells belong together for the purposes of a simulation step. The algorithm there is simpler than RegionKMeansHeuristic, but the underlying question — how do you partition space into meaningful, connected units? — is the same one this chapter just answered for static data.
Exercises¶
- Choosing k. Refit K-Means for
kinrange(2, 8)and plotkm.inertia_againstk(the "elbow method"). Does a clear elbow appear, or does inertia decrease smoothly without an obvious bestk? - A LISA-informed feature. Using the LISA machinery from Chapter 12, compute
Moran_Localonincomeand add the local statistic (lisa.Is) as a third column alongsideincomeanddensitybefore re-running both K-Means andRegionKMeansHeuristic. Does adding a spatial-autocorrelation-aware feature change how many K-Means clusters turn out contiguous, even though K-Means still isn't spatially constrained? - Weaker gradient. Rebuild
incomeanddensitywith smaller coefficients (e.g.0.5 * xsand0.3 * ysinstead of3 * xsand2 * ys), keeping the same noise level. Does the contiguity gap between K-Means and regionalization shrink, stay the same, or grow? What does that suggest about when the choice between the two methods matters most? - A different k for regions. Refit
RegionKMeansHeuristicwithn_clusters=6instead of4. Are all six regions still contiguous? Does any region become implausibly small or thin?
Summary¶
Key concepts introduced¶
- The distinction between grouping by similarity alone (K-Means) and grouping by similarity subject to spatial contiguity (regionalization)
sklearn.cluster.KMeanson multivariate geographic data, and why its clusters are not automatically spatially coherent — verified directly vianetworkx, not assumedspopt.region.RegionKMeansHeuristic, which reuses the samelibpysalweights object from Chapters 10–13 to guarantee every group is a single connected block- A practical criterion for choosing between the two: does the output need to be an actual region someone could draw a boundary around?
- Regionalization as a static preview of the spatial-partitioning problem Chapter 21's
create_neighborhood()solves dynamically, inside a running simulation
Chapter 15 turns from statistics back to communication — the mapping and visualization techniques for presenting exactly the kind of pattern the last three chapters learned to detect, model, and now group.
Further Reading¶
- Sergio J. Rey, Dani Arribas-Bel, and Levi J. Wolf, Geographic Data Science with Python (CRC Press) — freely available at https://geographicdata.science/book/; see their chapter on clustering and regionalization for the same K-Means/regionalization distinction applied to real San Diego census tracts
- Duque, J. C., Church, R. L., & Middleton, R. S. (2011). "The p-Regions Problem." Geographical Analysis, 43(1), 104-126 — the regionalization problem this chapter's
RegionKMeansHeuristicis one heuristic solution to - scikit-learn documentation, K-Means: https://scikit-learn.org/stable/modules/clustering.html#k-means
- spopt documentation, Region: https://pysal.org/spopt/notebooks/reg-kmeans-heuristic.html