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

Question

我n在某个任意空间中有数据点,我将它们聚类.
我的聚类算法的结果是由l长度为int的向量表示的分区,n每个点都指向一个簇.的值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的大小为nx n,true如果是点k,m则在同一簇中,false否则(无论簇"数"/"标号"如何).
因此,如果共生矩阵c1和c2相同,则l_1与l_2代表相同的分区.

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

有任何想法吗？

谢谢!

Answer 1

什么时候两个分区相同？

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

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

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

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

在上面的示例中，假设向量索引 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