クラスタリングアルゴリズムをテストする最良の方法

Question

クラスタリングアルゴリズムをテストする最良の方法は何ですか？私は停止基準を持つ凝集クラスタリングアルゴリズムを使用しています。クラスターが正しく形成されているかどうかをテストするにはどうすればよいですか？

Answer 1

これは、に依存しています。あなたがテストしたいものはです。

既知のアルゴリズムの独自の実装をテストするときは、結果を既知の優れた実装のものと比較するとよいでしょう。

階層的クラスタリングは、階層的であるため、品質に関してテストするのが難しいです。ランド指標などの一般的な数値は、厳密な区分にのみ有効です。階層的なクラスタリングから厳密なパーティショニングを得ることができますが、次にカットする高さを固定する必要があります。

Answer 2

事前にクラスタ化されたデータ（supervised learning）があり、そのクラスタリングアルゴリズムの結果をテストするのが理想的です。正確な分類の数を実行された分類の総数で割った数を数えて、正確な得点を得るだけです。

unsupervised learningを実行している場合、実際にアルゴリズムを評価する方法はありません。

Answer 3

グラフをどれくらいクラスター化できるか（粗粒度レベルで評価する）の良い経験則は、「固有値ギャップ」と関係がある。重み付けされたグラフAが与えられると、固有値を計算し、それらをソートする（これは固有値スペクトルである）。プロットすると、ある点でスペクトルに大きなジャンプがある場合、グラフを分割する自然な対応するブロックがあります。

以下は、ほぼブロック対角行列で与えられたブロック数の固有値スペクトル（コード内でcによってパラメータ化されている）に大きなギャップがある場合の例（numpy python）です。 、

from numpy import * 
import pylab as plt 

# Make a block diagonal matrix 
N = 30 
c = 5 
A = zeros((N*c,N*c)) 
for m in xrange(c): 
    A[m*N:(m+1)*N, m*N:(m+1)*N] = random.random((N,N)) 

# Add some noise 
A += random.random(A.shape) * 0.1 

# Make symmetric 
A += A.T - diag(A.diagonal()) 

# Show the original matrix 
plt.subplot(131) 
plt.imshow(A.copy(), interpolation='nearest') 

# Permute the matrix for effect 
idx = random.permutation(N*c) 
A = A[idx,:][:,idx] 

# Compute eigenvalues 
L = linalg.eigvalsh(A) 

# Show the results 
plt.subplot(132) 
plt.imshow(A, interpolation='nearest') 
plt.subplot(133) 
plt.plot(sorted(L,reverse=True)) 

plt.plot([c-.5,c-.5],[0,max(L)],'r--') 

plt.ylim(0,max(L)) 
plt.xlim(0,20) 
plt.show() 

​​

Answer 4

知られており、おそらく明らかがある場合、入力データを構築することが、時には有用である：（あなたのグラフノードを標識と同一）マトリックス順列は依然として同じスペクトルギャップを与えることに注意してください建設による回答。クラスタリングアルゴリズムでは、同じクラスター内の任意の2点間の最大距離が、異なるクラスター内の任意の2点間の最小距離よりも小さくなるように、Nクラスターでデータを構築することができます。もう1つの選択肢は、目に見えやすいクラスタを持つ2次元散布図としてプロット可能な多数の異なるデータセットを生成し、アルゴリズムの結果をこの構造と比較し、おそらくクラスタをまとめて移動させて、それら。

特定のクラスタリングアルゴリズムに関する知識があれば、よりうまくいくかもしれませんが、上記の方法では、明らかに明らかなバグを隠す可能性があります。