K 最近傍 (KNN) アルゴリズム - TECHCODEVIEW.COM

の K 最近傍 (KNN) アルゴリズム は、分類と回帰の問題に取り組むために使用される教師あり機械学習手法です。 Evelyn Fix と Joseph Hodges は 1951 年にこのアルゴリズムを開発し、その後 Thomas Cover によって拡張されました。この記事では、KNN アルゴリズムの基礎、仕組み、実装について説明します。

K 最近傍アルゴリズムとは何ですか?

KNN は、機械学習において最も基本的かつ不可欠な分類アルゴリズムの 1 つです。それはに属します教師あり学習この分野ではパターン認識に強力な応用が見出されています。これはノンパラメトリックであるため、現実のシナリオで広く使い捨て可能です。つまり、(GMM などの他のアルゴリズムとは対照的に、データの分布に関する基礎的な仮定を行いません) ガウス分布与えられたデータの）。座標を属性によって識別されるグループに分類する、いくつかの事前データ (トレーニングデータとも呼ばれます) が与えられます。

javatable

例として、2 つの特徴を含む次のデータポイントの表を考えてみましょう。

KNN アルゴリズム動作の可視化

ここで、別のデータポイントのセット (テストデータとも呼ばれます) が与えられた場合、トレーニングセットを分析してこれらのポイントをグループに割り当てます。未分類のポイントは「白」としてマークされていることに注意してください。

KNN アルゴリズムの背後にある直感

これらの点をグラフ上にプロットすると、いくつかのクラスターまたはグループを見つけることができる場合があります。ここで、未分類の点が与えられた場合、その最も近い点がどのグループに属しているかを観察することで、その点をグループに割り当てることができます。これは、「赤」として分類された点のクラスターに近い点は、「赤」として分類される可能性が高いことを意味します。

直感的には、最初の点 (2.5、7) は「緑」に分類され、2 番目の点 (5.5、4.5) は「赤」に分類されることがわかります。

なぜ KNN アルゴリズムが必要なのでしょうか?

(K-NN) アルゴリズムは、多用途で広く使用されている機械学習アルゴリズムであり、主にそのシンプルさと実装の容易さのために使用されます。基礎となるデータ分布についての仮定は必要ありません。また、数値データとカテゴリデータの両方を処理できるため、分類および回帰タスクでさまざまなタイプのデータセットに柔軟に選択できます。これは、特定のデータセット内のデータポイントの類似性に基づいて予測を行うノンパラメトリックな方法です。 K-NN は、他のアルゴリズムに比べて外れ値に対する感度が低くなります。

K-NN アルゴリズムは、ユークリッド距離などの距離メトリックに基づいて、指定されたデータポイントに最も近い K 個の近傍を見つけることによって機能します。データポイントのクラスまたは値は、K 個の近傍の多数決または平均によって決定されます。このアプローチにより、アルゴリズムがさまざまなパターンに適応し、データのローカル構造に基づいて予測を行うことができます。

KNN アルゴリズムで使用される距離メトリック

ご存知のとおり、KNN アルゴリズムは、クエリポイントに最も近いポイントまたはグループを識別するのに役立ちます。ただし、クエリポイントに最も近いグループまたは最も近い点を決定するには、何らかのメトリックが必要です。この目的のために、以下の距離メトリックを使用します。

ユークリッド距離

これは、平面/超平面内にある 2 点間のデカルト距離に他なりません。ユークリッド距離考慮している 2 つの点を結ぶ直線の長さとして視覚化することもできます。このメトリクスは、オブジェクトの 2 つの状態の間で行われる正味の変位を計算するのに役立ちます。

$ext{距離}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]$

マンハッタンの距離

マンハッタンの距離メトリックは通常、変位ではなくオブジェクトが移動した合計距離に関心がある場合に使用されます。このメトリックは、n 次元の点の座標間の絶対差を合計することによって計算されます。

$dleft ( x,y ight )={sum_{i=1}^{n}left | x_i-y_i ight |}$

