Suppose I run an unsupervised clustering algorithm. After multiple runs, I find clusters and would like to know if the same cluster was found more than once.

For example:

enter image description here

I can figure out A-orange, B-green and C-blue are probably the same because their centroids are close together.

However, take the following example:

enter image description here

How can I programmatically figure out that A-blue and C-orange are the same? That A-orange and C-blue are the same? But B-orange and B-blue are not similar to any in A and C?

  • $\begingroup$ Why negative vote? $\endgroup$ Jul 27, 2018 at 7:21

2 Answers 2


Use the famous Hungarian algorithm.

It computers the best match permutation.

You can find more details on Wikipedia:


  • $\begingroup$ This sounds like it might work. Do you know any implementation of this algorithm? Python would be preferred. $\endgroup$ Jul 27, 2018 at 7:23

This method is pretty much time consuming, but you may reduce the database useing sklearn train test split to get, say, 10% extract.

AB = A blue AO = A orange BB = B blue etc.

Spoiler: in the end you will get several classes, they are the different clusters.

The idea is as follows.

  1. Put all clusters into one class: C1 = [AB, AO, BB, BO, CB, CO]

  2. Start iterating through your data, get the next element X.

  3. Check if X in each element of class behaves the same way - either in or out.

  4. Split the classes that behave different. For example, if you check a point in the upper left corner, [AB, BO, CO] will say YES, whereas [AO, BB, CB] will say no. So we have two classes C1 = [AB, BO, CO] and C2 = [AO, BB, CB]

  5. Continue (go to step 3) until either each cluster is in a separate class or there is no more data.

So at some point, BO and BB will be in separate classes, but AB and CO will always behave the same way.

Here I am inspired by the algorithm that minimizes a DFA (Deterministic Finite Automaton).

  • $\begingroup$ Also, you do not expect the exact match between clusters, you may iterate not by single X, but by portions of data, and check if, say, 90% of data have common behavior for each element of each class. Like a Batch in neural networks. $\endgroup$
    – Timur
    Jul 22, 2018 at 18:29
  • $\begingroup$ You mention that it is "time consuming", what is the order of this function? $\endgroup$ Jul 27, 2018 at 7:24
  • $\begingroup$ It is linear with respect to the number of rows. $\endgroup$
    – Timur
    Jul 28, 2018 at 8:07
  • $\begingroup$ Awesome! Is there an implementation of this, or did you just make it up? $\endgroup$ Jul 28, 2018 at 10:20
  • $\begingroup$ I've made it up, but it shouldn't be a problem to implement. $\endgroup$
    – Timur
    Jul 28, 2018 at 13:02

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.