# How to identify clusters after multiple runs?

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: 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: 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? – Bruno Lubascher Jul 27 '18 at 7:21

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