Main Content

このページの翻訳は最新ではありません。ここをクリックして、英語の最新版を参照してください。

knnsearch

探索モデル オブジェクトを使用して k 最近傍を探索

ページ内をすべて折りたたむ

構文

Idx = knnsearch(Mdl,Y)
Idx = knnsearch(Mdl,Y,Name,Value)
[Idx,D] = knnsearch(___)

説明

例

Idx = knnsearch(Mdl,Y) は、網羅的探索または Kd 木を使用して、クエリ データ Y の各点 (行または観測値) に対する最近傍 (最も近い点、行または観測値) を Mdl.X から探索します。knnsearch は Idx を返します。これは、最近傍を表す Mdl.X 内のインデックスから構成される列ベクトルです。

例

Idx = knnsearch(Mdl,Y,Name,Value) は、1 つ以上の Name,Value ペア引数で指定された追加オプションを使用して、Y に対して最も近い Mdl.X 内の点のインデックスを返します。たとえば、探索する最近傍の数や、Mdl.Distance に格納されているものとは異なる距離計量を指定します。また、最も近い距離が同順位の場合に行う処理を指定することもできます。

例

[Idx,D] = knnsearch(___) は、前の構文の入力引数のいずれかを使用して、さらに行列 D を返します。D には、Mdl.X 内の最も近い観測値に対応する Y 内の各観測値間の距離が格納されます。既定では、D の列は、距離計量による近さの昇順で並べ替えられます。

例

すべて折りたたむ

ライブ スクリプトを開く

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

Figure contains an axes object. The axes object with title Fisher's Iris Data -- Nearest Neighbors contains 6 objects of type line. These objects represent setosa, versicolor, virginica, query point, minkowski, chebychev.

目的の点を拡大します。

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

Figure contains an axes object. The axes object with title Fisher's Iris Data -- Nearest Neighbors contains 6 objects of type line. These objects represent setosa, versicolor, virginica, query point, minkowski, chebychev.

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

入力引数

すべて折りたたむ

最近傍探索モデル。ExhaustiveSearcher または KDTreeSearcher モデル オブジェクトを指定します。

Mdl が ExhaustiveSearcher モデルの場合、knnsearch は網羅的探索を使用して最近傍を探索します。それ以外の場合、knnsearch は成長した Kd 木を使用して最近傍を探索します。

クエリ データ。数値行列を指定します。

Y は、m 行 K 列の行列です。Y の各行は観測値 (事例) に、各列は予測子 (変数または特徴量) に対応します。Y の列数は、Mdl.X に格納されている学習データの列数と同じでなければなりません。

データ型: single | double

名前と値の引数

オプションの引数のペアを Name1=Value1,...,NameN=ValueN として指定します。ここで Name は引数名、Value は対応する値です。名前と値の引数は他の引数の後ろにする必要がありますが、ペアの順序は関係ありません。

R2021a より前では、名前と値をそれぞれコンマを使って区切り、Name を引用符で囲みます。

例: 'K',2,'Distance','minkowski' は、Y の各点に対する 2 つの最近傍を Mdl.X から探索することと、ミンコフスキー距離計量を使用することを指定します。

両方の最近傍探索モデル

すべて折りたたむ

クエリ観測値に対する学習データの近傍を求めるために使用する距離計量。'Distance' と文字ベクトル、string スカラー、または関数ハンドルから構成されるコンマ区切りのペアとして指定します。

両方のタイプの最近傍探索モデルについて、knnsearch は次の距離計量をサポートします。

値説明
'chebychev'チェビシェフ距離 (最大座標差)。
'cityblock'市街地距離。
'euclidean'ユークリッド距離。
'minkowski'ミンコフスキー距離。既定の指数は 2 です。別の指数を指定するには、'P' 名前と値のペアの引数を使用します。

Mdl が ExhaustiveSearcher モデル オブジェクトである場合、knnsearch は次の距離計量もサポートします。

