我n在任意空间中都有数据点，并且将它们聚类。 我的聚类算法的结果是一个由l长度为int的矢量表示的分区，该矢量n将每个点分配给一个聚类。的值l的范围从0到（可能）n-1。
n
l
n-1
例：
l_1 = [ 1 1 1 0 0 2 6 ]
将n=7点划分为4个簇：前三个点聚在一起，第四个和第五个聚在一起，最后两个点形成两个不同的单例簇。
n=7
假设我有两个分区l_1，l_2如何 有效地 确定它们是否代表相同的分区？
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，m并且在同一群集中，false否则在同一群集中（与群集“数字” /“标签”无关）。 因此，如果共生矩阵c1和c2是再相同l_1并l_2代表相同的分区。
c1
true
k
m
false
c2
但是，由于点的数量n可能很大，因此我想避免使用O（n^2）解…
n^2
有任何想法吗？
谢谢！
什么时候两个分区相同？
如果他们具有完全相同的成员，可能。
因此，如果您只想测试身份，则可以执行以下操作：
用分区中 最小的 对象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等。
如果要测量两个聚类的 相似 程度，一种好的方法是查看对象对的precision / recall / 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
