최근접이웃 탐색

MATLAB에는 문제의 차원 수에 따른 최근접이웃 계산 방식이 여러 개 있습니다.

• 2차원 탐색과 3차원 탐색의 경우, triangulation 클래스에서 제공하고 delaunayTriangulation 클래스에서 상속하는 nearestNeighbor 메서드를 사용합니다.

• 4차원 이상의 경우, 삼각분할을 생성하는 delaunayn 함수와 탐색을 수행하는 상호 보완적인 dsearchn 함수를 사용합니다. 이러한 N차원 함수는 2차원과 3차원을 지원하지만, 삼각분할 탐색 메서드만큼 보편적이거나 효율적이지는 않습니다.

이 예제에서는 delaunayTriangulation을 사용하여 2차원에서 최근접이웃 탐색을 수행하는 방법을 보여줍니다.

먼저 15개의 임의 점 집합을 만듭니다.

X = [3.5 8.2; 6.8 8.3; 1.3 6.5; 3.5 6.3; 5.8 6.2; 8.3 6.5;...
    1 4; 2.7 4.3; 5 4.5; 7 3.5; 8.7 4.2; 1.5 2.1; 4.1 1.1; ...
    7 1.5; 8.5 2.75];

점을 플로팅하고 주석을 추가하여 ID 레이블을 표시합니다.

plot(X(:,1),X(:,2),'ob')
hold on
vxlabels = arrayfun(@(n) {sprintf("X%d",n)},(1:15)');
Hpl = text(X(:,1) + 0.2,X(:,2) + 0.2,vxlabels, ...
      FontWeight="bold",HorizontalAlignment="center", ...
      BackgroundColor="none");
hold off

이들 점으로 들로네 삼각분할(Delaunay Triangulation)을 만듭니다.

dt = delaunayTriangulation(X);

쿼리 점을 만들고, nearestNeighbor 메서드를 사용하여 각 쿼리 점에 대응하는 X에서의 최근접이웃 인덱스를 구합니다.

numq = 10;
rng(0,"twister");
q = 2 + rand(numq,2)*6;
xi = nearestNeighbor(dt,q);

플롯에 쿼리 점을 추가하고, 각 쿼리 점과 이에 대한 최근접이웃을 잇는 선분을 추가합니다.

xnn = X(xi,:);

hold on
plot(q(:,1),q(:,2),"or");
plot([xnn(:,1) q(:,1)]',[xnn(:,2) q(:,2)]',"-r");

vxlabels = arrayfun(@(n) {sprintf("q%d",n)},(1:numq)');
Hpl = text(q(:,1) + 0.2,q(:,2) + 0.2,vxlabels, ...
      FontWeight="bold",HorizontalAlignment="center", ...
      BackgroundColor="none");

hold off

3차원에서 최근접이웃 탐색을 수행하는 것은 delaunayTriangulation을 기반으로 한 2차원 예제의 직접적인 연장선상에 있습니다.

4차원 이상의 경우, 다음 예제에 표시된 대로 delaunayn 함수와 dsearchn 함수를 사용합니다.

4차원에서 임의의 샘플 점을 만들고 delaunayn을 사용하여 점을 삼각분할합니다.

X = 20*rand(50,4)-10;
tri = delaunayn(X);

쿼리 점을 만들고, 각 쿼리 점에 대해 dsearchn 함수를 사용하여 X에서의 최근접이웃 인덱스를 구합니다.

q = rand(5,4);
xi = dsearchn(X,tri, q);

nearestNeighbor 메서드와 dsearchn 함수를 사용하면 각 쿼리 점과 해당 최근접이웃 점 사이의 유클리드 거리를 선택적 인수로 반환할 수 있습니다. 4차원 예제에서는 다음과 같이 거리 dnn을 계산할 수 있습니다.

[xi,dnn] = dsearchn(X,tri,q);