5

我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，trueif 点位于同一簇中，k否则（无论簇“编号”/“标签”如何）。 因此，如果共现矩阵和相同，则和表示相同的分区。mfalse
c1c2l_1l_2

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

有任何想法吗？

谢谢！

4

3 回答 3

3

两个分区何时相同？

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

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

用分区中最小的对象 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
于 2013-03-20T12:55:42.290 回答
1

如果您要重新标记分区，如前所述，您可能需要为 n 个项目中的每一个搜索 n 个标签。即解决方案是O(n^2)。

这是我的想法：同时扫描两个列表，为每个列表中的每个分区标签维护一个计数器。您需要能够将分区标签映射到计数器编号。如果每个列表的计数器不匹配，则分区不匹配。这将是 O(n)。

这是 Python 中的概念证明：

l_1 = [ 1, 1, 1, 0, 0, 2, 6 ]

l_2 = [ 2, 2, 2, 9, 9, 3, 1 ]

l_3 = [ 2, 2, 2, 9, 9, 3, 3 ]

d1 = dict()
d2 = dict()
c1 = []
c2 = []

# assume lists same length

match = True
for i in range(len(l_1)):
    if l_1[i] not in d1:
        x1 = len(c1)
        d1[l_1[i]] = x1
        c1.append(1)
    else:
        x1 = d1[l_1[i]]
        c1[x1] += 1

    if l_2[i] not in d2:
        x2 = len(c2)
        d2[l_2[i]] = x2
        c2.append(1)
    else:
        x2 = d2[l_2[i]]
        c2[x2] += 1

    if x1 != x2 or  c1[x1] != c2[x2]:
        match = False

print "match = {}".format(match)
于 2013-03-20T13:46:15.330 回答
0

在matlab中：

function tf = isIdenticalClust( l_1, l_2 )
%
% checks if partitions l_1 and l_2 are identical or not
%
tf = all( accumarray( {l_1} , l_2 , [],@(x) all( x == x(1) ) ) == 1 ) &&...
     all( accumarray( {l_2} , l_1 , [],@(x) all( x == x(1) ) ) == 1 );

这是做什么的：根据分区对
所有元素进行分组，并检查每个集群中的所有元素是否都相同。根据重复相同的分区。 如果两个分组都产生同质集群 - 它们是相同的。l_1l_2l_1l_2l_1

于 2013-03-20T13:29:12.780 回答