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

Amazon SageMaker AI の k 最近傍 (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 近傍についてインデックスに対してクエリを実行します。ポイントへの参照に基づいて、アルゴリズムは分類または回帰予測を行います。提供されたクラスラベルまたは値に基づいて予測を行います。k-NN は、フラットインデックス、逆インデックス、および直積量子化を使用する逆インデックスの 3 タイプのインデックスを提供します。このタイプは index_type パラメータで指定します。

モデルをシリアル化する

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

• model_algo-1: 最近傍を計算するためのシリアル化されたインデックスを含みます。

• model_algo-1.labels: インデックスからのクエリ結果に基づいて予測ラベルを計算するためのシリアル化ラベル (np.float32 バイナリ形式) を含みます。

• model_algo-1.json: 推論のためにトレーニングから取得した k および predictor_type ハイパーパラメータを他の関連する状態とともに保存する、JSON 形式のモデルメタデータを含みます。

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"
}