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

  1. The probability of each pair of points in a cluster being together does not exceed some threshold.
  2. Some points have a constraint of not being together, no matter their distance.
  3. 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.

  1. Does this direction make sense for ~1000-~10000 points with ~20 clusters of ~10 points, with the rest being noise?
  2. If so, how can this be done efficiently? Maybe it is NP-hard?
  • $\begingroup$ Do you know how many clusters you have (exactly, not approximately)? $\endgroup$
    – nir shahar
    Commented Dec 6, 2021 at 17:15
  • $\begingroup$ I don't understand what is meant by "The probability of each pair of points in a cluster being together does not exceed some threshold.". Can you rephrase? Can you state that in mathematics? What is the experiment, and what is the probability taken over (what are the random choices)? If this is a universally quantified ("for all") statement, what is quantified over? Do you really mean "does not exceed" rather than "is not below"? $\endgroup$
    – D.W.
    Commented Dec 6, 2021 at 22:41
  • $\begingroup$ What does "Discard clusters of less than 3 points"? Is the final clustering allowed to contain clusters of fewer than 3 points or not? Must the final clustering cover all points, or can you have some point that is not a part of any cluster? $\endgroup$
    – D.W.
    Commented Dec 6, 2021 at 22:42
  • $\begingroup$ What exactly desired output? Do you want to know whether any clustering exists that meets your three requirements? Do you additionally want to optimize some objective function? Your proposed approach makes it sound like you are trying to maximize some objective function, but you haven't stated anything about that in the problem description, so I suspect something is missing. What do cliques have to do with anything? Please state the problem more carefully and completely. $\endgroup$
    – D.W.
    Commented Dec 6, 2021 at 22:43
  • $\begingroup$ @nirshahar I don't have any information on the number of clusters prior to computation. $\endgroup$
    – Gulzar
    Commented Dec 7, 2021 at 9:22


Your Answer

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