k近傍法アルゴリズムとは

KNNアルゴリズムとは

k近傍法（KNN）アルゴリズムは、近接性を使用して個々のデータ・ポイントのグループ化に関する分類または予測を行う、非パラメトリックな教師あり学習分類器です。これは、今日の機械学習で使用されている、最も人気があり、かつ最もシンプルな分類および回帰分類器の1つです。

KNNアルゴリズムは回帰問題にも分類問題にも使用できますが、通常は、類似のポイントが互いに近くにあるという仮定に基づいて動作する分類アルゴリズムとして使用されます。

分類問題の場合、クラス・ラベルは多数決に基づいて割り当てられます。つまり、特定のデータ・ポイントの周囲で最も頻繁に表されるラベルが使用されます。これは技術的には「相対多数」とみなされますが、文献では「多数決」という用語がより一般的に使用されています。これらの用語の違いは、「多数決」は技術的には50%を超える票を必要とし、これは主にカテゴリーが2つしかない場合に有効ですす。複数のカテゴリーがある場合。例：4つのカテゴリーがある場合、クラスについての結論を出すのに必ずしも50%の得票が必要というわけではありません。25%を超える投票でクラス・ラベルを割り当てることができます。ウィスコンシン大学マディソン校（University of Wisconsin-Madison）は、こちら（ibm.com外部へのリンク）の例を挙げてこれをわかりやすくまとめています。

回帰問題では分類問題と同様の概念が使用されますが、この場合は、k個の最近傍の平均が取得され、分類についての予測が行われます。ここでの主な違いは、分類は離散値に使用されるのに対し、回帰は連続値に使用されることです。ただし、分類を行う前に、距離を定義する必要があります。最も一般的に使用されるのはユークリッド距離ですが、これについては後ほど詳しく説明します。
また、KNNアルゴリズムは「遅延学習」モデルのファミリーの一部でもあることにも注目してください。つまり、トレーニングを実行するのではなく、トレーニング・データセットの保存のみを実行します。これは、分類または予測が行われているときにすべての計算が行われることも意味します。すべてのトレーニング・データを保存するためにメモリーに大きく依存するため、インスタンス・ベースまたはメモリー・ベースの学習方法とも呼ばれます。
統計学者であったEvelyn Fix博士とJoseph Hodges博士は、1951年に発表した論文（ibm.com外部へのリンク）でKNNモデルに関する最初のアイデアを提唱したとされています。一方、情報理論と統計学の専門であったThomas Cover博士は、「Nearest Neighbor Pattern Classification（最近傍パターン分類）」という論文（ibm.com外部へのリンク）で2博士の研究を深めています。これは、かつてほどの人気はありませんが、そのシンプルさと正確さから、今でもデータ・サイエンスで最初に学ぶアルゴリズムの1つです。ただし、データセットが大きくなるにつれて、KNNはますます非効率になり、全体的なモデルのパフォーマンスが低下するため、単純な推奨システム、パターン認識、データマイニング、金融市場予測、侵入検知などでよく使用されます。

AIガバナンスの活用で責任あるAIワークフローを構築

チームが責任あるAIを加速するのに役立つ構成要素とベスト・プラクティスについて説明します。

関連コンテンツ

AIガバナンスに関するホワイト・ペーパーに登録する

KNNの計算：距離メトリクス

要約すると、k最近傍アルゴリズムの目的は、特定のクエリー・ポイントの最近傍を識別し、そのポイントにクラス・ラベルを割り当てることです。これを実現するために、KNNにはいくつかの要件があります。

距離メトリクスを決定する

特定のクエリー・ポイントに最も近いデータ・ポイントを特定するには、クエリー・ポイントと他のデータ・ポイント間の距離を計算する必要があります。これらの距離メトリクスは、クエリー・ポイントをさまざまな領域に分割する決定境界を形成するのに役立ちます。一般的に、決定境界はボロノイ図で視覚化されます。

選択できる距離の測定方法はいくつかありますが、この記事では次の点についてのみ説明します。

ユークリッド距離（p=2）： これは最も一般的に使用される距離測定であり、実数値のベクトルに限定されます。以下の式を使用して、クエリー・ポイントと測定対象の他のポイント間の直線を測定します。

マンハッタン距離（p=1）：これも、2点間の絶対値を測定するためによく使われる距離メトリクスです。これは、市街地の道路を経由してある住所から別の住所まで移動する方法を示すグリッドで視覚化されることが多いため、「タクシー距離」または「市街地ブロック距離」とも呼ばれます。

ミンコフスキー距離：この距離測定は、ユークリッド距離とマンハッタン距離の測定基準を一般化した形式です。以下の式のパラメーター「p」を使用すると、他の距離メトリックを作成できます。ユークリッド距離は「p」が2の場合にこの式で表され、マンハッタン距離は「p」が1の場合に表されます。

ハミング距離： この手法は通常、ブール値または文字列ベクトルで使用され、ベクトルが一致しないポイントを識別します。そのため、これはオーバーラップ・メトリクスとも呼ばれています。これは次の式で表すことができます。

例えば、次の文字列があった場合、2つの値のみが異なるため、ハミング距離は2になります。

KNNを計算する：kの定義

