Matlab：幫助尋找最小距離

Question

我試圖找到距離候選集最小距離的點。 Z是矩陣，行是維度，列表示點。計算點間距離，然後用最小距離和距離記錄點。以下是代碼片段。該代碼適用於小維度和小組點。但是，對於大型數據集（N = 100萬個數據點，維數也很高），需要很長時間。有沒有一種有效的方法？

Answer 1

我建議你用pdist來爲你做重擔。該函數將計算陣列中每兩個點之間的成對距離。所產生的載體，必須投入才能使用squareform找到每一對極小值矩陣形式：

N = 100; 
Z = rand(2,N); % each column is a 2-dimensional point 

% pdist assumes that the second index corresponds to dimensions 
% so we need to transpose inside pdist() 
distmatrix = squareform(pdist(Z.','euclidean')); % output is [N, N] in size 
% set diagonal values to infinity to avoid getting 0 self-distance as minimum 
distmatrix = distmatrix + diag(inf(1,size(distmatrix,1))); 
mindists = min(distmatrix,[],2); % find the minimum for each row 
sum_dist = sum(mindists); % sum of minimal distance between each pair of points 

此計算每對兩次，但我認爲這是對你的最初實現真實的。

想法是pdist計算其輸入列之間的成對距離。所以我們把Z的轉置放入pdist。由於全部輸出總是一個零對角線的方形矩陣，所以實現了pdist，使得它只在向量中返回高於對角線的值。因此需要致電squareform以獲得適當的距離矩陣。然後，這個矩陣的行最小值必須找到，但首先我們必須排除對角線中的零。我很懶，所以我把inf插入對角線，以確保最小值在別處。最後，我們只需要總結最小的距離。