knnsearch

knnsearch は、ExhaustiveSearcher または KDTreeSearcher モデル オブジェクトを受け入れて、クエリ データに対する最近傍を学習データから探索します。ExhaustiveSearcher モデルは、網羅的探索アルゴリズムを呼び出します。KDTreeSearcher モデルは、knnsearch で最近傍の探索に使用される Kd 木を定義します。

フィッシャーのアヤメのデータセットを読み込みます。クエリ データ用に 5 つの観測値をデータから無作為に抽出します。

load fisheriris
rng(1); % For reproducibility
n = size(meas,1);
idx = randsample(n,5);
X = meas(~ismember(1:n,idx),:); % Training data
Y = meas(idx,:);                % Query data

変数 meas には 4 つの予測子が含まれています。

既定の 4 次元 Kd 木を成長させます。

MdlKDT = KDTreeSearcher(X)

MdlKDT = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'euclidean'
    DistParameter: []
                X: [145x4 double]

MdlKDT は KDTreeSearcher モデル オブジェクトです。書き込み可能なプロパティは、ドット表記を使用して変更できます。

網羅的最近傍探索モデルを準備します。

MdlES = ExhaustiveSearcher(X)

MdlES = 
  ExhaustiveSearcher with properties:

         Distance: 'euclidean'
    DistParameter: []
                X: [145x4 double]

MdlKDT は ExhaustiveSearcher モデル オブジェクトです。このオブジェクトには、最近傍の探索に使用する距離計量などのオプションが格納されています。

Kd 木の成長と網羅的最近傍探索モデルの準備には、createns も使用できます。

各クエリ観測値に対応する最近傍のインデックスを学習データから探索します。既定の設定を使用して、両方のタイプの探索を実行します。既定の設定では、各クエリ観測値について探索する近傍の数は 1 です。

IdxKDT = knnsearch(MdlKDT,Y);
IdxES = knnsearch(MdlES,Y);
[IdxKDT IdxES]

ans = 5×2

    17    17
     6     6
     1     1
    89    89
   124   124

この場合、探索の結果は同じです。

関数 createns を使用して、Kd 木最近傍探索モデル オブジェクトを成長させます。k 最近傍を探索するため、オブジェクトとクエリ データを関数 knnsearch に渡します。

フィッシャーのアヤメのデータセットを読み込みます。

load fisheriris

クエリ セットとして使用するため、5 つのアヤメのデータを無作為に予測子データから抽出します。

rng(1)                      % For reproducibility
n = size(meas,1);           % Sample size
qIdx = randsample(n,5);     % Indices of query data
tIdx = ~ismember(1:n,qIdx); % Indices of training data
Q = meas(qIdx,:);
X = meas(tIdx,:);

学習データを使用して 4 次元の Kd 木を成長させます。最近傍の探索にミンコフスキー距離を指定します。

Mdl = createns(X,'Distance','minkowski')

Mdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 2
                X: [145x4 double]

X には 4 つの列があり、距離計量がミンコフスキーであるため、既定では createns は KDTreeSearcher モデル オブジェクトを作成します。既定では、ミンコフスキー距離の指数は 2 です。

求める学習データ (Mdl.X) のインデックスは、クエリ データ (Q) の各点における 2 つの最近傍です。

IdxNN = knnsearch(Mdl,Q,'K',2)

IdxNN = 5×2

    17     4
     6     2
     1    12
    89    66
   124   100

IdxNN の各行はクエリ データの観測値に、列の順序は距離の昇順で並べ替えた最近傍の順序に対応しています。たとえば、ミンコフスキー距離に基づくと、Q(3,:) の 2 番目の最近傍は X(12,:) になります。

フィッシャーのアヤメのデータセットを読み込みます。

load fisheriris

クエリ セットとして使用するため、5 つのアヤメのデータを無作為に予測子データから抽出します。

rng(4);                     % For reproducibility
n = size(meas,1);           % Sample size
qIdx = randsample(n,5);     % Indices of query data
X = meas(~ismember(1:n,qIdx),:);
Y = meas(qIdx,:);