k-NNアルゴリズムのk値は、特定のクエリー・ポイントの分類を決定するためにチェックされる近傍の数を定義します。例えば、k=1の場合、インスタンスは最も近い単一の隣接インスタンスと同じクラスに割り当てられます。異なる値によって過剰適合または不足適合が発生する可能性があるため、kの定義はバランスを取る作業になる可能性があります。kの値が小さいと分散は高くなりますが、バイアスは弱くなります。一方、kの値が大きいとバイアスが強くなり、分散が低くなる可能性があります。kの選択は入力データに大きく依存します。外れ値やノイズの多いデータは、kの値が高いほどパフォーマンスが向上する可能性が高いためです。全体として、分類で同点にならないようにkを奇数にすることが推奨され、クロス検証戦術はデータセットに最適なkを選択するのに役立ちます。

k近傍法とPython

さらに深く理解するには、Python と scikit-learn (sklearn とも呼ばれます) を使用して、k-NN アルゴリズムについてさらに詳しく学習できます。Watson Studioのチュートリアルでは、このライブラリーの基本的な構文を学習できます。このライブラリーには、NumPy、pandas、Matplotlibなどの他の一般的なライブラリーも含まれています。次のコードは、KNNモデルを作成して予測する一例です。

from sklearn.neighbors import KNeighborsClassifier
model_name = ‘K最近傍分類子’
knnClassifier = KNeighborsClassifier(n_neighbors = 5, metric = ‘minkowski’, p=2)
knn_model = Pipeline(steps=[(‘preprocessor’, preprocessorForFeatures), (‘classifier’ , knnClassifier)])
knn_model.fit(X_train, y_train)
y_pred = knn_model.predict(X_test)

機械学習におけるk-NNの適用

k-NNアルゴリズムは、主に分類を中心にさまざまなアプリケーションで利用されてきました。そのユースケースには次のようなものがあります。

- データ前処理：データセットには欠損値が含まれることがよくありますが、KNNアルゴリズムは欠損データ補完と呼ばれるプロセスでそれらの値を推定できます。

- 推奨エンジン：Webサイトからのクリックストリーム・データを使用して、KNNアルゴリズムがユーザーに追加コンテンツを自動的に推奨するために使用されています。この研究（ibm.com外部へのリンク）では、ユーザーが特定のグループに割り当てられ、そのグループのユーザー行動に基づいて推奨事項が提示されることが示されています。ただし、KNNのスケーリングの問題を考慮すると、このアプローチは大規模なデータセットには最適ではない可能性があります。

- 金融：さまざまな金融業や経済界のユースケースでも使用されています。例えば、ある論文（ibm.com外部へのリンク）では、信用データにKNNを使用すると、銀行が組織または個人への融資のリスクを評価するのにどのように役立つかが示されています。ローン申込者の信用度を判断するために使用されます。別の学術誌（ibm.com外部へのリンク）では、株式市場予測、通貨交換レート、先物取引、マネーロンダリングの分析における使用について取り上げています。

- ヘルスケア：KNNはヘルスケア業界にも応用されており、心臓発作や前立腺がんのリスクを予測しています。このアルゴリズムは、最も可能性の高い遺伝子発現を計算することによって機能します。

- パターン認識：KNNは、テキスト内のパターンの識別や数字の分類（ibm.com外部へのリンク）にも役立ちます。これは、フォームや郵送用封筒に記載されている手書きの番号を識別する際に特に役立ちます。

KNNアルゴリズムの長所と短所

他の機械学習アルゴリズムと同様、k-NNにも長所と短所があります。プロジェクトやアプリケーションによっては、それが適切な選択となる場合とそうでない場合があります。

メリット

- 適用が簡単：シンプルかつ高精度であるため、データ・サイエンスを学ぶ初心者はこのあるごリスムを初期の段階で学びます。

- 適応が簡単：新しいトレーニング・サンプルが追加されると、すべてのトレーニング・データがメモリーに保存されるため、アルゴリズムは新しいデータを考慮して調整されます。

- ハイパーパラメータが少ない：KNNに必要なのはk値と距離メトリックのみで、他の機械学習アルゴリズムと比較するとその必要数は少なくなります。

デメリット

- スケーリングがうまくいかない： KNNは遅延アルゴリズムであるため、他の分類器と比較して、より多くのメモリーとデータ・ストレージを消費します。これには、時間と費用の両方の観点からコストがかかる可能性があります。メモリーとストレージが増えるとビジネス経費が増加し、データが増えると計算にかかる時間が長くなります。計算の非効率性に対処するために、Ball-Treeなどのさまざまなデータ構造が作成されていますが、ビジネスの問題によっては、異なる分類子が最適な場合もあります。

- 次元の呪い：KNNアルゴリズムは次元の呪いに陥りやすく、高次元のデータ入力ではパフォーマンスが低下します。これはピーキング現象とも呼ばれ、アルゴリズムが最適な特徴数に達した後、特にサンプル・サイズが小さい場合に、追加の特徴によって分類エラーの量が増加します。

- 過剰適合になりやすい：「次元の呪い」により、KNNは過剰適合になりやすい傾向があります。これを防ぐために特徴選択と次元削減の手法が活用されていますが、kの値もモデルの動作に影響を与える可能性があります。kの値が低ければデータが過剰適合する可能性がありますが、kの値が高いと、より広い領域または近隣で値を平均化するため、予測値が「平滑化」される傾向があります。ただし、kの値が高すぎると、データが不足する可能性があります。