なんぞそれ？
k近傍法(K-Nearest Neighbor Algorithm)とは、機械学習の教師あり分類アルゴリズムの1つです。
KNNによる分類の特徴は、未知のデータに着目した際にそのデータの近隣情報に基づき、分類結果を予測することです。
K近傍法では、データ空間のユークリッド距離(またはマンハッタン距離)で最も近い点を探索する「最近傍探索問題」に基づき分類が実行されます。
長所と短所
メリット
-
実装が容易
このアルゴリズムの単純さと正確さが手伝い、新米のデータサイエンティストが最初に学ぶ分類子の1つになっているほどだとか。 -
適応が容易
このアルゴリズムでは、すべてのトレーニングデータがメモリーに保存されるため、新しいトレーニングサンプルが追加された場合に新しいデータを考慮した調整が行われます。 -
ハイパーパラメーターが少ない
KNNではk値と距離メトリックのみが必要です。これは他の機械学習アルゴリズムと比較して少ないです。
デメリット
-
拡張に適していない
KNNは遅延アルゴリズムであるため、他の分類子と比較して多くのメモリとストレージを消費します。
そのため、時間と費用の両方の観点でコストがかかる可能性があります。
メモリとストレージが増えるとビジネスコストが増加し、データ量が増えると計算時間が長くなります。
計算の非効率性に対処するために、Ball-Treeなどのさまざまなデータ構造が作成されていますが、ビジネス上の問題によっては、別の分類子が理想的な場合もあります。 -
次元の呪い
KNNアルゴリズムは、次元の呪いの犠牲になる傾向があります。つまりは高次元のデータ入力では十分に機能しないことを意味します。
これは、ピーキング現象とも呼ばれ、アルゴリズムが最適な数の特徴量に達した後に、特にサンプルサイズが小さい場合、追加の特徴量によって分類エラーの量が増加します。 -
オーバーフィットする傾向
次元の呪いのために、KNNでは、オーバーフィットしやすいという傾向もあります。
これが起こるのを回避するために、特徴量選択と次元削減の手法が活用されていますが、kの値もモデルの動作に影響を与える可能性があります。
kの値を小さくすると、データをオーバーフィットする可能性があります。
一方、kの値を大きくすると、より広い範囲（近傍）で値が平均化されるため、予測値が平滑化される傾向があります。
かといって、kの値が大きすぎるとデータをアンダーフィットする可能性が出てきます。
KNNの計算
距離メトリック
ユークリッド距離（p=2)
これは最も一般的に使用される距離指標であり、実数値ベクトルに制限されます。
この式を使用して、照会ポイントと測定対象の他のポイントの間の直線を測定します。
$$d(x,y)=(\sum_{i=1}^{n}|x_i - y_i|^2)^\frac{1}{2} =\sqrt{\sum_{i=1}^{n}(x_i - y_i)^2} $$
マンハッタン距離（p=1）
これも一般的な距離指標で、2点間の絶対値を測定します。
一般的にグリッドで視覚化されるため、タクシー距離または市街地ブロック距離とも呼ばれ、市街地の道路を通ってある住所から別の住所に移動する経路を示します。
$$d(x,y)=(\sum_{i=1}^{n}|x_i - y_i|^1)^\frac{1}{1} =\sum_{i=1}^{n}|x_i - y_i| $$
ミンコフスキー距離 ミノフスキー粒子
この距離指標は、ユークリッド距離メトリックとマンハッタン距離メトリックを一般化した形式です。 次の式のパラメータpを使用して、他の距離メトリックを作成できます。 pが2に等しい場合、この数式はユークリッド距離を表し、pが1に等しい場合、この数式はマンハッタン距離を表します。
$$d(x,y)=(\sum_{i=1}^{n}|x_i - y_i|^p)^\frac{1}{p}$$
kの定義
k-NNアルゴリズムのk値は、特定の照会ポイントの分類を決定するためにチェックされる近傍の数を定義します。
例えば、k=1の場合、インスタンスは最も近い1つの近傍と同じクラスに割り当てられます。
kを定義する際には、その値によってオーバー・フィットやアンダー・フィットにつながる可能性があるため、バランスに注意する必要があります。
kの値を小さくすると、分散は大きくなりますがバイアスは小さくなります。逆にkの値を大きくすると、バイアスは大きくなりますが分散は小さくなります。
多くの外れ値やノイズを持つデータでは、kの値を大きくすることでより良好な結果を得られる可能性があるため、入力データを十分に考慮してkを選択する必要があります。
全体的には、分類において同順位が発生することを回避するために、kには奇数を指定することをお勧めします。
また、交差検証戦術は、データ・セットに最適なkを選択するのに役立ちます。
あとがき
今回はk近傍法について何となくまとめてみました。
何日か後に見たら全部頭から抜けてる気がしますねぇ…。
記Q&K