5

n任意の空間にデータポイントがあり、それらをクラスター化します。私のクラスタリングアルゴリズムの結果は、各ポイントをクラスターに割り当てる長さ
のintベクトルで表されるパーティションです。の範囲の値は0から（おそらく）です。lnln-1

例：

l_1 = [ 1 1 1 0 0 2 6 ]

ポイントを4つのクラスターに分割しn=7ます。最初の3つのポイントは一緒にクラスター化され、4番目と5番目は一緒にクラスター化され、最後の2つのポイントは2つの異なるシングルトンクラスターを形成します。

私の質問：

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 ]

最後の2つのポイントがグループ化されるため、同一ではなくなります。

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で、trueifポイントがkありm、同じクラスター内にあり、falseそれ以外の場合は（クラスターの「番号」/「ラベル」に関係なく）です。
したがって、共起行列c1とc2が同一である場合、l_1とl_2は同一のパーティションを表します。

ただし、ポイントの数はかなり多い可能性があるため、O（ ）ソリューションnは避けたいと思います。n^2

何か案は？

ありがとう！

4

3 に答える 3

3

2つのパーティションはいつ同一ですか？

おそらく、まったく同じメンバーがいる場合です。

したがって、IDをテストするだけの場合は、次の操作を実行できます。

各パーティション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は正規化して

[ 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にあります。

2つのクラスタリングがどの程度類似しているかを測定する場合は、オブジェクトペアの適合率/再現率/ f1を調べることをお勧めします。ここで、ペア（a、b）は、aとbが同じクラスターに属している場合にのみ存在します。

更新：これは2次式であると主張されていたので、さらに明確にします。

標準形を作成するには、次のアプローチ（実際の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 に答える