createns

最近傍探索モデルオブジェクトの作成

構文

NS = createns(X)

NS = createns(X,Name=Value)

説明

NS = createns(X) は、n 行 K 列の学習データの数値行列 X を使用して、ExhaustiveSearcher モデルオブジェクトまたは KDTreeSearcher モデルオブジェクトを作成します。

NS = createns(X,Name=Value) では、1 つ以上の名前と値の引数を使用して追加オプションを指定します。たとえば、hnswSearcher モデルオブジェクトを作成する場合は NS = createns(X,NSMethod="hnsw") のように、作成するオブジェクトのタイプを NSMethod を設定して指定できます。

例

すべて折りたたむ

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

ライブスクリプトを開く

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

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 に渡します。

既定の Kd 木を成長させる

ライブスクリプトを開く

ユークリッド距離を使用する 4 次元の Kd 木を成長させます。

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

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

n = 
150

k = 
4

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

データセット全体を学習データとして使用して、4 次元の Kd 木を成長させます。

Mdl1 = KDTreeSearcher(X)

Mdl1 = 
  KDTreeSearcher with properties:

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

Mdl1 は KDTreeSearcher モデルオブジェクトで、プロパティがコマンドウィンドウに表示されます。このオブジェクトには、距離計量など、成長した 4 次元 Kd 木に関する情報が格納されています。プロパティの値は、ドット表記を使用して変更できます。

または、createns を使用して Kd 木を成長させることができます。

Mdl2 = createns(X)

Mdl2 = 
  KDTreeSearcher with properties:

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

Mdl2 は KDTreeSearcher モデルオブジェクトでもあり、Mdl1 と等価です。X には 4 つの列があり、既定の距離計量はユークリッドであるため、createns は既定では KDTreeSearcher モデルを作成します。

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

ミンコフスキー距離計量による Kd 木の成長

ライブスクリプトを開く

指数が 5 のミンコフスキー距離を使用して Kd 木を成長させます。

フィッシャーのアヤメのデータセットを読み込みます。花弁の寸法を格納する変数を作成します。

load fisheriris
X = meas(:,3:4);

Kd 木を成長させます。指数が 5 のミンコフスキー距離を指定します。

Mdl = createns(X,'Distance','minkowski','P',5)

Mdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 5
                X: [150x2 double]

X には 2 つの列があり、距離計量がミンコフスキーであるため、createns は既定では KDTreeSearcher モデルオブジェクトを作成します。

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

ライブスクリプトを開く

関数 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,:) になります。

入力引数

すべて折りたたむ

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

学習データ。数値行列を指定します。X には、それぞれが観測値 (インスタンスまたは事例) に対応する n 個の行と、それぞれが予測子 (特徴) に対応する K 個の列が含まれます。

データ型: single | double

名前と値の引数

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

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

例: NS = createns(X,'Distance','mahalanobis') は、最近傍を探索するときにマハラノビス距離計量を使用する ExhaustiveSearcher モデルオブジェクトを作成します。

すべての探索モデル

すべて折りたたむ

`NSMethod` — 最近傍探索法
`"kdtree"` | `"exhaustive"` | `"hnsw"`

作成するオブジェクトのタイプを定義するために使用される最近傍探索法。"kdtree"、"exhaustive"、または "hnsw" として指定します。

"kdtree" — createns は Kd 木アルゴリズムを使用して KDTreeSearcher モデルオブジェクトを作成します。
"exhaustive" — createns は網羅的探索アルゴリズムを使用して ExhaustiveSearcher モデルオブジェクトを作成します。
"hnsw" — createns は Hierarchical Navigable Small Worlds (HNSW) アルゴリズムを使用して hnswSearcher モデルオブジェクトを作成します。hnswSearcher は、他のモデルタイプよりも作成に時間がかかりますが、探索の実行が高速になります。一般に、hnswSearcher の結果は厳密な結果ではなく近似になります。

次の 3 つの条件が満たされる場合、既定値は "kdtree" です。

X の列数 (K) が 10 以下である (つまり、K ≤ 10)。
X がスパースでない
Distance が "euclidean"、"cityblock"、"chebychev" または "minkowski" である。

それ以外の場合、既定値は "exhaustive" です。

例: NSMethod="exhaustive"

データ型: char | string

`Distance` — 距離計量
`'euclidean'` (既定値) | 距離計量の文字ベクトルまたは string スカラー | 関数ハンドル

以後のクエリ点について最近傍を探索するために knnsearch または rangesearch を呼び出すときに使用する距離計量。距離計量の文字ベクトルまたは string スカラー、または関数ハンドルとして指定します。

すべてのタイプの最近傍探索モデルについて、createns は次の距離計量をサポートします。

