本文為英文版的機器翻譯版本，如內容有任何歧義或不一致之處，概以英文版為準。

# k-NN 演算法的運作方式
<a name="kNN_how-it-works"></a>

Amazon SageMaker AI k 近鄰 (k-NN) 演算法遵循多步驟訓練程序，其中包括對輸入資料進行取樣、執行降維和建立索引。然後在推論過程中使用索引資料來有效地找到給定資料點的 k 近鄰，並根據相鄰的標籤或值進行預測。

## 步驟 1：範例
<a name="step1-k-NN-sampling"></a>

請使用 `sample_size` 參數指定要從訓練資料集採樣的資料點總數。例如，如果初始資料集有 1,000 個資料點，且 `sample_size` 設為 100，則當執行個體總數為 2 時，每個工作者的取樣點為 50。總共收集 100 個資料點。資料點抽樣依線性時間執行。

## 步驟 2：執行降維
<a name="step2-kNN-dim-reduction"></a>

k-NN 演算法目前的實作有兩種降維方法。您要在 `dimension_reduction_type` 超參數中指定方法。`sign` 方法指定隨機投影，使用利用隨機符號矩陣的線性投影，而 `fjlt` 方法指定以傅立葉轉換為基礎的快速 Johnson-Lindenstrauss 轉換。兩種方法都保留 L2 和內部產品距離。當目標維度很大且使用 CPU 推論有更好的效能時，應該使用 `fjlt` 方法。這些方法的運算複雜性各有不同。`sign` 方法需要 O (ndk) 時間，將維度 d 之一批 n 點的維度降到目標維度 k 的維度。`fjlt` 方法需要 O(nd log(d)) 時間，但涉及的常數較。使用降維會引進資料雜訊，而此雜訊會降低預測的準確性。

## 步驟 3：建立索引
<a name="step3-kNN-build-index"></a>

在推論期間，演算法會查詢範例點的 k 近鄰索引。根據參考點，演算法可建立分類或迴歸預測。它可以所提供的類別標籤或值為基礎建立預測。k-NN 提供三種不同類型的索引：一般索引、反轉索引和具產品量化的反轉索引。您要使用 `index_type` 參數指定類型。

## 序列化模型
<a name="kNN-model-serialization"></a>

當 k-NN 演算法完成訓練後，會序列化三個檔案以準備推論。
+ model\$1algo-1：包含序列化的索引以計算近鄰。
+ model\$1algo-1.labels：包含序列化的標籤 (np.float32 二進位格式)，根據索引的查詢結果計算預估標籤。
+ model\$1algo-1.json：包含 JSON 格式模型的中繼資料，存放來自訓練的 `k` 和 `predictor_type` 超參數以供推論，以及其他相關狀態。

透過 k-NN 目前的實作，您可以修改中繼資料檔案，變更計算預測的方式。例如，您可將 `k` 變更為 10，或將 `predictor_type` 變更為*迴歸器*。

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