I am looking for an algorithm to cluster elements of which I already know pairs that are not in the same cluster.

Take the following matrix. The values in the cells represent a score of closeness (the higher the closer). A negative value indicates that the elements cannot be in the same cluster.

-  a  b  c  d  e
a  -  4 -1  2  6
b  -  -  3  5 -1
c  -  -  - -1  4
d  -  -  -  -  7

A possible clustering of these elements is as follows. {a, d, e}, {b, c}.

Notice that the pairs (a, c), (b, e), and (c, d) are separated in the clustering.

Are there any algorithms that consider this kind of prior knowledge about the target clusters?


1 Answer 1


There are semi-supervised clustering algorithms known as "constraint clustering.

There are often two kinds of constraints considered:

  • must-link constraints: objects that are known to belong to the same cluster
  • cannot-link constraints: objects that are known to be different clusters

Your Answer

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

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