ミンコフスキー距離

ユークリッド距離とマンハッタン距離は、ミンコフスキー距離。

$dleft ( x,y ight )=left ( {sum_{i=1}^{n}left ( x_i-y_i ight )^p} ight )^{frac{1}{p }}$

上の式から、p = 2 の場合はユークリッド距離の式と同じであり、p = 1 の場合はマンハッタン距離の式が得られると言えます。

上で説明したメトリクスは、問題を扱うときに最も一般的です。機械学習問題はありますが、次のような他の距離メトリックもありますハミング距離これは、内容がブール値でも文字列値でもよい 2 つのベクトル間の重複比較が必要な問題を処理するときに便利です。

KNN アルゴリズムの k の値を選択するにはどうすればよいですか?

KNN アルゴリズムでは、アルゴリズム内の近傍数を定義するために k の値が非常に重要です。 k 最近傍 (k-NN) アルゴリズムの k の値は、入力データに基づいて選択する必要があります。入力データに外れ値やノイズが多い場合は、k の値が大きいほど良いでしょう。分類における同点を避けるために、k には奇数の値を選択することをお勧めします。相互検証メソッドは、特定のデータセットに最適な k 値を選択するのに役立ちます。

KNNアルゴリズムの仕組み

K 最近傍 (KNN) アルゴリズムは類似性の原理に基づいて動作し、トレーニングデータセット内の K 最近傍のラベルまたは値を考慮して、新しいデータポイントのラベルまたは値を予測します。

KNNアルゴリズムの仕組み

KNN がどのように機能するかを段階的に説明します。

ステップ 1: K の最適値を選択する

K は、予測を行う際に考慮する必要がある最近傍の数を表します。

ステップ 2: 距離の計算

ターゲットデータポイントとトレーニングデータポイント間の類似性を測定するには、ユークリッド距離が使用されます。データセット内の各データポイントとターゲットポイントの間の距離が計算されます。

ステップ 3: 最も近い隣人を見つける

ターゲットポイントまでの距離が最小の k データポイントが最近傍データポイントになります。

ステップ 4: 分類に投票するか、回帰のために平均をとる

分類問題では、多数決を行ってクラスラベルを決定します。近傍クラスの中で最も多く出現したクラスが、ターゲットデータポイントの予測クラスになります。
回帰問題では、K 個の最近傍のターゲット値の平均を取ることによってクラスラベルが計算されます。計算された平均値は、ターゲットデータポイントの予測出力になります。

X を n データ点を持つトレーニングデータセットとし、各データ点は d 次元の特徴ベクトルで表されます。 X_i Y は、X の各データポイントに対応するラベルまたは値です。新しいデータポイント x が与えられると、アルゴリズムは x と各データポイントの間の距離を計算します。 X_i X では、ユークリッド距離などの距離計量を使用します。 $ext{距離}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]$

このアルゴリズムは、X から x までの距離が最も短い K データポイントを選択します。分類タスクの場合、アルゴリズムは、K 個の最近傍の中で最も頻度の高いラベル y を x に割り当てます。回帰タスクの場合、アルゴリズムは K 個の最近傍の値 y の平均または加重平均を計算し、それを x の予測値として割り当てます。

KNN アルゴリズムの利点

実装が簡単 アルゴリズムの複雑さはそれほど高くないためです。
簡単に適応 – KNN アルゴリズムの動作に従って、すべてのデータがメモリストレージに保存されるため、新しい例またはデータポイントが追加されるたびに、アルゴリズムはその新しい例に従って自動的に調整され、将来の予測にも貢献します。
いくつかのハイパーパラメータ – KNN アルゴリズムのトレーニングに必要なパラメータは、k の値と、評価メトリックから選択する距離メトリックの選択だけです。

KNN アルゴリズムの欠点

