Main Content

このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

最近傍点を使用した分類

ペアワイズ距離計量

学習データセット内の点に対する距離に基づいてクエリ点を分類すると、新しい点を簡単かつ有効に分類できます。さまざまな計量を使用して、距離を調べることができます。pdist2 を使用して、データセットとクエリ点間の距離を検出します。

距離計量

mx 行 n 列のデータ行列 X (mx 個の 1 行 n 列の行ベクトル x1、x2、...、xmx として扱われる) と、my 行 n 列のデータ行列 Y (my 個の 1 行 n 列の行ベクトル y1、y2、...、ymy として扱われる) が与えられた場合、ベクトル xs と yt の間のさまざまな距離は次のように定義されます。

  • ユークリッド距離

    dst2=(xsyt)(xsyt).

    ユークリッド距離はミンコフスキー距離の特殊なケース、p = 2 の場合です。

    ユークリッド距離を指定するには、Distance パラメーターを 'euclidean' に設定します。

  • 標準化されたユークリッド距離

    dst2=(xsyt)V1(xsyt),

    ここで、V は j 番目の対角要素が (S(j))2 である n 行 n 列の対角行列です。S は各次元のスケーリング係数のベクトルです。

    標準化されたユークリッド距離を指定するには、Distance パラメーターを 'seuclidean' に設定します。

  • 高速ユークリッド距離はユークリッド距離と同じで、予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算されます。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。スパース データはサポートされません。高速ユークリッド距離アルゴリズムを参照してください。

    高速ユークリッド距離を指定するには、Distance パラメーターを 'fasteuclidean' に設定します。

  • 標準化された高速ユークリッド距離は標準化されたユークリッド距離と同じで、予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算されます。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。スパース データはサポートされません。高速ユークリッド距離アルゴリズムを参照してください。

    標準化された高速ユークリッド距離を指定するには、Distance パラメーターを 'fastseuclidean' に設定します。

  • マハラノビス距離

    dst2=(xsyt)C1(xsyt),

    ここで、C は共分散行列です。

    マハラノビス距離を指定するには、Distance パラメーターを 'mahalanobis' に設定します。

  • 市街地距離

    dst=j=1n|xsjytj|.

    市街地距離はミンコフスキー距離の特殊なケース、p = 1 の場合です。

    市街地距離を指定するには、Distance パラメーターを 'cityblock' に設定します。

  • ミンコフスキー距離

    dst=j=1n|xsjytj|pp.

    p = 1 という特殊なケースでは、ミンコフスキー距離は市街地距離を与えます。p = 2 という特殊なケースでは、ミンコフスキー距離はユークリッド距離を与えます。p = ∞ という特殊なケースでは、ミンコフスキー距離はチェビシェフ距離を与えます。

    ミンコフスキー距離を指定するには、Distance パラメーターを 'minkowski' に設定します。

  • チェビシェフ距離

    dst=maxj{|xsjytj|}.

    チェビシェフ距離はミンコフスキー距離の特殊なケース、p = ∞ の場合です。

    チェビシェフ距離を指定するには、Distance パラメーターを 'chebychev' に設定します。

  • コサイン距離

    dst=(1xsyt(xsxs)(ytyt)).

    コサイン距離を指定するには、Distance パラメーターを 'cosine' に設定します。

  • 相関距離

    dst=1(xsx¯s)(yty¯t)(xsx¯s)(xsx¯s)(yty¯t)(yty¯t),

    ここで

    x¯s=1njxsj

    および

    y¯t=1njytj.

    相関距離を指定するには、Distance パラメーターを 'correlation' に設定します。

  • ハミング距離は、一致しない座標の比率です。

    dst=(#(xsjytj)/n).

    ハミング距離を指定するには、Distance パラメーターを 'hamming' に設定します。

  • Jaccard 距離は、1 からジャカード係数 (異なる非ゼロ座標の比率) を引きます。

    dst=#[(xsjytj)((xsj0)(ytj0))]#[(xsj0)(ytj0)].

    Jaccard 距離を指定するには、Distance パラメーターを 'jaccard' に設定します。

  • スピアマン距離は、1 から一連の値として扱われる観測値間の標本スピアマン順位相関係数を引きます。

    dst=1(rsr¯s)(rtr¯t)(rsr¯s)(rsr¯s)(rtr¯t)(rtr¯t),

    ここで

    • rsj は、tiedrank により計算される、x1j、x2j、...xmx,j から取得された xsj の順位です。

    • rtj は、tiedrank により計算される、y1j、y2j、...ymy,j から取得された ytj の順位です。

    • rs および rt は、xs および yt の座標単位の順位ベクトルです。つまり、rs = (rs1, rs2, ... rsn) および rt = (rt1, rt2, ... rtn) です。

    • r¯s=1njrsj=(n+1)2.

    • r¯t=1njrtj=(n+1)2.

    スピアマン距離を指定するには、Distance パラメーターを 'spearman' に設定します。

k 最近傍探索および半径探索

n 個の点と距離関数のセット X があれば、k 最近傍点 (kNN) 検索により、X 内のクエリ点またはクエリ点の集合 Y に対する k 最近傍点を検索できます。kNN 検索手法と kNN ベースのアルゴリズムは、ベンチマーク学習規則として広く使用されています。kNN 検索手法は比較的使いやすいので、他の分類手法による結果と kNN の結果を簡単に比較できます。この手法は次のようなさまざまな分野で使用されています。

  • バイオインフォマティクス

  • イメージ処理およびデータ圧縮

  • ドキュメンテーションの取得

  • コンピューター ビジョン

  • マルチメディア データベース

  • マーケティング データ解析

次のようなその他の機械学習アルゴリズムにも kNN 検索を使用できます。

  • kNN 分類

  • 局所的加重回帰

  • 欠損データの補定と内挿

  • 密度推定

k-means クラスタリングなどの多くの距離ベースの学習関数と共に、kNN 検索を使用することもできます。

これに対して、正の実数値 r の場合、rangesearchY 内の各点の距離 r 内にある X 内のすべての点を検索します。この固定半径探索は、同じ距離計量と検索クラスをサポートし、同じ検索アルゴリズムを使用するため、kNN 検索と密接に関連しています。

網羅的探索を使用した k 最近傍探索

入力するデータが次の条件のいずれかを満たす場合、knnsearch では既定の設定で網羅的探索手法を使用して、k 最近傍点を検索します。

  • X の列数が 10 を超えている。

  • X がスパース。

  • 距離計量が以下のいずれか。

    • 'seuclidean'

    • 'mahalanobis'

    • 'cosine'

    • 'correlation'

    • 'spearman'

    • 'hamming'

    • 'jaccard'

    • カスタム距離関数

探索オブジェクトが ExhaustiveSearcher モデルのオブジェクトである場合、knnsearch では網羅的探索手法も使用します。網羅的探索手法では、各クエリ点から X 内のすべての点までの距離が検索され、昇順にランク付けされて、距離が最小の k 点が返されます。たとえば、次の図は k = 3 の最近傍点を示しています。

3-nearest neighbors diagram. knnsearch computes the displayed distances by using the exhaustive search method.

Kd 木を使用した k 最近傍探索

入力するデータが次の条件をすべて満たす場合、knnsearch では既定の設定で Kd ツリーを作成して、k 最近傍を検索します。

  • X の列の数が 10 を下回っています。

  • X がスパースでない

  • 距離計量が以下のいずれか。

    • 'euclidean' (既定の設定)

    • 'cityblock'

    • 'minkowski'

    • 'chebychev'

探索オブジェクトが KDTreeSearcher モデルのオブジェクトである場合、knnsearch では Kd ツリーも使用します。

Kd ツリーでは、データがノードに分割されます。その数は、座標に基づいて (カテゴリとは対照的に)、ノードあたり最大で BucketSize 点 (既定値は 50) です。次の図は、patch オブジェクトを使用してさまざまな "バケット" を色分けする概念を示しています。

Diagram of data divided into nodes by Kd-tree

与えられたクエリ点に対する k 最近傍点を検索する場合、knnsearch では次のようになります。

  1. クエリ点が属しているノードを調べます。次の例では、クエリ点 (32,90) はノード 4 に属しています。

  2. そのノード内の k 最近傍点と、クエリ点までの距離を求めます。次の例では、赤い丸で囲んだ点はクエリ点から等距離にあり、ノード 4 内でクエリ点に最も近い点です。

  3. クエリ点から k 番目に最も近い点まで任意の方向へ等距離にある、任意の面積をもつ他のすべてのノードを選択します。この例では、ノード 4 内の最近傍点まで等距離にある半径内で、クエリ点を中心とする黒い実線の円と重なり合っているのはノード 3 だけです。

  4. その範囲内のノードで、クエリ点により近い点を検索します。次の例では、赤の四角形で囲んだ点は、ノード 4 内の点よりもわずかにクエリ点の近くにあります。

Diagram of nodes and nearest neighbors

10 次元 (列) 未満の大きいデータセットに Kd ツリーを使用すると、knnsearch で必要な計算が距離のサブセットだけになるので、網羅的探索手法を使用する場合よりもはるかに効率的になります。Kd ツリーの効率を向上させるには、KDTreeSearcher モデルを使用します。

探索モデル オブジェクトとは

基本的に、モデル オブジェクトは情報を格納するための便利な手段です。特定の探索モデルに関する値および型についてのプロパティは、関連するモデル間で同じになります。モデルに情報を格納することに加え、特定のアクションをモデルに対して実行できます。

knnsearch を使用すると、k 最近傍探索を探索モデルに対して効率的に実行できます。また、探索モデルと rangesearch を使用すると、指定した半径内に含まれているすべての近傍を探索できます。さらに、モデルの作成や使用を行わずに探索を実行する汎用の関数 knnsearch および rangesearch もあります。

どのタイプのモデルおよび探索方法がデータに最適であるかを判別するには、以下を考慮します。

  • データに多くの (たとえば、10 を超える) 列があるかどうか。ExhaustiveSearcher モデルが適している可能性があります。

  • データがスパースかどうか。ExhaustiveSearcher モデルを使用します。

  • 最近傍の検索に次の距離計量のいずれかを使用するかどうか。ExhaustiveSearcher モデルを使用します。

    • 'seuclidean'

    • 'mahalanobis'

    • 'cosine'

    • 'correlation'

    • 'spearman'

    • 'hamming'

    • 'jaccard'

    • カスタム距離関数

  • データセットが巨大であるかどうか (ただし 10 列未満)。KDTreeSearcher モデルを使用します。

  • 多くのクエリ点に対して最近傍点を検索するかどうか。KDTreeSearcher モデルを使用します。

クエリ データの分類

この例では、以下を行ってクエリ データを分類する方法を示します。

  1. Kd 木を成長させる。

  2. 成長した木を使用して k 最近傍探索を実行する。

  3. 各最近傍間で最高の表現になるクラスにクエリ点を割り当てる。

フィッシャーのアヤメの分析データの最後の 2 列に基づいて新しい点を分類します。最後の 2 列のみを使用することにより、プロット作成が容易になります。

load fisheriris
x = meas(:,3:4);
gscatter(x(:,1),x(:,2),species)
legend('Location','best')

Figure contains an axes object. The axes object contains 3 objects of type line. One or more of the lines displays its values using only markers These objects represent setosa, versicolor, virginica.

新しい点をプロットします。

newpoint = [5 1.45];
line(newpoint(1),newpoint(2),'marker','x','color','k',...
   'markersize',10,'linewidth',2)

Figure contains an axes object. The axes object contains 4 objects of type line. One or more of the lines displays its values using only markers These objects represent setosa, versicolor, virginica.

Kd 木の近傍探索モデルを準備します。

Mdl = KDTreeSearcher(x)
Mdl = 
  KDTreeSearcher with properties:

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

MdlKDTreeSearcher モデルです。既定の設定では、距離計量にユークリッド距離を使用して近傍を探索します。

新しい点に最も近い 10 個の標本点を検索します。

[n,d] = knnsearch(Mdl,newpoint,'k',10);
line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o',...
    'linestyle','none','markersize',10)

Figure contains an axes object. The axes object contains 5 objects of type line. One or more of the lines displays its values using only markers These objects represent setosa, versicolor, virginica.

knnsearch で検索された最近傍点は、8 つだけのようです。実際は、この特定のデータセットに重複する値が含まれています。

x(n,:)
ans = 10×2

    5.0000    1.5000
    4.9000    1.5000
    4.9000    1.5000
    5.1000    1.5000
    5.1000    1.6000
    4.8000    1.4000
    5.0000    1.7000
    4.7000    1.4000
    4.7000    1.4000
    4.7000    1.5000

計算された距離がプロット軸の見かけの距離に等しく対応するように軸を等しくし、近傍点がよく見えるように拡大します。

xlim([4.5 5.5]);
ylim([1 2]);
axis square

Figure contains an axes object. The axes object contains 5 objects of type line. One or more of the lines displays its values using only markers These objects represent setosa, versicolor, virginica.

10 個の近傍点の種類を求めます。

tabulate(species(n))
       Value    Count   Percent
   virginica        2     20.00%
  versicolor        8     80.00%

10 個の最近傍点の多数決に基づく規則を使用して、新しい点を versicolor として分類できます。

グループの周りに円を描画することによって、近傍点を視覚的に特定します。新しい点の位置に基づいて円の中心と直径を定義します。

