knnsearch
探索モデル オブジェクトを使用して k 最近傍を探索
説明
は、1 つ以上の Idx
= knnsearch(Mdl
,Y
,Name,Value
)Name,Value
ペア引数で指定された追加オプションを使用して、Y
に対して最も近い Mdl.X
内の点のインデックスを返します。たとえば、探索する最近傍の数や、Mdl.Distance
に格納されているものとは異なる距離計量を指定します。また、最も近い距離が同順位の場合に行う処理を指定することもできます。
例
Kd 木と網羅的探索による最近傍の探索
knnsearch
は、ExhaustiveSearcher
または KDTreeSearcher
モデル オブジェクトを受け入れて、クエリ データに対する最近傍を学習データから探索します。ExhaustiveSearcher
モデルは、網羅的探索アルゴリズムを呼び出します。KDTreeSearcher
モデルは、knnsearch
で最近傍の探索に使用される Kd 木を定義します。
フィッシャーのアヤメのデータ セットを読み込みます。クエリ データ用に 5 つの観測値をデータから無作為に抽出します。
load fisheriris rng(1); % For reproducibility n = size(meas,1); idx = randsample(n,5); X = meas(~ismember(1:n,idx),:); % Training data Y = meas(idx,:); % Query data
変数 meas
には 4 つの予測子が含まれています。
既定の 4 次元 Kd 木を成長させます。
MdlKDT = KDTreeSearcher(X)
MdlKDT = KDTreeSearcher with properties: BucketSize: 50 Distance: 'euclidean' DistParameter: [] X: [145x4 double]
MdlKDT
は KDTreeSearcher
モデル オブジェクトです。書き込み可能なプロパティは、ドット表記を使用して変更できます。
網羅的最近傍探索モデルを準備します。
MdlES = ExhaustiveSearcher(X)
MdlES = ExhaustiveSearcher with properties: Distance: 'euclidean' DistParameter: [] X: [145x4 double]
MdlKDT
は ExhaustiveSearcher
モデル オブジェクトです。このオブジェクトには、最近傍の探索に使用する距離計量などのオプションが格納されています。
Kd 木の成長と網羅的最近傍探索モデルの準備には、createns
も使用できます。
各クエリ観測値に対応する最近傍のインデックスを学習データから探索します。既定の設定を使用して、両方のタイプの探索を実行します。既定の設定では、各クエリ観測値について探索する近傍の数は 1
です。
IdxKDT = knnsearch(MdlKDT,Y); IdxES = knnsearch(MdlES,Y); [IdxKDT IdxES]
ans = 5×2
17 17
6 6
1 1
89 89
124 124
この場合、探索の結果は同じです。
ミンコフスキー距離によるクエリ データの最近傍の探索
関数 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: [145x4 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,:)
になります。
最近傍探索に同順位を含める
フィッシャーのアヤメのデータ セットを読み込みます。
load fisheriris
クエリ セットとして使用するため、5 つのアヤメのデータを無作為に予測子データから抽出します。
rng(4); % 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,:);
学習データを使用して 4 次元の Kd 木を成長させます。最近傍の探索にミンコフスキー距離を指定します。
Mdl = KDTreeSearcher(X);
Mdl
は KDTreeSearcher
モデル オブジェクトです。既定の設定では、最近傍を探索するための距離計量はユークリッド尺度です。
求める学習データ (X
) のインデックスは、クエリ データ (Y
) の各点における 7 つの最近傍です。
[Idx,D] = knnsearch(Mdl,Y,'K',7,'IncludeTies',true);
Idx
と D
は、5 つのベクトルが含まれている cell 配列です。各ベクトルには少なくとも 7 つの要素が含まれています。
Idx
に含まれているベクトルの長さを表示します。
cellfun('length',Idx)
ans = 5×1
8
7
7
7
7
セル 1
には長さが k = 7 より大きいベクトルが含まれているので、クエリ観測値 1 (Y(1,:)
) は X
内の観測値の少なくとも 2 つと同じ距離にあります。
Y(1,:)
に対する最近傍のインデックスとその距離を表示します。
nn5 = Idx{1}
nn5 = 1×8
91 98 67 69 71 93 88 95
nn5d = D{1}
nn5d = 1×8
0.1414 0.2646 0.2828 0.3000 0.3464 0.3742 0.3873 0.3873
学習観測値 88
および 95
は、クエリ観測値 1
から 0.3873 cm 離れています。
異なる距離計量を使用した k 最近傍の比較
異なる距離計量を使用して 2 つの KDTreeSearcher
モデルに学習をさせ、この 2 つのモデルでクエリ データの k 最近傍を比較します。
フィッシャーのアヤメのデータ セットを読み込みます。花弁の測定値を予測子と考えます。
load fisheriris X = meas(:,3:4); % Predictors Y = species; % Response
予測子を使用して KDTreeSearcher
モデル オブジェクトに学習をさせます。指数が 5 のミンコフスキー距離を指定します。
KDTreeMdl = KDTreeSearcher(X,'Distance','minkowski','P',5)
KDTreeMdl = KDTreeSearcher with properties: BucketSize: 50 Distance: 'minkowski' DistParameter: 5 X: [150x2 double]
最初にミンコフスキー距離計量を、次にチェビシェフ距離計量を使用して、クエリ点 (newpoint
) に対する 10 個の最近傍を X
から探索します。クエリ点は、モデルの学習に使用したデータと列次元が同じでなければなりません。
newpoint = [5 1.45]; [IdxMk,DMk] = knnsearch(KDTreeMdl,newpoint,'k',10); [IdxCb,DCb] = knnsearch(KDTreeMdl,newpoint,'k',10,'Distance','chebychev');
IdxMk
と IdxCb
はそれぞれ、ミンコフスキー距離計量とチェビシェフ距離計量を使用した newpoint
に対する最近傍に対応する X
の行インデックスが格納されている 1 行 10 列の行列です。要素 (1,1) は最も近い要素、要素 (1,2) は次に近い要素です。以後についても同様です。
学習データ、クエリ点および最近傍をプロットします。
figure; gscatter(X(:,1),X(:,2),Y); title('Fisher''s Iris Data -- Nearest Neighbors'); xlabel('Petal length (cm)'); ylabel('Petal width (cm)'); hold on plot(newpoint(1),newpoint(2),'kx','MarkerSize',10,'LineWidth',2); % Query point plot(X(IdxMk,1),X(IdxMk,2),'o','Color',[.5 .5 .5],'MarkerSize',10); % Minkowski nearest neighbors plot(X(IdxCb,1),X(IdxCb,2),'p','Color',[.5 .5 .5],'MarkerSize',10); % Chebychev nearest neighbors legend('setosa','versicolor','virginica','query point',... 'minkowski','chebychev','Location','Best');
目的の点を拡大します。
h = gca; % Get current axis handle. h.XLim = [4.5 5.5]; h.YLim = [1 2]; axis square;
いくつかの観測値は等しいので、プロットで識別できる最近傍は 8 つだけです。
大規模データに対する HNSW の速度と精度
大規模なデータ セットを作成し、1000 個のクエリ点についての HNSW 探索モデルの速度と網羅的探索モデルの速度を比較します。
データを作成します。
rng default % For reproducibility A = diag(1:100); B = randn(100,10); K = kron(A,B); ss = size(K)
ss = 1×2
10000 1000
データ K
の行数は 1e4
、列数は 1e3
になります。
データ K
から HNSW 探索モデル オブジェクト h
を作成します。
tic; h = hnswSearcher(K); chnsw = toc
chnsw = 10.6544
1000 個のランダムなクエリ点を作成します。特徴量 (列) は 1000 個です。5 つの最近傍を探索するように指定します。
Y = randn(1000, 1000); tic; [idx, D] = knnsearch(h,Y,K=5); thnsw = toc
thnsw = 0.0797
データ K から網羅的探索モデル オブジェクト e
を作成します。
tic e = ExhaustiveSearcher(K); ces = toc
ces = 0.0021
網羅的探索モデルの作成は HNSW 探索モデルの作成よりもはるかに高速になります。
e
を使用した探索時間を測定し、その結果を HNSW 探索モデル h
を使用した時間と比較します。
tic; [idx0, D0] = knnsearch(e,Y,K=5); tes = toc
tes = 1.4841
このケースでは、HNSW 探索モデルの方が網羅的探索モデルよりも計算が約 20 倍高速になります。
HNSW 探索の結果に、網羅的探索の結果と何らかの点で異なる結果がいくつあるかを調べます。
v = abs(idx - idx0); % Count any difference in the five found entries vv = sum(v,2); % vv = 0 means no difference nz = nnz(vv) % Out of 1000 rows how many differ at all?
nz = 118
ここでは、HNSW 探索の 1000 個の結果のうち 118 個が網羅的探索の結果と異なっています。
既定以外のパラメーターで学習させることで HNSW 探索モデルの精度を改善できるか試します。具体的には、MaxNumLinksPerNode
と TrainSetSize
の値を大きくします。これらの設定は、学習と最近傍探索の速度に影響します。
tic; h2 = hnswSearcher(K,MaxNumLinksPerNode=48,TrainSetSize=2000); chnsw2 = toc
chnsw2 = 78.4836
これらのパラメーターを使用すると、探索モデルの学習に約 7 倍の時間がかかります。
tic; [idx2, D2] = knnsearch(h2,Y,K=5); thnsw2 = toc
thnsw2 = 0.1049
HNSW を使用した最近傍探索の速度は前より低下しますが、それでも網羅的探索より 10 倍以上高速です。
v = abs(idx2 - idx0); vv = sum(v,2); nz = nnz(vv)
nz = 57
低速になるものの精度が高まる HNSW 探索で、厳密な結果と何らかの点で異なる結果は 1000 個のうち 57 個だけです。時間測定の結果を table にまとめます。
timet = table([chnsw;ces;chnsw2],[thnsw;tes;thnsw2],'RowNames',["HNSW";"Exhaustive";"HNSW2"],'VariableNames',["Creation" "Search"])
timet=3×2 table
Creation Search
_________ ________
HNSW 10.654 0.079741
Exhaustive 0.0021304 1.4841
HNSW2 78.484 0.10492
入力引数
Mdl
— 最近傍探索モデル
ExhaustiveSearcher
モデル オブジェクト | KDTreeSearcher
モデル オブジェクト | hnswSearcher
モデル オブジェクト
最近傍探索モデル。ExhaustiveSearcher
、KDTreeSearcher
、または hnswSearcher
モデル オブジェクトとして指定します。
Mdl
が ExhaustiveSearcher
モデルの場合、knnsearch
は網羅的探索を使用して最近傍を探索します。Mdl
が KDTreeSearcher
モデルの場合、knnsearch
は成長した Kd 木を使用して最近傍を探索します。Mdl
が hnswSearcher
モデルの場合、knnsearch
は Hierarchical Navigable Small Worlds 近似最近傍探索アルゴリズムを使用します。詳細については、k 最近傍探索および半径探索を参照してください。
Y
— クエリ データ
数値行列
クエリ データ。数値行列を指定します。
Y
は、m 行 K 列の行列です。Y
の各行は観測値 (事例) に、各列は予測子 (変数または特徴量) に対応します。Y
の列数は、Mdl.X
に格納されている学習データの列数と同じでなければなりません。
データ型: single
| double
名前と値の引数
オプションの引数のペアを Name1=Value1,...,NameN=ValueN
として指定します。ここで Name
は引数名、Value
は対応する値です。名前と値の引数は他の引数の後ろにする必要がありますが、ペアの順序は関係ありません。
R2021a より前では、名前と値をそれぞれコンマを使って区切り、Name
を引用符で囲みます。
例: 'K',2,'Distance','minkowski'
は、Y
の各点に対する 2 つの最近傍を Mdl.X
から探索することと、ミンコフスキー距離計量を使用することを指定します。
Distance
— 距離計量
Mdl.Distance
(既定値) | 'cityblock'
| 'euclidean'
| 'mahalanobis'
| 'minkowski'
| 'seuclidean'
| 関数ハンドル | ...
クエリ観測値に対する学習データの近傍を求めるために使用する距離計量。次の表の値のいずれか、または関数ハンドルとして指定します。
すべてのタイプの最近傍探索モデルについて、knnsearch
は次の距離計量をサポートします。
値 | 説明 |
---|---|
'chebychev' | チェビシェフ距離 (最大座標差) |
'cityblock' | 市街地距離 |
'euclidean' | ユークリッド距離 |
'minkowski' | ミンコフスキー距離。既定の指数は 2 です。別の指数を指定するには、名前と値の引数 'P' を使用します。 |
Mdl
が ExhaustiveSearcher
モデル オブジェクトである場合、knnsearch
は次の距離計量もサポートします。
値 | 説明 |
---|---|
'correlation' | 1 から、観測値間の標本線形相関を減算 (値の系列として処理) |
'cosine' | (行ベクトルとして扱われる) 観測値間の夾角の余弦を 1 から減算 |
'fasteuclidean' | 予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算されるユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。この距離計量は、NSMethod が 'exhaustive' の場合にのみ使用できます。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。 |
'fastseuclidean' | 予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算される標準化されたユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。この距離計量は、NSMethod が 'exhaustive' の場合にのみ使用できます。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。 |
'hamming' | ハミング距離 (異なる座標の比率) |
'jaccard' | 1 からジャカード係数 (異なる非ゼロ座標の比率) を減算 |
'mahalanobis' | 正定値共分散行列を使用して計算されるマハラノビス距離。共分散行列の値を変更するには、名前と値の引数 'Cov' を使用します。 |
'seuclidean' | 標準化されたユークリッド距離。X の行とクエリ行列 Y の行の間の各座標差は、X から算出される標準偏差の対応する要素で除算することによりスケーリングされます。別のスケーリングを指定するには、名前と値の引数 'Scale' を使用します。 |
'spearman' | 1 から観測値間の標本スピアマン順位相関係数を減算 (値の系列として処理) |
Mdl
が hnswSearcher
モデル オブジェクトの場合、knnsearch
は ExhaustiveSearcher
の表にある距離を fast
から始まる "fasteuclidean"
と "fastseuclidean"
を除いてすべてサポートします。
Mdl
が ExhaustiveSearcher
モデル オブジェクトである場合、@
を使用してカスタム距離計量の関数ハンドル (たとえば @distfun
) を指定することもできます。カスタム距離関数は、次のようになっていなければなりません。
function D2 = distfun(ZI,ZJ)
という形式になっている。次の引数を受け入れる。
Mdl.X
またはY
の 1 行が含まれている 1 行 K 列のベクトルZI
。K はMdl.X
の列数です。Mdl.X
またはY
の複数行が含まれている m 行 K 列の行列ZJ
。m は正の整数です。
m 行 1 列の距離のベクトル
D2
を返す。D2(
は、観測値j
)ZI
とZJ(
の間の距離です。j
,:)
詳細は、距離計量を参照してください。
例: 'Distance','minkowski'
データ型: char
| string
| function_handle
IncludeTies
— すべての最近傍を含むというフラグ
false
(0
) (既定値) | true
(1
)
クエリ観測値から同じ距離にある複数の最近傍を含めるかどうかのフラグ。'IncludeTies'
と false
(0
) または true
(1
) をコンマ区切りのペアとして指定します。
IncludeTies
が true
の場合、次のようになります。
IncludeTies
が false
の場合、knnsearch
はクエリ点から同じ距離にある観測値の中でインデックスが最も小さいものを選択します。
例: 'IncludeTies',true
K
— 最近傍の個数
1
(既定値) | 正の整数
各クエリ観測値について学習データで探索する最近傍の数。'K'
と正の整数をコンマ区切りのペアとして指定します。
例: 'K',2
データ型: single
| double
P
— ミンコフスキー距離計量の指数
2
(既定値) | 正のスカラー
ミンコフスキー距離計量の指数。正のスカラーとして指定します。この引数は、Distance
が "minkowski"
である場合のみ有効です。
P
の値により、モデル オブジェクトの DistParameter
プロパティの値が設定されます。
例: P=3
データ型: single
| double
SortIndices
— 返されたインデックスを距離に従って並べ替えるためのフラグ
true
(1
) (既定値) | false
(0
)
返されたインデックスを距離に従って並べ替えるためのフラグ。'SortIndices'
と true
(1
) または false
(0
) から構成されるコンマ区切りのペアとして指定します。
以下の場合は、SortIndices
を false
に設定して速度を向上させることができます。
X
内に多数の最近傍がある多数の観測値がY
に含まれている。Mdl
はKDTreeSearcher
モデル オブジェクトです。IncludeTies
がfalse
。
この場合、knnsearch
が返す最近傍のインデックスに特定の順序はありません。SortIndices
が true
である場合、最近傍のインデックスは距離の昇順で並べ替えられます。
既定では、SortIndices
は true
です。Mdl
が ExhaustiveSearcher
モデル オブジェクトであるか、IncludeTies
が true
である場合、常にインデックスが並べ替えられます。
例: 'SortIndices',false
データ型: logical
Cov
— マハラノビス距離計量の共分散行列
cov(Mdl.X,'omitrows')
(既定値) | 正定値行列
マハラノビス距離計量の共分散行列。'Cov'
と正定値行列をコンマ区切りのペアとして指定します。Cov
は K 行 K 列の行列で、K は Mdl.X
の列数です。Cov
を指定して '
Distance
','mahalanobis'
を指定しなかった場合、knnsearch
はエラー メッセージを返します。
例: 'Cov',eye(3)
データ型: single
| double
Scale
— 標準化されたユークリッド距離計量のスケール パラメーター値
std(Mdl.X,'omitnan')
(既定値) | 非負の数値ベクトル
標準化されたユークリッド距離計量のスケール パラメーター値。'Scale'
と非負の数値ベクトルから構成されるコンマ区切りのペアとして指定します。Scale
の長さは K です。K は Mdl.X
の列数です。
学習データとクエリ データの間の距離は、対応する Scale
の要素を使用してスケーリングされます。Scale
を指定して '
Distance
','seuclidean'
を指定しなかった場合、knnsearch
はエラー メッセージを返します。
例: 'Scale',quantile(Mdl.X,0.75) - quantile(Mdl.X,0.25)
データ型: single
| double
SearchSetSize
— 最近傍候補リストのサイズ
max(10,K)
(既定値) | K
から N
までの正の整数
探索プロセスでの単一のクエリ点に対する最近傍候補リストのサイズ。K
から N
までの正の整数として指定します。値が大きいほど探索が詳細になり、真の最近傍が見つかる可能性が高まりますが、探索にかかる時間は長くなります。SearchSetSize
は、データに含まれる特徴量の数 K
(Mdl.X
の列数) 以上でなければならず、学習データの行数 N
(Mdl.X
の行数) 以下でなければなりません。
例: SearchSetSize=15
データ型: double
メモ
'
Distance
'
、'
Cov
'
、'
P
'
または '
Scale
'
を指定した場合、Mdl.Distance
と Mdl.DistParameter
の値は変更されません。
出力引数
Idx
— 最近傍の学習データのインデックス
数値行列 | 数値ベクトルの cell 配列
最近傍の学習データのインデックス。数値行列または数値ベクトルの cell 配列として返されます。
IncludeTies
(既定はfalse
) を指定しなかった場合、Idx
は m 行 k 列の数値行列になります。m はY
の行数、k は名前と値のペアの引数'K'
で指定された探索対象の最近傍の個数です。Idx(j,i)
は、Mdl.X(Idx(j,i),:)
がクエリ観測値Y(j,:)
に対して最も近いMdl.X
内の k 個の観測値の 1 つであることを示します。'IncludeTies',true
を指定した場合、Idx
は m 行1
列の cell 配列になり、クエリ観測値Y(j,:)
に最も近いMdl.X
内の観測値のインデックスが少なくとも k 個含まれているベクトルがセルj
(Idx{j}
) に格納されます。
SortIndices
が true
である場合、knnsearch
はインデックスを距離の昇順で並べ替えます。
D
— 最近傍の距離
数値行列 | 数値ベクトルの cell 配列
クエリ データに対する最近傍の距離。数値行列または数値ベクトルの cell 配列として返されます。
IncludeTies
(既定はfalse
) を指定しなかった場合、D
は m 行 k 列の数値行列になります。m はY
の行数、k は名前と値のペアの引数'K'
で指定された探索対象の最近傍の個数です。D(j,i)
は、距離計量によるMdl.X(Idx(j,i),:)
とクエリ観測値Y(j,:)
の間の距離です。'IncludeTies',true
を指定した場合、D
は m 行1
列の cell 配列になり、クエリ観測値Y(j,:)
に最も近いMdl.X
内の観測値の距離が少なくとも k 個含まれているベクトルがセルj
(D{j}
) に格納されます。
SortIndices
が true
である場合、knnsearch
は距離を昇順で並べ替えます。
ヒント
knnsearch
は、Y
の各点についての k 最近傍である k (正の整数) 個の点を Mdl.X
内で探索します。これに対して rangesearch
は、Y
の各点に対する距離が r
(正のスカラー) 以内であるすべての点を Mdl.X
内で探索します。
アルゴリズム
高速ユークリッド距離アルゴリズム
Distance
引数の fast
から始まる値 ('fasteuclidean'
や 'fastseuclidean'
など) で使用されるアルゴリズムでは、計算時間の短縮のために追加のメモリを使用してユークリッド距離が計算されます。このアルゴリズムは、Albanie の[1]などで "ユークリッド距離行列トリック" として提唱されているものです。内部テストでは、このアルゴリズムによって予測子の数が 10 個以上の場合に時間の短縮になることが確認されています。'fast'
から始まるアルゴリズムでは、スパース データはサポートされません。
このアルゴリズムでは、xi と xj のすべての点間の距離の行列 D を求めるために (xi のそれぞれに n 個の変数を格納)、次の方程式の最後の行を使用して距離を計算します。
方程式の最後の行にある行列 は "グラム行列" と呼ばれます。正方化と加算によって平方距離を計算する代わりに、グラム行列を計算して使用すると、一連の平方距離の計算は高速になりますが、数値的安定性は少し低くなります。詳細については、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.
代替機能
knnsearch
は、ExhaustiveSearcher
、KDTreeSearcher
、またはhnswSearcher
モデル オブジェクトとクエリ データを必要とするオブジェクト関数です。同じ条件下の網羅的探索または Kd 木探索で、オブジェクト関数knnsearch
は、名前と値の引数NSMethod="exhaustive"
またはNSMethod="kdtree"
をそれぞれ指定した関数knnsearch
と同じ結果を返します。関数knnsearch
にはhnswSearcher
モデルを指定するための同様の名前と値の引数はないことに注意してください。k 最近傍分類については、
fitcknn
とClassificationKNN
を参照してください。
参照
[1] Friedman, J. H., Bentley, J., and Finkel, R. A. (1977). “An Algorithm for Finding Best Matches in Logarithmic Expected Time.” ACM Transactions on Mathematical Software Vol. 3, Issue 3, Sept. 1977, pp. 209–226.
[2] Malkov, Yu. A., and D. A. Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. Available at https://arxiv.org/abs/1603.09320.
拡張機能
C/C++ コード生成
MATLAB® Coder™ を使用して C および C++ コードを生成します。
使用上の注意事項および制限事項:
次の表は、
knnsearch
の引数に関する注意です。この表に含まれていない引数は、完全にサポートされています。引数 注意と制限 Mdl
Mdl
がhnswSearcher
オブジェクトの場合、コード生成にMdl
は使用できません。コード生成で
Mdl
を使用する方法は 2 つあります。たとえば、最近傍探索モデルのコード生成を参照してください。saveLearnerForCoder
、loadLearnerForCoder
およびcodegen
(MATLAB Coder) を使用して、関数knnsearch
のコードを生成します。saveLearnerForCoder
を使用して、学習済みモデルを保存します。loadLearnerForCoder
を使用して保存済みモデルを読み込んで関数knnsearch
を呼び出す、エントリポイント関数を定義します。次に、codegen
を使用して、エントリポイント関数のコードを生成します。codegen
(MATLAB Coder) の-args
の値にcoder.Constant(Mdl)
を含めます。
Mdl
がKDTreeSearcher
オブジェクトであり、コード生成のビルド タイプが 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) を参照してください。
'Distance'
カスタム距離関数にすることはできません。
コンパイル時の定数でなければなりません。この値は、生成されたコード内では変更できません。
knnsearch
では、高速ユークリッド距離計算、つまり名前がfast
から始まる距離計量 ('fasteuclidean'
など) のコード生成はサポートされていません。
'IncludeTies'
コンパイル時の定数でなければなりません。この値は、生成されたコード内では変更できません。
'SortIndices'
サポートされません。出力引数は常に並べ替えられます。 名前と値のペアの引数 名前と値の引数に含まれる名前はコンパイル時の定数でなければなりません。たとえば、生成されたコードでミンコフスキー距離についてユーザー定義の指数を使用可能にするには、
{coder.Constant('Distance'),coder.Constant('Minkowski'),coder.Constant('P'),0}
をcodegen
(MATLAB Coder) の-args
の値に含めます。Idx
'IncludeTies'
にtrue
を指定した場合、数値精度のために、生成コード内の同順位の距離の並び順が MATLAB の順序と異なる可能性があります。knnsearch
は、生成されたスタンドアロン C/C++ コードにおいて、整数型 (int32
) のインデックスを返します。そのため、関数は、単精度の入力を使用する場合、厳密な単精度のサポートを可能にします。MEX コード生成では、関数は依然として MATLAB の動作に一致する倍精度のインデックスを返します。R2020a より前:
knnsearch
は、生成されたスタンドアロン C/C++ コードにおいて、倍精度のインデックスを返します。
詳細については、コード生成の紹介と最近傍探索モデルのコード生成を参照してください。
バージョン履歴
R2010a で導入R2024a: hnswSearcher
オブジェクトを使用した近似探索
hnswSearcher
モデル オブジェクトを使用して近似最近傍を探索します。hnswSearcher
オブジェクトは、ExhaustiveSearcher
オブジェクトや KDTreeSearcher
オブジェクトよりも作成に時間がかかりますが、近似最近傍の計算は高速になります。hnswSearcher
オブジェクトを作成するには、関数 hnswSearcher
を使用するか、NSMethod="hnsw"
を指定して createns
を使用します。詳細については、hnswSearcher
を参照してください。
R2023a: キャッシュを使用した高速ユークリッド距離
'fasteuclidean'
および 'fastseuclidean'
の距離計量では、キャッシュと別のアルゴリズムを使用してユークリッド距離の計算が高速化されます (アルゴリズムを参照)。
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:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
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
- United Kingdom (English)