QGIS cluster points based on similar sum // maximum treshold of an attribute of each cluster

I need to cluster point layer features based on an attribute so each cluster has a similar total sum of this attribute values:

E.g. I have generated 1000 random points with values between 1-100. Task: Cluster these points so each cluster has a sum of values similar to 1000.

In QGIS I have tries several clustering processing tools (K-means, DBSCAN, ST-DBSCAN) and plugins ( Attribute based clustering; ClusterPoints; QGIS Scipy Clustering - no compatible with QGIS 3) but none of these tools/plugins enables the option to cluster the features based on similar sum of an attribute. I suppose PyQGIS is needed for this but I am missing an idea of the workflow to implement this task.

Another (similar) task will be how to cluster these point geometries so the sum of an attribute (numeric) is maximally 1000 (no overrun). Because of the similar approach (question character) I did not create a new question for this task.

Any suggestions/ideas how to calculate this?

• Can the clusters overlap?
– Matt
Apr 12, 2023 at 12:46
• @Matt No. Based on the clusterID assignment polygons for further calculations will be generated. The areas cannot overlap therefore. Apr 12, 2023 at 12:50
• @BERA I think I get your point - clustering based on exactly identical sum values will not be possible (question modified). So yes, I want to get as close as possible. Apr 12, 2023 at 13:37
• Sounds to me like an intractable problem. Are you giving a number of clusters to start with? Apr 12, 2023 at 15:21
• There's a fair bit of information that you haven't specified in the question. For example, how well clustered do the points need to be, or is the sum the only thing that matters? And you've said "similar to 1000", but that could mean anything. If you do K-means clustering using the K ~= sum(values)/1000, probability suggests that you'll get a good number of clusters with values close to 1000. Not a bad starting point. But what's the furthest that's acceptable? You're trying to do an optimisation which doesn't neatly converge. So you need to set parameters. Apr 21, 2023 at 8:32