ctr = newpoint - d(end);
diameter = 2*d(end);
% Draw a circle around the 10 nearest neighbors.
h = rectangle('position',[ctr,diameter,diameter],...
   'curvature',[1 1]);
h.LineStyle = ':';

Figure contains an axes object. The axes object contains 6 objects of type line, rectangle. One or more of the lines displays its values using only markers These objects represent setosa, versicolor, virginica.

同じデータセットを使用して、3 つの新しい点に対する最近傍点を 10 個検索します。

figure 
newpoint2 = [5 1.45;6 2;2.75 .75];
gscatter(x(:,1),x(:,2),species)
legend('location','best')
[n2,d2] = knnsearch(Mdl,newpoint2,'k',10);
line(x(n2,1),x(n2,2),'color',[.5 .5 .5],'marker','o',...
   'linestyle','none','markersize',10)
line(newpoint2(:,1),newpoint2(:,2),'marker','x','color','k',...
   'markersize',10,'linewidth',2,'linestyle','none')

Figure contains an axes object. The axes object contains 5 objects of type line. One or more of the lines displays its values using only markers These objects represent setosa, versicolor, virginica.

新しい点に対してそれぞれ 10 個の最近傍点の種類を検索します。

tabulate(species(n2(1,:)))
       Value    Count   Percent
   virginica        2     20.00%
  versicolor        8     80.00%
