KDTreeSearcher

Kd 木最近傍探索モデルを作成

説明

KDTreeSearcher モデル オブジェクトには、Kd 木アルゴリズムを使用した最近傍探索の結果が格納されます。結果は、学習データ、距離計量とそのパラメーター、および各葉ノードにおけるデータ点の最大数 (つまりバケット サイズ) です。Kd 木アルゴリズムでは、K 次元空間で n 個の点を再帰的に二分木に分割することにより、n 行 K 列のデータ セットを分割します。

KDTreeSearcher モデル オブジェクトの作成後、knnsearch による最近傍探索または rangesearch による半径探索を実行して、格納されている木からクエリ データに対するすべての近傍点を探索できます。K が小さく (K ≤ 10)、学習セットとクエリ セットがスパースではなく、学習セットとクエリ セットに多数の観測値が含まれている場合、Kd 木アルゴリズムは網羅的探索アルゴリズムより効率的です。

作成

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

構文

Mdl = KDTreeSearcher(X)

Mdl = KDTreeSearcher(X,Name,Value)

説明

Mdl = KDTreeSearcher(X) は、n 行 K 列の学習データの数値行列 (X) を使用して、既定の Kd 木 (Mdl) を成長させます。

Mdl = KDTreeSearcher(X,Name,Value) では、1 つ以上の名前と値のペアの引数を使用して追加オプションを指定します。各葉ノードにおけるデータ点の最大数 (つまりバケット サイズ) および距離計量の指定と、距離計量パラメーター (DistParameter) プロパティの設定を行うことができます。たとえば KDTreeSearcher(X,'Distance','minkowski','BucketSize',10) は、最近傍を探索するときにミンコフスキー距離を使用し、バケット サイズに 10 を使用するよう指定します。DistParameter を指定するには、名前と値のペアの引数 P を使用します。

入力引数

X — 学習データ

数値行列

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

データ型: single | double

名前と値の引数

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

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

例: 'Distance','minkowski','P',3,'BucketSize',10 は、最近傍を探索するときに、ミンコフスキー距離、ミンコフスキー距離計量の指数として 3、バケット サイズとして 10 を使用するよう指定します。

Distance — 距離計量

'euclidean' (既定値) | 'chebychev' | 'cityblock' | 'minkowski'

以後のクエリ点について最近傍を探索するために knnsearch または rangesearch を呼び出すときに使用する距離計量。'Distance' と次のいずれかの値から構成されるコンマ区切りのペアとして指定します。

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

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

KDTreeSearcher モデル オブジェクトの作成には距離計量が使用されないので、オブジェクトの作成後にドット表記を使用して距離計量を変更できます。

例: 'Distance','minkowski'

P — ミンコフスキー距離計量の指数

2 (既定値) | 正のスカラー

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

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

例: P=3

データ型: single | double

BucketSize — 各葉ノードの最大データ点数

50 (既定値) | 正の整数

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

例: 'BucketSize',10

データ型: single | double

プロパティ

X — 学習データ

読み取り専用: 数値行列

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

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

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

データ型: single | double

Distance — 距離計量

'euclidean' | 'chebychev' | 'cityblock' | 'minkowski'

以後のクエリ点について最近傍を探索するために knnsearch または rangesearch を呼び出すときに使用する距離計量。'chebychev'、'cityblock'、'euclidean' または 'minkowski' を指定します。

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

距離計量は KDTreeSearcher モデル オブジェクトの作成に使用されないので、ドット表記を使用して変更できます。

DistParameter — 距離計量のパラメーター値

[] | 正のスカラー

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

Distance が 'minkowski' である場合、DistParameter はミンコフスキー距離の式における指数です。それ以外の場合、DistParameter は [] になります。これは、指定された距離計量の式にパラメーターがないことを示します。

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

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

データ型: single | double

BucketSize — 各葉ノードの最大データ点数

読み取り専用: 正の整数

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

Kd 木の各葉ノードにおけるデータ点の最大数。正の整数を指定します。

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

データ型: single | double

オブジェクト関数

knnsearch	探索モデル オブジェクトを使用して k 最近傍を探索
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: [150×4 double]

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

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

Mdl2 = createns(X)

Mdl2 = 
  KDTreeSearcher with properties:

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

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

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

最近傍探索に使用するミンコフスキー距離の指定

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

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

createns と学習データを使用して 2 次元の Kd 木を成長させます。ミンコフスキー距離計量を指定します。

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

Mdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 2
                X: [150×2 double]

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

ドット表記を使用して Mdl のプロパティにアクセスします。たとえば、Mdl.DistParameter を使用してミンコフスキー距離指数にアクセスします。

Mdl.DistParameter

ans = 
2

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

• 最近傍のインデックスと距離を求めるための knnsearch

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

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

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

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

load fisheriris
X = meas;

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

Mdl = KDTreeSearcher(X)

Mdl = 
  KDTreeSearcher with properties:

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

近傍探索モデルでミンコフスキー計量を使用して学習データとクエリ データの間の距離を計算するように指定します。

Mdl.Distance = 'minkowski'

Mdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 2
                X: [150×4 double]

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

ミンコフスキー距離によるクエリ データの最近傍の探索

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

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

load fisheriris

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

rng(1)                      % For reproducibility
n = size(meas,1);           % Sample size
qIdx = randsample(n,5);     % Indices of query data
tIdx = ~ismember(1:n,qIdx); % Indices of training data
Q = meas(qIdx,:);
X = meas(tIdx,:);

学習データを使用して 4 次元の Kd 木を成長させます。最近傍の探索にミンコフスキー距離を指定します。

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

Mdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 2
                X: [145×4 double]

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

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

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

IdxNN = 5×2

    17     4
     6     2
     1    12
    89    66
   124   100

IdxNN の各行はクエリ データの観測値に、列の順序は距離の昇順で並べ替えた最近傍の順序に対応しています。たとえば、ミンコフスキー距離に基づくと、Q(3,:) の 2 番目の最近傍は X(12,:) になります。

拡張機能

C/C++ コード生成

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

使用上の注意事項および制限事項:関数 knnsearch および rangesearch はコード生成をサポートします。

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

バージョン履歴

R2010a で導入

参考

ExhaustiveSearcher | createns | knnsearch | rangesearch | hnswSearcher

トピック

• k 最近傍探索および半径探索
• 距離計量