Geospatial clustering algorithm with constraints on maximum distance and total premises

Question

Hi,

I am currently faced with the following challenge:

* My data (attached) contains hexagonal grids within a country (based on Uber's H3 system)
* Each of these hexagons has been allocated a number of premises (i.e., the estimated number of premises within the hexagonal polygon) as well as area and premises density data (calculated using spatial info)
* What I need to be able to do is form contiguous clusters of these hexagons with constraints on the total premises able to be contained within a cluster and the maximum distance of any hexagon's centroid from that of the cluster 'core' which should be the mostpremises-dense hex in a given cluster.

I have written a clustering algorithm which should yield appropriate results however it is extremely computationally expensive and will take days to run. Does anyone have experience with this type of problem as I have struggled to find solutions elsewhere

H3_hex_grid_trimmed_with_premises_count.zip

olly_jones_98 · Answer

This is the output of the current process for a single region and my iterative process

Screenshot 2024-06-28 153331.png

Spatial_clustering_problem_iterative_method.zip

olly_jones_98 · Answer

Hi KGT, 
Thank you for the reply. I will lay it out that I am not a data-scientist also so may not interpret some terminology correctly at times. However, I am fairly certain thsi would be classified as a predictive regionalisation problem.

I do know the ideal number of clusters in this instance, yes, but the quantum across a country is more in the region of 5,000–10,000 clusters (hence the heavy processing)

The challenge I have found with a k-means based (and similairly with other clustering algorithms using Python-based solutions) is that they are challenging to correctly constrain by the total premises. Interesting suggestion around the brute forcing, however I think with the quantum of population count being in the 30-million range, the processing of this quantum of spatial objects would be extremely computationally expensive.

On the final point, one interesting idea I did have was if we used my current iterative approach, but could define the centroid of the hexagon being considered in a given iteration, we could use a lat/long range to filter out any hex's that are outside the boundary but purely numerically and thus slimming down the computational requirement?

olly_jones_98 · Answer

The core of the problem is thus:
What is the most efficient way to cluster together hexagonal polygons (containing a certain population count, i.e., a number) so that the entire grid is split into clusters each of which has a cluster core (designated as the most densely populated hexagon in a cluster) and each cluster needs to be constrained so that no hexagon within a given cluster is more than Xkm (let's say 20km) from the cluster core and constrained so that the maximum number of premises within the cluster is Y (let's say 40,000).

This is the basis for the problem and I have solved this using an iterative macro (will upload as a reply later) however the iterative macro is not able to do the following two things:
1) Run efficiently - each iteration for a single small country like the UK takes over 5 hours even when running on smaller subsets such as individual regions and then combining in post-processes

2) Target a specified number of clusters - I do know broadly the target number of resulting clusters so if there is a methodology to bring this constraint in that would be ideal as it is currently just trial and improvement on the parameters to get to a sensible resulting number of clusters (or crude post-processing)