入力データを使用して 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異なる距離計量を使用した k 最近傍の探索
ライブ スクリプトを開く
最初にミンコフスキー距離計量を、次にチェビシェフ距離計量を使用して、Y 内の各点に対する 10 個の最近傍を X 内で探索します。
フィッシャーのアヤメのデータ セットを読み込みます。
load fisheririsX = meas(:,3:4); % Measurements of original flowersY = [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')
fasteuclidean 距離を使用した距離計算の高速化
ライブ スクリプトを開く
2 つの大規模な点の行列を作成し、既定の "euclidean" 距離計量を使用した knnsearch の所要時間を測定します。
rng default % For reproducibilityN = 10000;X = randn(N,1000);Y = randn(N,1000);Idx = knnsearch(X,Y); % Warm up function for more reliable timing informationticIdx = knnsearch(X,Y);standard = toc
standard = 28.1783
次に、"fasteuclidean" 距離計量を使用した knnsearch の所要時間を測定します。キャッシュ サイズは 100 に指定します。
Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100); % Warm up functionticIdx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100);accelerated = toc
accelerated = 2.7198
計算の高速化によって標準よりも何倍速くなったかを評価します。
standard/accelerated
ans = 10.3606
この例では、高速化したバージョンの方が 3 倍を超える速さになっています。
入力引数
すべて折りたたむ
X — 入力データ
数値行列
入力データ。数値行列を指定します。X の行は観測値に、列は変数に対応します。
データ型: single | double
Y — クエリ点
数値行列
クエリ点。数値行列を指定します。Y の行は観測値に、列は変数に対応します。Y の列数は X と同じでなければなりません。
データ型: single | double
名前と値の引数
オプションの引数のペアを Name1=Value1,...,NameN=ValueN として指定します。ここで Name は引数名、Value は対応する値です。名前と値の引数は他の引数の後ろにする必要がありますが、ペアの順序は関係ありません。
R2021a より前では、名前と値をそれぞれコンマを使って区切り、Name を引用符で囲みます。
例: knnsearch(X,Y,'K',10,'IncludeTies',true,'Distance','cityblock') は、市街地距離を使用して、同順位を含む 10 個の最近傍を探索します。
K — 最近傍の個数
1 (既定値) | 正の整数
Y 内の各点について X 内で探索する最近傍の個数。'K' と正の整数から構成されるコンマ区切りのペアとして指定します。
例: 'K',10
データ型: single | double
IncludeTies — すべての最近傍を含むというフラグ
false (0) (既定値) | true (1)
クエリ点から同じ距離にあるすべての最近傍を含むというフラグ。'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' | 'exhaustive'
最近傍探索法。'NSMethod' と次のいずれかの値から構成されるコンマ区切りのペアとして指定します。
'kdtree'— Kd 木を作成して使用することにより最近傍を探索します。X の列数が 10 以下であり、Xがスパースではなく、距離計量が'euclidean'、'cityblock'、'chebychev'または'minkowski'である場合、'kdtree'が既定値になります。それ以外の場合、既定値は'exhaustive'です。値
'kdtree'は、距離計量が上記の 4 つの尺度のいずれかである場合のみ有効です。'exhaustive'—X内のすべての点から Y 内の各点までの距離の値を計算することにより、網羅的探索アルゴリズムを使用します。
例: 'NSMethod','exhaustive'
Distance — 距離計量
'euclidean' (既定値) | 'seuclidean' | 'fasteuclidean' | 'fastseuclidean' | 'cityblock' | 'chebychev' | 'minkowski' | 'mahalanobis' | 'cosine' | 'correlation' | 'spearman' | 'hamming' | 'jaccard' | 関数ハンドル | ...
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
CacheSize — メガバイト単位のグラム行列のサイズ
1e3 (既定値) | 正のスカラー | "maximal"
メガバイト単位のグラム行列のサイズ。正のスカラーまたは "maximal" として指定します。関数 knnsearch で CacheSize を使用できるのは、名前と値の引数 Distance が fast で始まり、名前と値の引数 NSMethod が 'exhaustive' に設定されている場合のみです。
CacheSize を "maximal" に設定すると、knnsearch は、MX 行 MY 列のサイズの中間行列全体に十分なメモリを割り当てようと試みます。ここで、MX は入力データ X の行数、MY は入力データ Y の行数です。キャッシュ サイズは、中間行列全体に対して十分な大きさである必要はありませんが、少なくとも MX 行 1 列のベクトルを保持する十分な大きさでなければなりません。そうでない場合、knnsearch でのユークリッド距離の計算に標準のアルゴリズムが使用されます。
引数 Distance の値が fast で始まり、NSMethod の値が 'exhaustive' である場合に、CacheSize の値が大きすぎるか "maximal" であると、利用可能なメモリを超えるグラム行列の割り当てが knnsearch で試行されることがあります。この場合、MATLAB® はエラーを生成します。
例: CacheSize="maximal"
データ型: double | char | string
Scale — 標準化されたユークリッド距離計量のスケール パラメーター値
std(X,'omitnan') (既定値) | 非負の数値ベクトル
標準化されたユークリッド距離計量のスケール パラメーター値。'Scale' と非負の数値ベクトルから構成されるコンマ区切りのペアとして指定します。'Scale' の長さは X の列数と同じにします。標準化されたユークリッド距離を knnsearch で計算するときに、X の各座標と各クエリ点が 'Scale' の対応する要素によってスケーリングされます。この引数は、'Distance' が 'seuclidean' である場合のみ有効です。
例: 'Scale',quantile(X,0.75) - quantile(X,0.25)
データ型: single | double
BucketSize — Kd 木の葉ノードにおけるデータ点の最大数
50 (既定値) | 正の整数
Kd 木の葉ノードにおけるデータ点の最大数。'BucketSize' と正の整数から構成されるコンマ区切りのペアとして指定します。この引数は、NSMethod が 'kdtree' である場合のみ有効です。
例: 'BucketSize',20
データ型: single | double
SortIndices — 返されたインデックスを距離に従って並べ替えるためのフラグ
true (1) (既定値) | false (0)
返されたインデックスを距離に従って並べ替えるためのフラグ。'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
出力引数
すべて折りたたむ
Idx — 最近傍の入力データのインデックス
数値行列 | 数値ベクトルの cell 配列
最近傍の入力データのインデックス。数値行列、または数値ベクトルの 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 はインデックスを距離の昇順で並べ替えます。
D — 最近傍の距離
数値行列 | 数値ベクトルの cell 配列
クエリ点に対する最近傍の距離。数値行列、または数値ベクトルの 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 最近傍探索および半径探索を参照してください。
高速ユークリッド距離アルゴリズム
Distance 引数の fast から始まる値 ('fasteuclidean' や 'fastseuclidean' など) で使用されるアルゴリズムでは、計算時間の短縮のために追加のメモリを使用してユークリッド距離が計算されます。このアルゴリズムは、Albanie の[1]などで "ユークリッド距離行列トリック" として提唱されているものです。内部テストでは、このアルゴリズムによって予測子の数が 10 個以上の場合に時間の短縮になることが確認されています。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。
このアルゴリズムでは、xi と xj のすべての点間の距離の行列 D を求めるために (xi のそれぞれに n 個の変数を格納)、次の方程式の最後の行を使用して距離を計算します。
方程式の最後の行にある行列 は "グラム行列" と呼ばれます。正方化と加算によって平方距離を計算する代わりに、グラム行列を計算して使用すると、一連の平方距離の計算は高速になりますが、数値的安定性は少し低くなります。詳細については、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.
拡張機能
tall 配列
メモリの許容量を超えるような多数の行を含む配列を計算します。
使用上の注意事項および制限事項:
Xが tall 配列の場合、Yを tall 配列にすることはできません。同様に、Yが tall 配列の場合、Xを tall 配列にすることはできません。
詳細は、tall 配列を参照してください。
C/C++ コード生成
MATLAB® Coder™ を使用して C および C++ コードを生成します。
使用上の注意事項および制限事項:
コード生成では、
Xの列数が 7 より多い場合、名前と値のペアの引数'NSMethod'の既定値は'exhaustive'です。名前と値のペアの引数
'Distance'の値はコンパイル時の定数でなければならず、カスタム距離関数にすることはできません。名前と値のペアの引数
'IncludeTies'の値は、コンパイル時の定数でなければなりません。名前と値のペアの引数
'SortIndices'はサポートされていません。出力引数は常に並べ替えられます。knnsearchでは、高速ユークリッド距離計算、つまり名前がfastから始まる距離計量 ('fasteuclidean'など) のコード生成はサポートされていません。名前と値の引数に含まれる名前はコンパイル時の定数でなければなりません。たとえば、生成されたコードでミンコフスキー距離についてユーザー定義の指数を使用可能にするには、
{coder.Constant('Distance'),coder.Constant('Minkowski'),coder.Constant('P'),0}を codegen (MATLAB Coder) の-argsの値に含めます。'IncludeTies'にtrueを指定した場合、数値精度のために、生成コード内の同順位の距離の並び順が MATLAB の順序と異なる可能性があります。knnsearchが kd 木探索アルゴリズムを使用し、コード生成のビルド タイプが MEX 関数である場合、codegen (MATLAB Coder) は並列計算用に Intel® スレッディング ビルディング ブロック (TBB) を使用して MEX 関数を生成します。それ以外の場合、codegenは parfor (MATLAB Coder) を使用してコードを生成します。kd 木探索アルゴリズムの場合の MEX 関数 —
codegenは、マルチコア プラットフォームにおける並列計算用に Intel TBB を使用して、最適化された MEX 関数を生成します。この MEX 関数を使用して MATLAB アルゴリズムを高速化できます。Intel TBB の詳細については、https://www.intel.com/content/www/us/en/developer/tools/oneapi/onetbb.htmlを参照してください。生成された
parforバージョンのコードをテストするために MEX 関数を生成する場合、Intel TBB の使用を無効化できます。MEX 構成オブジェクトのExtrinsicCallsプロパティをfalseに設定します。詳細については、coder.MexCodeConfig (MATLAB Coder) を参照してください。網羅的探索アルゴリズムの場合の MEX 関数と、両方のアルゴリズムの場合のスタンドアロン C/C++ コード — 生成される
knnsearchのコードでは、parfor (MATLAB Coder) を使用して、サポートされている共有メモリ マルチコア プラットフォームで並列的に動作するループが作成されます。コンパイラが Open Multiprocessing (OpenMP) アプリケーション インターフェイスをサポートしない場合、または OpenMP ライブラリを無効にした場合、MATLAB Coder™ はparforループをforループとして扱います。サポートされるコンパイラについては、サポートされるコンパイラを参照してください。OpenMP ライブラリを無効にするには、構成オブジェクトのEnableOpenMPプロパティをfalseに設定します。詳細については、coder.CodeConfig (MATLAB Coder) を参照してください。
knnsearchは、生成されたスタンドアロン C/C++ コードにおいて、整数型 (int32) のインデックスを返します。そのため、関数は、単精度の入力を使用する場合、厳密な単精度のサポートを可能にします。MEX コード生成では、関数は依然として MATLAB の動作に一致する倍精度のインデックスを返します。R2020a より前:
knnsearchは、生成されたスタンドアロン C/C++ コードにおいて、倍精度のインデックスを返します。
コード生成の詳細については、コード生成の紹介および一般的なコード生成のワークフローを参照してください。
GPU 配列
Parallel Computing Toolbox™ を使用してグラフィックス処理装置 (GPU) 上で実行することにより、コードを高速化します。
使用上の注意事項および制限事項:
名前と値の引数
NSMethodは"exhaustive"として指定しなければなりません。名前と値の引数
IncludeTiesおよびSortIndicesは既定値として指定しなければなりません。名前と値の引数
Distanceは"fasteuclidean"または"fastseuclidean"として指定できません。
詳細は、GPU での MATLAB 関数の実行 (Parallel Computing Toolbox)を参照してください。
バージョン履歴
R2010a で導入
すべて展開する
R2023a: キャッシュを使用した高速ユークリッド距離
'fasteuclidean' および 'fastseuclidean' の距離計量では、キャッシュと別のアルゴリズムを使用してユークリッド距離の計算が高速化されます (アルゴリズムを参照)。キャッシュのサイズは名前と値の引数 CacheSize を使用して設定します。
参考
createns | knnsearch | ExhaustiveSearcher | KDTreeSearcher | hnswSearcher | rangesearch
トピック
- k 最近傍探索および半径探索
- 距離計量
MATLAB コマンド
次の MATLAB コマンドに対応するリンクがクリックされました。
コマンドを MATLAB コマンド ウィンドウに入力して実行してください。Web ブラウザーは MATLAB コマンドをサポートしていません。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- Deutsch
- English
- Français
- United Kingdom (English)
Asia Pacific
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 日本 (日本語)
- 한국 (한국어)
Contact your local office
