ExhaustiveSearcher

網羅的最近傍探索モデルの作成

説明

ExhaustiveSearcher モデルオブジェクトには、網羅的最近傍探索の学習データ、距離計量、および距離計量のパラメーター値が格納されます。網羅的探索アルゴリズムでは、学習データに含まれている n 個の観測値すべてについて、各クエリ観測値からの距離を求めます。距離は、n 行 K 列の数値行列になります。

ExhaustiveSearcher モデルオブジェクトを作成したら、knnsearch による最近傍探索または rangesearch による半径探索を実行して、クエリデータに対する学習データの近傍点を探索します。網羅的探索アルゴリズムは、K が大きい場合 (K > 10) に Kd 木アルゴリズムより効率的です。また、距離計量の選択に関して Kd 木アルゴリズムより柔軟です。また、ExhaustiveSearcher モデルオブジェクトはスパースなデータにも対応しています。

作成

関数 createns または関数 ExhaustiveSearcher (ここで説明) を使用して、ExhaustiveSearcher オブジェクトを作成します。どちらの関数も同じ構文を使用しますが、関数 createns には名前と値のペアの引数 'NSMethod' があります。これは、最近傍探索法を選択するために使用されます。関数 createns は KDTreeSearcher オブジェクトも作成します。ExhaustiveSearcher オブジェクトを作成するには 'NSMethod','exhaustive' を指定します。K > 10 であるか、学習データがスパースであるか、距離計量がユークリッド、市街地、チェビシェフ、ミンコフスキーのいずれでもない場合、既定値は 'exhaustive' です。

構文

Mdl = ExhaustiveSearcher(X)

Mdl = ExhaustiveSearcher(X,Name,Value)

説明

例

Mdl = ExhaustiveSearcher(X) は、学習データ (X) の n 行 K 列の数値行列を使用して、網羅的最近傍探索オブジェクト (Mdl) を作成します。

例

Mdl = ExhaustiveSearcher(X,Name,Value) では、1 つ以上の名前と値のペアの引数を使用して追加オプションを指定します。距離計量を指定し、距離計量のパラメーター (DistParameter プロパティ) を設定できます。たとえば、ExhaustiveSearcher(X,'Distance','chebychev') はチェビシェフ距離を使用する網羅的最近傍探索オブジェクトを作成します。DistParameter を指定するには、名前と値のペアの引数 Cov、P または Scale を使用します。

入力引数

すべて展開する

`X` — 学習データ
数値行列

網羅的探索アルゴリズムを準備する学習データ。数値行列を指定します。X には、それぞれが観測値 (インスタンスまたは事例) に対応する n 個の行と、それぞれが予測子 (特徴量) に対応する K 個の列を含めます。

データ型: single | double

名前と値の引数

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

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

例: 'Distance','mahalanobis','Cov',eye(3) は、最近傍を探索するときにマハラノビス距離を使用し、マハラノビス距離計量の共分散行列に 3 行 3 列の単位行列を使用するよう指定します。

プロパティ

すべて展開する

`X` — 学習データ
数値行列

このプロパティは読み取り専用です。

このプロパティの設定は、createns または ExhaustiveSearcher の入力引数 X で行います。

データ型: single | double

`Distance` — 距離計量
文字ベクトル | string スカラー | カスタム距離関数

以後のクエリ点について最近傍を探索するために knnsearch または rangesearch を呼び出すときに使用する距離計量。文字ベクトルまたは string スカラー ('chebychev'、'cityblock'、'correlation'、'cosine'、'euclidean'、'fasteuclidean'、'fastseuclidean'、'hamming'、'jaccard'、'minkowski'、'mahalanobis'、'seuclidean'、'spearman')、または関数ハンドルとして指定します。

このプロパティの設定は、createns または ExhaustiveSearcher の名前と値のペアの引数 'Distance' で行います。

距離計量は ExhaustiveSearcher モデルオブジェクトの作成に使用されないので、ドット表記を使用して変更できます。'fast' から始まるアルゴリズムでは、スパースデータはサポートされません。

