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

Question

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

Answer 1

グラフを (粗粒レベルで) どの程度クラスター化できるかを評価するための経験則は、「固有値のギャップ」と関係があります。重み付けされたグラフAを指定して、固有値を計算し、並べ替えます (これが固有値スペクトルです)。プロットすると、ある時点でスペクトルに大きなジャンプがある場合、グラフを分割する自然に対応するブロックがあります。

以下は、ほぼブロックの対角行列が与えられた場合に、ブロックの数で固有値スペクトルに大きなギャップがあることを示す (numpy python の) 例です (cコードでパラメーター化されています)。行列の順列 (グラフ ノードのラベル付けと同じ) でも同じスペクトル ギャップが得られることに注意してください。

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 2

何に対してテストするかによって異なります。

既知のアルゴリズムの独自の実装をテストする場合、結果を既知の適切な実装の結果と比較したい場合があります。

階層的クラスタリングは、階層的であるため、品質に関してテストするのが困難です。ランド インデックスなどの一般的な尺度は、厳密なパーティショニングに対してのみ有効です。階層クラスタリングから厳密なパーティショニングを取得できますが、カットする高さを修正する必要があります。

Answer 3

理想的には、ある種の事前にクラスター化されたデータ（教師あり学習）があり、その上でクラスター化アルゴリズムの結果をテストします。正確なスコアを取得するには、正しい分類の数を実行された分類の総数で割った数を数えるだけです。

教師なし学習を行っている場合、アルゴリズムを評価する方法は実際にはありません。

Answer 4

構築による既知の、おそらく明白な答えがある場合、入力データを構築すると便利な場合があります。クラスタリング アルゴリズムの場合、同じクラスター内の任意の 2 点間の最大距離が、異なるクラスター内の任意の 2 点間の最小距離よりも小さくなるように、N 個のクラスターを使用してデータを構築できます。もう 1 つのオプションは、クラスターが目に見える 2 次元散布図としてプロット可能な多数の異なるデータ セットを生成し、アルゴリズムの結果をこの構造と比較し、おそらくクラスターを一緒に移動して、アルゴリズムが認識できない場合を確認することです。彼ら。

特定のクラスタリング アルゴリズムの知識があれば、より適切に実行できる可能性がありますが、上記の方法では、少なくとも明白なバグをカバーから洗い流す可能性があります。