I've came across the following problem:

Imagine we have a set of `n`

samples that we want to classify into `k`

classes labeled `1-k`

. We run `M`

different clustering algorithms and get `M`

different outputs. The catch is that the same clusters in different outputs can be given a different label in each output.

How to find the common clusters between all outputs? The obious solution I think is to run over all possible pairs of samples, checking whether they are classified the same in each ouput. That gives complexity of `O(n^2*M)`

.

Can we do better (maybe if we add some assumptions)?

Thanks.

**EDIT**

I'll give an example. We have 4 samples, k=2 and got the following outputs:

```
A 1 1 2
B 1 1 2
C 2 2 1
D 1 1 1
```

Than the only common cluster is (A,B) since it s the only pair that is classified the same in all outputs.

## comments: