Matlab : 최소 거리를 찾는 데 도움이

Question

후보 세트에서 최소 거리에있는 지점을 찾으려고합니다. Z는 행이 차원이고 행이 점을 나타내는 행렬입니다. 포인트 간 거리를 계산 한 다음 최소 거리와 거리로 포인트를 기록하십시오. 아래는 코드 스 니펫입니다. 이 코드는 작은 치수와 작은 점 집합에 대해서는 잘 작동합니다. 그러나 대용량 데이터 세트 (N = 1 백만 데이터 포인트 및 차원 또한 높음)에 대해서는 오랜 시간이 걸립니다. 효율적인 방법이 있습니까?

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에 넣습니다. 전체 출력은 항상 대각선이 0 인 정사각형 행렬이기 때문에 벡터에서 대각선 위의 값만 반환하도록 pdist이 구현됩니다. 적절한 거리 매트릭스를 얻으려면 squareform을 호출해야합니다. 그런 다음이 행렬의 행 단위 최소값을 찾아야하지만 먼저 대각선에서 0을 제외해야합니다. 저는 게으르므로 최소값이 다른 곳에 있는지 확인하기 위해 inf을 대각선으로 넣었습니다. 결국 우리는 최소한의 거리를 합산해야합니다.