knnsearch
探索モデル オブジェクトを使用して k 最近傍を探索
説明
Idx = knnsearch(Mdl,Y,Name,Value)Name,Value ペア引数で指定された追加オプションを使用して、Y に対して最も近い Mdl.X 内の点のインデックスを返します。たとえば、探索する最近傍の数や、Mdl.Distance に格納されているものとは異なる距離計量を指定します。また、最も近い距離が同順位の場合に行う処理を指定することもできます。
例
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: [145×4 double]
MdlKDT は KDTreeSearcher モデル オブジェクトです。書き込み可能なプロパティは、ドット表記を使用して変更できます。
網羅的最近傍探索モデルを準備します。
MdlES = ExhaustiveSearcher(X)
MdlES =
ExhaustiveSearcher with properties:
Distance: 'euclidean'
DistParameter: []
X: [145×4 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: [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,:) になります。
フィッシャーのアヤメのデータ セットを読み込みます。
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 離れています。
異なる距離計量を使用して 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: [150×2 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 つだけです。
大規模なデータ セットを作成し、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
入力引数
名前と値の引数
出力引数
ヒント
knnsearch は、Y の各点についての k 最近傍である k (正の整数) 個の点を Mdl.X 内で探索します。これに対して rangesearch は、Y の各点に対する距離が r (正のスカラー) 以内であるすべての点を Mdl.X 内で探索します。
アルゴリズム
代替機能
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.