値説明
'correlation'1 から、一連の値として扱われる観測間の標本線形相関係数を引きます。
'cosine'(行ベクトルとして扱われる) 観測値間の夾角の余弦を 1 から減算します。
'hamming'異なる座標の比率を示すハミング距離。
'jaccard'1 から、ジャカード係数 (異なる非ゼロ座標の比率) を引いた値。
'mahalanobis'正定値共分散行列を使用して計算されるマハラノビス距離。共分散行列の値を変更するには、名前と値のペアの引数 'Cov' を使用します。
'seuclidean'標準化されたユークリッド距離。Mdl.X の行とクエリ行列の行の間の各座標差は、Mdl.X から計算される、対応する標準偏差の要素で除算することによりスケーリングされます。他のスケーリングを指定するには、名前と値のペアの引数 'Scale' を使用します。
'spearman'1 から、観測値間の標本スピアマンの順位相関 (値の系列として扱われる) を引いた値。

Mdl が ExhaustiveSearcher モデル オブジェクトである場合、@ を使用してカスタム距離計量の関数ハンドル (たとえば @distfun) を指定することもできます。カスタム距離関数は、次のようになっていなければなりません。

  • function D2 = distfun(ZI,ZJ) という形式になっている。

  • 次の引数を受け入れる。

    • Mdl.X または Y の 1 行が含まれている 1 行 K 列のベクトル ZI。K は Mdl.X の列数です。

    • Mdl.X または Y の複数行が含まれている m 行 K 列の行列 ZJ。m は正の整数です。

  • m 行 1 列の距離のベクトル D2 を返す。D2(j) は、観測値 ZI と ZJ(j,:) の間の距離です。

詳細は、距離計量を参照してください。

例: 'Distance','minkowski'

クエリ観測値から同じ距離にある複数の最近傍を含めるかどうかのフラグ。'IncludeTies' と false (0) または true (1) をコンマ区切りのペアとして指定します。

IncludeTies が true の場合、次のようになります。

  • knnsearch は、k 番目に小さい距離に等しい距離をもつすべての最近傍を出力引数に含めます。k は、名前と値のペアの引数 'K' で指定された探索済み最近傍の個数です。

  • Idx と D は m 行 1 列の cell 配列になり、それぞれ少なくとも k 個のインデックスと距離のベクトルがセルごとに格納されます。D の各ベクトルには、距離が昇順で並べ替えられて格納されます。Idx の各行には、D 内の距離に対応する最近傍のインデックスが格納されます。

IncludeTies が false の場合、knnsearch はクエリ点から同じ距離にある観測値の中でインデックスが最も小さいものを選択します。

例: 'IncludeTies',true

各クエリ観測値について学習データで探索する最近傍の数。'K' と正の整数をコンマ区切りのペアとして指定します。

例: 'K',2

データ型: single | double

ミンコフスキー距離計量の指数。'P' と正のスカラー値をコンマで区切って指定します。この引数は、'Distance' が 'minkowski' である場合のみ有効です。

例: 'P',3

データ型: single | double

Kd 木最近傍探索モデル用

すべて折りたたむ

返されたインデックスを距離に従って並べ替えるためのフラグ。'SortIndices' と true (1) または false (0) から構成されるコンマ区切りのペアとして指定します。

以下の場合は、SortIndices を false に設定して速度を向上させることができます。

  • X 内に多数の最近傍がある多数の観測値が Y に含まれている。

  • Mdl は KDTreeSearcher モデル オブジェクトです。

  • IncludeTies が false。

この場合、knnsearch が返す最近傍のインデックスに特定の順序はありません。SortIndices が true である場合、最近傍のインデックスは距離の昇順で並べ替えられます。

既定では、SortIndices は true です。Mdl が ExhaustiveSearcher モデル オブジェクトであるか、IncludeTies が true である場合、常にインデックスが並べ替えられます。

例: 'SortIndices',false

データ型: logical

網羅的最近傍探索モデルの場合