学習データを使用して 4 次元の Kd 木を成長させます。最近傍の探索にミンコフスキー距離を指定します。

Mdl = KDTreeSearcher(X);

Mdl は KDTreeSearcher モデル オブジェクトです。既定の設定では、最近傍を探索するための距離計量はユークリッド尺度です。

求める学習データ (X) のインデックスは、クエリ データ (Y) の各点における 7 つの最近傍です。

[Idx,D] = knnsearch(Mdl,Y,'K',7,'IncludeTies',true);

Idx と D は、5 つのベクトルが含まれている cell 配列です。各ベクトルには少なくとも 7 つの要素が含まれています。

Idx に含まれているベクトルの長さを表示します。

cellfun('length',Idx)

ans = 5×1

     8
     7
     7
     7
     7

セル 1 には長さが k = 7 より大きいベクトルが含まれているので、クエリ観測値 1 (Y(1,:)) は X 内の観測値の少なくとも 2 つと同じ距離にあります。

Y(1,:) に対する最近傍のインデックスとその距離を表示します。

nn5 = Idx{1}

nn5 = 1×8

    91    98    67    69    71    93    88    95

nn5d = D{1}

nn5d = 1×8

    0.1414    0.2646    0.2828    0.3000    0.3464    0.3742    0.3873    0.3873

学習観測値 88 および 95 は、クエリ観測値 1 から 0.3873 cm 離れています。

異なる距離計量を使用して 2 つの KDTreeSearcher モデルに学習をさせ、この 2 つのモデルでクエリ データの k 最近傍を比較します。

フィッシャーのアヤメのデータセットを読み込みます。花弁の測定値を予測子と考えます。

load fisheriris
X = meas(:,3:4); % Predictors
Y = species;     % Response

予測子を使用して KDTreeSearcher モデル オブジェクトに学習をさせます。指数が 5 のミンコフスキー距離を指定します。

KDTreeMdl = KDTreeSearcher(X,'Distance','minkowski','P',5)

KDTreeMdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 5
                X: [150x2 double]

最初にミンコフスキー距離計量を、次にチェビシェフ距離計量を使用して、クエリ点 (newpoint) に対する 10 個の最近傍を X から探索します。クエリ点は、モデルの学習に使用したデータと列次元が同じでなければなりません。

newpoint = [5 1.45];
[IdxMk,DMk] = knnsearch(KDTreeMdl,newpoint,'k',10);
[IdxCb,DCb] = knnsearch(KDTreeMdl,newpoint,'k',10,'Distance','chebychev');

IdxMk と IdxCb はそれぞれ、ミンコフスキー距離計量とチェビシェフ距離計量を使用した newpoint に対する最近傍に対応する X の行インデックスが格納されている 1 行 10 列の行列です。要素 (1,1) は最も近い要素、要素 (1,2) は次に近い要素です。以後についても同様です。

学習データ、クエリ点および最近傍をプロットします。

figure;
gscatter(X(:,1),X(:,2),Y);
title('Fisher''s Iris Data -- Nearest Neighbors');
xlabel('Petal length (cm)');
ylabel('Petal width (cm)');
hold on
plot(newpoint(1),newpoint(2),'kx','MarkerSize',10,'LineWidth',2);   % Query point 
plot(X(IdxMk,1),X(IdxMk,2),'o','Color',[.5 .5 .5],'MarkerSize',10); % Minkowski nearest neighbors
plot(X(IdxCb,1),X(IdxCb,2),'p','Color',[.5 .5 .5],'MarkerSize',10); % Chebychev nearest neighbors
legend('setosa','versicolor','virginica','query point',...
   'minkowski','chebychev','Location','Best');

目的の点を拡大します。

h = gca; % Get current axis handle.
h.XLim = [4.5 5.5];
h.YLim = [1 2];
axis square;

いくつかの観測値は等しいので、プロットで識別できる最近傍は 8 つだけです。