`DistParameter` — 距離計量のパラメーター値
`[]` | 正のスカラー

距離計量のパラメーター値。空 ([]) または正のスカラーを指定します。

サポートされる距離計量の距離パラメーターを次の表で説明します。

距離計量パラメーターの説明

距離計量	パラメーターの説明
`'mahalanobis'`	マハラノビス距離の計算に使用する共分散行列を表す正定値行列。既定では、`cov(Mdl.X,'omitrows')` を使用して共分散が設定されます。このプロパティの設定は、`createns` または `ExhaustiveSearcher` の名前と値のペアの引数 `'Cov'` で行います。 `Mdl.DistParameter = CovNew` のようにドット表記を使用して `DistParameter` を変更できます。`CovNew` は K 行 K 列の正定数値行列です。
`'minkowski'`	ミンコフスキー距離の指数を表す正のスカラー。既定の指数は `2` です。このプロパティの設定は、`createns` または `ExhaustiveSearcher` の名前と値のペアの引数 `'P'` で行います。 `Mdl.DistParameter = PNew` のようにドット表記を使用して `DistParameter` を変更できます。`PNew` は正のスカラーです。
`'seuclidean'`	標準化されたユークリッド距離を計算するときに予測子のスケーリングに使用する値を表す正の数値ベクトル。既定の設定では、次の処理が行われます。 `scale = std(Mdl.X,'omitnan')` を使用して `X` の各予測子 (列) の標準偏差を推定する。対応する `scale` の要素で除算して、`X` とクエリ行列の行間の座標差をスケーリングする。このプロパティの設定は、`createns` または `ExhaustiveSearcher` の名前と値のペアの引数 `'Scale'` で行います。 `Mdl.DistParameter = sNew` のようにドット表記を使用して `DistParameter` を変更できます。`sNew` は K 次元の正の数値ベクトルです。

'mahalanobis'

マハラノビス距離の計算に使用する共分散行列を表す正定値行列。既定では、cov(Mdl.X,'omitrows') を使用して共分散が設定されます。

このプロパティの設定は、createns または ExhaustiveSearcher の名前と値のペアの引数 'Cov' で行います。

Mdl.DistParameter = CovNew のようにドット表記を使用して DistParameter を変更できます。CovNew は K 行 K 列の正定数値行列です。

'minkowski'

ミンコフスキー距離の指数を表す正のスカラー。既定の指数は 2 です。

このプロパティの設定は、createns または ExhaustiveSearcher の名前と値のペアの引数 'P' で行います。

Mdl.DistParameter = PNew のようにドット表記を使用して DistParameter を変更できます。PNew は正のスカラーです。

'seuclidean'

標準化されたユークリッド距離を計算するときに予測子のスケーリングに使用する値を表す正の数値ベクトル。既定の設定では、次の処理が行われます。

scale = std(Mdl.X,'omitnan') を使用して X の各予測子 (列) の標準偏差を推定する。
対応する scale の要素で除算して、X とクエリ行列の行間の座標差をスケーリングする。

このプロパティの設定は、createns または ExhaustiveSearcher の名前と値のペアの引数 'Scale' で行います。

Mdl.DistParameter = sNew のようにドット表記を使用して DistParameter を変更できます。sNew は K 次元の正の数値ベクトルです。

Mdl.Distance がこの表に記載されているパラメーターのいずれにも該当しない場合、Mdl.DistParameter を [] にします。これは、指定した距離計量の式にパラメーターがないことを意味します。

データ型: single | double

オブジェクト関数

`knnsearch`	探索モデルオブジェクトを使用して k 最近傍を探索
`rangesearch`	探索モデルオブジェクトを使用して指定距離内の近傍をすべて探索

例

すべて折りたたむ

既定の網羅的最近傍探索モデルの学習

ライブスクリプトを開く

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

load fisheriris
X = meas;
[n,k] = size(X)

n = 150

k = 4

X には 150 個の観測値と 4 つの予測子があります。

