翻訳は機械翻訳により提供されています。提供された翻訳内容と英語版の間で齟齬、不一致または矛盾がある場合、英語版が優先します。

k-NN アルゴリズムの仕組み

Amazon SageMaker k-nearest neighbors (k-NN) アルゴリズムは、入力データのサンプリング、ディメンション削減の実行、インデックスの構築を含むマルチステップトレーニングプロセスに従います。次に、インデックス化されたデータは推論中に使用され、特定のデータポイントの k に最も近い隣接を効率的に見つけ、隣接するラベルまたは値に基づいて予測を行います。

ステップ 1: サンプリングする

トレーニングデータセットからサンプリングするデータポイントの総数を指定するには、sample_size パラメータを使用します。たとえば、初期データセットに 1,000 個のデータポイントがあり、sample_size が 100 に設定されている場合 (インスタンスの総数は 2)、各ワーカーは 50 ポイントをサンプリングします。合計 100 個のデータポイントが収集されます。サンプリングはデータポイントの数を基準に線形時間で実行されます。

ステップ 2: 次元削減を実行する

k-NN アルゴリズムの現在の実装には、2 つの次元削減手法が用意されています。手法を指定するには、dimension_reduction_type ハイパーパラメータを使用します。sign 法は、ランダム符号の行列を用いる線形射影を使用するランダム射影を指定します。一方、fjlt 法は、フーリエ変換に基づく手法である高速 Johnson-Lindenstrauss 変換を指定します。どちらの方法でも L2 と内積距離は保持されます。fjlt メソッドは、ターゲットディメンションが大きく、CPU推論でパフォーマンスが向上する場合に使用します。これらの手法は、計算の複雑性が異なります。sign 法は、次元 d の n 個のポイントのバッチの次元を標的次元 k に縮小するために O(ndk) 時間を必要とします。fjlt 法は O(nd log(d)) 時間を必要としますが、関係する定数はより大きくなります。次元削減を使用すると、データにノイズが入り、このノイズが予測精度を低下させる可能性があります。

ステップ 3: インデックスを構築する

推論中、アルゴリズムはサンプルポイントの k-nearest-neighborsのインデックスをクエリします。ポイントへの参照に基づいて、アルゴリズムは分類または回帰予測を行います。提供されたクラスラベルまたは値に基づいて予測を行います。k-NN は、フラットインデックス、逆インデックス、および直積量子化を使用する逆インデックスの 3 タイプのインデックスを提供します。このタイプは index_type パラメータで指定します。

モデルをシリアル化する

k-NN アルゴリズムはトレーニングを終了すると、推論に備えて 3 つのファイルをシリアル化します。

k-NN の現在の実装では、メタデータファイルを修正して予測の計算方法を変更できます。たとえば、k を 10 に変更したり、predictor_type を regressor に変更したりできます。

{
  "k": 5,
  "predictor_type": "classifier",
  "dimension_reduction": {"type": "sign", "seed": 3, "target_dim": 10, "input_dim": 20},
  "normalize": False,
  "version": "1.0"
}