k最近傍法と高次元データ
1. 序章
このチュートリアルでは、k最近傍アルゴリズムについて学習します。 これは、基本的な機械学習モデルです。 分類タスクと回帰タスクの両方に適用できます。 それでも、それを分類タスクに適用するのがより一般的です。
精度を上げるために値と距離のメトリックを選択する方法を探ります。 次に、アルゴリズムが高次元データセットでどのように動作するかを分析します。 最後に、高次元性に関連する問題の潜在的な治療法について説明します。
2. k-最近傍
k最近傍法（k-NN）アルゴリズムは、類似したアイテムが互いに近いことを前提としています。そこで、最も近い近傍を調べることによってデータポイントを決定します。
新しい観測の結果を予測するために、最も近い過去の観測を評価します。 これらの隣接する観測値に基づいて予測を行います。 平均を直接取得することも、加重平均を使用することもできます。
k-NNアルゴリズムには、いくつかの利点があります。
- 主なアイデアはシンプルで実装が簡単です
- インスタンスベースであり、追加のトレーニングフェーズは必要ありません
- このアルゴリズムは、分類タスクと回帰タスクの両方に適しています
- データセットにいつでも簡単に新しい観測値を追加できます
- 出力は理解しやすく、解釈しやすい
- 調整するハイパーパラメータは1つだけです（）
反対に、いくつかの欠点があります。
- アルゴリズムは過去の観察に依存します
- ノイズの多いデータ、外れ値、欠落値に非常に敏感です
- 同種の機能が必要なため、機能のスケーリングなどのデータ前処理が必要です
- カテゴリ機能を操作するのは難しい
- 大規模なデータセットで距離を計算するにはコストがかかる
- 高次元データの距離を計算するにはコストがかかる
2.1. 値の選択
可能性のある同点を排除するために奇数として選択するのが一般的な方法です。値が偶数の場合、二項分類で投票数が等しくなる可能性があります。
ここで、異なる値を選択すると、異なる分類結果が得られます。 したがって、k-NNアルゴリズムを使用する場合、値を決定することは重要なステップです。
結果として、の選択は決定境界の形状に影響を与えます。
大きな値を選択すると、すべてをより可能性の高いクラスとして分類することにより、バイアスが高くなります。その結果、個々のポイントをあまり重視せずに、クラス間の決定境界がスムーズになります。
逆に、値が小さいと分散が大きくなり、出力が不安定になります。トレーニングセットを少し変更すると、分類境界が大きく変更されます。 この効果は、交差するクラスでより顕著になります。
したがって、出力を観察して、テストセットと検証セットに基づいて値を選択する必要があります。 トレーニングと検証のエラーは、k-NN分類器の動作に関する良いヒントを提供します。
トレーニングエラーは、= 1の場合に最小（0）です。 大きくなるにつれて、トレーニングエラーは予想どおりに大きくなります。 一方、値が小さすぎたり大きすぎたりすると、検証エラーが高くなります。 値の適切な選択は、検証エラーが最小になる場所です：
2.2. 距離関数
距離の計算に使用されるメトリックは、k-NNアルゴリズムのハイパーパラメーターではありません。 それでも、距離メトリックの選択は結果を変更し、モデルの成功に影響を与えます。
ユークリッド距離は、データポイント間の距離を計算するための最も一般的な距離メトリックです。ただし、手元のデータセットのサイズとディメンションに応じて、距離メトリックを選択する必要があります。
よく知られていて一般的に使用されているメトリックを調べてみましょう。 ミンコフスキー距離は、n次元空間の2点xとyの間の距離を測定するための一般化されたメトリックです。
マンハッタン距離（街区またはL1距離）は、ミンコウスキーの特殊なケースであり、p=1に設定します。
言い換えると、xとyの間の距離は、デカルト座標間の絶対差の合計です。
ユークリッド距離は、ミンコフスキー距離のもう1つの特殊なケースであり、p=2です。
ユークリッド空間の点xとyの間の距離を表します。
チェビシェフ距離は次の場合です：
実数値のベクトル空間でミンコウスキーの差のすべてのバリエーションを使用できます。 値を大きくすると距離が変わるため、決定境界は次のようになります。
高次元のデータセットでは、小さい値を使用する方が有利です。距離の計算は、小さい値を使用すると高速になるためです。 したがって、マンハッタン距離は、非常に高次元のデータセットに最適なオプションです。
ハミング距離は、実数値のベクトルに加えて整数値のベクトル空間に使用できる距離測度です。 これは通常、等しくない文字間の距離を測定することにより、等しい長さの文字列を比較するために使用されます。
ジャッカード距離は、ブール値のベクトル間の距離を見つけるのに適した尺度です。 サンプルセット全体で重複するフィーチャを計算します。
コサイン類似度メジャーは、三角不等式を保持していないため、メトリックではありません。 しかし、それは文書や遺伝子配列などのベクターオブジェクトを分類するために採用されています。 フィーチャ内の特定のインスタンスの頻度を測定します。
3. 高次元性
k-NNアルゴリズムのパフォーマンスは、特徴の数が増えるにつれて悪化します。したがって、次元の呪いの影響を受けます。 なぜなら、高次元空間では、k-NNアルゴリズムは2つの困難に直面しているからです。
- 距離を計算し、高次元空間で最も近い近傍を見つけることは、計算コストが高くなります
- 同様のポイントが密接に位置しているという私たちの仮定は破られます
特徴の数が増えると、データポイント間の距離が目立たなくなります。 さらに、隣人を見つけるためにカバーする必要のある総面積が増加します。
データセットに多数の特徴があり、各特徴の値が[0、1]の範囲にある単純な設定を考えてみましょう。 10に固定し、（観測数）を1000に固定します。 さらに、各機能の値が均一に分布していると仮定しましょう。
この設定で、=10個のデータポイントを含む立方体の辺の長さを調べてみましょう。
たとえば、= 2の場合、0.1 0.1の正方形は総面積の1/100をカバーし、合計10のデータポイントをカバーします。
fを=3にインクリメントすると、ボリュームの1/100をカバーするために、辺の長さが0.63の立方体が必要になります。
を増やし続けると、辺の長さは指数関数的に増加します。 辺の長さは次のように定式化できます。
= 100の機能、=0.955であることがわかります。 同様の方法で繰り返すと、=1000は=0.995になります。
結果として、同様の観測が近いという最初の仮定は失敗します。 すべてのデータポイント間の距離がますます小さくなるにつれて、同様の観測値が高次元のデータセットに密集しているとは言えません。
それでも、基本的な構造を失うことなく、データセットを低次元で表現する方法があります。 潜在的な治療法を見てみましょう：
3.1. データ削減
元のプロパティ次元削減を維持しながら、低次元空間で高次元データを表現することを呼びます。
特徴選択手法を使用して、データセットからより冗長な特徴を排除できます。 この方法により、最も関連性の高い機能のみが保持されます。
または、特徴抽出を使用してデータを低次元空間にマッピングすることもできます。 新しい機能セットは、必ずしも元のコンポーネントのサブセットである必要はありません。 通常、新しい機能は既存の機能を組み合わせて生成されます。 たとえば、主成分分析（PCA）は線形マッピングを適用して、最小限の数の機能で情報を最大化します。
PCAとカーネル法は、データセットの真の次元が実際の表現よりも低い場合に特に有益です。 たとえば、マッピング後に2つのフィーチャを使用して、3D空間の2次元平面上の点を表すことができます。
もう1つのデータ削減手法は、より少ない観測値でより小さな形式でデータを表すことです。 計算数が減少すると、数減少アルゴリズムがk-NNパフォーマンスに役立ちます。
3.2. 近似k-NNの使用
場合によっては、おおよその解を見つけることが許容されます。 正確な解の検索にコストがかかりすぎる場合は、正確な結果を保証せずに近似アルゴリズムを採用できます。 高次元類似性検索手法により、高次元設定でのk-NNの高速近似が可能になります。
局所性鋭敏型ハッシュ（LSH）アルゴリズムは、同様のアイテムを確率の高いバケットにハッシュします。 名前が示すように、同様のアイテムが最後に同じバケットに入れられることを期待しています。
ハッシュテーブルの使用は、クエリとデータ生成の両方で簡単かつ効率的です。 このように、LSH法を使用して、近似の最も近い近傍をすばやく見つけます。
ランダム射影では、任意の2点間の距離を（）の係数で変更することにより、m点を高次元空間から次元のみに変換できます。 したがって、マッピングはユークリッド距離を保持します。 したがって、k-NNアルゴリズムを実行すると、はるかに低いコストで同じ結果が生成されます。
ランダム射影フォレスト（rpForests）は、高速近似クラスタリングを実行します。 それらは、最も近い隣人を迅速かつ効率的に近似します。
4. 結論
この記事では、k-NNアルゴリズムについて説明しました。 ハイパーパラメータの変更が結果にどのように影響するか、およびそのハイパーパラメータを調整する方法を分析しました。
次に、高次元データセットでのk-NNアルゴリズムの動作を調べました。 最後に、近似アルゴリズムを使用してパフォーマンスの問題を克服する方法について説明しました。