スケールしない – これについては、KNN アルゴリズムも遅延アルゴリズムとみなされていると聞いています。この用語の主な重要性は、これにはデータストレージだけでなく多くのコンピューティング能力も必要となることです。このため、このアルゴリズムは時間がかかり、リソースも消耗します。
次元の呪い – これによると、KNN アルゴリズムはピーキング現象として知られる用語があります。次元の呪いこれは、次元が高すぎる場合、アルゴリズムがデータポイントを適切に分類するのに困難に直面することを意味します。
過学習になりやすい – アルゴリズムは次元の呪いの影響を受けるため、過剰適合の問題も発生しやすくなります。したがって一般的には機能の選択同様に次元削減この問題に対処するために技術が適用されています。

プログラム例:

2 つの分類子 (グループ) として 0 と 1 を仮定します。

C++

// C++ program to find groups of unknown> // Points using K nearest neighbour algorithm.> #include> using> namespace> std;> struct> Point> {> >int> val;>// Group of point> >double> x, y;>// Co-ordinate of point> >double> distance;>// Distance from test point> };> // Used to sort an array of points by increasing> // order of distance> bool> comparison(Point a, Point b)> {> >return>

(a.distance  } // This function finds classification of point p using // k nearest neighbour algorithm. It assumes only two // groups and returns 0 if p belongs to group 0, else // 1 (belongs to group 1). int classifyAPoint(Point arr[], int n, int k, Point p) {  // Fill distances of all points from p  for (int i = 0; i   arr[i].distance =  sqrt((arr[i].x - p.x) * (arr[i].x - p.x) +  (arr[i].y - p.y) * (arr[i].y - p.y));  // Sort the Points by distance from p  sort(arr, arr+n, comparison);  // Now consider the first k elements and only  // two groups  int freq1 = 0; // Frequency of group 0  int freq2 = 0; // Frequency of group 1  for (int i = 0; i   {  if (arr[i].val == 0)  freq1++;  else if (arr[i].val == 1)  freq2++;  }  return (freq1>周波数2 ? 0:1); } // ドライバーコード int main() { int n = 17; // データポイントの数 Point arr[n];  arr[0].x = 1;  arr[0].y = 12;  arr[0].val = 0;  arr[1].x = 2;  arr[1].y = 5;  arr[1].val = 0;  arr[2].x = 5;  arr[2].y = 3;  arr[2].val = 1;  arr[3].x = 3;  arr[3].y = 2;  arr[3].val = 1;  arr[4].x = 3;  arr[4].y = 6;  arr[4].val = 0;  arr[5].x = 1.5;  arr[5].y = 9;  arr[5].val = 1;  arr[6].x = 7;  arr[6].y = 2;  arr[6].val = 1;  arr[7].x = 6;  arr[7].y = 1;  arr[7].val = 1;  arr[8].x = 3.8;  arr[8].y = 3;  arr[8].val = 1;  arr[9].x = 3;  arr[9].y = 10;  arr[9].val = 0;  arr[10].x = 5.6;  arr[10].y = 4;  arr[10].val = 1;  arr[11].x = 4;  arr[11].y = 2;  arr[11].val = 1;  arr[12].x = 3.5;  arr[12].y = 8;  arr[12].val = 0;  arr[13].x = 2;  arr[13].y = 11;  arr[13].val = 0;  arr[14].x = 2;  arr[14].y = 5;  arr[14].val = 1;  arr[15].x = 2;  arr[15].y = 9;  arr[15].val = 0;  arr[16].x = 1;  arr[16].y = 7;  arr[16].val = 0;  /*テストポイント*/ ポイント p;  p.x = 2.5;  p.y = 7;  // テストポイントのグループを決定するパラメータ int k = 3;  printf ('未知の点に分類された値' ' は %d です。
', assignAPoint(arr, n, k, p));  0を返します。 }>>

ジャワ

// Java program to find groups of unknown> // Points using K nearest neighbour algorithm.> import> java.io.*;> import> java.util.*;> class> GFG {> >static> class> Point {> >int> val;>// Group of point> >double> x, y;>// Co-ordinate of point> >double> distance;>// Distance from test point> >}> >// Used to sort an array of points by increasing> >// order of distance> >static> class> comparison>implements> Comparator {> >public> int> compare(Point a, Point b)> >{> >if>