tabulate(species(n2(2,:)))
      Value    Count   Percent
  virginica       10    100.00%
tabulate(species(n2(3,:)))
       Value    Count   Percent
  versicolor        7     70.00%
      setosa        3     30.00%

メソッド knnsearch と関数のその他の使用例については、個々のリファレンス ページを参照してください。

カスタム距離計量を使用した最近傍の検索

この例は、カイ二乗距離に関する Y の各観測値に最も近い観測値 X の 3 つのインデックスを検出する方法を示します。この距離計量はコレスポンデンス分析、特に環境アプリケーションで使用されます。

2 つの行列に正規分布データを無作為に生成します。行数は可変ですが、列数は同じでなくてはなりません。この例はプロットに 2 次元データを使用します。

rng(1) % For reproducibility
X = randn(50,2);
Y = randn(4,2);

h = zeros(3,1);
figure
h(1) = plot(X(:,1),X(:,2),'bx');
hold on
h(2) = plot(Y(:,1),Y(:,2),'rs','MarkerSize',10);
title('Heterogeneous Data')

Figure contains an axes object. The axes object with title Heterogeneous Data contains 2 objects of type line. One or more of the lines displays its values using only markers

X および Y の行は観測値に対応し、列は一般的には次元 (たとえば予測子) です。

