本文属于机器翻译版本。若本译文内容与英语原文存在差异,则一律以英文原文为准。
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:包含格式化的模型元数据,该元数据存储来自训练的
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" }