algorithm - 测试聚类算法的最佳方法

Question

测试聚类算法的最佳方法是什么？我正在使用具有停止标准的凝聚聚类算法。如何测试簇是否正确形成？

Answer 1

评估图形可以聚类的程度(在粗粒度级别上)的一个很好的经验法则与“特征值差距”有关。给定一个加权图 A，计算特征值并对它们进行排序(这是特征值谱)。作图时，如果频谱在某一点有较大的跳跃，则自然有一个相应的 block 来划分图形。

下面是一个示例(在 numpy python 中)显示，给定一个几乎 block 对角矩阵，在 block 数(由代码中的 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()