データセット全体を学習データとして使用して、網羅的最近傍探索モデルを準備します。

Mdl1 = ExhaustiveSearcher(X)

Mdl1 = 
  ExhaustiveSearcher with properties:

         Distance: 'euclidean'
    DistParameter: []
                X: [150x4 double]

Mdl1 は ExhaustiveSearcher モデルオブジェクトで、プロパティがコマンドウィンドウに表示されます。このオブジェクトには、距離計量など、学習済みアルゴリズムに関する情報が格納されています。プロパティの値は、ドット表記を使用して変更できます。

または、createns を使用し、探索法として 'exhaustive' を指定することによっても、網羅的最近傍探索モデルを準備できます。

Mdl2 = createns(X,'NSMethod','exhaustive')

Mdl2 = 
  ExhaustiveSearcher with properties:

         Distance: 'euclidean'
    DistParameter: []
                X: [150x4 double]

Mdl2 は ExhaustiveSearcher モデルオブジェクトでもあり、Mdl1 と等価です。

一連のクエリデータに対する最近傍を X から探索するには、ExhaustiveSearcher モデルオブジェクトとクエリデータを knnsearch または rangesearch に渡します。

最近傍探索にマハラノビス距離を指定する

ライブスクリプトを開く

フィッシャーのアヤメのデータセットを読み込みます。花弁の寸法に焦点を当てます。

load fisheriris
X = meas(:,[3 4]); % Predictors

網羅的最近傍探索モデルを準備します。マハラノビス距離計量を指定します。

Mdl = createns(X,'Distance','mahalanobis')

Mdl = 
  ExhaustiveSearcher with properties:

         Distance: 'mahalanobis'
    DistParameter: [2x2 double]
                X: [150x2 double]

距離計量がマハラノビスであるため、createns は既定では ExhaustiveSearcher モデルオブジェクトを作成します。

ドット表記を使用して Mdl のプロパティにアクセスします。たとえば、マハラノビス共分散パラメーターにアクセスするには、Mdl.DistParameter を使用します。

Mdl.DistParameter

ans = 2×2

    3.1163    1.2956
    1.2956    0.5810

クエリデータと Mdl は、次の関数に渡すことができます。

最近傍のインデックスと距離を求めるための knnsearch
指定距離内にある最近傍のインデックスをすべて求めるための rangesearch

`ExhaustiveSearcher` モデルのプロパティの変更

ライブスクリプトを開く

ドット表記を使用して、ExhaustiveSearcher モデルオブジェクトを作成し、Distance プロパティを変更します。

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

load fisheriris
X = meas;

データセット全体を学習データとして使用して、既定の網羅的探索アルゴリズムを学習させます。

Mdl = ExhaustiveSearcher(X)

Mdl = 
  ExhaustiveSearcher with properties:

         Distance: 'euclidean'
    DistParameter: []
                X: [150x4 double]

近傍探索モデルでマハラノビス尺度を使用して学習データとクエリデータの間の距離を計算するように指定します。

Mdl.Distance = 'mahalanobis'

Mdl = 
  ExhaustiveSearcher with properties:

         Distance: 'mahalanobis'
    DistParameter: [4x4 double]
                X: [150x4 double]

Mdl とクエリデータを knnsearch または rangesearch のいずれかに渡すと、マハラノビス距離に基づいてクエリデータ内の点に対する最近傍を求めることができます。

マハラノビス距離によるクエリデータの最近傍の探索

ライブスクリプトを開く

関数 createns を使用して、網羅的探索モデルオブジェクトを作成します。k 最近傍を探索するため、オブジェクトとクエリデータを関数 knnsearch に渡します。

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

load fisheriris

クエリセットとして使用するため、5 つのアヤメのデータを無作為に予測子データから抽出します。

rng('default');             % 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,:);

学習データを使用して網羅的最近傍探索モデルを準備します。最近傍の探索にマハラノビス距離を指定します。

Mdl = createns(X,'Distance','mahalanobis')

