Source-linked AI summary
ClustGeo: an R package for hierarchical clustering with spatial constraints
Marie Chavent, Vanessa Kuentz-Simonet, Amaury Labenne, Jérôme Saracco
TL;DR
The paper addresses how to incorporate spatial or other constraints into hierarchical clustering without relying on strict contiguity. It introduces a Ward-like method combining feature-space and constraint-space dissimilarities, then illustrates α selection on 303 French municipalities with ClustGeo.
Problem
Strict contiguity can separate highly similar objects, while weighting geographical dissimilarities raises the problem of choosing that weight objectively.
Method
The method combines two dissimilarity matrices with α ∈ [0,1] and minimizes a convex combination of their homogeneity criteria during hierarchical clustering.
Results
A choice of α = 0.2 corresponds to a 7% loss of socio-economic homogeneity and a 17% increase in geographical homogeneity.
Takeaways & Limitations
ClustGeo implements the Ward-like method and supports mapping clusters formed under spatial constraints, including contexts beyond geographical units.
Takeaways & Limitations
The criterion Qβ cannot select the number of clusters because it decreases with K and equals 1 for n clusters and 0 for one cluster.
Abstract
from arXiv · showhide
In this paper, we propose a Ward-like hierarchical clustering algorithm including spatial/geographical constraints. Two dissimilarity matrices $D_0$ and $D_1$ are inputted, along with a mixing parameter $α\in [0,1]$. The dissimilarities can be non-Euclidean and the weights of the observations can be non-uniform. The first matrix gives the dissimilarities in the "feature space" and the second matrix gives the dissimilarities in the "constraint space". The criterion minimized at each stage is a convex combination of the homogeneity criterion calculated with $D_0$ and the homogeneity criterion calculated with $D_1$. The idea is then to determine a value of $α$ which increases the spatial contiguity without deteriorating too much the quality of the solution based on the variables of interest i.e. those of the feature space. This procedure is illustrated on a real dataset using the R package ClustGeo.
1 Introduction
The paper motivates soft spatially constrained hierarchical clustering as a way to balance similarity in feature variables with spatial or other contiguity requirements. It proposes combining two dissimilarity spaces through a tunable parameter rather than imposing strict contiguity.
- Motivation: Clustering may require constraints that restrict allowable solutions beyond similarity-based homogeneity.Contiguity constraints require clustered objects to form connected sets, and arise in spatial, temporal, image, social-science, and genetic applications.
- Contiguity constraints: A contiguity matrix records whether object pairs are linked, while a contiguous cluster requires a path between every pair of its objects.Strict hierarchical procedures can merge only contiguous clusters, but common definitions of cluster contiguity may produce reversals in the dendrogram.
- Soft constraints: Strict contiguity can separate highly similar objects when they are spatially distant.Soft spatial constraints instead modify dissimilarities so the resulting clusters can be more or less spatially contiguous according to the geographical weighting.
- Contribution: The proposed Ward-like hierarchical method combines feature-space and constraint-space dissimilarities using D0, D1, and α ∈ [0,1].At each stage it minimizes a convex combination of the two homogeneity criteria; increasing α decreases D0 homogeneity and increases D1 homogeneity.
- Illustration: The method is illustrated with 303 French municipalities described by four socio-economic variables and analyzed using socio-economic and geographical distances.The paper uses the ClustGeo package and maps the resulting clusters for visualization and reproducibility.
2 Ward-like hierarchical clustering with dissimilarities and non-uniform weights
The paper generalizes Ward-style hierarchical clustering to arbitrary dissimilarities and non-uniform observation weights through pseudo-inertia and aggregation measures. The resulting procedure is implemented in ClustGeo and hclust-compatible workflows.
- Generalized criterion: For non-Euclidean dissimilarities, ordinary variance-based inertia is not meaningful, so the method optimizes a pseudo within-cluster inertia criterion.The framework supports dissimilarity data, including non-numerical observations, while retaining a Ward-like hierarchical interpretation.
- Generalized criterion: The pseudo-inertia of a cluster decreases as the observations within it become more homogeneous.The partition pseudo within-inertia likewise measures homogeneity across the K clusters.
- Hierarchical process: The merge increase δ(A, B) equals the change in within-cluster inertia and becomes the dendrogram height for the merged cluster.Lance–Williams updates calculate aggregation measures between the new cluster and every remaining cluster.
- Hierarchical process: At each step, the algorithm merges the pair of clusters that produces the smallest increase in pseudo within-cluster inertia.Starting from n singleton clusters, it recursively obtains partitions with fewer clusters until one cluster remains.
- Implementation: The implementation accepts dissimilarities and observation weights through hclustgeo, including non-uniform weights.For the 303-municipality dataset, the package provides the estuary data and supports uniform or population-based weighting.
- Implementation: When using hclust with uniform weights, the required aggregation input is a transformed matrix rather than the raw dissimilarity matrix.The sum of dendrogram heights can be checked against the dataset’s total pseudo-inertia.
3 Ward-like hierarchical clustering with two dissimilarity matrices
The paper develops a Ward-like hierarchical clustering procedure that combines feature-space and constraint-space dissimilarities through a mixing parameter. It builds nested partitions by minimizing mixed within-cluster inertia, then selects α for a fixed K by trading off feature homogeneity against geographic cohesion.
- Inputs and mixed criterion: Two dissimilarity matrices represent feature-space and constraint-space relationships, with non-uniform observation weights and potentially non-Euclidean dissimilarities.D0 can describe socio-economic variables, while D1 can describe geographical distances.
- Inputs and mixed criterion: The mixing parameter α weights the constraint contribution in the clustering procedure and controls the quality trade-off between the two dissimilarity spaces.α = 0 uses D0 alone, whereas α = 1 uses D1 alone.
- Ward-like hierarchical process: At each agglomerative step, the algorithm merges the pair of clusters that produces the smallest increase in mixed within-cluster inertia.The procedure starts with n singleton clusters and successively obtains partitions with fewer clusters until one cluster remains.
- Ward-like hierarchical process: The proposed procedure differs from applying Ward clustering directly to Dα because α explicitly controls the separate pseudo-inertia contributions of D0 and D1.Direct Ward clustering on the convex combination uses a single pseudo-inertia and therefore does not provide the same decomposition of contributions.
- Choosing α: For a fixed number K of clusters, α is selected from a grid by balancing reduced feature-space homogeneity against increased geographic cohesion.The two homogeneity criteria are plotted across candidate α values so the user can choose a suitable compromise.
- Choosing α: When local neighborhood dissimilarities make the total constraint-space pseudo-inertia very small, the corresponding criterion can be much smaller than the feature-space criterion, complicating α selection.This scale imbalance is identified as a practical limitation for few-cluster solutions.
4 An illustration of hierarchical clustering with geographical constraints using the package ClustGeo
The ClustGeo case study applies hierarchical clustering to 303 French municipalities using socio-economic and geographical dissimilarities. Choosing α = 0.2 improves spatial cohesion while preserving most socio-economic homogeneity, with related neighborhood constraints producing even more compact clusters at a small criterion cost.
- 4.1 The data: The reproducible dataset contains 303 French municipalities described by four socio-economic variables, with D0 measuring socio-economic distances and D1 geographical distances.The variables are employment rate, graduate rate, apartment-housing ratio, and agricultural land.
- 4.2 Choice of the number K of clusters: Ward clustering using D0 alone retains K = 5 clusters after visual inspection of the dendrogram.The resulting partition is called P5.
- 4.2 Choice of the number K of clusters: The D0-only partition has geographically uneven clusters: cluster 5 is compact around Bordeaux and Arcachon, whereas cluster 3 is scattered across the study area.Cluster interpretations also reflect distinct socio-economic profiles, including urban, suburban, forest, and estuary municipalities.
- 4.3 Obtaining a partition taking into account the geographical constraints: α = 0.2 is selected for geographical distances, corresponding to a 7% loss of socio-economic homogeneity and a 17% increase in geographical homogeneity.The choice balances the competing D0- and D1-based explained pseudo-inertias for five clusters.
- 4.3 Obtaining a partition taking into account the geographical constraints: With geographical distances and α = 0.2, P5bis gains spatial homogeneity while retaining recognizable socio-economic interpretations; several clusters become spatially compact.Cluster 5 adds Blaye, clusters 1 and 2 become more spatially homogeneous, and cluster 3 is concentrated predominantly in the Médoc.
- 4.4 Obtaining a partition taking into account the neighborhood constraints: For neighborhood constraints, normalized explained inertias suggest α = 0.2 or 0.3, and α = 0.2 is retained because the application prioritizes socio-economic homogeneity.The resulting P5ter is more spatially compact than P5bis, permits non-neighboring municipalities in one cluster, and has Q0 quality of 72.69% versus 75.58% for P5bis.
5 Concluding remarks
The paper introduces a Ward-like hierarchical clustering method with soft spatial constraints and implements it in the R package ClustGeo. The approach can also incorporate a second dissimilarity matrix to refine an existing clustering without fundamentally disrupting it.
- The Ward-like hierarchical algorithm includes soft spatial constraints and is implemented in the R package ClustGeo.For geographical observations, resulting clusters can be represented on a map according to the selected spatial constraints.
- The method also applies beyond geographical units by interpreting D1 as dissimilarities in a broader constraint space.The paper notes that D1 need not represent spatial constraints when observations are not geographical units.
- A second dataset can refine an initial clustering through its dissimilarity matrix without basically disrupting the original solution.The example contrasts an initial dataset of p0 variables with new variables measured on the same n individuals.