我n在一些任意的空间数据点，我集群他们。
我的聚类算法的结果是由一个int矢量表示的分区l长度的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是大小为n X n与true如果点k和m是相同的簇和在false否则（不考虑簇“数字”的/“标签”）。
因此，如果共生矩阵c1和c2相同，则l_1和l_2代表相同的分区。
然而，由于点的数量， n ，可能是相当大的，我想避免O（ n^2 ）解决方案...
有任何想法吗？
谢谢！
当两个分区相同？
也许，如果他们有相同的成员。
所以，如果你只是想测试的身份，你可以做到以下几点：
代替用在分区的最小对象ID的每个分区ID。
然后2个分区成为是当且仅当该表示是相同的，相同。
另外，在上述的例子中，让我们假设向量索引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 canonicalizes到
[ 1 1 1 4 4 6 6 ]
为了使它更清楚，这里是另一个例子：
l_4 = [ A B 0 D 0 B A ]
canonicalizes到
[ 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
如果你要重新标记您的分区，如前面所说，你将有可能需要到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)
在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_1根据分区l_2 ，并检查是否所有元件l_1在每个簇都相同。 重复相同的用于隔开l_2根据l_1 。
如果两个分组产生均质簇 - 它们是相同的。
文章来源: How to determine if two partitions (clusterings) of data points are identical?
