knnsearch
入力データを使用して k 最近傍を探索
説明
Idx = knnsearch(X,Y,Name,Value)Idx を返します。たとえば、探索する最近傍の個数や、探索で使用する距離計量を指定できます。
例
年齢と体重に従って、Y 内の患者に最も似ている患者を hospital データ セット内で探索します。
hospital データ セットを読み込みます。
load hospital; X = [hospital.Age hospital.Weight]; Y = [20 162; 30 169; 40 168; 50 170; 60 171]; % New patients
X と Y の間で knnsearch を実行して、最近傍のインデックスを求めます。
Idx = knnsearch(X,Y);
Y 内の患者に年齢と体重が最も近い患者を X 内で探索します。
X(Idx,:)
ans = 5×2
25 171
25 171
39 164
49 170
50 172
最初にミンコフスキー距離計量を、次にチェビシェフ距離計量を使用して、Y 内の各点に対する 10 個の最近傍を X 内で探索します。
フィッシャーのアヤメのデータ セットを読み込みます。
load fisheriris X = meas(:,3:4); % Measurements of original flowers Y = [5 1.45;6 2;2.75 .75]; % New flower data
ミンコフスキー距離計量とチェビシェフ距離計量を使用して、X とクエリ点 Y の間で knnsearch を実行します。
[mIdx,mD] = knnsearch(X,Y,'K',10,'Distance','minkowski','P',5); [cIdx,cD] = knnsearch(X,Y,'K',10,'Distance','chebychev');
2 つの最近傍探索の結果を可視化します。学習データをプロットします。マーカー X でクエリ点をプロットします。円を使用してミンコフスキー最近傍を表します。星形五角形を使用してチェビシェフ最近傍を表します。
gscatter(X(:,1),X(:,2),species) line(Y(:,1),Y(:,2),'Marker','x','Color','k',... 'Markersize',10,'Linewidth',2,'Linestyle','none') line(X(mIdx,1),X(mIdx,2),'Color',[.5 .5 .5],'Marker','o',... 'Linestyle','none','Markersize',10) line(X(cIdx,1),X(cIdx,2),'Color',[.5 .5 .5],'Marker','p',... 'Linestyle','none','Markersize',10) legend('setosa','versicolor','virginica','query point',... 'minkowski','chebychev','Location','best')
2 つの大規模な点の行列を作成し、既定の "euclidean" 距離計量を使用した knnsearch の所要時間を測定します。
rng default % For reproducibility N = 10000; X = randn(N,1000); Y = randn(N,1000); Idx = knnsearch(X,Y); % Warm up function for more reliable timing information tic Idx = knnsearch(X,Y); standard = toc
standard = 7.7757
次に、"fasteuclidean" 距離計量を使用した knnsearch の所要時間を測定します。キャッシュ サイズは 100 に指定します。
Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100); % Warm up function tic Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100); accelerated = toc
accelerated = 1.1016
計算の高速化によって標準よりも何倍速くなったかを評価します。
standard/accelerated
ans = 7.0583
この例では、高速化したバージョンの方が 3 倍を超える速さになっています。
入力引数
名前と値の引数
出力引数
ヒント
knnsearchは、一定の正の整数 k について、Y内の各点に最も近い k 個の点をX内で探索します。Y内の各点から一定距離以内にあるすべての点をX内で探索するには、rangesearchを使用します。knnsearchは、探索オブジェクトを保存しません。探索オブジェクトを作成するには、creatensを使用します。
アルゴリズム
代替機能
関数 knnsearch の名前と値のペアの引数 'NSMethod' を適切な値 (網羅的探索アルゴリズムの場合は 'exhaustive'、Kd 木アルゴリズムの場合は 'kdtree') に設定した場合、オブジェクト関数 knnsearch を使用して距離探索を実行することにより得られる結果と同じ探索結果になります。関数 knnsearch とは異なり、オブジェクト関数 knnsearch では ExhaustiveSearcher または KDTreeSearcher モデル オブジェクトが必要です。
Simulink ブロック
Simulink® に k 最近傍探索を統合するには、Statistics and Machine Learning Toolbox™ ライブラリにある KNN Search ブロックを使用するか、MATLAB Function ブロックを関数 knnsearch と共に使用します。たとえば、MATLAB Function ブロックの使用によるクラス ラベルの予測を参照してください。
使用するアプローチを判断する際は、以下を考慮してください。
Statistics and Machine Learning Toolbox ライブラリ ブロックを使用する場合、固定小数点ツール (Fixed-Point Designer)を使用して浮動小数点モデルを固定小数点に変換できます。
MATLAB Function ブロックを関数
knnsearchと共に使用する場合は、可変サイズの配列に対するサポートを有効にしなければなりません。
参照
[1] Albanie, Samuel. Euclidean Distance Matrix Trick. June, 2019. Available at https://samuelalbanie.com/files/Euclidean_distance_trick.pdf.
[2] Friedman, J. H., J. Bentley, and R. A. Finkel. “An Algorithm for Finding Best Matches in Logarithmic Expected Time.” ACM Transactions on Mathematical Software 3, no. 3 (1977): 209–226.
