我遇到了以下问题：
假设我们有一组 n 个样本，我们想将其分类为标记为 1-k 的 k 类。我们运行 M 种不同的聚类算法，得到 M 种不同的输出结果。问题是，在不同的输出结果中，相同的聚类可能会被赋予不同的标签。
如何找到所有输出结果之间的共同聚类？我认为显而易见的解决方案是对所有可能的样本对进行遍历，检查它们在每个输出结果中是否被归类为同一类别。这会带来 O(n^2*M) 的复杂度。
我们能否做得更好（也许可以加入一些假设）？
谢谢。
编辑
下面以一个例子说明。我们有4个样本，k=2，并得到以下输出结果：
A 1 1 2
B 1 1 2
C 2 2 1
D 1 1 1
在所有输出中，唯一常见的聚类是(A,B)，因为它是唯一一个在所有输出中都被分类相同的一对。
据我所知，您需要检查任何两个输出是否实际上具有相似的结构，但您只能想到使用O(n^2)算法来完成。如果您的问题是以上问题，则可以进行以下优化：
伪代码：
int arr1 = [1 1 2 2];
int arr2 = [2 2 1 1];
list sets1[k];
list sets2[k];
for(int i=0;i<n;i++) {
sets1[arr1[i]-1].add(i);
sets2[arr2[i]-1].add(i);
}
boolean flag = true;
for(int i=0;i<k;i++) {
flag = flag && compare(sets1[arr1[i]-1],sets2[arr2[i]-1]);
if(flag == false)
return flag
}
return flag
时间复杂度 :-
比较函数最多只访问arr1和arr2中的所有元素一次，因此总体时间复杂度为O(n)。
编辑 :-
如果你需要评估是否所有类似于小于O(M^2*n)的输出，则：
1. calculate sets for all M
2. Calculate hash for each set using standard hash functions.
3. if two set are equal then their hashes are also equal with high probability
4. Sort k hash for each output in O(logk)
5. Get all equivalent set using hash map in O(M*logM)
总体复杂度：计算集合的时间复杂度为O(n*M)，获取相似输出的时间复杂度为O(M*logM)，因此总时间复杂度为O(M*(n+logM))
Min-Hash 可以用于高效地估计两个聚类之间的相似度。它的时间复杂度与元素数量成线性关系，因此可以将运行时间降至 O(n*k^2*j)（其中 j 是 Min-Hash 使用的哈希函数数量，较高的值会给出更准确的结果）。
分析聚类，而不是数据点，例如通过计算列联表。
这将使您轻松降至O(M*k*k*n)加上O(n log n)，一旦对您的聚类内容进行排序（以实现高效交集），如果您没有预先对它们进行排序。
我认为分析k-means结果并不划算。在相当复杂的数据上，它们只能像随机凸分割一样好。