Main Content

createns

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

説明

NS = createns(X) は、nK 列の学習データの数値行列 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]

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

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

Mdl2 = createns(X,'NSMethod','exhaustive')
Mdl2 = 
  ExhaustiveSearcher with properties:

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

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

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

ユークリッド距離を使用する 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]

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

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

Mdl2 = createns(X)
Mdl2 = 
  KDTreeSearcher with properties:

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

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

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

指数が 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 には、それぞれが観測値 (インスタンスまたは事例) に対応する n 個の行と、それぞれが予測子 (特徴) に対応する K 個の列が含まれます。

データ型: single | double

名前と値の引数

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

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

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

すべての探索モデル

すべて折りたたむ

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

  • "kdtree"creatensKd 木アルゴリズムを使用して 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

以後のクエリ点について最近傍を探索するために 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 列のベクトル ZIKX の列数です。

    • X または Y の複数行が含まれている mK 列の行列 ZJm は正の整数です。

  • m 行 1 列の距離のベクトル D2 を返す。D2(j) は、観測値 ZIZJ(j,:) の間の距離です。

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

例: 'Distance','minkowski'

データ型: char | string | function_handle

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

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

例: P=3

データ型: single | double

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

すべて折りたたむ

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

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

例: Cov=eye(3)

データ型: single | double

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

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

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

データ型: single | double

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

すべて折りたたむ

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

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

例: 'BucketSize',10

データ型: single | double

Hierarchical Navigable Small Worlds アルゴリズム

すべて折りたたむ

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

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

データ型: double

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

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

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

  1. 非常に精度が高い (厳密な探索に近い) 探索結果が得られる十分に大きい値を指定します。

  2. 精度が適度に良好な範囲 (再現率 0.95 ~ 0.99) になるまで、値を小さくしながらクエリのテストを実行します。

データ型: double

出力引数

すべて折りたたむ

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

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

アルゴリズム

すべて折りたたむ

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

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

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

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

方程式の最後の行にある行列 xiTxj"グラム行列" と呼ばれます。正方化と加算によって平方距離を計算する代わりに、グラム行列を計算して使用すると、一連の平方距離の計算は高速になりますが、数値的安定性は少し低くなります。詳細については、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 で導入

すべて展開する