I have some 3d point cloud I wish to cluster into some number of clusters.
I have the probability of two points being in the same cluster given as some function of their relative locations, with the probability being 1 for the same location, and 0 for infinite distance.
I would like some algorithm to cluster the cloud into distinct subsets of points, such that
- The probability of each pair of points in a cluster being together does not exceed some threshold.
- Some points have a constraint of not being together, no matter their distance.
- Discard clusters of less than 3 points.
I figured I could represent the problem as a weighted, full, graph, with the vertices being the points, and the weights being the probabilities of points being adjacent, and try to find distinct, max multiplicative-weight (as in not sum) cliques.
It is also possible to make the graph quite sparse by zeroing-out low weights.
- Does this direction make sense for ~1000-~10000 points with ~20 clusters of ~10 points, with the rest being noise?
- If so, how can this be done efficiently? Maybe it is NP-hard?