最近傍点を使用した分類

ペアワイズ距離計量

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

距離計量

mx 行 n 列のデータ行列 X (mx 個の 1 行 n 列の行ベクトル x₁、x₂、...、x_mx として扱われる) と、my 行 n 列のデータ行列 Y (my 個の 1 行 n 列の行ベクトル y₁、y₂、...、y_my として扱われる) が与えられた場合、ベクトル x_s と y_t の間のさまざまな距離は次のように定義されます。

ユークリッド距離
$d_{s t}^{2} = (x_{s} - y_{t}) (x_{s} - y_{t})^{'} .$
ユークリッド距離はミンコフスキー距離の特殊なケース、p = 2 の場合です。
標準化されたユークリッド距離
$d_{s t}^{2} = (x_{s} - y_{t}) V^{- 1} (x_{s} - y_{t})^{'},$
ここで、V は j 番目の対角要素が (S(j))² である n 行 n 列の対角行列です。S は各次元のスケーリング係数のベクトルです。
マハラノビス距離
$d_{s t}^{2} = (x_{s} - y_{t}) C^{- 1} (x_{s} - y_{t})^{'},$
ここで、C は共分散行列です。
市街地距離
$d_{s t} = \sum_{j = 1}^{n} | x_{s j} - y_{t j} | .$
市街地距離はミンコフスキー距離の特殊なケース、p = 1 の場合です。
ミンコフスキー距離
$d_{s t} = \sqrt[p]{\sum_{j = 1}^{n} {| x_{s j} - y_{t j} |}^{p}} .$
p = 1 という特殊なケースでは、ミンコフスキー距離は市街地距離を与えます。p = 2 という特殊なケースでは、ミンコフスキー距離はユークリッド距離を与えます。p = ∞ という特殊なケースでは、ミンコフスキー距離はチェビシェフ距離を与えます。
チェビシェフ距離
$d_{s t} = \max_{j} {| x_{s j} - y_{t j} |} .$
チェビシェフ距離はミンコフスキー距離の特殊なケース、p = ∞ の場合です。
コサイン距離
$d_{s t} = (1 - \frac{x_{s} {y^{'}}_{t}}{\sqrt{(x_{s} {x^{'}}_{s}) (y_{t} {y^{'}}_{t})}}) .$
相関距離
$d_{s t} = 1 - \frac{(x_{s} - {\bar{x}}_{s}) {(y_{t} - {\bar{y}}_{t})}^{'}}{\sqrt{(x_{s} - {\bar{x}}_{s}) {(x_{s} - {\bar{x}}_{s})}^{'}} \sqrt{(y_{t} - {\bar{y}}_{t}) {(y_{t} - {\bar{y}}_{t})}^{'}}},$
ここで
${\bar{x}}_{s} = \frac{1}{n} \sum_{j} x_{s j}$
および
${\bar{y}}_{t} = \frac{1}{n} \sum_{j} y_{t j} .$
ハミング距離
$d_{s t} = (# (x_{s j} \neq y_{t j}) / n) .$
Jaccard 距離
$d_{s t} = \frac{# [(x_{s j} \neq y_{t j}) \cap ((x_{s j} \neq 0) \cup (y_{t j} \neq 0))]}{# [(x_{s j} \neq 0) \cup (y_{t j} \neq 0)]} .$
スピアマン距離
$d_{s t} = 1 - \frac{(r_{s} - {\bar{r}}_{s}) {(r_{t} - {\bar{r}}_{t})}^{'}}{\sqrt{(r_{s} - {\bar{r}}_{s}) {(r_{s} - {\bar{r}}_{s})}^{'}} \sqrt{(r_{t} - {\bar{r}}_{t}) {(r_{t} - {\bar{r}}_{t})}^{'}}},$
ここで
- r_sj は、tiedrank により計算される、x_1j、x_2j、...x_mx,j から取得された x_sj の順位です。
- r_tj は、tiedrank により計算される、y_1j、y_2j、...y_my,j から取得された y_tj の順位です。
- r_s および r_t は、x_s および y_t の座標単位の順位ベクトルです。つまり、r_s = (r_s₁, r_s₂, ... r_sn) および r_t = (r_t1, r_t2, ... r_tn) です。
- ${\bar{r}}_{s} = \frac{1}{n} \sum_{j} r_{s j} = \frac{(n + 1)}{2}$ .
- ${\bar{r}}_{t} = \frac{1}{n} \sum_{j} r_{t j} = \frac{(n + 1)}{2}$ .

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

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

バイオインフォマティクス
イメージ処理およびデータ圧縮
ドキュメンテーションの取得
コンピュータービジョン
マルチメディアデータベース
マーケティングデータ解析

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

kNN 分類
局所的加重回帰
欠損データの補定と内挿
密度推定

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

これに対して、正の実数値 r の場合、rangesearch は Y 内の各点の距離 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 では次のようになります。

クエリ点が属しているノードを調べます。次の例では、クエリ点 (32,90) はノード 4 に属しています。
そのノード内の k 最近傍点と、クエリ点までの距離を求めます。次の例では、赤い丸で囲んだ点はクエリ点から等距離にあり、ノード 4 内でクエリ点に最も近い点です。
クエリ点から k 番目に最も近い点まで任意の方向へ等距離にある、任意の面積をもつ他のすべてのノードを選択します。この例では、ノード 4 内の最近傍点まで等距離にある半径内で、クエリ点を中心とする黒い実線の円と重なり合っているのはノード 3 だけです。
その範囲内のノードで、クエリ点により近い点を検索します。次の例では、赤の四角形で囲んだ点は、ノード 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 モデルを使用します。

クエリデータの分類

ライブスクリプトを開く

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

Kd 木を成長させる。
成長した木を使用して k 最近傍探索を実行する。
各最近傍間で最高の表現になるクラスにクエリ点を割り当てる。

フィッシャーのアヤメの分析データの最後の 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]

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

新しい点に最も近い 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) = \sqrt{\sum_{j = 1}^{J} w_{j} {(x_{j} - z_{j})}^{2}},$

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

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

入力引数として X の 1 行 (たとえば x) および行列 Z を取る。
x を Z の各行と比較する。
長さ $n_{z}$ のベクトル D を返す。 $n_{z}$ は Z の行数です。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


  Properties, Methods

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

参考

fitcknn | ClassificationKNN | ExhaustiveSearcher | KDTreeSearcher