0
$\begingroup$

I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its cluster.

However, it is not only necessary to match the points to the closest allowed zone, but also to take into consideration the distance to other points of the same cluster.

In the example image given, in the clustered picture, the green points at the top right belong to the green cluster despite being closest to the blue area, because their neighbours are all green.

Ultimately, a network would be created from each cluster (lets say the points are a series of sinks), and linked to each respective zone via a single optimally placed point within the zone (which represents the source). A cost function would evaluate the cost of the network (i.e. minimizing the cost of a weighted graph). The difficulty is that the optimal placement of the source point is not known until the cluster is defined. The overall goal is to minimize the cost of all the networks combined.

Is there any algorithm available that can do this type of clustering? Otherwise how would you proceed?

enter image description here

Improve this question
$\endgroup$
4
  • $\begingroup$ I think you can try running clustering disregarding the zones first. Then placing dummy dots in the zones and running again. This can potentially cause some of the dots to be in different clusters. And for each such dot, you can decide then, if the dummy dots would not be in the map, which other cluster from the first run it would be part of. $\endgroup$
    – zetaprime
    Feb 6, 2020 at 14:32
  • $\begingroup$ This sounds a bit vague: "take into consideration" doesn't say how you want to weight the tradeoff between "nearest zone" vs "cluster of nearest points". $\endgroup$
    – D.W. ♦
    Feb 6, 2020 at 19:05
  • $\begingroup$ Ultimately, a network would created from each cluster (lets say the points are a series of sinks), and linked to each respective zone via a single optimally placed point within the zone (which represents the source). A cost function would evaluate the cost of the network (i.e. minimizing the cost of a weighted graph). The difficulty is that the optimal placement of the source point is not known until the cluster is defined. The overall goal is to minimize the cost of all the networks combined. I hope this helped clarify the problem. $\endgroup$
    – cvcs5
    Feb 6, 2020 at 21:29
  • $\begingroup$ OK. Please edit the question to incorporate that information. We prefer that questions read well for someone who encounters them for the first time (so don't use "edit: ..."), and that people don't need to read the comments to understand the question. Thank you! $\endgroup$
    – D.W. ♦
    Feb 6, 2020 at 23:12

1 Answer 1

Reset to default
1
$\begingroup$

One approach would be to devise a loss function for each point, that says how much you will penalize the cluster assigned to that point, as a function of what clusters are assigned to its neighbors and what the nearest zones are; then let the total loss be the sum off the losses for each point; and then use some optimization algorithm to find the assignment that minimizes the total loss.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.