Main Content

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

knnsearch

入力データを使用して k 最近傍を探索

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

構文

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

説明

例

Idx = knnsearch(X,Y) は、Y 内の各クエリ点に対する最近傍を X 内で探索し、列ベクトル Idx にインデックスを返します。Idx の行数は Y と同じです。

Idx = knnsearch(X,Y,Name,Value) は、1 つ以上の名前と値のペアの引数で指定された追加オプションを使用して Idx を返します。たとえば、探索する最近傍の個数や、探索で使用する距離計量を指定できます。

例

[Idx,D] = knnsearch(___) は、前の構文の入力引数のいずれかを使用して、行列 D も返します。D には、Y 内の各観測値と X 内の対応する最も近い観測値の間の距離が格納されます。

例

すべて折りたたむ

ライブ スクリプトを開く

年齢と体重に従って、Y 内の患者に最も似ている患者を hospital データセット内で探索します。

hospital データセットを読み込みます。

load hospital;
X = [hospital.Age hospital.Weight];
Y = [20 162; 30 169; 40 168; 50 170; 60 171];   % New patients

X と Y の間で knnsearch を実行して、最近傍のインデックスを求めます。

Idx = knnsearch(X,Y);

Y 内の患者に年齢と体重が最も近い患者を X 内で探索します。

X(Idx,:)
ans = 5×2

    25   171
    25   171
    39   164
    49   170
    50   172
ライブ スクリプトを開く

最初にミンコフスキー距離計量を、次にチェビシェフ距離計量を使用して、Y 内の各点に対する 10 個の最近傍を X 内で探索します。

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

load fisheriris
X = meas(:,3:4);    % Measurements of original flowers
Y = [5 1.45;6 2;2.75 .75];  % New flower data

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

[mIdx,mD] = knnsearch(X,Y,'K',10,'Distance','minkowski','P',5);
[cIdx,cD] = 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(mIdx,1),X(mIdx,2),'Color',[.5 .5 .5],'Marker','o',...
   'Linestyle','none','Markersize',10)
line(X(cIdx,1),X(cIdx,2),'Color',[.5 .5 .5],'Marker','p',...
   'Linestyle','none','Markersize',10)
legend('setosa','versicolor','virginica','query point',...
'minkowski','chebychev','Location','best')

Figure contains an axes object. The axes object contains 6 objects of type line. These objects represent setosa, versicolor, virginica, query point, minkowski, chebychev.

入力引数

すべて折りたたむ

入力データ。数値行列を指定します。X の行は観測値に、列は変数に対応します。

データ型: single | double

クエリ点。数値行列を指定します。Y の行は観測値に、列は変数に対応します。Y の列数は X と同じでなければなりません。

データ型: single | double

名前と値の引数

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

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

例: knnsearch(X,Y,'K',10,'IncludeTies',true,'Distance','cityblock') は、市街地距離を使用して、同順位を含む 10 個の最近傍を探索します。

Y 内の各点について X 内で探索する最近傍の個数。'K' と正の整数から構成されるコンマ区切りのペアとして指定します。

例: 'K',10

データ型: single | double

クエリ点から同じ距離にあるすべての最近傍を含むというフラグ。'IncludeTies' と false (0) または true (1) から構成されるコンマ区切りのペアとして指定します。

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

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

  • knnsearch は、k 番目に短い距離と等しい距離をもつすべての最近傍を出力引数に含めます。k を指定するには、名前と値のペアの引数 'K' を使用します。

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

例: 'IncludeTies',true

最近傍探索法。'NSMethod' と次のいずれかの値から構成されるコンマ区切りのペアとして指定します。

  • 'kdtree' — Kd 木を作成して使用することにより最近傍を探索します。X の列数が 10 以下であり、X がスパースではなく、距離計量が 'euclidean'、'cityblock'、'chebychev' または 'minkowski' である場合、'kdtree' が既定値になります。それ以外の場合、既定値は 'exhaustive' です。

    値 'kdtree' は、距離計量が上記の 4 つの尺度のいずれかである場合のみ有効です。

  • 'exhaustive' — X 内のすべての点から Y 内の各点までの距離の値を計算することにより、網羅的探索アルゴリズムを使用します。