(a.distance   return -1;  else if (a.distance>b.距離) 1 を返します。  0を返します。  } } // この関数は、 // k 最近傍アルゴリズムを使用して点 p の分類を見つけます。 // 2 つのグループのみを想定しており、p がグループ 0 に属している場合は 0 を返し、そうでない場合は // 1 (グループ 1 に属している) を返します。  static int assignAPoint(Point arr[], int n, int k, Point p) { // p からのすべての点の距離を埋める for (int i = 0; i arr[i]. distance = Math.sqrt( (arr[ i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)); // ポイントを距離で並べ替えます。 p Arrays.sort(arr, new COMPANY()); // 最初の k 要素と 2 つのグループのみを考慮します。 int freq1 = 0; // グループ 0 の頻度 int freq2 = 0; (int i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return (freq1> freq2 ? 0 : 1); } / / ドライバーコード public static void main(String[] args) { int n = 17 // データポイント数 Point[] arr = new Point[n];<17; i++) {  arr[i] = new Point();  }  arr[0].x = 1;  arr[0].y = 12;  arr[0].val = 0;  arr[1].x = 2;  arr[1].y = 5;  arr[1].val = 0;  arr[2].x = 5;  arr[2].y = 3;  arr[2].val = 1;  arr[3].x = 3;  arr[3].y = 2;  arr[3].val = 1;  arr[4].x = 3;  arr[4].y = 6;  arr[4].val = 0;  arr[5].x = 1.5;  arr[5].y = 9;  arr[5].val = 1;  arr[6].x = 7;  arr[6].y = 2;  arr[6].val = 1;  arr[7].x = 6;  arr[7].y = 1;  arr[7].val = 1;  arr[8].x = 3.8;  arr[8].y = 3;  arr[8].val = 1;  arr[9].x = 3;  arr[9].y = 10;  arr[9].val = 0;  arr[10].x = 5.6;  arr[10].y = 4;  arr[10].val = 1;  arr[11].x = 4;  arr[11].y = 2;  arr[11].val = 1;  arr[12].x = 3.5;  arr[12].y = 8;  arr[12].val = 0;  arr[13].x = 2;  arr[13].y = 11;  arr[13].val = 0;  arr[14].x = 2;  arr[14].y = 5;  arr[14].val = 1;  arr[15].x = 2;  arr[15].y = 9;  arr[15].val = 0;  arr[16].x = 1;  arr[16].y = 7;  arr[16].val = 0;  /*Testing Point*/  Point p = new Point();  p.x = 2.5;  p.y = 7;  // Parameter to decide group of the testing point  int k = 3;  System.out.println(  'The value classified to unknown point is '  + classifyAPoint(arr, n, k, p));  } } // This code is contributed by Karandeep1234>

Python3

import> math> def> classifyAPoint(points,p,k>=>3>):> >'''> >This function finds the classification of p using> >k nearest neighbor algorithm. It assumes only two> >groups and returns 0 if p belongs to group 0, else> >1 (belongs to group 1).> >Parameters -> >points: Dictionary of training points having two keys - 0 and 1> >Each key have a list of training data points belong to that> >p : A tuple, test data point of the form (x,y)> >k : number of nearest neighbour to consider, default is 3> >'''> >distance>=>[]> >for> group>in> points:> >for> feature>in> points[group]:> >#calculate the euclidean distance of p from training points> >euclidean_distance>=> math.sqrt((feature[>0>]>->p[>0>])>*>*>2> +>(feature[>1>]>->p[>1>])>*>*>2>)> ># Add a tuple of form (distance,group) in the distance list> >distance.append((euclidean_distance,group))> ># sort the distance list in ascending order> ># and select first k distances> >distance>=> sorted>(distance)[:k]> >freq1>=> 0> #frequency of group 0> >freq2>=> 0> #frequency og group 1> >for> d>in> distance:> >if> d[>1>]>=>=> 0>:> >freq1>+>=> 1> >elif> d[>1>]>=>=> 1>:> >freq2>+>=> 1> >return> 0> if> freq1>周波数2>>.> >format>(classifyAPoint(points,p,k)))> if> __name__>=>=> '__main__'>:> >main()>

