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?

  • Why negative vote? – BrunoGL Jul 27 at 7:21
up vote 1 down vote accepted

Use the famous Hungarian algorithm.

It computers the best match permutation.

You can find more details on Wikipedia:

https://en.wikipedia.org/wiki/Hungarian_algorithm

  • This sounds like it might work. Do you know any implementation of this algorithm? Python would be preferred. – BrunoGL Jul 27 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).

  • 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. – Timur Jul 22 at 18:29
  • You mention that it is "time consuming", what is the order of this function? – BrunoGL Jul 27 at 7:24
  • It is linear with respect to the number of rows. – Timur Jul 28 at 8:07
  • Awesome! Is there an implementation of this, or did you just make it up? – BrunoGL Jul 28 at 10:20
  • I've made it up, but it shouldn't be a problem to implement. – Timur Jul 28 at 13:02

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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