Main Content

knnsearch

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

説明

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

XY の間で 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. One or more of the lines displays its values using only markers These objects represent setosa, versicolor, virginica, query point, minkowski, chebychev.

2 つの大規模な点の行列を作成し、既定の "euclidean" 距離計量を使用した knnsearch の所要時間を測定します。

rng default % For reproducibility
N = 10000;
X = randn(N,1000);
Y = randn(N,1000);
Idx = knnsearch(X,Y); % Warm up function for more reliable timing information
tic
Idx = knnsearch(X,Y);
standard = toc
standard = 20.8135

次に、"fasteuclidean" 距離計量を使用した knnsearch の所要時間を測定します。キャッシュ サイズは 100 に指定します。

Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100); % Warm up function
tic
Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100);
accelerated = toc
accelerated = 2.0801

計算の高速化によって標準よりも何倍速くなったかを評価します。

standard/accelerated
ans = 10.0062

この例では、高速化したバージョンの方が 3 倍を超える速さになっています。

入力引数

すべて折りたたむ

入力データ。数値行列を指定します。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' を使用します。

  • IdxD は 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 が使用する距離計量。次の表のいずれかの値または関数ハンドルとして指定します。

説明
'euclidean'ユークリッド距離
'seuclidean'標準化されたユークリッド距離。X の行とクエリ行列 Y の行の間の各座標差は、X から算出される標準偏差の対応する要素で除算することによりスケーリングされます。別のスケーリングを指定するには、名前と値の引数 'Scale' を使用します。
'fasteuclidean'予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算されるユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。この距離計量は、NSMethod'exhaustive' の場合にのみ使用できます。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。
'fastseuclidean'予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算される標準化されたユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。この距離計量は、NSMethod'exhaustive' の場合にのみ使用できます。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。
'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'

データ型: char | string | function_handle

メガバイト単位のグラム行列のサイズ。正のスカラーまたは "maximal" として指定します。関数 knnsearchCacheSize を使用できるのは、名前と値の引数 Distancefast で始まり、名前と値の引数 NSMethod'exhaustive' に設定されている場合のみです。

CacheSize"maximal" に設定すると、knnsearch は、MXMY 列のサイズの中間行列全体に十分なメモリを割り当てようと試みます。ここで、MX は入力データ X の行数、MY は入力データ Y の行数です。キャッシュ サイズは、中間行列全体に対して十分な大きさである必要はありませんが、少なくとも MX 行 1 列のベクトルを保持する十分な大きさでなければなりません。そうでない場合、knnsearch でのユークリッド距離の計算に標準のアルゴリズムが使用されます。

引数 Distance の値が fast で始まり、NSMethod の値が 'exhaustive' である場合に、CacheSize の値が大きすぎるか "maximal" であると、利用可能なメモリを超えるグラム行列の割り当てが knnsearch で試行されることがあります。この場合、MATLAB® はエラーを生成します。

例: CacheSize="maximal"

データ型: double | char | string

ミンコフスキー距離計量の指数。'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) から構成されるコンマ区切りのペアとして指定します。

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

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

  • NSMethod'kdtree'

  • IncludeTiesfalse

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

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

例: '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}) に格納されます。

SortIndicestrue である場合、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}) に格納されます。

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

ヒント

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

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

アルゴリズム

すべて折りたたむ

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

高速ユークリッド距離アルゴリズム

Distance 引数の fast から始まる値 ('fasteuclidean''fastseuclidean' など) で使用されるアルゴリズムでは、計算時間の短縮のために追加のメモリを使用してユークリッド距離が計算されます。このアルゴリズムは、Albanie の[1]などで "ユークリッド距離行列トリック" として提唱されているものです。内部テストでは、このアルゴリズムによって予測子の数が 10 個以上の場合に時間の短縮になることが確認されています。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。

このアルゴリズムでは、xi と xj のすべての点間の距離の行列 D を求めるために (xi のそれぞれに n 個の変数を格納)、次の方程式の最後の行を使用して距離を計算します。

Di,j2=xixj2=(xixj)T(xixj)=xi22xiTxj+xj2.

方程式の最後の行にある行列 xiTxj"グラム行列" と呼ばれます。正方化と加算によって平方距離を計算する代わりに、グラム行列を計算して使用すると、一連の平方距離の計算は高速になりますが、数値的安定性は少し低くなります。詳細については、Albanie の[1]を参照してください。

グラム行列を格納するためにソフトウェアで既定で使用されるキャッシュのサイズは 1e3 メガバイトです。キャッシュ サイズは名前と値の引数 CacheSize を使用して設定できます。CacheSize の値が大きすぎるか "maximal" である場合、利用可能なメモリを超えるグラム行列の割り当てが knnsearch で試行されることがあります。この場合、MATLAB はエラーを生成します。

参照

[1] Albanie, Samuel. Euclidean Distance Matrix Trick. June, 2019. Available at https://www.robots.ox.ac.uk/%7Ealbanie/notes/Euclidean_distance_trick.pdf.

代替機能

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

Simulink ブロック

Simulink®k 最近傍探索を統合するには、Statistics and Machine Learning Toolbox™ ライブラリにある KNN Search ブロックを使用するか、MATLAB Function ブロックを関数 knnsearch と共に使用します。たとえば、MATLAB Function ブロックの使用によるクラス ラベルの予測を参照してください。

使用するアプローチを判断する際は、以下を考慮してください。

  • Statistics and Machine Learning Toolbox ライブラリ ブロックを使用する場合、固定小数点ツール (Fixed-Point Designer)を使用して浮動小数点モデルを固定小数点に変換できます。

  • MATLAB Function ブロックを関数 knnsearch と共に使用する場合は、可変サイズの配列に対するサポートを有効にしなければなりません。

参照

[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 で導入

すべて展開する