C#

using> System;> using> System.Collections;> using> System.Collections.Generic;> using> System.Linq;> // C# program to find groups of unknown> // Points using K nearest neighbour algorithm.> class> Point {> >public> int> val;>// Group of point> >public> double> x, y;>// Co-ordinate of point> >public> int> distance;>// Distance from test point> }> class> HelloWorld {> >// This function finds classification of point p using> >// k nearest neighbour algorithm. It assumes only two> >// groups and returns 0 if p belongs to group 0, else> >// 1 (belongs to group 1).> >public> static> int> classifyAPoint(List arr,>int> n,>int> k, Point p)> >{> >// Fill distances of all points from p> >for> (>int>

i = 0; i   arr[i].distance = (int)Math.Sqrt((arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y));  // Sort the Points by distance from p  arr.Sort(delegate(Point x, Point y) {  return x.distance.CompareTo(y.distance);  });  // Now consider the first k elements and only  // two groups  int freq1 = 0; // Frequency of group 0  int freq2 = 0; // Frequency of group 1  for (int i = 0; i   if (arr[i].val == 0)  freq1++;  else if (arr[i].val == 1)  freq2++;  }  return (freq1>周波数2 ? 0:1);  静的 void Main() { int n = 17; // データポイントの数 List arr = new List();  for(int i = 0; i arr.Add(new Point()); } arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1] .x = 2; arr[1].y = 0; arr[2].y = 1; arr[3].x = 3; arr[3].val = 1; arr[4].y = 6; val = 0; arr[5].x = 1.5; arr[5].val = 1; arr[6].y = 2; [6].val = 1; arr[7].y = 1; arr[8].x = 3.8 = 3; arr[8].x = 3; arr[9].val = 0; 10].y = 4; arr[11].x = 4; arr[11].val = 1; 3.5; arr[12].y = 0; arr[13].y = 0; ].x = 2; arr[14].y = 1; arr[15].y = 0; ; arr[16].x = 1; arr[16].val = 0; /* ポイント p = 新しいポイント (); // テストポイントのグループを決定するパラメータ int k = 3;  Console.WriteLine('不明点に分類された値は ' + assignAPoint(arr, n, k, p));  } } // コードは Nidhi goel によって寄稿されました。>>

JavaScript