j 次元の x 点と z 点のカイ二乗距離は次のようになります。

χ(x,z)=j=1Jwj(xj-zj)2,

ここで、wj は次元 j に関連付けられている重みです。

各次元に対して重みを選択し、カイ二乗距離関数を指定します。距離関数は以下の手順を実行しなければなりません。

  • 入力引数として X の 1 行 (たとえば x) および行列 Z を取る。

  • xZ の各行と比較する。

  • 長さ nz のベクトル D を返す。nzZ の行数です。D の各要素は x に対応する観測と Z の各行に対応する観測との間の距離です。

w = [0.4; 0.6];
chiSqrDist = @(x,Z)sqrt(((x-Z).^2)*w);

この例では例示のために任意の重みを使用します。

Y の各観測値に最も近い 3 つのインデックスを、X の観測値で検出します。

k = 3;
[Idx,D] = knnsearch(X,Y,'Distance',chiSqrDist,'k',k);

idx および D は、4 行 3 列の行列です。

  • idx(j,1) は、X における最も近い観測値から Y における観測値 j への行インデックスであり、D(j,1) はその距離です。

  • idx(j,2) は、X において次に近い観測値と Y における観測値 j の行インデックスであり、D(j,2) はその距離です。

  • 以下同様です。

プロットにおける最も近い観測値を特定します。

for j = 1:k
    h(3) = plot(X(Idx(:,j),1),X(Idx(:,j),2),'ko','MarkerSize',10);
end 
legend(h,{'\texttt{X}','\texttt{Y}','Nearest Neighbor'},'Interpreter','latex')
title('Heterogeneous Data and Nearest Neighbors')
hold off

Figure contains an axes object. The axes object with title Heterogeneous Data and Nearest Neighbors contains 5 objects of type line. One or more of the lines displays its values using only markers These objects represent \texttt{X}, \texttt{Y}, Nearest Neighbor.

Y の複数の観測値では最近傍が共有されます。

カイ二乗距離計量はユークリッド距離計量と同等ですが、オプションでスケーリング パラメーターを使用することを検証します。

[IdxE,DE] = knnsearch(X,Y,'Distance','seuclidean','k',k, ...
    'Scale',1./(sqrt(w)));
AreDiffIdx = sum(sum(Idx ~= IdxE))
AreDiffIdx = 0
AreDiffDist = sum(sum(abs(D - DE) > eps))
AreDiffDist = 0

3 つの最近傍のうち 2 つの実装間において、インデックスおよび距離は実質的に等しくなります。

教師あり学習での k 最近傍分類

ClassificationKNN 分類モデルでは、以下を行うことができます。

教師あり学習のステップの手順に従って分類用のデータを準備します。次に、fitcknn を使用して分類器を構築します。

KNN 分類器の構築

次の例は、フィッシャーのアヤメのデータ用に k 最近傍分類器を構築する方法を示しています。

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

load fisheriris
X = meas;    % Use all data for fitting
Y = species; % Response data

fitcknn を使用して分類器を構築します。

Mdl = fitcknn(X,Y)
Mdl = 
  ClassificationKNN
             ResponseName: 'Y'
    CategoricalPredictors: []
               ClassNames: {'setosa'  'versicolor'  'virginica'}
           ScoreTransform: 'none'
          NumObservations: 150
                 Distance: 'euclidean'
             NumNeighbors: 1


