ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

knnsearch

データを使用して k 最近傍点を検出する

構文

IDX = knnsearch(X,Y)
[IDX,D] = knnsearch(X,Y)
[IDX,D] = knnsearch(X,Y,'Name',Value)

説明

IDX = knnsearch(X,Y) は、Y の各ポイントにおける X の最近傍点を検出します。X は mx 行 n 列の配列で、Y は my 行 n 列の配列です。XY の行は観測に、列は変数に対応します。IDX は、my 行の列ベクトルです。IDX の各行には、Y 内の対応する行について X 内の最近傍点のインデックスが含まれます。

[IDX,D] = knnsearch(X,Y) は、Y 内の各観測と X 内の対応する最も近い観測の間の距離を含む my 行 1 列のベクトル D を返します。つまり、D(i) は、X(IDX(i),:)Y(i,:) の間の距離です。

[IDX,D] = knnsearch(X,Y,'Name',Value) は、コンマで区切られた、1 つ以上のオプションの名前と値のペアを受け入れます。単一引用符で囲んで Name を指定します。

knnsearch は、探索オブジェクトを保存しません。探索オブジェクトを作成するには、createns を使用します。

入力引数

名前/値のペアの引数

'K'

Y の各点について X の最近傍点の数を指定する、正の整数。既定値は 1 です。IDXD は my 行 K 列の行列です。D は各行の距離を昇順に並べ替えます。IDX の各行には、D 内の K 最小距離に対応する X 内の K 最近傍点のインデックスが含まれます。

'IncludeTies'

関数 knnsearch に、距離値が K 番目に短い距離に等しいすべての近傍点が含まれるかどうかを示す論理値です。IncludeTiestrue の場合、knnsearch はすべての近傍点を含みます。このケースでは、IDXD は my 行 1 列のセル配列です。IDX および D の各行には、少なくとも K 個の数字をもつベクトルが含まれます。D は、各ベクトルの距離を昇順に並べ替えます。IDX の各行には、D の最短距離に対する最近傍点のインデックスが含まれます。

既定値: false

'NSMethod'

最近傍点検索メソッド。値は以下のいずれかになります。

  • 'kdtree'Kd ツリーを作成して最近傍点の検出に使用します。X の列数が 10 列より少なく、X がスパースでなく、距離測定が次に示した計量のいずれかである場合、これが既定値となります。'kdtree' は、距離測定が以下のいずれかである場合のみ有効です。

    • 'euclidean'

    • 'cityblock'

    • 'minkowski'

    • 'chebychev'

  • 'exhaustive'X 内のすべての点から Y 内の各点への距離値を計算する網羅的探索アルゴリズムを使用して、最近傍点を検出します。

'Distance'

距離計量を指定する文字列または関数ハンドル。値は、以下のいずれかです。

  • 'euclidean' — ユークリッド距離 (既定の設定)。

  • 'seuclidean' — 標準化されたユークリッド距離。X の行とクエリ行列間の各座標差は、S=nanstd(X)X から算出された標準偏差の対応する要素で割ってスケールされます。S に別の値を指定するには、Scale 引数を使用します。

  • 'cityblock' — 市街地距離。

  • 'chebychev' — チェビシェフ距離 (最大座標差)。

  • 'minkowski' — ミンコフスキー距離。既定の設定の指数は 2 です。異なる指数を指定するには、'P' 引数を使用します。

  • 'mahalanobis' — 正定共分散行列 C を使用して計算されたマハラノビス距離。C の既定値は nancov(X) です。C の値を変更するには、Cov パラメーターを使用します。

  • 'cosine' — 1 から、ベクトルとして扱われる観測間の夾角の余弦を引きます。

  • 'correlation' — 1 から、一連の値として扱われる観測間の標本線形相関係数を引きます。

  • 'spearman' — 1 から、一連の値として扱われる観測間の標本スピアマン順位相関係数を引きます。

  • 'hamming' — ハミング距離。異なる座標の割合です。

  • 'jaccard' — 1 からジャカード係数 (異なる非ゼロ座標の割合) を引きます。

  • カスタム距離関数 — @ を使用して指定された距離関数 (@distfun など)。距離関数は、形式が function D2 = distfun(ZI, ZJ) であり、X または Y の 1 行を含む 1 行 n 列のベクトル ZI、または X または Y の複数行を含む m2 行 n 列の行列 ZJ を引数として取り、距離 D2 の m2 行 1 列ベクトルを返さなければなりません。ここで、j 番目の要素は観測 ZIZJ(j,:) の間の距離です。

これらの距離計量の詳細は、「距離計量」を参照してください。

'P'

ミンコフスキー距離の指数を示す正のスカラー p。このパラメーターは、Distance'minkowski' の場合にのみ有効です。既定値は 2 です。

'Cov'

マハラノビス距離を計算する際に共分散行列を示す正定行列。このパラメーターは、Distance'mahalanobis' の場合にのみ有効です。既定値は nancov(X) です。

'Scale'

非負値を含み、X 内の列数と同じ長さをもつベクトル SX の各座標と各クエリ点は、標準化されたユークリッド距離を計算する際に S の対応する要素によってスケーリングされます。この引数は、Distance'seuclidean' の場合にのみ有効です。既定値は nanstd(X) です。

'BucketSize'

kd ツリーの葉ノード内のデータ点の最大数。この引数は、kd ツリー検索メソッドを使用している場合のみ有意です。既定値は 50 です。

すべて展開する

k 近傍法による分類

p 値が 5'minkowski' 距離計量を最初に使用し、次に 'chebychev' 距離計量を使用して y の各点について x で 10 個の最近傍点を検出します。

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

load fisheriris
x = meas(:,3:4);
y = [5 1.45;6 2;2.75 .75];

xy のクエリ点との間で、最初にミンコフスキー距離計量、次にチェビシェフ距離軽量を使用して、knnsearch を実行します。

[n,d]=knnsearch(x,y,'k',10,'distance','minkowski','p',5);
[ncb,dcb] = knnsearch(x,y,'k',10,...
   'distance','chebychev');

2 つの最近傍検索の結果を表示します。学習データをプロットします。クエリ点に対して X をプロットします。円を使用してミンコフスキー最近傍を表します。星形五角形を使用してチェビシェフ最近傍を表します。

gscatter(x(:,1),x(:,2),species)
line(y(:,1),y(:,2),'marker','x','color','k',...
   'markersize',10,'linewidth',2,'linestyle','none')
line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o',...
   'linestyle','none','markersize',10)
line(x(ncb,1),x(ncb,2),'color',[.5 .5 .5],'marker','p',...
   'linestyle','none','markersize',10)
legend('setosa','versicolor','virginica','query point',...
'minkowski','chebychev')
set(legend,'location','best')

詳細

すべて展開する

ヒント

  • 固定の正の整数 K の場合、knnsearchY の各点に最も近い XK 点を検索します。これに対して、正の実数値 r の場合、rangesearchY 内の各点の距離 r 内にある X 内のすべての点を検索します。

アルゴリズム

特定の検索アルゴリズムの詳細は、「距離計量」を参照してください。

参考文献

[1] Friedman, J. H., Bentely, J., and Finkel, R. A. (1977) An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software 3, 209.

この情報は役に立ちましたか?