Mdl = 
  ExhaustiveSearcher with properties:

         Distance: 'mahalanobis'
    DistParameter: [4x4 double]
                X: [145x4 double]

距離計量がマハラノビスであるため、createns は既定では ExhaustiveSearcher モデルオブジェクトを作成します。

マハラノビス距離の計算には、学習データ内の予測子 (列) の共分散行列が使用されます。この値を表示するには、Mdl.DistParameter を使用します。

Mdl.DistParameter

ans = 4×4

    0.6547   -0.0368    1.2320    0.5026
   -0.0368    0.1914   -0.3227   -0.1193
    1.2320   -0.3227    3.0671    1.2842
    0.5026   -0.1193    1.2842    0.5800

求める学習データ (Mdl.X) のインデックスは、クエリデータ (Y) の各点における 2 つの最近傍です。

IdxNN = knnsearch(Mdl,Y,'K',2)

IdxNN = 5×2

     5     6
    98    95
   104   128
   135    65
   102   115

IdxNN の各行は、クエリデータの観測値に対応します。列の順序は、距離の昇順で並べ替えた最近傍の順序に対応します。たとえば、マハラノビス距離に基づくと、Y(3,:) の 2 番目の最近傍は X(128,:) になります。

アルゴリズム

すべて展開する

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

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

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

$\begin{matrix} D_{i, j}^{2} = ‖ x_{i} - x_{j} ‖^{2} \\ = (^{x_{i} - x_{j}) T} (x_{i} - x_{j}) \\ = ‖ x_{i} ‖^{2} - 2 x_{i}^{T} x_{j} + ‖ x_{j} ‖^{2} . \end{matrix}$

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

参照

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

拡張機能

C/C++ コード生成
MATLAB® Coder™ を使用して C および C++ コードを生成します。

使用上の注意事項および制限事項:

関数 knnsearch および rangesearch はコード生成をサポートします。
ExhaustiveSearcher モデルオブジェクトに学習をさせる場合、名前と値のペアの引数 'Distance' の値をカスタム距離関数にすることはできません。
ExhaustiveSearcher では、高速ユークリッド距離計算、つまり名前が fast から始まる距離計量 ('fasteuclidean' など) のコード生成はサポートされていません。

詳細については、コード生成の紹介と最近傍探索モデルのコード生成を参照してください。

バージョン履歴

R2010a で導入

すべて展開する

R2023a: キャッシュを使用した高速ユークリッド距離

'fasteuclidean' および 'fastseuclidean' の距離計量では、キャッシュと別のアルゴリズムを使用してユークリッド距離の計算が高速化されます (アルゴリズムを参照)。これらの距離計量は関数 knnsearch にのみ適用されます。

参考

KDTreeSearcher | createns | knnsearch | rangesearch

ExhaustiveSearcher

説明

作成

構文

説明

入力引数

X — 学習データ 数値行列

プロパティ

X — 学習データ 数値行列

Distance — 距離計量 文字ベクトル | string スカラー | カスタム距離関数

DistParameter — 距離計量のパラメーター値 [] | 正のスカラー

オブジェクト関数

例

既定の網羅的最近傍探索モデルの学習

最近傍探索にマハラノビス距離を指定する

ExhaustiveSearcher モデルのプロパティの変更

マハラノビス距離によるクエリ データの最近傍の探索

アルゴリズム

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

参照

拡張機能

C/C++ コード生成 MATLAB® Coder™ を使用して C および C++ コードを生成します。

バージョン履歴

R2023a: キャッシュを使用した高速ユークリッド距離

参考

トピック

`X` — 学習データ
数値行列

`X` — 学習データ
数値行列

`Distance` — 距離計量
文字ベクトル | string スカラー | カスタム距離関数

`DistParameter` — 距離計量のパラメーター値
`[]` | 正のスカラー

`ExhaustiveSearcher` モデルのプロパティの変更

マハラノビス距離によるクエリデータの最近傍の探索

C/C++ コード生成
MATLAB® Coder™ を使用して C および C++ コードを生成します。