すべて折りたたむ

マハラノビス距離計量の共分散行列。'Cov' と正定値行列をコンマ区切りのペアとして指定します。Cov は K 行 K 列の行列で、K は Mdl.X の列数です。Cov を指定して 'Distance','mahalanobis' を指定しなかった場合、knnsearch はエラー メッセージを返します。

例: 'Cov',eye(3)

データ型: single | double

標準化されたユークリッド距離計量のスケール パラメーター値。'Scale' と非負の数値ベクトルから構成されるコンマ区切りのペアとして指定します。Scale の長さは K です。K は Mdl.X の列数です。

学習データとクエリ データの間の距離は、対応する Scale の要素を使用してスケーリングされます。Scale を指定して 'Distance','seuclidean' を指定しなかった場合、knnsearch はエラー メッセージを返します。

例: 'Scale',quantile(Mdl.X,0.75) - quantile(Mdl.X,0.25)

データ型: single | double

メモ

'Distance'、'Cov'、'P' または 'Scale' を指定した場合、Mdl.Distance と Mdl.DistParameter の値は変更されません。

出力引数

すべて折りたたむ

最近傍の学習データのインデックス。数値行列または数値ベクトルの cell 配列として返されます。

  • IncludeTies (既定は false) を指定しなかった場合、Idx は m 行 k 列の数値行列になります。m は Y の行数、k は名前と値のペアの引数 'K' で指定された探索対象の最近傍の個数です。Idx(j,i) は、Mdl.X(Idx(j,i),:) がクエリ観測値 Y(j,:) に対して最も近い Mdl.X 内の k 個の観測値の 1 つであることを示します。

  • 'IncludeTies',true を指定した場合、Idx は m 行 1 列の cell 配列になり、クエリ観測値 Y(j,:) に最も近い Mdl.X 内の観測値のインデックスが少なくとも k 個含まれているベクトルがセル j (Idx{j}) に格納されます。

SortIndices が true である場合、knnsearch はインデックスを距離の昇順で並べ替えます。

クエリ データに対する最近傍の距離。数値行列または数値ベクトルの cell 配列として返されます。

  • IncludeTies (既定は false) を指定しなかった場合、D は m 行 k 列の数値行列になります。m は Y の行数、k は名前と値のペアの引数 'K' で指定された探索対象の最近傍の個数です。D(j,i) は、距離計量による Mdl.X(Idx(j,i),:) とクエリ観測値 Y(j,:) の間の距離です。

  • 'IncludeTies',true を指定した場合、D は m 行 1 列の cell 配列になり、クエリ観測値 Y(j,:) に最も近い Mdl.X 内の観測値の距離が少なくとも k 個含まれているベクトルがセル j (D{j}) に格納されます。

SortIndices が true である場合、knnsearch は距離を昇順で並べ替えます。

ヒント

knnsearch は、Y の各点についての k 最近傍である k (正の整数) 個の点を Mdl.X 内で探索します。これに対して rangesearch は、Y の各点に対する距離が r (正のスカラー) 以内であるすべての点を Mdl.X 内で探索します。

代替機能

  • knnsearch は、ExhaustiveSearcher または KDTreeSearcher モデル オブジェクトとクエリ データを必要とするオブジェクト関数です。同じ条件の場合、それぞれ名前と値のペアの引数 'NSMethod','exhaustive' または 'NSMethod','kdtree' を指定すると、オブジェクト関数 knnsearch は関数 knnsearch と同じ結果を返します。

  • k 最近傍分類については、fitcknn と ClassificationKNN を参照してください。

参照

[1] Friedman, J. H., Bentley, J., and Finkel, R. A. (1977). “An Algorithm for Finding Best Matches in Logarithmic Expected Time.” ACM Transactions on Mathematical Software Vol. 3, Issue 3, Sept. 1977, pp. 209–226.

拡張機能

バージョン履歴

R2010a で導入

参考

| | | | | |

トピック