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

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

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

ステップ 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 つのファイルをシリアル化します。

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

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

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

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

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