k-NN 算法的工作原理 - Amazon SageMaker
Amazon Web Services 文档中描述的 Amazon Web Services 服务或功能可能因区域而异。要查看适用于中国区域的差异,请参阅 中国的 Amazon Web Services 服务入门 (PDF)

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

k-NN 算法的工作原理

Amazon SageMaker k-最近邻 (k-nn) 算法遵循多步训练过程,其中包括对输入数据进行采样、执行降维和建立索引。然后,在推理过程中使用索引数据来有效地找到给定数据点的 k 个最近邻域,并根据相邻的标签或值进行预测。

步骤 1:样本

要指定从训练数据集中采样的数据点总数,请使用 sample_size 参数。例如,如果初始数据集有 1000 个数据点,而 sample_size 设置为 100,使用的实例总数为 2,则每个工作实例将采样 50 个点。总共将收集 100 个数据点。在采样运行过程中,时间与数据点数呈线性方式。

步骤 2:执行维度缩减

k-NN 算法的当前实施有两种维度缩减方法。您可以在 dimension_reduction_type 超参数中指定方法。sign 方法指定一个随机投影,使用采用随机符号矩阵的线性投影,而 fjlt 方法指定一个快速 Johnson-Lindenstrauss 变换,这是一种基于傅立叶变换的方法。这两种方法保留 L2 和内积距离。当目标维度较大且CPU推理性能更好时,应使用该fjlt方法。这些方法的计算复杂性不同。sign 方法需要 O(ndk) 时间,以便将一批 n 个维度 d 数据点的维度减少到目标维度 k。fjlt 方法需要 O(nd log(d)) 时间,但仅在涉及的常量更大时使用。使用维度缩减会将噪点引入到数据中,这种噪点会降低预测准确度。

步骤 3:构建索引

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

序列化模型

当 k-NN 算法完成训练后,它会序列化三个文件以准备推理。

  • model_algo-1:包含用于计算最近邻点的序列化索引。

  • model_algo-1.labels:包含用于根据索引查询结果计算预测标签的序列化标签(np.float32 二进制格式)。

  • model_algo JSON -1.json:包含格式化的模型元数据,该元数据存储来自训练的kpredictor_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" }