最近傍探索

問題の次元によって、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 三角形分割を作成します。

dt = delaunayTriangulation(X);

いくつかのクエリ点を作成し、各クエリ点について、対応する X 内の最近傍のインデックスを nearestNeighbor メソッドを使用して求めます。

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);