class Point {> >constructor(val, x, y, distance) {> >this>.val = val;>// Group of point> >this>.x = x;>// X-coordinate of point> >this>.y = y;>// Y-coordinate of point> >this>.distance = distance;>// Distance from test point> >}> }> // Used to sort an array of points by increasing order of distance> class Comparison {> >compare(a, b) {> >if>

(a.distance   return -1;  } else if (a.distance>b.距離) { 1 を返します。  0を返します。  } } // この関数は、 // k 最近傍アルゴリズムを使用して点 p の分類を見つけます。 // 2 つのグループのみを想定しており、p がグループ 0 に属している場合は 0 を返し、そうでない場合は // 1 (グループ 1 に属している) を返します。 function assignAPoint(arr, n, k, p) { // p からのすべての点の距離を埋める for (let i = 0; i arr[i]. distance = Math.sqrt((arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)) } // p からの距離でポイントを並べ替えます arr.sort(new) Comparison()); // 最初の k 要素と 2 つのグループだけを考えます let freq1 = 0; // グループ 0 の頻度 let freq2 = 0; // グループ 1 の頻度 for (let i = 0; i if (arr) [i].val === 0) { freq1++; } else if (arr[i].val === 1) { freq2++; } } // ドライバーコード const n = 17; // データポイントの数 const arr = new Array(n) for (let i = 0; i<17; i++) {  arr[i] = new Point(); } arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1].x = 2; arr[1].y = 5; arr[1].val = 0; arr[2].x = 5; arr[2].y = 3; arr[2].val = 1; arr[3].x = 3; arr[3].y = 2; arr[3].val = 1; arr[4].x = 3; arr[4].y = 6; arr[4].val = 0; arr[5].x = 1.5; arr[5].y = 9; arr[5].val = 1; arr[6].x = 7; arr[6].y = 2; arr[6].val = 1; arr[7].x = 6; arr[7].y = 1; arr[7].val = 1; arr[8].x = 3.8; arr[8].y = 3; arr[8].val = 1; arr[9].x = 3; arr[9].y = 10; arr[9].val = 0; arr[10].x = 5.6; arr[10].y = 4; arr[10].val = 1; arr[11].x = 4 arr[11].y = 2; arr[11].val = 1; arr[12].x = 3.5; arr[12].y = 8; arr[12].val = 0; arr[13].x = 2; arr[13].y = 11; arr[13].val = 0; arr[14].x = 2; arr[14].y = 5; arr[14].val = 1; arr[15].x = 2; arr[15].y = 9; arr[15].val = 0; arr[16].x = 1; arr[16].y = 7; arr[16].val = 0; // Testing Point let p = {  x: 2.5,  y: 7,  val: -1, // uninitialized }; // Parameter to decide group of the testing point let k = 3; console.log(  'The value classified to unknown point is ' +  classifyAPoint(arr, n, k, p) ); function classifyAPoint(arr, n, k, p) {  // Fill distances of all points from p  for (let i = 0; i   arr[i].distance = Math.sqrt(  (arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)  );  }  // Sort the Points by distance from p  arr.sort(function (a, b) {  if (a.distance return -1;  else if (a.distance>b.距離) 1 を返します。  0を返します。  });  // 次に、最初の k 要素と 2 つのグループだけを考えます。 let freq1 = 0; // グループ 0 の周波数 let freq2 = 0; // グループ 1 の頻度 for (let i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return freq1> freq2 ? 0 : 1; }>>

>        出力：    
Javaカウンター
 The value classified as an unknown point is 0.>
    時間計算量:    O(N * logN)  
    補助スペース:    ○(1)
 KNN アルゴリズムの応用
    データの前処理    – 機械学習の問題に対処するとき、最初に次のことを実行します。 KNN インピュート これは、高度な代入手法に一般的に使用される非常に効果的な方法です。
    パターン認識    – KNN アルゴリズムは非常にうまく機能します。MNIST データセットを使用して KNN アルゴリズムをトレーニングし、評価プロセスを実行した場合、精度が高すぎるという事実に遭遇したはずです。
    レコメンデーションエンジン    – KNN アルゴリズムによって実行される主なタスクは、膨大なデータセットのコーパスを使用して作成された既存のグループに新しいクエリ ポイントを割り当てることです。これはまさに、   Python を使用した K 最近傍 | ML  
  Python を使用して K 最近傍法を最初から実装する  
  K 最近傍法の数学的説明  
  加重 K-NN  
 よくある質問 (FAQ) 
 Q. なぜ KNN は遅延学習者なのでしょうか? 
  KNN アルゴリズムは、トレーニング段階ではモデルを構築しません。このアルゴリズムはトレーニング データセット全体を記憶し、分類時にデータセットに対してアクションを実行します。 
   
 Q. なぜ KNN がノンパラメトリックなのでしょうか? 
  KNN アルゴリズムは、分析しているデータについての仮定を行いません。 
   
 Q. KNNとK meansの違いは何ですか? 
  KNN は分類問題に使用される教師あり機械学習モデルであるのに対し、K 平均法はクラスタリングに使用される教師なし機械学習モデルです。 
 KNN の K は最近傍の数であり、K 意味の K はクラスターの数です。