値	説明
`'chebychev'`	チェビシェフ距離 (最大座標差)
`'cityblock'`	市街地距離
`'euclidean'`	ユークリッド距離
`'minkowski'`	ミンコフスキー距離。既定の指数は 2 です。別の指数を指定するには、名前と値の引数 `'P'` を使用します。

createns が網羅的探索アルゴリズムを使用する ('NSMethod' が 'exhaustive') 場合、createns は次の距離計量もサポートします。

値	説明
`'correlation'`	1 から、観測値間の標本線形相関を減算 (値の系列として処理)
`'cosine'`	(行ベクトルとして扱われる) 観測値間の夾角の余弦を 1 から減算
`'fasteuclidean'`	予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算されるユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。`'fast'` から始まるアルゴリズムでは、スパースデータはサポートされません。詳細については、アルゴリズムを参照してください。
`'fastseuclidean'`	予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算される標準化されたユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。`'fast'` から始まるアルゴリズムでは、スパースデータはサポートされません。詳細については、アルゴリズムを参照してください。
`'hamming'`	ハミング距離 (異なる座標の比率)
`'jaccard'`	1 からジャカード係数 (異なる非ゼロ座標の比率) を減算
`'mahalanobis'`	マハラノビス距離
`'seuclidean'`	標準化されたユークリッド距離
`'spearman'`	1 から観測値間の標本スピアマン順位相関係数を減算 (値の系列として処理)

HNSW アルゴリズム (NSMethod="hnsw") では、fast から始まる "fasteuclidean" と "fastseuclidean" を除き、網羅的探索アルゴリズム向けのリストに記載された同じ距離計量がサポートされます。"hnsw" アルゴリズムではカスタム距離計量はサポートされません。

createns が網羅的探索アルゴリズムを使用する ('NSMethod' が 'exhaustive') 場合、@ を使用してカスタム距離計量の関数ハンドル (たとえば @distfun) を指定することもできます。カスタムな距離関数は、次のようになっていなければなりません。

function D2 = distfun(ZI,ZJ) という形式になっている。
次の引数を受け入れる。
- X またはクエリ点 Y の 1 行が含まれている 1 行 K 列のベクトル ZI。K は X の列数です。
- X または Y の複数行が含まれている m 行 K 列の行列 ZJ。m は正の整数です。
m 行 1 列の距離のベクトル D2 を返す。D2(j) は、観測値 ZI と ZJ(j,:) の間の距離です。

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

例: 'Distance','minkowski'

データ型: char | string | function_handle

`P` — ミンコフスキー距離計量の指数
`2` (既定値) | 正のスカラー

ミンコフスキー距離計量の指数。正のスカラーとして指定します。この引数は、Distance が "minkowski" である場合のみ有効です。

P の値により、モデルオブジェクトの DistParameter プロパティの値が設定されます。

例: P=3

データ型: single | double

網羅的最近傍探索モデルと Hierarchical Navigable Small Worlds 探索モデル

すべて折りたたむ

`Cov` — マハラノビス距離計量の共分散行列
`cov(X,"omitrows")` (既定値) | 正定値行列

マハラノビス距離計量の共分散行列。K 行 K 列の正定値行列として指定します。K は X の列数です。この引数は、Distance が "mahalanobis" である場合のみ有効です。

Cov の値により、モデルオブジェクトの DistParameter プロパティの値が設定されます。

例: Cov=eye(3)

データ型: single | double

`Scale` — 標準化されたユークリッド距離計量のスケールパラメーター値
`std(X,"omitnan")` (既定値) | 非負の数値ベクトル

標準化されたユークリッド距離計量のスケールパラメーター値。長さ K の非負の数値ベクトルとして指定します。K は X の列数です。学習データとクエリデータの間の距離は、対応する Scale の要素を使用してスケーリングされます。この引数は、Distance が "seuclidean" である場合のみ有効です。

Scale の値により、モデルオブジェクトの DistParameter プロパティの値が設定されます。

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

データ型: single | double

Kd 木を使用する最近傍探索モデルの場合

すべて折りたたむ

`BucketSize` — 各葉ノードの最大データ点数
`50` (既定値) | 正の整数

Kd 木の各葉ノードにおける最大データ点数。'BucketSize' と正の整数をコンマで区切って指定します。

この引数は、KDTreeSearcher モデルオブジェクトを作成する場合のみ有効です。

例: 'BucketSize',10

データ型: single | double

Hierarchical Navigable Small Worlds アルゴリズム

すべて折りたたむ

`MaxNumLinksPerNode` — ノードごとに作成される結合数
`min(16,N)` (`N` は `X` の行数) (既定値) | 正のスカラー

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

ノードごとに作成される結合数。正のスカラーとして指定します。通常は、約 5 ～ 48 の数値を設定します。MaxNumLinksPerNode が TrainSetSize を超えてはなりません。

データ型: double

`TrainSetSize` — 最近傍候補リストのサイズ
`200` (既定値) | 正の整数

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

