測試聚類算法的最佳方法

Question

測試聚類算法的最佳方法是什麼？我正在使用具有停止標準的凝聚聚類算法。我如何測試集羣是否正確形成？

Answer 1

這取決於你想測試什麼。

當您測試自己的已知算法實現時，您可能想要將結果與已知良好實現的結果進行比較。

分層聚類很難在質量方面進行測試，因爲它是分層的。蘭德指數等常用指標只適用於嚴格劃分。您可以從層次聚類中獲得嚴格的分區，但是您需要修復要切割的高度。

Answer 2

理想情況下，你有一些預先羣集的數據（supervised learning）並測試你的聚類算法的結果。只需計算正確分類的數量除以執行的分類總數即可獲得準確性分數。

如果你在做unsupervised learning，那麼真的沒有辦法評估你的算法。

Answer 3

評估一個圖形可以聚集多少（在粗粒度級別上）的好的經驗法則與「特徵值間隙」有關。給定加權圖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 4

它有時是有益的構造的輸入數據，其中有一個已知的，並且也許明顯，回答建設。對於聚類算法，您可以使用N個聚類構建數據，使得同一個聚類中任意兩個點之間的最大距離小於不同聚類中任意兩個點之間的最小距離。另一種選擇是生成許多不同的數據集，作爲具有顯而易見的羣集的二維散點圖，然後將算法的結果與此結構進行比較，可能將羣集移動到一起以查看算法何時無法看到他們。

根據您的特定聚類算法的知識，您可能會做得更好，但以上可能至少有一些機會可以從掩護中清除明顯的錯誤。