c++ - 如何确定数据点的两个分区(聚类)是否相同？

Question

我在某个任意空间中有 n 个数据点，并将它们聚类。
我的聚类算法的结果是一个由长度为 n 的 int vector l 表示的分区，将每个点分配给一个聚类。 l 的值范围从 0 到(可能)n-1。

例子:

l_1 = [ 1 1 1 0 0 2 6 ]

将 n=7 点划分为 4 个簇:前三个点聚集在一起，第四个和第五个点聚集在一起，最后两个点形成两个不同的单例簇。

我的问题:

假设我有两个分区 l_1 和 l_2 我怎样才能有效地确定它们是否代表相同的分区？

例子:

l_2 = [ 2 2 2 9 9 3 1 ]

与 l_1 相同，因为它表示点的相同分区(尽管集群的“数字”/“标签”不相同)。
另一方面

l_3 = [ 2 2 2 9 9 3 3 ]

不再相同，因为它将最后两点组合在一起。

我正在寻找 C++、python 或 Matlab 中的解决方案。

不需要的方向

一种天真的方法是比较共现矩阵

c1 = bsxfun( @eq, l_1, l_1' );
c2 = bsxfun( @eq, l_2, l_2' );
l_1_l_2_are_identical = all( c1(:)==c2(:) );

共现矩阵 c1 的大小为 nxn 且 true 如果点 k 和 m 在同一簇中，否则为 false(无论簇“number”/“label”如何)。
因此，如果共现矩阵 c1 和 c2 相同，则 l_1 和 l_2 表示相同的分区。

但是，由于点数 n 可能非常大，我想避免 O(n^2) 的解决方案...

有什么想法吗？

谢谢!

Answer 1

什么时候两个分区相同？

可能如果他们有完全相同的成员。

因此，如果您只是想测试身份，您可以执行以下操作:

用分区中的最小对象 ID 替换每个分区 ID。

那么两个分区是相同的当且仅当这个表示是相同的。

在上面的示例中，假设 vector 索引 1 .. 7 是您的对象 ID。然后我会得到规范形式

[ 1 1 1 4 4 6 7 ]
  ^ first occurrence at pos 1 of 1 in l_1 / 2 in l_2
        ^ first occurrence at pos 4

对于 l_1 和 l_2，而 l_3 规范化为

[ 1 1 1 4 4 6 6 ]

为了更清楚，这里是另一个例子:

l_4 = [ A B 0 D 0 B A ]

规范化为

      [ 1 2 3 4 3 2 1 ]

因为簇“A”第一次出现在位置 1，“B”在位置 2 等。

如果您想衡量两个聚类的相似程度，一个好的方法是查看对象对的精度/召回率/f1，其中当且仅当 (a,b) 对存在如果 a 和 b 属于同一个簇。

更新:既然有人声称这是二次的，我会进一步澄清。

要生成规范形式，请使用以下方法(实际 python 代码):

def canonical_form(li):
  """ Note, this implementation overwrites li """
  first = dict()
  for i in range(len(li)):
    v = first.get(li[i])
    if v is None:
      first[li[i]] = i
      v = i
    li[i] = v
  return li

print canonical_form([ 1, 1, 1, 0, 0, 2, 6 ])
# [0, 0, 0, 3, 3, 5, 6]
print canonical_form([ 2, 2, 2, 9, 9, 3, 1 ])
# [0, 0, 0, 3, 3, 5, 6]
print canonical_form([ 2, 2, 2, 9, 9, 3, 3 ])
# [0, 0, 0, 3, 3, 5, 5]
print canonical_form(['A','B',0,'D',0,'B','A'])
# [0, 1, 2, 3, 2, 1, 0]
print canonical_form([1,1,1,0,0,2,6]) == canonical_form([2,2,2,9,9,3,1])
# True
print canonical_form([1,1,1,0,0,2,6]) == canonical_form([2,2,2,9,9,3,3])
# False