最近傍候補リストのサイズ。正の整数として指定します。通常は、約 100 ～ 2000 の数値を設定します。TrainSetSize は、MaxNumLinksPerNode 以上でなければならず、N (X の行数) 以下でなければなりません。

TrainSetSize の適切な値を探すときは、次の方法を試すことができます。

非常に精度が高い (厳密な探索に近い) 探索結果が得られる十分に大きい値を指定します。
精度が適度に良好な範囲 (再現率 0.95 ～ 0.99) になるまで、値を小さくしながらクエリのテストを実行します。

データ型: double

出力引数

すべて折りたたむ

`NS` — 最近傍探索モデル
`ExhaustiveSearcher` モデルオブジェクト | `KDTreeSearcher` モデルオブジェクト | `hnswSearcher` モデルオブジェクト

最近傍探索モデル。ExhaustiveSearcher、KDTreeSearcher、または hnswSearcher モデルオブジェクトとして返されます。

最近傍探索モデルオブジェクトの作成後、それを使用して knnsearch による最近傍探索を実行して、クエリデータに近い学習データの点を探索できます。ExhaustiveSearcher または KDTreeSearcher モデルオブジェクトの場合に限り、rangesearch を使用した半径探索も実行できます。

アルゴリズム

すべて折りたたむ

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

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.

バージョン履歴

R2010a で導入

すべて展開する

R2024a: Hierarchical Navigable Small Worlds (HNSW) 探索モデルの作成

HNSW 探索モデルを作成するには、探索モデルオブジェクトを作成するときに NSMethod="hnsw" を指定します。HNSW アルゴリズムは、他の探索モデルタイプよりも探索が高速な近似最近傍探索モデルです。詳細については、hnswSearcher を参照してください。

HNSW 探索モデルでは、fast から始まる "fasteuclidean" と "fastseuclidean" を除き、網羅的探索アルゴリズム向けのリストに記載された同じ Distance 計量がサポートされます。HNSW ではカスタム距離計量はサポートされません。

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

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

参考

knnsearch | rangesearch | KDTreeSearcher | ExhaustiveSearcher | hnswSearcher

トピック

k 最近傍探索および半径探索

createns

構文

説明

例

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

既定の Kd 木を成長させる

ミンコフスキー距離計量による Kd 木の成長

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

入力引数

X — 学習データ 数値行列

名前と値の引数

NSMethod — 最近傍探索法 "kdtree" | "exhaustive" | "hnsw"

Distance — 距離計量 'euclidean' (既定値) | 距離計量の文字ベクトルまたは string スカラー | 関数ハンドル

P — ミンコフスキー距離計量の指数 2 (既定値) | 正のスカラー

Cov — マハラノビス距離計量の共分散行列 cov(X,"omitrows") (既定値) | 正定値行列

Scale — 標準化されたユークリッド距離計量のスケール パラメーター値 std(X,"omitnan") (既定値) | 非負の数値ベクトル

BucketSize — 各葉ノードの最大データ点数 50 (既定値) | 正の整数

MaxNumLinksPerNode — ノードごとに作成される結合数 min(16,N) (N は X の行数) (既定値) | 正のスカラー

TrainSetSize — 最近傍候補リストのサイズ 200 (既定値) | 正の整数

出力引数

NS — 最近傍探索モデル ExhaustiveSearcher モデル オブジェクト | KDTreeSearcher モデル オブジェクト | hnswSearcher モデル オブジェクト

アルゴリズム

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

参照

バージョン履歴

R2024a: Hierarchical Navigable Small Worlds (HNSW) 探索モデルの作成

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

参考

トピック

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

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

`NSMethod` — 最近傍探索法
`"kdtree"` | `"exhaustive"` | `"hnsw"`

`Distance` — 距離計量
`'euclidean'` (既定値) | 距離計量の文字ベクトルまたは string スカラー | 関数ハンドル

`P` — ミンコフスキー距離計量の指数
`2` (既定値) | 正のスカラー

`Cov` — マハラノビス距離計量の共分散行列
`cov(X,"omitrows")` (既定値) | 正定値行列

`Scale` — 標準化されたユークリッド距離計量のスケールパラメーター値
`std(X,"omitnan")` (既定値) | 非負の数値ベクトル

`BucketSize` — 各葉ノードの最大データ点数
`50` (既定値) | 正の整数

`MaxNumLinksPerNode` — ノードごとに作成される結合数
`min(16,N)` (`N` は `X` の行数) (既定値) | 正のスカラー

`TrainSetSize` — 最近傍候補リストのサイズ
`200` (既定値) | 正の整数

`NS` — 最近傍探索モデル
`ExhaustiveSearcher` モデルオブジェクト | `KDTreeSearcher` モデルオブジェクト | `hnswSearcher` モデルオブジェクト