Matlab：最小距離を見つける手助け

Question

私は候補セットから最小距離にある点を見つけようとしています。 Zは、行が次元であり、列が点を示す行列です。点間距離を計算し、最小距離とその距離でポイントを記録する。以下はコードスニペットです。このコードは、小さな次元と小さな点セットでうまく機能します。しかし、大きなデータセット（N = 100万データポイントおよび次元も高い）には長い時間がかかります。効率的な方法はありますか？

Answer 1

あなたは重い荷を降ろすためにpdistを使用することをお勧めします。この関数は、配列内の2点間のペア間の距離を計算します。得られたベクターは、各ペアの最小値を見つけるために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 

これを2回すべてのペアを計算し、私はこれはあなたの元の実装のための真のだと思います。

pdistは、入力の列間のペアごとの距離を計算するという考え方です。そこで、Zの転置をpdistに入れます。完全な出力は常にゼロ対角の正方行列であるため、pdistは、対角より上の値だけをベクトルに戻すように実装されています。適切な距離行列を得るには、squareformへの呼び出しが必要です。次に、この行列の行ごとの最小値を求める必要がありますが、まず対角線のゼロを除外しなければなりません。私は怠け者でしたので、最小値がどこかにあることを確認するために、infを対角に入れました。結局のところ、最小限の距離を合計するだけです。