k近傍法アルゴリズム（KNNまたはk-NNとも呼ばれる）は、ノンパラメトリックな教師あり学習の分類子であり、近接性を利用して個々のデータ・ポイントのグループ化に関する分類や予測を行います。 これは回帰問題または分類問題のどちらにも使用できますが、一般的には分類アルゴリズムとして使用され、類似したポイントが相互に近接して存在するという前提に基づいています。
分類問題の場合、クラス・ラベルは多数決に基づいて割り当てられます。つまり、特定のデータ・ポイントの周囲で最も頻繁に表現されるラベルが使用されます。 これは技術的には「相対多数決」と見なされますが、文献では一般的に「多数決」という用語が使用されています。 これらの用語の違いは、「多数決」では技術的には50%を超える過半数が必要となりますが、これは主にカテゴリーが2つしかない場合に機能します。 複数のクラス（例えば4つのカテゴリー）がある場合、クラスについて結論を出すために必ずしも50%の投票が必要になるわけではありません。投票が25%を超えたクラス・ラベルを割り当てることもあります。 ウィスコンシン大学マディソン校では、これについて この資料 （PDF, 1.2 MB） （ibm.com外部のリンク）で例を使用してわかりやすく要約しています。
回帰問題は分類問題と同様の概念を使用しますが、この場合、k個の最近傍の平均を取って分類に関する予測を行います。 ここでの主な違いは、分類が離散値に使用されるのに対して、回帰は連続値に使用されるという点です。 ただし、分類を行う前に距離を定義する必要があります。 ユークリッド距離が最も一般的に使用されますが、これについては後で詳しく説明します。
また、KNNアルゴリズムは「遅延学習（怠惰学習）」モデルの一種であることにも注意してください。つまり、トレーニング段階ではなくトレーニング・データ・セットのみを保存します。 またこれは、分類や予測を行う際にすべての計算が行われることも意味します。 すべてのトレーニング・データの保管はメモリーに大きく依存するため、インスタンス・ベースまたはメモリー・ベースの学習方法とも呼ばれます。
KNNモデルに関する初期の発想は、Evelyn Fix氏とJoseph Hodges氏によって1951年の 論文 （PDF、1.1 MB） （ibm.com外部のリンク） で発表され、その概念を広げたのがThomas Cover氏の 研究 （PDF、1 MB）（ibm.com外部のリンク）「Nearest Neighbor Pattern Classification」です。 かつてほどの人気はありませんが、その単純さと正確さによって、データ・サイエンスで学ぶ最初のアルゴリズムの1つとなっています。 しかし、データ・セットが大きくなると、KNNの効率は低下し、モデル全体のパフォーマンスが低下します。 一般的に、KNNは単純な推奨システム、パターン認識、データ・マイニング、金融市場予測、侵入検知などに使用されます。
要約すると、k近傍法アルゴリズムの目標は、特定の照会ポイントの最近傍を識別し、そのポイントにクラス・ラベルを割り当てることです。 これを行うために、KNNにはいくつかの要件があります。
距離メトリックの決定
特定の照会ポイントに最も近いデータ・ポイントを判別するには、照会ポイントと他のデータ・ポイントの間の距離を計算する必要があります。 これらの距離メトリックは、照会ポイントを異なる領域に分割する決定境界を形成するのに役立ちます。 一般的に、決定境界はボロノイ図で視覚化されます。
選択できる距離指標はいくつかありますが、この記事では以下の項目についてのみ説明します。
ユークリッド距離（p=2）： これは最も一般的に使用される距離指標であり、実数値ベクトルに制限されます。 次の式を使用して、照会ポイントと測定対象の他のポイントの間の直線を測定します。
マンハッタン距離（p=1）：これも一般的な距離指標で、2点間の絶対値を測定します。 これは、一般的にグリッドで視覚化されるため、タクシー距離または市街地ブロック距離とも呼ばれ、市街地の道路を通ってある住所から別の住所に移動する経路を示します。
ミンコフスキー距離：この距離指標は、ユークリッド距離メトリックとマンハッタン距離メトリックを一般化した形式です。 次の式のパラメータpを使用して、他の距離メトリックを作成できます。 pが2に等しい場合、この数式はユークリッド距離を表し、pが1に等しい場合、この数式はマンハッタン距離を表します。
ハミング距離：通常、この手法は、ブール値や文字列のベクトルで使用され、ベクトルが一致しないポイントを識別します。 そのため、オーバーラップ・メトリックとも呼ばれています。 これは次の式で表すことができます。
例えば、次の文字列がある場合、2つの値だけが異なっているため、ハミング距離は2になります。
k-NNアルゴリズムのk値は、特定の照会ポイントの分類を決定するためにチェックされる近傍の数を定義します。 例えば、k=1の場合、インスタンスは最も近い1つの近傍と同じクラスに割り当てられます。 kを定義する際には、その値によってオーバー・フィットやアンダー・フィットにつながる可能性があるため、バランスに注意する必要があります。 kの値を小さくすると、分散は大きくなりますが、バイアスは小さくなります。逆に、kの値を大きくすると、バイアスは大きくなりますが、分散は小さくなります。 多くの外れ値やノイズを持つデータでは、kの値を大きくすることでより良好な結果を得られる可能性があるため、入力データを十分に考慮してkを選択する必要があります。 全体的には、分類において同順位が発生することを回避するために、kには奇数を指定することをお勧めします。また、交差検証戦術は、データ・セットに最適なkを選択するのに役立ちます。
k近傍法とPython
より深く掘り下げるには、Pythonとscikit-learn（sklearmとも呼ばれる）を使用して、k-NNアルゴリズムの詳細を学習できます。 Watson Studioの チュートリアル では、このライブラリーから基本的な構文を学習できます。このライブラリーには、NumPy、pandas、Matplotlibなどの一般的なライブラリーも含まれています。 次のコードは、KNNモデルを作成し、それを使用して予測する方法の例です。
from sklearn.neighbors import KNeighborsClassifier
model_name = 'K-Nearest Neighbor Classifier'
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アルゴリズムは、主に分類の分野において、さまざまな用途で使用されています。 以下は、いくつかのユース・ケースの例を示しています。
- データ前処理：データ・セットの値が欠落していることはよくありますが、KNNアルゴリズムでは、欠落データの代入として知られるプロセスでこれらの値を推定できます。
- 推奨エンジン：KNNアルゴリズムは、Webサイトからのクリック・ストリーム・データを使用して、追加コンテンツに関する推奨を自動的にユーザーに提供しています。 この調査 （ibm.com外部のリンク）は、ユーザーが特定のグループに割り当てられ、そのグループのユーザーの行動に基づいて推奨が行われることを示しています。 しかし、KNNのスケーリングの問題を考えると、このアプローチはより大きなデータ・セットには最適ではないかもしれません。
- 金融：このアルゴリズムは、さまざまな金融および経済の導入事例でも使用されています。 例えば、ある論文 （PDF、391KB） （ibm.com外部のリンク） では、信用データにKNNを使用することが、銀行が企業や個人に対する融資のリスクを評価するのに役立つことを示しています。 融資申請者の信用力を判断するために使用されます。 別のジャーナル （PDF、447 KB）（ibm.com外部のリンク） では、株式市場の予測、為替レート、先物取引、マネーロンダリングの分析での利用を紹介しています。
- 医療：KNNは、医療業界でも活用されており、心臓発作や前立腺癌のリスクを予測しています。 このアルゴリズムは、最も可能性の高い遺伝子発現を計算することで機能します。
- パターン認識：KNNは、テキストや数字の分類 （ibm.com外部のリンク）などのパターンの識別にも役立っています。 これは、伝票や封筒に記載されている手書きの数字を識別するのに特に有用です。
他の機械学習アルゴリズムと同様に、k-NNにも長所と短所があります。 プロジェクトや用途によって、適切な選択肢である場合と、そうでない場合があります。
- 実装が容易：このアルゴリズムの単純さと正確さによって、新しいデータ・サイエンティストが最初に学ぶ分類子の1つになっています。
- 適応が容易：このアルゴリズムでは、すべてのトレーニング・データがメモリーに保存されるため、新しいトレーニング・サンプルが追加された場合に新しいデータを考慮した調整が行われます。
- ハイパーパラメーターが少ない：KNNでは、k値と距離メトリックのみが必要です。これは、他の機械学習アルゴリズムと比較して少ない数です。
- 拡張に適していない：KNNは遅延アルゴリズムであるため、他の分類子と比較して多くのメモリーとデータ・ストレージを消費します。 そのため、時間と費用の両方の観点でコストがかかる可能性があります。 メモリーとストレージが増えるとビジネス・コストが増加し、データ量が増えると計算時間が長くなります。 計算の非効率性に対処するために、Ball-Treeなどのさまざまなデータ構造が作成されていますが、ビジネス上の問題によっては、別の分類子が理想的な場合もあります。
- 次元の呪い：KNNアルゴリズムは、次元の呪いの犠牲になる傾向があります。これは、高次元のデータ入力では十分に機能しないことを意味します。 これは、ピーキング現象 （PDF、340MB） （ibm.com外部のリンク）とも呼ばれ、アルゴリズムが最適な数の特徴量に達した後に、特にサンプル・サイズが小さい場合、追加の特徴量によって分類エラーの量が増加します。
- オーバーフィットする傾向：「次元の呪い」のために、KNNでは、オーバーフィットしやすいという傾向もあります。 これが起こるのを回避するために、特徴量選択と次元削減の手法が活用されていますが、kの値もモデルの動作に影響を与える可能性があります。 kの値を小さくすると、データをオーバーフィットする可能性があります。一方、kの値を大きくすると、より広い範囲（近傍）で値が平均化されるため、予測値が「平滑化」される傾向があります。 しかし、kの値が大きすぎると、データをアンダーフィットする可能性があります。
IBM Cloud Pak for Dataは、任意のクラウド上で、すべてのデータをAIとアナリティクスで使用可能にするデータ・ファブリックを提供するオープンで、拡張可能なデータ・プラットフォームです。
AIモデルを構築、実行、管理します。 オープンソース・コードやビジュアル・モデリングを使用して、任意のクラウド上でデータを準備し、モデルを構築できます。 結果の予測と最適化を行うこともできます。
堅固なパフォーマンスを実現するために構成および最適化されたフルマネージドのSQLクラウド・データベース、Db2 on Cloudをご紹介します。