既定の k 最近傍分類器は、単一の最近傍のみを使用します。多くの場合、それより多くの近傍をもつ分類器のほうがロバストです。

Mdl の近傍サイズを 4 に変更します。これは、Mdl が 4 つの最近傍を使用して分類することを意味します。

Mdl.NumNeighbors = 4;

KNN 分類器の品質の確認

次の例は、再代入と交差検証を使用して k 最近傍分類器の品質を調べる方法を示しています。

KNN 分類器の構築 にあるように、フィッシャーのアヤメのデータ用の KNN 分類器を構築します。

load fisheriris
X = meas;    
Y = species; 
rng(10); % For reproducibility
Mdl = fitcknn(X,Y,'NumNeighbors',4);

再代入損失を調べます。これは既定では、Mdl の予測での誤分類率の比率です (既定の設定と異なるコスト、重み、または事前確率については、lossを参照してください。)

rloss = resubLoss(Mdl)
rloss = 0.0400

この分類器は学習データが 4% の場合は不正確な予測を行います。

このモデルから交差検証分類器を構築します。

CVMdl = crossval(Mdl);

交差検証損失を調べます。これは、学習に使用されないデータを予測したときの各交差検証済みモデルの平均損失です。

kloss = kfoldLoss(CVMdl)
kloss = 0.0333

交差検証分類器の精度は再代入精度とほぼ同じです。したがって、新しいデータが学習データとほぼ同じ分布であると仮定すると、Mdl では新しいデータの約 4% が誤判定されることを予想できます。

KNN 分類器を使用した分類の予測

次の例は、k 最近傍分類器での分類を予測する方法を示します。

KNN 分類器の構築 にあるように、フィッシャーのアヤメのデータ用の KNN 分類器を構築します。

load fisheriris
X = meas;    
Y = species; 
Mdl = fitcknn(X,Y,'NumNeighbors',4);

平均の花の分類を予測します。

flwr = mean(X); % an average flower
flwrClass = predict(Mdl,flwr)
flwrClass = 1x1 cell array
    {'versicolor'}

KNN 分類器の変更

次の例は、k 最近傍分類器を変更する方法を示します。

KNN 分類器の構築 にあるように、フィッシャーのアヤメのデータ用の KNN 分類器を構築します。

load fisheriris
X = meas;    
Y = species; 
Mdl = fitcknn(X,Y,'NumNeighbors',4);

既定の 1 つの最近傍ではなく 3 つの最近傍が使用されるよう、モデルを変更します。

Mdl.NumNeighbors = 3;

再代入予測と、新しい近傍の数をもつ交差検証損失を比較します。

loss = resubLoss(Mdl)
loss = 0.0400
rng(10); % For reproducibility
CVMdl = crossval(Mdl,'KFold',5);
kloss = kfoldLoss(CVMdl)
kloss = 0.0333

この場合、3 つの近傍があるモデルは 4 つの近傍があるモデルと交差検証損失が同じです (KNN 分類器の品質の確認を参照してください)。

既定値の代わりに余弦距離が使用されるようにモデルを変更し、損失を調べます。余弦距離を使用するには、網羅的探索手法を使用してモデルを再作成しなければなりません。

CMdl = fitcknn(X,Y,'NSMethod','exhaustive','Distance','cosine');
CMdl.NumNeighbors = 3;
closs = resubLoss(CMdl)
closs = 0.0200

これで、分類器の再代入誤差が前より少なくなりました。

新しいモデルの交差検証バージョンの品質を調べます。

CVCMdl = crossval(CMdl);
kcloss = kfoldLoss(CVCMdl)
kcloss = 0.0200

CVCMdl は、CVMdl より交差検証損失が小さくなっています。ただし一般的には、再代入誤差を小さくしても、テスト標本予測の精度が向上したモデルが作成されるとは限りません。

参考

| | |