A partition-free spatial clustering that preserves topology: application to built-up density

Abstract

Urban density is central to urban research and planning and can be defined in numerous ways. Most measures of urban density however are biased by arbitrary chosen spatial units at their denominator and ignore the relative location of elementary urban objects within those units. We solve these two problems by proposing a new graph-based density index which we apply to the case of buildings in Belgium. The method includes two main steps. First, a graph-based spatial descending hierarchical clustering (SDHC) delineates clusters of buildings with homogeneous inter-building distances. A Moran scatterplot and a maximum Cook’s distance are used to prune the minimum spanning tree at each iteration of the SDHC. Second, within each cluster, the ratio of the number of buildings to the sum of inter-building distances is calculated. This density of buildings is thus defined independently of the definition of any basic spatial unit and preserves the built-up topology, i.e. the relative position of buildings. The method is parsimonious in parameters and can easily be transferred to other punctual objects or extended to account for additional attributes.

Appendices

Appendix 1: Chunking of the database

To limit computation time, the database is divided into different chunks spatially adjacent to each other. However, this chunking produces border effects that might bias the results. Indeed, two buildings belonging potentially to the same morphological structure can be separated if they belong to two different chunks. To avoid these border effects, a second chunking process is applied to the same dataset (Fig. 14). The method runs for each chunk separately. The results of the chunks from the chunking 1 are then combined but the subgraphs close (1,000 metres) to the chunks border are replaced by subgraphs from chunking 2 to give the buildings’ density of Belgium (Sect. 4).

Fig. 14

Two chunkings

The final results of the method are not dependent on the initial chunking. Indeed, if each building is assigned the density value of the subgraph to which it belongs, then more than 92% of the buildings have exactly the same density with chunking 1 and chunking 2. If buildings within 1,000 metres of the chunking boundaries are not taken into account (boundary effect), the percentage of identical density between the two chunkings increases even more to 97%.

Appendix 2: Calculation of the spatial lag

The spatial lag is the product of the row standardised matrix of adjacency with the standardised vector of distance between the centroids of the buildings. The adjacency matrix (diagonal equal to zero) is obtained by the product of the incidence matrix with its transpose (Fig. 15).

Fig. 15

Calculation of the spatial lag on a simple spatial toy structure of buildings

Appendix 3: Sensitivity to condition (1)

Condition (1) expresses the fact that if the total length of the graph is higher than 10,000 metres, the outlier is removed. With this condition, we ensure that the method detects fine-scale morphological features. We assume that a graph longer than 10,000 m is too heterogeneous with regard to its inter-building distances. It is therefore necessary to remove the outlier detected in the Moran scatterplot to allow the method to search for more homogeneous topological clusters as it does in condition (3). Note that the 10,000 m threshold was not selected at random: several values were tested (see examples in Figs. 16, 17 and 18). With values larger than 10,000, the algorithm cannot distinguish different topological patterns, especially in the countryside. Conversely, with values lower than 10,000 the algorithm detects small local topological differences that are not relevant in terms of density measure.

Fig. 16

Comparing different thresholds in condition (1) on a given pattern of buildings (a)

Fig. 17

Test of different value to condition (1) on a pattern of buildings

Fig. 18

Test of different value to condition (1) on a pattern of buildings

Appendix 4: The 26,462 clusters for Belgium according to the SDHC

See Fig. 19.

Fig. 19

26,462 clusters following spatial clustering

Appendix 5: The topology-based built density index computed for Belgium

See Fig. 20.

Fig. 20

Topology-based built density index computed for Belgium