例: 'NSMethod','exhaustive'

knnsearch が使用する距離計量。'Distance' と次の表のいずれかの値または関数ハンドルから構成されるコンマ区切りのペアとして指定します。

値説明
'euclidean'ユークリッド距離。
'seuclidean'標準化されたユークリッド距離。X の行とクエリ行列 Y の行の間の各座標差は、X から計算される、対応する標準偏差の要素で除算することによりスケーリングされます。他のスケーリングを指定するには、名前と値のペアの引数 'Scale' を使用します。
'cityblock'市街地距離。
'chebychev'チェビシェフ距離 (最大座標差)。
'minkowski'ミンコフスキー距離。既定の指数は 2 です。別の指数を指定するには、'P' 名前と値のペアの引数を使用します。
'mahalanobis'正定値共分散行列を使用して計算されるマハラノビス距離。共分散行列の値を変更するには、名前と値のペアの引数 '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。

  • j 番目の要素が観測値 ZI および ZJ(j,:) の間の距離になっている、m2 行 1 列の距離のベクトル D2 を返す。

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

例: 'Distance','chebychev'

ミンコフスキー距離計量の指数。'P' と正のスカラー値をコンマで区切って指定します。

この引数は、'Distance' が 'minkowski' である場合のみ有効です。

例: 'P',3

データ型: single | double

マハラノビス距離計量の共分散行列。'Cov' と正定値行列から構成されるコンマ区切りのペアとして指定します。

この引数は、'Distance' が 'mahalanobis' である場合のみ有効です。

例: 'Cov',eye(4)

データ型: single | double

標準化されたユークリッド距離計量のスケール パラメーター値。'Scale' と非負の数値ベクトルから構成されるコンマ区切りのペアとして指定します。'Scale' の長さは X の列数と同じにします。標準化されたユークリッド距離を knnsearch で計算するときに、X の各座標と各クエリ点が 'Scale' の対応する要素によってスケーリングされます。この引数は、'Distance' が 'seuclidean' である場合のみ有効です。

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

データ型: single | double

Kd 木の葉ノードにおけるデータ点の最大数。'BucketSize' と正の整数から構成されるコンマ区切りのペアとして指定します。この引数は、NSMethod が 'kdtree' である場合のみ有効です。

例: 'BucketSize',20

データ型: single | double

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

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

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

  • NSMethod が 'kdtree'。

  • IncludeTies が false。

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

既定では、SortIndices は true です。NSMethod が 'exhaustive' であるか、IncludeTies が true である場合、常にインデックスが並べ替えられます。

例: 'SortIndices',false

データ型: logical

出力引数

すべて折りたたむ

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

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

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

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

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

  • IncludeTies (既定は false) を指定しなかった場合、D は m 行 k 列の数値行列になります。m は Y の行数、k は探索対象の最近傍の個数です。D(j,i) は、距離計量による X(Idx(j,i),:) と Y(j,:) の間の距離です。

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

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

ヒント

  • knnsearch は、一定の正の整数 k について、Y 内の各点に最も近い k 個の点を X 内で探索します。Y 内の各点から一定距離以内にあるすべての点を X 内で探索するには、rangesearch を使用します。

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

アルゴリズム

特定の検索アルゴリズムの詳細は、k 最近傍探索および半径探索を参照してください。

代替機能

関数 knnsearch の名前と値のペアの引数 'NSMethod' を適切な値 (網羅的探索アルゴリズムの場合は 'exhaustive'、Kd 木アルゴリズムの場合は 'kdtree') に設定した場合、オブジェクト関数 knnsearch を使用して距離探索を実行することにより得られる結果と同じ探索結果になります。関数 knnsearch とは異なり、オブジェクト関数 knnsearch では ExhaustiveSearcher または KDTreeSearcher モデル オブジェクトが必要です。

参照

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

拡張機能

バージョン履歴

R2010a で導入

参考

| | |

トピック