本文属于机器翻译版本。若本译文内容与英语原文存在差异，则一律以英文原文为准。

# 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` 参数。例如，如果初始数据集有 1000 个数据点，而 `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) 时间，以便将一批 n 个维度 d 数据点的维度减少到目标维度 k。`fjlt` 方法需要 O(nd log(d)) 时间，但仅在涉及的常量更大时使用。使用维度缩减会将噪点引入到数据中，这种噪点会降低预测准确度。

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

在推理过程中，算法会查询样本点 k-nearest-neighbors的索引。根据对数据点的参考，该算法进行分类或回归预测。它根据提供的分类标签或值进行预测。k-NN 提供三种不同类型的索引：平面索引、反向索引以及带有乘积量化的反向索引。您可以使用 `index_type` 参数指定类型。

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

当 k-NN 算法完成训练后，它会序列化三个文件以准备推理。
+ model\_algo-1：包含用于计算最近邻点的序列化索引。
+ model\_algo-1.labels：包含用于根据索引查询结果计算预测标签的序列化标签（np.float32 二进制格式）。
+ model\_algo-1.json：包含 JSON 格式的模型元数据，该元数据存储来自推理训练的 `k` 和 `predictor_type` 超参数以及其他相关状态。

借助 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"
}
```