Hierarchical Clustering with Contiguity Constraint in R
Dublin Core
Title
Hierarchical Clustering with Contiguity Constraint in R
Subject
R, hclust, constrained clustering, space, chronological clustering, Lance and Williams
algorithm
algorithm
Description
This article presents a new implementation of hierarchical clustering for the R language
that allows one to apply spatial or temporal contiguity constraints during the clustering
process. The need for contiguity constraint arises, for instance, when one wants to partition a map into different domains of similar physical conditions, identify discontinuities in
time series, group regional administrative units with respect to their performance, and so
on. To increase computation efficiency, we programmed the core functions in plain C. The
result is a new R function, constr.hclust, which is distributed in package adespatial.
The program implements the general agglomerative hierarchical clustering algorithm
described by Lance and Williams (1966; 1967), with the particularity of allowing only
clusters that are contiguous in geographic space or along time to fuse at any given step.
Contiguity can be defined with respect to space or time. Information about spatial contiguity is provided by a connection network among sites, with edges describing the links
between connected sites. Clustering with a temporal contiguity constraint is also known
as chronological clustering. Information on temporal contiguity can be implicitly provided
as the rank positions of observations in the time series. The implementation was mirrored
on that found in the hierarchical clustering function hclust of the standard R package
stats (R Core Team 2022). We transcribed that function from Fortran to C and added the
functionality to apply constraints when running the function.
The implementation is efficient. It is limited mainly by input/output access as massive
amounts of memory are potentially needed to store copies of the dissimilarity matrix and
update its elements when analyzing large problems. We provided R computer code for
plotting results for numbers of clusters.
that allows one to apply spatial or temporal contiguity constraints during the clustering
process. The need for contiguity constraint arises, for instance, when one wants to partition a map into different domains of similar physical conditions, identify discontinuities in
time series, group regional administrative units with respect to their performance, and so
on. To increase computation efficiency, we programmed the core functions in plain C. The
result is a new R function, constr.hclust, which is distributed in package adespatial.
The program implements the general agglomerative hierarchical clustering algorithm
described by Lance and Williams (1966; 1967), with the particularity of allowing only
clusters that are contiguous in geographic space or along time to fuse at any given step.
Contiguity can be defined with respect to space or time. Information about spatial contiguity is provided by a connection network among sites, with edges describing the links
between connected sites. Clustering with a temporal contiguity constraint is also known
as chronological clustering. Information on temporal contiguity can be implicitly provided
as the rank positions of observations in the time series. The implementation was mirrored
on that found in the hierarchical clustering function hclust of the standard R package
stats (R Core Team 2022). We transcribed that function from Fortran to C and added the
functionality to apply constraints when running the function.
The implementation is efficient. It is limited mainly by input/output access as massive
amounts of memory are potentially needed to store copies of the dissimilarity matrix and
update its elements when analyzing large problems. We provided R computer code for
plotting results for numbers of clusters.
Creator
Guillaume Guénard
Source
https://www.jstatsoft.org/article/view/v103i07
Publisher
Université de Montréal
Date
July 2022
Contributor
Fajar bagus W
Format
PDF
Language
English
Type
Text
Files
Collection
Citation
Guillaume Guénard, “Hierarchical Clustering with Contiguity Constraint in R,” Repository Horizon University Indonesia, accessed April 4, 2025, https://repository.horizon.ac.id/items/show/8263.